-
摘要: 由无人机(Unmanned aerial vehicles, UAV)和地面移动机器人组成的异构机器人系统在协作执行任务时, 可以充分发挥两类机器人各自的优势. 无人机运动灵活, 但通常续航能力有限; 地面机器人载荷多, 适合作为无人机的着陆平台和移动补给站, 但运动受路网约束. 本文研究这类异构机器人系统协作路径规划问题. 为了降低完成任务的时间代价, 提出一种由蚁群算法(Ant colony optimization, ACO)和遗传算法(Genetic algorithm, GA)相结合的两步法对地面机器人和无人机的路线进行解耦, 同时规划地面机器人和无人机的路线. 第1步使用蚁群算法为地面机器人搜索可行路线. 第2步对无人机的最优路径建模, 采用遗传算法求解并将无人机路径长度返回至第1步中, 用于更新路网的信息素参数, 从而实现异构协作系统路径的整体优化. 另外, 为了进一步降低无人机的飞行时间代价, 研究了无人机在其续航能力内连续完成多任务的协作路径规划问题. 最后, 通过大量仿真实验验证了所提方法的有效性.Abstract: The heterogeneous robot system, composed of unmanned aerial vehicles (UAVs) and ground mobile robots, can give full play to the respective advantages of the two types of robots when performing tasks in cooperation. UAVs have the characteristics of flexibility, but they usually have limited endurance. Ground robots can bear large loads and are suitable for use as landing platforms and mobile replenishment stations for UAVs, but their movement is constrained by the road network. This paper studies the cooperative path planning of the heterogeneous robot systems. In order to reduce the time cost of the task, this paper proposes a two-step strategy combining ant colony optimization (ACO) and genetic algorithm (GA) to decouple the routes of mobile robot and UAV, and plans the routes of mobile robot and UAV at the same time. In the first step, ant colony optimization is used to search for feasible routes of the mobile robot. In the second step, we derive the model of the UAV＇s optimal path and use the genetic algorithm to solve it. The UAV path length is returned to the first step to update the pheromone in the road network. Then, we realize the overall optimization of the heterogeneous collaborative system path. In order to further reduce the flight time cost of UAVs, this paper also studies the problem of cooperative path planning for UAVs to continuously complete multiple tasks within their endurance capabilities. Finally, a large number of simulation experiments verify the effectiveness of the proposed method.
-
Key words:
- Heterogeneous robot systems /
- path planning /
- road network constraint /
- two-step strategy
-
空中无人机 (Unmanned aerial vehicles, UAV) 和地面机器人在自己的工作领域内都可以发挥很好的作用, 但是都各有优缺点. 如, 微型无人机行动自由、视野开阔, 在搜索和检测目标方面具有不可替代的优势, 但是无人机单次续航时间通常有限. 地面机器人具有智能驾驶、载荷能力强、续航时间长的特点, 缺点是只能在道路网络中行驶, 视野严重受限. 因此, 若将空中无人机与地面移动机器人结合构成异构协作系统, 让地面车作为无人机的着陆平台及能量补给站, 可以取长补短、优势互补, 大大拓展机器人系统代替人类完成任务的能力[1-5]. 由无人机和地面机器人组成的异构系统在任务调度、目标跟踪、定位与抓捕、合作建图、持续监测以及物流配送等方面都有广泛的应用前景[6-10]. 本文对这一类异构机器人系统的路径规划问题展开研究.
目前对异构机器人系统的路径规划研究主要有两类, 一类是同时规划无人机和地面车的路线; 另一类是仅规划无人机的路线. 在第1类中, 不考虑地面车的运动范围, 即假设地面是完全空旷的, 允许地面车在二维平面上做任意运动, 同时规划地面车和无人机的路线. 第2类在第1类的研究基础上, 考虑实际环境中道路的限制, 但是事先为地面车选择一条路径, 然后仅规划无人机的路线, 通常约定无人机只允许在目标点或道路节点处起飞或降落.
对于第1类, 不考虑地面机器人运动范围的研究, 很多是关于带有无人机的旅行商问题(Travelling salesman problem, TSP)或者广义旅行商问题的研究[11-12]. Murray等[13]和Ha等[14]研究异构机器人系统的包裹投递, 允许无人机在客户处起飞或降落, 客户既可以被无人机访问, 也可以由地面车访问, 但是一次仅访问一个客户. 针对文献[13]研究的问题, Ham[15]允许地面车和无人机一次访问多个目标点. Klauco等[5]在允许无人机一次访问多个目标点的基础上, 优化了目标点的访问顺序. Agatz等[11]研究了地面车和无人机合作的TSP问题, 基于局部搜索和动态规划方法提出了一种启发式算法, 并将结果与小规模案例的最优解进行了比较. Freitas等[12]的研究中允许目标点由地面车或无人机访问, 提出了一种混合启发式方法, 得到了无人机和地面车共同访问目标点的路径. Klauco等[16]研究异构机器人系统的包裹投递问题, 并将研究的问题简化为混合整数规划问题. 陈洋等[17]给目标点加入邻域约束, 无人机只需要到达目标点的邻域, 进一步节省了完成任务的时间.
第2类研究结合了道路的实际情况, 地面车的运动受到路面障碍物或者建筑物的约束, 因而假定地面车选择了一条固定的路线, 在此情形下仅需规划无人机的路线. 现有研究只能限定无人机在特定位置起飞或降落. 例如: Ham[15]首先研究了地面车路径固定情形下的无人机路径规划问题. Maini等[18]研究了异构机器人系统在复杂环境中测绘的应用, 由于地面道路错综复杂, 需要为地面车事先选择一条道路, 允许无人机一次访问多个测绘点. Carlsson等[19]研究了异构机器人系统进行物流配送的路径规划问题. 在地面车路径已知的基础上, 提出一种启发式方法求得无人机的路线. Mathew等[20]将地面车的路径限制在一条道路上, 然后为无人机选择一些确定的地点, 在这些确定点处选择无人机的起飞点和降落点, 从而得到无人机的路线.
现实中的车辆必须在道路上行驶. 因此本文的研究给异构机器人系统加入地面路网的约束, 使研究更接近实际情况. 由于人为给定地面车的路径会破坏异构机器人整体的最优性能, 因此本文将两者的路径计算放入同一个优化模型中, 不仅规划无人机的路径, 而且同时规划地面车的路径. 由Carlsson等[19]的研究可知, 当允许无人机在道路上随时起降时可降低时间成本, 因此本文的研究允许无人机在地面车上根据需要随时起飞, 进一步减少飞行时间和所需能量. 并且, 为了进一步缩短无人机的总飞行距离以节省能量, 本文考虑允许无人机在其续航时间范围内连续访问多个目标点.
由于地面车和无人机的路线之间相互耦合, 且由于地面路网的复杂性, 地面车的路线难以使用传统方法建立约束表达式对耦合关系进行描述, 因此本文提出使用蚁群算法(Ant colony optimization, ACO)和遗传算法(Genetic algorithm, GA)相结合的“两步法”对地面移动机器人和无人机的路径进行求解, 两步之间通过信息素建立桥梁, 达到全局优化的目标, 研究思路如图1所示. 本文的贡献主要包括两个方面: 1) 建立了异构机器人在路网约束下的路径规划模型; 2) 提出一种两步法求解异构机器人系统的路径规划方法.
1. 异构机器人系统路径规划模型
1.1 问题描述
考虑有一个道路网络和若干待访问的目标点, 该访问任务由一架无人机和一台地面车组成异构机器人系统协作完成. 地面车充当移动平台为无人机的着陆和补能提供支持. 目标点的访问由无人机完成, 目标点的坐标和地面路网已知. 该过程可描述如下: 地面车携带无人机和相应的补能装置从起点出发, 无人机在地面路网中选择一条合适的路线行驶到终点. 在行驶过程中, 地面车始终在道路上保持速度vc行驶, 无人机需要在合适的时候从地面车上起飞去访问目标点, 且无人机以vh的速度匀速飞行(仅考虑地面的投影速度), 无人机每次起飞访问的目标点个数和顺序由规划结果决定. 在无人机离开地面车访问目标点的过程中, 地面车在路网中继续行驶, 到达合适的汇合点时, 无人机降落在地面车上补能, 由地面车载着无人机一起在路网中运动, 并在此期间完成能量补给, 直到下一个合适的起飞点起飞再去访问下一个目标点. 考虑到现实情况下电池充能时间较长, 所以补能的方式选择为自动更换电池. 如此往复, 直到完成所有目标点的访问之后, 无人机降落在地面车上随之一起运动到终点, 整个任务完成. 如图2所示的地面车具有为无人机自动更换电池的功能.
上述问题在二维平面中的描述如图3所示. 目标点的坐标为
${\boldsymbol{q}_i} \in {{\bf{R}}^{2 \times 1}},i = 1,2, \cdots ,N$ (N为目标点个数), 地面路径段连接处节点为${\boldsymbol{n}_j} \in {{\bf{R}}^{2 \times 1}}, j = 1,2, \cdots ,K$ (K为连接点的个数).${\boldsymbol{S}} \in {{\bf{R}}^{2 \times 1}}$ 为整个任务的起点,${\boldsymbol{E}} \in {{\bf{R}}^{2 \times 1}}$ 为终点. 无人机的续航能力由无人机携带满格电池所能飞行的最大距离表示, 假设U表示无人机的最大续航时间, 则无人机续航能力为${d_{\max }} = U \times {v_{\rm{h}}}$ , 因此, 为了保证无人机能够安全返回, 无人机飞行范围的最大半径为$R ={d_{\max }}/2$ . 假设地面车携带了充足的能量, 能保证完成任务过程中持续运动, 并随时可为无人机提供足够的备用电池.
图 3 路网约束下异构机器人系统示意图Fig. 3 Schematic diagram of heterogeneous robot system with road network constraints本文假设无人机和地面车可以相互识别, 道路网络中没有障碍和拥堵现象, 并且忽略无人机和地面车的加速度. 通过构建该系统的数学模型, 计算地面车的路线和无人机的起降点, 从而得到无人机的路线, 进而得到异构机器人系统的运动路径.
1.2 路径规划建模
本节在分析无人机路径时, 假设已知地面车的路径(随机初始化), 而地面车的路径优化将在第2.1节采用蚁群算法求解.
由于地面路网由若干折线段连接而成, 难以用连续函数表示, 但是容易用一系列按顺序连接的离散点表示. 假设路径离散化后相邻两点之间间距为l, 离散点的坐标按顺序存储在矩阵
$\boldsymbol{L} \in {{\bf{R}}^{M \times 2}}$ 中, 其中M为离散点的个数. 因此无人机只需在矩阵L中选择其访问每个目标点的起飞点和降落点的编号, 编号确定后即确定了无人机的飞行路线.1.2.1 目标点访问顺序建模
假设目标点序列为
$\boldsymbol{O} = \left[ {{\boldsymbol{q}_1},{\boldsymbol{q}_2}, \cdots ,{\boldsymbol{q}_N}} \right]$ , 鉴于对这些目标点的访问顺序都是需要优化的, 设优化后的目标点序列为$\boldsymbol{\tilde O} = \left[ {{{\boldsymbol{\tilde q}}_1},{{\boldsymbol{\tilde q}}_2}, \cdots ,{{\boldsymbol{\tilde q}}_N}} \right]$ . 定义二值排列矩阵[12]$\boldsymbol{P} \in {{\bf{R}}^{N \times N}}$ ,${P_{i,j}} \in \left\{ {0,1} \right\}$ , 则有$$\boldsymbol{\tilde O} = \boldsymbol{OP} = \left[ {{{\boldsymbol{\tilde q}}_1},{{\boldsymbol{\tilde q}}_2}, \cdots ,{{\boldsymbol{\tilde q}}_N}} \right]$$ (1) $$\sum\limits_{i = 1}^N {{P_{i,j}}} = 1,\;\;j = 1,2,\cdots,N$$ (2) $$\sum\limits_{j = 1}^N {{P_{i,j}}} = 1,\;\;i = 1,2,\cdots,N$$ (3) 其中, Pi, j = 1表示原第i个目标点
${{\boldsymbol{q}}_i}$ 调整为第j个访问. 约束(2)表示优化顺序后, 无人机每次选择一个目标点进行访问. 约束(3)表示每个目标点仅被访问一次.1.2.2 无人机路径建模
引入起飞逻辑矩阵
$\boldsymbol{\alpha } \in {{\bf{R}}^{M \times N}}$ 和着陆逻辑矩阵$\boldsymbol{\beta } \in {{\bf{R}}^{M \times N}}$ , 其中${\alpha _{i,j}} \in \left\{ {0,1} \right\}$ ,${\beta _{i,j}} \in \left\{ {0,1} \right\}$ .${\alpha _{i,j}} = 1$ 表示无人机在L的第i个点处起飞去访问目标点${\tilde {\boldsymbol{q}}_j}$ . 类似地,${\beta _{i,j}} = 1$ 表示无人机访问完目标点${\tilde {\boldsymbol{q}}_j}$ 后在L中的第i个点处降落在地面车上.引入
$\boldsymbol{\alpha } $ 和$\boldsymbol{\beta } $ 后, 得到约束式(4) ~ (10).$$\sum\limits_{i = 1}^M {{\alpha _{i,j}}} = 1,\;\;j = 1,2,\cdots,N$$ (4) $$\sum\limits_{i = 1}^M {{\beta _{i,j}}} = 1,\;\;j = 1,2,\cdots,N$$ (5) $$\sum\limits_{j = 1}^N {\left( {{\alpha _{i,j}} + {\beta _{i,j}}} \right)} \leq 1,\;\;i = 1,2,\cdots,M$$ (6) $$ \begin{aligned}[b] \sum\limits_{i = 1}^n {\left( {{\beta _{i,j}} - {\alpha _{i,j}}} \right)} \leq 0,\;& n = 1,2,\cdots,M,\;\\ & \quad\; j = 1,2,\cdots,N \end{aligned} $$ (7) $$\begin{aligned}[b] \sum\limits_{i = 1}^n {\left( {{\alpha _{i,j + 1}} - {\beta _{i,j}}} \right)} \leq 0,\;&n = 1,2,\cdots,M,\;\\ &j = 1,2,\cdots,N - 1\end{aligned}$$ (8) $$\begin{aligned}[b] &\frac{1}{{{v_{\rm{h}}}}}\left( \left\| {\sum\limits_{i = 1}^M {{\alpha _{i,j}}\boldsymbol{L}_i^{\rm{T}}} - \sum\limits_{k = 1}^N {{\boldsymbol{q}_j}{P_{k,j}}} } \right\| + \left\| \sum\limits_{i = 1}^M {{\beta _{i,j}}\boldsymbol{L}_i^{\rm{T}}} \; - \right.\right.\\ & \qquad \left.\left.\sum\limits_{k = 1}^N {{\boldsymbol{q}_j}{P_{k,j}}} \right\| \right) \le U,\;\;j = 1,2,\cdots,N\\[-15pt] \end{aligned}$$ (9) $$\begin{aligned}[b] &\frac{1}{{{v_{\rm{h}}}}}\left( \left\| {\sum\limits_{i = 1}^M {{\alpha _{i,j}}\boldsymbol{L}_i^{\rm{T}}} - \sum\limits_{k = 1}^N {{\boldsymbol{q}_j}{P_{k,j}}} } \right\| + \left\| \sum\limits_{i = 1}^M {{\beta _{i,j}}\boldsymbol{L}_i^{\rm{T}}} \; -\right.\right.\\ &\qquad \left.\left.\sum\limits_{k = 1}^N {{\boldsymbol{q}_j}{P_{k,j}}} \right\| \right) = \frac{l}{{{v_{\rm{c}}}}}\sum\limits_{i = 1}^M {i\left( {{\beta _{i,j}} - {\alpha _{i,j}}} \right)} ,\\ &\qquad\qquad\qquad\qquad\qquad\quad j = 1,2,\cdots,N\\[-10pt] \end{aligned}$$ (10) 约束(4)表示无人机访问每个目标点时只能有一个起飞点. 类似地, 约束(5)表示无人机访问完每个目标点之后只能有一个降落点. 约束(6)表示L中的每个点最多只允许无人机起飞或降落一次. 约束(7)表示无人机访问每个目标点时的起飞点必须在降落点之前. 约束(8)表示无人机起飞访问下一个目标点必须在访问完上一个目标点降落之后.
在约束(9)中,
${\boldsymbol{L}_i} \in {{\bf{R}}^{1 \times 2}}$ 表示矩阵L的第i行向量,$\sum\nolimits_{i = 1}^M{{\alpha _{i,j}}\boldsymbol{L}_i^{\rm{T}}}$ 表示无人机访问目标j时的起飞坐标,$\sum\nolimits_{i = 1}^M {{\beta _{i,j}}\boldsymbol{L}_i^{\rm{T}}}$ 表示无人机访问目标j之后的降落坐标. 约束(9)表示无人机每次访问目标点的飞行时间应该在续航时间范围内, 即无人机在能量耗尽之前就要回到地面车上进行补能. 约束(10)表示无人机访问每个目标点从起飞到降落的耗时与地面车从无人机的起飞点运动到无人机的降落点的耗时必须相同, 以避免地面车和无人机之间互相等待.以无人机的飞行距离为代价, 构造如式(11)所示的目标函数.
$$\begin{split} \min f =\;& \sum\limits_{j = 1}^N \left(\left\| {\sum\limits_{i = 1}^M {{\alpha _{i,j}}\boldsymbol{L}_i^{\rm{T}}} - \sum\limits_{k = 1}^N {{\boldsymbol{q}_j}{P_{k,j}}} } \right\| +\right.\\ &\left.\left\| {\sum\limits_{i = 1}^M {{\boldsymbol{\beta }_{i,j}}\boldsymbol{L}_i^{\rm{T}}} - \sum\limits_{k = 1}^N {{\boldsymbol{q}_j}{P_{k,j}}} } \right\| \right) \end{split}$$ (11) 根据以上模型, 该路径规划问题可以转化为如下所示的优化问题P1:
$$\begin{split} &{\rm{P1}}{\rm{ }}\mathop {\min }\limits_{\boldsymbol{P},\boldsymbol{\alpha },\boldsymbol{\beta }} f\\ &\quad{\rm{s}}{\rm{.t}}.\;{\rm{ }}(2) \sim (10)\\ &\quad{P_{i,j}} \in \left\{ {0,1} \right\},0 \le i \le N,0 \le j \le N\\ &\quad{\alpha _{i,j}}{\rm{, }}{\beta _{i,j}} \in \left\{ {0,1} \right\},0 \le i \le M,0 \le j \le N \end{split}$$ 2. 异构机器人系统路径规划算法设计
采用两步法对该路径规划问题求解. 第1步, 使用改进的蚁群算法(Modified ACO, MACO)在路网中为地面车选择一条能够到达终点并能使无人机访问到所有目标点的最短路线Rs. 无人机能够成功访问到某个目标点的条件可参考图3中圆圈标示. 考虑无人机的续航能力, 只有地面车的路线经过以目标点为圆心, 以R为半径的圆时, 无人机才能访问到相应的目标点. 第2步, 将第1步得到的地面车路径Rs离散化, 对优化问题P1采用遗传算法, 求得对应于Rs的无人机的最优路径, 然后将无人机的飞行总距离返回到第1步中, 修改蚁群算法信息素的更新. 这种两步法称为MACO-GA, 流程如图4所示, 其中左侧虚线框为第1步, 右侧虚线框为第2步. iter1为蚁群算法最大迭代次数, iter2为遗传算法种群最大遗传代数.
2.1 改进的蚁群算法
如果蚂蚁选择的下一个运动节点能够使无人机在一定程度上访问更多的目标点, 即地面车运动经过的路线段穿越更多的图3所示的圆形区域, 则蚂蚁的这种决策有可能使所有的目标点在更短的时间内访问完成, 即在一定程度上缩短地面车路径的总长度. 因此, 对蚁群算法的启发函数改进为
$${\eta _{ij}}\left( t \right){\rm{ = }}\frac{{{y_{ij}}}}{{{d_{ij}}}}$$ (12) 式中,
${d_{ij}}$ 是路径$(i,j )$ 的长度,${y_{ij}}$ 是该路径段穿越的圆圈的个数, 即地面车选择该路径段能够使无人机访问到的目标点的个数.为了诱导蚂蚁选择能够使无人机的飞行距离更短的地面车路线, 将第2步得到的无人机路径长度用于第1步中蚁群算法信息素的更新, 改进后的信息素更新方法为
$${\tau _{ij}}\left( {t + 1} \right) = \left( {1 - \rho } \right){\tau _{ij}}\left( t \right) + \Delta {\tau _{ij}}\left( t \right){\rm{ + }}\Delta \tau _{ij}^{bs}\left( t \right)$$ (13) 式(13)前两项的含义与传统蚁群算法相同, 其中
$\rho \in (0,1)$ 为信息素的挥发系数:$\Delta {\tau _{ij}}(t)$ 为本次循环中路径$(i,j )$ 上信息素增加的总量,$\Delta {\tau _{ij}}(t) = \sum\nolimits_{k = 1}^m {\Delta \tau _{ij}^k(t)}$ , 其中$\Delta \tau _{ij}^k(t)$ 为蚂蚁$k $ 在时刻$t $ 播散在路径$(i,j ) $ 上的信息素. 当蚂蚁从节点$i $ 运动到节点$j $ 时,$\Delta \tau _{ij}^k\left( t \right) = {{Q{d_{ij}}}}/{{{L_k}}}$ , 其中,$Q $ 为已知的信息素总量,${L_k}$ 为蚂蚁$k $ 的路径总长度.式(13)的第3项
$\Delta \tau _{ij}^{bs}\left( t \right)$ 是根据第2步得到的最优无人机飞行路径而增加的信息素量. 假设当前迭代中地面车路线为$R_s $ , 在第2步计算中得到了与之对应的无人机全局最优路径$V_s $ , 则蚂蚁需要在路线$R_s $ 中释放额外的信息素. 释放量$\Delta \tau _{ij}^{bs}\left( t \right)$ 定义为$$\Delta \tau _{ij}^{bs}\left( t \right){\rm{ = }}\left\{ \begin{aligned} &\frac{{GQ}}{{{D^{bs}}}},\;\;{\rm{ }}{{搜索到与}}\;{{{R_s}}}\;{{对应的最优路径}}\;{{V}_{s}}\\ &0,\qquad{\rm{ }}{{其他}} \end{aligned} \right.$$ (14) 式中, 常量
$G $ 表示蚂蚁释放额外信息素的增益,${D^{bs}}$ 表示无人机最优路径$V_s $ 的长度.2.2 遗传算法设计
在第2.1节中, 由MACO得到了能使无人机访问到所有目标点的最短地面车路径
$R_s $ . 本节将采用遗传算法并基于第1.2节中的模型对无人机的路线进行优化. 只要求得变量${\boldsymbol{P}} $ ,$\boldsymbol{\alpha } $ 和$\boldsymbol{\beta } $ , 则无人机的路线也随之确定. 在设计遗传编码之前, 先将这3个变量分为两组,${\boldsymbol{P}} $ 为一组,$\boldsymbol{\alpha } $ 和$\boldsymbol{\beta } $ 为另一组, 将两组分别执行编码、选择、交叉和变异等操作.2.2.1 编码方法
1) P的编码(code1)
code1采用如下方式进行编码: 所有的初始染色体长度均为N, 每个基因取值为1 ~ N之间的整数, 并且每条染色体中的基因不重复. 显然, 该编码方式满足约束式(2)和(3).
2)
$\boldsymbol{\alpha } $ 和$\boldsymbol{\beta } $ 的编码(code2)为了表示L中起飞点和降落点序号的关系, code2中的基因由
$\boldsymbol{\alpha } $ 和$\boldsymbol{\beta } $ 中的元素交替排列. 以$M= 700 $ 、$N=4 $ 、目标点访问顺序为q2→q3→q1→q4为例, 给出code2的一个编码示例如表1所示.表 1 code2的一个编码示例Table 1 A sample of code2编码对象 编码内容 code1 基因值 2 3 1 4 code2 基因值 15 62 78 104 350 461 666 692 $\boldsymbol{\alpha } $, $\boldsymbol{\beta } $为1
的元素${\alpha } _{15, 2}$ ${\beta } _{62, 2}$ ${\alpha } _{78, 3}$ ${\beta }_{104, 3}$ ${\alpha } _{350, 1}$ ${\beta }_{461, 1}$ ${\alpha }_{666, 4}$ ${\beta }_{692, 4}$ code2中的所有染色体满足如下条件:
a)每个基因的取值范围为1 ~
$M $ ;b)每条染色体中的基因不重复;
c)每条染色体中的基因按升序排列.
按以上方式编码的
$\boldsymbol{\alpha } $ 和$\boldsymbol{\beta } $ 的染色体可直接满足约束式(4) ~ (8), 仅有约束式(9)和(10)存在被违反的可能.2.2.2 遗传操作的设计
1) 选择操作. 由于code1和code2的编码是一一对应的, 因此, 将code1和code2同时进行选择, 选择方法为转轮赌法. 假设种群规模为
$W $ ,$f(i) $ 为个体$i $ 的适应度值, 则第$i $ 个个体被选择的概率为$$p(i) = \frac{{f(i)}}{{\sum\limits_{j = 1}^W {f(j)} }},\;\;\forall i = 1,2, \cdots ,W$$ (15) 式中,
$f(i) $ 由适应度函数计算得到, 将在第2.2.3节中介绍.2)交叉操作. code1采用两点交叉, 交叉后染色体仍应满足: 每个基因取值范围为1 ~
$N $ , 并且每条染色体中的基因不重复; code2采用单点交叉, 交叉后的染色体仍应满足第2.2.1节中的条件a) ~ c).3) 变异操作. code1变异时采用倒置的方法, 即选中一段基因, 将该段基因倒置; code2变异时随机选择2个相邻的起飞、降落点用随机产生的数字替换, 变异后仍要满足第2.2.1节中的条件a) ~ c).
2.2.3 适应度函数的设计
根据前面介绍的编码方法和遗传操作方法可知, 约束式(2) ~ (8)均直接满足, 只有约束式(9)和式(10)可能被违反. 本文以式(9)和式(10)的违反量构造函数作为惩罚项加入目标函数中. 约束式(9)和式(10)的违反量分别如式(17)和式(18)所示. 个体的代价由目标函数与违反量之和组成, 即
$${f_{\rm{p}}} = f + {\lambda _1}{p_1}{\rm{ + }}{\lambda _2}{p_2}$$ (16) $$\begin{split} {p_1} =\;& \sum\limits_{j = 1}^N \left( \max \left( \frac{1}{{{v_{\rm{h}}}}}\left( \left\| {\sum\limits_{i = 1}^M {{\alpha _{i,j}}\boldsymbol{L}_i^{\rm{T}}} - \sum\limits_{k = 1}^N {{\boldsymbol{q}_j}{P_{k,j}}} } \right\| + \right.\right.\right.\\ &\left.\left.\left.\left\| {\sum\limits_{i = 1}^M {{\beta _{i,j}}\boldsymbol{L}_i^{\rm{T}}} - \sum\limits_{k = 1}^N {{\boldsymbol{q}_j}{P_{k,j}}} } \right\| \right) - U,0 \right) \right) \\[-20pt] \end{split}$$ (17) $$\begin{split} {p_2} =\;& \sum\limits_{j = 1}^N \left| \frac{l}{{{v_{\rm{c}}}}}\sum\limits_{i = 1}^M {i\left( {{\beta _{i,j}} - {\alpha _{i,j}}} \right)} - \frac{1}{{{v_{\rm{h}}}}}\left( \left\| \sum\limits_{i = 1}^M {{\alpha _{i,j}}\boldsymbol{L}_i^{\rm{T}}} -\right.\right.\right. \\ &\left.\left.\left.\sum\limits_{k = 1}^N {{\boldsymbol{q}_j}{P_{k,j}}} \right\| + \left\| {\sum\limits_{i = 1}^M {{\beta _{i,j}}\boldsymbol{L}_i^{\rm{T}}} - \sum\limits_{k = 1}^N {{\boldsymbol{q}_j}{P_{k,j}}} } \right\| \right) \right| \end{split}$$ (18) 其中,
${\lambda _1}$ ,${\lambda _2}$ 分别为违反量$p_1,p_2 $ 的权重, 即惩罚因子, 可以根据经验取值. 当${\lambda _1}$ ,${\lambda _2}$ 取较大值时, 违反量能够被快速消除, 但是优化问题P1可能会过快地收敛到局部最优值; 相反, 如果${\lambda _1}$ ,${\lambda _2}$ 取较小值, 违反量的消除速度慢, 同时函数值$f_{\rm{p}} $ 也收敛较慢, 更有可能找到全局最优解. 由于$f_{\rm{p}} $ 的值越小表示越接近最优解, 而适应度值越大越接近最优解, 即适应度值与$f_{\rm{p }} $ 的大小总体呈反比关系. 因此, 本文将适应度值设为fitness = 1/$f_{\rm{p}} $ .3. 仿真实验
为了验证上述模型和算法, 本节在3种不同的场景中对该系统进行路径规划, 并分析结果, 其中改进蚁群算法和遗传算法的参数为多次实验得出的最佳参数, 目标点坐标随机生成, 但保证目标点与路网的距离小于无人机最大访问半径.
3.1 简单路网下的仿真
一个简单路网及其拓扑结构如图5所示, 其中S为起点, E为终点, 实线为地面路网, 图5(b)中星号为目标点.
蚁群算法参数为: 迭代次数为30, 种群大小为300, a = 1, b = 1,
$\rho = 0.3$ , Q = 1, G = 500. 遗传算法参数为: 迭代次数800, 种群大小600, 选择概率0.3, 交叉概率0.3, 变异概率0.3,${\lambda _1}{\rm{ \;= \;}}{\lambda _2}{\rm{ \;=\; }} 500$ . 目标点坐标为: (0, 20), (10, 20), (10, 10), (20, 4), (33, 20), (33, 2), (45, 3), (51, 20), (60, 9).地面车和无人机的路径规划结果如图6所示. 在图6(a)中, 粗实线为规划的地面车路线, 与各目标点相连的细实线为无人机路径, “q” 的下标和左边的数字分别为目标点的原始顺序和优化后的访问顺序编号, ti和li分别为无人机访问
${\tilde {\boldsymbol{q}}_i}$ 时的起飞点和降落点. 由图6(a)可知, 无人机的飞行距离为57.6729 km, 地面车的运动路径为:${\boldsymbol{S}}\to {\boldsymbol{n}}_7 \to {\boldsymbol{n}}_6 \to {\boldsymbol{n}}_5 \to {\boldsymbol{n}}_2 \to {\boldsymbol{n}}_1\to {\boldsymbol{E }}$ , 无人机访问目标点的顺序为:${\boldsymbol{q}}_5 \to {\boldsymbol{q}}_4 \to {\boldsymbol{q}}_3 \to {\boldsymbol{q}}_2 \to {\boldsymbol{q}}_1$ , 即矩阵P的解为: P1, 5 = 1, P2, 4 = 1, P3, 3 = 1, P4, 2 = 1, P5, 1 = 1, 其余元素为0.地面路径离散点的个数为
$M=397 $ , 无人机起降点的编号依次为: 43, 72, 74, 114, 184, 224, 284, 318, 369, 382, 即对应$\boldsymbol{\alpha} $ ,$\boldsymbol{\beta}$ 的解为:${\alpha } _{43, 5} = 1 $ ,${\beta } _{72, 5 } = 1$ ,${\alpha } _{74, 4 } = 1$ ,${\beta } _{114, 4} = 1$ ,${\alpha } _{184, 3} = 1$ ,${\beta } _{224, 3} = 1$ ,${\alpha } _{284, 2} = 1$ ,${\beta } _{318, 2} = 1$ ,${\alpha } _{369, 1} = 1$ ,${\beta } _{382, 1} = 1$ ,${{\boldsymbol{\alpha}}} $ ,${{\boldsymbol{\beta}}} $ 矩阵其余元素均为0. 矩阵${\boldsymbol{P}} $ 、$\boldsymbol{\alpha}$ 、$\boldsymbol{\beta} $ 的解满足约束式(2) ~ (9).地面车路径长度的收敛曲线如图6(b)所示, 在蚁群算法的第10次迭代中得到了最短的无人机路线, 在图6(b)中, 该点用实心点标出. 由于目标函数是使无人机的飞行距离最短, 因此, 有必要对蚁群算法第10代的无人机的飞行状况进行分析. 无人机在蚁群算法第10代的距离收敛曲线如图6(c)所示. 图中实线为无人机的飞行距离, 即按式(11)求得的目标函数值, 由图可知, 目标函数在大约400代时收敛到稳定值. 点划线是按式(18)计算出的带惩罚项的目标函数曲线
$f_{\rm{p}} $ .无人机的起飞降落点坐标以及约束(9)和(10)的违反量如表2所示. 在表2中,
$t_a $ 为无人机访问每个目标点的耗时, 违反量的值为0时表示无人机的飞行时间未超出续航时间, 即约束(9)未被违反, 值为正数时表示约束被违反, 显然在本实验结果中约束(9)未被违反.$t_g $ 为无人机访问每个目标点时地面车单独行驶的时间,$|t_a-t_g| $ 为访问每个目标点时无人机与地面车消耗的时间差, 根据第1.2.2节的建模, 该值应尽可能小. 在本实验结果中, 最大值发生在访问目标点${\boldsymbol{q}}_1 $ 和${\boldsymbol{q}}_3 $ 时, 为 0.0013 h, 相当于4.68 s, 即无人机需等待地面车的时长为4.68 s. 该时长很小, 在实际应用中可以接受, 而且如果提高路网的离散精度, 可以进一步减少甚至消除该时间差.表 2 简单路网仿真中无人机的约束违反量 (h)Table 2 UAV constraints violations in the simulation of the simple road network (h)目标点 无人机
用时$t_a $约束(9)违反量
$\max(t_a-U,0) $地面车
耗时$t_g $时间差
$|t_a-t_g| $${\tilde {\boldsymbol{q}}_1}({{\boldsymbol{q}}_5})$ 0.1271 0 0.128 0.0009 ${\tilde {\boldsymbol{q}}_2}({{\boldsymbol{q}}_4})$ 0.1599 0 0.160 0.0001 ${\tilde {\boldsymbol{q} }_3}({ {\boldsymbol{q} }_3})$ 0.1613 0 0.160 0.0013 ${\tilde {\boldsymbol{q}}_4}({{\boldsymbol{q}}_2})$ 0.1392 0 0.140 0.0008 ${\tilde {\boldsymbol{q}}_5}({{\boldsymbol{q}}_1})$ 0.0533 0 0.052 0.0013 3.2 复杂路网下的仿真
复杂路网及其拓扑结构如图7所示, 图7(b)中实线为地面路网, 星号为目标点.
蚁群算法迭代次数为50, 种群大小为300,
$a=1 $ ,$b=1 $ ,$\rho = 0.3$ ,$Q=1 $ ,$G=500 $ . 遗传算法参数为: 迭代次数1000, 种群大小1000, 选择概率0.3, 交叉概率0.4, 变异概率0.4,${\lambda _1}{\rm{ \;=\; }}{\lambda _2}{\rm{ \;= \;}}500$ . 目标点坐标为: (14, 12), (16, 25), (25, 24), (37, 19), (35, 29), (17, 33), (8, 36), (50, 46), (30, 45), (17, 45).地面车和无人机的路径规划结果如图8所示. 由图8(a)可知, 无人机的飞行距离为100.0022 km, 矩阵
${\boldsymbol{P}} $ 的解为$$\begin{split} &P_{1,4}=1 ,\;P_{2,2}=1 ,\;P_{3,3}=1 ,P_{4,1}= 1 ,\;P_{5,2}=1 \\ &P_{6,6}=1 ,\; P_{7,7}=1 ,\;P_{8,10}=1 ,P_{9,9}=1 ,\;P_{10,8}=1 \end{split}$$ 其余元素为0.
$\boldsymbol{\alpha } ,$ $\boldsymbol{\beta } $ 的解为$$\begin{split} &{\alpha } _{89,4}=1,\;{\beta }_{109,4}=1 ,\;{\alpha } _{134,5}=1,{\beta }_{151,5}=1 \\ &{\alpha }_{192,3}=1,\; {\beta }_{206,3}=1 ,\;{\alpha }_{207,1}=1 ,\;{\beta }_{269,1}=1 \\ &{\alpha }_{283,2}=1 ,\; {\beta } _{300,2}=1, \; {\alpha } _{314,6}=1,\; {\beta }_{342,6}=1 \\ &{\alpha } _{343,7}=1,\;{\beta } _{378,7}=1 ,\; {\alpha } _{378,10}=1 ,\;{\beta } _{407,10}=1 \\ &{\alpha } _ {455,9}=1 ,\;{\beta } _{475,9}=1 ,\;{\alpha } _{533,8}=1 ,\;{\beta } _{579,8}=1 \end{split}$$ $\boldsymbol{\alpha } ,$ $\boldsymbol{\beta } $ 矩阵其余元素均为0. 矩阵${\boldsymbol{P}} ,$ $\boldsymbol{\alpha } ,$ $\boldsymbol{\beta } $ 的解满足约束(2) ~ (8).地面车路径长度的收敛曲线如图8(b)所示, 在蚁群算法的第42次迭代中得到了最短的无人机路线, 无人机在蚁群算法第42代的距离收敛曲线如图8(c)所示. 由图可知, 目标函数在大约400代时收敛到稳定值, 为100.0022 km.
无人机的起飞降落点坐标以及约束(9)和(10)的违反量如表3所示. 约束(9)未被违反, 约束(10)的最大违反量为0.0091 h, 表示地面车需等待无人机32.76 s. 该时长很小, 在应用中可以接受.
表 3 复杂路网仿真中无人机的约束违反量 (h)Table 3 UAV constraint violations in the simulation of the complex road network (h)目标点 无人机
用时$ t_a $约束(9)违反量
$\max(t_a-U,0) $地面车
耗时$t_g $时间差
$ |t_a-t_g| $${\tilde {\boldsymbol{q}}_1}({{\boldsymbol{q}}_4})$ 0.0859 0 0.086 0.0001 ${\tilde {\boldsymbol{q}}_2}({{\boldsymbol{q}}_5})$ 0.0761 0 0.076 0.0001 ${\tilde {\boldsymbol{q}}_3}({{\boldsymbol{q}}_3})$ 0.0482 0 0.048 0.0002 ${\tilde {\boldsymbol{q}}_4}({{\boldsymbol{q}}_1})$ 0.2331 0 0.224 0.0091 ${\tilde {\boldsymbol{q}}_5}({{\boldsymbol{q}}_2})$ 0.0668 0 0.066 0.0008 ${\tilde {\boldsymbol{q}}_6}({{\boldsymbol{q}}_6})$ 0.1078 0 0.108 0.0002 ${\tilde {\boldsymbol{q}}_7}({{\boldsymbol{q}}_7})$ 0.1643 0 0.164 0.0003 ${\tilde {\boldsymbol{q}}_8}({{\boldsymbol{q}}_{10}})$ 0.1042 0 0.104 0.0002 ${\tilde {\boldsymbol{q}}_9}({{\boldsymbol{q}}_9})$ 0.0863 0 0.086 0.0003 ${\tilde {\boldsymbol{q}}_{10}}({{\boldsymbol{q}}_8})$ 0.1084 0 0.108 0.0004 3.3 复杂路网中发生交通中断情形
为了验证算法的可靠性, 本节假设路网中某路段因施工、故障等原因导致地面车交通中断, 因此需要重新规划路径. 不失一般性, 假设断开的路段为图7(b)中节点
${\boldsymbol{n}}_{15} $ 和${\boldsymbol{n}}_{19} $ 之间的路段. 仿真参数中仅遗传算法种群大小改为1200, 其余参数均与第3.2节相同.地面车和无人机的路径规划结果如图9所示. 由图9(a)可知, 无人机的飞行距离为126.3833 km, 矩阵
${\boldsymbol{P}} $ 的解为$$\begin{split} &P_{1,4}=1 ,\;P_{2,2}=1 ,\;P_{3,3}=1 ,P_{2,2}= 1 ,\;P_{5,1}=1 \\ &P_{6,6}=1 ,\; P_{7,7}=1 ,\;P_{8,10}=1 ,P_{9,9}=1 ,\;P_{10,8}=1 \end{split}$$ 其余元素为0.
${{\boldsymbol{\alpha}} } ,$ ${{\boldsymbol{\beta}} } $ 的解为$$\begin{split} &{\alpha } _{196, 4}=1,\;{\beta }_{216, 4}=1 ,\;{\alpha } _{217, 3}=1,{\beta }_{267, 3}=1 \\ &{\alpha }_{268, 1}=1,\; {\beta }_{323, 1}=1 ,\;{\alpha }_{328, 2}=1 ,\;{\beta }_{345, 2}=1 \\ &{\alpha }_{366, 6}=1 ,\; {\beta } _{393, 6}=1, \; {\alpha } _{396, 7}=1,\; {\beta }_{434, 7}=1 \\ &{\alpha } _{436, 1}=1,\;{\beta } _{456, 1}=1 ,\; {\alpha } _{503, 9} =1 ,\;{\beta } _{523, 9}=1 \\ &{\alpha } _ {613, 8}=1 ,\;{\beta } _{641, 8}=1 \end{split}$$ $\boldsymbol{\alpha } ,$ $\boldsymbol{\beta } $ 矩阵其余元素均为0. 矩阵${\boldsymbol{P}} ,$ $\boldsymbol{\alpha } ,$ $\boldsymbol{\beta } $ 的解满足约束(2) ~ (8).
图 9 复杂路网交通中断时的仿真结果Fig. 9 Simulation results on the complex road network in case interruption地面车路径长度的收敛曲线如图9(b)所示, 在蚁群算法的第41次迭代中得到了最短的无人机路线, 无人机在蚁群算法第41代的距离收敛曲线如图9(c)所示.
无人机的起飞降落点坐标以及约束(9)和(10)的违反量如表4所示. 显然约束(9)未被违反, 约束(10)的最大违反量为0.001 h, 相当于3.6 s, 即地面车需等待地面车3.6 s. 该时长很小, 在实际中可以接受.
表 4 交通中断仿真中无人机的约束违反量 (h)Table 4 UAV constraint violations in the simulation with traffic interruption (h)目标点 无人机
用时$t_a $约束(9)违反量
$\max(t_a-U,0)$地面车
耗时$t_g $时间差
$|t_a-t_g| $${\tilde {\boldsymbol{q}}_1}({\boldsymbol{q}}_5)$ 0.1338 0 0.134 0.0002 ${\tilde {\boldsymbol{q}}_2}({\boldsymbol{q}}_4)$ 0.2137 0 0.214 0.0003 ${\tilde {\boldsymbol{q}}_3}({\boldsymbol{q}}_3)$ 0.1899 0 0.190 0.0001 ${\tilde {\boldsymbol{q}}_4}({\boldsymbol{q}}_1)$ 0.2244 0 0.224 0.0004 ${\tilde {\boldsymbol{q}}_5}({\boldsymbol{q}}_2)$ 0.0766 0 0.076 0.0006 ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_6)$ 0.1070 0 0.106 0.0010 ${\tilde {\boldsymbol{q}}_7}({\boldsymbol{q}}_7)$ 0.1625 0 0.162 0.0005 ${\tilde {\boldsymbol{q}}_8}({\boldsymbol{q}}_{10})$ 0.0910 0 0.092 0.0010 ${\tilde {\boldsymbol{q}}_9}({\boldsymbol{q}}_{9})$ 0.0981 0 0.098 0.0001 ${\tilde {\boldsymbol{q}}_{10}}({\boldsymbol{q}}_{8})$ 0.1074 0 0.108 0.0006 3.4 本文方法MACO-GA与MACO-PSO的对比
为验证本文所提MACO-GA方法的优越性, 将其与改进蚁群算法−粒子群算法(MACO-Particle swarm optimization, MACO-PSO)进行对比. 对比实验包括简单路网和复杂路网的路径规划, 对比结果如图10、图11、表5和表6所示.
表 5 简单路网中的比较结果Table 5 Comparison results in simple road network算法名称 最优代价值 平均运行时间 (s) MACO-GA 56.8479 0.1832 MACO-PSO 87.6916 0.3628 表 6 复杂路网中的比较结果Table 6 Comparison results in complex road network算法名称 最优代价值 平均运行时间 (s) MACO-GA 116.8250 0.2453 MACO-PSO 331.2657 0.4873 由图10和表5可以看出, 在简单路网中, MACO-GA算法在迭代的前期收敛速度比MACO-PSO略慢, 但是稳定后可以获得更小的代价值, 并且算法每步平均运行时间远小于MACO-PSO. 在复杂路网中, 算法运行具有类似的效果. 此外, 优化求解每步平均运行时间更少, 这表明本文提出的MACO-GA算法的时间复杂度比MACO-PSO更小. 以上对比分析表明了本文所提算法的有效性.
4. 拓展 —— 一次访问多个目标点的路径规划
由于无人机的续航能力有限, 在前面的研究中, 仅允许无人机一次访问一个目标点便返回地面车上补充能量. 当多个目标点的距离较近时, 无人机可能有能力连续访问多个目标点后再返回地面车, 因此在前面的基础上, 考虑在无人机的续航能力允许的范围内, 一次性连续访问多个目标点, 进一步缩短无人机的飞行距离, 提高无人机执行任务的效率. 本节仍然采用第3.3节中改进蚁群算法和遗传算法相结合的两步法, 且蚁群算法部分和遗传算法部分中P的编码及遗传操作均不做改动, 仅将遗传算法中
$\boldsymbol{\alpha } $ 和$\boldsymbol{\beta } $ 的编码、交叉和变异操作以及遗传算法的适应度函数稍作改变.4.1 编码方法
本节在染色体中引入0元素, 元素为0的基因位表示无人机在该目标点处不做起飞或降落的操作, 不为0的元素含义与第2.2节相同. 每条染色体在编码时随机产生0元素和非0元素. 除了需满足第2.2.1节中的约束条件a) ~ c)之外, 采用此编码方式的染色体需额外满足的约束条件为: 1) 0元素和非0元素的个数均为偶数, 且0元素和非0元素均应成对出现; 2) 染色体的第一个和最后一个基因位不为0, 且每一对0元素的第一个应该在偶数基因位; 3) 非0元素按升序排列.
以
$M=700 $ ,$N=5 $ , 目标点访问顺序为(2, 5, 1, 4, 3)为例, 一个满足所有条件的染色体的例子如图12所示. 图12所示的染色体的含义为: 无人机起飞, 连续访问${\boldsymbol{q}}_2 $ 和${\boldsymbol{q}}_5 $ 后降落, 然后起飞连续访问${\boldsymbol{q}}_1 $ 和${\boldsymbol{q}}_4 $ 后降落, 然后起飞访问${\boldsymbol{q}}_3 $ , 降落, 整个访问过程结束.4.2 交叉操作与变异操作
交叉操作仍为单点交叉, 交叉与变异后仍需满足第2.2.1节中的约束条件a) ~ c), 因此本节仅允许交叉点在染色体的奇数基因位处, 且交叉后每条染色体仍应满足非0元素升序排列. 对于变异操作, 选择一组起飞降落点, 重新产生一组数据代替原数据, 这组起降点需满足的条件为: 第1个元素为降落点, 第2个元素为起飞点. 以图12所示的染色体为例, 标示出该染色体中所有可以发生交叉和变异操作的位置如图13, 图中下方的箭头(第3个除外)指出所有可以发生交叉操作的点, 椭圆框出所有可以发生变异操作的基因组(图中仅画出1个指示箭头).
图 13 染色体的可行交叉变异位置Fig. 13 Feasible positions of cross and mutation within a chromosome4.3 仿真结果
由约束(10)可知, 在无人机的每次起飞出勤过程中, 无人机和地面车的耗时必须相等. 当目标点数目增加时, 无人机起降点的排列变得密集, 约束(10)将更加容易被违反. 而由于约束(9)和(10)之间的制约关系, 约束(9)也可能被违反. 因此, 为验证第4.1节和第4.2节中提出的模型与算法, 在图7所示的复杂路网中增加若干目标点进行仿真测试. 增加的目标点坐标为: (30, 29), (27, 25), (19, 46), (26, 47), 遗传算法部分参数修改如下: 离散精度
$l=0.1 $ , 迭代次数1000, 种群大小2000,${\lambda _1}{\rm{ \;=\; }}500$ ,${\lambda _2}{\rm{ \;=\; }}350$ , 其他参数不变.4.3.1 一次访问一个目标点时的结果
为了对比分析算法拓展后能够减少无人机的飞行距离和违反量, 首先按第3节的算法求解无人机一次访问一个目标点时的路径规划结果, 如图14所示. 无人机的起飞降落点坐标以及约束(9)和(10)的违反量如表7所示. 由表7可知, 当无人机访问
${\boldsymbol{q}}_{12} $ 和${\boldsymbol{q}}_1 $ 时, 约束(9)被违反; 访问${\boldsymbol{q}}_{13} $ 时, 约束(10)的违反量为0.0153 h, 即55.08 s, 比第3节中的违反量大很多.
图 14 无人机一次访问一个目标点的路径规划结果Fig. 14 Path planning results of drone visiting one point each time表 7 无人机每次访问单个目标点时的约束违反量 (h)Table 7 UAV constraint violations when it is allowed to visit one point each time (h)目标点 无人机
用时$t_a $约束(9)违反量
$\max(t_a-U,0) $地面车
耗时$t_g $时间差
$|t_a-t_g| $${\tilde {\boldsymbol{q}}_1}({\boldsymbol{q}}_4)$ 0.0784 0 0.076 0.0024 ${\tilde {\boldsymbol{q}}_2}({\boldsymbol{q}}_5)$ 0.0670 0 0.066 0.0010 ${\tilde {\boldsymbol{q}}_3}({\boldsymbol{q}}_{11})$ 0.0941 0 0.090 0.0041 ${\tilde {\boldsymbol{q}}_4}({\boldsymbol{q}}_{12})$ 0.0579 0.1921 0.058 0.0001 ${\tilde {\boldsymbol{q}}_5}({\boldsymbol{q}}_3)$ 0.0544 0 0.054 0.0004 ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_1)$ 0.2512 0.0012 0.246 0.0052 ${\tilde {\boldsymbol{q}}_7}({\boldsymbol{q}}_2)$ 0.0669 0 0.066 0.0009 ${\tilde {\boldsymbol{q}}_8}({\boldsymbol{q}}_6)$ 0.1150 0 0.114 0.0010 ${\tilde {\boldsymbol{q}}_9}({\boldsymbol{q}}_7)$ 0.1368 0 0.136 0.0008 ${\tilde {\boldsymbol{q}}_{10}}({\boldsymbol{q}}_{10})$ 0.0863 0 0.086 0.0003 ${\tilde {\boldsymbol{q}}_{11}}({\boldsymbol{q}}_{13})$ 0.1033 0 0.088 0.0153 ${\tilde {\boldsymbol{q}}_{12}}({\boldsymbol{q}}_{14})$ 0.1303 0 0.120 0.0103 ${\tilde {\boldsymbol{q}}_{13}}({\boldsymbol{q}}_9)$ 0.0798 0 0.078 0.0018 ${\tilde {\boldsymbol{q}}_{14}}({\boldsymbol{q}}_8)$ 0.1068 0 0.106 0.0008 4.3.2 一次连续访问多个目标点时的路径规划结果及比较分析
本节使用第4.2节的算法, 重新规划异构机器人系统的路径, 结果如图15(a)所示. 地面车路径长度的收敛曲线如图15(b)所示, 在蚁群算法的第29次迭代中得到了最短的无人机路线, 无人机在蚁群算法第29代的距离收敛曲线如图15(c)所示.
图 15 无人机一次访问多个目标点的路径规划结果Fig. 15 Path planning results of drone visiting multi-points each time由图15(a)可知, 无人机的飞行距离为108.6227 km, 无人机访问所有目标点的过程为: 第1次起飞访问
${\boldsymbol{q}}_4 $ , 第2次起飞连续访问${\boldsymbol{q}}_5 $ 和${\boldsymbol{q}}_{11 }$ , 第3次连续访问${\boldsymbol{q}}_{12 }$ 和${\boldsymbol{q}}_3 $ , 第4次访问${\boldsymbol{q}}_1 $ , 第5次访问${\boldsymbol{q}}_2 $ , 第6次访问${\boldsymbol{q}}_6 $ , 第7次访问${\boldsymbol{q}}_7 $ , 第8次连续访问${\boldsymbol{q}}_{10 }$ 和${\boldsymbol{q}}_{13} $ , 第9次连续访问${\boldsymbol{q}}_{14 }$ 和${\boldsymbol{q}}_9 $ , 第10次访问${\boldsymbol{q}}_8 $ . 无人机的起飞降落点坐标以及约束(9)和(10)的违反量如表8所示.表 8 允许无人机每次访问多个目标点时的约束违反量 (h)Table 8 UAV constraint violations when it is allowed to visit multi-points each time (h)目标点 无人机
用时$t_a $约束(9)违反量
$\max(t_a-U,0) $地面车
耗时$t_g $时间差
$|t_a-t_g| $${\tilde {\boldsymbol{q}}_1}({\boldsymbol{q}}_4)$ 0.0811 0 0.0800 0.0011 ${\tilde {\boldsymbol{q}}_2}({\boldsymbol{q}}_5,{\boldsymbol{q}}_{11})$ 0.1115 0 0.1120 0.0005 ${\tilde {\boldsymbol{q}}_3}({\boldsymbol{q}}_{12},{\boldsymbol{q}}_{3})$ 0.0620 0 0.0630 0.0010 ${\tilde {\boldsymbol{q}}_4}({\boldsymbol{q}}_1)$ 0.2460 0 0.2440 0.0020 ${\tilde {\boldsymbol{q}}_5}({\boldsymbol{q}}_2)$ 0.0680 0 0.0680 0 ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_6)$ 0.1099 0 0.1100 0.0001 ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_7)$ 0.1458 0 0.1460 0.0002 ${\tilde {\boldsymbol{q}}_8}({\boldsymbol{q}}_{10},{\boldsymbol{q}}_{13})$ 0.1122 0 0.1120 0.0002 ${\tilde {\boldsymbol{q}}_9}({\boldsymbol{q}}_{14},{\boldsymbol{q}}_{9})$ 0.1458 0 0.1460 0.0002 ${\tilde {\boldsymbol{q}}_{10}}({\boldsymbol{q}}_8)$ 0.1067 0 0.1062 0.0005 由表8可知, 约束(9)未被违反, 约束(10)的违反量最大值仅为0.0020 h, 相当于7.2 s, 即地面车需等待无人机7.2 s. 由仿真结果可知, 算法拓展后不仅缩短了无人机的飞行距离, 而且减小了无人机和地面机器人互相等待的时间.
5. 结束语
本文所研究的系统由一架无人机和一辆无人地面车组成, 其中地面车负载能力强并可以携带足够多的能量或物资, 其能量在执行任务的过程中不会耗尽, 而无人机的续航能力有限, 它在执行任务的过程中需要返回地面车上充电或更换电池. 地面车在路网中行驶, 由无人机去访问位于路网附近的目标点. 所有目标访问完成后, 无人机降落在地面车上一起运动到给定的终点.
本文考虑实际环境中道路网络的限制, 仅允许地面车在道路网络中行驶, 为了缩短完成任务的时间, 不仅规划无人机的路径, 还同时为地面车规划路径. 本文提出采用蚁群算法和遗传算法相结合的两步法解决了上述问题, 分别在3种不同的环境中验证了所提方法的有效性. 为了进一步缩短任务时间, 还研究了允许无人机每次出勤时连续访问多个目标点的路径规划问题.
由于要满足无人机的续航时间约束以及无人机与地面车无需互相等待的约束, 目标点的数量不宜过多. 如果目标点数目过多, 可能会引起无人机起降坐标点过于拥挤, 从而使得无人机需要等待地面车. 未来的工作中将考虑加入多个无人机来解决该问题. 虽然本文的方法在异构机器人协作规划中表现出优势, 但还没有得到实物验证. 后续工作将重点关注本文方法在空地异构协作机器人中的物理实现以及在协作投递、巡逻和监测领域的应用.
-
图 3 路网约束下异构机器人系统示意图
Fig. 3 Schematic diagram of heterogeneous robot system with road network constraints
图 9 复杂路网交通中断时的仿真结果
Fig. 9 Simulation results on the complex road network in case interruption
图 13 染色体的可行交叉变异位置
Fig. 13 Feasible positions of cross and mutation within a chromosome
图 14 无人机一次访问一个目标点的路径规划结果
Fig. 14 Path planning results of drone visiting one point each time
图 15 无人机一次访问多个目标点的路径规划结果
Fig. 15 Path planning results of drone visiting multi-points each time
表 1 code2的一个编码示例
Table 1 A sample of code2
编码对象 编码内容 code1 基因值 2 3 1 4 code2 基因值 15 62 78 104 350 461 666 692 $\boldsymbol{\alpha } $, $\boldsymbol{\beta } $为1
的元素${\alpha } _{15, 2}$ ${\beta } _{62, 2}$ ${\alpha } _{78, 3}$ ${\beta }_{104, 3}$ ${\alpha } _{350, 1}$ ${\beta }_{461, 1}$ ${\alpha }_{666, 4}$ ${\beta }_{692, 4}$ 
下载: 导出CSV
表 2 简单路网仿真中无人机的约束违反量 (h)
Table 2 UAV constraints violations in the simulation of the simple road network (h)
目标点 无人机
用时$t_a $约束(9)违反量
$\max(t_a-U,0) $地面车
耗时$t_g $时间差
$|t_a-t_g| $${\tilde {\boldsymbol{q}}_1}({{\boldsymbol{q}}_5})$ 0.1271 0 0.128 0.0009 ${\tilde {\boldsymbol{q}}_2}({{\boldsymbol{q}}_4})$ 0.1599 0 0.160 0.0001 ${\tilde {\boldsymbol{q} }_3}({ {\boldsymbol{q} }_3})$ 0.1613 0 0.160 0.0013 ${\tilde {\boldsymbol{q}}_4}({{\boldsymbol{q}}_2})$ 0.1392 0 0.140 0.0008 ${\tilde {\boldsymbol{q}}_5}({{\boldsymbol{q}}_1})$ 0.0533 0 0.052 0.0013
下载: 导出CSV
表 3 复杂路网仿真中无人机的约束违反量 (h)
Table 3 UAV constraint violations in the simulation of the complex road network (h)
目标点 无人机
用时$ t_a $约束(9)违反量
$\max(t_a-U,0) $地面车
耗时$t_g $时间差
$ |t_a-t_g| $${\tilde {\boldsymbol{q}}_1}({{\boldsymbol{q}}_4})$ 0.0859 0 0.086 0.0001 ${\tilde {\boldsymbol{q}}_2}({{\boldsymbol{q}}_5})$ 0.0761 0 0.076 0.0001 ${\tilde {\boldsymbol{q}}_3}({{\boldsymbol{q}}_3})$ 0.0482 0 0.048 0.0002 ${\tilde {\boldsymbol{q}}_4}({{\boldsymbol{q}}_1})$ 0.2331 0 0.224 0.0091 ${\tilde {\boldsymbol{q}}_5}({{\boldsymbol{q}}_2})$ 0.0668 0 0.066 0.0008 ${\tilde {\boldsymbol{q}}_6}({{\boldsymbol{q}}_6})$ 0.1078 0 0.108 0.0002 ${\tilde {\boldsymbol{q}}_7}({{\boldsymbol{q}}_7})$ 0.1643 0 0.164 0.0003 ${\tilde {\boldsymbol{q}}_8}({{\boldsymbol{q}}_{10}})$ 0.1042 0 0.104 0.0002 ${\tilde {\boldsymbol{q}}_9}({{\boldsymbol{q}}_9})$ 0.0863 0 0.086 0.0003 ${\tilde {\boldsymbol{q}}_{10}}({{\boldsymbol{q}}_8})$ 0.1084 0 0.108 0.0004
下载: 导出CSV
表 4 交通中断仿真中无人机的约束违反量 (h)
Table 4 UAV constraint violations in the simulation with traffic interruption (h)
目标点 无人机
用时$t_a $约束(9)违反量
$\max(t_a-U,0)$地面车
耗时$t_g $时间差
$|t_a-t_g| $${\tilde {\boldsymbol{q}}_1}({\boldsymbol{q}}_5)$ 0.1338 0 0.134 0.0002 ${\tilde {\boldsymbol{q}}_2}({\boldsymbol{q}}_4)$ 0.2137 0 0.214 0.0003 ${\tilde {\boldsymbol{q}}_3}({\boldsymbol{q}}_3)$ 0.1899 0 0.190 0.0001 ${\tilde {\boldsymbol{q}}_4}({\boldsymbol{q}}_1)$ 0.2244 0 0.224 0.0004 ${\tilde {\boldsymbol{q}}_5}({\boldsymbol{q}}_2)$ 0.0766 0 0.076 0.0006 ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_6)$ 0.1070 0 0.106 0.0010 ${\tilde {\boldsymbol{q}}_7}({\boldsymbol{q}}_7)$ 0.1625 0 0.162 0.0005 ${\tilde {\boldsymbol{q}}_8}({\boldsymbol{q}}_{10})$ 0.0910 0 0.092 0.0010 ${\tilde {\boldsymbol{q}}_9}({\boldsymbol{q}}_{9})$ 0.0981 0 0.098 0.0001 ${\tilde {\boldsymbol{q}}_{10}}({\boldsymbol{q}}_{8})$ 0.1074 0 0.108 0.0006
下载: 导出CSV
表 5 简单路网中的比较结果
Table 5 Comparison results in simple road network
算法名称 最优代价值 平均运行时间 (s) MACO-GA 56.8479 0.1832 MACO-PSO 87.6916 0.3628
下载: 导出CSV
表 6 复杂路网中的比较结果
Table 6 Comparison results in complex road network
算法名称 最优代价值 平均运行时间 (s) MACO-GA 116.8250 0.2453 MACO-PSO 331.2657 0.4873
下载: 导出CSV
表 7 无人机每次访问单个目标点时的约束违反量 (h)
Table 7 UAV constraint violations when it is allowed to visit one point each time (h)
目标点 无人机
用时$t_a $约束(9)违反量
$\max(t_a-U,0) $地面车
耗时$t_g $时间差
$|t_a-t_g| $${\tilde {\boldsymbol{q}}_1}({\boldsymbol{q}}_4)$ 0.0784 0 0.076 0.0024 ${\tilde {\boldsymbol{q}}_2}({\boldsymbol{q}}_5)$ 0.0670 0 0.066 0.0010 ${\tilde {\boldsymbol{q}}_3}({\boldsymbol{q}}_{11})$ 0.0941 0 0.090 0.0041 ${\tilde {\boldsymbol{q}}_4}({\boldsymbol{q}}_{12})$ 0.0579 0.1921 0.058 0.0001 ${\tilde {\boldsymbol{q}}_5}({\boldsymbol{q}}_3)$ 0.0544 0 0.054 0.0004 ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_1)$ 0.2512 0.0012 0.246 0.0052 ${\tilde {\boldsymbol{q}}_7}({\boldsymbol{q}}_2)$ 0.0669 0 0.066 0.0009 ${\tilde {\boldsymbol{q}}_8}({\boldsymbol{q}}_6)$ 0.1150 0 0.114 0.0010 ${\tilde {\boldsymbol{q}}_9}({\boldsymbol{q}}_7)$ 0.1368 0 0.136 0.0008 ${\tilde {\boldsymbol{q}}_{10}}({\boldsymbol{q}}_{10})$ 0.0863 0 0.086 0.0003 ${\tilde {\boldsymbol{q}}_{11}}({\boldsymbol{q}}_{13})$ 0.1033 0 0.088 0.0153 ${\tilde {\boldsymbol{q}}_{12}}({\boldsymbol{q}}_{14})$ 0.1303 0 0.120 0.0103 ${\tilde {\boldsymbol{q}}_{13}}({\boldsymbol{q}}_9)$ 0.0798 0 0.078 0.0018 ${\tilde {\boldsymbol{q}}_{14}}({\boldsymbol{q}}_8)$ 0.1068 0 0.106 0.0008
下载: 导出CSV
表 8 允许无人机每次访问多个目标点时的约束违反量 (h)
Table 8 UAV constraint violations when it is allowed to visit multi-points each time (h)
目标点 无人机
用时$t_a $约束(9)违反量
$\max(t_a-U,0) $地面车
耗时$t_g $时间差
$|t_a-t_g| $${\tilde {\boldsymbol{q}}_1}({\boldsymbol{q}}_4)$ 0.0811 0 0.0800 0.0011 ${\tilde {\boldsymbol{q}}_2}({\boldsymbol{q}}_5,{\boldsymbol{q}}_{11})$ 0.1115 0 0.1120 0.0005 ${\tilde {\boldsymbol{q}}_3}({\boldsymbol{q}}_{12},{\boldsymbol{q}}_{3})$ 0.0620 0 0.0630 0.0010 ${\tilde {\boldsymbol{q}}_4}({\boldsymbol{q}}_1)$ 0.2460 0 0.2440 0.0020 ${\tilde {\boldsymbol{q}}_5}({\boldsymbol{q}}_2)$ 0.0680 0 0.0680 0 ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_6)$ 0.1099 0 0.1100 0.0001 ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_7)$ 0.1458 0 0.1460 0.0002 ${\tilde {\boldsymbol{q}}_8}({\boldsymbol{q}}_{10},{\boldsymbol{q}}_{13})$ 0.1122 0 0.1120 0.0002 ${\tilde {\boldsymbol{q}}_9}({\boldsymbol{q}}_{14},{\boldsymbol{q}}_{9})$ 0.1458 0 0.1460 0.0002 ${\tilde {\boldsymbol{q}}_{10}}({\boldsymbol{q}}_8)$ 0.1067 0 0.1062 0.0005
下载: 导出CSV
-
[1] Garone E, Naldi R, Casavola A, Frazzoli E. Cooperative mission planning for a class of carrier-vehicle systems. In: Proceedings of the 49th IEEE Conference on Decision and Control (CDC). Atlanta, Georgia, USA: IEEE, 2010. 1354–1359 [2] 武文亮, 周兴社, 沈博, 赵月. 集群机器人系统特性评价研究综述. 自动化学报, 2022, 48(5): 1153−1172 doi: 10.16383/j.aas.c200964Wu Wen-Liang, Zhou Xing-She, Shen Bo, Zhao Yue. A review of swarm robotic systems property evaluation research. Acta Automatica Sinica, 2022, 48(5): 1153−1172 doi: 10.16383/j.aas.c200964 [3] Ulmer M W, Thomas B W. Same-day delivery with heterogeneous fleets of drones and vehicles. Networks, 2018, 72(4): 475-505. doi: 10.1002/net.21855 [4] Mario M, Leonardo C, Michele O, Dell’Orco M. En route truck–drone parcel delivery for optimal vehicle routing strategies. IET Intelligent Transport Systems, 2018, 12(4): 253-261. doi: 10.1049/iet-its.2017.0227 [5] Klauco M, Blažek S, Kvasnica M. An optimal path planning problem for heterogeneous multi-vehicle systems. International Journal of Applied Mathematics and Computer Science, 2016, 26(2): 297-308. doi: 10.1515/amcs-2016-0021 [6] Wang T, Huang P F, Dong G Q. Modeling and path planning for persistent surveillance by unmanned ground vehicle. IEEE Transactions on Automation Science and Engineering, 2021, 18(4): 1615−1625 [7] Ding Y L, Xin B, Zhang H, Chen J. A memetic algorithm for curvature-constrained path planning of messenger UAV in air-ground coordination. In: Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (SMC). Toronto, ON, Canada: IEEE, 2020. 1465–1472 [8] Ramasamy M, Ghose D. Learning-based preferential surveillance algorithm for persistent surveillance by unmanned aerial vehicles. In: Proceedings of the International Conference on Unmanned Aircraft Systems (ICUAS). Arlington, VA, USA: IEEE, 2016. 1032–1040 [9] 李勇, 李坤成, 孙柏青, 张秋豪, 王义娜, 杨俊友. 智能体Petri网融合的多机器人-多任务协调框架. 自动化学报, 2021, 47(8): 2029−2049. https://doi.org/10.16383/j.aas.c190400. doi: 10.16383/j.aas.c190400LI Yong, LI Kun-Cheng, SUN Bai-Qing, ZHANG Qiu-Hao, WANG Yi-Na, YANG Jun-You. Multi-robot multi-task coordination framework based on the integration of intelligent agent and Petri net. Acta Automatica Sinica, 2021, 47(8): 2029−2049. doi: 10.16383/j.aas.c190400 [10] Sun G, Zhou R, Di B, Dong Z, Wang Y. A Novel Cooperative path planning for multi-robot persistent coverage with obstacles and coverage period constraints. Sensors, 2019, 19(9), 1994: 1-28. doi: 10.1109/JSEN.2019.2897439 [11] Agatz N, Bouman P, Schmidt M. Optimization approaches for the traveling salesman problem with drone. Transportation Science, 2018, 52(4): 965-981. doi: 10.1287/trsc.2017.0791 [12] De Freitas J C, Penna P H. A variable neighborhood search for flying sidekick traveling salesman problem. International Transactions in Operational Research, 2019, 27(1): 267-290. [13] Murray C C, Chu A G. The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery. Transportation Research Part C-emerging Technologies, 2015, 54(54): 86-109. [14] Ha Q M, Deville Y, Pham Q D, Hoàng Hàc M. On the min-cost traveling salesman problem with drone. Transportation Research Part C-emerging Technologies, 2018, 86: 597-621. doi: 10.1016/j.trc.2017.11.015 [15] Ham A. Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming. Transportation Research, 2018, 91: 1-14. [16] Klauco M, Blazek S, Kvasnica M, Fikar M. Mixed-integer SOCP formulation of the path planning problem for heterogeneous multi-vehicle systems. In: Proceedings of the European Control Conference (ECC). Strasbourg, France: IEEE, 2014. 1474–1479 [17] 陈洋, 谭艳平, 程磊, 吴怀宇. 邻域约束下空地异构机器人系统路径规划方法. 机器人, 2017, 39(1): 1-7.Chen Yang, Tan Yan-Ping, Cheng Lei, Wu Huai-Yu. Path planning for a heterogeneous aerial-ground robot system with neighbourhood constraints. Robot, 2017, 39(1): 1-7. [18] Maini P, Sundar K, Singh M, Rathinam S, Sujit P B. Cooperative aerial–ground vehicle route planning with fuel constraints for coverage applications. IEEE Transactions on Aerospace and Electronic Systems, 2019, 55(6): 3016-3028. doi: 10.1109/TAES.2019.2917578 [19] Carlsson J G, Song S. Coordinated logistics with a truck and a drone. Management Science, 2018, 64(9): 4052-4069. doi: 10.1287/mnsc.2017.2824 [20] Mathew N, Smith S L, Waslander S L. Planning paths for package delivery in heterogeneous multirobot teams. IEEE Transactions on Automation Science and Engineering, 2015, 12(4): 1298-1308. doi: 10.1109/TASE.2015.2461213 期刊类型引用(10)
1. 毛剑琳，李昊楠，张凯翔，张书凡，付丽霞. 基于耦合度矩阵的安全区间多机器人路径k鲁棒规划算法. 控制与决策. 2025(02): 488-496 . 
百度学术2. 姚鹏，钟晨. 面向非广域目标的无人机对峙跟踪方法. 无人系统技术. 2024(01): 78-86 . 百度学术3. 张宇璇，张楠. 基于改进灰狼算法的物流机器人运动路径规划方法. 计算机测量与控制. 2024(09): 276-282 . 百度学术4. 朱大智，颜清，王柳乃. 基于机器视觉和进化算法的变电站巡检机器人运行路径规划方法. 微型电脑应用. 2024(12): 202-206 . 百度学术5. 陈洋，李赢，华铁丹，邱权. 基于异构无人系统的水渠网络自主巡检路径规划. 农业机械学报. 2023(07): 79-87+155 . 百度学术6. 潘斌. 一种可配置异构多核SoC的设计实现方法. 单片机与嵌入式系统应用. 2023(09): 20-23 . 百度学术7. 才洋，于功志，纪雅悦. 多目标遗传算法下焊接机器人焊接路径规划方法研究. 焊接技术. 2023(12): 112-116 . 百度学术8. 李昊楠，毛剑琳，张凯翔，李大焱，王妮娅. 一种基于安全区间的多机器人路径k鲁棒规划算法. 仪器仪表学报. 2023(10): 274-282 . 百度学术9. 张琰，蔡静. 复杂环境下移动机器人自动路径规划研究. 电脑编程技巧与维护. 2022(10): 122-124+144 . 百度学术10. 唐元智. 生产建设项目水土保持监测技术方法研究进展. 中国水土保持. 2021(12): 53-57 . 百度学术其他类型引用(11)
-
下载:
计量
- 文章访问数: 1864
- HTML全文浏览量: 506
- PDF下载量: 407
- 被引次数: 21
