Next: Gap Finding Up: Reasoning About Path-Planning with Previous: EPB/PDO Implementation.3

## Stages in Path Planning

The overall strategy of the path planning system includes three general stages (with a certain amount of interaction between the three). These three stages are:

1.
Find a gap between the obstacles surrounding the moving object in its current position.
2.
Check that the gap is big enough for the moving object to fit through.
3.
Specify directions of motion which take the moving object to the opening of the gap, and then through it.

These three stages appear relatively independent, but they affect each other in the following ways:

• Where there is more than one possible gap, each candidate must be evaluated in terms of its suitability for later planning stages. Information about fit and motion must therefore be available to the gap finder.
• The procedure for establishing the presence of a gap also establishes the narrowest extent of the gap in terms of the partial distance ordering. This information will later be necessary when checking fit, so must be passed on from the gap finding stage to the fit checking stage.
• In addition to the narrowest extent of the gap, an entry point must be recorded, relative to which motion into the gap can be specified. The gap finding stage records this information for use in the motion specification stage.
• Fit depends on the orientation of the moving object, which is determined in part by the direction of motion when approaching the gap. This means that some information about direction of motion must be available in the fit-checking stage, before motion is planned.

These factors make it impossible for the ``stages'' to be carried out independently, but it is still possible to separate the types of reasoning that must be carried out to solve each part of the problem.

The path planning strategy becomes more complex if more complex fields of obstacles are to be dealt with (where the moving object has to move in turn through more than one gap). The implemented system does not deal with this case, but it is discussed along with other possible extensions in the final section of this chapter.

Next: Gap Finding Up: Reasoning About Path-Planning with Previous: EPB/PDO Implementation.3
Alan Blackwell
2000-11-17