Decentralized motion planning for multiple mobile robots: The cocktail party model

This paper presents an approach for decentralized real-time motion planning for multiple mobile robots operating in a common 2-dimensional environment with unknown stationary obstacles. In our model, a robot can see (sense) the surrounding objects. It knows its current and its target's position, is able to distinguish a robot from an obstacle, and can assess the instantaneous motion of another robot. Other than this, a robot has no knowledge about the scene or of the paths and objectives of other robots. There is no mutual communication among the robots; no constraints are imposed on the paths or shapes of robots and obstacles. Each robot plans its path toward its target dynamically, based on its current position and the sensory feedback; only the translation component is considered for the planning purposes. With this model, it is clear that no provable motion planning strategy can be designed (a simple example with a dead-lock is discussed); this naturally points to heuristic algorithms. The suggested strategy is based on maze-searching techniques. Computer simulation results are provided that demonstrate good performance and a remarkable robustness of the algorithm (meaning by this a virtual impossibility to create a dead-lock in a ''random'' scene).