現代的な果樹園の静かな列の中に、新しい種類の労働者が空へと舞い上がりました。それは無人航空機、すなわちドローンです。かつての大型で轟音を立てるトラクターとは異なり、これらの機械は木々の間を縫うように進むほど機敏であり、注意を要する病気になった葉や栄養不足の枝だけを標的にできるほど精密です。この「一律の散布」から「標的を絞ったケア」への転換は、化学薬品を節約し、環境を保護することを約束します。しかし、一台のドローンだけで全作業をこなすことはできません。バッテリーは切れ、液体農薬を運ぶタンクはすぐに満杯になります。広大な畑を守るためには、ドローンの艦隊（フリート）が協力して動かなければなりません。特定の地点にスプレーをかけるために飛び出し、中央の基地に戻って補充を行い、再び飛び出すという作業を交代で行う必要があります。課題は、どのドローンがどの木へ行くのか、どのような順序で行うのか、そして各ドローンが何回の往復を行うかを決定することにあります。もし計画が不適切であれば、一部のドローンは疲れ果て、他のドローンは手持ち無沙汰になるか、あるいはさらに悪いことに、地図上では短く見える経路が実際には木によって遮られていたり禁止区域であったりして、ドローンが墜落したり貴重なエネルギーを浪費したりすることになります。
南京郵電大学と南京理工大学の研究者たちは、これらの艦隊を調整するための新しい手法を開発することで、この複雑なスケジューリングのパズルに取り組みました。彼らは、単に木と木の間の直線距離を見るのではなく、枝や建物、制限区域などの障害物を回避するためにドローンが実際に飛ばなければならない安全な経路を計算するシステムを作り上げました。艦隊にとって最適なスケジュールを見つけ出すために、彼らはセイウチの行動にインスピoreされた新しいコンピュータ・アルゴリズムを設計しました。野生のセイウチは、新しい餌場を探索する必要性と、群れの近くに留まる安全性のバランスを取りながら、グループで移動します。研究者たちは、これらの社会的行動を数学的なルールへと翻訳し、コンピュータが数百万もの可能な飛行計画の中から、すべてのドローンが均等かつ安全に稼働し続けるような計画を見つけ出せるようにしました。
チームは、彼らが「改良型セイウチ最適化アルゴリズム（enhanced walrus optimizer）」と呼ぶこの新しいアルゴリズムを、同様の問題に使用されるいくつかの既存の手法と比較検証しました。彼らは、起伏のある地形、様々な高さの木々、そしてドローンが進入できない飛行禁止区域を備えた、現実的な果樹園環境をシミュレーションしました。これらのシミュレーションにおいて、新しいアルゴリズムは他の手法を一貫して上回りました。艦隊が飛行しなければならない総距離をわずかながらも意味のある範囲で短縮しましたが、その最も顕著な成果は、ワークロード（作業量）のバランス調整にありました。最良の結果では、最も忙しいドローンと最も暇なドローンの飛行距離の差が、次に優れた手法と比較して半分近くまで削減されました。これは、現実世界のシナリオにおいて、ドローンがほぼ同時に摩耗し、使い果たされた機械を交換することなく、艦隊がより長く稼働できることを意味します。
この成功の重要な要素は、研究者たちが果樹園の現実をどのように扱ったかにあります。多くの計画システムは、ドローンが次の木まで直線的に飛行できると想定しています。研究者たちは、この仮定が危険であることを示しました。証明された経路探索技術を用いて、障害物を回避するために必要な実際の迂回ルートをマッピングすることで、アルゴリズムによって生成されたスケジュールが物理的に飛行可能であることを保証しました。また、彼らは計画に第3の次元を加え、ドローンが地面や樹冠の上で安全な高度を維持し、急激な上昇や下降を行わないようにしました。これは航空機にとって危険を伴う可能性があるからです。彼らのシステムによって生成されたすべての飛行経路は、ドローンのバッテリー制限と安全規則の範囲内に収まっていることが確認されました。
この研究は、この新しいアプローチが、木や障害物が動かない静的な環境においてうまく機能することを裏付けています。研究者たちは、彼らの手法が、一つのドローンが過剰に働き、他のドローンが休んでいるという、全体の操作を遅らせる一般的な問題を防止することに特に優れていることを見出しました。このシステムは、まだ動く障害物や変化する天候には対応しておらず、すべてのドローンが同一であることを前提としていますが、自動農業の未来に向けた強固な基礎を提供しています。果樹園を平坦な地図ではなく複雑な三次元空間として扱い、自然に触発されたスマートなアルゴリズムを使用して艦隊を管理することで、研究者たちは、これらのロボット労働者を安全、効率的、かつバランスよく運用するための実用的な方法を提示しました。その結果、このスケジューリング手法は、混沌とした飛行の混在を、調整された信頼できる運用へと変え、作業を行う機械に過度な負担をかけることなく果樹園を守ることを可能にしています。
技術要約：改良型セイウチ最適化アルゴリズムを用いた、植物保護作業のための障害物認識型マルチUAVスケジューリング
問題提起
本論文は、複雑な地形や障害物を有する果樹園環境における、協調的な植物保護用無人航空機（UAV）のスケジューリングという課題に取り組んでいる。従来の被覆経路計画とは異なり、本研究は離散的な病害パッチや栄養不足箇所への標的型処理に焦点を当てている。核心となる問題は、以下の制約条件下での単一デポ、マルチUAV、マルチソート（複数回の出撃）スケジューリングタスクである。
- 航続性能とペイロード： バッテリー駆動範囲と農薬積載量の制限により、中央デポへの繰り返しの帰還が必要となる。
- 障害物回避： 木々、建物、飛行禁止区域の存在により、ユークリッド（直線）距離では正確なルート計画が困難となる。
- ワークロードの均衡： 特定のUAVへの過負荷を防ぐため、均質なフリート間でタスクを均等に分配する必要がある。
- 3次元的な実現可能性： 地形クリアランス、上昇角制限、および樹冠上空の特定の作業高度を遵守した、実行可能な経路を生成する必要がある。
既存の手法は、エッジコストを直線距離で評価することが多く、障害物が導入された際に実行不可能または非効率なルートを招く可能性がある。さらに、これらの特定の2.5次元制約の下で、タスク割り当て、訪問順序、およびルート実現を同時に最適化する研究はほとんど存在しない。
手法
著者らは、決定論的なルート実現レイヤーとメタヒューリスティック・スケジューリング最適化者を組み合わせた、2段階のフレームワークを提案している。
スケジューリングモデル：
- 目的関数： 総移動距離、最大累積UAV間距離（メイクスパン）、およびUAV間ルート長の標準偏差（ワークロードの均衡）を最小化する多目的関数。
- エッジコスト： ユークリッド距離の代わりに、静的な占有グラフに対するA* 探索から得られるエッジコスト（cij）を使用する。これにより、スケジューリングアルゴリズムが障害物や飛行禁止区域を回避するための水平方向の迂回を考慮することを保証する。
- 制約条件： ペイロード制限、最大ソート長、および単一デポへの帰還制約を課す。デコーダは、容量または航続範囲の限界に達するまでタスクを詰め込むことで、ソートを構成する。
ルート実現（2.5次元）：
- 水平方向： スケジュールに基づき、A*が衝突のない経路をタスク間で再構築する。
- 垂直方向： 2.5D高度モデルが高度プロファイルを割り当てる。UAVは地形上の巡航高度（Hc）を維持し、タスク地点の樹冠上空の作業高度（Hmin）まで滑らかに降下し、最大上昇角（20∘）を遵守する。
- 実現可能性チェック： 実現された3D空間距離は、スケジューリング後に計算され、UAVの航続性能制限に対して検証される。
改良型セイウチ最適化（CRWO）：
標準的なセイウチ最適化（WO）に対し、以下の3つの特定戦略を用いて改良を加えることで、NP困難な組合せスケジューリング問題を解決する。
- ランダム差分変異（Random Differential Mutation）： 歴史的な最良解とランダムな個体の差を利用して摂動を指示し、探索と開発のバランスをとる。
- レンズイメージング対向学習（Lens-Imaging Opposition-Based Learning）： 探索空間全体にわたって対称的な候補解を生成し、局所最適解からの脱出を図る。
- 離散近傍探索（Discrete Neighbourhood Search）： エリート解に適用され、タスクの再割り当てと訪問優先順位を精緻化する。
- エンコーディング： タスクのUAVへの割り当てと訪問優先順位の両方をエンコードするデュアルランダムキー表現を用い、連続的な最適化演算によって離散問題を解決する。
主な貢献
- 障害物認識型定式化： エッジコストをユークリッド距離ではなくA*を介して事前計算するスケジューリングモデルを定式化し、最適化目的が実行可能なルートコストと一致することを保証した。
- CRWOアルゴリズム： 高次元かつ制約付きのマルチUAVスケジューリングに特化して設計された改良型メタヒューリスティック（CRWO）の開発。標準的なWO、PSO、GWOなどに対して優れた性能を示す。
- 2.5D実現フレームワーク： 2Dスケジューリング探索と3Dルート実現を分離する逐次的なアプローチにより、検索空間を完全な3Dダイナミクスで複雑化させることなく、地形クリアランスと上昇角の制約を満たすスケジュールを生成する。
- 包括的な評価： 低、中、高の障害物密度における8つのアルゴリズムに対する厳格なベンチマーク、および特定のCRWOコンポーネントの寄与を分離するためのアブレーション研究。
実験結果
実験は、50個のタスクと6機のUAVを含む800m × 800mの果樹園マップを用いて行われた。
- ベースラインとの比較： 中程度の障害物シナリオにおいて、CRWOは最強のベースラインであるPSOを上回り、平均目的関数値を3.71%、最大累積UAV間空間距離を3.70%、UAV間ルート長の標準偏差を**47.62%**削減した。
- ワークロードの均衡： CRWOはすべての障害物密度において一貫して最も低いワークロード変動（標準偏差）を達成し、優れたフリート利用率を示した。
- 実現可能性： 実現されたすべてのソートは、航続性能、障害物回避、地形クリアランス（最小5.52m）、および上昇角（≤20∘）の制約を満たした。
- A* vs ユークリッド： A*エッジコストの使用は、ユークリッド・スケジューリングと比較して総移動距離を大幅には減少させなかったが、ワークロードの均衡を大幅に改善した（ペア走行においてルート長の標準偏差を50.43mから23.11mに減少させた）。
- アブレーション： 差分変異、対向学習、および離散近傍探索の組み合わせが最終的な性能を得るために必要であることを確認した。いずれかのコンポーネントを削除すると、結果が悪化した。
意義と主張
本論文は、CRWOが、障害物回避とフリートのバランスが重要となる、静的な単一デポの植物保護作業のための実用的なスケジューリング手法であることを主張している。著者らは、この手法が純粋な最短経路アルゴリズムではなく、「バランスの取れたスケジューラ」であることを強調している。その主な価値は、ワークロードを均等に分配し、最適化フェーズ中に複雑な3D結合を必要とせずに安全制約を満たすことにある。
著者らは、現在のフレームワークが静的なマップ、決定論的な需要、および均質なフリートに限定されていることを認め、控えめな範囲を設定している。彼らは、この手法がグローバルな最適解を保証するものではないことを明示しており、動的な再割り当て、ヘテロジニアス（異種混合）なフリート、および飛行条件の不確実性に対処するには将来の研究が必要であるとしている。結論として、総移動距離の利点はわずかであるが、ワークロードの均衡と安全性の遵守における大幅な改善により、CRWOが標的型の果樹保護における実行可能なソリューションとなることを示している。
毎週最高の electrical engineering 論文をお届け。
スタンフォード、ケンブリッジ、フランス科学アカデミーの研究者に信頼されています。
受信トレイを確認して登録を完了してください。
問題が発生しました。もう一度お試しください。
スパムなし、いつでも解除可能。
週刊ダイジェスト — 最新の研究をわかりやすく。登録