Rectangular Pyramid Partitioning using Integrated Depth Sensors (RAPPIDS): A Fast Planner for Multicopter Navigation
This addresses the need for efficient local navigation in drones, though it appears incremental as it builds on existing planning methods with a new collision detection approach.
The paper tackles the problem of fast collision checking and planning for multicopters in cluttered environments, presenting RAPPIDS, which uses a pyramid-based spatial partitioning method to enable rapid trajectory evaluation, achieving 30 Hz operation on constrained hardware and evaluating thousands of trajectories per second.
We present RAPPIDS: a novel collision checking and planning algorithm for multicopters that is capable of quickly finding local collision-free trajectories given a single depth image from an onboard camera. The primary contribution of this work is a new pyramid-based spatial partitioning method that enables rapid collision detection between candidate trajectories and the environment. By leveraging the efficiency of our collision checking method, we shown how a local planning algorithm can be run at high rates on computationally constrained hardware, evaluating thousands of candidate trajectories in milliseconds. The performance of the algorithm is compared to existing collision checking methods in simulation, showing our method to be capable of evaluating orders of magnitude more trajectories per second. Experimental results are presented showing a quadcopter quickly navigating a previously unseen cluttered environment by running the algorithm on an ODROID-XU4 at 30 Hz.