Planning in information space for a quadrotor helicopter in a GPS-denied environment

This paper describes a motion planning algorithm for a quadrotor helicopter flying autonomously without GPS. Without accurate global positioning, the vehicle’s ability to localize itself varies across the environment, since different environmental features provide different degrees of localization. If the vehicle plans a path without regard to how well it can localize itself along that path, it runs the risk of becoming lost. We use the Belief Roadmap (BRM) algorithm 1, an information-space extension of the Probabilistic Roadmap algorithm, to plan vehicle trajectories that incorporate sensing. We show that the original BRM can be extended to use the Unscented Kalman Filter (UKF), and describe a sampling algorithm that minimizes the number of samples required to find a good path. Finally, we demonstrate the BRM path-planning algorithm on the helicopter, navigating in an indoor environment with a laser range-finder.