计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (27): 233-238.

• 工程与应用 • 上一篇    下一篇

拉格朗日松弛的无人机路径规划

刘  山1,顾晔倩1,李雨石1,曹盛文1,刘  轩2   

  1. 1.中国民航大学 计算机学院,天津 300300
    2.麦基尔大学 电气和计算机工程系,魁北克 蒙特利尔 H3AoG4,加拿大
  • 出版日期:2012-09-21 发布日期:2012-09-24

Lagrange relaxation for UAV path planning

LIU Shan1, GU Yeqian1, LI Yushi1, CAO Shengwen1, LIU Xuan2   

  1. 1.School of Computer Application, Civil Aviation?University of China, Tianjin 300300, China
    2.Department of Electrical and Computer Engineering, McGill University, Montréal, Quebec H3AoG4, Canada
  • Online:2012-09-21 Published:2012-09-24

摘要: 提出了基于城市建筑物遮挡模型的无人驾驶飞行器(简称无人机)路径规划方法,主要包含两方面的内容:一是利用圆柱体虚拟城市的建筑物环境,使建筑物对无人机的遮挡面积可计算,另外,由于建筑物的相对位置会相互遮挡,不可以进行简单的面积加法。采用程序实现了无人机的遮挡总和的计算,即每个建筑物遮挡面积的并集。二是在计算出无人机飞行的水平平面上(x,y)点的遮挡曲面值的基础上,给出了无人机基于拉格朗日松弛算法的优化路径规划,即走一条遮挡面积最小的路径的方法。给出matlab仿真结果,实验结果表明该方法是十分有效的。

关键词: 无人机, 路径规划, 城市环境, 遮挡, 拉格朗日松弛算法

Abstract: It proposes a path planning algorithm based on an urban building block model for Unmanned Air Vehicle(UAV for short).The proposed algorithm mainly contains two aspects. First the algorithm simulates the buildings in urban environment with cylinders, so it’s able to calculate the block area of the relative position between the buildings and UAV. In addition, the total shading area isn’t the addition of each shading area, instead it’s a union set. The algorithm calculates the union set by using a program. Second, after calculating the curved surface of UAV’s flight plane, this algorithm proposes an optimal path planning method based on Lagrange relaxation of UAV. The path is a polygonal line along the equant diagonal line on the searching area of UAV. The shading area of this path is minimal. The Matlab simulation result suggests this algorithm is efficient.

Key words: Unmanned Air Vehicle(UAV), path planning, urban environment, blocked, Lagrange relaxation algorithm