Regret 挿入法Regret insertion

内部実装あり（単体では実行不可）解説: 原論文と照合済み

RMCA の task sequence を作る内部割当ヒューリスティクス。

概要

Regret 挿入法は、task を最良の agent へ入れた場合と次善の agent へ入れた場合の差（regret）が大きい task から sequence へ挿入するヒューリスティクスです。RMCA は regret-based marginal-cost heuristic を使います[rmca-ral-2021, §Task Assignment Framework, p.4]。

サイト上の実装

src/lib/assignment/regret-insertion.ts の純関数として実装し、RMCA から呼び出します。単体 Solver ではないため、シミュレータの Solver 一覧には出ません。

完全性・最適性などの保証

理論保証。**原論文で確認できた記述だけ**を載せています。「不明」は「保証が無い」ではなく「原論文で未確認」の意味です。
完全性	不明
最適性	不明
対象	MAPD

適用範囲の注意: RMCA の内部部品として src/lib/assignment/regret-insertion.ts に実装。単体 Solver ではない。rmca-ral-2021 は regret-based marginal-cost heuristic を用いるが、古典的 regret insertion の原典までは本プロジェクトで確認していない。

保証の根拠（原論文の記述）

rmca-ral-2021 PDF pp.3–4（式 (1)、Algorithm 1–2）の regret-based marginal-cost ordering を確認したが、regret insertion 固有の完全性・最適性・準最適性を述べる定理・補題は確認できなかった。

原論文

Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and Delivery
Zhe Chen, Javier Alonso-Mora, Xiaoshan Bai ほか (2021) Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and Delivery. IEEE Robotics and Automation Letters, vol. 6, no. 3
DOI再配布可

公開実装

対応する公開実装は、まだマニフェストへ登録されていません。

最終照合日: 2026-08-02