When you describe a warehouse floor to a robot, the representation you choose has significant downstream consequences. A flat coordinate map treats every point in the floor as roughly equivalent and relies on collision-avoidance behaviours at the robot level to prevent two robots from occupying the same space. A lane-and-node graph treats the warehouse as a network of traversable paths with defined capacity and directionality constraints built into the model itself.
The graph model is not just a different data format. It changes what questions the orchestration layer can ask and answer efficiently. This post covers why we have been working with graph representations, specifically for the problem of detecting and resolving path conflicts across concurrent robot task assignments.
What a Warehouse Graph Actually Looks Like
The canonical representation starts by identifying the set of navigable nodes: bay pick positions, cross-aisle intersections, staging areas, dock face positions, charging stations, and any other point where a robot may stop or change direction. Each node has attributes: its physical location, capacity (how many robots can occupy it simultaneously), and any type constraints (a charging station is only accessible to robots below a certain battery threshold, for example).
Edges connect nodes and represent traversable segments: a lane run between two bays, the length of a cross-aisle, a ramp transition between floor levels. Edges carry directional attributes (one-way or bidirectional), an estimated traversal time for a given robot type and payload, and a capacity attribute representing how many robots can be in transit on that segment simultaneously. A narrow aisle that can only accommodate a single robot in one direction at a time has capacity 1 with a one-way constraint during occupation.
This structure makes certain computations straightforward. Finding all paths from node A to node B is a graph traversal. Finding whether a given path overlaps with another robot's planned path is an edge-set intersection. Identifying the minimum set of edges whose removal would disconnect a source from a destination is a max-flow/min-cut problem. None of these are trivial with a flat coordinate map; all of them have well-understood algorithms in a graph model.
How Path Conflicts Arise in Concurrent Task Assignment
Consider a facility with three active ops requests running concurrently, each generating two to four robot tasks. At any given moment, six to twelve robots are in motion, each following a planned route through the warehouse graph. Path conflicts arise when two or more of those routes share an edge or node in a way that would cause either a collision or an unproductive wait.
The simplest conflict type is head-on contention: robot A is assigned to traverse lane 7 northward while robot B is assigned to traverse lane 7 southward at approximately the same time. If the lane is bidirectional but too narrow for two robots to pass, one of them has to yield. The question is: which one, and how?
The second type is intersection contention: two robots converge on the same cross-aisle intersection from different directions and need to negotiate right of way. This is analogous to a four-way stop but with multiple robots potentially involved at the same intersection within a short time window.
The third type is convoy formation: multiple robots assigned to tasks that happen to use the same route segment in the same direction. This is not a collision risk but it is a throughput risk. A convoy of three robots spaced two seconds apart on a narrow lane creates a long occupancy period that blocks any robot trying to use the same lane in the opposite direction.
The fourth type is destination contention: multiple tasks targeting the same node at overlapping times, most commonly at dock faces or staging areas with limited capacity. Even if the routes there are non-conflicting, the destination becomes a choke point.
Detection Before Dispatch vs. Resolution in Motion
There are two broad strategies for handling path conflicts: detect them at dispatch time, before any robot moves, and assign routes that are non-conflicting by construction; or detect conflicts as robots move and resolve them dynamically using local negotiation protocols.
The local negotiation approach is what most AMR platforms implement at the robot level. Individual robots exchange position data via a coordination protocol (MiR, Locus, and others use variants of this) and negotiate right of way using priority signals. This works reasonably well for simple head-on scenarios but becomes unpredictable when multiple robots are involved in overlapping conflicts, and it cannot reason about task-level objectives. A robot that wins a right-of-way negotiation might be carrying a lower-priority task than the one that waited.
Pre-dispatch conflict detection works differently. Before assigning routes to a new set of tasks, the orchestration layer queries the current route reservations of all active robots, identifies conflicts with the candidate routes, and selects assignments that avoid those conflicts or sequence through them with defined time separation. This requires knowing the full set of planned routes, which is exactly what a stateful orchestration layer holds.
We are not claiming pre-dispatch detection replaces dynamic avoidance. A robot may deviate from its planned route because of a local sensor event, making the pre-computed conflict analysis stale. Both layers matter. But pre-dispatch detection significantly reduces the number of in-motion conflicts that dynamic avoidance has to handle, which reduces the robot-level negotiation overhead and the unpredictable wait times it can produce.
Reservation-Based Conflict Avoidance
One practical approach to pre-dispatch conflict detection is edge reservation: each planned route is broken into a sequence of (edge, time_window) pairs representing when a robot is expected to occupy that edge. When a new task is being routed, the planner checks whether any candidate path's (edge, time_window) pairs overlap with existing reservations. If they do, the planner either selects an alternative path or time-shifts the new task's route to avoid the overlap.
Time-shifting means scheduling the robot to start traversal of a contested segment slightly later, after the reservation window of the conflicting robot has cleared. This works well when the time overlap is small and the delay cost is acceptable. When multiple contested segments exist on the shortest path, the accumulated delay from time-shifting may make a longer alternative path preferable.
The reservation window granularity matters a lot in practice. Reserving an entire lane for 90 seconds because a robot will be somewhere on it during that interval is too coarse. It blocks other tasks from using parts of the lane that the robot won't actually occupy during the reservation window. Reserving at the edge-segment level, with time windows derived from speed estimates and payload, is more accurate but more expensive to compute and maintain.
Edge reservations also go stale when a robot deviates. If robot 07 was supposed to be in lane 6 between 14:22:10 and 14:22:40 but instead stopped and waited at a sensor alert, the reservation is now inaccurate and could be blocking routes that are actually safe to use. Stale reservation cleanup is an operational requirement, not just a nice-to-have.
Priority and Preemption in the Graph
Not all robot tasks have equal priority. A time-sensitive ops request serving a departing truck has higher priority than a background replenishment task. When a conflict exists between two routes and time-shifting both is not acceptable, the orchestration layer needs a priority ordering to decide which task defers.
In the graph model, priority can be encoded at the task level and used as a tiebreaker when route assignments conflict. The lower-priority task gets time-shifted or rerouted; the higher-priority task proceeds on the preferred path. This makes priority decisions explicit and traceable rather than emergent from whatever local negotiation protocol the robots happen to run.
Preemption is the stronger version: if a high-priority task is blocked by an already-moving lower-priority robot, can that robot be recalled to a waiting position to clear the path? This is technically possible but operationally disruptive. Preemption should be a last resort, reserved for situations where the priority differential is large and the cost of the lower-priority robot waiting at a standby position is acceptable.
Limits of the Graph Approach
Graph-based conflict resolution depends on the graph being accurate. A map that was correct at commissioning but hasn't been updated after a layout change will generate false routes, incorrect conflict predictions, and unexpected robot behaviours. Keeping the graph current is an ongoing operational responsibility, not a one-time setup task.
Speed estimates used to compute time windows are approximations. Real robots slow down around corners, vary speed with payload, and respond to local sensor events in ways that the graph model doesn't capture at full fidelity. The time-window reservations are therefore approximate, and the conflict detection is approximate. The system is managing probability of conflict, not guaranteeing zero conflict. Dynamic avoidance at the robot level remains necessary as a backstop.
The graph model also does not capture human traffic. People move through warehouses in ways that don't respect lane assignments or right-of-way logic. Robot-level sensors handle this at the avoidance layer, but the planning layer has no visibility into where a human is likely to be in 40 seconds. Human and robot traffic interact in the physical space in ways the graph cannot fully anticipate.
These are not arguments against graph-based planning. They are arguments for being precise about what it does and doesn't provide. It moves conflict prediction from reactive to proactive, reduces in-motion negotiation load, and makes priority decisions traceable. It doesn't make the problem disappear.