Real-Time Motion Planning for Agile Autonomous Vehicles

Abstract

Planningthepathofanautonomous,agilevehicleinadynamicenvironmentisaverycomplexproblem,especially when the vehicle is required to use its full maneuvering capabilities. Recent efforts aimed at using randomized algorithms for planning the path of kinematic and dynamic vehicles have demonstrated considerable potential for implementation on future autonomous platforms. This paper builds upon these efforts byproposing a randomized path planning architecture for dynamical systems in the presence of é xed and moving obstacles. This architecture addresses thedynamic constraints on the vehicle's motion, and it providesat the same timeaconsistentdecoupling between low-level control and motion planning. The path planning algorithm retains the convergence properties of its kinematic counterparts. System safety is also addressed in the face of é nite computation times by analyzing the behavior of the algorithm when the available onboard computation resources are limited, and the planning must be performed in real time. The proposed algorithm can be applied to vehicles whose dynamics are described eitherbyordinarydifferential equationsor byhigher-level, hybrid representations. Simulation examplesinvolving a ground robot and a small autonomous helicopter are presented and discussed. the position of all of its points with respect to an inertial reference frame. We will assume that such a coné guration can be described by a é nite number of parameters. The conéguration space is the set of all possible coné gurations of the robot. Cell decomposition methods rely on the partition of the con- é guration space into a é nite number of regions, in each of which collision-free paths can be found easily. The motion-planning prob- lem then is translated into the problem of é nding a sequence of neighboring cells, including the initial and énal conditions.5