Online Roadmaps for Task-based Navigation in Urban Terrain

Abstract

Sensor‐based navigation in a priori unknown terrain is a challenging problem, even if one could assume perfect obstacle sensing and vehicle state estimation. Especially in urban terrain or rescue scenarios, the terrain topology is fully three dimensional, i.e. overhangs from power lines, bridges or debris exist that invalidate the common assumption of the terrain being a 2D height map. It is a challenging problem to perform computationally efficient planning from higher level task planning down to the effective flight control actions. This is particularly a concern on board embedded computers of small aerial platforms. In this presentation we focus on sensor‐based planning in urban example scenarios. We briefly present our Mission Planning and Execution (MiPlEx) framework that comprises an online roadmap approach for multi-query planning in 3D terrain. Simply stated, due to its multi‐query property the amount of collision checking is reduced, such that a persistent free space representation allows to spare computing resources for the task planning and vehicle guidance. Although roadmaps were initially developed as a static a priori path planner, it now needs to be continuously updated during sensor‐based navigation through complex terrain topologies. Challenges addressed by our approach deal with an online capable search graph update method, to find a suitable set of sampling parameters as well as a local connection strategy that accounts for the limited obstacle sensor field of view(s) and the aircraft dynamic limits.