Source-linked AI summary
Class-Based Heuristic Selection for Solving the Flying Block Puzzle
Sanyar Ahmadi, Pedram Asadzadeh, Amanj Khorramian
TL;DR
Generic heuristics struggle with the structural constraints of hard spatial-planning instances, studied here through the NP-complete two-column Flying Block Puzzle. CBHA* combines a general move constraint, seven-class kinematic heuristic selection, and class-conditional tie-breaking; it solves 93.4% of benchmark cases versus 64% for DPA*, 39% for SA*, and 17% for BFS.
Problem
Generic heuristics provide insufficient guidance in constrained spatial domains because they fail to represent geometric occlusion, cascading dependencies, and bottleneck clearance constraints.
Method
CBHA* combines an admissible General Move Constraint heuristic, a seven-class kinematic taxonomy with class-specific heuristics, and class-conditional depth or vertical-distance tie-breaking.
Results
93.4% success rate versus 64% for DPA*, 39% for SA*, and 17% for BFS across benchmark cases.
Takeaways & Limitations
Class-triggered heuristic switching and tie-breaker selection provide a structurally grounded approach to efficient spatial planning with parallels in other clearance-constrained domains.
Takeaways & Limitations
Performance gains are tied to the structural regularity of the 2-column variant, so wider or irregular domains require re-deriving the class partition.
Abstract
from arXiv · showhide
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.
1 Introduction
The two-column Flying Block Puzzle is an NP-complete spatial-planning testbed whose geometric bottlenecks resemble clearance constraints in robotics and logistics. CBHS addresses generic heuristics’ failure to exploit such structure through class-specific heuristic and tie-breaking selection.
- The 2-column Flying Block Puzzle is an NP-complete testbed requiring reasoning about geometric occlusion and cascading positional dependencies.
- Limited vacant cells force long sliding sequences, mirroring constraints in multi-agent path finding, warehouse robotics, and block relocation.
- Generic heuristics fail to exploit puzzle-specific structural properties and suffer scalability problems on larger instances.
- CBHS dynamically maps instance features to heuristic strategies by instantiating the algorithm-selection paradigm.
- The framework contributes a general admissible heuristic, DPA*, a seven-class taxonomy, and class-conditional depth or vertical-distance tie-breaking.
2 Problem Formulation and Properties
The puzzle places polyomino pieces in a 2 × h frame and seeks a minimum-cost sequence moving a target piece to its goal. Vacancy scarcity imposes formal movement, crossing, and flipping constraints.
- The state uses a width-2, height-h frame containing polyomino pieces, with gray cells occupied and white cells vacant.
- Pieces are classified into exhaustive shape types including I-shaped, L-shaped, and comb-shaped polyominoes.
- The objective is a minimum-length unit-cost move sequence placing the target piece at its designated goal.
- The General Move Constraint states that a piece of size n with k vacancies must preserve at least n−k occupied cells after any valid move.
- When k < n, pieces cannot jump; rectangular pieces with n > 2 cannot cross columns; comb pieces with k < s cannot flip horizontally.
3 Heuristic Development for A* Algorithm
The heuristic development begins with a primitive goal-occupancy lower bound and refines it using vacancy-limited displacement costs. The resulting general heuristic is consistent.
- The primitive heuristic counts non-target pieces occupying goal cells and adds one for every non-goal state.
- A blocking piece occupying g_i goal cells requires at least ⌈g_i/k⌉ moves to clear when k vacancies are available.
- The general heuristic is defined from the goal-cell set, blocking pieces, their occupied goal-cell counts, and the vacancy count.
- Theorem 5 establishes consistency because one move displaces at most k cells of a blocking piece, reducing ⌈g_p/k⌉ by at most one.
4 Depth-Prioritized A* Search
Standard heuristic values often form broad plateaus, limiting A* guidance. Depth-Prioritized A* resolves ties by expanding deeper nodes first, which performed best among tested criteria.
- The general heuristic can assign identical f-values across many frontier nodes, providing insufficient guidance when its range is small.
- Depth-priority breaks f = g + h ties by expanding nodes with greater root-to-node depth g first.
- Among misplaced units, piece-to-goal distance, and search depth, depth-priority performed best in the tested comparison.
5 Kinematic Taxonomy and State-Space Partitioning
The paper partitions puzzle states into seven kinematic classes determined by vacancy ratio and goal-piece geometry, assigning each class a consistent heuristic and a class-specific tie-breaker. The partition captures distinct movement constraints, including jumping, column crossing, blocking clearance, bypasses, and residual geometric cases.
- 5.1 Sufficiency: The Partition Tree: The seven-class partition is determined by vacancy ratio and goal-piece geometry, with each class admitting an admissible and consistent heuristic.Theorem 6 establishes that the partition is exact for states with k ≥1.
- 5.2 Class A: Class A covers k ≥ n, where jumping moves are available and the general heuristic is applied directly.The general heuristic is accurate in this regime because the goal piece can execute jumps.
- 5.4 Class B: Class B handles I-shaped pieces with n ≥3 and k < n, requiring same-column blockers to be cleared because the piece cannot cross columns.Its heuristic combines vertical distance, vacancy count, blocking pieces, and path occupancy; consistency is proved by Theorem 7.
- 5.5 Class C: Class C handles I-shaped pieces with n = 2 and k = 1, where rotation permits column crossing and each advance requires a clearing move, yielding a 2d lower bound.The heuristic also incorporates orientation, frame-side, and advance-readiness indicators.
- 5.6–5.7 Classes D–E: Classes D and E cover L-shaped pieces with k = 1 and k = 2, respectively; Class E uniquely exploits bypassing a size-1 blocker without removing it.Theorem 9 establishes consistency for Class D, while Theorem 10 handles the bypass case for Class E.
- 5.8–5.10 Classes F–G and tie-breaking: Classes F and G cover comb-shaped and residual symmetric cases, using blocker-clearance or vertical-distance heuristics, while tie-breaking switches by class.Depth tie-breaking is used for Classes A–E; vertical-distance tie-breaking is used for Classes F and G because ⌈d/k⌉ can remain unchanged across successive advances.
6 Results and Discussion
Across 146 instances, CBHA* substantially outperformed BFS, Standard A*, and DPA* by combining class-specific heuristics with adaptive tie-breaking, while remaining limited by extreme structural complexity and domain-specific design requirements.
- Overall performance: CBHA* solves 93.4% of cases versus 64% for DPA*, 39% for SA*, and 17% for BFS.These comparisons cover the seven puzzle classes and overall performance.
- Search efficiency: CBHA* reduces node expansions by 87.98% versus Standard A* and 91.31% versus BFS, with an average effective branching factor of 3.Its class-specific heuristics prune trajectories that are not kinematically relevant.
- Search efficiency: CBHA* explores average depths of 12, compared with 4–7 for the baselines, indicating focused rather than broad exploration.The depth comparison is reported alongside the effective branching-factor analysis.
- Limitations: Extreme configurations with coordinated movement of large blocking pieces create solution depths beyond the algorithms’ resource budget.The study also notes that CBHA* sacrifices generality and requires expert effort to derive taxonomies and provably consistent heuristics.
- Per-class behavior: Depth tie-breaking performs best in Classes A–E, whereas vertical-distance tie-breaking is more effective in Classes F and G.The optimal tie-breaking rule is class-dependent rather than universal.
- Per-class behavior: DPA* outperforms CBHA* only in Class G at small vertical distances, where hG is nearly zero and provides little guidance.The class-specific heuristic is therefore weak in these shallow-depth cases.
7 Methods
The evaluation uses 146 independently solved instances across seven kinematic classes, with four algorithms compared under shared representations and fixed resource limits. Reported averages distinguish successful-run efficiency from aggregate success and failure statistics.
- 146 test instances span seven kinematic classes and vary piece positions, piece types and sizes, vacant units, and solution depths.
- All four algorithms share state representation and move generation, while SA*, DPA*, and CBHA* use min-heaps with class-dependent ordering.SA* orders by f; DPA* uses (f, −g); CBHA* uses (f, −g) for Classes A–E and a different ordering for Classes F–G.
- Each instance was solved independently under a 12 GB RAM and 30-minute wall-clock budget, with limit-reaching runs recorded as failures.Failure statistics include expanded nodes and EBF at the limit, while successful-run averages exclude failed runs.
- Success rate measures solved instances, average node expansions and EBF cover successful runs, and average maximum depth covers all runs.Lower EBF indicates more focused search, whereas maximum depth reflects exploration breadth rather than solution quality.
- Aggregate comparisons exclude Class A and two Class A outliers, using instance-weighted means over Classes B–G.The excluded Class A instances have frame heights 200 and 500.
A Proofs of Theorem 1 (General Move Constraint), Corollary 2 (Jumping Move Constraint), and Corollary 3 (Crossing Constraint)
The General Move Constraint bounds how much of a piece can change position when vacancies are limited. Its consequences rule out jumping moves and certain cross-column transitions for sufficiently large pieces.
- For a piece of size n with k vacant cells, every valid move preserves at least n−k cells of the piece’s previous position.
- If k < n, the piece cannot execute a jumping move because a jump would require zero overlap with its previous position.
- A rectangular piece with n > 2 and k < n cannot move from one frame column to the other.Such a piece must occupy a vertical segment within one column, so changing columns would require a prohibited jump.
B Proof of Theorem 4 (Comb-Piece Flip Constraint)
The comb-piece flip constraint shows that insufficient vacancies prevent a comb-shaped piece from reaching its horizontally reflected configuration. The proof compares newly occupied cells with the comb’s free spaces.
- A comb-shaped piece with s free spaces cannot flip across its horizontal symmetry axis when k < s vacant cells are available.
- The proof assumes a valid flip, then uses reflection symmetry to show that all free spaces must become newly occupied.
- The General Move Constraint bounds newly occupied cells by k, while the reflected comb requires at least s, yielding the contradiction s ≤ k against k < s.
C Primitive Heuristic — Definition, Algorithm, and Consistency Proof
The primitive heuristic counts blocking pieces in the goal region and adds a non-goal indicator, yielding a consistent lower bound. The general heuristic refines it with vacancy-sensitive move counts, motivating class-specific heuristics when plateaus reduce guidance.
- The primitive heuristic hp(s) = |P(s)| + δ(s) counts distinct non-target pieces occupying goal cells and adds one for non-goal states.
- Algorithm C1 collects unique non-target pieces in goal positions and returns their count, adding one when the board is not solved.
- The general heuristic replaces unit blocking-piece contributions with vacancy-dependent lower bounds, using ⌈gi/k⌉ move counts while preserving consistency.Its consistency proof bounds each one-move decrease by one using the General Move Constraint.
- The primitive heuristic is consistent because each move changes its value by at most one under unit step costs.The proof handles non-target moves, target moves, and transitions into the goal state.
- When large blocking pieces meet limited vacancies, the primitive heuristic underestimates clearing cost and becomes less effective.
I Full Consistency Proof for the Class C Heuristic
The Class C heuristic is shown consistent by verifying zero value at the goal and a one-step decrease bound across all move cases.
- Goal-state condition: The proof establishes hC(sgoal) = 0 because vertical distance, rotation, frame-side discrepancy, and readiness terms all vanish at the goal.
- Triangle inequality: Consistency requires hC(s) − hC(s′) ≤1 for every single transition s → s′.
- Case analysis: Clearing a blocked front, advancing the goal piece, removing a frame-side discrepancy, and completing final placement each produce a net heuristic decrease of exactly 1.
- Remaining moves: All other moves change the heuristic by at most one, so the complete case analysis proves hC is consistent.
J Full Consistency Proof for the Class D Heuristic
The Class D consistency proof reduces to the Class B argument, replacing general cell-count distance with vertical distance under a single-vacancy constraint.
- Goal-state condition: The Class D heuristic is zero at the goal state, using zero vertical distance and no Class D blocking pieces.
- Triangle inequality: With k = 1, the ceiling distance bound is replaced by the direct relation dv −d′v ≤1.
- Case reduction: Because no piece can cross columns when k < n, orientation-change and frame-side terms are absent, leaving the three Class B cases exhaustive.
K Full Consistency Proof for the Class E Heuristic
The Class E consistency proof verifies the goal condition and bounds the heuristic change for vertical advances, bypasses, blocker removal, and bypass activation.
- Goal-state condition: The Class E heuristic equals zero at the goal because vertical distance, blocking-piece cost, and bypass status are all zero there.
- Triangle inequality: Consistency requires hE(s) − hE(s′) ≤1 for every single move.
- Move cases: A vertical advance reduces the goal-piece distance by at most one while leaving the other heuristic terms unchanged.
- Move cases: A size-1 bypass reduces vertical offset by two but removes the pointing requirement, yielding a net heuristic decrease of 1.
- Move cases: Removing occupied cells or activating the bypass condition changes the heuristic by at most one, completing the consistency proof.