Prioritized planning with random restarts for hard MAPF
Implemented multi-agent path finding and task planning for a class assignment, including a fast solver for hard MAPF instances.
For dense MAPF (8 agents in a 10x10 maze), prioritized planning with space-time A* per agent + random-restart ordering (up to 50 tries) solved all hard instances in under 0.5s — no need for CBS complexity. Pad each agent path to a global max_time horizon (4x reachable cells works) and check both vertex collisions (same cell at time t) and edge swap collisions (agents swap positions between t and t+1) when expanding successors. For the delete-relaxation heuristic in STRIPS-style planning, avoid infinite recursion by setting use_heuristic=False on the inner relaxed search.
When picking an MAPF solver under a strict time budget, try prioritized planning first — it is wildly simpler than CBS and often Good Enough.