Collision and Deadlock Avoidance in Multirobot Systems: A Distributed Approach
提出一种实时分布式算法，通过反复停止和恢复机器人来避免多机器人系统中的碰撞和死锁，每个机器人自主检查后续状态是否被占用以及单步移动是否会导致死锁。
Collision avoidance is a critical problem in motion planning and control of multirobot systems. Moreover, it may induce deadlocks during the procedure to avoid collisions. In this paper, we study the motion control of multirobot systems where each robot has its own predetermined and closed path to execute persistent motion. We propose a real-time and distributed algorithm for both collision and deadlock avoidance by repeatedly stopping and resuming robots. The motion of each robot is first modeled as a labeled transition system, and then controlled by a distributed algorithm to avoid collisions and deadlocks. Each robot can execute the algorithm autonomously and real-timely by checking whether its succeeding state is occupied and whether the one-step move can cause deadlocks. Performance analysis of the proposed algorithm is also conducted. The conclusion is that the algorithm is not only practically operative but also maximally permissive. A set of simulations for a system with four robots are carried out in MATLAB. The results also validate the effectiveness of our algorithm.