用于解决飞行块难题的基于类的启发式选择

arXiv:2608.27476v1 公告类型：新 摘要：启发式搜索是从仓库物流到机器人导航等自主系统规划的基础，但通用启发式无法利用管理受限空间域的结构约束，导致搜索性能在更困难的情况下灾难性地降低。我们通过两列飞行块拼图来研究这个问题，这是一个严格的 NP 完全空间规划微观世界，其瓶颈几何形状反映了多智能体路径查找、自主车辆导航和块重定位系统中遇到的间隙到尺寸的约束。我们引入了基于类的启发式 A* (CBHA*) 算法，该算法集成了通用移动约束，以在空单元稀缺时捕获最小位移成本；正式的运动学分类法，将状态空间划分为七个互斥的类，并具有基于空位比和球门几何形状的可证明可接受的启发式；以及类条件打破平局机制，可在深度优先和垂直距离排序之间动态切换，以克服 f 值平台。在 146 个基准实例中，CBHA* 实现了 93.4% 的成功率，而深度优先 A* 为 64%，标准 A* 为 39%，BFS 为 17%，同时相对于标准 A* 减少了 87.98% 的节点扩展，并维持约 3 的平均有效分支因子，这表明类触发的自适应启发式算法构成了高效空间规划的原则性机制，可在结构上推广到物理约束系统。