RMCARMCA
シミュレータで実行可解説: 原論文と照合済み
容量制約を持つ agent の task assignment と path planning を同時に扱う MAPD 手法。
概要
RMCA は agent が複数 task を同時に運べる容量制約を導入し、割当と path planning を同時に更新します。従来手法が capacity 1 を仮定することとの差が出発点です[rmca-ral-2021, §Problem Formulation, p.2]。
まず何がうれしいのか
pickup のたびに delivery へ戻る必要がないため、近い task をまとめて運べます。割当の marginal cost を実際の path planning に反映できます。
中心となるアイデア
potential assignment heap を作り、regret の大きい task から sequence へ挿入します。経路は pickup / delivery の順序を守り、容量と vertex / edge-swap conflict を同時に検査します[rmca-ral-2021, Algorithm 1, p.4]。
目的関数
RMCA が最小化するのは average service time ではなく total travel delay (TTD) です[rmca-ral-2021, §Formula Definition As An Optimisation Problem, p.3]。サイトの objective は total-travel-delay、service time は別の表示指標です。
実装上の注意
AgentSpec.capacity の既定値は 1 で、既存 MAPD と互換です。TaskSpec.goals を指定すると複数 goal を順に訪れます。regret insertion は単体 Solver ではなく RMCA 内部の純関数です。
実験してみる
MAPD: capacity 2 と容量を 1 にしたコピーを比較し、total travel delay、capacity、平均 service time を別々に確認してください。
完全性・最適性などの保証
| 完全性 | 不明 |
|---|---|
| 最適性 | 不明 |
| 対象 | MAPD |
適用範囲の注意: 1 エージェントが複数タスクを同時に運べる容量制約付き MAPD。regret ベースの割当と経路計画を統合。サイト版は教育用で、目的は service time ではなく TTD。PDF で完全性・最適性を保証する定理を確認できなかったため guarantees は unknown。公開実装は未特定。
保証の根拠（原論文の記述）
rmca-ral-2021 PDF pp.1–4（Problem Formulation、式 (1)、Algorithm 1–2）を確認したが、RMCA の完全性・最適性を述べる保証定理・補題は確認できなかった。p.3 の TTD は目的関数の定義であり、保証ではない。
原論文
公開実装
対応する公開実装は、まだマニフェストへ登録されていません。