When studying combinatorial
motion planning algorithms, it is important to carefully consider the
definition of the input. What is the representation used for the
robot and obstacles? What set of transformations may be applied to
the robot? What is the dimension of the world? Are the robot and
obstacles convex? Are they piecewise linear? The specification of
possible inputs defines a set of problem instances on which the
algorithm will operate. If the instances have certain convenient
properties (e.g., low dimensionality, convex models), then a
combinatorial algorithm may provide an elegant, practical solution.
If the set of instances is too broad, then a requirement of both
completeness and practical solutions may be unreasonable. Many
general formulations of general motion planning problems are
PSPACE-hard^{6.1}; therefore,
such a hope appears unattainable. Nevertheless, there exist general,
complete motion planning algorithms. Note that focusing on the
representation is the opposite philosophy from sampling-based
planning, which hides these issues in the collision detection module.

Steven M LaValle
2020-08-14