Optimal route re-planning for mobile robots: a massively parallel incremental A* algorithm

Abstract

The principal advantage of incremental A* algorithms for precomputing and maintaining routes for mobile robotic vehicles is the completeness and optimality of the approach. However, the computational burden becomes unreasonable when large worlds are modeled or fine resolution is required, since the complexity is bound by the area modeled. This problem is compounded when multiple vehicles and multiple goals are involved, since routes to each goal from each vehicle must be maintained. This paper presents a massively parallel incremental A* algorithm suitable for implementing in VLSI. The number of iterations of the parallel algorithm is bound by the optimal path length, providing a significant speedup for large worlds. Empirical studies combined with a feasible VLSI design estimate that path calculations on a 1000 by 1000 world could be done in approximately 110 mS worse case.