Motion planning problems are interesting in many ways. First, it is easy to establish a number of technical relations between them and more general AI planning problems, e.g., dealing with interacting subgoals, hierarchical planning, regression, etc. But unlike general AI planning problems, MP problems are well formulated, which makes it easier to assess progress. No need to use toy domains. No risk of hiding core ideas behind irrelevant details when real applications are considered. MP problems are also difficult; most have been proven computationally hard. Interestingly, some proofs that block-world planning is hard are derived from pre-existing proofs that coordinating the motions of several objects is hard. On the other hand, unlike with games like chess, the rules can be changed. If we think that a MP problem has become too simple or no longer interesting, we can make it more difficult, say, by adding uncertainties or by making the environment more dynamic.
In this talk I will discuss two major families of MP methods. One uses random sampling to build a connectivity model of a continuous space. The other uses "physical criticalities" to meaningfully discretize a continuous space. The first type of method is relevant to search; the second to efficient problem formulation. In the conclusion, I will briefly introduce more prospective MP issues/methods that are likely to be relevant to AI.