Multiple path coordination for mobile robots: a geometric algorithm

Abstract

This paper presents a geometric based approach for multiple mobile robot motion coordination. All the robot paths being computed independently, we address the problem of coordinating the motion of the robots along their own path in such a way they do not collide each other. The proposed algorithm is based on a bounding box representation of the obstacles in the so-called coordination diagram. The algorithm is resolution-complete. Its efficiency is illustrated by examples involving more than 100 robots. 1 Introduction: Path coordination This paper addresses the following problem: consider n mobile robots sharing the same workspace and planning their paths independently; n such paths being given we want to devise an algorithm deciding whether coordinated motions exist for the mobile robots along their own paths, so that each robot can reach its own goal without colliding the other ones. The problem is known as the multiple robot path coordination problem [ Latombe, 1991b ] ....