Next: Gap Finding
Up: Reasoning About Path-Planning with
Previous: EPB/PDO Implementation.3
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