trsing’s diary

勉強、読んだ本、仕事で調べたこととかのメモ。

Conflict-based searchメモ

はじめに

お仕事で群制御せななあという感じになってきたので調べてると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アルゴリズム。

問題定義

  • 入力

    • グラフ: G(V, E)
    • k個のエージェント: a_1,a_2,\dots,a_k
    • 各エージェントのスタート位置とゴール位置: start_i, goal_i

  • 出力
    エージェントが衝突せずにゴールに到着するパス(スタート位置からゴールに到着するまでの一連のアクション)

  • 制約

    • 衝突禁止。同時刻に一つの頂点に2つ以上のエージェントが存在することはできない。
    • すれ違い禁止。連続した時間ステップで2つ以上のエージェントがエッジを横切ることはできない。

  • コスト関数 今回使用するコスト関数はSum-of-costs。 各エージェントがゴールに到着して停止1するまでにかかった時間の総和。

MAPFの難しさ

探索空間が指数関数的に増加する。 1ステップでO(分岐係数^{エージェント数})。 格子型のマップ2でエージェント数が20なら5^{20}=95,367,431,640,625。1ステップでこれ。やってられっか。

CBSアルゴリズム

二つのレベル(High,Low)の処理で構成される。
HighレベルはCT(constraint tree)を探索する。衝突のないnodeが見つかったらそれをgoalとして終了。
Lowレベルは対象エージェントa_iに対するパスを生成する。

constraint tree

二分木3。各ノードは次の情報から構成される。

  • 制約集合(N.constraints):各制約は(a_i, v, t) (時刻tでエージェントa_iに頂点vにいることを禁止)または(a_i, v_1, v_2, t) (時刻tでエージェントa_iにv_1からv_2への移動を禁止。すれ違いを防ぐ)。 親ノードの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_iと制約集合を受け取り、エージェントa_iに対して制約を満たす最適パスを生成する。 エージェントa_i以外は存在しないものとして探索する。 論文では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)だわ。

  1. ゴールに居続ける。他の頂点に移動しない。↩
  2. 上下左右待機で分岐係数5↩
  3. 簡易化のため。二分木じゃなくてもいい。↩
  4. 親をたどれば制約を追えるので追加した制約のみ保持しておけばよい。↩
  5. 追加した制約の対象となるエージェントのパスのみ更新すればよい。対象でないエージェントのパスは変わらないため。↩