Motion Planning

  

 

Input description: A polygonal-shaped robot in a given starting position in a room containing polygonal obstacles, with a desired ending position t.

Problem description: Find the shortest path in the room taking to t without intersecting any of the obstacles.

Discussion: The difficulty of motion planning will be obvious to anyone who has ever had to move a large piece of furniture into a small apartment. The problem of motion planning also arises in systems for molecular docking. Many drugs are small molecules that act by binding to a given target model. The problem of identifying which binding sites are accessible to a candidate drug is clearly an instance of motion planning. Plotting paths for mobile robots is another canonical motion-planning application.       

Motion planning also provides a tool for computer animation. Given a set of object models that appear in two different scenes and , a motion planning algorithm can construct a short sequence of intermediate motions to transform to . These motions can serve to fill in the intermediate scenes between and , with such scene interpolation greatly reducing the amount of work the animator has to do.   

There is a wide range in the complexity of motion planning problems, with many factors to consider:

• Is your robot a point? - When the robot is a point, the problem becomes finding the shortest path from to t around the obstacles, also known as geometric shortest path. The most readily implementable approach constructs the visibility graph of the polygonal obstacles, plus the points and t. This visibility graph has a vertex for each obstacle vertex and an edge between two obstacle vertices if they ``see'' each other without being blocked by some obstacle edge.    

  A brute-force algorithm to construct the visibility graph tests each candidate edge against the obstacle edges for a total time of time. By weighting each edge of the visibility graph with its length and using Dijkstra's shortest-path algorithm (see Section ) on this graph, we can find the shortest path from to t in time bounded by the time to construct the graph.

• How is your robot free to move? - Motion planning becomes considerably more difficult when the robot becomes a polygon instead of a point. Now we must make sure that all of the corridors we use are wide enough to permit the robot to pass through. The complexity depends upon the number of degrees of freedom the robot has to move. Is it free to rotate as well as to translate? Does the robot have links that are free to bend or to rotate independently, as in an arm with a hand? Each degree of freedom corresponds to a dimension in the search space. Therefore, the more freedom, the harder it is to compute a path between two locations, although it becomes more likely that such a path exists.    
• Can you simplify the shape of your robot? - Motion planning algorithms tend to be complex and time-consuming. Anything you can do to simplify your environment would be a win. In particular, consider replacing your robot by an enclosing disk. If there is a path for the disk, there will be a path for whatever is inside of it. Further, since any orientation of a disk is equivalent to any other orientation, rotation provides no help in finding a path Therefore, all movements are limited to translation only.   
• Are motions limited to translation only? - When rotation is not allowed, the expanded obstacles approach can be used to reduce the problem to that of motion planning for a point robot, which is simply the shortest path in a graph. Pick a reference point on the robot, and replace each obstacle by the Minkowski sum of the object and the robot (see Section ). This creates a larger obstacle, defined as the robot walks a loop around the obstacle while maintaining contact with it. Finding a path from the initial position of the reference point to the goal point amidst these fattened obstacles defines a legal path for the polygonal robot.   
• Are the obstacles known in advance? - Thus far we have assumed that the robot starts out with a map of its environment. This is not always true, or even possible, in applications where the obstacles move. There are two approaches to solving motion planning problems without a map. The first approach explores the environment, building a map of what has been seen, and then uses this map to plan a path to the goal. A simpler strategy, which will fail in environments of sufficient complexity, proceeds like a sightless man with a compass. Walk in the direction towards the goal until progress is blocked by an obstacle, and then trace a path along the obstacle until the robot is again free to proceed directly towards the goal.   

The most practical approach to motion planning involves randomly sampling the configuration space of the robot. The configuration space defines the set of legal positions for the robot and has one dimension for each degree of freedom. For a planar robot capable of translation and rotation, the degrees of freedom are the x- and y-coordinates of a reference point on the robot and the angle relative to this point. Certain points in this space represent legal positions, while others intersect obstacles.   

Construct a set of legal configuration-space points by random sampling. For each pair of points and , decide whether there exists a direct, nonintersecting path between them. Construct a graph with vertices for each legal point and edges for each such traversable pair. The problem of finding a motion between two arbitrary positions reduces to seeing if there is a direct path from the initial/final position to some vertex in the graph, and then solving a shortest-path problem in the graph.

There are lots of ways to enhance this basic technique for specific applications, such as adding additional vertices to regions of particular interest. This is a nice, clean approach for solving problems that would get very messy otherwise.

Implementations: An implementation of collision detection (not really motion planning) is the I_COLLIDE collision detection library. For more information, check out the I_COLLIDE WWW page: http://www.cs.unc.edu/ geom/I_COLLIDE.html.  

O'Rourke [O'R94] gives a toy implementation of an algorithm to plot motion for a two-jointed robot arm in the plane. See Section .  

Notes: Motion planning was originally studied by Schwartz and Sharir as the ``piano mover's problem.'' Their solution constructs the complete free space of robot positions which do not intersect obstacles, and then finds the shortest path within the proper connected component. These free space descriptions are very complicated, involving arrangements of higher-degree algebraic surfaces. The fundamental papers on the piano mover's problem appear in [HSS87], with [SS90] being a survey of current results. The best general result for this free space approach to motion planning is due to Canny [Can87], who showed that any problem with d degrees of freedom can be solved in , although faster algorithms exist for special cases of the general motion planning problem.   

Latombe's book [Lat91] describes practical approaches to motion planning, including the random sampling method described above. The expanded obstacle approach to motion planning is due to Lozano-Perez and Wesley [LPW79]. The heuristic, sightless man's approach to motion planning discussed above has been studied by Lumelski [LS87].

The time complexity of algorithms based on the free-space approach to motion planning depends intimately on the combinatorial complexity of the arrangement of surfaces defining the free space. Algorithms for maintaining arrangements are presented in Section . Davenport-Schintzl sequences often arise in the analysis of such arrangements. Sharir and Agarwal [SA95] provide a comprehensive treatment of Davenport-Schintzl sequences and their relevance to motion planning.   

Kedem and Sharir [KS90] give an time algorithm to find a path (not necessarily shortest) to translate a convex k-gon from to t. Vegter [Veg90] gives an optimal algorithm for moving a line segment (often called a ladder) in the plane with both translation and rotation.

Related Problems: Shortest path (see page ), Minkowski sum (see page ).