This work develops path planning algorithms for a polyhedral robot and static obstacles . Path planning is important for robot navigation and manipulation, design for assembly, virtual prototyping, and computer graphics. Although complete planning algorithms are available, they have proved impractical. The most successful technique to date is probabilistic planning. The drawback is that there is no efficient way to select enough samples to guarantee a specified success rate. Picking an optimal sampling rate is critical when the robot/obstacle configuration space contains narrow channels, as is common in structured environments. Too many samples make the planner inefficient, whereas too few make it unreliable.
We hypothesize that the problem lies in the local planner: the subroutine that tests if two robot configurations can be connected by a simple path. In current planners, the only candidate path is the line segment between the two configurations. Narrow channels cannot accommodate long segments, so the planner must traverse them in many local steps. At each step, many configurations are explored before a reachable one is found, since most directions are blocked.
Our work explores such solutions. |
