Assume that ; the obstacles, , are polygonal; and the robot, , is a polygonal body that is only capable of translation. Under these assumptions, will be polygonal. For the special case in which is a point in , maps directly to without any distortion. Thus, the problems considered in this section may also be considered as planning for a point robot. If is not a point robot, then the Minkowski difference, (4.37), of and must be computed. For the case in which both and each component of are convex, the algorithm in Section 4.3.2 can be applied to compute each component of . In general, both and may be nonconvex. They may even contain holes, which results in a model such as that shown in Figure 6.1. In this case, and may be decomposed into convex components, and the Minkowski difference can be computed for each pair of components. The decompositions into convex components can actually be performed by adapting the cell decomposition algorithm that will be presented in Section 6.2.2. Once the Minkowski differences have been computed, they need to be merged to obtain a representation that can be specified in terms of simple polygons, such as those in Figure 6.1. An efficient algorithm to perform this merging is given in Section 2.4 of . It can also be based on many of the same principles as the planning algorithm in Section 6.2.2.
To implement the algorithms described in this section, it will be helpful to have a data structure that allows convenient access to the information contained in a model such as Figure 6.1. How is the outer boundary represented? How are holes inside of obstacles represented? How do we know which holes are inside of which obstacles? These questions can be efficiently answered by using the doubly connected edge list data structure, which was described in Section 3.1.3 for consistent labeling of polyhedral faces. We will need to represent models, such as the one in Figure 6.1, and any other information that planning algorithms need to maintain during execution. There are three different records:
Steven M LaValle 2012-04-20