基于改进Dijkstra算法的防冲突最短路径规划研究  

Anti-collision Shortest Path Planning Based on Improved Dijkstra Algorithm

作　　者：黄翼虎[1] 于亚楠 HUANG Yi-hu;YU Ya-nan(College of Automation and Electronic Engineering,Qingdao University of Science and Technology,Qingdao 266061,China)

机构地区：[1]青岛科技大学自动化与电子工程学院,山东青岛266061

出　　处：《计算机与现代化》2022年第8期20-24,共5页Computer and Modernization

摘　　要：多无人机在执行作业任务时可能面临发生航迹冲突的矛盾,由此提出一种改进Dijkstra算法用来实现多无人机寻找最短且互不冲突航线的功能。在经典Dijkstra算法搜寻并对各航迹节点遍历运算的过程中,通过引入各节点的前驱节点变长回溯数组来记录各节点包含的所有前驱节点,找出各任务从起始点到达目标点所存在的全部可行的最短长度航线。再引入时间窗冲突判断模型从各任务的所有可行航线中将互不冲突的航线分离出来,一旦所有航线都冲突,则将其中一条最短航线中的冲突节点当作临时障碍点处理,通过改变回溯数组重新找出与其他任务互不冲突的一条最短航线。应用Matlab软件设计编写程序来进行算法验证,实验表明该改进算法在多无人机执行作业任务时可以规划出各任务包含的全部长度最短且互不冲突的航线,任务集合的规划效率有了明显提高。Multiple UAVs may face the contradiction of track conflict when performing operational tasks.Therefore,an improved Dijkstra algorithm is proposed to realize the function of multiple UAVs to find the shortest and non-conflicting route.In the process of searching and traversing each track node by the classical Dijkstra algorithm,the variable length backtracking array of precursor nodes of each node is introduced to record all precursor nodes contained in each node,and all feasible shortest length routes from the starting point to the target point of each task are found.Then the time window conflict judgment model is introduced to separate the non-conflicting routes from all feasible routes of each task.Once all routes conflict,the conflict node in one of the shortest routes is treated as a temporary obstacle point and the shortest route that does not conflict with other tasks is re found by changing the backtracking array.Matlab software is used to design and write programs to verify the algorithm.The experiments show that the improved algorithm can plan all the shortest and non-conflicting routes contained in each task when multiple UAVs perform operational tasks and the planning efficiency of task set has been significantly improved.

关 键 词：DIJKSTRA算法 变长回溯数组 时间窗模型 互不冲突路径 最短路径 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]