Files and links (1)
PDFOpen Access (License Unspecified), Open Access
Dissertation
Multi-robot navigation in a maze
Doctor of Philosophy (Ph.D.), Drexel University
1996
DOI:
https://doi.org/10.17918/00009200
Abstract
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. 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. 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.
Metrics
35 File views/ downloads
12 Record Views
Details
- Title
- Multi-robot navigation in a maze
- Creators
- Andres Lebaudy
- Awarding Institution
- Drexel University
- Degree Awarded
- Doctor of Philosophy (Ph.D.)
- Publisher
- Drexel University; Philadelphia, Pennsylvania
- Number of pages
- xii, 127 pages
- Resource Type
- Dissertation
- Language
- English
- Academic Unit
- College of Engineering (1970-2026); Drexel University
- Other Identifier
- 991021888944504721