Beyond Classical Search

Artificial Intelligence Chapter 4

Date: 23.03.27 ~ 23.04.02

Writer: 9tailwolf


Introduction

Chapter 3 addressed a single category of problems: observable, deterministic, known environments where solution is a sequence of actions. In this chapter, we look at what happens when these assumptions are relaxed.


Local Search Algorithm in Discrete

Local search algorithms operate using a single current node rather than multiple paths and generaly move only to neighbors of that node. So they are not systematic, but use very little memory, and find solutions in large state space.

Hill Climbing

Hill Climbing is algorithm that move to highest value node in current state. But there is a problem. Algorithm state can go to local maximum. To solve this problem, there are algorithms such as allows sideway move in the same state, a limited sideway move algorithm, stochastic hill climbing, and random restart hill climbing.

Algorithm

def Hill_Climbing(problem):
    current = problem.inital
    while:
        neighber = max(state(current), key = state.value)
        if neighber.value <= current.value:
            return current
        current = neighber
Simulated annealing

Simulated annealing is algorithm that move to highest value node in current state but allow bad moves when there is no better state. It is combining hill climbing with a random work.

Algorithm

def Simulated_Annealing(problem,schedule):
    current = problem.initial
    turn = 0
    while:
        turn += 1
        T = schedule(turn) # probablity
        if T == 0:
            return current

        next = random(state(current))
        if next.value > current.value:
            current = next
        if probablity(exp((next.value-current.value)/T)):
            current = next

Local Beam Search is algorithm that move to highest value node in current state with number of k nodes. There is a difference with Random restart hill climbing, nodes can share their state information. To make diversity, algorithm can apply stochastic beam search.

Genetic Algorithm

Genetic algorithm is transformed Local Beam search algorithm that solve problem to combine two state. Algorithm is as follows, Initial Population - Fitness Function, Selection - Crossover - Mutation. First, algorithm start with inital Population. And algorithm evaluate each state by fitness function, which return high value when state close to solution. Next, select state according to fitness function. And crossover is carried out. Lastly, mutation happen. Mutation contribute to find solution.

Algorithm

def Genetic_Algorithm(population, fitness_function):
    while solution in population:
        new_population = set()
        for i in population:
            x = random(population,fitness_function)
            y = random(population,fitness_function)
            child = reproduce(x,y)
            
            if random(mutation)==True: 
                child = mutate(child)
            
            new_population.add(child)
        
        population = new_population


Searching with Nondeterministic Actions

When the environment is nondeterministic, the agent does not know what state it transitions to after taking an action. So the solution to such a problem is not a sequence but a conditional(contingency) plan.

And - Or Search Tree

And-Or Search is algorithm that choose action by Or function, which return actions in current state, then make path by and function, which shows every situations by action in current state.

Algorithm

def And_Or_Search_Tree(problem):
    Or_Search(problem.initial_state, problem, [])

def Or_Search(state,problem,path):
    if state == Goal:
        return []
    if state in path:
        return Fail
    for action in problem.action(state):
        plan = And_Search(result(action,state), problem, path + state)
        if plan is not Fail:
            return plan + action
    return Fail
            
def And_Search(state,problem,path):
    result = []
    for s in states:
        plan = Or_Search(s,problem,path)
        if plan == Fail:
            return Fail
        result.append((s,plan))
    return result


Searching with Partial Observation State

Searching with No Observations

When the environment is partially observable, the agent does not know for sure what state it is. In this environment, normaly we apply universal algorithm. The key concept required for soving partially observable problems is the belief state. In that environment, we can defind problem as follows.

  • State : If Physical problem \(P\) has \(N\) states, then it has \(2^{N}\) belief states.
  • Inital state : It can be \(P\), set of all states.
  • Actions : Suppose belief state \(b = {s_{1},s_{2}}\), it is possible that \(b_{1}\) action isn’t equal to \(b_{2}\) action. When every action affect nothing to environment, then Action set \(a\) can be union of all actions. but else, action set \(a\) can be intersection of all actions.
  • Transition : Suppose that \(b'\) is a belief state after action \(a\) in \(b\), then \(b'\) is union of result with possible combination of element in \(b\) and element in \(a\)
  • Goal Test : if every goal is in \(b\), then goal test passed.
  • Path Cost : Define path cost is complex.

The goal is making algorithm that reach goal for Initial state. It is Incremental belief-state search.

Searching with Partial Observations

If agent have sensor that can scan partial environment, we can define \(Percept(s)\) function and make \(b\) by observation prediction. Possible state \(b_{p}\) can be writen as \(b_{p} = \{o:o = Percept(s) \& s \in b\}\). Update of state can present as \(b' = \{s:o = Percept(s) \& s \in b\}\), as a result, result of action in state \(b\) can be \(b' = \{b:b=update(action(b,a),o) \& o \in b_{p}\}\)

solving of Partical Observation problem is similar as Or-And Search Tree.


Online Searching

Online searching is algorithm that execute action and computing interleave. Online searching has several characteristics.

  • Decreasing competitive ratio is a key to make more effcient algorithm.
  • It can apply in irreversible algorithm.
  • When problem has dead-end sector, probability of failure increase. Online searching is good for problem that doesn’t have dead-sector.

Algorithm

def Online_DFS_Search(goal):
    path = []
    result = dict()
    untried = dict()
    unbacktracked = dict()
    
    s,a = None,None
    
    while s_ = input():
        if s_ == goal:
            return stop
        if s_ not in untried.keys():
            untried[d_] = action(s_)
        
        if s != None:
            result[s,a] = s_
            unbacktracked[s_] = s
        
        if untried[s_] == None:
            if unbacktracked[s_] == None:
                reutrn Stop
            else:
                bs = unbacktracked[s_].pop()
                a = result[s_,action(bs)]
        else:
            a = untried[s_].pop()
        
        s = s_
        path.append(a)

There is a way to improve online search algorithm. Apply Random work for hill climbing isn’t useful. But by using memory, algorithm can be improved. LRTA*(Learning Real Time A star) is a algorithm that using heuristic function to estimate a cost for making goal.

def LRTA_Agent(goal):
    path = []
    result = dict()
    H = dict()
    
    s,a = None,None
    
    while s_ = input():
        if s_ == goal:
            return path
        if s_ not in H.keys():
            H[s_] = h(s_)
        
        if s != None:
            result[s,a] = s_
            H[s] = LRTA_Cost(s,b,result[s,b],H)
        a = action(min(b,key = LRTA_Cost(s_,b,result[s_,b],H)))
        s = s_
        path.append(a)
def LRTA_Cost(s,a,s_,H):
    if s_ is not defined:
        return h(s)
    else:
        return c(s,a,s_) + H(s_)