next up previous contents
Next: Checking for Fit Up: Reasoning About Path-Planning with Previous: Stages in Path Planning

Gap Finding

The first task carried out by the gap finding part of the path planning system is to establish whether path finding is necessary at all. If there are any directions in which the moving object is not facing any obstacles, then it can easily move into free space, by advancing in that direction. This initial test is carried out so that the gap finding module can be easily integrated into a more complex planning system. It would normally be used, for instance, to identify the goal state of an obstacle field negotiation problem.

If there are no sides of the moving object which are free of obstacles, the obstacles on every side are examined to find out whether there are gaps between each obstacle and its neighbour.

Note that the term ``side'' when applied to the moving object means here a segment on the coarsest boundary level. Initial motion planning takes place at this coarse level, because details of the object shape only become significant during actual motion. A ``gap'' is a path around the boundary of an obstacle which starts at an obstructing boundary element, and ends at a boundary element that meets the ``free space'' criterion. The obstacle boundary between these two elements must not contact any other obstacle.

The search procedure used to find gaps is evident from this definition. For every obstacle, the obstacle boundary is searched in both directions, starting from a boundary element which is in proximity to the moving object. The search is terminated when a portion of the boundary is in contact with another obstacle, when a free-space element is encountered, or when the searches from each direction meet.

Along the search path, a record is kept of the narrowest extent of the gap. This is the smallest distance from an element along the gap to any other obstacle, as found in the partial distance ordering. At any point, the search for the nearest neighbour of a boundary element must exclude the moving object itself (since proximity to the moving object will be recorded in the partial distance ordering in the same way as proximity between obstacles).


next up previous contents
Next: Checking for Fit Up: Reasoning About Path-Planning with Previous: Stages in Path Planning
Alan Blackwell
2000-11-17