エージェント集合 $\mathcal{A}$ の各個体が、無向グラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ 上で割り当てられたタスク集合 $\mathcal{T}_i$ を順次訪問し、最終目標 $g_i$ に到達する経路を決定する問題を扱う。この問題は、タスクの順序決定とマルチエージェント経路計画（MAPF）が統合されているため、探索空間が指数関数的に増大する。従来のMAPF手法では、高密度な環境においてスケーラビリティが不足したり、構成ベースの手法では不完全性によりデッドロックを回避できず解を見つけられない困難がある。
既存の構成ベース手法であるCTS-PIBTの不完全性を克服するため、停滞したエージェントを特定して完全性のあるMAPFソルバーで局所的に再計画を行うロック検出・解放メカニズムを導入した点が新規である。また、解の品質を継続的に向上させるために、大近傍探索（LNS）に基づくanytimeな洗練プロセスを組み込んだ。これにより、従来の構成ベース手法の計算効率を維持しながら、高密度環境での成功率と解の品質（flowtime）を大幅に向上させている。
まず二段階の手順でタスクシーケンスを生成し、Extended-PIBTを用いて経路を計算する。解が実行不能な場合、未完了タスクを持つエージェントと動きを阻害するゴール到達済みのエージェントからなる集合 $\mathcal{L}$ を特定し、停滞開始時刻 $t_{\text{lock}} = \min_{a \in \mathcal{L}} t_a$ を算出する。解放フェーズでは、時刻 $t_{\text{lock}}$ における $\mathcal{L}$ の構成を初期状態とし、LaCAMを用いて局所的なMAPF問題を解くことでデッドロックを回避する。さらに、LNSを用いて、ランダム、交差ベース、ランダムウォークの3種類の近傍選択戦略を指数移動平均 $w_i \leftarrow (1-\alpha)w_i + \alpha \cdot \mathbb{I}(\text{cost improvement} > 0)$ で適応的に重み付けしながら、破壊と再構築を繰り返すことで総フロータイムを削減する。
疎な環境（sparse）と迷路状の高密度環境（dense）のベンチマークを用い、成功率、実行時間、flowtimeを評価指標として比較した。sparse設定では、CTS-CBSやCBSSよりも高い成功率を示し、CTS-PIBTと比較してflowtimeを平均10.4%改善した。dense設定のアブレーション研究では、ロック検出・解放モジュールによりCTS-PIBTの成功率を28.95%から89.47%向上させ、LNSによりCTS-PIBT-anytimeと比較してflowtimeを1.25%から17.49%短縮した。実機ロボットを用いた実験でも、ライブロックを回避し全エージェントがタスクを完遂できることが確認された。
本研究は、構成ベースの効率性と完全性のあるソルバーの堅牢性を組み合わせているが、今後の課題として、より大規模なエージェントおよびタスクシステムへの拡張が挙げられる。また、意思決定を加速させるための学習ベースのヒューリスティックの導入や、動的な環境または不確実性を伴う環境への対応についても検討が必要である。
本研究では、エージェントが衝突を回避しながら一連のタスクを完了させる、組合せ爆発の困難を伴う協調的タスクシーケンシングおよびマルチエージェント経路計画（CTS-MAPF）問題に対し、階層的なフレームワークであるCTS-PLLを提案している。この手法は、構成ベースのCTS-MAPF計画パラダイムを拡張したものであり、密な環境下での堅牢性を確保するために、完全な計画手法を用いたエージェントのロック検知および解放メカニズムを導入している。さらに、解の品質を継続的に向上させるため、大近傍探索（LNS）に基づく anytime な洗練プロセスを備えている。疎および密なベンチマークを用いた広範な評価の結果、CTS-PLLは既存手法と比較して、競争力のある実行効率を維持しつつ、より高い成功率と解の品質を達成することが示された。また、実ロボットを用いた実験により、提案手法の実用的な実現可能性も実証されている。
Collaborative Task Sequencing and Multi-Agent Path Finding (CTS-MAPF)は、エージェントが衝突を回避しながら、一連のタスクを順序立てて実行し、最終的に指定されたゴールに到達する問題を扱う。この問題は、組合せ論的なタスク順序の決定とマルチエージェント経路計画（MAPF）を統合するため、探索空間が指数関数的に増大し、従来のMAPFよりも解決が困難である。既存手法として、最適性や限定的な劣最適性を保証するConflict-Based Search (CBS) 系の手法があるが、高密度な環境ではスケーラビリティに課題があり、一方でCTS-PIBTのような構成ベースの手法は効率的だが、不完全性や解の改善能力の欠如という限界を持つ。本研究では、CTS-PIBTを拡張した新しいCTS-MAPFソルバーを提案し、停滞したエージェントを特定して完全性のあるMAPFソルバーで局所的な再計画を行う「ロックエージェント検出・解放メカニズム」を導入することで、効率を維持しつつ堅牢性を向上させている。さらに、Large Neighborhood Search (LNS) に基づく洗練手続きを各計画サイクルに組み込んだ anytime メカニズムを導入することで、計算時間の経過とともに解の品質を継続的に改善することが可能である。
CTS-MAPF問題は、無向グラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ 上で、エージェント集合 $\mathcal{A}$ の各エージェントが初期位置 $s_i$ から、割り当てられたタスク集合 $\mathcal{T}_i$（特定の頂点を訪問するタスク）を順次完了し、最終目標 $g_i$ に到達する経路 $\pi_i = (v_{i,0}, v_{i,1}, \dots, v_{i,T})$ を決定する問題である。解の制約として、任意の時刻 $t$ において、同一頂点に複数のエージェントが存在する頂点衝突 $v_{i,t} = v_{j,t}$ および、隣接する頂点間を入れ替わるエッジ衝突 $\{v_{i,t}, v_{i,t+1}\} = \{v_{j,t+1}, v_{j,t}\}$ の両方を禁止する必要がある。既存手法であるCTS-PIBTは、タスクシーケンス生成と、優先度継承を用いた再帰的バックトラッキングを行うExtended-PIBTによる経路計画を組み合わせた階層的フレームワークである。Extended-PIBTは、各時刻において優先度の高いエージェントから順に、衝突を回避しつつ次の未訪問タスクまたは目標へ向かう移動を選択するが、局所的な衝突がデッドロックやライブロックに発展した場合、解を見つけられない可能性がある。本研究では、これらの課題を解決するために、デッドロックやライブロックに陥ったエージェントを検出しLaCAMに基づく局所的な再計画を行うモジュールと、LNS（Large Neighborhood Search）を用いて解の質を継続的に改善するAnytimeフレームワークを導入している。
CTS-PLLは、共同タスクシーケンシングとマルチエージェント経路探索（MAPF）を統合した、堅牢かつAnytimeなフレームワークである。本手法は、まず二段階の手順でタスクシーケンスを生成し、各シーケンスに対してExtended-PIBTを用いて経路を計算するが、解が実行不能な場合はロック検出および解放モジュールを起動する。ロック検出では、未完了のタスクを持つエージェントと、それらの動きを阻害しているゴール到達済みのエージェントからなる集合 $\mathcal{L}$ を特定し、各エージェント $a \in \mathcal{L}$ が最後にタスクを完了した時刻 $t_a$ の最小値 $t_{\text{lock}} = \min_{a \in \mathcal{L}} t_a$ を用いて、停滞が始まる時刻を特定する。解放フェーズでは、時刻 $t_{\text{lock}}$ における $\mathcal{L}$ の構成を初期状態とし、エージェントの配置をランダムに置換した目標構成をターゲットとしてLaCAMを適用することで、局所的なMAPF問題を解き、デッドロックを回避する。さらに、得られた実行可能な解の品質を向上させるため、Large Neighborhood Search（LNS）による改善プロセスを導入している。LNSでは、ランダム、交差ベース、ランダムウォークの3種類の近傍選択戦略を用い、各戦略の有効性を指数移動平均 $w_i \leftarrow (1-\alpha)w_i + \alpha \cdot \mathbb{I}(\text{cost improvement} > 0)$ によって適応的に重み付けしながら、破壊と再構築（優先度付き計画法による再計画）を繰り返すことで、総フロータイムの削減を図る。
本研究では、シミュレーションおよび実機ロボットを用いた実験により、提案手法であるCTS-PLLの有効性を検証している。実験は、エージェント密度が低い「sparse」設定と、mazeマップを用いた高密度な「dense」設定の2つのシナリオで行われ、成功率、実行時間、および解の品質（flowtime）を評価指標としている。CTS-PLLには、ロック検出・解放モジュールのみを持つCTS-PLL-v1、早期終了型でLNS最適化を含まないCTS-PLL-v2、およびLNSによる継続的な改善を行う完全なanytime版であるCTS-PLL-v3の3つのバリアントが存在する。sparse設定において、CTS-PLLはCTS-CBSやCBSSといった探索ベースの手法よりも高い成功率を示し、CTS-PIBTと同等の計算効率を維持しつつ、LNSの導入によりflowtimeを大幅に改善することを確認した。dense設定におけるアブレーション研究では、CTS-PLL-v1がCTS-PIBTに対してタスク数に応じて28.95%から89.47%の成功率向上を実現し、さらにCTS-PLL-v3はLNSモジュールの効果により、CTS-PIBT-anytimeと比較してflowtimeを1.25%から17.49%短縮できることが示された。実機を用いたtoioロボットによる実験では、優先度ベースの計画では解決できないエージェント間のライブロックが発生した際、提案手法がLaCAMに基づく局所的な再計画によってこれを回避し、全エージェントがタスクを完遂できることを実証した。
本研究では、構成ベースの探索に堅牢性と解の洗練メカニズムを統合した、CTS-MAPF問題を解決するためのフレームワークであるCTS-PLLを提案している。本手法は、ロック検出とLaCAMに基づく局所的な再計画を組み合わせることで、CTS-PIBTが直面する失敗事例を効果的に克服しており、さらにAnytime LNSによる解の洗練を用いることで、高密度かつ混雑した環境における経路品質を向上させている。実験の結果、疎な環境においてCTS-PLLは成功率100%を達成し、CBSSやCTS-CBSを大きく上回るとともに、CTS-PIBTと比較して解の品質を平均10.4%改善した。また、高密度なシナリオにおけるアブレーション実験や実機ロボットを用いた検証を通じて、提案手法が実現可能性と効率性の両面で優れていること、および実環境への適用が可能であることが示された。今後の展望として、より大規模なエージェント・タスクシステムへの拡張、意思決定を加速させるための学習ベースのヒューリスティックの導入、および動的または不確実な環境への対応が挙げられている。