##

10.2.3 Graph Search Methods

Value iteration is quite general; however, in many instances, most of
the time is wasted on states that do not update their values because
either the optimal cost-to-go is already known or the goal is not yet
reached. Policy iteration seems to alleviate this problem, but it is
limited to small state spaces. These shortcomings motivate the
consideration of alternatives, such as extending the graph search
methods of Section 2.2. In some cases, Dijkstra's
algorithm can even be extended to quickly obtain optimal solutions,
but a strong assumption is required on the structure of solutions. In
the nondeterministic setting, search methods can be developed that
produce only feasible solutions, without regard for optimality. For
the methods in this section, need not be finite, as long as the
search method is systematic, in the sense defined in Section
2.2.

**Subsections**

Steven M LaValle
2012-04-20