用于最优经典计划的高维势启发式
LatPlan 通过无标签图像数据学习领域无关的经典计划器模型,提出了基于可信性的启发式方法 PBH,可以显著提高图像拼图和汉诺塔领域的有效解决方案数量。
Jun, 2023
提供了一种基于状态距离测量的置信状态距离估计框架,利用聚合状态距离度量的方法来定义置信状态之间的距离,实现了一些技术来聚合状态距离及其关联属性,提出了几种规划图启发式方法的广义形式,利用 BDD 来计算最有效的技巧,这些启发式方法在两个规划器上得到了有效应用。
Mar, 2011
层次任务网络规划中的复杂理论界限研究,包括提供计划的验证、可执行计划的存在性和给定状态是否可以通过某个计划到达等三个经典问题。研究发现,在常数偏序宽度(及其推广)的原始任务网络上,这三个问题均可以在多项式时间内解决,而对于后两个问题,只有在有关状态空间的明显必要限制下才成立。然后,提出了一个算法元定理和相应的下界,以确定使得一般多项式时间可解性结果从原始任务网络推广到一般任务网络的紧密条件。最后,通过分析三个问题的参数化复杂性,表明通过将网络的偏序宽度替换为网络的点覆盖数可以实现这三个问题的固定参数可解性,而网络的其他经典图论参数(包括树宽、树深度和前述的偏序宽度)则无法实现这三个问题的固定参数可解性。
Jan, 2024
本研究提出了一种新的基于指针的 GP 解空间、评估和启发式函数,以及 BFGP 算法,为了实现 GP 的启发式搜索,避免了提前 grounding state 或 action 所带来的问题,能有效处理大型状态变量集合和大量数值域的情况。
Jan, 2023
本文利用 Bidirectional A * 算法及三种启发式算法(曼哈顿距离、线性位差和行走距离)解决了 Fifteen Puzzle 问题,并将这三种启发式算法混合运用,有效减少了算法生成状态数和扩展节点数,大大降低了空间复杂度,保证了最优解或接近最优解。
Jan, 2023
本论文重新审视了启发式函数在规划中的模仿学习中的必要和充分条件,并针对给定的前向搜索算法的变体提出了一族基于排名的损失函数。另外,从学习理论的角度讨论了为什么优化成本 - 目标 h * 是不必要困难的。实验比较在多样化的问题集上明确地支持了得出的理论。
Oct, 2023
这篇研究报告讨论了如何解决 NP-Complete 决策问题中的 “相位边界” 问题,介绍了在 K-SAT 中发生的相变的解析解和实验研究。其中,在计算代价随问题规模呈指数级增长的情况下,首次发现了 “随机一阶相变” 的本质,并提出了可能的搜索启发式算法改进方案来应对决策问题中的 “脊骨”。
Oct, 1999
本文提出了一种可有效设计和实现通用游戏空间状态 - 动作特征的方法,并提供了适用于广泛不同游戏使用的设计和具体实现,这种方法可以训练出符合本地区域状态变量的特征,以此来激励或者抑制动作。
Jan, 2022
本研究介绍了一种利用启发式算法解决定理证明和计划制定问题的方法,并将其应用于 situation calculus 中。该方法通过使用 A * 搜索算法排列一系列情境,并利用删除松弛法控制启发式规划器,获得较短的计划方案,并探索较少的状态。实验表明,该方法可以应用于较大规模的问题。
Mar, 2023