LEARNING HIERARCHICAL TRAVERSABILITY REPRESENTATION FOR EFFICIENT MULTI-RESOLUTION PATH PLANNING

Abstract

Path finding on grid-based obstacle maps is an important and much studied problem with applications in robotics and autonomy. Traditionally, in the AI community, heuristic search methods (e.g. based on Dijkstra and A*, or based on random trees) are used to solve this problem. This search, however incurs significant computational cost that grows with the size and resolution of the obstacle grid and has to be mitigated with effective heuristics in order to allow path finding in real time. In this work we introduce a learning framework using deep neural networks with a stackable convolution kernel to establish a hierarchy of directional traversability representations with decreasing resolution that can serve as an efficient heuristic to guide a multi-resolution path planner. This path planner finds paths efficiently starting on the lowest resolution traversability representation and then refining the path incrementally through the hierarchy until it addresses the original obstacle constraints. We demonstrate the benefits and applicability of this approach on datasets of maps we created to represent both indoor and outdoor environments in order to represent different real world applications. The conducted experiments show that our method can improve the time of path planning by 30% in indoor environments and 66% in outdoor environments compared to the application of the same heuristic search method applied to the original obstacle map, which demonstrates the effectiveness of this method.