Robot Path Planning for Multiple Target Regions

Optimal path planning to point goals is a well-researched problem. However, in the context of mobile robotics, it is often desirable to generate plans which visit a sequence of regions, rather than point goals. In this paper, we investigate methods for planning paths which visit multiple regions in a specified order, whilst minimising total path cost. We propose Multi-Region A*, an extension to the A* algorithm with an admissible heuristic for traversing multiple target regions. The heuristic is used to trim sub-optimal paths from the search, thereby reducing the computation time required to find the optimal solution. Additionally, we extend this method to create the Windowed Multi-Region A* which plans through overlapping sequences of regions. This provides a mechanism to trade-off optimality against computation time. We evaluate the performance of the proposed methods against point-to-point A* planning methods using a simulation of a wheeled office robot. The evaluation shows that Multi-Region A* with search pruning produces an optimal path, and the Windowed Multi-Region A* with a small window size gives a good approximate solution without compromising the total navigation time, in addition to providing robustness to dynamic obstacles.