はじめに
お仕事で群制御せななあという感じになってきたので調べてるとMAPFという分野(?)がそれっぽく、 この分野ではCBSを知ってて当然みたいな感触。 のわりに日本語での解説を見つけられなかったので元の論文(多分)を読んだ。
元論文
https://www.sciencedirect.com/science/article/pii/S0004370214001386
CBSだけじゃなくてMAPFの難しさや先行事例についてもざっと説明してくれてるでとてもありがたかった。
今回のメモには書かないけどCBSで最適解が得られることの証明やCBSの欠点とその緩和方法(MA-CBS)についても書いてる。ありがたや。
前提知識
ヒューリスティック探索の基礎(?)。次の資料によくまとまってる。日本語。うれしい。
https://jinnaiyuu.github.io/pdf/textbook.pdf
MAPFについて
multi-agent pathfinding。 複数のエージェントが衝突せずにそれぞれのゴールに到達するまでのパスを求める。 CBSは最適MAPFアルゴリズム。
問題定義
入力
- グラフ:
- k個のエージェント:
- 各エージェントのスタート位置とゴール位置:
出力
エージェントが衝突せずにゴールに到着するパス(スタート位置からゴールに到着するまでの一連のアクション)制約
- 衝突禁止。同時刻に一つの頂点に2つ以上のエージェントが存在することはできない。
- すれ違い禁止。連続した時間ステップで2つ以上のエージェントがエッジを横切ることはできない。
コスト関数 今回使用するコスト関数はSum-of-costs。 各エージェントがゴールに到着して停止1するまでにかかった時間の総和。
MAPFの難しさ
探索空間が指数関数的に増加する。 1ステップで。 格子型のマップ2でエージェント数が20なら。1ステップでこれ。やってられっか。
CBSアルゴリズム
二つのレベル(High,Low)の処理で構成される。
HighレベルはCT(constraint tree)を探索する。衝突のないnodeが見つかったらそれをgoalとして終了。
Lowレベルは対象エージェントに対するパスを生成する。
constraint tree
二分木3。各ノードは次の情報から構成される。
- 制約集合(N.constraints):各制約は (時刻でエージェントに頂点にいることを禁止)または (時刻tでエージェントにからへの移動を禁止。すれ違いを防ぐ)。 親ノードのconstraintsに制約を一つ加えたものを持つ。4
- 解(N.solution):それぞれのエージェントに対するパス。 パスは制約(N.constraints)を満たす。5
- 総コスト(N.cost):解(N.solution)のコスト。それぞれのパスのコストの総和。ノードのf-value(論文の1.や3.3.1.参照)。
Highレベル
CTに対し、最良優先探索を行う。評価基準はコスト(N.cost)。コストが同じ場合は衝突が少ない方を優先する。 解(N.solution)を検証し、衝突がある場合は衝突を防ぐ制約を追加した子ノードを生成し処理を続ける。 衝突がない場合はノードNをgoalとし処理を終了する。
Lowレベル
対象エージェントと制約集合を受け取り、エージェントに対して制約を満たす最適パスを生成する。 エージェント以外は存在しないものとして探索する。 論文ではA*を使用しているがsingle-agent pathfindingアルゴリズムを使用できる。
疑似コード
python風。
root = Node() root.constraints = 空集合 # 制約なし root.solution = 各エージェントのパス # 制約なしでlow level処理したもの root.cost = root.solutionのコスト open.put(root) while not open.empty(): node = openリスト中の一番コスト低いやつ conflicts = node.solutionを検証 # 衝突(a_i,a_j,v,t)のリストを得られるとする if 衝突無し: # 衝突がないのでgoal return node.solution conflict = conflictsの最初の衝突 for agent in conflict: # a_i, a_jに制約を加えた子ノードを作る child = Node() child.constraints = node.constraintsに(agent, v, t)を加えたもの child.solution = node.solution child.solution[agent] = agentのパスを更新 # agentについて制約child.constraintsでlow level処理したもの child.cost = child.solutionのコスト if 解あり: open.put(child)
その他
お仕事の要件に近いのMAPD(Multi-Agent Pickup and Delivery)だわ。