Introduction to AI - Week 8

Search
Represent a search problem as:

The Blocks World

Blocks World: classical planning scenario:
blocks that stand on a table or stand on top of each other or are hold by a robot hand (mutual relationship disregarded otherwise) and can be manipulated by a robot hand

Description by predicates of the form

 Ontable(x)  x stands on the table
 On(x,y)  x stands on y
 Clear(x)  nothing stands on x
 Handempty  robot hand is empty
 Holds(x)  robot hand holds x

Ontable(A)
Ontable(B)
On(D,A)
On(C,D)
Clear(C)
Clear(B)
Handempty

What is a "Search Problem"?

Planning problem is given by initial state & goal state, e.g., goal:

          
Ontable(B)
Ontable(C)
On(D,B)
On(A,D)
Clear(A)
Clear(C)
Handempty

For this transition are certain operators available. In blocks world
 PICKUP(x)  picking up x from the table
 PUTDOWN(x)  putting down x on the table
 STACK(x,y)  putting x on y
 UNSTACK(x,y)  picking up x from y

Formalise operators!
Find plan


Operators of the Blocks World

-------- ------------- -------------
  PICKUP(x)
 preconditions  Clear(x)
   Ontable(x)
   Handempty
 delete list  Clear(x)
   Ontable(x)
   Handempty
 add list  Holds(x)
  PUTDOWN(x)
 preconditions  Holds(x)
 delete list  Holds(x)
 add list  Clear(x)
   Ontable(x)
   Handempty
-------- ------------- -------------
  STACK(x,y)
 preconditions   Holds(x)
    Clear(y)
 delete list   Holds(x)
    Clear(y)
 add list   Clear(x)
    On(x,y)
    Handempty
  UNSTACK(x,y)
 preconditions  Clear(x)
   On(x,y)
   Handempty
 delete list  Clear(x)
   On(x,y)
   Handempty
 add list  Holds(x)
   Clear(y)
-------- ------------- -------------

General search algorithm

function general-search(problem,insert) -> solution
;;; insert is a function to determine, where to
;;; insert the nodes which are newly expanded
insertion-function(init(problem)) -> nodes
while not null(nodes) or not goal-test(problem)(node) 
do 
     first(nodes) -> node
     insert(nodes,expand(node,operators(problem))) -> nodes
     remove(node,nodes) -> nodes
od
if null(nodes) then failure
else node -> solution

Breadth-first search

Breadth-first is given by:
insert appends the new nodes to the end of nodes
Example:

Breadth-first search finds optimal solutions
implemented as Queue ("First in First Out")


An Example for Breadth-first search


Depth-first search

Depth-first is given by:
insert inserts the new nodes at the front of nodes
Example: (assume no expansion possible when no successor)

Depth-first search can fail to find solutions
implemented as Stack ("Last in First Out")


An Example for Depth-first search


Depth Limited Depth First

As depth first, but do not generate nodes deeper in the tree than an a priori fixed limit.

If there is no solution within limit l, then no solution will be found.


Iterative Deepening


Bi-Directional Search

In bi-directional search, start the process simultaneously from the initial start and backwards from the goal state, in order to reduce the complexity.
The shaded area corresponds to the search effort

Avoiding Repeated States

The safest way to avoid any repeated states is to store all states visited and compare each node whether it has been visited before. If yes, don't add it. The problem with this strategy is that firstly you have to store all states visited (space) and make many comparisons (time).

Cheaper (albeit incomplete) forms are:


Heuristic Search

Assume a heuristic function h such that h(n) is the estimated cost of the cheapest path from the state at node n to a goal state.
In best-first-search the insertion function orders the nodes with respect to some measure.

function
Best-First-Search(problem,eval-function) -> solution
;;; input: a problem and an evaluation function
function orders nodes by eval-function -> queue-function
general-search(problem,queue-function) -> solution

Greedy Search and A*-Search

greedy-search: insert best nodes at beginning of nodes according to h, that is,
function Greedy-Search(problem) -> solution
;;; input: a problem
best-first-search(problem,h) -> solution
A*-search: insert best nodes at beginning of nodes
according to f=g+h with g actual cost to that node, h estimated cost to the goal. In the A* algorithm the heuristic function h must be optimistic in order to find the best solution.
function A-star(problem) -> solution
;;; input: a problem
best-first-search(problem,g+h) -> solution

Example

Assume you wanted to search for the shortest path from Arad to Bucharest (taken from [Russell-Norvig 2003])

Task: Find path from Arad to Bucharest

Heuristic: Air distance

 Town  Air Dist.
 Arad  366
 Bucharest  0
 Craiova  160
 Dobreta  242
 Eforie  161
 Fagaras  176
 Giurgiu  77
 Hirsova  151
 Iasi  226
 Lugoj  244
 Mehadia  241
 Neamt  234
 Oradea  380
 Pitesti  100
 Rimnicu Vilcea  193
 Sibiu  253
 Timisoara  329
 Urziceni  80
 Vaslui  199
 Zerind  374

Greedy Search in the Example

Possibilities from Arad: Go to Zerind, Timisoara, or Sibiu?
Take as heuristic the air distance:
Zerind (374), Timisoara (329), or Sibiu (253)
Closest air distance Sibiu, hence go to Sibiu.

Possibilities from Sibiu: Arad, Fagaras, Oradea, or Rimnicu Vilcea?
Take as heuristic the air distance:
Arad (366), Fagaras (176), Oradea (380), or Rimnicu Vilcea (193)
Closest air distance Fagaras, hence go to Fagaras.

Possibilities from Fagaras: Go to Sibiu or Bucharest?
Take as heuristic the air distance:
Sibiu (253) or Bucharest (0)?
Closest air distance Bucharest, hence go to Bucharest.

That is 140km +99km +211km = 450km .


Greedy Search in the Example (Cont'd)


A*-Search in the Example

Possibilities from Arad: Go to Zerind, Timisoara, or Sibiu?
Take as heuristic the air distance plus cost to town:
Zerind (374+75=449), Timisoara (329+118=447), or Sibiu (253+140=393)
Most promising Sibiu, hence explore going to Sibiu.

Possibilities from Sibiu: Arad, Fagaras, Oradea, or Rimnicu Vilcea?
Take as heuristic the air distance plus cost to town:
Arad (140+140+366=646), Fagaras (140+99+176=415), Oradea (140+151+380=671), or Rimnicu Vilcea (140+80+193=413)
Overall most promising not expanded Rimnicu Vilcea, hence explore going to Rimnicu Vilcea


A*-Search in the Example (Cont'd)

Possibilities from Rimnicu Vilcea: Sibiu, Pitesti, or Craiova?
Take as heuristic the air distance plus cost to town:
Sibiu (140+80+80+253=553), Pitesti (140+80+97+100=417), or Craiova (140+80+146+160=526)
Overall most promising not expanded Fagaras, hence explore going to Fagaras (from Sibiu)

Possibilities from Fagaras: Sibiu, or Bucharest?
Take as heuristic the air distance plus cost to town:
Sibiu (140+99+99+253=591), or Bucharest (140+99+211+0=450)
Overall most promising not expanded Pitesti, hence explore going to Pitesti (from Rimnicu Vilcea)


A*-Search in the Example (Cont'd)

Possibilities from Pitesti: Rimnicu Vilcea, Craiova, or Bucharest?
Take as heuristic the air distance plus cost to town:
Rimnicu Vilcea (140+80+97+97+193=607), Craiova (140+80+97+138+160=615) or Bucharest (140+80+97+101+0=418)
Overall most promising go to Bucharest from Pitesti.

Since there is no way to get on a shorter route to Bucharest the last one is taken.


A*-Search in the Example (Cont'd)


Properties of the A*-Algorithm


Hill-Climbing and Simulated Annealing


Heuristics in the Blocksworld

Problem: Find a heuristic function h for estimating how far the current state is from goal state:

In the extreme case, the heuristic function exactly knows what to do. Then there is no search, but we have an algorithmic procedure.


Properties of Some Search Algorithm


Properties of Search Algorithms (Cont'd)

   Breadth-first  Depth-first  Greedy  A*
-------- ------------- -------------
 Complete  Yes  No  No  Yes
 Optimal  Yes  No  No  Yes
 Time  exponential  exponential  exponential  exponential
 Space  exponential  linear  linear  exponential

Further Reading    



© Manfred Kerber, 2004, Introduction to AI
24.4.2005
The URL of this page is http://www.cs.bham.ac.uk/~mmk/Teaching/AI/Teaching/AI/l8.html.
URL of module http://www.cs.bham.ac.uk/~mmk/Teaching/AI/