Bitwise Trajectory Elimination: An Efficient Method for Filtering Trajectory Libraries for Quadrotor Navigation

Abstract

Quadrotor flight in cluttered, unknown environments is challenging due to the limited range of perception sensors, challenging obstacles, and limited onboard computation. In this work, we directly address these challenges by proposing an efficient, reactive planning approach. We introduce the Bitwise Trajectory Elimination (BiTE) algorithm for efficiently filtering out in-collision trajectories from a trajectory library by using bitwise operations. Then, we outline a full receding-horizon planning approach for quadrotor flight in unknown environments demonstrated at up to 50 Hz on an onboard computer. This approach is evaluated extensively in simulation and shown to collision check up to 4896 trajectories in under under 20µs, which is the fastest collision checking time for a MAV planner, to the best of the authors’ knowledge. Finally, we validate our planner in over 120 minutes of flights in forest-like and urban subterranean environments.