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

Abstract: 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.

Key words: Dijkstra algorithm, variable length backtracking array, time window model, non-conflicting paths, shortest path