We propose a two stage approach to planning in
uncertain environments. The first stage maintains information about
the global connectivity of the environment. In this stage of planning,
only hard objects are considered. Global connectivity is approximated
using a global dynamic roadmap which is updated as the environment
changes. As a result, approximate global paths can be extracted from
the global dynamic roadmap that is free of hard objects. The second
stage uses a global path extracted from the dynamic roadmap to locally
plan in the environment. These kinodyanmic local plans take into
account the soft objects, or neighboring other agents, to find safe
plans. The local paths are also updated as the environment changes.
|