Abstract
This work makes two contributions to geometric motion planning for multiple robots: 1) motion plans are computed that simultaneously optimize an independent performance measure for each robot; 2) a general spectrum is defined between decoupled and centralized planning, in which we introduce coordination along independent roadmaps. By considering independent performance measures, we introduce a form of optimality that is consistent with concepts from multiobjective optimization and game theory literature. Previous multiple-robot motion planning approaches that consider optimality combine individual performance measures into a scalar criterion. As a result, these methods can fail to find many potentially useful motion plans. We present implemented, multiple-robot motion planning algorithms that are derived from the principle of optimality, for three problem classes along the spectrum between centralized and decoupled planning: 1) coordination along fixed, independent paths; 2) coordination along independent roadmaps; 3) general, unconstrained motion planning. Computed examples are presented for all three problem classes that illustrate the concepts and algorithms.
Original language | English (US) |
---|---|
Pages (from-to) | 912-925 |
Number of pages | 14 |
Journal | IEEE Transactions on Robotics and Automation |
Volume | 14 |
Issue number | 6 |
DOIs | |
State | Published - 1998 |
Externally published | Yes |
Keywords
- Game-theory
- Mobile robots
- Motion planning
- Multiobjective optimization
- Multiple robots
- Obstacle avoidance
- Path planning
- Scheduling
ASJC Scopus subject areas
- Control and Systems Engineering
- Electrical and Electronic Engineering