対象は、自律移動ロボットが稼働する配送センターにおいて、時間の異なるタイミングで到着する収集・配送タスクを複数エージェントが処理するMAPDである。各タスクには収集位置と配送位置があり、エージェントは収集位置へ移動した後、配送位置へ移動してタスクを完了する。MAPDは、エージェントへタスクの順序を割り当てる問題と、割り当てられた仕事を衝突なく実行する経路計画問題に分けて扱われる。後者はMulti-Agent Path Finding（MAPF）として研究されており、エージェント間の衝突、経路の長さ、処理完了までの時間が重要になる。
主な新規性は、MAPDのタスク割当て部分に複数の遺伝的アルゴリズムを提案し、単一目的だけでなく多目的最適化としても検討した点にある。多目的版ではNSGA-IIを用い、makespanとservice timeという二つの目的を同時に最小化する。経路計画には新規にすべてを設計し直すのではなく、Prioritized Planning（PP）とConflict Based Search（CBS）という既存手法を利用し、将来の衝突を避けるPPの変種PP-Eも評価した。さらに、目的間の関係を分析し、初期集団の生成方法や複数の遺伝的アルゴリズムの比較を通じて、割当てと経路計画の組合せを検討した。抜粋だけでは、すべての提案アルゴリズムの詳細な差分や実装上の新規演算子までは確定できない。
個体はタスクの割当てと、エージェントごとのタスク順序を表すベクトルによって解を表現する。初期集団の一部または全部をランダムに作る代わりに、現在のエージェント位置からタスクの収集位置までの推定コストを用い、最も近いエージェントとタスクを順次選ぶヒューリスティックが使われる。単一目的の遺伝的アルゴリズムとしてGA-TA、GA-E、Elitist、Steady Stateが扱われ、多目的版としてNSGA-IIに基づくNSGA-M、NSGA-ST、NSGA-Oが挙げられている。選択にはトーナメント選択が用いられ、NSGA-IIでは非優越ソートとクラウディング距離によって解を扱う。得られたタスク列をもとに、PP、CBS、または将来の衝突を考慮して目標到達後に別の空き位置へ移動するPP-Eで経路を計画する。
実験は文献で利用可能なインスタンスを用い、21×35の小規模環境と81×81の大規模環境で行われた。エージェント数、タスク数、環境規模、タスクのシステムへの到着率を変化させ、遺伝的アルゴリズムと経路計画手法の組合せを比較した。比較対象には、文献で用いられたCentralおよびTP、ならびにPP、PP-E、CBSと複数の遺伝的アルゴリズムが含まれる。評価には主としてmakespanとservice timeが使われ、計算時間が5分を超えた解は期限切れと扱われた。抜粋からは各条件の全数値、反復回数、ハードウェア、すべての統計検定結果は確認できない。
結果は、タスク割当てと経路計画を分離した構成でも、適切な組合せによって既存の比較手法を上回り得ることを示唆する。小規模環境では、PP-EとGA-TAおよび初期化ヒューリスティックの組合せが、PPの同様の組合せより全インスタンスで良く、平均改善率は0.41%だった。また、PP-EとPPはいずれもTPより良く、平均改善率はそれぞれ5.88%と5.50%と報告されている。一方、CBSは良い解を生成するが計算コストが高く、GA-TAは比較されたGA-Eより良い結果を得た。将来課題として、より現実的な環境、別の初期集団ヒューリスティック、自由になったエージェントによるタスク交換の影響が挙げられている。
倉庫や配送センターでは、オンライン商取引の拡大などを背景に、製品を移動させる自律移動ロボットの利用が進んでいる。MAPDは、時間とともに現れるタスクを複数ロボットが協調して処理する研究モデルであり、ロボットの割当てと移動の両方を扱う。関連するMAPFでは、既知の地図上で複数エージェントが互いに衝突せず目的地へ到達する必要がある。
MAPDでは、各タスクに収集位置と配送位置があり、エージェントはこの順序を守って移動しなければならない。タスク割当てが悪いと総完了時間や個々のサービス時間が増え、経路計画が悪いと衝突や解なしが生じる。提示された本文は、タスク到着が異なる時刻に発生し、システム内のタスクがなくなると問題が終了する設定を説明している。
makespanは全タスクが完了するまでの全体的な時間、service timeはタスク処理に関する別の時間指標として扱われる。PPは優先順位に従ってエージェントを順番に計画し、CBSは衝突を検出して制約を分岐させる探索法である。CBSの計算量は衝突数に対して指数的になると本文で説明されている。PP-Eは、エージェントが最終目的位置に着いた後の将来の衝突を避けるため、別の空き位置への移動を可能にする。
小規模環境では、計画手法と遺伝的アルゴリズムを変えながら、CentralとTPを含む比較が行われた。大規模環境では、GA-TA、Elitist、Steady State、NSGA-M、NSGA-ST、NSGA-Oの6手法間で比較したと抜粋に記載されている。目的間の相関を調べるため、ランダム個体と独立実行を用いた分析も行われた。利用されたすべてのパラメータや各実験の完全な構成は、提示資料だけでは確定しない。
GA-TAはGA-Eより良い結果を示したと報告されている。PP-EとPPはTPより良く、PP-Eの平均改善率は5.88%、PPは5.50%だった。PP-EとPPをGA-TAおよび初期化ヒューリスティックと組み合わせた比較では、PP-E側の平均改善率が0.41%だった。抜粋は総括的な優位性を述べるが、全インスタンスの数値や多目的手法ごとの順位を網羅していない。
遺伝的アルゴリズムによるタスク割当てと既存のMAPF経路計画を組み合わせる方法は、MAPDに対する有効な構成として提示されている。特にGA-TA、PP-E、初期化ヒューリスティックの組合せが、提示された比較では良好だった。NSGA-IIによる多目的化は、makespanだけでなくservice timeも考慮する枠組みを与える。
提示された抜粋には、実験結果の完全な表、信頼区間、再現に必要な遺伝的アルゴリズムの全パラメータが含まれていない。したがって、報告された平均改善率以外の細かな差や、どの条件でどの手法が失敗したかは確定できない。CBSの高い計算コスト、経路計画と割当てを分離することによる制約、現実のロボット形状や動的障害物をどこまで扱えるかも、抜粋だけでは評価できない。
MAPDでは、タスク割当てと衝突回避を別々に最適化すると、局所的に良い判断が全体の処理時間を悪化させる可能性がある。本研究は、遺伝的アルゴリズムで割当てを探索し、PP、PP-E、CBSで移動を実現する実用的な分解を比較した点で、倉庫ロボットの協調計画を考える基礎になる。二つの時間目的を扱うことで、全体の終了時刻と個々のサービスのバランスを検討できる。
MAPDやMAPFのタスク割当て、優先順位付き経路計画、CBS、遺伝的アルゴリズムを学びたい研究者に適している。倉庫ロボットの実運用性能を直接評価した研究、あるいは完全な再現手順や網羅的な理論解析を求める読者には、本文全体と実験データの追加確認が必要である。