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
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.
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≥3 , k<n
hB(s)=⌈k(s)d(s)⌉+p∈PB(s)∑⌈k(s)gp(s)⌉
7
C
I-shaped, n=2 , k=1
hC(s)=2(dv(s)+R(s)+F(s))−M(s)
8
D
L-shaped, n=3 , k=1
hD(s)=dv(s)+p∈PD(s)∑gp(s)
9
E
L-shaped, n=3 , k=2
hE(s)=dv(s)+p∈PE(s)∑⌈2gp(s)⌉−δ(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) or dv(s) is the relevant vertical distance; PX(s) (for X∈{B,D,E} ) is the set of blocking pieces on the goal path for class X ; gp(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 δ(s) is defined in Section 5.7 . Class C does not use an explicit blocking-piece set PC(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
≥ 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
≥ 13,681,738
61
4
B
SA*
33
≥ 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
Figure G1: An example of Class A. The goal is to find the shortest sequence of moves to reach the target state.
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.
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).
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.
Figure M14: This sequence demonstrates the optimal solution for moving the target piece from its initial state (0) to the final target state (6).
Figure O15: Some examples of challenging configurations beyond the reach of our algorithms.
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
Greedy Best-First Search (GBFS) is the dominant approach for solving search problems where the goal can be estimated with a heuristic, such as planning, route finding, navigation, and pathfinding. This is especially true when the memory is tightly constrained, such as planning on edge devices. To alleviate that, we present GONDOR (Greedy Online Navigation with Dynamic Outpost-based Re-search), a memory-efficient extension of GBFS that allows search to continue under strict memory limits by periodically compressing the search tree while retaining a sparse set of anchor states, then upon reaching the goal reconstructs the path by re-searching between the sparse states. We analyze the algorithm and discuss several variants defined by different outpost selection policies. In addition, we explore using Bloom filters for compact duplicate detection in the closed list. Experiments across numeric planning domains and heuristic configurations show that GONDOR consistently improves coverage under low memory budgets compared to standard GBFS. We release the implementation of GONDOR and the Bloom-filter variant to facilitate further research on memory-efficient heuristic search.
Yonatan Vernik, Alexander Tuisov, Alexander Shleyfman
Computer Science Department, Bar-Ilan University · Independent Researcher
Recent learning-based path planners use neural networks to process visual map representations and approximate heuristics for classical search algorithms, yielding near-optimal paths with reduced search effort. However, these methods are tied to the shortest-path objective implicit in their supervision, which limits their flexibility to accommodate alternative criteria. We introduce FlexPath, a two-stage framework that decouples feasibility from preference. In Stage 1, we use imitation learning to acquire a task-independent spatial prior over feasible paths from visual map inputs. In Stage 2, differentiable Path Shape Objectives (PSOs) adapt this prior toward task-specific criteria without relearning path structure, requiring only efficient objective-level adaptation. A single pretrained model can be adapted to multiple objectives. For shortest-path planning, FlexPath reduces search effort on TMP by 14.3% compared to the state-of-the-art TransPath, while also finding lower-cost paths on average and demonstrating strong zero-shot generalization across three unseen domains. For obstacle clearance with minimum clearance distance 2, it achieves 96.8% full obstacle avoidance while maintaining low search cost. The framework further extends to semantic-aware avoidance and waypoint guidance via objective-level adaptation, and remains compatible with classical planners at inference time. Data and code are available at https://github.com/FraunhoferIVI/FlexPath.