有限规划的完整参数化复杂度分析
研究人员利用参数化复杂性的框架提出了基于经验案例规划中的计划重用问题的理论结果,并对该问题的几种变体进行了参数化复杂性分析,特别地,我们考虑了重用现有计划的问题,并对相关的限制条件采用参数进行了讨论。
Jul, 2013
研究了具有平面和命题表示的概率规划领域中测试和寻找小规划的计算复杂性,发现问题的复杂性分别属于 PL,P,NP,co-NP,PP,NP^PP,co-NP^PP 和 PSPACE,提出了一个新的基本 NP^PP 完全问题 E-MAJSAT,表明 E-MAJSAT 问题的启发式算法的开发对于广泛问题的高效算法很重要。
Aug, 1998
本文研究了与基于案例规划相关的问题的计算复杂性:当已知类似实例的计划时进行规划,以及从计划库进行规划。我们证明了从单个案例进行规划的复杂性与生成式规划(即从头开始规划)相同;使用案例的扩展定义,如果案例中存储的领域与搜索计划的领域相似,则可以减少复杂度。从计划库进行规划的复杂性也得到了证明是相同的。在这两种情况下,规划的复杂性在最坏情况下仍为 PSPACE-complete。
Jul, 2004
层次任务网络规划中的复杂理论界限研究,包括提供计划的验证、可执行计划的存在性和给定状态是否可以通过某个计划到达等三个经典问题。研究发现,在常数偏序宽度(及其推广)的原始任务网络上,这三个问题均可以在多项式时间内解决,而对于后两个问题,只有在有关状态空间的明显必要限制下才成立。然后,提出了一个算法元定理和相应的下界,以确定使得一般多项式时间可解性结果从原始任务网络推广到一般任务网络的紧密条件。最后,通过分析三个问题的参数化复杂性,表明通过将网络的偏序宽度替换为网络的点覆盖数可以实现这三个问题的固定参数可解性,而网络的其他经典图论参数(包括树宽、树深度和前述的偏序宽度)则无法实现这三个问题的固定参数可解性。
Jan, 2024
本论文介绍了一种名为 “编译方案” 的概念,并使用这种概念分析了一大类命题规划命题形式的表达能力,结果确认了 GRAPHPLAN 算法中有关条件效应的扩展是优化的,同时发现允许在先决条件和效果条件中使用一般命题公式会给生成计划带来额外的 Schwierigkeit。
Jun, 2011
通过研究动作的不同发生次数来分析导致规划正式化丧失可决定性的可能原因,使用多值偏序计划的概念实现了一个 NP 完全的数值规划片段,并研究了软性前提的优化技术。
Jul, 2023
该研究以逻辑程序模型为背景,讨论了固定参数复杂度、参数化决策问题以及稳定模型等方面的研究,发现设置模型边界以解决问题的算法并不可行,提出了对于多项式时间算法的更好期望。
Jul, 2001
本研究针对具有简单因果图的规划问题进行了三个新的复杂度结果研究。其中,针对具有二元状态变量和有向无环因果图的 3S 问题,我们提出了可用宏实现多项式时间复杂度的规划算法;同时,我们证明了具有多值变量和链式因果图的规划问题的方案存在问题为 NP - 难问题。最后,我们证明了具有二元状态变量和多叉树型因果图的规划问题的方案存在问题是 NP 完全问题。
Oct, 2011
本文提出了一种基于动态认知逻辑 (DEL) 的新型算法,该算法限制了规划代理的推理深度为一个上界 b,以模态深度 b 为最多的高阶知识进行推理。算法利用了一种新型的 b-bisimulation 收缩确保了最小模型的唯一性。我们证明了深度有界规划算法是正确的。此外,我们证明了在推理深度的限制 b 内具有解决方案的规划任务的完备性(因此按照标准定义的迭代界限增加变体是完备的)。在推理深度的限制 b 下,该算法被证明是 (b + 1)-EXPTIME 完全,同时在代理和原子的数量上是固定参数可处理的。我们提供了算法的树搜索和图搜索变体,并将树搜索版本的实现与基准认知规划器进行了基准测试。
Jun, 2024
本篇论文研究条件规划问题,从传统规划的角度出发,探索运用可满足性算法,采用量化布尔公式表达的方法,解决条件规划中存在的不确定性和非确定性问题,并给出实验结果。
May, 2011