Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Generalized and Sub-Optimal Bipartite Constraints for Conflict-Based Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| use time-annotated bicliques (CBS+TAB) instead of classic edge/vertex constraints | CBS · Boston, 16-connected | final CT size: 1,422 -> 174 | Helped |
| add time annotation to max-vertex biclique constraints (MVB -> TAB) (ablation) | CBS+MVB · Boston 0 256, 8-connected | problems solved in 30s (sum over 25 tests): 1,446 -> 1,574 | Helped |
| add time annotation to max-vertex biclique constraints (MVB -> TAB) (ablation) | CBS+MVB · room-64-64-8, 16-connected | final CT size: 1,451 -> 321 | Helped |
| use time-range constraints instead of edge constraints for biclique (Time vs TAB) | CBS · Boston 0 256, 8-connected | problems solved in 30s (sum over 25 tests): 1,312 -> 1,574 | Helped |
| approximate biclique as 1xN (TMA) instead of full TAB (ablation) | CBS+TAB · Boston 0 256, 32-connected | problems solved in 30s (sum over 25 tests): 974 -> 1,205 | Helped |
| approximate biclique as 1xN (TMA) instead of full TAB (ablation) | CBS+TAB · Boston 0 256, 8-connected | problems solved in 30s (sum over 25 tests): 1,563 vs 1,574 | No clear effect |
| add conditional constraints (TCC) to GCBS with time-range constraints | GCBS+Time · Berlin 1 256, 8-connected | problems solved in 30s (sum over 25 tests): 2,473 -> 4,413 | Helped |
| add conflicting paths strategy (TCP) on top of TCC (ablation) | GCBS+TCC · empty-48-48, 8-connected | problems solved in 30s (sum over 25 tests): 4,043 -> 5,271 | Helped |
| add conflicting paths strategy (TCP) on top of TCC (ablation) | GCBS+TCC · Boston 0 256, 8-connected | problems solved in 30s (sum over 25 tests): 6,021 -> 5,879 | Hurt |
| add conditional constraints / TCP to GCBS (ablation) | GCBS[16] · den520d 50 agents, 16-connected | solution cost: 7269 -> 7321 | No clear effect |
Closest papers by meaning
- Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures (AAAI 2025 · similarity 0.85)
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding (AAAI 2024 · similarity 0.85)
- Inapproximability of Optimal Multi-Agent Pathfinding Problems (AAAI 2025 · similarity 0.85)
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.84)
- Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding (AAAI 2025 · similarity 0.84)
- Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024 · similarity 0.84)
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.