陈 琳，付 兵，潘海鸿，戴 骏，董海涛

(1. 广西大学 机械工程学院，南宁 530004；2. 广西制造系统与先进制造技术重点实验室，南宁 530004；3.湖北汽车工业学院 机械工程学院，湖北 十堰 442002)

一种适用于多机器人的动态包围体层次树碰撞检测算法*

陈 琳1,2，付 兵1,3，潘海鸿1,2，戴 骏1,2，董海涛1,2

(1. 广西大学 机械工程学院，南宁 530004；2. 广西制造系统与先进制造技术重点实验室，南宁 530004；3.湖北汽车工业学院 机械工程学院，湖北 十堰 442002)

多机器人协同工作在喷涂、焊接、装配等工业现场应用广泛。多机器人碰撞检测是多机器人系统安全、可靠工作的内在保证。针对现有多机器人间碰撞检测算法耗时过多问题，提出动态包围体层次树碰撞检测算法，该算法利用不同包围体的长处构建三层结构的动态包围体层次树，采用层次展开的遍历方式提高多机器人间碰撞检测效率。在多机器人工作站中进行仿真实验，得出对2、4、6、8个机器人采用动态包围体层次树碰撞检测算法的碰撞检测效率分别是RAPID算法的1.657，1.738，2.088，2.149倍。这验证所提出的动态包围体层次树碰撞检测算法能有效提高多机器人间碰撞检测效率。

动态包围体层次树;碰撞检测;多机器人

0 引言

碰撞检测的目的是用来探测空间中移动的几何物体之间是否相交，相交则找出相交的特征(overlap features)。碰撞检测广泛应用于工程实践，机器人，计算图形处理，动画，CAD/CAM，游戏中。因其重要性，许多学者在过去的二十年里对碰撞检测算法进行了广泛研究[1]。他们分别提出各具特色的AABB[2]，OBB[3]，bounding sphere[4]，K-dops[5]，SSV[6]等包围体(bounding volume)算法，并用于碰撞检测中。……