空中机器人(UAV)轨迹规划设计与仿真①

， ，

(安徽工业大学 机械工程学院，安徽 马鞍山 243000)

0 引 言

空中机器人是当今研究的热点，不论在军事还是民用都发挥了巨大的作用。如物流配送[1]，农用机器人[2]，车辆导航系统[3]，汽车泊车系统[4]等领域均得到了应用[5]，而轨迹规划是空中机器人研究的一个重要组成部分，所以空中机器人自主规划路径问题一直是各大高校研究的热点。空中机器人轨迹规划问题可以概括为在顺利躲避障碍物的前提下，机器人可以自主找到一条从初始点到目标点的最短路径[6]。在研究的最初期，轨迹规划问题是采用人工规划的方法，但是此方法不能实现预期的飞行任务，随着对问题的深入研究，国内外学者提出了一系列轨迹规划算法包括蚁群算法、粒子群算法、遗传算法、A*算法、模糊逻辑算法[7-10]等 ，其中粒子群算法于1992年被Marco Dorigo提出，其灵感来自于蚂蚁寻找食物时，蚂蚁的路径轨迹。和其他算法相比较而言，具有以下优点:1.优良的分布式计算机制；2.较强的鲁棒性；3.全局搜索方法；4.易于其他算法结合，利用蚁群算法通过栅格法对空中机器人飞行环境在MATLAB中进行二维建模。通过仿真分析，可以看出蚁群算法在空中机器人轨迹规划得到了很好应用。

1 二维轨迹环境建模

1.1 环境模型预处理

空中机器人的飞行轨迹是在一定空间内进行的，假设空中机器人的飞行高度保持不变，飞行速度不变，并且假设在飞行过程中飞行环境不发生变化，那么空中机器人的飞行轨迹就可以简化成一个二维轨迹规划问题类似于移动机器人的轨迹规划问题。

1.2 栅格法

栅格法[11]是在进行轨迹规划时采用栅格来表示地图，假设空中机器人的飞行环境是长为L,宽为W的二维空间，并且每个栅格的长和宽均为b，那么栅格的总数就位(L/b)×(W/b)。飞行环境A可由栅格Gij表示：

A={Gij/Gij=0或1，i,j为整数}

(1)

其中Gij=0表示无障碍区域，1表示有障碍区域 通过使用栅格法将空中机器人的飞行环境变成了可以用0,1表示的网格单元。栅格的标识方法通常有两种：直角坐标法和序号法。考虑到序号法相比直角坐标法更加节省系统的存储空间[12]，因此本文采用序号法对栅格进行编码，按照从左到右，从上到下依次对栅格进行编码，如图1所示。

12345678910111213141516171819202122232425262728293031323334353637383940…………………………7172737475767778798081828384858687888990919293949596979899100

图1 栅格编码图

1.3 二维飞行环境建模

当空中机器人在离线状态下要进行飞行轨迹规划，首先应获取飞行环境信息，二维飞行环境建模的关键所在是如何将环境信息转变为数字信息。在MATLAB中进行飞行环境仿真，MATLAB主要对矩阵信息进行加载，因此本文的环境建模主要是将环境信息转换为用矩阵表示的数值。

根据栅格法构造矩阵，用矩阵来表示环境信息，如下20×20矩阵G，由此也可知道该环境被分割为400个小栅格，在矩阵G20x20中，0表示自由区域，1表示障碍物区域。

将矩阵G20x20在MATLAB环境中进行建模，得到结果如图2

2 基于蚁群算法的空中机器人(UAV)轨迹规划

2.1 蚁群算法概述

采用蚁群算法对空中机器人的轨迹进行规划，主要基于以下几个原因：1优良的分布式计算机制；2较强的鲁棒性；3全局搜索方法；4易于其他算法结合

蚁群算法是一种模仿蚂蚁群体行为的智能优化算法，蚁群算法较早的应用在TSP问题，很多文献基于TSP问题来详细介绍蚁群算法的基本原理[13],文中以采用此种方法。

图2 二维环境建模

2.2 最优轨迹

在确定最优轨迹之前，首先介绍旅行商问题简称为TSP,可将TSP问题进行如下描述：假设共有n个城市C={c1,c2,…,cn}及不同城市组合的路径长短dij(1in,1jn,i≠j)。TSP 问题可以描述为从起点出发经过所有城市且每座城市只经过一次，最终回到起点的一条最短路径问题。设城市i和j之间的距离是dij，表示如式所示：

dij=[(xi-xj)2+(yi-yj)2]1/2

(2)

基于上述TSP问题，则可以将空中机器人轨迹规划问题描述为：假设空中机器人从原点开始飞行，并且在飞行过程中共经过w个位置点，其中第p个位置的坐标为Wp=(xp，yp),那么在飞行过程中空中机器人的飞行距离可以表示为：

(3)

由于在空中机器人飞过这w个位置点时，经过这些点的顺序是不同的，假设总共有l条不同的轨迹路线，通过(3)式可以计算不同轨迹路线的长度，那么可以形成一个长度集合Lall，minL就是在长度集合Lall中长度最短的那条路径。

Lall=[L1,L2,L3…,Ll]

(4)

minL=min(Lall)

(5)

2.3 蚁群算法的应用

(6)

式中：allowedk代表第k只蚂蚁当其处在栅格i时供其下一步可以移动的栅格；τij代表栅格i和栅格j之间的信息素强度；a的作用是可以控制信息素的相对重要程度；β的作用是控制路径长度的相对重要程度；ηij表示栅格i到栅格j的能见度，反映有栅格i转移到栅格j的启发程度[14]。

图3 基本蚁群的算法框图

根据问题可知每次蚂蚁必须经过所有的城市，而且同一城市不得重复经过，因此为每只蚂蚁都设计了一个数据结构，称为禁忌列表(Tabu List)。禁忌表的作用是可以对蚂蚁的路径进行约束，在禁忌表中记录了在本次循环中蚂蚁已经走过的城市，那么在本次循环中就不允许蚂蚁再通过禁忌表中记录的这些城市。在结束一次循环之后，可以根据在禁忌表中记录城市的顺序从而可以计算出每只蚂蚁所爬过的路径长度。计算完成后，禁忌表中记录的数据被清除，那么该蚂蚁就可以重新选择其他路径。图3为基本蚁群的算法框图

在蚂蚁行走过程中中会存在启发信息无法体现的问题，这是由于残留信息素过多的原因，因此在每只蚂蚁走遍所有城市之后，要求对残留信息素信息素进行更新处理。(t+n)时刻在路径(i,j)上的信息量按式(7)和式(8)所示的规则进行更新

τij(t+n)=(1-ρ)·τij(t)+Δτij(t)

(7)

(8)

(9)

式中：LK表示第k只蚂蚁其爬过的那条路径的总长度，Q表示第k只蚂蚁在其爬过的路径上释放的信息素总量[15]

3 规划结果

设置初始蚂蚁数量m,启发式因子α、期望启发式因子β、信息素强度Q、信息素蒸发系数ρ[16]，迭代循环次数K，初始参数值见图：

图4 二维参数初始值

图5 蚁群算法求解二维环境模型的最短路径

图6 蚁群算法求解二维环境模型的最短路径(改变起始点)

确定起始点S，终止点E，在MATLAB仿真后求得路径。如图5所示，S点代表起始点，E代表终止点，在S和E之间有一条线段，这就是通过基本蚁群算法在已知二维环境的条件下求得的一条最优路径。如图6，改变起始点和终止点的位置通过仿真同样会得到一条最优路径。

通过仿真的轨迹图所示可以了解到，蚁群算法在寻找到达终点的路径过程中，是按照其基本原理来实现的，在图7中可以看到从起始点到终止点的一系列线条，代表蚂蚁寻找目标过程中所走过的每一条路径。然后通过比较每一条路径的长度来确定出最短路径，也就是寻找的最优路径。

图7 蚁群算法的搜索路径

4 结 语

蚁群算法在寻找最优路径过程中随着迭代次数的增加，所收寻到的路径越来越短，图中直线代表了平均路径长度，带有雪花点的线代表的是最优路线长度，最终在迭代了100次左右，两条线收敛在同一数据上，由此可知参数的选取是合适的，所寻得的路径也是可行的，整个路径规划的过程是成功的。但本文仅是对二维飞行环境进行规划，与实际飞行情况略有不符，日后还需进一步进行研究。同时蚁群算法本身也存在着缺点：1蚁群算法在进行飞行轨迹规划时需要进行多次迭代，浪费时间，因此效率较低。2当在求解问题中，经过的点越多(经过的城市越多)，那么就有可能存在求得的结果只是求解过程中一部分的最优解而非整个求解问题的最优解。因此，我们还需进一步的研究以改进蚁群算法。