Path Planning by Negotiation for Decentralized Agents

This paper presents a real-time path-planning algorithm for decentralized agents, which provides guaranteed collision-free paths for the agents towards their desired destinations. The algorithm is run locally on the agents, which can exchange information using wireless communication. The algorithm is robust with respect to arbitrary delays in the wireless traffic, possible sources being transmission time, error correction, and others. Agents move on reserved areas which are guaranteed not to intersect, therefore ensuring safety. The basic algorithm is augmented by the introduction of waypoints, which increase performance at the cost of additional wireless traffic. The algorithm is successfully implemented in simulation and on a real system of autonomous robots. The results are presented and discussed.