Why Motion Planning is relevant to AI

Jean-Claude Latombe
Computer Science Department
Stanford University


Motion planning problems range from computing robot paths avoiding collision with static obstacles to generating sensor-based strategies to navigate reliably despite various uncertainties or to achieve complex goals such as finding an unpredictable moving target that tries to hide among view-obstructing obstacles.

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.

Eyal Amir
Last modified: Wed Jan 13 12:58:49 PST 1999