基于初等运动的多机器人避碰及死锁预防

该文以一实际应用为背景提出了多移动机器人避碰及死锁预防算法 ,该算法将机器人的运行环境形式化地描述为初等运动集、冲突图、总任务集及机器人作业集 ,利用集合论、图论的有关方法及技术实现了多机器人间的避碰与死锁预防 .当机器人的运行环境改变时 ,只需要对相应的集合描述文件进行修改 ,而不用对程序做任何改动 .算法的另一个特点是利用避碰算法巧妙地完成了死锁预防 .仿真和实际运行证明了该算法高效可靠 .

This paper gives the algorithms of multi-robot collision avoidance and deadlock prevention. The working environment of robots is formally described as an Elementary Motion Set, Conflict Graph, Task Set and Job Set. The input of the algorithms in this paper is only these four sets. Theory and method of set and graph are used to realize collision avoidance and deadlock prevention. The movement of mobile robots are decomposed to elementary motion, and when a robot is executing a certain element motion, any other robot can not executing this elementary motion and the elementary motion that is conflict to this one. An algorithm has been developed to realize collision avoidance through lock and unlock the elementary motion at the correct time. The main idea of deadlock prevention is to find all deadlock circles at first, and then the two elementary motions at the exit of this deadlock circle are defined as conflict even though they are not conflict in actually. Because of the effect of the collision avoidance algorithm, the exit of this deadlock circle is always open,  so the deadlock can be prevented. The detail of this algorithm has been presented in this paper. The four sets are described as an input file of program, so when the environment has been changed, the only thing we should do is only to rewrite this four input file, and then these collision avoidance and deadlock prevention algorithms will work correctly without any change. Another special character of the algorithm is that the collision avoidance algorithm is also used to prevent the deadlock, and it lightens the burden of system and reduces the chance of mistake. The background of this research is an actually application. The simulation result and the actual application of these algorithms in a Multi-AGV system are given at the end of this paper. Both the simulation and the actual application have verified that the algorithms are efficient and reliable.