| We consider path planning for multiple mobile robots navigating in a rectangular maze divided into cells of equal size. Some cells contain permanent obstacles and some are empty and available for a robot to move into. All robots are synchronized and each robot is allowed to move into an empty cell adjacent to the one that it presently occupies. The objective is to determine a set of collision-free paths that lead each robot from a specified initial location to a specified goal location in minimum time.;Our study provides new near-optimal on-line algorithms for safe navigation of limited-vision robots. We also provide exact expressions for the mean path lengths within mazes of arbitrary architectures.;Two general approaches are investigated: centralized planning and distributed planning. Using centralized-planning, a single processor with full knowledge of the maze topology and of the initial and goal locations of the robots determines the time-optimal paths using standard graph search techniques. The central planners provide optimal solutions (whenever one exists) but they are computationally prohibitive--the complexity of the graph search grows exponentially in the number of navigating robots. In the distributed-planning version, minimum-length paths are first computed for each robot independently (i.e., under the assumption that each robot navigates the maze alone). The individually-optimal paths are then modified locally to produce collision-free paths. Our modifications are based on limiting the robots' visible neighborhood--robots adjust their independently-planned paths when they "see" other robots in their vicinity and realize the threat of collision. In the limit, robots are totally "blind" and they learn about the existence of other robots by colliding with them. |
