Traffic management and conflict prevention

1. Engineering problem

Two robots planning independently can meet head-on in a corridor or arrive at the same junction together. A traffic manager reserves nodes and edges in time and resolves conflicts by delay or rerouting.

2. When is this needed?

• Operating more than one robot in shared space.
• Narrow aisles and doors.
• Mixed fleets from several vendors.

3. Selection and design decisions

Two classic conflicts on a graph with time steps: a vertex conflict (two robots at the same node at the same time) and a swap (edge) conflict (two robots exchanging nodes along one edge). Open-RMF’s README (read 2026-11-06) describes a platform for multi-fleet management in which a traffic component is one part; the principle here is general. Waiting resolves vertex conflicts when someone can wait; head-on swaps in a single-width corridor need a passing place, a one-way rule or a reroute.

4. Advantages and disadvantages

• Priority rules are simple and can starve low-priority robots.
• Central reservation avoids conflicts and depends on the network; local negotiation is resilient.
• More space (passing bays) costs layout changes and saves delays.

5. Requirements and constraints

• Reservation of all shared resources (nodes, edges, doors).
• A fallback for lost communications (stop and wait, not proceed).
• Deadlock detection.

6. Architecture

robot plans (node, time) ─▶ traffic manager: reserve ─▶ conflict? ─▶ delay or reroute ─▶ approved plan ─▶ robots

7. Implementation

1. Model the space as a graph with capacities.
2. Collect each robot’s planned path with times.
3. Detect vertex and swap conflicts (below).
4. Resolve by waiting or rerouting.
5. Handle what waiting cannot resolve (passing places).

def conflicts(plans):
    found, at = [], {}
    for robot, path in plans.items():
        for t, node in enumerate(path):
            if (node, t) in at:
                found.append(("vertex", node, t, at[(node, t)], robot))
            at[(node, t)] = robot
    names = list(plans)
    for i, a in enumerate(names):
        for b in names[i + 1:]:
            pa, pb = plans[a], plans[b]
            for t in range(min(len(pa), len(pb)) - 1):
                if pa[t] == pb[t + 1] and pa[t + 1] == pb[t]:
                    found.append(("swap", tuple(sorted((pa[t], pa[t + 1]))), t, a, b))
    return found
plans = {"A": ["n1", "n2", "n3", "n4"], "C": ["n8", "n9", "n3", "n10"], "D": ["n11", "n12", "n13", "n14"], "E": ["n12", "n11", "n15", "n16"]}
for c in conflicts(plans):
    print(c)
plans["C"] = ["n8", "n8", "n9", "n3"]                                  # C waits one step at its start
print("after delaying C by one step:", conflicts(plans))

Printed (checked by the site’s tests):

('vertex', 'n3', 2, 'A', 'C')
('swap', ('n11', 'n12'), 0, 'D', 'E')
after delaying C by one step: [('swap', ('n11', 'n12'), 0, 'D', 'E')]

Reading it: robots A and C both reach node n3 at step 2 (a vertex conflict); D and E swap places on the n11–n12 edge (a swap conflict). Delaying C by one step resolves the vertex conflict; the swap remains, because waiting does not let two robots pass in a single-width corridor. The graph and paths are invented.

8. Real examples

• Narrow aisle: one-way rule and a passing bay every 10 m.

9. Failure scenarios

• Assuming waiting fixes every conflict.
• No fallback when a robot loses communication in a shared corridor.
• Ignoring doors and lifts as shared resources.

10. Troubleshooting

1. Visualise the reservations over time.
2. Look for cyclic waits.
3. Check clock sync between planners.

11. Validation

• The detector prints the lines shown (executed by the site tests).
• A simulation with many robots shows no collisions and no unresolved deadlocks.

12. Engineering checklist

• Space modelled as a graph
• Vertex and swap conflicts detected
• Resolution strategy
• Deadlock handling
• Communication-loss fallback

13. Further references

• Open-RMF README: open-rmf/rmf, read 2026-11-06 (“the Open-RMF platform for multi-fleet robot management”; supported for the ROS 2 distributions Humble, Jazzy, Kilted and Rolling).

Related on FixTheRobot