A two-tiered global path planning strategy for limited memory mobile robots

Multi-robot systems have inherent advantages such as the ability to allocate and redistribute tasks across the team of robots. For multi-robot tasks such as exploration of large environments, some of the available robots may only possess simple embedded controllers with limited memory capacity. However, in some situations these limited robots may be required to perform global path planning to navigate beyond localised regions of the large environment. Global path planning can be problematic for the limited memory robots if they are unable to store the entire map in their local memory. Hence, this paper presents and evaluates a two-tiered path planning technique to permit global path planning. A set of local maps describing the global map is searched using a two-tiered A* algorithm that executes entirely on the limited memory robots. Planning time, data communication and path length are evaluated for various combinations of local and global maps. Employing smaller local map sizes in large global maps is capable of yielding superior or comparable execution times to non-memory constrained planning. (C) 2011 Elsevier B.V. All rights reserved.