CAJ | 학술논문

针对现有多机器人间碰撞检测算法耗时过多的问题，提出上层动态剔除层、中间连杆层、底层3层结构的并行动态包围体层次树碰撞检测算法。首先采用3层结构构建机器人两两间动态包围体层次树；然后依次对上、中、底各层设计并行加速的并行架构，采用OpenM P的3种并行结构实现碰撞检测并行计算。通过6或8个机器人工作站进行实验并分析算法的时间复杂度，结果表明，在相同实验条件下，动态包围体层次树中间连杆层、底层并行处理后碰撞检测效率是原动态包围体层次树的2倍左右，是RA PID的4倍以上；所提出的并行架构能够发挥出动态包围体层次树的层次结构优势，并行计算下的动态包围体层次树算法能有效地提高多机器人间碰撞检测效率。
침대현유다궤기인간팽당검측산법모시과다적문제，제출상층동태척제층、중간련간층、저층3층결구적병행동태포위체층차수팽당검측산법。수선채용3층결구구건궤기인량량간동태포위체층차수；연후의차대상、중、저각층설계병행가속적병행가구，채용OpenM P적3충병행결구실현팽당검측병행계산。통과6혹8개궤기인공작참진행실험병분석산법적시간복잡도，결과표명，재상동실험조건하，동태포위체층차수중간련간층、저층병행처리후팽당검측효솔시원동태포위체층차수적2배좌우，시RA PID적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 .