Problem Solving by Searching

Artificial Intelligence Chapter 3

Date: 23.03.20 ~ 23.03.26

Writer: 9tailwolf


Introduction

This Chapter deals with Problem Solving Agent. We Study about definition of problem and solution in some condition(Informed Search).


Problem Solving Agent

Definition of Problem
  • Inital State
  • Action : Actions that agent can do in state \(s\)
  • Transition Model : Description of what each action does. \(Result(s,a)\) returns the state thal result from doing action \(a\) in state \(s\)
  • Goal Test : Determines whether a given state is a goal
  • Path Cost : The cost that need in each actions
Problem Type
  • Deterministic, Fully observable : Single State Problem
  • Non-observable : Conformant Problem
  • Non-deterministic, Partially observable : contingency Problem
  • Unknown State Space : Exploration problem


Searching Algorithm

Problem Solving by search algorithm
  1. Define problems
  2. Make action tree
  3. Choose node(=action that can do in parents node).
  4. Find goal.


Measuring Problem solving performance
  • Completeness : Can we find solution ?
  • Optimality : Does answer is optimal ?
  • Time Complexity : How long does algorithm takes ?
  • Space Complexity : How much memory does algorithm takes ?


Uninformed Search Algorithm

Breadth-First Search is algorithm that expand closest node. It works when all action have the same cost. It is complete and optimal. Time complexity of BFS is \(O(b^{d})\), Space complexity of BFS is \(O(b^{d})\).

Algorithm

def BFS(action, first_node, solution):
    node = first_node
    queue = Queue(node)
    explored = {node}
    while queue:
        node = queue.pop()
        if node == solution:
            return node
        else:
            for child in action(node):
                if child not in explored:
                    queue.push(child)
                    explored.add(child)
    return Fail


Uniform Cost Search is the algorithm that expand the node with the lowest path cost. It is complete when step cost is larger then inital value \(\epsilon\) and it is optimal. Time complexity of Uniform cost search is \(O(b^{1+\frac{C^{*}}{\epsilon}})\), Space complexity of uniform cost search is \(O(b^{1+\frac{C^{*}}{\epsilon}})\).

Algorithm

def Uniform_Cost_Search(action, cost, first_node,solution):
    reached = {}
    cost[first_node] = 0
    while cost:
        node = cost.pop()
        reached.add(node)
        if node==solution:
            return node
        for child,cost in action(node):
            if child is not in reached and child.cost > node.cost + cost:
                cost[child] = node.cost + cost
    return Fail


Depth-First Search is the algorithm that expand the deepest node in the current frontier of the search tree. It is not complete by loop(if no loop, then complete), and not optimal. Time complexity of depth first search is \(O(b^{d})\), Space complexity of depth first search is \(O(bd)\).

Algorithm

def DFS(action, first_node, solution):
    node = first_node
    stack = Stack(node)
    explored = {node}
    while stack:
        node = stack.pop()
        if node == solution:
            return node
        else:
            for child in action(node):
                if child not in explored:
                    stack.push(child)
                    explored.add(child)
    return Fail


Depth-Limited Search is the DFS algorithm with limited depth \(l\). When \(l\) is smaller then depth of solution, it is not complete. When \(l\) is larger then depth of solution, and not optimal. Time complexity of depth limited search is \(O(b^{d})\), Space complexity of depth limited search is \(O(bd)\).

Algorithm

def DLS(action, first_node, solution,l):
    node = first_node
    stack = Stack(node)
    explored = {node}
    while stack:
        node,d = stack.pop()
        if node == solution:
            return node
        else:
            for child in action(node):
                if child not in explored and d<l:
                    stack.push((child,d+1))
                    explored.add(child)
    return Fail


Iterative Deeping Search is the DFS algorithm with limited depth \(l\), and \(l\) gradually increase. It is complete, and optimal. Time complexity of iterative deeping search is \(O(b^{d})\), Space complexity of iterative deeping search is \(O(bd)\).

Algorithm

def IDS(action, first_node, solution):
    l = 1
    while True:
        l += 1
        node = first_node
        stack = Stack(node)
        explored = {node}
        while stack:
            node,d = stack.pop()
            if node == solution:
                return node
            else:
                for child in action(node):
                    if child not in explored and d<l:
                        stack.push((child,d+1))
                        explored.add(child)
        if every(d)<l:
            return Fail


Bidirection search is the algorithm that execute BFS from start node and finish node. It is complete, and optimal. Time complexity of iterative deeping search is \(O(b^{\frac{d}{2}})\), Space complexity of iterative deeping search is \(O(b^{\frac{d}{2}})\).


Informed Search Algorithm

An informed search strategy is one that uses domain-specific hints about the location of goals.

Greedy best-first search is the algorithm that expand the closest node to goal. It is complete in finite state but not in infinite state. and not optimal. Time and space complexity of Greedy best-first search is \(O(V)\) in bad condition but \(O(bm)\) in good condition.

A* search is the algorithm that find a minimum cost path. Minimum cost is evaluated by sum of \(g(n)\), path cost between start to n node, and \(h(n)\), estimated cost between n node to solution. The condition to be optimal in A* search algorithm, \(h(n)\) would be admissable heuristic(=not overestimation. For example, straight line distance function.) and consistency(=monotonicity. Every nodes should satisf \(h(n) \leq cost(n,m) + h(m)\) when there is a action \(n\) to \(m\) condition.).

Proof of Optimality of A* search

  • When \(h(n)\) is admissable, then \(h(n)\) is consistancy : When there is a action \(n\) to \(m\), then \(f(m) = g(m) + h(m) = g(n) + cost(n,m) + h(m)\) Since \(h(n)\) is admissable, \(cost(n,m) + h(m) \geq h(n)\). Thus, \(g(n) + cost(n,m) + h(m) \geq g(n) + h(n) = f(n)\) , \(f(m) \geq f(n)\).

  • Whenever A* search select optimal path : Since the order of choosn path costs are increasing, non-optimal path isnt selected.

The properties of A search algorithm is as follows, It is complete and optimal, and the time complexity is \(exp(h \times l)\), space complexity is \(O(V)\)


Iteration-Deeping A*
  • IDA* Algorithm : Similar as Depth-limited search, but there is a difference between cost and depth.
  • Recursive best-first search : Find and expand node with minimum \(f(n)+cost(n,m)\) value.

Algorithm

def RBFS(problem, node, limit):
    if problem.goalTest():
        return solution(node)
    successors = []
    for action in problem.actions:
        successors.append(child(problem,node,action))
    if successors == None:
        return Fail, inf
    for s in successors:
        s.f = max(s.g+s.h,node.f)
    while:
        best = min(successors)
        if best.f>limit:
            return Fail
        result,best.f = RBFS(problem,vest,min(f_limit,min_2(successors)))
        if result != Fail:
            return result
  • MA* Algorithm : Memory Bounded A* search
  • SMA* Algorithm : Memory Bounded A* search. But when Memory is reached limit, then delete maximum cost node, and the oldest node when there is a overlapped maximum cost.