文章背景与核心概要
本文研究了受限领域中的空间规划与启发式搜索局限性，采用飞行积木拼图（Flying Block Puzzle）这一严格的NP完全空间规划微观世界，旨在模拟机器人技术、仓储物流以及多智能体路径规划中常见的空间余隙与尺寸约束。
为了克服通用启发式算法在处理较难问题实例时出现的性能急剧下降问题，作者引入了基于类别的启发式 A*（CBHA*）算法。该方法具备以下特点： 一项通用移动约束（General Move Constraint），用于在空闲单元稀缺时计算最小位移成本； 一个形式化运动学分类体系，利用基于空闲率和目标拼块几何形状的可采纳启发式函数，将状态空间划分为七个互不排斥的类别； 一个类条件决胜机制（class-conditional tie-breaking mechanism）*，可在深度优先和垂直距离排序之间动态切换，以摆脱 \(f\) 值平台期。
在146个基准实例上的评估结果表明，CBHA* 取得了 93.4% 的成功率（相比之下，深度优先 A* 为 64%，标准 A* 为 39%，BFS 为 17%），同时与标准 A* 相比，节点扩展数减少了 87.98%。
Class-Based Heuristic Selection for Solving the Flying Block Puzzle
Class-Based Heuristic Selection for Solving the Flying Block Puzzle
Summary
Summary
本文探讨了受限领域中的空间规划与启发式搜索的局限性，所使用的工具是飞行积木拼图（Flying Block Puzzle）——这是一个严格的NP完全空间规划微观世界，旨在反映机器人学、仓储物流以及多智能体路径规划中发现的余隙与尺寸约束。
This paper investigates spatial planning and heuristic search limitations in constrained domains using the Flying Block Puzzle—a rigorously NP-complete spatial planning microworld designed to mirror clearance-to-size constraints found in robotics, warehouse logistics, and multi-agent path finding.
为了克服通用启发式算法在更困难的问题实例上出现的灾难性性能退化，作者引入了基于类别的启发式 A*（CBHA*）算法。该方法具有以下特点： * 一个通用移动约束，用于在空闲单元稀缺时处理最小位移成本。 * 一个形式化运动学分类法，利用基于空闲率和目标拼块几何形状的、可证明是可采纳的启发式方法，将状态空间划分为七个互斥的类别。 * 一个类条件决胜机制，在深度优先和垂直距离排序之间动态交替，以逃离 \(f\) 值平台期。
To overcome the catastrophic performance degradation of generic heuristics on harder problem instances, the authors introduce the Class-Based Heuristic A* (CBHA*) algorithm. This approach features: * A General Move Constraint to account for minimum displacement costs when vacant units are scarce. * A formal kinematic taxonomy partitioning the state space into seven mutually exclusive classes utilizing provably admissible heuristics based on vacancy ratios and goal-piece geometry. * A class-conditional tie-breaking mechanism that dynamically alternates between depth-priority and vertical-distance ordering to escape \(f\)-value plateaus.
在对 146 个基准实例进行评估后，CBHA* 实现了 93.4% 的成功率（相比之下，深度优先 A 为 64%，标准 A 为 39%，BFS 为 17%），同时相对于标准 A，节点扩展数减少了 87.98%*。
Evaluated over 146 benchmark instances, CBHA* achieved a 93.4% success rate (compared to 64% for Depth-Prioritized A, 39% for Standard A, and 17% for BFS), while reducing node expansions by 87.98% relative to Standard A*.
Document Metadata
Document Metadata
| 元数据字段 | 详情 |
|---|---|
| arXiv ID | arXiv:2608.27476 [cs.AI] |
| 学科 | 人工智能 (cs.AI) |
| 作者 | Sanyar Ahmadi, Pedram Asadzadeh, Amanj Khorramian |
| 提交日期 | 2026年8月20日 |
| 文档统计 | 27 页，15 张图表，2 个表格 |
| MSC 分类 | 68T20, 68Q25 |
| ACM 分类 | I.2.8; F.2.2 |
| DOI | 10.48550/arXiv.2608.27476 |
Metadata Field Details arXiv ID arXiv:2608.27476 [cs.AI] Subjects Artificial Intelligence ( cs.AI)Authors Sanyar Ahmadi, Pedram Asadzadeh, Amanj Khorramian Submission Date August 20, 2026 Document Stats 27 pages, 15 figures, 2 tables MSC Classes 68T20, 68Q25 ACM Classes I.2.8; F.2.2 DOI 10.48550/arXiv.2608.27476
Access & Resources
Access & Resources
- 全文选项： 查看 PDF | HTML（实验性） | TeX 源码
- 引用工具： Google Scholar | Semantic Scholar | NASA ADS
- Full-Text Options: View PDF | HTML (Experimental) | TeX Source
- Citation Tools: Google Scholar | Semantic Scholar | NASA ADS