Fast Generation of Collision-Free Trajectories for Robot Swarms Using GPU Acceleration
Authors:
Open Access
- 24 December 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 7, 6679-6690
Abstract
As the capabilities of robots and their control systems improve, we see an increasing number of use-cases where the simultaneous operation of robots within a space is advantageous. Although trajectories for individual robots can be computed quickly using existing methods, when robots operate simultaneously and in close proximity, the requirement for collision avoidance introduces a coupling between robot trajectories and makes the trajectory generation problem difficult to solve quickly. In this paper we propose a parallelizable formulation of such problems and a method for solving them quickly on modern graphics processing units, using momentum-based gradient descent. We demonstrate the proposed framework in simulation using two case studies: a swarm of 200 quadcopters traversing a maze, and a fleet of 100 bicycle robots changing their formation. In both cases, our method requires just seconds to generate feasible, collision-free trajectories for the entire swarm.Keywords
This publication has 31 references indexed in Scilit:
- Kinematic and dynamic vehicle models for autonomous driving control design2015
- Decoupled multiagent path planning via incremental sequential convex programming2015
- A GPU-Enabled Parallel Genetic Algorithm for Path Planning of Robotic Operators2014
- A UAV path planning with parallel ACO algorithm on CUDA platform2014
- Trajectory generation and control for precise aggressive maneuvers with quadrotorsThe International Journal of Robotics Research, 2012
- GPU-based parallel collision detection for fast motion planningThe International Journal of Robotics Research, 2011
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- Data parallel algorithmsCommunications of the ACM, 1986
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955