Path planning on grid maps with unknown goal poses

Abstract

Path planning for robots typically consists of finding a path from a given start state to one or multiple given goal states. However, there are situations in which the pose of the goal state is not explicitly known, e.g. in sensor-based autonomous driving in unknown environments. This paper presents a path planner that is capable of planning feasible paths in the absence of goal poses. The approach combines the advantages of both the focused search of A* and the uniformly-exploring search of Rapidly Exploring Random Trees. With this approach, it is possible to quickly find potential goal states and their corresponding paths and to continue the exploration as processing time allows. Furthermore, it is shown how to cluster paths to extract the main possible directions. Results on simulation and real data are given to demonstrate the utility and efficiency of the proposed approach.