state variables = exponential number of states
frontier may be exponentially large
time vs. space
large time
may be allowed
example: move boats for clearing an area of the ocean
execution takes days, long time for planning allowed
large space
not enough memory = no solution
How much time is allowed for planning depends on the specific case. Some plans
take days or months for being executed, so a large amount of time spended on
planning may not be a problem; on the other hand, a non-playing character in a
videogame is supposed to react almost immediately.
Still, memory is constrained in both cases. When the available memory is
exhausted, a program can do nothing but stopping.
trade time for memory
solution:
spend more time
save memory
iterative deepening
start from initial state
reach all states at distance one
reach all states at distance two
reach all states at distance three
…
this is iterative deepening in general
applied to A*: later
search(node, bound) {
if (bound = 0)
return;
for each successor s of node
search(s, bound - 1)
}
for each bound: depth-first visit
required memory: up to bound nodes
simplified case: no loops
This pseudocode only show how the visit is performed. It omits the termination
condition: the goal is reached.
When the goal is reached the algorithm may stop and return it. Due to the
breadth-first exploration policy, that solution will be minimal. This is
however not the case when a non-admissible heuristics is used.
This algorithm works if the graph is loop-free. Loops are taken into account in
a later slide.
repetitions
bound = 0
bound = 1
bound = 2
bound = 3
nodes visited when bound=1
visited again for bound=2, bound=3, etc.
even worse with cycles!
(but still works)
loops
do not return to a node already visited in the
current search
search(node, visited, bound) {
if (bound = 0 or node ∈ visited)
return;
for each successor s of node
search(s, visited ∪ {node}, bound - 1)
}
do not proceed if s ∈ visitedvisited: nodes in the path from the root to s
repetitions and loops
an example problem
(with a loop)
in the following slides:
half line = direction left to explore
(because search went in another way)
red line = blocked because node already visited
example order of the successors
most nodes in this example have only one successors
two nodes with two successors: where to go first?
for the sake of this example:
first successors on the left if possible, otherwise down
Heuristics are not considered yet. This is a description of how iterative
deepening on graphs works.
Since a node may have multiple successors, the loop “for each
successor s of node” depends on the order of successors.
For the sake of this example, successors are assumed to be ordered that way.
bound = 0
the call to search() returns immediately
bound = 1
search() called on the starting node
calls itself on its successor with bound = 0
stops because of the bound
bound = 2
this is longer
four recursive calls to search()
two slides
bound = 2, first part
first call to search(), with bound = 2
calls itself on the successor with bound = 1
recursive call to search() with bound = 1
two successors: first go down, then up
go down with bound = 0
mark other direction as left to explore when done
stop because of the bound
go back
bound = 2, second part
go back, take last road not taken before
again, stop because of the bound
fast forward to search = 7
search() called with bound = 3,…6
omitted here
These calls are performed by the algorithm, but are omitted here because they
are similar either to the previously shown ones or to the ones shown next.
The figures for these omitted calls are in the web page:
iterative deepening example.
bound = 7
start again from the beginning
bound = 7
call on the successor with bound = 6
bound = 7
call on one successor with bound = 5
the other will be visited later
bound = 7
another recursive call, bound = 4
bound = 7
another recursive call, bound = 3
two successors
visit one, mark the other for visiting later
bound = 7
recursive call on one successor, bound = 2
bound = 7
recursive call with bound = 1
bound = 7
successor already visited
do not go there!
backtrack instead
backtrack to the point of the last suspended direction
(black half-line on the right)
was: bound = 3
follow the half-line with bound = 2
bound = 7
now bound = 2
go to the successor with bound = 1
bound = 7
now bound = 1
go to the successor with bound = 0
bound = 7
now bound = 0
stop because of the bound
backtrack
still one direction unexplored (half-line)
go back and take it
was: bound = 6
bound = 7
go back all the way
until the last untried choice
was: bound = 6
then go forward, with bound = 5
bound = 7
like previously:
search stopped because node already visited
go the last untried choice
bound = 7
stop because of the bound
no suspended direction
backtrack all the way
bound = 8
next iterationis with bound = 8
first part as before
bound = 8
stop because node already visited
try last suspended way
bound = 8
target reached
comments on the examples
node reached for bound = x
is reached again for bound = x+1, x+2, x+3, …
loops: nodes reached twice for the same bound
in general: multiple times
efficiency of iterative deepening
bredth-first = each node reached once
iterative deepening = nodes reached multiple times
bredth-first more time-efficient than iterative deepening
but: requires storing the frontier
may become large
iterative deepening only stores:
visited
set of visited nodes
records of recursive calls
one call for each node in the current path
requires less space
efficiency of iterative deepening
in comparison with breadth-first search:
does not store frontier, only path from starting node
nodes visited multiple times
how bad point 2 is?
comparison: large loops
iterative deepening ends up storing all nodes in the path
breadth-first does not: frontier never larger than two nodes
The frontier is made of the nodes at a fixed distance from the start. In this
case, for every fixed distance only two or one node is that far from the start.
Instead, iterative deepening follows each path until either the target node or
an already visited node is found. If none of the nodes is a goal node, it ends
up following the whole loop.
comparison: long lines
breadth-first: linear
iterative deepening: quadratic
Both algorithms take the same space.
Iterative deepening takes more time because it visits the line once for each
bound.
comparison: complete trees
breadth-first: size of frontier doubles at each levels
iterative deepening: path is logarithmic with nodes
time?
Iterative deepening is much more space-efficent than breadth-first, since it
only takes a logarithmic amount of memory. Running time is compared in the next
slide.
comparison: complete trees, time
breadth-first: number of nodes
iterative deepening:
bound = 1, cost 1
bound = 2, cost 2
…
last iteration: number of nodes
really so bad?
As expected, iterative deepening takes longer since it visits the same nodes
multiple times, which breadth-first does not. But how longer does it take,
exactly?
comparison: complete trees, time in reverse order
breadth-first: number of nodes (16)
iterative deepening
(sum from last iteration to first):
number of nodes (16)
half the number of nodes (8)
half of that (4)
half of that (2)
half of that (1)
total: 16 + (8 + 4 + 2 +1) = 16 + 15
only twice the cost of breadth-first
The total cost for iterative deepening is the same as calculated before but
shown in reverse order: instead of first iteration+second+third+…+last,
is presented as last+second-last+…+second+first. The result is of course
the same.
the lilypad and the pond
a lilypad in a pond doubles its covered area each day
on day 30, it finishes covering the whole pond
which day did it cover half of it?
lilypad = ninfea
pond = stagno
unexpected properties of exponential functions
pond covered on day 30
double area each day
previous day (29): half of the pond
iterative deepening vs. breadth-first
iterative deepening wins when:
nodes have many successors
loops are small
cost of actions
previous example: all edges have cost 1
if costs differ: one issue arises
cost of actions: example
previous slides: each line costs 1 to follow
now: different costs
The previous examples assumed that the cost of moving from a node to another is
always 1. In general, the cost of different actions may differ.
In the example, the curved line costs 3 while the straight lines cost
1 each.
bounding the number of steps
when bound = 1:
target reached following the curved line only
not reached following the first straight line only
cost of first solution found is 3
the two straight lines have total cost 1+1
If the bound is taken to be the maximal number of crossed edges, an edge of
cost 10 is followed when bound = 1 but two consecutive edges
of cost 1 and 2 are only followed both when bound =
2. The target is reached first with a non-optimal path.
bounding the total costs of the steps
bound = 0
return immediately
bound = 1
do not follow the curved line
(cost 3 > bound 1)
follow the first straight line
(cost 1 ≤ bound 1)
bound = 2
do not follow the curved line
(cost 3 > bound 2)
follow the first and then the second straight line
(total cost 1+1 ≤ bound 1)
target reached optimally, but…
Bounding the total cost of the path makes the optimal solution reached first.
Yet, this method has a problem.
search(node, visited, bound) {
if (bound ≤ 0 or node ∈ visited)
return;
for each successor s of node
search(s, visited ∪ {node}, bound - node→s)
}
node→s is the cost of going from node to s
previously: node→s = 1
now: some value
This is the algorithm that was implicitly performed in the previous example:
the bound limits the total cost of the sequence of actions that can be
performed at each iteration.
useless iterations
example problem
execute iterative deepening with costs
bound = 0
as usual: return immediately
only starting node reached
bound = 1
nodes at cost-distance 4 and 5 not analyzed
since both 4 and 5 are greater than bound = 1
not a problem if costs are all one
in the example:
no node at cost-distance 2 or 3
iterations for bound = 2 and bound = 3 useless
in general:
no node in a certain interval of costs
missing distances: solution
go from bound = 1 straight to bound=4
skip 2 and 3
how to tell the bounds to skip?
not by testing bound = 2 and bound = 3!
The solution cannot be: just test whether some node is at a given distance from
the start by searching. Seaching without reaching any node is exactly the
problem to solve.
first search: gather additional information
bold: lines that cross the border
nodes next to be visited
but were not because of the bound
first search: next node
nodes about to be visited
but were not because of the bound
their distance: 4, 5, 1+3
with bound = 4 at least a new node is reached
detect and skip useless bounds
during the search:
when stopping the search because of the bound
calculate distance of nodes about to be visited
maintain the minimum
next iteration: bound = minimum
iterative deepening A*
instead of the distance start⇒n
use start⇒n + h(n)