next up previous contents
Next: EPB/PDO Implementation.3 Up: Reasoning About Path-Planning with Previous: Reasoning About Path-Planning with

The Path-Planning Problem

Path planning problems are a far more common concern in robotics than the simple sliding problem presented in the previous section. The typical problem formulation in path planning is the ``(piano) mover's problem'', or ``findpath problem''. This problem, like my sliding problem, involves a number of obstacles and a single moving object. The difference between the mover's problem and the sliding problem is that in the mover's problem, the goal is to find a path through the obstacles while avoiding touching any of them (rather than finding what can happen when maintaining contact with them).5.1

The obstacles in my examples are all right angled polygons, with a mixture of concave and convex vertices, and with multiple levels of detail on the boundary. This is also true of the moving object. Most of the implemented code allows for angles which are not right angles, and for curved edges, but examples with these properties were not tested, for reasons explained later.

The reasoning performed in solving this problem was intended to complement that performed in the sliding problem. It involves motion of the moving object through free space, and discovery of non-contact paths between obstacles. The goal state is a position for the moving object which is on the other side of the obstacles initially surrounding it, and provides unbounded movement away from those obstacles. The solution to the problem also includes a suggested path which will enable the moving object to reach that goal state.

The remainder of this section first discusses the implementation of the extended polygon boundary/partial distance ordering representation, and then describes the reasoning strategies used to solve path planning problems. The overall stages in solving a problem are discussed first, and the method of solution for each stage is then described.


next up previous contents
Next: EPB/PDO Implementation.3 Up: Reasoning About Path-Planning with Previous: Reasoning About Path-Planning with
Alan Blackwell
2000-11-17