| Environments containing multiple robots may arise for any number of reasons. In such settings, the usual problems of collision avoidance and path planning are changed significantly and new types of problems are introduced. These new problems include coordinating the robots' motions, dividing work among the robots, and scheduling the use of common resources. Designing efficient algorithms to solve the unique multiple-robot problems helps to realize the potential benefits of the parallelism inherent in these systems.; Three multiple-robot systems are considered in this thesis. The first of these is a planar environment containing multiple mobile robots, each tethered by a cable to a unique point in their environment. Such robots are used for assembly, inspection, and hazardous waste clean-up tasks. Based on the model developed for this system, an algorithm for constructing a set of nonintersecting planar curves connecting specified pairs of points is developed, and the relationship between this problem and problems in VLSI design are shown.; The second system considered is a set of tethered robots moving in three dimensions. Such robots are used in underwater robotics. For both tethered-robot systems, polynomial-time motion-planning algorithms are presented. The algorithms produce cooperative motion plans that allow the robots to move simultaneously to their assigned destinations and result in desirable configurations of their cables. In certain cases the paths constructed will be the shortest possible paths; discussion of why this is not always possible is given.; The third system consists of a collection of robots, each capable of executing a terrain-covering algorithm in a planar environment. The problem addressed is how to divide a planar environment into a number of regions, so each robot may be assigned a region in which to execute its terrain-covering algorithm and all robots will do roughly the same amount of work. For this purpose, a new polygon partitioning problem is defined and a polynomial-time algorithm is developed to solve this problem.; The models and algorithms developed for the interesting new geometric problems presented by these systems lead to efficient and effective motion plans that realize some of the advantages of having many robots working in parallel. |
