Navigation · Theory · M8
M8-T5 — Traffic Management, Deadlock and Livelock
A fleet can fail without a single robot failing: every robot works, and nobody moves.
Each robot in a deadlock is doing the right thing: it waits politely for a space to clear. The space belongs to a robot that is waiting for a space that belongs to another, and so on round a circle. Livelock is the lively cousin, where everyone is busy and nothing gets done. Neither is cured by a better local planner. Both are cured by rules about who may be where, written into the map and the fleet manager.
Learning objectives
After this lesson, you should be able to:
- Define deadlock, livelock and starvation, and recognise each from a log of waits and positions.
- State the four conditions for deadlock and match each prevention method to the condition it breaks.
- Use reservations, one-way lanes, ordering of resources and capacity limits to prevent gridlock.
- Estimate how a traffic rule changes the capacity of a single-lane corridor.
The intuition
Four cars arrive at the same time at a four-way stop with no priority rule, each waiting for the car on its right. Everyone is courteous and nobody moves. That is a deadlock: a closed loop of waiting. Not one party is broken, and no amount of patience will help.
Now two people meet in a corridor. One steps left, the other steps in the same direction; both step right; both step left again. They are moving all the time and not passing. That is a livelock: state changes without progress. The cure is not more effort, it is an asymmetric rule: “both keep right”.
A third problem is quiet. A robot with a low priority always yields to the robots with a high priority, and in a busy hour it never gets to go. That is starvation: the system as a whole makes progress, one member never does.
Fleet managers prevent these by treating the building as a set of shared resources (lanes, junctions, lifts, doors, chargers) and handing them out by rule. The aim is not to resolve a deadlock when it happens; it is to arrange the rules so that it cannot.
The mathematics
The four conditions
Coffman, Elphick and Shoshani (1971) showed that deadlock needs all four of these conditions at once, which is why breaking any one prevents it:
| Condition | For robots | Breaking it |
|---|---|---|
| Mutual exclusion | A lane segment or a junction holds one robot at a time | Make the space wide enough to share, or add bays and passing places |
| Hold and wait | A robot occupies a place while requesting the next | Reserve the whole stretch before entering, or release first: all or nothing |
| No preemption | A robot cannot be made to give up its place | Allow a supervisor to back a robot out, or allow it to retreat after a timeout |
| Circular wait | Robots wait for each other in a ring | Order the resources, make lanes one-way, or give strict priorities |
Wait-for graph
Draw a node for each robot and an arrow from i to j if i is waiting for a place that j holds. A cycle in this graph is a deadlock. A fleet manager can build the graph from the robots’ states every second and check it. A wait chain without a cycle is only congestion: the head of the chain is moving.
Livelock and starvation
Livelock cannot be seen in a wait-for graph, since nobody is waiting. It shows in the motion: robots move, but their distance to the goal does not fall over a window of time, and their positions repeat. The progress test of lesson M7-T6 catches it. Starvation shows in the statistics: one robot’s waiting time grows without bound while others are served.
Preventing by design
| Rule | How it works | Price |
|---|---|---|
| Reservation of a section | A robot asks for the whole lane or junction, and enters only when it has been granted | Longer waits; a lock that is never released blocks everyone, so reservations need a time limit |
| One-way lanes | Opposing traffic uses different lanes; a cycle can only form at junctions | Longer routes, and a loop of one-way lanes can still gridlock if full |
| Ordering of resources | Every robot requests places in one global order, so a ring cannot form | The order must be consistent across the whole building |
| Capacity limit | At most k − 1 robots may enter a loop of k places, so there is always a free place to move into | Fewer robots in the zone at once |
| Strict priority with ageing | Priority by urgency, rising with waiting time | A rule about rules: ageing prevents starvation |
| Timeout, back out, random delay | After waiting too long a robot retreats, then waits a random time before trying again | Can livelock if all retreat together; randomness is what breaks the tie |
These are the same ideas as in operating systems and railways, with the same warnings: the safest systems have an operator-visible tool to see who is waiting for whom.
A worked example
The cost of an exclusive lock. A single-lane corridor is 12 m long. Robots travel at 0.6 m/s, are 0.8 m long and keep a gap of 0.6 m when following. A robot crossing needs 12 / 0.6 = 20 s to get from entry to exit, and 21.3 s from the front crossing the entry until the rear has cleared the exit: (12 + 0.8) / 0.6.
| Traffic rule | Time to move robots through | Capacity |
|---|---|---|
| Exclusive lock for every robot, either direction | 21.3 s per robot | 60 / 21.3 = 2.8 robots/min |
| Batch of 4 in one direction, then the other direction | 21.3 + 3 × 2.33 = 28.3 s per batch of 4 | 4 × 60 / 28.3 = 8.5 robots/min |
The following headway is (0.8 + 0.6) / 0.6 = 2.33 s. Letting robots follow one another in the same direction triples the capacity of the same corridor (8.47 against 2.81), and that is the reason traffic rules usually grant a lane to a direction for as long as robots are queued, up to a limit that stops the other direction starving.
The four-way ring. In the figure each of four robots has entered the junction approach and holds one of the four quadrants of the junction, and each needs the quadrant held by its neighbour. Allow at most three robots to enter the junction at once (k − 1 for a ring of four) and one of them always has a free quadrant ahead, so the ring cannot close. A sign “one at a time” would also work and would cut the capacity.
The lobby of lab M8-L4. It is a close relative: there robot 1 parks in the corridor that robot 2 needs. It is not a ring, it is a robot that holds a place for ever, but the cure is of the same family: do not let robots park in a one-cell-wide corridor, or decide who goes first (stage 3 searches the priority order).
Engineering implications and limitations
Put the rule in the map
Mark the lane graph (lesson M2-T5) with direction, capacity and waiting places. A corridor too narrow for two robots gets a capacity of one and a bay at each end; a lift gets a queue and a rule that a robot never waits inside it for another resource; a charger gets a place to wait that is not on the main route (lesson M8-T6). It is much cheaper to design out a deadlock than to detect it.
Detect anyway, and have an exit
Run a cycle check on the wait-for graph and a no-progress monitor on every robot, and decide beforehand what happens: back out the robot with the lowest priority, release its reservations, replan, and tell an operator. A robot should always be able to retreat along the way it came; make that a design rule for lanes, and check that the retreat cell is not reserved by someone else.
Asymmetry breaks livelock
If two robots follow the same reactive rule they can mirror each other for ever. Break the symmetry with an identifier (the lower number yields), a convention (pass on the right), or a random delay. Reciprocal methods such as ORCA (lesson M6-T5) are designed so that each robot takes half the avoidance, but they assume open space; in a corridor use explicit rules.
Reservations need leases
A robot that has reserved a lane and then loses power or radio holds the lane for everyone. Give every reservation a lease that must be renewed by a heartbeat, and let the fleet manager revoke it when it expires. Decide what an operator must do before restarting a fleet after a power cut: a fleet recovering all at once can recreate the very jam it was in.
Open-source fleet frameworks
Fleet integration frameworks such as Open-RMF keep a shared traffic schedule that the fleets’ adapters read and negotiate over. Whatever the product, the questions to ask are the same: who owns a reservation, how long does it live, who may revoke it, and what do robots from different vendors do when they disagree.
Common misconceptions
“Deadlock means a robot or a program is broken.”
Every robot can behave perfectly. Deadlock is a property of the rules and the map, which is why the cure is in the rules and the map.
“Livelock is a slow deadlock.”
Nothing is waiting in a livelock: the robots are moving, often fast. The cure is asymmetry (priorities, conventions, randomness), not patience.
“A timeout and a retreat fix deadlock.”
They break the no-preemption condition, but if all robots retreat together and try again together they livelock. Add a random delay or a priority.
“More robots only mean more congestion.”
Past a certain density they mean gridlock: the capacity of a ring falls to zero. A limit on how many robots may enter a zone keeps the fleet moving.
Engineering takeaways
- Deadlock needs four conditions at once (mutual exclusion, hold and wait, no preemption, circular wait); break one and it cannot happen.
- Deadlock is a cycle in the wait-for graph; livelock is motion without progress; starvation is one robot never being served.
- Reservations, one-way lanes, resource ordering and capacity limits prevent gridlock by design; timeouts need randomness or priority.
- Letting robots follow in a batch can triple the capacity of a single lane compared with a lock per robot.
- Give reservations leases, mark waiting places in the map, and keep a tool that shows who waits for whom.
References and further reading
The classic paper on deadlock conditions and a description of a large warehouse fleet that coordinates robots by reservation.
- E. G. Coffman, M. Elphick and A. Shoshani, “System deadlocks”, ACM Computing Surveys 3(2), 1971.
- P. R. Wurman, R. D’Andrea and M. Mountz, “Coordinating hundreds of cooperative, autonomous vehicles in warehouses”, AI Magazine 29(1), 2008.
- Open-RMF documentation, “Traffic Management” (traffic schedule and negotiation), open-rmf.github.io.
Knowledge check
Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.
Question 1
Four robots wait at a junction, each blocked by the one on its right. Which of the four conditions for deadlock is the one that is easiest to break by a rule, and what rule?
Explanation
Circular wait. Give the junction a capacity of three robots, make the approaches one-way, or give a fixed priority order. Any of these means the ring of waits cannot close.
Question 2
A 6 m single-lane corridor, robots at 0.5 m/s, 0.8 m long, 0.5 m following gap. Capacity with an exclusive lock per robot, and with batches of 3 in one direction?
Explanation
Exclusive: (6 + 0.8) / 0.5 = 13.6 s per robot, so 4.4 robots/min. Batch of 3: headway (0.8 + 0.5) / 0.5 = 2.6 s, so 13.6 + 2 × 2.6 = 18.8 s for three robots, 3 × 60 / 18.8 = 9.6 robots/min, about twice as many.
Question 3
Two robots in a corridor each sidestep left, then right, then left again, in step, and never pass. Is this deadlock? What fixes it?
Explanation
No, it is livelock: they keep moving and make no progress. An asymmetric rule fixes it: keep right, let the lower identifier yield, or add a random delay.
What’s next
Next: the other shared resources of a fleet, the charger and the dock, and the numbers that say whether the fleet is doing its job.
Related content
Nothing below is required to finish this lesson.
- BeforeM8-T4: Multi-Robot Path Finding
Plan for several robots with prioritized planning and explain what conflict-based search adds.
- LabM8-L4: Break the Deadlock
Three robots meet at the elevator lobby at 07:40 and none will move: plan so that all of them get through.
Get notified when the next lesson and new labs are released.
One email per new lesson or lab.