AAAINov, 2015

一种基于符号 SAT 的 POMDP 几乎必达性小策略算法

PDF
TL;DR研究 POMDPs 的几乎确定可达性问题，提出了具有小内存的策略的符号算法，通过有效编码到 SAT 并使用 SAT solver 来解决问题。
pomdpsprobabilistic planningalmost-sure reachabilitymemory strategiessymbolic algorithm
发现论文，激发创造
  • 带安全可达目标的 POMDP 有界策略合成

    本文研究了带安全可达性目标的部分可观测马尔可夫决策过程（POMDPs），提出了一种基于目标约束信念空间和符号约束的方法来合成能实现安全可达性目标的策略，并通过实验结果表明，该方法能够在大量信念空间中高效地搜索有效策略。

    Jan, 2018

  • POMDP 中的最优成本几乎确定可达性

    本文研究部分可观察马尔可夫决策过程 (POMDPs)，带有一组目标状态并且每个转移都有一个整数成本。研究的最优化目标是在确保（概率为 1）几乎达到目标集时最小化预期总成本。我们证明，对于整数成本，近似最优成本是不可判定的。对于正成本，我们的结果有：（i）我们建立了最优成本的匹配下限和上限，上限是双指数；（ii）我们表明，近似最优成本的问题是可判定的，并且提出了建立在具有有限时间段目标的 POMDP 算法上的近似算法。虽然这个算法的最坏运行时间是双指数的，但我们还介绍了算法的有效停止标准，并实验性地表明它在许多有意义的示例中表现良好。

    Nov, 2014

  • 具有随时确定性保证的在线 POMDP 规划

    通过简化解决方案与理论上最优解之间的确定性关系，解决了在计算上昂贵的部分可观测马尔可夫决策过程（POMDPs）困难，为自主代理在不完全信息环境下的规划提供了确定性界限。

    Oct, 2023

  • 部分可观察马尔可夫决策过程的基于点的模型检验方法

    提出了一种在部分可观察的马尔可夫决策过程（POMDP）中实现满足线性时间逻辑公式的策略的方法，该方法使用基于点的价值迭代方法来高效地近似满足所需逻辑公式的最大概率，并计算相应的置信状态策略。证明该方法适用于大型 POMDP 领域，并为最终策略的性能提供了强大的边界。

    Jan, 2020

  • 无折扣 POMDP 中带有可达性目标的声音启发搜索值迭代

    该研究论文探讨了部分可观测马尔可夫决策过程（POMDPs）中的最大可达性概率问题（MRPP），研究了一种基于点估计方法和基于试探性启发式搜索的新算法，解决了处理无限时域问题中循环的问题，并在实验评估中表现出优越性。

    Jun, 2024

  • POMDP 的粒子信念逼近的最优性保证

    本文提出了利用基于粒子滤波置信转移模型的有限样本粒子置信 MDP 近似解决 POMDP 的方法。在五个基准 POMDP 实验中，与其他领先的连续观察 POMDP 求解器相比，表明这种方法可以实现与其他领先的连续观察 POMDP 求解器竞争力的表现。

    Oct, 2022

  • 搜索有限策略空间求解 POMDPs

    本文研究部分可观察马尔可夫决策过程（POMDPs）的解决方案，探讨如何从有限状态自动机的限制集合中找到最佳策略，进而展示了通过分支定界法和梯度上升法寻找全局最优确定性策略和局部最优随机策略的优越实验结果。

    Jan, 2013

  • 通过信念压缩寻找近似的 POMDP 解决方案

    该研究提出了一种用于解决大型部分观察马尔可夫决策过程（POMDPs）的算法，通过降低置信度空间的维度来进行策略逼近，其中采用了指数族主成分分析方法，并且该算法成功地应用于合成问题和移动机器人导航任务中。

    Jun, 2011

  • 部分可观察马尔可夫决策过程的值函数逼近

    本文介绍了部分可观测马尔可夫决策过程 (POMDP) 的近似（启发式）方法，研究其性质和关系，并提供一些新见解。该理论结果在代理导航领域的问题上得到了实验支持。

    Jun, 2011

  • 网格图可达性和益智游戏

    我们研究了求解迷宫类问题的 CP 和 SAT 方法，提出了一种新的可达性编码，并通过实验证明这种新编码在以 SAT 为范式的规划问题中，尤其是考虑到同时执行多个动作时是非常适用的。

    Oct, 2023