Abstract
We propose a distributed and optimal motion planning algorithm for multiple robots. The computationally expensive problem is decomposed into two modules - path planning and velocity planning. The D* search method is applied in both modules, based on either geometric formulation or schedule formulation. Optimization is achieved at the individual robot level by defining cost functions to minimize, and also at the team level by a global measurement function reflecting performance indices of interest as a team. Contrary to our knowledge of previous results on multi-robot motion planning that either obtain optimal solutions through centralized and exhaustive computing, or achieve distributed implementations without considering any optimization issues, our approach combines these two features and explicitly optimizes performance functions through a distributed implementation. It is also one of the few that is capable of handling outdoor rough terrain environments and real time replanning. Simulations are shown on a Mars-like rough terrain using a 3D vehicle planner and control simulator. The algorithm was also implemented and successfully run on a group of Nomad 200 indoor robots.
Original language | English |
---|---|
Pages (from-to) | 2612-2619 |
Number of pages | 8 |
Journal | Proceedings - IEEE International Conference on Robotics and Automation |
Volume | 3 |
State | Published - 2002 |
Event | 2002 IEEE International Conference on Robotics adn Automation - Washington, DC, United States Duration: 11 May 2002 → 15 May 2002 |
Keywords
- Coordination diagram
- Cost function
- Motion planning
- Multi robots
- Performance index