基于可视图法的改进Dijkstra算法  

A Modified Dijkstra's Algorithm Based on Visibility Graph

作　　者：李大东[1] 孙秀霞[1] 彭建亮[1] 孙彪[1] 

机构地区：[1]空军工程大学工程学院,西安710038

出　　处：《电光与控制》2010年第3期40-43,共4页Electronics Optics & Control

摘　　要：针对基于可视图的Dijkstra单向最短路径规划算法难以加入飞行性能约束的问题,将飞行轨迹视为一系列直线和圆弧,利用转弯离开点与进入点构建三圆弧组合实现避障转弯,成功地在算法中引入最小转弯半径约束。采用纯数学公式推导,详细介绍了推导过程。算法减少了无关节点运算,提高了查询与规划最短路径效率。通过对比仿真,验证了算法有效性。It is usually difficult to integrate flight constrains into Dijkstra＇ s algorithm for uni-directional shortest path planning based on visible images. We took the vehicle trajectory as a series of lines and ares, used the leaving point and entering point of the turning circle for constructing a combination of three ares to avoid obstacles,and thus we introduced a constrain of minimum turning radius into the algorithm successfully. The formula derivation process was introduced in detail. The algorithm could reduce the calculation nodes and improve the effectiveness of shortest path searching and planning. Simulation result showed the practicability of this algorithm.

关 键 词：航迹规划 DIJKSTRA算法 可视图 避障路径规划 

分 类 号：V249[航空宇航科学与技术—飞行器设计]