基于前向状态空间搜索的启发式搜索算法是实现 FF 规划系统的主要技巧,该系统因比 HSP 系统更具优越性能而赢得了最近 AIPS-2000 规划竞赛的冠军。
Jun, 2011
通过研究动作的不同发生次数来分析导致规划正式化丧失可决定性的可能原因,使用多值偏序计划的概念实现了一个 NP 完全的数值规划片段,并研究了软性前提的优化技术。
Jul, 2023
该研究探讨了规划算法中启发式函数(heuristic functions)的作用,以及不同领域结构和搜索性能之间的关系,通过使用 NP 难问题 h + 函数(an idealized heuristic function)和 30 个广泛使用的基准测试领域的案例研究,发现许多规划领域具有相对容易的拓扑结构,并可通过域分析技术自动识别出这些拓扑现象。
Sep, 2011
介绍了 FFRob 算法,它使用 Extended Action Specification (EAS) 作为一般性的计划表示来支持任意谓词为条件。通过使用批量采样操纵基元和一个多查询路网结构来迭代离散化任务和运动规划问题,FFRob 可以有效地计算启发式,并结合几何和运动学规划约束,给出距离目标的紧密估计。同时,FFRob 也是概率上完备并且具有有限的期望运行时间。
Aug, 2016
本文介绍了基于对象导向工作台架构的时间最小承诺启发式搜索规划器 Model Checking Integrated Planning System(MIPS),它在国际规划大赛中表现出色,该规划器分离了显式和符号的直接搜索算法,是一个完整且最优的状态空间规划器。
本研究利用 COLIN 算法结合 LP 线性规划算法实现了 PDDL 的具体应用,支持经过规划的任务中存在线性计算,时刻变化等特殊表达形式,并且针对多参数的优化效果采用了混合整数编程算法进行优化。
Jan, 2014
通过学习来自 Scratch 的方法,我们提出了第一种能够学习无领域依赖规划启发式的方法。我们通过将规划问题的删除松弛表示的超图映射到通过超图从当前状态到目标的最小成本路径的成本估计来学习启发式。我们将图形网络推广到超图上学习,通过训练从最优成本计划中得到的状态 / 价值对来学习规划启发式。我们的实验表明,生成的 STRIPS-HGN 体系结构能够学习出与 LM-cut 等现有删除松弛启发式竞争的启发式,并且我们学习的启发式能够推广到不同的问题和领域。
Nov, 2019
Fast Downward 是一种基于启发式搜索的经典计划系统,它使用多值计划任务的另一种表示来计算其启发函数,称为因果图启发式函数,这与传统的基于忽略运算符负交互作用的 HSP 启发式函数非常不同。
提出了一种名为 Probabilistic-FF 的新的概率规划算法,该算法结合了 Conformant-FF 的技术和加权模型计数技术,可在具有概率部分不可观测性的问题上进行推理,并在各种概率域中显示出良好的可扩展性。
Oct, 2011
本文探讨了当无完整符号化模型可用时,如何使用 STRIPS 模型来改进基于机器学习的黑盒计划。我们的研究表明,这是一种提高黑盒计划效率的有效方式,超越了收集更多数据或调整机器学习架构。
Jul, 2022