文章快速检索 高级检索

Route planning algorithm for configuring airborne pseudolites
ZENG Lingchuan , LI Dapeng , QU Yi , REN Aiai , GONG Yingkui
Received: 2015-07-16; Accepted: 2015-10-23; Published online: 2015-15-17 10:41
Foundation item: National Natural Science Foundation of China (91438207)
Corresponding author. Tel.: 010-82178658 E-mail: ykgong@aoe.ac.cn
Abstract: This paper focuses on the airborne pseudolites based on airships and proposes a route planning method to configure airborne pseudolites from the initial position to the target position. First, by analyzing the geometric dilution of precision (GDOP) as the performance of navigation enhancement, a route planning cost function was designed based on the distance and GDOP. Then, on the basis of sparse A* algorithm and analysis of constraint conditions, a route planning algorithm was proposed which can adjust the weights of distance and GDOP adaptively, and the route was smoothed by the Dubins curve. Finally, the route planning algorithm was validated through the simulated experiments. The simulated experimental results show that the route planning algorithm can reduce the GDOP cost effectively and improve user positional accuracy in the subsequent route planning if the GDOP value is severe at current time; on the other hand, while the GDOP approaches its optimal value, the algorithm will increase the weight of distance to make pseudolites move to their destinations as quickly as possible and reduce the time consumption during the subsequent route planning.
Key words: navigation enhancement     airborne pseudolites     route planning     sparse A* search algorithm     Dubins curve

1 空基伪卫星组网性能指标

 (1)

 (2)

 (3)

 (4)

 (5)

 (6)

 (7)

 (8)

 (9)

2 空基伪卫星航路规划算法设计

2.1 航路规划代价函数设计

A*算法是一种标准启发式搜索算法，在路径规划和图搜索领域中应用非常广泛。在利用A*算法进行航路搜索时，通常将规划环境表示为网格的形式，通过预先设定的代价函数寻找最小代价航路。算法对当前位置的每一个可能到达网格单元计算代价函数，然后选择代价函数最低的网格单元加入搜索空间。加入搜索空间的这一新网格单元又被用来进行下一次的搜索，产生更多的可能路径[13]

A*算法的代价函数定义为

 (10)

 (11)

 (12)

2.2 代价函数权重自适应调整

 (13)

 (14)

2.3 航路规划约束条件

 (15)

Dubins曲线由一系列圆弧及其切线组成，已被证明是在满足一定曲率条件下，连接给定方向向量的两点间的最短轨迹曲线[15]。这样，在给定飞艇最大曲率(挠率)的情况下，可以采用Dubins曲线对由传统稀疏A*算法规划出的路径进行平滑处理，得到可飞行路径。

 图 1 Dubins曲线平滑处理原理 Fig. 1 Principle of smoothing with Dubins curve
 (16)

2.4 基于稀疏A*算法的航路规划算法

1)对每颗伪卫星构造当前节点待扩展区。待扩展区的水平剖面是夹角大小为Φmax的2倍的扇面，扇面的半径在数值上等于航迹段步长L。并以进入当前节点速度在水平面上投影的方向为对称轴。垂直剖面的夹角大小为θmax的2倍，关于水平方向对称。

2)分割各颗伪卫星当前位置点的待扩展区。如图 2所示，首先在垂直剖面内均匀取M个方向，得到M个2倍于Φmax大小的扇面；然后把每一个扇面均匀分为N个扇区，这样可得到M×N个小扇区，共形成M×(N+1)个扩展节点。判断每个扩展节点位置坐标是否满足飞行高度约束，若不满足，则将该节点位置高度限制为高程约束的边界值。

 图 2 开放节点扩展示意图 Fig. 2 Schematic diagram of expanding open nodes

3)将n个伪卫星对应的待扩展区组合成一个搜索空间，各个伪卫星分别遍历各自对应的待扩展区，经排列组合后共形成[M×(N+1)]n种组网方式。

4)设置伪卫星之间碰撞危险的距离阈值dmin，遍历检测搜索空间，检测各个伪卫星的间距。若在某种组网方式中，存在2个及以上的伪卫星的间距距离小于距离阈值，则将该组网方式从搜索空间中剔除。若剔除以后搜索空间为空集，则OPEN表置空，返回步骤3。

5)将第3)步计算得到的每种组网情况对应的各伪卫星位置坐标集合，插入到OPEN表中。

6)返回步骤3。

1)沿航路前行方向，每隔L/2的距离选取一个航路上的位置点(大地坐标系)，组成位置点序列，设第一个位置点为当前位置点。

2)从当前位置点开始，依次往后连续取3个点，分别设为A(xA, yA, zA)、B(xB, yB, zB)和C(xC, yC, zC)。计算夹角(拐弯角)的余弦值，若为0则转到第7)步；否则执行第3)步。

3)计算水平拐弯角Φ，若Φ为钝角，则Φ的值用π－Φ替代。根据式(16)计算曲率半径r；同时，根据计算出曲率圆的圆心O在大地坐标系下的坐标O(xO, yO, zO)。

4)设DACOB的交点，根据图 1中几何关系，计算得到如下向量长度：

 (17)

pC均为3×1列向量，T为本地坐标系到大地坐标系的转换矩阵(3×3方阵)，于是可得线性方程组：

 (18)

5)设置旋转角度步长Δω，在本地坐标系中将O为圆心向C点旋转，每转过Δω即在圆弧上采样一个位置点，计算该点在本地坐标系下的坐标；再通过计算得到采样点在大地坐标系下的坐标pk

6)连接A、C及采样点，得到Dubins曲线

7)若C为位置点序列中的最后一个位置点，航路规划算法结束；否则，将B设为当前位置点，返回第2)步。

 图 3 Dubins曲线平滑前后的航路对比 Fig. 3 Comparison of route with and without smoothing by Dubins curve
3 仿真结果分析

 参数 数值 飞艇数量 5 飞艇编队初始位置 1号艇：(122.0，24.5，10 000) (经度/(°)，纬度/(°)，高度/m) 2号艇：(122.5，25.0，10 000) 3号艇：(123.0，25.5，10 000) 4号艇：(123.5，25.0，10 000) 5号艇：(124.0，24.5，10 000) 飞艇高程范围/m [2 000，30 000] 航迹段长度(步长)/m 5 000 最小曲率半径/m 4 330 最小挠率半径/m 4 330 最小间距阈值/m 5 000 服务区域经度范围/(°) [112.0，114.0] 服务区域纬度范围/(°) [25.5，27.5] 垂直方向搜索扇面数 3 水平方向搜索扇区数 4

3.1 离线航路规划仿真

1)距离代价权重与GDOP代价权重按式(13)和式(14)进行自适应调节。

2)距离代价权重优先，GDOP代价权重为0。

3) GDOP代价权重优先，距离代价权重为0。

4)距离代价与GDOP代价权重为固定值1/2。

 图 4 不同权重条件下的三维航路规划结果 Fig. 4 3D route planning of airships in different conditions of weight

 图 5 不同权重条件下航路规划中各飞艇与目标部署位置平均距离变化曲线 Fig. 5 Curves of average distance from airships' position to deployed target position in different conditions of weight during route planning

 图 6 不同代价权重条件下航路规划中的GDOP代价变化曲线 Fig. 6 Curves of GDOP cost in different conditions of weight during route planning
3.2 在线航路重规划仿真

 图 7 3号艇在线航路重规划的仿真 Fig. 7 Simulation of online route re-planning of No.3 airship

 图 8 在线航路重规划的GDOP代价对比 Fig. 8 Comparison of GDOP cost of online route re-planning
4 结论

1)采用权重自适应可调的航路规划算法，规划的航路一方面能够有效降低导航增强服务区域的GDOP值，提高用户定位精度；另一方面又能够使飞艇较快到达目标部署位置，不会明显增加飞艇运动的时间和燃料消耗，表明航路规划算法具有良好的经济性。

2)当编队中的个别飞艇在运动过程中偏离预定航路时，可采用基于单艇调整和基于编队调整2种在线航路重规划方法，前者的算法搜索速度更快，规划路径更短，而GDOP代价与后者相比相差并不大，因此更适合在线实时的航路重规划。

#### 文章信息

ZENG Lingchuan, LI Dapeng, QU Yi, REN Aiai, GONG Yingkui

Route planning algorithm for configuring airborne pseudolites

Journal of Beijing University of Aeronautics and Astronsutics, 2016, 42(7): 1388-1397
http://dx.doi.org/10.13700/j.bh.1001-5965.2015.0477