従来のマルチエージェント経路探索（MAPF）は、すべてのエージェントに到達すべき目標地点が割り当てられていることを前提としている。しかし、自動倉庫のタスク待ちロボット、移動可能な荷物、駐車場の車両などの実世界では、特定の目的地を持たないエージェントが存在する。本研究は、グラフ上で目標を持つ「割り当て済みエージェント」と、目標を持たず任意の頂点へ移動可能な「未割り当てエージェント」が混在する環境における、衝突のない経路計画を対象とする。
全エージェントに目的地を強制する従来のMAPFに対し、未割り当てエージェントが道を空けるために任意に移動することを許容するMAPFUAという問題定義を導入した点に新規性がある。また、システムの処理能力、エネルギー消費、および未割り当てエージェントの移動コストという、異なる運用目的に応じた3つのコスト関数を定義した。
割り当て済みエージェントには開始地点から目標地点への経路を、未割り当てエージェントには開始地点からグラフ上の任意の頂点への経路を割り当てる。未割り当てエージェントは、その場に留まることも、他のエージェントの経路を改善するために移動することも可能である。最適化の指標として、割り当て済みエージェントの目標到達までのタイムステップの総和を最小化するSST、全エージェントの総移動回数を最小化するFuel、および移動した未割り当てエージェントの数を最小化するNUAの3種類を用いる。
本論文は問題の定義と概念の提案を主目的としており、具体的な実験データ、比較アルゴリズム、および数値的な評価結果は示されていない。
未割り当てエージェントには目的地がないため、既存のA*やCBSといったアルゴリズムでは、許容的なヒューリスティックの再設計や衝突解決メカニズムの構築が必要となる。また、エージェント数と利用可能な場所の比率が高い密な環境では、未割り当てエージェントを静的な障害物として扱うことが困難になる。今後の課題として、各コスト関数における計算複雑性の解明、計算時間と解の質のトレードオフを考慮したアルゴリズムの開発、および環境のトポロジーが与える影響の調査が挙げられる。
提供されたセクションには、著者名、所属機関、および連絡先メールアドレスのみが記載されており、研究の内容、手法、実験、結果に関する情報は含まれていません。
古典的なマルチエージェント経路探索（MAPF）は、各エージェントの開始地点から目標地点までの経路を、エージェント同士が衝突しないように見つけるタスクである。この問題は、倉庫や工場、デジタルエンターテインメント、交通制御、航空分野など、幅広い実用的な応用先を持つ。そのため、人工知能、ロボティクス、産業工学といった多様な領域の研究者から大きな関心を集めている。MAPFには、様々な設定や派生問題、コスト目的が提案されており、それらを解決するための数多くのアルゴリズムが開発されてきた。なお、この問題はNP困難であることが証明されている。
従来のMAPFは全エージェントに目標地点が割り当てられていることを前提とするが、本研究では目標を持たないエージェントが存在するMAPF with Unassigned Agents (MAPFUA) という問題を定義する。グラフ G = (V, E) 上において、特定の目標地点へ到達すべき割り当て済みエージェントの集合 A と、目標を持たない未割り当てエージェントの集合 U が存在する。割り当て済みエージェントは開始地点から目標地点までの経路を辿る必要がある一方、未割り当てエージェントは開始地点からグラフ上の任意の頂点へ移動可能であり、他のエージェントの経路を確保するために移動して道を空けることが可能である。解は、すべてのエージェントの経路が互いに衝突しない状態として定義され、未割り当てエージェントは移動せずにその場に留まることもできる。この問題設定は、タスク待ちのロボットが存在する倉庫環境や、タスク完了後に次の指示を待つLifelong MAPF、さらには移動能力を持つ荷物自体がエージェントとして振る舞う自動化倉庫などの実世界のシナリオに適用できる。
MAPFUAにおけるコスト関数は、割り当てられたエージェントを目標地点へ運ぶ従業員が、経路確保のために未割り当てのエージェントを移動させる駐車場での車両回収シナリオに基づき、3種類定義されている。1つ目のSum of Service Time (SST)は、各割り当て済みエージェントを目標地点へ移動させるために必要なタイムステップの総和であり、システムの処理能力の最大化に対応する。2つ目のFuelは、すべてのエージェントが行った移動回数の総計であり、待機時間はコストに含まれず、移動に必要なエネルギーコストの最小化に対応する。3つ目のNumber of Unassigned Agents that Move (NUA)は、経路の長さではなく、移動した未割り当てエージェントの個数を最小化することを目的とする。NUAの最小化は、未割り当て車両の所有者の不満や事故リスクの軽減、および従業員が新しい車両を操作する際の手間を減らすという観点に基づいている。
MAPFUA（割り当てられていないエージェントが存在するマルチエージェント経路探索）は、未割り当てのエージェントに特定の目的地がないという特性を持つため、既存のMAPFアルゴリズムには大幅な修正が必要となります。今後の研究課題として、まずMAPFUAの理論的な特性評価や、異なるコスト関数における計算複雑性の解明が挙げられます。アルゴリズム開発においては、A*やCBSといった既存手法をベースに、許容的なヒューリスティックの再設計や、割り当て済みエージェントと未割り当てエージェント間の衝突解決メカニズムの構築が求められます。また、実用性を考慮し、計算時間と解の質のトレードオフを行う有界劣最適アルゴリズムや、高速だが解の質に制約のない無界劣最適アルゴリズムの開発も重要です。さらに、エージェント数と利用可能な場所の総数の比率を示すalrが高い、密な環境下での動作が極めて重要となります。密な環境では未割り当てのエージェントを静的な障害物として扱うことが困難になるため、環境のトポロジーや、密な領域と疎な領域が混在する環境への対応についても研究が必要です。