Real-time motion planning for agile autonomous vehicles

The operation of an autonomous vehicle in an unknown, dynamic environment is a very complex problem, especially when the vehicle is required to use its full maneuvering capabilities, and to react in real time to changes in the operational environment. A new class of algorithms, based on the construction of probabilistic roadmaps, has been recently introduced, and proven to provide a very fast and efficient scheme for motion planning for robots with many degrees of freedom, while maintaining completeness guarantees (in a probabilistic sense). In this paper we will present an extension of the probabilistic roadmap approach, which is able to deal effectively with the system dynamics, in an environment characterized by moving obstacles. This is accomplished through a Lyapunov function based approach to the construction of the roadmap. The proposed algorithm can be directly applied to a very general class of dynamical systems, including traditional state space systems, as well as hybrid systems (systems including both discrete and continuous dynamics). Simulation examples, involving a small autonomous helicopter, will be presented and discussed. © 2000 by the American Institute of Aeronautics and Astronautics, Inc. All rights reserved.