通过分类启发式策略，大幅提升复杂空间规划问题的求解效率。
Class-Based Heuristic Selection for Solving the Flying Block Puzzle
- 按状态分类设计启发式函数，结合空位比例与目标块几何特征。
- 在146个实例上成功率93.4%，节点扩展量减少87.98%。
- 适合需高效路径规划的机器人、自动驾驶及物流系统应用。
启发式搜索是自主系统中规划的核心，但在受限空间域中，通用启发式无法利用结构约束，导致难题实例性能崩溃。本文以双列飞行积木谜题这一严格NP完全的空间规划微型世界为研究对象，其瓶颈几何结构反映了多智能体路径规划、自动驾驶和积木重定位中的清障-尺寸约束。提出类基启发式A*（CBHA*）算法，融合通用移动约束以捕捉稀缺空位下的最小位移成本；建立基于运动学的七类状态划分，基于空位比和目标块几何生成可证明可接受的启发式；采用类条件冲突解决机制，动态切换深度优先与垂直距离排序，克服f值平台。在146个基准实例上，CBHA*成功率达93.4%，远超深度优先A*的64%、标准A*的39%和BFS的17%；相比标准A*，节点扩展减少87.98%，平均有效分支因子维持约3，证明类触发自适应启发式是高效空间规划的普适机制，可推广至具结构性物理约束的系统。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。