Metraipolis › archive › dc_9fa5891460dc

Class-Based Heuristic Selection for Solving the Flying Block Puzzle — arXiv:2608.27476

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.27476
License (as archived)
CC0-1.0
Archived
2026-10-17T10:47:01.488Z
SHA-256 of the archived text
ab1a6562109e89e3871602ce36ae4d86227fc9b8a3d29877960a93c21029448e
Stable URL of this page
https://metraipolis.com/documento/dc_9fa5891460dc

How to cite

Class-Based Heuristic Selection for Solving the Flying Block Puzzle — arXiv:2608.27476 — arXiv (en), https://arxiv.org/abs/2608.27476 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9fa5891460dc (Metraipolis archive dc_9fa5891460dc, sha256 ab1a6562109e89e3871602ce36ae4d86227fc9b8a3d29877960a93c21029448e)
BibTeX
@misc{dc9fa5891460dc,
  title = {Class-Based Heuristic Selection for Solving the Flying Block Puzzle — arXiv:2608.27476},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.27476},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9fa5891460dc; sha256 ab1a6562109e89e3871602ce36ae4d86227fc9b8a3d29877960a93c21029448e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.27476. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Heuristic search underlies planning in autonomous systems ranging from warehouse logistics to robotic navigation, yet generic heuristics fail to exploit the structural constraints that govern constrained spatial domains, causing search performance to degrade catastrophically on harder instances. We study this problem through the two-column Flying Block Puzzle, a rigorously NP-complete spatial planning microworld whose bottleneck geometry mirrors clearance-to-size constraints encountered in multi-agent path finding, autonomous vehicle navigation, and block relocation systems. We introduce the Class-Based Heuristic A* (CBHA*) algorithm, which integrates a General Move Constraint to capture minimum displacement costs when vacant units are scarce, a formal kinematic taxonomy partitioning the state space into seven mutually exclusive classes with provably admissible heuristics based on vacancy ratio and goal-piece geometry, and a class-conditional tie-breaking mechanism that dynamically switches between depth-priority and vertical-distance ordering to overcome f-value plateaus. Over 146 benchmark instances, CBHA* achieves a 93.4% success rate against 64% for Depth-Prioritized A*, 39% for Standard A*, and 17% for BFS, while reducing node expansions by 87.98% relative to Standard A* and sustaining an average effective branching factor of approximately 3, demonstrating that class-triggered adaptive heuristics constitute a principled mechanism for efficient spatial planning that generalizes structurally to physical constraint systems.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-31 in cs.AI).
Categorie arXiv: Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2608.27476 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T10:33:42.326Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-08-31?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).