Depth first

By making a stack (Last-In, First-Out; or LIFO), aggressive
exploration of the state transition graph occurs, as opposed to the
uniform expansion of breadth-first search. The resulting variant is
called *depth-first search* because the search dives quickly into
the graph. The preference is toward investigating longer plans very
early. Although this aggressive behavior might seem desirable, note
that the particular choice of longer plans is arbitrary. Actions are
applied in the **forall** loop in whatever order they happen to be
defined. Once again, if a state is revisited, there is no work to do
in line 12. Depth-first search is systematic for any finite but
not for an infinite because it could behave like Figure
2.3a. The search could easily focus on one
``direction'' and completely miss large portions of the search space
as the number of iterations tends to infinity. The running time of
depth first search is also
.

Steven M LaValle 2012-04-20