一种陌生环境的无人机在线Laguerre航路规划方法

魏铂淞, 张启瑞, 许卓凡, 王亮

(1.西北工业大学 航天学院, 陕西 西安 710072;2.空军工程大学 航空航天工程学院, 陕西 西安 710038;3.西北工业大学 无人机特种技术国家重点实验室, 陕西 西安 710065)

一种陌生环境的无人机在线Laguerre航路规划方法

魏铂淞1, 张启瑞2, 许卓凡2, 王亮3

(1.西北工业大学 航天学院, 陕西 西安 710072;2.空军工程大学 航空航天工程学院, 陕西 西安 710038;3.西北工业大学 无人机特种技术国家重点实验室, 陕西 西安 710065)

针对多旋翼无人机在陌生城市低空安全飞行的需要,研究了适合于陌生环境应用的在线航路规划方法。在分析传统Laguerre图航路规划原理及其航路安全性优势的基础上,首先导出了面向单个拟飞通道的Laguerre规划航路的特性。进而,通过最小化航路安全误差,建立了单个航段的最佳安全航路。在上述研究的基础上,提出了面向陌生环境的在线滚动式Laguerre航路规划方法。设计了模拟城市建筑物分布的仿真飞行场景,并通过对比分析不同规划方法对于仿真场景的航路规划结果,显示了本文算法在航路规划问题中避撞安全性方面的优势。

多旋翼无人飞行器; 航路规划; Laguerre图; 城市环境

0 引言

近年来,由于操控方便、价格低廉、用途广泛等原因,小型商业多旋翼无人机发展迅速,正在受到越来越多的重视和喜爱。在技术和市场的共同推动下,未来城市商业无人机的发展和运用空间极为广阔。据有关机构预测,未来十年商业无人机的市场产值可能达到千亿美元。但无人机发展和运用的一路高歌猛进,也正在给无人机在城市的低空飞行安全带来巨大的挑战,无人机撞击建筑物的事件时有发生。最近两年连续发生过无人机撞击建筑物而坠毁的事件[1]。如何保证无人机在城市低空飞行的安全,已成为一个亟待研究和解决的问题。

航路规划是保证无人机飞行安全的重要技术[2-3]。传统的航路规划方法包括基于遍历搜索原理的A*类航路规划方法[4]、基于Voronoi图的方法[5]、基于Laguerre图的方法[6]、基于速度场等的航路规划方法[7-8]。大多数传统航路规划方法是预先完成型方法,需要事先知道飞行区域的环境信息。这种要求难以适用于陌生的城市环境。为此,本文将对面向陌生城市环境的基于Laguerre图的在线安全航路规划方法进行研究。

1 城市环境航路规划及Laguerre图方法

1.1 陌生城市环境的航路规划问题

低空城市环境中的航路规划有其特殊性,首先应考虑安全问题。文献[9]将城市建筑物看作各种不规则的威胁区,首次将基于Laguerre图的规划方法扩展到对于非圆形不规则威胁区的航路规划,建立了基于Laguerre图的自优化A*航路规划算法。但这一方法需要为所有的非圆形威胁区建立外接圆,需要提前预知所有的建筑物及其分布,且规划必须提前完成。对于障碍物分布密集的情形,其执行效率也会降低。该方法的这些运行需求,对于无法提前掌握详细环境信息的陌生任务区域来说,是难以适应的。

求解陌生城市环境中的航路规划问题,是要在预先缺少任务区域详细地理和环境信息的情况下,为无人机确定出可飞的安全航路。这一要求极大地限制了各种需要预先完成的规划方法的运用。考虑到无人机可以利用自身携带的CCD相机等光电探测设备和图像处理系统实时感知前方的环境,因此,如果能在此基础上实现实时航路规划,就可以较好地解决这一难题。为此,本文将建立一种基于Laguerre图的在线安全航路规划方法。

1.2 基于Laguerre图的航路规划

根据文献[6,10],Laguerre图是对于一组圆的加权Voronoi图。通常意义上的Voronoi图考虑的是平面中一组点的集合。对于集合中的每一个点,平面中到该点距离小于到其他点的距离的点构成的多边形区域即称为Voronoi图,这里的距离度量就是点到点的欧式距离。如果把点的集合换成圆的集合,把距离度量换成Laguerre距离,即点到圆的切点的距离,那么,所得到的图形就被称之为Laguerre图。其数学定义阐述如下:

(1)

为了更方便地构造Laguerre图,文献[7]建立了一种能够有效降低计算规模的构造算法,将Laguerre图用于航路规划,是考虑到Laguerre图用圆替换了点,更加接近于对威胁区的表达,所以可以得到更好的安全航路。仿真研究也表明,基于Laguerre图的航路规划相较于Voronoi图方法,对于航路安全有着突出优势。

2 基于Laguerre图在线滚动航路规划方法

传统的Laguerre图航路规划是在已知任务区域全局信息的情况下,首先构建出任务区域的全局Laguerre图,再通过对所有可能航路的代价评估,一次性得到全局规划航路。考虑到陌生城市环境的特点,将全程航路分解为若干个航段,首先考察单个航段的最佳避撞安全航路,然后再完成全航程的航路规划。

2.1 基于Laguerre图的单航段航路规划

设建筑物A和建筑物B的阴影矩形如图1所示。其边界A1A2与边界B1B2之间的通道为拟飞通道。为简化分析,假设两个建筑物具有等长的边,即A1A2=B1B2=2a。将每个拟飞通道设定为一个独立航段。为完成基于Laguerre图的航路规划,分别以A1A2和B1B2为弦做外接圆,圆心分别位于各自垂直平分线上的P点和O点,两个外接圆的半径分别为rA和rB。记边界A1A2与B1B2的中点分别为F和E点,圆心距OP=b。

图1 单个拟飞通道的Laguerre航路分析图Fig.1 Diagram for analysis of Laguerre route of an aisle

按照Laguerre图定义,由圆O和圆P生成的Laguerre边是位于两个外接圆之间的直线,记为C1C2,设其与建筑物A的边界的垂直距离为LA,则直线C1C2就是对应这两个外接圆的Laguerre航路。为进一步分析该航路的安全特性,取C1C2上的任意一点G,从该点向两个圆分别作切线,切点为Q和H。则由Laguerre边的定义可知GH=GQ。在图1中,存在两组直角三角形关系,从而可得两组几何方程:

(2)

(3)

结合GH=GQ可得:

(4)

同时,由图中几何关系可知PG=PF+LA,OG=OE+LB,且L=LA+LB。将这些等式关系带入式(4),可以进一步导出:

LB×OE)+(PF2-OE2)

(5)

(6)

2(L-LA)×OE

(7)

L2=2LA(PF+OE+L)-2L×OE

=2LA×b-2L×OE

(8)

进一步可导出C1C2与建筑物外边界的距离为:

(9)

根据式(9),对位于两个建筑物之间的单个航段,基于Laguerre图得到的规划航路是沿着该通道纵向、与建筑物A的外边界距离为LA=(L2+2L×OE)/2b的直线。定义该航路与两侧建筑物外边界的距离的平方和为避撞安全误差ES,即:

(10)

对应于最安全的防碰撞航路,必然使下式成立:

(11)

(12)

由此得出结论,根据Laguerre图的航路规划原理,位于两个建筑物之间的单个拟飞通道的最佳防碰撞安全航路位于该通道的中位航路上。依据该结论,可以很方便地为每个航段获得最安全的Laguerre规划航路。

2.2 在线Laguerre航路规划

基于上述分析和结论,对在城市环境中飞行的小型旋翼无人机,可以通过单航段的滚动Laguerre规划实现全程实时航路规划。首先,无人机可利用机载图像处理系统实时感知当前拟飞通道的边界信息。依据这些信息建立通道的Laguerre航路,并以中位航路作为安全飞行航路，将航路指令注入飞行控制计算机,控制无人机按照该航路完成本航段飞行。当该航段完成后,再按上述流程滚动进行下一航段的规划和飞行,直至完成最后一个航段。这样,通过对每一个航段均滚动执行相同的规划算法,即可使无人机在线完成基于Laguerre图的全程安全航路规划。该方法运行流程如图2所示。

图2 在线Laguerre航路规划方法流程图Fig.2 Flowchart of the online Laguerre route planning method

3 仿真试验分析

以小型旋翼无人机在城市低空环境中运送货物为背景,使无人机模拟穿越建筑物密集的城市环境。按照某城市小区建筑物的实际分布情况,设计仿真试验的模拟飞行场景如图3所示。

图3 仿真试验模拟飞行场景图Fig.3 Simulated testing scenario in emulation test

分别使用3种不同方法为无人机完成从起点STA到终点END的航路规划。3种方法得到的规划航路如图4所示。其中,方法1为文献[9]提出的基于Laguerre图的自优化A*航路规划算法(LA-STAR);方法2为文献[11]提出的基于局部回溯与广度优先思想相结合的综合航路规划方法(LBT);方法3为本文建立的在线Laguerre安全航路规划方法(LRP)。需要说明的是,在LA-STAR方法中,需要为拟飞区域中的每个建筑物都建立一定的外接圆,然后才能进行基于Laguerre图的航路规划。而LBT方法在运用时同样需要提前知道拟飞区域的建筑物分布信息。另外,本文航路规划算法得到的是初始航路,在转弯处通常是折线。为了适应实际的飞行,需要对这些折线进行平滑处理,图中在折线处显示的小内切圆,就是用于平滑处理的。

图4 3种方法规划出的航路Fig.4 Routes planned with three methods

为进一步考察仿真试验得到的规划航路的防碰撞安全性,根据式(10)定义的航路避撞安全误差,3种方法得到的航路避撞安全误差曲线如图5所示。

图5 仿真规划航路的避撞安全误差曲线Fig.5 Curves of route collision avoidance safe errors

为保证不同航路上对比航点选择的一致性,沿飞行方向任意选取了N个参考点P1到PN,按照这些参考点在每个航路上对应选择N个航点,其中Pk表示1～N的任意位置。考察每个航点处的避撞安全误差值。在这里,主要考察的并不是每条航路对应的误差值的大小,因为每条航路所经历的通道不一样,通道宽度也不同,所以无法按统一标准来比较误差的大小。针对航路防碰撞的特点,主要考察误差曲线在通道内的起伏情况。从3条航路对应的避撞安全误差曲线可以看出,本文方法规划出的航路防撞误差曲线在飞行通道内起伏平稳,显示了本文方法所得到的航路对于防碰撞具有更大的优势。

4 结束语

本文以陌生城市的低空飞行任务为背景,在已有研究的基础上,探索了将Laguerre图方法应用于陌生城市环境的实时在线规划方法。尽管仿真试验结果表明本文方法在实时航路安全方面取得了较好的效果,但还需进行更加深入的研究，特别是目前的研究只是考虑了较简单的建筑物位置关系。在现代化大城市中,各种高层建筑物不仅形状多样,而且位置关系复杂。对于在这些复杂情况下的方法研究和实践,将是今后研究的一个重点。

[1] Liam Stack.New Jersey man is arrested after drone hits Empire State building[EB/OL].(2016.02.05)[2016.5].http://www.nytimes.com/2016/02/05/nyregion/new-jersey-man-is-arrested-after-drone-hits-empire-state-building.html.

[2] 魏瑞轩,李学仁.无人机系统与作战运用[M].北京:国防工业出版社, 2014.

[3] 董世友,龙国庆,祝小平.无人机航路规划的研究[J].飞行力学,2004 22(3):21-24.

[4] Yao J F,Lin C,Xie X B,et al.Path planning for virtual human motion using improved A*star algorithm[C]//Proc. of the 7th International Conference on Information Technology:New Generations.Las Vegas,NV:IEEE,2010:1154-1158.

[5] 张雷,王道波,段海滨,等.一种用于SEAD任务的改进型Voronoi图[J].国防科技大学学报,2010,32(3): 121-126.

[6] 王树磊,魏瑞轩,沈东,等.面向航路规划的Laguerre图构造算法[J].系统工程与电子技术,2013,35(3):552-556.

[7] 李春涛,易小芹,胡木.基于速度矢量场的无人机实时动态航路规划[J].南京航空航天大学学报,2012,44(3):340-346.

[8] 肖秦琨,高晓光.一种无人机局部航路重规划算法研究[J].飞行力学,2006,24(1):85-88.

[9] 魏瑞轩,许卓凡,王树磊,等,基于Laguerre图的自优化A*无人飞行器航路规划算法[J].系统工程与电子技术,2015,37(3):577-582.

[10] Marina Gavrilova,Jon Rokne.On sweep-plane analysis of Laguerre Verona diagram[C]//Proc.of the 4th International Symposium on Voronoi Diagram in Science and Engineering (ISVD 2007).Washington,DC,USA:IEEE,2007:260-264.

[11] 张启瑞,魏瑞轩,茹常剑,等.城市密集不规则障碍空间无人飞行器航路规划[J].控制理论与应用,2015,32(10):1407-1413.

(编辑：方春玲)

A method of online Laguerre route planning for UAVs flying in an unknown regions

WEI Bo-song1, ZHANG Qi-rui2, XU Zhuo-fan2, WANG Liang3

(1.School of Astronautics, NWPU, Xi’an 710072, China;2.Aeronautics and Astronautics Engineering College, AFEU, Xi’an 710038, China;3.National Key Laboratory of Special Technology on UAV, NWPU, Xi’an 710065, China)

Aiming at the safe flying requirement for multi-rotor UAV in urban lower aerial regions, a method of online route planning for unknown urban areas are studied in this paper. By demonstrating the route planning principle of the traditional Laguerre diagram method and advantages on route safety, the characteristic of Laguerre route planning for an independent flight aisle is firstly studied. And then by minimizing the route’s collision avoidance safe error, the safest route is built for a single flying-phrase channel. Based on above researches, an online rolling Laguerre method for route planning is presented for unknown urban lower flying areas. A simulation flight testing scenario is designed by referring a real buildings distribution on an urban community. By comparing the route planning results of various planning methods for the same simulation flight scenes, the advantages on route collision avoidance and online route planning have been shown for the method mentioned in this paper.

multi-rotor UAV; route planning; Laguerre diagram; urban area

2016-03-22;

2016-09-05;

时间:2016-09-22 14:55

国家自然科学基金资助(61573373)

魏铂淞(1995-)，男，陕西岐山人，本科生，研究方向为探测制导与控制工程。

V279

A

1002-0853(2017)01-0057-04