Skip to content

PIBT

cuplan.PIBT — Priority Inheritance with Backtracking (Okumura, Machida, Défago and Tamura 2022, Artificial Intelligence 310:103752). No whole-path planning: every timestep, each agent proposes the neighbouring vertex closest to its goal, and conflicts are settled on the spot — a high-priority agent lends its priority to the occupant of the vertex it wants, recursively, backtracking when a chain cannot move. Priorities grow while an agent is away from its goal and reset on arrival, which prevents starvation.

Guarantees, stated plainly

PIBT is incomplete: it can livelock on instances that require an agent to move far away from its goal. Reachability of every goal is verified up front, so a failure is reported as livelock within the step bound, never silently. LaCAM — on the roadmap — wraps PIBT in a complete search and fixes exactly this.

Parallelization

Three parts, two of them parallel:

  1. Distance oracle — one exact goal-distance table per agent, the dominant cost in pymapf's implementation (a serial Dijkstra per agent). Here it is a single batched BFS.
  2. Candidate evaluation — each step, every agent's five candidate vertices are gathered and ordered by goal distance with random tie-breaking: one vectorized gather + argsort across all agents.
  3. Inheritance chains — recursive and data-dependent, so they run on the host, exactly as written in the paper.

Runs are reproducible for a fixed seed, and identical between the CPU and CUDA backends (the backends change where the oracle is computed, not any decision).

Priority Inheritance with Backtracking (PIBT), GPU-assisted.

PIBT (Okumura et al. 2022, Artificial Intelligence 310:103752) plans one timestep at a time: each agent proposes the neighbouring vertex closest to its goal, and conflicts are settled on the spot by priority inheritance with backtracking. Priorities grow while an agent is away from its goal and reset on arrival, which prevents starvation.

What parallelizes and what does not, stated plainly:

  • The distance oracle — one exact goal-distance table per agent, the dominant cost in pymapf's implementation (one serial Dijkstra per agent) — is a single batched BFS on the selected backend.
  • The candidate evaluation — gathering the five candidate vertices of every agent and ordering them by goal distance with random tie-breaking — is one vectorized gather + argsort across all agents per timestep.
  • The inheritance chains are recursive and data-dependent, so they run on the host, exactly as written in the paper.

PIBT is incomplete: it can livelock on instances that require an agent to move far away from its goal (LaCAM, on the roadmap, fixes that by wrapping PIBT in a complete search). Reachability of every goal is checked up front, so failures are reported as livelock, not silence.

PIBT

Rule-based one-step-at-a-time MAPF solver (Okumura et al. 2022).

Parameters:

Name Type Description Default
max_timestep int | None

give up after this many timesteps. Defaults to a bound proportional to the map size and the agent count.

 None
seed int | None

fixes tie-breaking, making a run reproducible.

 0
backend Backend

backend used for the batched distance oracle and the per-step candidate evaluation.

 'auto'
Source code in cuplan/pibt.py 
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
class PIBT:
    """Rule-based one-step-at-a-time MAPF solver (Okumura et al. 2022).

    Args:
        max_timestep: give up after this many timesteps. Defaults to a
            bound proportional to the map size and the agent count.
        seed: fixes tie-breaking, making a run reproducible.
        backend: backend used for the batched distance oracle and the
            per-step candidate evaluation.
    """

    name = "pibt"

    def __init__(
        self,
        max_timestep: int | None = None,
        seed: int | None = 0,
        backend: Backend = "auto",
    ):
        self.max_timestep = max_timestep
        self.seed = seed
        self.backend = backend

    def solve(self, problem: Problem) -> Solution | None:
        """Return a conflict-free :class:`~cuplan.problem.Solution` or None."""
        started = time.perf_counter()
        which = resolve_backend(self.backend)
        grid = problem.grid
        w = grid.width
        n = len(problem.agents)
        names = [a.name for a in problem.agents]
        rng = np.random.default_rng(self.seed)

        # Batched exact distance oracle: (n, cells), -1 -> +inf.
        dist = (
            distance_maps(grid, problem.goals, backend=which)
            .reshape(n, -1)
            .astype(np.int64)
        )
        dist[dist < 0] = _INF

        positions = problem.starts[:, 0].astype(np.int64) * w + problem.starts[:, 1]
        goals = problem.goals[:, 0].astype(np.int64) * w + problem.goals[:, 1]
        if (dist[np.arange(n), positions] >= _INF).any():
            return None  # some agent cannot reach its goal
        candidates = _candidate_table(grid)

        base = np.arange(n, dtype=np.float64) / (n + 1)
        priorities = base.copy()
        horizon = self.max_timestep or (grid.free_cells + 4 * n + 8)

        steps = [positions.copy()]
        for _ in range(horizon):
            if (positions == goals).all():
                break
            order = np.argsort(-priorities, kind="stable")
            ranked = self._rank_candidates(dist, candidates, positions, rng)
            nxt = _pibt_step(positions, ranked, order)
            if nxt is None:
                return None
            positions = nxt
            steps.append(positions.copy())
            at_goal = positions == goals
            priorities = np.where(at_goal, base, priorities + 1.0)

        if not (positions == goals).all():
            return None  # livelock within the horizon

        array = np.stack(steps)  # (T+1, n)
        cells = np.stack([array // w, array % w], axis=-1)
        return Solution(
            paths=paths_from_array(cells, names, problem.goals),
            algorithm=self.name,
            backend=which,
            runtime=time.perf_counter() - started,
        )

    def _rank_candidates(
        self,
        dist: np.ndarray,
        candidates: np.ndarray,
        positions: np.ndarray,
        rng: np.random.Generator,
    ) -> np.ndarray:
        """Order every agent's candidate vertices by goal distance.

        One gather + argsort over the whole batch: ``(n, 5)`` candidate
        cells, distances looked up in each agent's own table, ties
        broken by a fresh random key (the randomness LaCAM relies on).
        Invalid candidates sort last and are marked -1.
        """
        n = len(positions)
        cand = candidates[positions]  # (n, 5)
        valid = cand >= 0
        d = np.where(valid, dist[np.arange(n)[:, None], cand.clip(min=0)], _INF)
        d = np.where(d >= _INF, _INF, d)
        keys = d.astype(np.float64) + rng.random((n, 5))
        keys[~valid] = np.inf
        order = np.argsort(keys, axis=1, kind="stable")
        ranked = np.take_along_axis(cand, order, axis=1)
        ranked[np.take_along_axis(~valid, order, axis=1)] = -1
        return ranked

solve 

solve(problem)

Return a conflict-free :class:~cuplan.problem.Solution or None.

Source code in cuplan/pibt.py 
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
def solve(self, problem: Problem) -> Solution | None:
    """Return a conflict-free :class:`~cuplan.problem.Solution` or None."""
    started = time.perf_counter()
    which = resolve_backend(self.backend)
    grid = problem.grid
    w = grid.width
    n = len(problem.agents)
    names = [a.name for a in problem.agents]
    rng = np.random.default_rng(self.seed)

    # Batched exact distance oracle: (n, cells), -1 -> +inf.
    dist = (
        distance_maps(grid, problem.goals, backend=which)
        .reshape(n, -1)
        .astype(np.int64)
    )
    dist[dist < 0] = _INF

    positions = problem.starts[:, 0].astype(np.int64) * w + problem.starts[:, 1]
    goals = problem.goals[:, 0].astype(np.int64) * w + problem.goals[:, 1]
    if (dist[np.arange(n), positions] >= _INF).any():
        return None  # some agent cannot reach its goal
    candidates = _candidate_table(grid)

    base = np.arange(n, dtype=np.float64) / (n + 1)
    priorities = base.copy()
    horizon = self.max_timestep or (grid.free_cells + 4 * n + 8)

    steps = [positions.copy()]
    for _ in range(horizon):
        if (positions == goals).all():
            break
        order = np.argsort(-priorities, kind="stable")
        ranked = self._rank_candidates(dist, candidates, positions, rng)
        nxt = _pibt_step(positions, ranked, order)
        if nxt is None:
            return None
        positions = nxt
        steps.append(positions.copy())
        at_goal = positions == goals
        priorities = np.where(at_goal, base, priorities + 1.0)

    if not (positions == goals).all():
        return None  # livelock within the horizon

    array = np.stack(steps)  # (T+1, n)
    cells = np.stack([array // w, array % w], axis=-1)
    return Solution(
        paths=paths_from_array(cells, names, problem.goals),
        algorithm=self.name,
        backend=which,
        runtime=time.perf_counter() - started,
    )