MAPFにおける衝突回避の数理モデル

はじめに

マルチエージェント経路計画（MAPF: Multi-Agent Path Finding）は、複数のロボットが互いに衝突せずに目的地へ到達する経路を求める問題です。

倉庫ロボットの台数が増えるほど、デッドロックやライブロックのリスクが高まります。本記事では、MAPFにおける衝突の数学的定義と、最適化の目的関数を解説します。

衝突の定義

MAPF では2種類の衝突を考えます。

頂点衝突（Vertex Conflict）

2つのエージェント $a_i$ と $a_j$ が同時刻 $t$ に同じノード $v$ を占有する場合：

\text{conflict}_v(a_i, a_j, t) \iff \pi_i(t) = \pi_j(t) = v

ここで $\pi_i(t)$ はエージェント $a_i$ の時刻 $t$ における位置を表します。

辺衝突（Edge Conflict）

2つのエージェントが同時刻に同じ辺を反対方向に通過する場合：

\text{conflict}_e(a_i, a_j, t) \iff \pi_i(t) = \pi_j(t+1) \land \pi_i(t+1) = \pi_j(t)

最適化目的関数

MAPF の一般的な最適化目的は2つあります。

Makespan の最小化

全エージェントが目的地に到達する最遅時刻を最小化：

\min \max_{i \in \{1, \ldots, k\}} |\pi_i|

Sum-of-Costs の最小化

全エージェントの経路コスト合計を最小化：

\min \sum_{i=1}^{k} |\pi_i|

目的関数	特徴	適用場面
Makespan	最遅到着を最小化	スループット重視
Sum-of-Costs	総移動量を最小化	エネルギー効率重視

CBSアルゴリズム

Conflict-Based Search (CBS) は MAPF の代表的なアルゴリズムです。

cbs_pseudocode.py

def cbs(agents, graph):
    root = CTNode(constraints=[], solution=find_individual_paths(agents))
    open_list = [root]
    while open_list:
        node = open_list.pop(0)  # lowest cost
        conflict = find_first_conflict(node.solution)
        if conflict is None:
            return node.solution  # conflict-free
        for constraint in resolve(conflict):
            child = CTNode(
                constraints=node.constraints + [constraint],
                solution=replan(node, constraint)
            )
            open_list.append(child)
    return None  # no solution

インライン数式の例

エージェント数を $k$ 、グラフの頂点数を $|V|$ 、辺数を $|E|$ とすると、状態空間のサイズは $O(|V|^k)$ となります。しかし実際には、制約ツリーの分岐が限定的であるため、探索空間は大幅に削減されます。

まとめ

MAPFは計算複雑性の観点からNP困難ですが、CBS系のアルゴリズムにより実用的な規模の問題を解くことが可能です。Rovnouはこれらの研究成果を活用し、倉庫ロボットのリアルタイム経路最適化を実現しています。

本記事は MAPF研究の概要を参考に作成しました。

はじめに#

衝突の定義#

頂点衝突（Vertex Conflict）#

辺衝突（Edge Conflict）#

最適化目的関数#

Makespan の最小化#

Sum-of-Costs の最小化#

CBSアルゴリズム#

インライン数式の例#

まとめ#