Quality Roadmaps and Sparsification for lmproved Online Roadmap Efficiency

Abstract

This work surveys the problem of unmanned aerial vehicle which has to efficiently update its free space representation for real time online planning purposes in unknown terrains. Specifically, the objective of this work is making more efficient online roadmap updates onboard an unmanned rotorcraft. With a more efficient online roadmap, the vehicle can update larger sensor regions in real time, permitting the use of better sensors with wider field of view and, consequently, a more efficient exploration of big a priori unknown urban terrains. To produce a more efficient online roadmap, first we evaluate different sampling strategies used in sampling-based in motion planning. We adapt and speed up the state-of-art Incremental Roadmap Spanner to reduce the number of edges of the roadmap, while keeping near-optimal the roadmap paths. We propose the Memory Spanner Roadmap (MSpaR) approach, which is an enhancement in the adapted spanner to add an online repair capability. The proposed algorithm was implemented and evaluated in the Mission Planning and Execution framework (MiPlEx). The results show that MSpaR was able to reduce the CPU runtime of the planner by up 77 percent compared to the original k-nearest connected roadmap.