Artificial IntelligenceUninformed & Informed Search

Uninformed Search

AI
Views:

Uninformed Search means agent doesn’t know how close a state is to the goal state.
Strategies that know whether one non-goal state is “more promising” than another are called Informed Search or Heuristic Search strategies; they are covered in next article.

The root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. In general, all the nodes are expanded at a given depth in the search tree before any nodes at the next level are expanded.

BFS on a simple binary tree

Frontier: a FIFO queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//-----------------------BREADTH-FIRST-SEARCH--------------------------
function BREADTH-FIRST-SEARCH(problem) returns a solution, or failure
  node with STATE = problem.INITIAL-STATE, PATH-COST = 0
  if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
  frontier = a FIFO queue with node as the only element
  explored = an empty set
  loop do
    if EMPTY?(frontier ) then return failure
    node = POP(frontier ) /* chooses the shallowest node in frontier */
    add node.STATE to explored
    for each action in problem.ACTIONS(node.STATE) do
      child = CHILD-NODE(problem, node, action)
      if child.STATE is not in explored or frontier then
        //goal test is applied to each node when it is generated rather than when it is selected for expansion
        if problem.GOAL-TEST(child.STATE) then return SOLUTION(child)
        frontier = INSERT(child,frontier )

Evaluation

  • Complete:
    If the shallowest goal node is at some finite depth d, breadth-first search will eventually find it after generating all shallower nodes (provided the branching factor b is finite).
  • Not optimal:
    Only optimal when the path cost is a non-decreasing function of the depth of the node. The most common such scenario is that all actions have the same cost.
  • Time complexity:
    Imagine branching factor is $b$ (each state has $b$ successors).
    The root generates $b$ nodes at the first level.
    Each of these generates $b$ more nodes, for a total of $b^2$ at the second level.
    Each of these generates $b$ more nodes, yielding $b^3$ nodes at the third level, and so on.
    Suppose that the solution is at depth $s$.
    $$
    b + b^2 + b^3 + ··· + b^s = O(b^s)
    $$
BFS
  • Space complexity:
    There will be $O(b^{s−1})$ nodes in the explored set and $O(b^s)$ nodes in the frontier.

Always expands the deepest node in the current frontier of the search tree. The search proceeds immediately to the deepest level of the search tree, where the nodes have no successors. As those nodes are expanded, they are dropped from the frontier, so then the search “backs up” to the next deepest node that still has unexplored successors

DFS. The unexplored region is shown in light gray. Explored nodes with no descendants in the frontier are removed from memory. M is the only goal node.

Frontier: a LIFO queue

Evaluation

The properties of DFS strongly on whether the graph-search or tree-search version is used

  • Complete:
    Complete by graph-search if finite state space.
    Not Complete by treee-search, maybe follow the loop forever.
  • Not optimal:
    Return the leftmost solution.
  • Time complexity:
    Imagine branching factor is $b$.
    Suppose that maximum depth is $m$.
    Therefore, time complexity is $O(b^m)$, bigger than BFS.
    In tree search version, $m$ may be much larger than $d$ (the depth of shallowest solution).
DFS
  • Space complexity:
    Only needs to store a single path from the root to a leaf node, along with the remaining unexpanded sibling nodes for each node on the path. Once a node has been expanded, it can be removed from memory as soon as all its descendants have been fully explored.
    Therefore, DFS requires storage of only $O(bm)$ nodes. (if not use explored set)

The embarrassing failure of DFS in infinite state spaces can be alleviated by supplying DFS with a predetermined depth limit $l$. That is, nodes at depth $l$ are treated as if they have no successors.
DFS can be viewed as a special case of depth-limited search with $l=d$.

Evaluation

  • Not Complete: $l$ can be smaller than $s$.
  • Not optimal: $l$ can be bigger than $d$.
  • Time complexity: $O(b^l)$
  • Space complexity: $O(bl)$

Get DFS’s space advantage with BFS’s time advantage. Repeat the DFS by gradually increasing the depth limit, until a goal is found.

1
2
3
4
5
6
//-----------------------BREADTH-FIRST-SEARCH--------------------------
function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution, or failure
  for depth = 0 to ∞ do
    result ← DEPTH-LIMITED-SEARCH(problem, depth)
    if result != cutoff then return result 
    //the cutoff value indicates no solution within the depth limit.

Limit 0 is root node.
Run a DFS with depth limit 1. If no solution…
Run a DFS with depth limit 2. If no solution…
Run a DFS with depth limit 3. …

Four iterations of IDS on a binary tree.

Evaluation

  • Complete: same as BFS
  • Not optimal: same as BFS
  • Time complexity: $O(b^s)$
    asymptotically the same as BFS
    There is some extra cost for generating the upper levels multiple times, but it is not large.
    For example, if $b = 10$ and $s = 5$, the numbers are
    $N(IDS) = 50 + 400 + 3000 + 20000 + 100000 = 123450$
    $N(BFS) = 10 + 100 + 1000 + 10000 + 100000 = 111110$
  • Space complexity: $O(bs)$

BFS is only optima with non-decreasing cost function.
But UCS can find the least-cost(optimal) path with any step-cost function.
Instead of expanding the shallowest node, UCS expands the node n with the lowest $g(n)$ (which is path cost).

There are two other significant differences from breadth-first search.

  • The first is that the goal test is applied to a node when it is selected for expansion rather than when it is first generated. The reason is that the first goal node that is generated may be on a suboptimal path.
  • The second difference is that a test is added in the end in case a better path is found to a node currently on the frontier

Frontier: a priority queue (ordered by cumulative cost g(n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//----------------------- UNIFORM-COST-SEARCH--------------------------
function UNIFORM-COST-SEARCH(problem) returns a solution, or failure
  node with STATE = problem.INITIAL-STATE, PATH-COST = 0
  frontier = a priority queue ordered by PATH-COST, with node as the only element
  explored = an empty set
  loop do
    if EMPTY?(frontier ) then return failure
    node = POP(frontier ) /* chooses the lowest-cost node in frontier */
    if problem.GOAL-TEST(node.STATE) then return SOLUTION(node) //different goaltest location
    add node.STATE to explored
    for each action in problem.ACTIONS(node.STATE) do
      child = CHILD-NODE(problem, node, action)
      if child.STATE is not in explored or frontier then
        frontier ← INSERT(child,frontier )
      else if child.STATE is in frontier with higher PATH-COST then
        replace that frontier node with child
Example

Part of the Romania state space

The goal is to get from Sibiu to Bucharest.
Frontier={ Sibiu-0 }

The successors of Sibiu are Rimnicu Vilcea and Fagaras, with costs 80 and 99, respectively.
Frontier={ Rimnicu Vilcea-80, Fagaras-99 }

The least-cost node, Rimnicu Vilcea, is expanded.adding Pitesti with cost 80 + 97 = 177.
Frontier={ Fagaras-99, Pitesti-177 }

The least-cost node is now Fagaras, so it is expanded, adding Bucharest with cost 99 + 211 = 310.
Frontier={ Pitesti-177, Bucharest-310 }

Now a goal node has been generated, but UCS keeps going, no goal test now.
Choosing Pitesti for expansion and adding a second path to Bucharest with cost 80+ 97+ 101 = 278.
Frontier={ Bucharest(2)-278, Bucharest(1)-310 }

Choosing Bucharest(2), goal test now, the node to expand is goal state Bucharest with g-cost 278, the solution is returned.

Evaluation
UCS is guided by path costs rather than depths, so its complexity is not easily characterized in terms of $b$ and $d$.
Define some new variables:
$C^*$ is the cost for the optimal plan that reach the goal.
$\epsilon$ is the minimum cost for each action
Therefore, we will go at most $C^*/\epsilon$ deep.

UCS

  • Complete:
    As long as there is a lower bound of the cost of each action ($\epsilon$ exist and $\epsilon>0$)
    UCS is a generalization of Breadth First Search in the sense that it takes costs of each edge into account.
  • Optimal:
    Whenever UCS selects a node n for expansion, the optimal path to that node has been found, because our expand strategy is expands the node with the lowest path cost g(n)
    Then, because step costs are non-negative, paths never get shorter as nodes are added.
    These two facts together imply that UCS expands nodes in order of their optimal path cost.
    Hence, the first goal node selected for expansion must be the optimal solution.
  • Time complexity: $O(b^{C^*/\epsilon})$
    Longer than BFS. BFS stops as soon as it generates a goal, whereas UCS examines all the nodes at the goal’s depth to see if one has a lower cost; thus UCS does strictly more work by expanding nodes at depth d unnecessarily.
  • Space complexity: $O(b^{C^*/\epsilon})$ roughly the last tier

Conceptually, all the search algorithms above are the same except for frontier strategies, and all frontier are priority queues (priority means strategy).

Share