Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It
Davide Tateo, Jacopo Banfi, Alessandro Riva, Francesco Amigoni, Andrea Bonarini
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 |
|---|---|---|---|
| use depth-first search (DFS) instead of sample-based search (SB) for 2 agents | SB · Office, 150 px, 2 agents | instances solved out of 50: 38 -> 48 | Improved |
| use DFS instead of SB for 10 agents | SB · Office, 100 px, 10 agents | instances solved out of 50: 22 -> 14 | Hurt |
| use DFS instead of SB for 10 agents | SB · Open, 50 px, 10 agents | instances solved out of 50: 41 -> 22 | Hurt |
| use DFS instead of SB for 10 agents | SB · Open, 150 px, 10 agents | instances solved out of 50: 50 -> 41 | Hurt |
| use randomized SB (RSB) instead of SB for 10 agents | SB · Office, 50 px, 10 agents | instances solved out of 50: 33 -> 19 | Hurt |
| use RSB instead of SB for 10 agents | SB · Open, 50 px, 10 agents | instances solved out of 50: 41 -> 25 | Hurt |
| use RSB instead of SB for 10 agents | SB · Open, 150 px, 10 agents | instances solved out of 50: 50 -> 50 | No clear effect |
| increase communication range from 50 px to 150 px | SB · Office, 10 agents | instances solved out of 50: 33 -> 21 | Hurt |
| increase communication range from 50 px to 150 px | SB · Open, 10 agents | instances solved out of 50: 41 -> 50 | Improved |
| increase communication range from 50 px to 150 px | DFS · Office, 10 agents | instances solved out of 50: 16 -> 10 | Hurt |
| increase communication range from 50 px to 150 px | DFS · Open, 10 agents | instances solved out of 50: 22 -> 41 | Improved |
| increase team size from 2 to 10 agents | SB · Office, 100 px | instances solved out of 50: 42 -> 22 | Hurt |
Closest papers by meaning
- Solving Multiagent Path Finding on Highly Centralized Networks (AAAI 2025 · similarity 0.90)
- Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024 · similarity 0.89)
- Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures (AAAI 2025 · similarity 0.89)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.88)
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding (AAAI 2024 · similarity 0.88)
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · 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.
