Jun, 2024

深度有界认知规划

PDF
TL;DR本文提出了一种基于动态认知逻辑 (DEL) 的新型算法，该算法限制了规划代理的推理深度为一个上界 b，以模态深度 b 为最多的高阶知识进行推理。算法利用了一种新型的 b-bisimulation 收缩确保了最小模型的唯一性。我们证明了深度有界规划算法是正确的。此外，我们证明了在推理深度的限制 b 内具有解决方案的规划任务的完备性（因此按照标准定义的迭代界限增加变体是完备的）。在推理深度的限制 b 下，该算法被证明是 (b + 1)-EXPTIME 完全，同时在代理和原子的数量上是固定参数可处理的。我们提供了算法的树搜索和图搜索变体，并将树搜索版本的实现与基准认知规划器进行了基准测试。
epistemic planningdynamic epistemic logicdepth-bounded planning algorithmcanonical b-bisimulation contractiontree search
发现论文，激发创造
  • 深度有限的认知逻辑

    DBEL 是 S5 的扩展，用来模拟深度有限的代理人进行关于知识公式的推理，同时添加了深度原子 Ead 和 Pad，扩展了公开声明逻辑的公理，解决了遗忘和知识泄漏等问题，并用这些逻辑来解决经典的泥泞孩子问题。

    Jul, 2023

  • 语义方法在认知规划中的可决定性（扩展版）

    利用动态认知逻辑（DEL）的多代理规划在处理非确定性、部分可观察性和任意知识嵌套方面具有广泛应用的行动形式主义中，我们通过一种新颖的语义方法达到可决定性的目标。我们展示了该框架具有可决定的特性，并研究了其他扩展的交换公理以实现更复杂的 DEL 的决定性。

    Jul, 2023

  • DELPHIC 实用 DEL 规划能力控制 (扩展版)

    用 DELPHIC 框架替代传统的 Kripke 模型，实现更紧凑的认知状态表示，并通过实验评估证实其在空间和时间上优于传统方法。

    Jul, 2023

  • 基于高阶信念变化的通用多智能体认知规划器

    提出了一种多代理认知规划的表示语言，解决了现有编译成经典计划所面临的各种限制，包括只能生成线性计划、限制公共行动和无法处理分离信念等问题。

    Jun, 2018

  • 有限置信推理的复杂性 - 无量词情况

    本文研究在信念水平下进行推理的计算复杂性，并进行了参数化复杂性理论的进一步细化，探究信念水平和非逻辑符号数量对复杂性的影响。

    May, 2018

  • 关于动态认知逻辑的复杂性

    本研究使用合法及完整的插入表技术，证明 DEL 语言中事件模型的模型检查问题是 PSPACE 完全的，并证明了满足性问题是 NEXPTIME-complete 的。

    Oct, 2013

  • ASP 中的多智体认知规划建模

    本文介绍了一种基于声明式编程技术的多智能体认知情境下的推理问题的解决方案，即 PLATO（基于 ePistemic 多智能体 Answer Program 解决方案），利用自定义认知状态表征和 ASP 求解器的效率，在从文献中收集的基准测试中取得了有竞争力的性能结果，并为其正确性开发了形式验证。

    Aug, 2020

  • 有限规划的完整参数化复杂度分析

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

    Oct, 2013

  • 自适应概率信赖约束下的连续高维信念空间规划

    研究了基于信念空间规划的在线决策问题，在信息收集等场景下，介绍了一种自适应的方法来寻求最大可行回报，应用这种方法可以在保证准确率的前提下显著加速在线决策过程，并进行了大量现实模拟来验证此方法的优越性。

    Feb, 2023

  • 感知规划的因果信念分解：完备性结果和实用逼近

    本文扩展了一种在规划中处理基于感知的信念跟踪的算法，该算法在可自定义的时间和空间范围内找出最可能的信念。此外，我们还引入了一种快速而有效的近似方法，该方法在时间和空间复杂度上都是指数级的，使算法可在高度宽但低因果宽度的领域中展现出最先进的实时性能。

    Sep, 2019