Jan, 2024

层次任务网络规划中的可解性边界

PDF
TL;DR层次任务网络规划中的复杂理论界限研究，包括提供计划的验证、可执行计划的存在性和给定状态是否可以通过某个计划到达等三个经典问题。研究发现，在常数偏序宽度（及其推广）的原始任务网络上，这三个问题均可以在多项式时间内解决，而对于后两个问题，只有在有关状态空间的明显必要限制下才成立。然后，提出了一个算法元定理和相应的下界，以确定使得一般多项式时间可解性结果从原始任务网络推广到一般任务网络的紧密条件。最后，通过分析三个问题的参数化复杂性，表明通过将网络的偏序宽度替换为网络的点覆盖数可以实现这三个问题的固定参数可解性，而网络的其他经典图论参数（包括树宽、树深度和前述的偏序宽度）则无法实现这三个问题的固定参数可解性。
hierarchy task network planningcomplexity-theoretic boundariespolynomial timepartial order widthparameterized complexity
发现论文，激发创造
  • 有限规划的完整参数化复杂度分析

    该论文研究了参数化复杂性下命题性规划问题的分类，重点关注了解决方案计划的长度参数和常见的句法限制，包括 PUBS 限制和条件 / 效果数量限制，并确定哪些问题适用于多项式内核，哪些不适用。

    Oct, 2013

  • 高血压和全序向前分解优化

    通过三阶段编译器设计优化预处理，构建基于 Hierarchical Task Networks 的 HTN planner，提高运行效率。

    Jul, 2022

  • 使用非时间启发式指导 HTN 时间规划中的搜索

    本文提出了一种使用现有启发式方法解决 HTN 问题的新型 POCL（偏序因果链接）方法，实验证明该方法表现优秀且能够优于现有方法，从而解决了缺乏正式和一致定义的时间分层规划问题的不便。

    Jun, 2023

  • 具有简单因果图的规划问题的复杂性

    本研究针对具有简单因果图的规划问题进行了三个新的复杂度结果研究。其中，针对具有二元状态变量和有向无环因果图的 3S 问题，我们提出了可用宏实现多项式时间复杂度的规划算法；同时，我们证明了具有多值变量和链式因果图的规划问题的方案存在问题为 NP - 难问题。最后，我们证明了具有二元状态变量和多叉树型因果图的规划问题的方案存在问题是 NP 完全问题。

    Oct, 2011

  • 用于最优经典计划的高维势启发式

    本研究尝试寻找一种比先前方法更有效的状态空间搜索算法，并通过构造新的图形结构来实现可行性和可解性的结果。

    Sep, 2019

  • 数字规划中的多值部分有序计划

    通过研究动作的不同发生次数来分析导致规划正式化丧失可决定性的可能原因，使用多值偏序计划的概念实现了一个 NP 完全的数值规划片段，并研究了软性前提的优化技术。

    Jul, 2023

  • 层次化计划中遇到截止日期的概率估计

    针对含不确定性任务时间的分层计划（或时间表），我们提出了一种确定性多项式算法以估计其在特定期限前完成的概率，或者，其 ' 完成时间 ' 小于给定持续时间的概率。对于我们提出的近似算法，我们建立了形式化的逼近界限，并通过任务网络对其进行实证验证，在精度和运行时间方面优于采样技术和精确计算。

    Mar, 2015

  • 泛化规划：非确定性抽象和轨迹约束

    本文研究了具有共同特征的问题集合的一般策略的特征和计算，并介绍了如何通过利用轨迹约束以及 LTL 公式来消除策略的终止条件以及降低规划的复杂度。

    Sep, 2019

  • 超树分解与可处理查询

    本文研究了关于合取查询 (conjunctive queries) 的一些决策问题，发现针对无环或几乎无环查询的问题虽然一般来说是 NP 完全，但限制到这些查询中节点的树宽度和循环度是有界的，变得易于处理。针对查询的宽度这一最普遍的概念，我们证明没有多项式时间的算法可以高效地判断查询的宽度是否小于等于 k，而引入的超树分解概念和超树宽度则可以周旋这一难点，使得相应的问题变得可解。

    Dec, 1998

  • 阈值树宽和超树宽

    介绍了树宽和超树宽的概念，并通过计算阈值树宽和超树宽，提出了一种固定参数算法，可在多项式时间内解决 CSP 问题。

    Oct, 2022