Introduction to AI - Week 8

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"?

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

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

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

Iterative Deepening

• Depth-Limited Search has the main advantage that the search process can't descend forever (in a branch without solution).

• However, it will not find a solution if all solutions require a depth greater than the limit.
• To overcome this problem (and to maintain the advantages of depth limited depth first search), one has introduced a form in which the limit is increased if there is no solution of a limit l. That is, choose initially l=1, iteratively increase l by 1, and perform on each level Depth Limited Depth First search until a solution is found.

Bi-Directional Search

Avoiding Repeated States

Cheaper (albeit incomplete) forms are:

• Do not return to the state you came from.
  That is, do not generate a node that is equal to your parent.

• Do not create cycles. That is, do not generate a node that is equal to any of your ancestors.

Heuristic Search

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

function Greedy-Search(problem) -> solution
;;; input: a problem
best-first-search(problem,h) -> solution

function A-star(problem) -> solution
;;; input: a problem
best-first-search(problem,g+h) -> solution

Example

Heuristic: Air distance

Greedy Search in the Example

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 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 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)

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

• Restriction on h: the heuristic function h may never overestimate the cost to reach the goal (such a heuristic is called admissible.
  Example: h as air distance is an optimistic estimate for a travel distance.
• If h is admissible, then f=g+h is as well.
• Along any path from the root, the f-cost never decreases, that is f is monotonic
• If h is admissible, the search tree is finitely branching (and there is a solution), then the A^*-algorithm finds an optimal solution

Hill-Climbing and Simulated Annealing

• Hill climbing is a search method, in which the next node to expand, is the node with the highest value of the nodes generated from the expansion of the current node.
• Problems with hill-climbing:
  • local maxima (algorithm misses the total maximum)
  • plateaux (the evaluation function is flat and is not informative)
  • ridges (saddle shaped area, oscillation, without finding the way further up may happen)
• Solutions:
  • Random restart hill-climbing
  • Simulated annealing: Allow for bad moves as well (that is, moves that lead down-hill), where the probability of such a move decreases exponentially with its badness. With decreasing temperature T, bad moves become less and less likely.

Heuristics in the Blocksworld

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

• differences in Ontable(x) considered particularly high
• differences in Handempty and Holds(x) very low
• Optimally, the differences for On(x,y) would be considered the more the lower in a tower x and y are

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

• Completeness: solution will eventually be found if there is one at all
• Optimality: does it find the highest-quality solution when there are several
• Time complexity: time to find a solution as function of the complexity of the problem
• Space complexity: how much memory is necessary for the search as function of the complexity of the problem

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    

• S. Russell, P. Norvig. Artificial Intelligence - A Modern Approach. 2nd Edition, Pearson Education, 2003. Chapters 3 & 4.
• Judea Pearl: Heuristics - Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984. Reading, Massachusetts.