IJCAIMay, 2024

使用多智能体 A* 近似求解 Dec-POMDP

PDF
TL;DR我们提出了一种基于 A * 算法的有限时域 Dec-POMDPs 策略计算方法，目标是以可扩展性为代价来牺牲最优性，在较大的时域内取得竞争性性能，主要特点是使用聚类的滑动窗口内存、修剪 A * 搜索树以及使用新颖的 A * 启发式策略。我们的实验结果显示与最先进的方法相比有竞争力的性能，并且在多个基准测试中取得了更优异的表现。此外，我们还提供了一种基于 A * 算法的找到最优值上界的方法，适用于长时域问题。主要特点是定期揭示状态的新启发式方法，从而限制可达置信度的数量。我们的实验证明了该方法的有效性和可扩展性。
finite-horizon dec-pomdpsa*-based algorithmclustered sliding window memorypruningnovel a* heuristics
发现论文，激发创造
  • MAA*: 解决分散式 POMDPs 的启发式搜索算法

    本文介绍了多智能体 A*（MAA*），这是第一种完整的和最优的启发式搜索算法，可用于解决具有有限时间视野的分散式部分可观测马尔可夫决策问题（DEC-POMDP）。该算法适用于在随机环境中操作的合作代理组的最优计划的计算，例如多机器人协调、网络流量控制或分布式资源分配。

    Jul, 2012

  • Dec-POMDP 中增量聚类和扩展以加速最优规划

    文章介绍了分散式不完全可观察马尔可夫决策过程（Dec-POMDPs）的最优解决方法，其中引入了广义多智能体 A * 算法（GMAA*），合成了增量聚类与增量展开，并提出了新的混合启发式表示，能够优化解决大规模 Dec-POMDPs 的问题。

    Feb, 2014

  • Dec-POMDP 中的平衡 Monte-Carlo 搜索

    本文介绍了一种基于模拟的 POMDP 求解器来构建 Dec-POMDP 的有限状态控制器节点以及一种相关的方法来启发式地导出初始 FSC，称为 MC-JESP，实验证明其竞争力甚至优于使用显式模型的许多离线方法

    May, 2023

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

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

    Jan, 2013

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

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

    Nov, 2014

  • 合作多智能体马尔可夫决策过程中的近似线性规划和分散策略改进

    我们提出了适用于合作多智能体有限和无限时域折扣马尔可夫决策过程的逼近策略迭代算法，其中使用近似线性规划计算近似值函数并实施分散策略改进。

    Nov, 2023

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

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

    Oct, 2023

  • BetaZero: 使用学习逼近的置信状态规划长时程 POMDPs

    介绍一种基于准确置信模型的 BetaZero 算法，该算法使用在线蒙特卡罗树搜索与线下神经网络逼近相结合的方法来实现长周期问题的在线决策，解决了部分可观测领域的挑战，并在地质勘探等现实任务中表现出色。

    May, 2023

  • POMDP 的在线规划算法

    本文介绍了一些基于在线方法的局部政策计算的 POMDP 方法，并在各种环境下对这些方法进行了评估，结果表明现代的启发式搜索方法能够高效地处理大型 POMDP 领域。

    Jan, 2014

  • POMDP 中的策略指导的逻辑规范学习：归纳逻辑编程方法

    从 POMDP 执行的痕迹中学习得到高质量的启发式方法，通过转换为逻辑语义并利用数据和时间高效的归纳逻辑编程生成可解释的基于信念的策略规范，以在线方式引导 POMDP 求解器的行动选择过程。使用 Answer Set Programming (ASP) 表达的学习启发式方法展现了性能优于神经网络且与最佳手工设计的任务特定启发式方法相当的特点。

    Feb, 2024