目录1.摘要2.两阶段路径规划方法3.实验分析4.结论5.参考文献6.算法辅导·应用定制·读者交流1.摘要研究面向多个植保无人航空系统UAS在分散、不规则农田上的协同喷洒任务同时考虑多个农药与电池补给基地。本文提出两阶段混合算法先嵌套遗传算法nested GA联合优化田块拆分与合并使每项任务的面积不超过但尽量接近单架次作业上限并减少跨田块转移用整数粒子群算法integer PSO配置 UAS 的初始基地与作业顺序以同时压缩总作业时间和非作业飞行距离。2.两阶段路径规划方法输入包括目标田块和基地的位置、UAS 数量与性能、作物喷洒要求。单架次最大作业面积记为S SS任一基地到任一田块均在飞行与作业续航范围内。第一阶段从原始田块生成面积受限的喷洒任务第二阶段生成各任务的覆盖路径并完成 UAS—基地—任务的分配与调度。基于嵌套 GA 田块拆分与合并原始田块集合为F FF田块数为f ff。面积超过S SS的田块沿最长边方向平移切分线直至每个子田块面积不超过S SS二进制拆分矩阵F S FSFS决定切分线从最长边朝最远顶点平移或反向平移。拆分后的田块数可预先计算为f ′ ∑ i 1 f ⌈ Area ( F i ) / S ⌉ f\sum_{i1}^{f}\left\lceil \operatorname{Area}(F_i)/S\right\rceilf′∑i1f⌈Area(Fi)/S⌉传统模式直接把这f ′ ff′个子田块视为独立架次。仅拆分会留下许多远小于S SS的任务因此论文用排列矩阵F M FMFM指定子田块的合并顺序。每个合并任务可包含两个或多个相邻子田块但必须满足单架次面积约束∑ Area ( F i ′ ′ ) ≤ S , i 1 , … , f ′ ′ . \sum \operatorname{Area}\!\left(F_i\right)\leq S,\qquad i1,\ldots,f.∑Area(Fi′′)≤S,i1,…,f′′.合并还受距离上限l m l_mlm约束。若合并任务i ii内相邻子田块中心的总距离为l i l_ili拆分—合并目标为G 1 f ′ ′ 1 α ∑ i 1 f ′ ′ l i . G_1f\frac{1}{\alpha}\sum_{i1}^{f}l_i.G1f′′α1i1∑f′′li.单架次覆盖路径与多基地调度单个子田块采用与初始化切分线方向一致的往复式覆盖航线喷幅w ww由作物喷洒要求确定。相邻航线的平移距离根据剩余横向距离和是否仍需转弯自适应调整。对于由多个子田块合并而成的一架次任务算法从 UAS 当前位置选择最近的作业起点完成当前子田块后继续选择最近的未覆盖子田块最后从末端飞向最近补给基地。非作业航段由起飞基地到首个作业起点的d 1 d_1d1、子田块之间的d 2 d_2d2和末端到降落基地的d 3 d_3d3构成。单架次路径生成逐次连接最近的未覆盖子田块任务结束后选择最近基地降落并同步更新田块集合和 UAS 位置。多 UAS 调度按预计降落时间动态选择下一架次较早完成的 UAS 优先领取任务。若同一基地的补给人力有限准备时间不仅包含固定的农药与电池更换时间还包含多架 UAS 排队造成的等待。所有起降时刻必须覆盖全部N NN个任务。初始基地分配向量B ′ BB′的每个元素代表一架 UAS 的出发基地其优化目标为G 2 t s ∑ i 1 f ′ ′ ( β 1 d 1 i β 2 d 2 i β 3 d 3 i ) , G_2t_s\sum_{i1}^{f}\left(\beta_1d_{1i}\beta_2d_{2i}\beta_3d_{3i}\right),G2tsi1∑f′′(β1d1iβ2d2iβ3d3i),其中t s t_sts是最后一架 UAS 完工时刻β 1 \beta_1β1、β 2 \beta_2β2、β 3 \beta_3β3分别刻画满载起飞、田块间转场和施药后返航三类航段的能耗差异。整数 PSO 通过下式更新粒子速度与基地编号V ( i , j 1 ) Round { ω V ( i , j ) c 1 r 1 [ B ′ ( b e s t , j ) − B ′ ( i , j ) ] c 2 r 2 [ B ′ ( i , b e s t ) − B ′ ( i , j ) ] } , V(i,j1)\operatorname{Round}\!\left\{\omega V(i,j)c_1r_1\left[B(\mathrm{best},j)-B(i,j)\right]c_2r_2\left[B(i,\mathrm{best})-B(i,j)\right]\right\},V(i,j1)Round{ωV(i,j)c1r1[B′(best,j)−B′(i,j)]c2r2[B′(i,best)−B′(i,j)]},B ′ ( i , j 1 ) Mod ( B ′ ( i , j ) V ( i , j 1 ) , b ) 1. B(i,j1)\operatorname{Mod}\!\left(B(i,j)V(i,j1),b\right)1.B′(i,j1)Mod(B′(i,j)V(i,j1),b)1.b bb为基地数ω \omegaω为惯性权重c 1 , c 2 c_1,c_2c1,c2为加速常数r 1 , r 2 ∈ [ 0 , 1 ] r_1,r_2\in[0,1]r1,r2∈[0,1]。取整和模运算把连续 PSO 更新映射回合法的整数基地编号。3.实验分析田块任务生成单纯拆分得到 83 个任务。固定合并距离上限时l m l_mlm越大架次数越少但跨田块距离随之增加。较宽松的距离上限有利于减少任务数却会增加跨田块合并若一开始允许过多田块合并还可能妨碍剩余田块形成更好的组合因此l m l_mlm的变化区间会同时改变最优F S FSFS和F M FMFM。当l m l_mlm依次取50 → 150 50\rightarrow15050→150、50 → 200 50\rightarrow20050→200、50 → 250 50\rightarrow25050→250、100 → 200 100\rightarrow200100→200、100 → 250 100\rightarrow250100→250和150 → 250 150\rightarrow250150→250m 时的拆分—合并方案绿色区域表示被组合进同一架次的子田块。基地分配与作业调度在 5 架 UAS、3 个基地的案例中整数 PSO 约在第 5 次迭代达到最小G 2 G_2G2得到初始基地分配B ′ [ 1 , 2 , 2 , 1 , 1 ] T B[1,2,2,1,1]^\mathsf{T}B′[1,2,2,1,1]T。该解没有把 UAS 均匀铺到三个基地而是在早期容忍轻微等待以避免中后期大量 UAS 集中到最受欢迎的 1 号基地。PSO 方案总作业时间为 178.9 min三种均匀分配的传统方案分别为 191.6、183.2 和 198.5 min。实际作业过程中UAS 可以在不同于起飞基地的位置降落任务也不是按基地周边简单划区而是随 UAS 完工时刻和剩余田块动态分配。方法比较与参数影响在固定补给准备时间 5 min 的测试中GA–PSO 在所有 UAS 数与基地数组合上都取得比 HHO–PSO 和传统方法更小的G 2 G_2G2、总作业时间与非作业距离。补给准备时间为 5 min 时GA–PSO、HHO–PSO 和传统方法的G 2 G_2G2随 UAS 数量变化每条曲线对应 1–5 个基地。在固定 4 架 UAS、把准备时间从 1 min 增至 5 min 的测试中三种方法的G 2 G_2G2均上升但 GA–PSO 增幅较缓。准备时间为 5 min 且仅有 1 个基地时GA–PSO、HHO–PSO 和传统方法的总作业时间分别为 267.30、300.85 和 412.40 min增加到 5 个基地后三者分别降至 209.45、222.82 和 294.37 min。HHO–PSO 与传统方法在准备时间由 4 min 增至 5 min 时更容易出现作业时间跃升说明初始基地分配和动态调度能抑制受限补给资源引起的拥塞。4.结论论文把喷洒任务生成、单架次覆盖路径、多 UAS 调度和多基地补给纳入两阶段优化。若目标是压缩工期应优先增加 UAS若目标是减少空飞应优先增加补给基地而基地扩展在补给拥塞明显时还能兼顾工期。5.参考文献Xu Y, Han Y, Sun Z, et al. Path planning optimization with multiple pesticide and power loading bases using several unmanned aerial systems on segmented agricultural fields[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022, 53(3): 1882-1894.6.算法辅导·应用定制·读者交流xx
2023 IEEE TSMCS，多农药与电池补给基地下分割农田多无人航空系统路径规划优化
目录1.摘要2.两阶段路径规划方法3.实验分析4.结论5.参考文献6.算法辅导·应用定制·读者交流1.摘要研究面向多个植保无人航空系统UAS在分散、不规则农田上的协同喷洒任务同时考虑多个农药与电池补给基地。本文提出两阶段混合算法先嵌套遗传算法nested GA联合优化田块拆分与合并使每项任务的面积不超过但尽量接近单架次作业上限并减少跨田块转移用整数粒子群算法integer PSO配置 UAS 的初始基地与作业顺序以同时压缩总作业时间和非作业飞行距离。2.两阶段路径规划方法输入包括目标田块和基地的位置、UAS 数量与性能、作物喷洒要求。单架次最大作业面积记为S SS任一基地到任一田块均在飞行与作业续航范围内。第一阶段从原始田块生成面积受限的喷洒任务第二阶段生成各任务的覆盖路径并完成 UAS—基地—任务的分配与调度。基于嵌套 GA 田块拆分与合并原始田块集合为F FF田块数为f ff。面积超过S SS的田块沿最长边方向平移切分线直至每个子田块面积不超过S SS二进制拆分矩阵F S FSFS决定切分线从最长边朝最远顶点平移或反向平移。拆分后的田块数可预先计算为f ′ ∑ i 1 f ⌈ Area ( F i ) / S ⌉ f\sum_{i1}^{f}\left\lceil \operatorname{Area}(F_i)/S\right\rceilf′∑i1f⌈Area(Fi)/S⌉传统模式直接把这f ′ ff′个子田块视为独立架次。仅拆分会留下许多远小于S SS的任务因此论文用排列矩阵F M FMFM指定子田块的合并顺序。每个合并任务可包含两个或多个相邻子田块但必须满足单架次面积约束∑ Area ( F i ′ ′ ) ≤ S , i 1 , … , f ′ ′ . \sum \operatorname{Area}\!\left(F_i\right)\leq S,\qquad i1,\ldots,f.∑Area(Fi′′)≤S,i1,…,f′′.合并还受距离上限l m l_mlm约束。若合并任务i ii内相邻子田块中心的总距离为l i l_ili拆分—合并目标为G 1 f ′ ′ 1 α ∑ i 1 f ′ ′ l i . G_1f\frac{1}{\alpha}\sum_{i1}^{f}l_i.G1f′′α1i1∑f′′li.单架次覆盖路径与多基地调度单个子田块采用与初始化切分线方向一致的往复式覆盖航线喷幅w ww由作物喷洒要求确定。相邻航线的平移距离根据剩余横向距离和是否仍需转弯自适应调整。对于由多个子田块合并而成的一架次任务算法从 UAS 当前位置选择最近的作业起点完成当前子田块后继续选择最近的未覆盖子田块最后从末端飞向最近补给基地。非作业航段由起飞基地到首个作业起点的d 1 d_1d1、子田块之间的d 2 d_2d2和末端到降落基地的d 3 d_3d3构成。单架次路径生成逐次连接最近的未覆盖子田块任务结束后选择最近基地降落并同步更新田块集合和 UAS 位置。多 UAS 调度按预计降落时间动态选择下一架次较早完成的 UAS 优先领取任务。若同一基地的补给人力有限准备时间不仅包含固定的农药与电池更换时间还包含多架 UAS 排队造成的等待。所有起降时刻必须覆盖全部N NN个任务。初始基地分配向量B ′ BB′的每个元素代表一架 UAS 的出发基地其优化目标为G 2 t s ∑ i 1 f ′ ′ ( β 1 d 1 i β 2 d 2 i β 3 d 3 i ) , G_2t_s\sum_{i1}^{f}\left(\beta_1d_{1i}\beta_2d_{2i}\beta_3d_{3i}\right),G2tsi1∑f′′(β1d1iβ2d2iβ3d3i),其中t s t_sts是最后一架 UAS 完工时刻β 1 \beta_1β1、β 2 \beta_2β2、β 3 \beta_3β3分别刻画满载起飞、田块间转场和施药后返航三类航段的能耗差异。整数 PSO 通过下式更新粒子速度与基地编号V ( i , j 1 ) Round { ω V ( i , j ) c 1 r 1 [ B ′ ( b e s t , j ) − B ′ ( i , j ) ] c 2 r 2 [ B ′ ( i , b e s t ) − B ′ ( i , j ) ] } , V(i,j1)\operatorname{Round}\!\left\{\omega V(i,j)c_1r_1\left[B(\mathrm{best},j)-B(i,j)\right]c_2r_2\left[B(i,\mathrm{best})-B(i,j)\right]\right\},V(i,j1)Round{ωV(i,j)c1r1[B′(best,j)−B′(i,j)]c2r2[B′(i,best)−B′(i,j)]},B ′ ( i , j 1 ) Mod ( B ′ ( i , j ) V ( i , j 1 ) , b ) 1. B(i,j1)\operatorname{Mod}\!\left(B(i,j)V(i,j1),b\right)1.B′(i,j1)Mod(B′(i,j)V(i,j1),b)1.b bb为基地数ω \omegaω为惯性权重c 1 , c 2 c_1,c_2c1,c2为加速常数r 1 , r 2 ∈ [ 0 , 1 ] r_1,r_2\in[0,1]r1,r2∈[0,1]。取整和模运算把连续 PSO 更新映射回合法的整数基地编号。3.实验分析田块任务生成单纯拆分得到 83 个任务。固定合并距离上限时l m l_mlm越大架次数越少但跨田块距离随之增加。较宽松的距离上限有利于减少任务数却会增加跨田块合并若一开始允许过多田块合并还可能妨碍剩余田块形成更好的组合因此l m l_mlm的变化区间会同时改变最优F S FSFS和F M FMFM。当l m l_mlm依次取50 → 150 50\rightarrow15050→150、50 → 200 50\rightarrow20050→200、50 → 250 50\rightarrow25050→250、100 → 200 100\rightarrow200100→200、100 → 250 100\rightarrow250100→250和150 → 250 150\rightarrow250150→250m 时的拆分—合并方案绿色区域表示被组合进同一架次的子田块。基地分配与作业调度在 5 架 UAS、3 个基地的案例中整数 PSO 约在第 5 次迭代达到最小G 2 G_2G2得到初始基地分配B ′ [ 1 , 2 , 2 , 1 , 1 ] T B[1,2,2,1,1]^\mathsf{T}B′[1,2,2,1,1]T。该解没有把 UAS 均匀铺到三个基地而是在早期容忍轻微等待以避免中后期大量 UAS 集中到最受欢迎的 1 号基地。PSO 方案总作业时间为 178.9 min三种均匀分配的传统方案分别为 191.6、183.2 和 198.5 min。实际作业过程中UAS 可以在不同于起飞基地的位置降落任务也不是按基地周边简单划区而是随 UAS 完工时刻和剩余田块动态分配。方法比较与参数影响在固定补给准备时间 5 min 的测试中GA–PSO 在所有 UAS 数与基地数组合上都取得比 HHO–PSO 和传统方法更小的G 2 G_2G2、总作业时间与非作业距离。补给准备时间为 5 min 时GA–PSO、HHO–PSO 和传统方法的G 2 G_2G2随 UAS 数量变化每条曲线对应 1–5 个基地。在固定 4 架 UAS、把准备时间从 1 min 增至 5 min 的测试中三种方法的G 2 G_2G2均上升但 GA–PSO 增幅较缓。准备时间为 5 min 且仅有 1 个基地时GA–PSO、HHO–PSO 和传统方法的总作业时间分别为 267.30、300.85 和 412.40 min增加到 5 个基地后三者分别降至 209.45、222.82 和 294.37 min。HHO–PSO 与传统方法在准备时间由 4 min 增至 5 min 时更容易出现作业时间跃升说明初始基地分配和动态调度能抑制受限补给资源引起的拥塞。4.结论论文把喷洒任务生成、单架次覆盖路径、多 UAS 调度和多基地补给纳入两阶段优化。若目标是压缩工期应优先增加 UAS若目标是减少空飞应优先增加补给基地而基地扩展在补给拥塞明显时还能兼顾工期。5.参考文献Xu Y, Han Y, Sun Z, et al. Path planning optimization with multiple pesticide and power loading bases using several unmanned aerial systems on segmented agricultural fields[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022, 53(3): 1882-1894.6.算法辅导·应用定制·读者交流xx
