Incremental Path Planning Using Partial Map Information for Mobile Robots

This paper proposes a practical method for planning paths incrementally for mobile robots in unknown environments using the latest sensory information. A* algorithm was modified in this research for it to be able to handle an occupancy grid map with unknown information. Then the paper presented an algorithm that is able to robustly and incrementally searching for an optimal path based on the partial map simultaneously built by the robot. Waypoints was generated to further optimize the obtained path and were sequentially traced by the robot in a simple, reactive way. Extensive simulations and experiments were carried out to verify the proposed planning algorithm

I. Introduction

One important feature of autonomous mobile robots is their ability to adapt themselves to operate in unstructured environments. Promising path planning and navigation algorithms require the availability of both a sufficiently reliable estimation of the current vehicle location and a sufficiently precise map of the navigation area. However, since a priori model maps are rarely available, utilizing partial knowledge obtained from sensory information is essential for a robot to accomplish tasks such as exploration and path planning. To find a path between two points in a known environment, visibility graph approaches [1] or graph search algorithms (such as Dijkstras, A* algorithm [2] and Bellman-Fords algorithms [3]) can be used. Similar to graph search, search-based methods [4], [5] exhaustively explore the system's configuration space.