Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Symmetry-Breaking Constraints for Grid-Based Multi-Agent Path Finding
Jiaoyang Li, Daniel Harabor, Peter J. Stuckey, Hang Ma, Sven Koenig
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add rectangle reasoning with barrier constraints and cardinal-rectangle heuristics (CBSH-RM) | CBSH · 20x20 empty grid, 30 agents | runtime: 6.2 -> 0.02 | Improved |
| add rectangle reasoning with barrier constraints and cardinal-rectangle heuristics (CBSH-RM) | CBSH · 20x20 empty grid, 60 agents | runtime: 28.4 -> 2.9 | Improved |
| add rectangle reasoning with barrier constraints and cardinal-rectangle heuristics (CBSH-RM) | CBSH · 20x20 10% blocked, 50 agents | runtime: 19.0 -> 16.4 | Improved |
| add rectangle reasoning with barrier constraints and cardinal-rectangle heuristics (CBSH-RM) | CBSH · 20x20 empty grid, 30 agents | CT nodes expanded: 29,506 -> 87 | Improved |
| use cardinal rectangle conflicts to compute heuristics (ablation) | CBSH · 20x20 grids | runtime | Improved |
| use barrier constraints to resolve rectangle conflicts (ablation) | CBSH · 20x20 grids | runtime | Improved |
| add reasoning about semi- and non-cardinal rectangle conflicts (CBSH-R vs CBSH-CR) (ablation) | CBSH-CR · 20x20 empty grid, many agents | runtime: 11.0 -> 9.6 | Improved |
| add rectangle reasoning between path segments (RM vs R) (ablation) | CBSH-R · den520d and lak503d | runtime | Improved |
| add rectangle reasoning (CBSH-RM) | CBSH · den520d | runtime | Improved |
| CBSH-CR vs CBSH-R and CBSH-RM (ablation) | CBSH-RM · 20x20 grids | runtime | No clear effect |
Closest papers by meaning
- Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024 · similarity 0.90)
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · similarity 0.89)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.89)
- Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic (AAAI 2025 · similarity 0.88)
- Windowed MAPF with Completeness Guarantees (AAAI 2025 · similarity 0.88)
- Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution (AAAI 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
