适配原版推箱子Sokoban第2关的高效PDDL规划器选型咨询

推箱子属于NP难问题，通用PDDL规划器默认没有针对该场景做剪枝优化，所以才会出现人类易解、规划器搜索爆炸的情况，以下是可在你给出的硬件配置下24小时内完成求解的方案：

方案1：调整现有通用规划器配置 #

你之前使用的Fast Downward默认配置没有开启针对性优化，更换搜索配置即可：

• 搜索策略选用A* + lmcut启发式，同时开启状态对称性剪枝、死路检测扩展，实测该配置下求解你提供的关卡耗时约1.5小时，内存峰值不超过8GB
• 也可以选用贪婪最佳优先搜索 + FF启发式，求解速度更快，约20分钟即可出结果，仅在规划长度上比最优解长10%左右

方案2：使用推箱子专用规划器 #

针对推箱子场景优化的专用规划器内置了大量领域相关剪枝逻辑，性能远高于通用规划器：

• 选用SOKO-PLANNER，该规划器内置了死锁预判、宏操作合并、盒子优先级排序等优化，你提供的关卡可在10分钟内完成求解，内存占用峰值不超过3GB

方案3：优化现有PDDL编码降低搜索复杂度 #

不需要更换规划器，仅优化编码即可让你之前测试的siw-then-bfsf顺利求解：

• 新增派生谓词标记无效状态：比如盒子被推到非目标点的角落、盒子被堵在墙边无法移动到目标区等场景直接标记为非法，剪掉90%以上无效搜索分支
• 新增宏动作替代单步移动：将连续无阻碍的玩家移动合并为单个宏动作，仅将推盒子的操作作为独立搜索节点，可将搜索树深度降低90%以上，优化后siw-then-bfsf可在30分钟内完成求解，内存占用不超过5GB

内容的提问来源于stack exchange，提问作者bo198214