study-mapfMAPF / Lifelong MAPF / MAPD 教材

最小費用最大流Min-Cost Max-Flow

シミュレータで実行可解説: 原論文と照合済み

時空間ネットワークへ匿名エージェントを流し、到達時刻と移動距離を最適化する。

概要

Min-Cost Max-Flow（MCMF）は、グラフ上の複数の供給点から需要点へ、容量制約を守りながら最大量の flow を送り、その中で総費用が最小のものを求めます。MAPF では cell を時刻ごとに複製した time-expanded network に変換します[network-flow-mapf-2012, §II.A, p.4]。

まず何がうれしいのか

同じチームの agent は goal の交換が可能です。個体ごとに path を固定せず、start の flow と target の flow をまとめて扱えるので、匿名 MAPF の割当を別に列挙せずに済みます。

前提となる知識

最大流、残余グラフ、augmenting path、vertex capacity、TAPF のチームモデルを使います。

対象問題

サイト版は 4 近傍、離散時間、move / wait、vertex conflict 禁止、edge-swap 禁止を使う 1 チーム TAPF です。CBM ではチームごとの low-level として呼びます。複数チームを 1 本の単一 commodity flow に混ぜることはしません。

中心となるアイデア

時刻 t の cell を in(t) と out(t) に分け、容量 1 の辺でつなぎます。これが vertex occupancy を表します。out(t) から隣接 cell の in(t+1) へ move 辺、同じ cell へ wait 辺を張り、start から source、target から sink へつなぎます。

アルゴリズムの手順

  1. horizon 分の時空間ノードを作る。
  2. start ごとに source 辺、target ごとに sink 辺を張る。
  3. 残余グラフで最短 augmenting path を繰り返す。
  4. flow が agent 数に達したら、使用辺を path へ復元する。
  5. サイト版 Solver は horizon を下界から増やし、最初に flow が通った値を makespan とする。

小さな例

2 体の start と 2 個の target が横一列にあるとします。各 target を別々の sink 辺にすることで、どちらの agent がどちらへ行くかを flow 自身が決めます。中央 cell の容量 1 により同時占有は起きません。

データ構造

疑似コード

for horizon = lowerBound, lowerBound + 1, ...:
  G ← buildTimeExpandedNetwork(horizon)
  (flow, cost) ← successiveShortestAugmentingPath(G, source, sink)
  if flow == numberOfAgents:
    return reconstruct(flow)
return failure

この短い形は network-flow-mapf-2012 の time-expanded network と、min-cost maximum flow の定義をサイト用に再構成したものです[network-flow-mapf-2012, §II.A, p.4][network-flow-mapf-2012, §V, p.9]。

実装上の注意

flow は匿名なので、復元時に start 辺から時刻順へ辿って agent ID を戻します。MCMF の費用最小と makespan 最小は同じ目的ではありません。サイト版は horizon を外側で最小化し、その horizon で move cost を最小化します。

よくある誤解

他手法との比較

CBM は MCMF をチームごとの low-level として使い、チーム間 conflict を high-level CBS で解消します。CBS-TA は assignment matrix と SOC を扱い、MCMF だけでは表さない割当制約を持ちます。

サイト上の実装との差異

論文の一般 network-flow 定式化を、ブラウザの有限 horizon と 4 近傍 grid に限定しています。残余最短路は Bellman–Ford、同値辺はノード番号順です。library 部品ではなく、単一チーム形状に限った Solver として実行できます。

実験してみる

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

理論保証。原論文で確認できた記述だけを載せています。 「不明」は「保証が無い」ではなく「原論文で未確認」の意味です。
完全性条件付き
最適性条件付き（eventually optimal 等。根拠欄を参照）
対象ネットワークフロー / TAPF

適用範囲の注意: 時空間グラフ上のフローとして MAPF（特に匿名エージェント版）を定式化する。CBM の低レベルがこれ。flow アルゴリズム自体の原典（Ford-Fulkerson 等）は未調査のまま。network-flow-mapf-2012 p.9 の条件付き保証だけを記録し、原典を推測していない。

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

network-flow-mapf-2012 p.9 Corollary 23（time-expanded network で Objective 21 の optimal solution が存在）/ p.9 Corollary 25（minimum cost maximum flow で Objective 24 の optimal solution が存在）。適用条件は permutation-invariant MAPF と十分な time horizon。

原論文

確認済みの箇所

公開実装

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

最終照合日: