Algorithm engineering · Multi-agent planning · Python
When plans
collide, recover.
- Automated tests
- 70
- Seeded oracle cases
- 1,200
- Planning strategies
- 3
- Post-recovery conflicts
- 0
What happens after a valid plan meets reality?
Multi-agent routes can be collision-free at planning time and unsafe one moment later. A delayed robot, vehicle or process can invalidate another agent's reserved position even when the original planner was correct.
The project treats disruption as part of the system. It simulates the failure, discovers the affected set, locks the executed prefix and replans only the remaining suffixes before a separate validator accepts the result.
Four boundaries from plan to proof.
- 01Plan
Static A*, canonical SIPP and reservation-aware planning establish the initial joint paths.
- 02Simulate
A discrete-time runtime executes paths and injects a declared one-step delay.
- 03Recover
Affected-set discovery protects completed work and selectively replans future suffixes.
- 04Validate
An independent checker tests legality, collisions, goal holding, prefixes and determinism.
A planner cannot certify itself.
Results are not marked solved until an independent validator passes every declared invariant.
Legal paths
Every path starts at its declared start, reaches its goal and uses only valid moves.
Vertex safety
No two agents may occupy the same cell at the same timestep.
Edge safety
No two agents may swap the same edge in opposite directions simultaneously.
Goal occupancy
An arrived agent continues to reserve its goal through the planning horizon.
Prefix integrity
Recovery preserves the executed prefix exactly and changes only future work.
Determinism
Fixed inputs produce the same plan, event trace, metrics and solution digest.
Search logic separated from presentation.
Three strategies, explicit trade-offs.
The benchmark record is limited to committed small instances. It shows where additional bounded search changes the result without turning local measurements into general performance claims.
Fixed priority
One deterministic order with the lowest search effort, but order-dependent and incomplete.
Priority trap: no planPriority sweep
Tries a bounded set of deterministic orders and retains the best valid result.
Priority trap: cost 11Bounded CBS
Resolves conflicts in a constraint tree and optimizes sum of costs when within its limit.
Priority trap: cost 11Correctness before spectacle.
01Low-level oracleCanonical SIPP matched an exact space-time BFS oracle across 1,000 deterministic random cases.
02Multi-agent casesOne hundred seeded prioritised-planning cases exercise reservations, conflicts and goal occupancy.
03CBS oracleOne hundred exact joint-state comparisons test the bounded Conflict-Based Search implementation.
04Regression setFive permanent scenarios protect crossing, order, storage-detour and recovery behavior.
05Scaling recordA controlled 9 × 9 family adds agents from two to six and reports deterministic expanded-state counts.
Bounded evidence, stated plainly.
Fixed-priority planning is order-dependent and incomplete. Priority sweep grows factorially. Conflict-Based Search can grow exponentially and is deliberately restricted to small instances.
This is a discrete-time planning laboratory, not a production railway dispatch system, robotics controller or safety-certified operational product. The measurements support the committed scenarios only.