Research map / Learning theory and algorithms / Combinatorial and search optimization
Optimal Pathfinding on Weighted Grid Maps
Mark Carlson, Sajjad K. Moghadam, Daniel D. Harabor, Peter J. Stuckey, Morteza Ebrahimi
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 diagonal branch pruning and prospective g pruning (ablation) | JPSW · Stripes maps | speedup over A* | Improved |
| Add orthogonal jump caching (ablation) | JPSW · Stripes maps | speedup over A* | Mixed |
| Combine pruning with a retained jump cache (ablation) | JPSW · Stripes maps | speedup over A* | Improved |
| Add diagonal branch pruning and prospective g pruning (ablation) | JPSW · City maps | speedup over A* | Improved |
| Add orthogonal jump caching and empty the cache between queries (ablation) | JPSW · City maps with lighter building terrain | speedup over A* | Improved |
| Add orthogonal jump caching and empty the cache between queries (ablation) | JPSW · City maps with heavier building terrain | speedup over A* | Mixed |
| Add diagonal branch pruning and prospective g pruning (ablation) | JPSW · Island and WC3 | speedup over A*: 8 and 4.5 times | Improved |
| Add orthogonal jump caching and empty the cache between queries (ablation) | JPSW · Multi-Terrain maps | speedup over A* | Improved |
| Add diagonal branch pruning and prospective g pruning (ablation) | JPSW · Guards | speedup over A* | Improved |
| Add orthogonal jump caching (ablation) | JPSW · Guards | speedup over A* | No clear effect |
| Use the basic neighbourhood successor and jumping rules without overscan fixes (ablation) | JPSW · Stripes maps | speedup over A* | Hurt |
| Use the basic neighbourhood successor and jumping rules without overscan fixes (ablation) | JPSW · Multi-Terrain maps | speedup over A* | Mixed |
Closest papers by meaning
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.85)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.84)
- Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search (AAAI 2024 · similarity 0.84)
- Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding (AAAI 2025 · similarity 0.84)
- Inapproximability of Optimal Multi-Agent Pathfinding Problems (AAAI 2025 · similarity 0.84)
- POGEMA: A Benchmark Platform for Cooperative Multi-Agent Pathfinding (ICLR 2025 · similarity 0.83)
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.
