Introduction to AI - Week 8

Search
Represent a search problem as:
• a state space that contains all possible configurations, (with start state and goal state)
• a set of operators for manipulating states
• start state and goal state (or a goal test)
• path costs for measuring the cost going along a path

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

insert appends the new nodes to the end of nodes
Example:

implemented as Queue ("First in First Out")

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

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

• 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

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:

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

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

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.

Take as heuristic the air distance:
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 .

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.

Take as heuristic the air distance plus cost to town:
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.

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