Research map / Learning theory and algorithms / Combinatorial and search optimization
Grid Pathfinding on the 2k Neighborhoods
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 |
|---|---|---|---|
| increase neighborhood from 4 to 8 | regular A* with 2^k-tile heuristic · Starcraft maps | solution cost: 804.2 -> 668.0 | Helped |
| increase neighborhood from 32 to 128 | regular A* with 2^k-tile heuristic · Starcraft maps | solution cost: 637.0 -> 634.8 | No clear effect |
| increase neighborhood from 4 to 128 | regular A* with 2^k-tile heuristic · Starcraft maps | runtime (ms): 10.59 -> 60.32 | Hurt |
| increase neighborhood from 4 to 128 | regular A* with 2^k-tile heuristic · BG maps | solution cost: 304.6 -> 236.3 | Helped |
| increase neighborhood from 4 to 128 | regular A* with 2^k-tile heuristic · WC3 maps | solution cost: 245.3 -> 197.3 | Helped |
| replace Euclidean with 2^k-tile heuristic in regular A* | regular A* 8-neighborhood · Starcraft maps | runtime (ms): 17.40 -> 12.98 | Helped |
| replace Euclidean with 2^k-tile heuristic in regular A* | regular A* 4-neighborhood · Starcraft maps | runtime (ms): 25.42 -> 10.59 | Helped |
| replace Euclidean with 2^k-tile heuristic in regular A* | regular A* 128-neighborhood · Starcraft maps | runtime (ms): 60.84 -> 60.32 | No clear effect |
| add canonical ordering to A* with 2^k-tile heuristic | A* 128-neighborhood · Starcraft maps | runtime (ms): 60.32 -> 15.29 | Helped |
| add canonical ordering to A* with 2^k-tile heuristic | A* 4-neighborhood · Starcraft maps | runtime (ms): 10.59 -> 8.79 | Helped |
| replace Euclidean with 2^k-tile heuristic in canonical A* | canonical A* 4-neighborhood · Starcraft maps | runtime (ms): 23.67 -> 8.79 | Helped |
| replace Euclidean with 2^k-tile heuristic in canonical A* | canonical A* 128-neighborhood · Starcraft maps | runtime (ms): 14.20 -> 15.29 | Hurt |
Closest papers by meaning
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.86)
- 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)
- LNS2+RL: Combining Multi-agent Reinforcement Learning with Large Neighborhood Search in Multi-agent Path Finding (AAAI 2025 · similarity 0.85)
- On Conformal Isometry of Grid Cells: Learning Distance-Preserving Position Embedding (ICLR 2025 · similarity 0.84)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (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.