Class-Based Heuristic Selection for Solving the Flying Block Puzzle

• URL: http://arxiv.org/abs/2608.27476v1
• Date: Thu, 20 Aug 2026 09:18:21 GMT
• Title: Class-Based Heuristic Selection for Solving the Flying Block Puzzle
• Abstract summary: Heuristic search underlies planning in autonomous systems ranging from warehouse logistics to robotic navigation.<n>We study this problem through the two-column Flying Block Puzzle, a rigorously NP-complete spatial planning microworld.<n>We introduce the Class-Based Heuristic A* algorithm, which integrates a General Move Constraint to capture minimum displacement costs.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Adaptive Error Budget Allocation for Fault-Tolerant Quantum Resource Estimation: A Metaheuristic Approach [0.14323566945483496]
  System-level resource estimation is a key component of fault-tolerant quantum computing toolchains.<n>We propose a training-free optimization framework that performs derivative-free search directly on the Azure Quantum Resource Estor.<n>We evaluate our framework across 433 circuits spanning 2 to 91 qubits from 31 families in the MQT Bench.
  arXiv  Detail & Related papers  (2026-08-16T07:14:29Z)
• LocalNav: Distilling Frontier VLMs and Embodied RL for On-Device Object Goal Navigation [53.88286427894783]
  Vision Language Models (VLMs) have emerged in the robotic domain as a powerful tool that enables environmental perception with language context.<n>Yet, their computational footprint typically confines them to cloud execution, hindering low-latency inference with local deployment on resource-constrained robots.<n>We present a distillation strategy that transfers complex spatial-semantic reasoning from large frontier models into a lightweight, 4B- parameter local VLM for edge execution on embedded GPU devices.
  arXiv  Detail & Related papers  (2026-06-26T09:11:59Z)
• Learning Reactive Dexterous Grasping via Hierarchical Task-Space RL Planning and Joint-Space QP Control [50.28263951510334]
  We propose a hybrid hierarchical control framework for reactive dexterous grasping.<n>The proposed framework explicitly decouples high-level spatial intent from low-level joint execution.<n>We extensively validate the proposed framework through a rigorous simulation-to-reality pipeline.
  arXiv  Detail & Related papers  (2026-05-05T04:49:38Z)
• O-ConNet: Geometry-Aware End-to-End Inference of Over-Constrained Spatial Mechanisms [6.353145241135741]
  O-ConNet is an end-to-end framework that infers mechanism structural parameters from only three sparse reachable points.<n>O-ConNet achieves Param-MAE 0.276 +/- 0.077 and Traj-MAE 0.145 +/- 0.018 on a self-constructed Bennett 4R dataset.<n>These results suggest that end-to-end learning can capture closed-loop structure and provide a practical route for inverse design of spatial over-constrained mechanisms.
  arXiv  Detail & Related papers  (2026-04-02T13:43:53Z)
• Adaptive-Horizon Conflict-Based Search for Closed-Loop Multi-Agent Path Finding [10.628717510399046]
  MAPF is a core coordination problem for large robot fleets in automated warehouses and logistics.<n>Existing approaches are either open-loop planners, which generate fixed trajectories, or closed-loops without reliable performance guarantees.<n>This paper presents ACCBS, a closed-loop built on a finite-horizon variant of CBS with a horizon-changing mechanism.
  arXiv  Detail & Related papers  (2026-02-12T14:55:16Z)
• Resolving Primitive-Sharing Ambiguity in Long-Tailed Industrial Point Cloud Segmentation via Spatial Context Constraints [9.6402526621774]
  Safety-critical components such as reducers and valves are systematically misclassified.<n>This work identifies a dual crisis unique to industrial 3D data extreme class imbalance 215:1 ratio.<n>We propose spatial context constraints that leverage neighborhood prediction consistency to disambiguate locally similar structures.
  arXiv  Detail & Related papers  (2026-01-27T02:52:28Z)
• QoS-Aware Hierarchical Reinforcement Learning for Joint Link Selection and Trajectory Optimization in SAGIN-Supported UAV Mobility Management [52.15690855486153]
  A space-air-ground integrated network (SAGIN) has emerged as an essential architecture for enabling ubiquitous UAV connectivity.<n>This paper formulates UAV mobility management in SAGIN as a constrained multiobjective joint optimization problem.
  arXiv  Detail & Related papers  (2025-12-17T06:22:46Z)
• CAHC:A General Conflict-Aware Heuristic Caching Framework for Multi-Agent Path Finding [0.0]
  We present textbfCAHC (Conflict-Aware Heuristic Caching), a general framework that caches values based on both state and relevant constraint context.<n>We demonstrate CAHC through a case study on CL-CBS for car-like robots, where we combine conflict-aware caching with an adaptive hybrid in textbfCARCHASE (Car-Like Robot Conflict-Aware Heuristic Adaptive Search Enhancement)<n>Our key innovations are (1) a compact emphconflict fingerprint that efficiently encodes which constraints affect a state's context, (2) a domain-adaptable
  arXiv  Detail & Related papers  (2025-12-13T08:42:18Z)
• Towards a Science of Scaling Agent Systems [79.64446272302287]
  We formalize a definition for agent evaluation and characterize scaling laws as the interplay between agent quantity, coordination structure, modelic, and task properties.<n>We derive a predictive model using coordination metrics, that cross-validated R2=0, enabling prediction on unseen task domains.<n>We identify three effects: (1) a tool-coordination trade-off: under fixed computational budgets, tool-heavy tasks suffer disproportionately from multi-agent overhead, and (2) a capability saturation: coordination yields diminishing or negative returns once single-agent baselines exceed 45%.
  arXiv  Detail & Related papers  (2025-12-09T06:52:21Z)
• Hierarchical Budget Policy Optimization for Adaptive Reasoning [49.621779447691665]
  We present Hierarchical Budget Policy Optimization (HBPO), a reinforcement learning framework that enables models to learn problem-specific reasoning depths without sacrificing capability.<n>HBPO partitions the exploration space into budget-constrained hierarchies (512-2560 tokens), each with differentiated reward structures that preserve both efficiency incentives and reasoning capabilities.<n>Extensive experiments demonstrate that HBPO reduces average token usage by up to 60.6% while improving accuracy by 3.14% across four reasoning benchmarks.
  arXiv  Detail & Related papers  (2025-07-21T17:52:34Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  We suggest learning the instance-dependent proxies that are supposed to notably increase the efficiency of the search. The first proxy we suggest to learn is the correction factor, i.e. the ratio between the instance independent cost-to-go estimate and the perfect one. The second proxy is the path probability, which indicates how likely the grid cell is lying on the shortest path.
  arXiv  Detail & Related papers  (2022-12-22T14:26:11Z)
• Tailored Learning-Based Scheduling for Kubernetes-Oriented Edge-Cloud System [54.588242387136376]
  We introduce KaiS, a learning-based scheduling framework for edge-cloud systems. First, we design a coordinated multi-agent actor-critic algorithm to cater to decentralized request dispatch. Second, for diverse system scales and structures, we use graph neural networks to embed system state information. Third, we adopt a two-time-scale scheduling mechanism to harmonize request dispatch and service orchestration.
  arXiv  Detail & Related papers  (2021-01-17T03:45:25Z)
• Evolving Search Space for Neural Architecture Search [70.71153433676024]
  We present a Neural Search-space Evolution (NSE) scheme that amplifies the results from the previous effort by maintaining an optimized search space subset. We achieve 77.3% top-1 retrain accuracy on ImageNet with 333M FLOPs, which yielded a state-of-the-art performance. When the latency constraint is adopted, our result also performs better than the previous best-performing mobile models with a 77.9% Top-1 retrain accuracy.
  arXiv  Detail & Related papers  (2020-11-22T01:11:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.