This encodes the desired outcome of a plan in terms of
the state and actions that are executed. There are generally two
different kinds of planning concerns based on the type of criterion:
- [1.]
**Feasibility:** Find a plan that causes arrival at a
goal state, regardless of its efficiency.
- [2.]
**Optimality:** Find a feasible plan that optimizes
performance in some carefully specified manner, in addition to
arriving in a goal state.

For most of the problems considered in this book, feasibility is
already challenging enough; achieving optimality is considerably
harder for most problems. Therefore, much of the focus is on finding
feasible solutions to problems, as opposed to optimal solutions. The
majority of literature in robotics, control theory, and related fields
focuses on optimality, but this is not necessarily important for many
problems of interest. In many applications, it is difficult to even
formulate the right criterion to optimize. Even if a desirable
criterion can be formulated, it may be impossible to obtain a
practical algorithm that computes optimal plans. In such cases,
feasible solutions are certainly preferable to having no solutions at
all. Fortunately, for many algorithms the solutions produced are not
too far from optimal in practice. This reduces some of the motivation
for finding optimal solutions. For problems that involve
probabilistic uncertainty, however, optimization arises more
frequently. The probabilities are often utilized to obtain the best
performance in terms of expected costs. Feasibility is often
associated with performing a worst-case analysis of uncertainties.

Steven M LaValle
2012-04-20