多机器人并行动态包围体层次树碰撞检测算法

Multi-Robot Parallel Dynamic Bounding Volume Hierarchy Tree Collision Detection Algorithm

针对现有多机器人间碰撞检测算法耗时过多的问题,提出上层动态剔除层、中间连杆层、底层3层结构的并行动态包围体层次树碰撞检测算法.首先采用3层结构构建机器人两两间动态包围体层次树;然后依次对上、中、底各层设计并行加速的并行架构,采用OpenMP的3种并行结构实现碰撞检测并行计算.通过6或8个机器人工作站进行实验并分析算法的时间复杂度,结果表明,在相同实验条件下,动态包围体层次树中间连杆层、底层并行处理后碰撞检测效率是原动态包围体层次树的2倍左右,是RAPID的4倍以上;所提出的并行架构能够发挥出动态包围体层次树的层次结构优势,并行计算下的动态包围体层次树算法能有效地提高多机器人间碰撞检测效率.

The existing collision detection algorithms for multi‐robot are excessively time‐consuming . To speed up the process ,a parallel collision detection algorithm using dynamic bounding volume tree with a three‐layer hierarchy was proposed .This new hierarchy consists of an upper dynamic removal layer ,a middle link layer and a bottom layer .Firstly ,the three‐layer hierarchy was adopted to build a dynamic bounding volume tree between every two robots . Secondly , a parallel architecture was designed to compute each layer respectively and speed up the calculation in parallel .Lastly ,parallel computing collision detection was implemented based on the three parallel structures using the OpenMP .Experiments performed on a 6/8 robots workstation and the analysis of time complexity show that under the same experimental conditions ,w hen parallel computing the middle link layer and the bottom layer of the dynamic bounding volume tree ,the efficiency of collision detection is about two times faster than that of the original data structure ,and over four times faster than that of RAPID . The proposed parallel architecture fully takes advantage of the hierarchical structure of the dynamic bounding volume tree ,and effectively improves the efficiency of collision detection among multi‐robot .