本研究は、オフラインで計算されたMAPFの計画コスト（Sum of Costs; SoC）が、物理ロボットの実行時における実時間（wall-clock completion time）を正確に予測できない問題を扱う。実行時には、エージェント間の先行制約、狭い空間での競合、および実行モニタによる停止・再開の遅延といった要因が、スカラー値であるSoCでは捉えきれない構造的な実行時間の差異を生じさせる。著者らは、実行時間を予測するための記述子を、(i) 標準的な $\text{SoC}$、(ii) 旋回数や停止・開始回数を含む $\text{primitive motion burden}$、(iii) ロボット間の先行制約数を含む $\text{interaction-aware plan structure}$ の3層に分解して定義した。
本研究の主な貢献は、物理ハードウェアを用いた大規模なコーパスにより、SoCを超える実行時間の予測信号を特定した点にある。具体的には、$\text{primitive motion burden}$ を導入することで、未知のシナリオに対する評価において、$\text{SoC}$ のみのモデルと比較して平均絶対誤差（MAE）を $2.76\,\text{s}$ から $1.42\,\text{s}$ へと大幅に削減できることを示した。また、$\text{interaction-aware plan structure}$ も予測精度の向上に寄与することを確認し、実行時間の乖離の多くがオフライン計画の段階で可視化可能であることを明らかにした。これにより、実行前に候補計画をスクリーニングするための新たな評価指標の指針を提示している。
7台のPololu 3Pi+ロボットを用い、Empty、Medium-Random、Bottleneckの3種（計15シナリオ）からなるライブラリで実験を行った。各シナリオに対し、CBSH2-RTC、EECBS、LaCAM3を用いて計8種類の計画を生成し、計480回の実行結果を含むハードウェア・コーパスを構築した。予測モデルは「Feature Ladder」として構成され、$\text{SoC}$ のみの $M_0$ から、基本動作負荷を加えた $M_2$、さらにAction Dependency Graph (ADG) から得られる相互作用負荷を加えた $M_3$ へと段階的に拡張される。評価には、シナリオ間の相関を防ぐ「5-fold family-balanced scenario split」を採用し、リッジ回帰モデルおよび試行レベルの変動を考慮する混合効果モデル（mixed-effects model）を用いて解析を行った。
480試行のコーパスを用いた検証の結果、$\text{SoC}$ のみのモデルでは予測精度が不十分であることが示された。最も顕著な精度向上は $\text{primitive motion burden}$ を導入した $M_2$ 階層で確認され、リッジ回帰では $MAE$ が約 $15\%$ 減少、混合効果モデルでは $MAE$ が約 $24\%$ 減少するという大幅な改善が確認された。また、$\text{interaction-aware structure}$ を追加した $M_3$ 階層においても、混合効果モデルにおいて $MAE$ が減少するなど、一貫した改善の方向性が示された。全体として、$\text{primitive motion burden}$ が $\text{SoC}$ と実測時間の乖離を埋める最も強力で信頼性の高い予測因子であることが実証された。
提案された記述子はオフライン計画から計算可能であり、同一プラットフォームにおける計画選定に活用できるが、予測値はプラットフォームや実行器に依存するため、大規模フリートへの適用には別途検証が必要である。本研究の限界として、実験環境が7台のロボットと単一の先行関係遵守型エグゼキュータに限定されており、検証された15のシナリオも広範なベンチマークとしては不十分である点が挙げられる。また、採用されたモデルは予測性能の理論的上限ではなく、特徴量の性質を検証するための解釈性を重視して設計されている。結論として、実行を意識したMAPFの評価においては、SoCのみに依存せず、プリミティブな運動記述子を考慮すべきであることが示唆された。
本研究は、Multi-Agent Path Finding (MAPF) において、従来の評価指標である Sum of Costs (SoC) や makespan が実際の実行時間（wall-clock completion time）を十分に予測できない問題を解決するため、CADENCE (Coordination- and Action-Driven Estimation for Networked Continuous Execution) という手法を提案している。7台の差動駆動ロボットを用いた実機環境において、15のシナリオ（Empty, Medium-Random, Bottleneck）から生成された120の計画を計480回実行したハードウェア・コーパスを用い、実行前に取得可能な特徴量から実行時間を予測する実験を行った。評価には、SoCに加えて、makespanや旋回数、停止・再始動回数などの「primitive motion burden」と、依存関係の深さや相互作用するロボットのペア数などの「interaction-aware coordination structure」を比較対象としている。シナリオ・ホールドアウトによるリッジ回帰モデルおよび試行レベルの混合効果モデルを用いた解析の結果、SoCのみのモデルと比較して、primitive motion burden を導入することで、MAE（平均絶対誤差）で約48.6%–59.8%、RMSE（平方根平均二乗誤差）で約44.2%–61.4%の誤差削減が確認された。結論として、interaction-aware な特徴量よりも primitive motion burden が最も信頼性の高い予測信号であり、実行時間の乖離の多くはロボットが動き出す前のオフライン計画の段階で可視化されていることが示された。
本研究は、オフラインで計算されたMAPF（Multi-Agent Path Finding）の計画コスト（Sum of Costs; SoC）が、物理的なロボット実行時の実時間（wall-clock completion time）を必ずしも正確に予測できない問題に着目している。実行時には、エージェントの行動順序の維持、ロボット間の先行制約、狭い空間での競合、および実行モニタによる停止・再開の遅延といった要因が、スカラー値であるSoCでは捉えきれない構造的な実行時間の差異を生じさせる。著者らは、実行時間を予測するための記述子を、(i) 標準的な計画品質を示す $\text{SoC}$、(ii) 回転数や連続移動、停止・開始回数を含む $\text{primitive motion burden}$、(iii) ロボット間の先行制約数や混雑への露出度を含む $\text{interaction-aware plan structure}$ の3層に分解して定義した。Pololu 3Pi+を用いた実機実験とOptitrackによる計測に基づき、4つのモデルを用いた検証を行った結果、未知のシナリオに対する評価において、$\text{primitive motion burden}$ を導入することで、$\text{SoC}$ のみの場合と比較して平均絶対誤差（MAE）を $2.76\,\text{s}$ から $1.42\,\text{s}$ へと大幅に削減できることを示した。さらに、$\text{interaction-aware plan structure}$ も $\text{primitive motion burden}$ に加えて、一貫した予測精度の向上に寄与することが確認された。
従来のMAPF評価は、Sum of Costs (SoC) や計画された makespan、プランナの実行時間といったプラン中心の指標に依存しており、これらは探索アルゴリズムの比較には適しているが、物理ロボット上での実際の実行時間（realized execution time）を予測するには不十分である。CBS などの最適解を求めるソルバであっても、ロボットの運動特性や先行制約、ロボット間の相互作用構造を考慮すると、コストの最小化が必ずしも実行時間の最小化に直結しない。本研究は、シミュレーションではなく物理ハードウェアを用いて、SoC 以外のプラン記述子が実行完了時間（wall-clock completion time）の予測に寄与するかを検証する点で既存研究と異なる。具体的には、不足している予測信号を「原始的な運動負荷（primitive motion burden）」と「相互作用を考慮した調整構造（interaction-aware coordination structure）」に分解し、シナリオを保持した検証（scenario-held-out validation）を通じて、これらが SoC を超えて予測価値を持つかを評価する。
本研究では、7台の差動駆動型Pololu 3Pi+ロボットを用いた固定ワークセルにおいて、計画の品質（Sum of Costs; SoC）ではなく、実行システムにおける実測の総完了時間（wall-clock completion time）を予測対象としている。シナリオライブラリは、障害物のない「Empty」、中程度の経路制約を持つ「Medium-Random」、および狭い通路に依存性が集中する「Bottleneck」の3つのファミリーからなる計15のシナリオで構成され、各シナリオの実現可能性はCBSH2-RTCを用いて検証されている。各シナリオに対し、CBSH2-RTCによる最適参照計画1件、複数の重み設定を用いたEECBSによる限定的劣最適計画4件、およびシードを変えたLaCAM3による計画3件の計8種類の計画を生成する。この設計により、計画生成器のメニューによってコストと構造的なバリエーションを誘発しつつ、単一の実行結果ではなく計画レベルの平均実行時間を予測対象とすることで、SoCのみを用いる場合と比較して、より豊かな計画記述子が実測時間をどの程度説明できるかを評価する。
本研究では、MAPF（Multi-Agent Path Finding）の計画から実際の実行時間を予測するため、依存関係を遵守する連続型エグゼキュータを用いたハードウェア実験系を構築している。予測モデルは、計画のみから抽出された特徴量を用いる「Feature Ladder」として構成されており、$\text{SoC}$（Sum of Costs）のみのModel 1から、回転数や停止回数などの基本動作負荷を加えたModel 2、さらにAction Dependency Graph (ADG) から得られる相互作用負荷（依存エッジ数、最大依存鎖の深さ、混雑露出度など）を加えたModel 3へと段階的に拡張される。評価指標には $\text{MAE}$ および $\text{RMSE}$ が用いられ、予測対象は実測の壁時計時間（wall-clock time）である。実験設定では、シナリオ間の相関によるリークを防ぐため、同一シナリオに属する全ての計画と試行を同一の分割に保持する「5-fold family-balanced scenario split」を採用している。推定器には、計画平均値に適合させるRidge回帰モデルと、試行レベルの変動を考慮する混合効果モデル（mixed-effects model）の2種類が用いられ、各モデルの性能はシナリオ単位で検証される。
本セクションでは、480試行のハードウェア・コーパスを用い、リッジ回帰モデルと混合効果モデルの2種類を用いて、特徴量階層（$M_0$から$M_3$）による実行時間の予測性能を評価している。実験の結果、Sum of Costs ($SoC$) のみのモデルでは予測精度が不十分であることが示され、特に混合効果モデルにおいて $SoC$ のみの $MAE$ は $s$、$RMSE$ は $s$ と、ヌル・ベースラインに近い値にとどまった。最も顕著な精度向上は、原始的な動作負荷（primitive-motion burden）を導入した $M_2$ 階層で確認され、リッジ回帰では $MAE$ が $s$ から $s$ へ（約 $15\%$ 減少）、混合効果モデルでは $MAE$ が $s$ から $s$ へ（約 $24\%$ 減少）と大幅に改善し、その統計的有意性も示された。さらに、相互作用を考慮した構造（interaction-aware structure）を追加した $M_3$ 階層では、リッジ回帰では信頼区間がゼロを跨ぐものの、混合効果モデルでは $MAE$ が $s$ から $s$ へ減少するなど、方向性として一貫した改善が見られた。結論として、原始的な動作負荷は $SoC$ と実際の実行時間の間を埋める強力な予測因子であるが、相互作用に関する特徴量の正確な寄与度を確定するには、現在のコーパスでは情報量が不足しており、より大規模なシナリオによる検証が必要である。
CADENCEで提案された記述子は、ロボットが移動を開始する前のオフライン計画から計算可能であり、従来のSum of Costs (SoC) よりも実際の実行時間に近い指標として、同一プラットフォーム・実行器における候補計画の選定やスクリーニングに活用できる。しかし、本手法の予測値はプラットフォームや実行器に依存しており、より大規模なフリートや異なる実行ポリシーへのスケール転送には、別途ハードウェアによる検証が必要となる。本研究の限界として、実験は7台のロボットと単一の先行関係を遵守する連続実行器という限定的な環境下で行われており、検証された15のシナリオ（Empty, Medium-Random, Bottleneck）も広範なベンチマークとしては不十分である。また、計画生成メニューを8スロットに固定したコーパス設計は再現性を高める一方で、あらゆるMAPFタスクやソルバーを代表するものではない。さらに、採用されたリッジ回帰や混合効果モデルは、予測性能の理論的上限を追求するものではなく、特徴量群の性質を検証するための解釈性を重視した設計となっている。
本研究は、標準的なMAPFの計画品質（SoC）だけでは、物理的なマルチロボット・ワークセルにおける実際の実行時間を予測するには不十分であり、実行前に計画側の追加的な構造情報を考慮する必要があることを結論付けている。7台のロボットを用いたハードウェアプラットフォームによる検証の結果、SoCは重要な傾向を示すものの、実時間（wall-clock completion time）を完全には説明できないことが明らかになった。最も顕著な追加信号は「プリミティブな運動負荷（primitive motion burden）」であり、計画側のmakespan、旋回（turns）、連続移動（consecutive moves）、および開始・停止の遷移（start–stop transitions）をSoCに加えることで、リッジ回帰モデルではMAEが $s$ から $s$ へ、混合効果モデルでは $s$ から $s$ へと、最も大きく信頼性の高い改善が見られた。また、相互作用を考慮した調整構造（Interaction-aware coordination structure）も実行信号のさらなる層を示唆しており、両方の解析において点推定値を改善させたが、現在のハードウェア・コーパスではその信頼性や大きさは確定していない。以上の結果から、実行を意識したMAPFの評価においてはSoCのみに依存すべきではなく、ロボットが動き出す前のプリミティブな運動記述子が、欠落している実行時間の信号の多くを捉えることができるという設計上の示唆が得られた。