Mathematical Models for Collision Avoidance in MAPF

Introduction#

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple robots to reach their destinations simultaneously.

As the number of warehouse robots increases, the risk of deadlocks and livelocks grows. This article explains the mathematical definitions of collisions in MAPF and the optimization objectives.

Collision Definitions#

MAPF considers two types of collisions.

Vertex Conflict#

Two agents $a_i$ and $a_j$ occupy the same node $v$ at the same timestep $t$:

where $\pi_i(t)$ denotes the position of agent $a_i$ at timestep $t$.

Edge Conflict#

Two agents traverse the same edge in opposite directions at the same timestep:

Optimization Objectives#

MAPF has two common optimization objectives.

Makespan Minimization#

Minimize the latest arrival time across all agents:

Sum-of-Costs Minimization#

Minimize the total path cost of all agents:

CBS Algorithm#

Conflict-Based Search (CBS) is the foundational MAPF algorithm.

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

Inline Math Examples#

Given $k$ agents, $|V|$ vertices, and $|E|$ edges, the state space is $O(|V|^k)$. In practice, however, the constraint tree branching is limited, drastically reducing the search space.

Conclusion#

MAPF is NP-hard in terms of computational complexity, but CBS-family algorithms make it possible to solve practical-scale problems. Rovnou leverages this research to deliver real-time path optimization for warehouse robots.

This article was written with reference to MAPF research overview.