Introduction

All of the algorithms presented in this chapter are complete, which means that for any problem instance (over the space of problems for which the algorithm is designed), the algorithm will either find a solution or will correctly report that no solution exists. By contrast, in the case of sampling-based planning algorithms, weaker notions of completeness were tolerated: resolution completeness and prob- abilistic completeness.

Representation is important 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 transforma- tions 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 op- erate. 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 complete- ness and practical solutions may be unreasonable. Many general formulations of general motion planning problems are PSPACE-hard1; therefore, such a hope ap- pears 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.

1This implies NP-hard. An overview of such complexity statements appears in Section 6.5.1.

249

Reasons to study combinatorial methods There are generally two good reasons to study combinatorial approaches to motion planning:

• 1. In many applications, one may only be interested in a special class of planning problems. For example, the world might be 2D, and the robot might only be capable of translation. For many special classes, elegant and efficient algorithms can be developed. These algorithms are complete, do not depend on approximation, and can offer much better performance than sampling- based planning methods, such as those in Chapter 5.
  2. It is both interesting and satisfying to know that there are complete algo- rithms for an extremely broad class of motion planning problems. Thus, even if the class of interest does not have some special limiting assumptions, there still exist general-purpose tools and algorithms that can solve it. These algorithms also provide theoretical upper bounds on the time needed to solve motion planning problems.

Warning: Some methods are impractical Be careful not to make the wrong assumptions when studying the algorithms of this chapter. A few of them are effi- cient and easy to implement, but many might be neither. Even if an algorithm has an amazing asymptotic running time, it might be close to impossible to implement. For example, one of the most famous algorithms from computational geometry can split a simple2 polygon into triangles in O(n) time for a polygon with n edges [190]. This is so amazing that it was covered in the New York Times, but the algorithm is so complicated that it is doubtful that anyone will ever implement it. Sometimes it is preferable to use an algorithm that has worse theoretical running time but is much easier to understand and implement. In general, though, it is valuable to understand both kinds of methods and decide on the trade-offs for yourself. It is also an interesting intellectual pursuit to try to determine how efficiently a problem can be solved, even if the result is mainly of theoretical interest. This might motivate others to look for simpler algorithms that have the same or similar asymptotic running times.

Roadmaps Virtually all combinatorial motion planning approaches construct a roadmap along the way to solving queries. This notion was introduced in Section 5.6, but in this chapter stricter requirements are imposed in the roadmap definition because any algorithm that constructs one needs to be complete. Some of the algorithms in this chapter first construct a cell decomposition of free from which the roadmap is consequently derived. Other methods directly construct a roadmap without the consideration of cells.

C

Let G be a topological graph (defined in Example 4.6) that maps into Cfree.

Furthermore, let S free be the swath, which is set of all points reached by , as defined in (5.40). The graph is called a roadmap if it satisfies two important conditions:

G

⊂ C G

2A polygonal region that has no holes.

1. Accessibility: From any q ∈ Cfree, it is simple and efficient to compute a

path τ : [0, 1] free such that τ (0) = q and τ (1) = s, in which s may be any point in S. Usually, s is the closest point to q, assuming is a metric space.

C

→ C

1. Connectivity-preserving: Using the first condition, it is always possible to connect some qI and qG to some s1 and s2, respectively, in S. The second

condition requires that if there exists a path τ : [0, 1] → Cfree such that

τ (0) = qI and τ (1) = qG, then there also exists a path τ ′ : [0, 1] → S, such that τ ′(0) = s1 and τ ′(1) = s2. Thus, solutions are not missed because G fails

to capture the connectivity of free. This ensures that complete algorithms are developed.

C

By satisfying these properties, a roadmap provides a discrete representation of the continuous motion planning problem without losing any of the original connectivity information needed to solve it. A query, (qI , qG), is solved by connecting each query point to the roadmap and then performing a discrete graph search on . To maintain completeness, the first condition ensures that any query can be connected to , and the second condition ensures that the search always succeeds if a solution exists.

G

G