Jamie Snape and Dinesh Manocha
Department of Computer Science, University of North Carolina at Chapel Hill
We present an algorithm for collision-free navigation of multiple flying robots in three-dimensional workspace. Our approach extends the model of a simple car to a simple-airplane, which has constraints on speed and steering angle and includes a configuration variable for the altitude. We use a locally optimal reciprocal collision avoidance scheme that computes the trajectory without any collisions or oscillations for each airplane independently. In addition, our algorithm explicitly considers the kinematic and dynamic constraints of a simple-airplane and uses the notion of variable reciprocity when choosing velocities to ensure that simple-airplanes that are less constrained take more responsibility for avoiding collisions. We test our approach in two simulations and compute collision-free and oscillation-free trajectories that satisfy the kinematic and dynamic constraints of each simple-airplane.
Path planning for multiple mobile robots or agents; collision avoidance.
Jamie Snape and Dinesh Manocha, "Navigating multiple simple-airplanes in 3D workspace," IEEE Int. Conf. Robotics and Automation, Anchorage, Alaska, 2010.
Sphere Scenario: Sixteen simple-airplanes (white ellipsoids) are placed at points on an imaginary sphere. Their goals are to navigate to a point on the opposite side of the sphere. The simple-airplanes will meet and have to negotiate around each other towards the middle of the sphere.
QuickTime Movie (13.2 MB)
Dynamic Obstacle Scenario: Four dynamic obstacles (larger red spheres) travel at a constant velocity across the workspace. Twelve simple-airplanes (smaller white ellipsoids) have to cross the paths of the obstacles to reach their goals, while avoiding collisions.
QuickTime Movie (16.4 MB)
This work was supported by ARO under Contract W911NF-04-1-0088, by NSF under Award 0636208, Award 0917040, and Award 0904990, by DARPA and RDECOM under Contract WR91CRB-08-C-0137, and by Intel.