Class-Based Heuristic A* Improves Constrained Spatial Planning

Summary

Researchers introduce Class-Based Heuristic A* (CBHA*), an adaptive search algorithm for constrained spatial planning. Tested on 146 Flying Block Puzzle instances, it achieved a 93.4% success rate versus 64% for Depth-Prioritized A*, 39% for Standard A*, and 17% for BFS, while reducing node expansions by 87.98% relative to Standard A*. The method uses a move constraint, a seven-class kinematic taxonomy, admissible heuristics, and class-dependent tie-breaking. The authors suggest the design may transfer to robotic navigation, autonomous vehicles, multi-agent path finding, and block relocation systems.