Class-Based Heuristic Selection for Solving the Flying Block Puzzle

Sanyar Ahmadi; Pedram Asadzadeh; Amanj Khorramian

cs.AIAug 20, 2026

Class-Based Heuristic Selection for Solving the Flying Block Puzzle

Authors: Sanyar Ahmadi, Pedram Asadzadeh, Amanj Khorramian

Organizations: Faculty of Computer Engineering University of Tehran Tehran, Iran · Faculty of Computer Engineering K. N. Toosi University of Technology Tehran, Iran · Department of Electrical and Computer Engineering University of Kurdistan Sanandaj, Iran

Abstract

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.

Figures & tables

Figure 1: Categorization of polyomino pieces in the Flying Block puzzle.

Figure 2: Unsolvable instances illustrating the three solvability constraints of Section 2 . Each panel shows an initial state (left) and the target goal position (right). (a) Unreachable due to the Jumping Move Constraint (Corollary 2 ): both the target piece and the blocking piece have size greater than the number of vacant units, so neither can execute a jumping move and the target piece cannot bypass the blocker to reach the goal. (b) Unreachable due to the Crossing Constraint (Corollary 3 ): the target piece is an I-shaped piece of size 3 with fewer than three vacant units; it cannot cross to the opposite column where the goal position is located. (c) Unreachable due to the Comb-Piece Flip Constraint (Theorem 4 ): the target piece is a comb-shaped piece with three free spaces, but the number of vacant units is strictly less than three, so the comb cannot flip across its horizontal axis of symmetry to align with the goal.

Figure 3: Worked examples motivating the general and class-based heuristics. (a–b) General heuristic: initial/final states and the optimal-solution sequence (Section 3 , General Heuristic). (c) Motivating example for class-based heuristic selection: target state and the full 15-state optimal sequence, showing the general heuristic plateaued at $h=3$ across states 1–11 before decreasing over the final four states to the true goal at state 15.

Panel of Figure 4 — Figure 4: Illustration of a puzzle solved in 4 moves, highlighting the optimal path. The figure shows how depth prioritization improves search efficiency by prioritizing deeper states with the same $f$ -value, allowing the algorithm to focus on more promising paths and reach the goal faster.

Class	Conditions	Heuristic formula	Theorem
B	I-shaped, $n\geq 3$ , $k<n$	$h_{B}(s)=\displaystyle\Bigl\lceil\frac{d(s)}{k(s)}\Bigr\rceil+\sum_{p\in P_{B}(s)}\Bigl\lceil\frac{g_{p}(s)}{k(s)}\Bigr\rceil$	7
C	I-shaped, $n=2$ , $k=1$	$h_{C}(s)=2\bigl(d_{v}(s)+R(s)+F(s)\bigr)-M(s)$	8
D	L-shaped, $n=3$ , $k=1$	$h_{D}(s)=d_{v}(s)+\displaystyle\sum_{p\in P_{D}(s)}g_{p}(s)$	9
E	L-shaped, $n=3$ , $k=2$	$h_{E}(s)=d_{v}(s)+\displaystyle\sum_{p\in P_{E}(s)}\Bigl\lceil\tfrac{g_{p}(s)}{2}\Bigr\rceil-\delta(s)$	10

Table 1: Closed-form heuristic definitions for Classes B–E. All heuristics assume unit step costs.

k(s)

is the number of vacant units;

d(s)

d_{v}(s)

is the relevant vertical distance;

P_{X}(s)

(for

X\in\{B,D,E\}

) is the set of blocking pieces on the goal path for class

X

;

g_{p}(s)

is the number of path-cells occupied by piece

p

. Class C indicators

R(s)

F(s)

M(s)

are defined in Section 5.5 ; the Class E indicator

\delta(s)

is defined in Section 5.7 . Class C does not use an explicit blocking-piece set

P_{C}(s)

; obstruction costs for this class are subsumed in the orientation penalty

R(s)

and the frame-side discrepancy

F(s)

(Section 5.5 ).

Figure 5: Performance comparison of BFS, SA*, DPA*, and CBHA* across the seven kinematic classes (A–G) and overall. Panel (a): success rate (%); (b): average expanded nodes (log scale); (c): average effective branching factor (log scale); (d): average maximum depth explored.

Class	Algorithm	$N$	Success (%)	Avg. nodes	EBF	Avg. max depth
A	BFS	32	28	$\geq$ 8,955,252	144	3
A	SA*		87	1,626,488	16	3.8
A	DPA*		100	8,941	4	4
A	CBHA*		100	8,941	4	4
B	BFS	24	25	$\geq$ 13,681,738	61	4
B	SA*		33	$\geq$ 10,765,203	15	5

Table 2: Full experimental results by algorithm and class: number of instances, success rate, average expanded nodes, effective branching factor (EBF), and average maximum solution depth. Overall success rates cited in the text are weighted averages over all 146 instances.

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 8 — Figure G1: An example of Class A. The goal is to find the shortest sequence of moves to reach the target state.

Panel of Figure 9 — Figure G2: This sequence demonstrates the optimal solution for moving the target piece from its initial state (0) to the final target state (4), with the computed heuristic value for Class A provided below each state.

Panel of Figure 10 — Figure G3: An example of Class C. The goal is to find the shortest sequence of moves to reach the target state.

Figure H4: Class B heuristic adjustments.

Figure I5: Four cases of the Class C consistency proof (Cases A–D).

Panel of Figure 13 — Figure K6: Example of the goal piece sliding past a blocking piece of size 1, demonstrating the corresponding decrease in heuristic estimation.

Figure L7: Comparison of execution times and effective branch factors for different algorithms (BFS, SA*, DPA*, and CBHA*) across various case scenarios of Class A.

Figure L8: Comparison of execution times and effective branch factors for different algorithms (BFS, SA*, DPA*, and CBHA*) across various case scenarios of Class B.

Figure L9: Comparison of execution times and effective branch factors for different algorithms (BFS, SA*, DPA*, and CBHA*) across various case scenarios of Class C.

Figure L10: Comparison of execution times and effective branch factors for different algorithms (BFS, SA*, DPA*, and CBHA*) across various case scenarios of Class D.

Figure L11: Comparison of execution times and effective branch factors for different algorithms (BFS, SA*, DPA*, and CBHA*) across various case scenarios of Class E.

Figure L12: Comparison of execution times and effective branch factors for different algorithms (BFS, SA*, DPA*, and CBHA*) across various case scenarios of Class F.

Figure L13: Comparison of execution times and effective branch factors for different algorithms (BFS, SA*, DPA*, and CBHA*) across various case scenarios of Class G.

Panel of Figure 21 — Figure M14: This sequence demonstrates the optimal solution for moving the target piece from its initial state (0) to the final target state (6).

Panel of Figure 22 — Figure O15: Some examples of challenging configurations beyond the reach of our algorithms.

Tree Search

Tree Search explores branching sequences of actions or decisions to find high-quality solutions under limits on time, memory, or computation.

See all 57 papers

Bidirectional Incremental Generalized Hybrid A*
May 28, 2026Sidharth Talia, Oren Salzman, Siddhartha SrinivasaKinodynamic Motion Planning Tree Search
GONDOR to the Rescue: Satisficing Planning with Low Memory
May 27, 2026Yonatan Vernik, Alexander Tuisov, Alexander ShleyfmanTree Search Memory-Efficient Optimization
Computer Science Department, Bar-Ilan University · Independent Researcher
FlexPath: Learned Semantic Path Priors for Image-Based Planning
Jun 8, 2026Taehyoung Kim, Tim Schoenbrod, David Eckel +1Motion Planning
Fraunhofer IVI · Technische Hochschule Ingolstadt

May 28, 2026J/K move · Enter open · S save

Bidirectional Incremental Generalized Hybrid A*

Sidharth Talia, Oren Salzman, Siddhartha Srinivasa

Kinodynamic Motion Planning Tree Search Graph-Based Planning Motion Planning Robot Motion Planning

Open paper AskPDF arXiv

We focus on the problem of efficient anytime kinodynamic planning for systems with complex dynamics in unstructured environments that make using precomputed motion primitives infeasible. Directly applying A* here is computationally infeasible due to the curse of dimensionality. Methods such as Hybrid A* (HA*) address this by pruning the search tree by discretizing the state space, but the coupling between pruning and discretization resolution can eliminate a vertex on the solution path. The Incremental Generalized Hybrid A* (IGHA*) breaks this coupling by organizing anytime search over a hierarchy of resolutions and by freezing vertices for later expansion rather than pruning. However, IGHA* can still freeze a vertex on the solution path, forcing the search to spend expansions elsewhere before reaching it. Our key insight is that bidirectional-IGHA* (Bi-IGHA*) not only gains the expected reduction in effective search depth from classical bidirectionality, but also mitigates this frozen-vertex barrier: when one search is blocked, the opposing search can reach it at a low resolution. We formalize this structural separation between Bi-IGHA* and IGHA* and empirically show a reduction in effective branching factor beyond the theoretical expectation from classic bidirectionality alone. Through open- loop experiments in R3, R4, and R6, we show that Bi- IGHA* substantially reduces expansions over IGHA*. Closed- loop experiments further demonstrate improved performance and feasibility in simulation and on a real-world robotic system. Link to Website: https://personalrobotics.github.io/IGHAStar/biighastar.html

Abstract

Tree Search

Explore similar work

Bidirectional Incremental Generalized Hybrid A*

GONDOR to the Rescue: Satisficing Planning with Low Memory

FlexPath: Learned Semantic Path Priors for Image-Based Planning