FluCaP:用于一阶 MDPs 的启发式搜索规划器
基于前向状态空间搜索的启发式搜索算法是实现 FF 规划系统的主要技巧,该系统因比 HSP 系统更具优越性能而赢得了最近 AIPS-2000 规划竞赛的冠军。
Jun, 2011
本文提出了一种基于线性规划的解决方法,通过将价值函数在一组一阶基函数的线性表示中计算适当的权值,解决了一阶马尔科夫决策过程中与特定领域实例无关的解决方案。并将该解决方法应用于电梯调度方面,具有丰富的特征空间和多标准加性奖励,证明了其优于许多直观、启发式指导政策。
Jul, 2012
通过使用第一阶表示中的紧凑策略来选择大型马尔可夫决策过程的策略,我们通过训练数据来诱导第一阶策略,使用具有分类概念语言的决策列表的合集来表示我们的策略,我们发现此方法在概率领域中具有优越的效果,并讨论了此方法在关系加固学习问题上的应用。
Dec, 2012
多智能体路径规划是解决一组智能体到达目标位置的无碰撞路径问题。先进的经典多智能体路径规划求解器通常采用启发式搜索方法以找到数百个智能体的解决方案,但通常是集中式的,而在短时间内可能难以扩展。机器学习方法学习每个智能体的策略非常吸引人,因为它们可以实现分散式系统,并在保持良好解决方案质量的同时具备良好的扩展性。我们的主要思想是,我们可以通过使用启发式搜索方法来改进机器学习的局部策略,以解决死锁和实现完全水平的规划。我们展示了几种无模型方法来使用带有学习策略的启发式搜索,这些方法显著提高了策略的成功率和可扩展性。据我们所知,我们首次证明了基于机器学习的多智能体路径规划方法在高拥塞场景(例如,20%智能体密度)中的可扩展性。
Mar, 2024
本文提出了两种近似解决因子化马尔可夫决策过程的算法,利用基函数表示近似值函数,其中每个基函数仅涉及一个小的子集,使用类似于变量消除的线性规划分解技术将指数级的 LP 规模缩小到多项式级别。我们的动态规划算法使用 max-norm 近似技术,对于超过 10^40 个状态的问题,我们的算法展示了有希望的可扩展性,并将其与现有的最新技术方法进行了比较,在某些问题上计算时间得到了指数级的提升。
Jun, 2011
本文介绍了一种可对连续和离散变量的大决策问题进行紧凑表示的混合分解 Markov 决策过程(MDP)模型和一种新的混合近似线性规划(HALP)框架,HALP 的核心思想是通过一组基函数的线性组合来近似最优价值函数,并通过线性规划来优化其权重, 并证明其在多种混合优化问题中的可扩展潜力。
Sep, 2011
这篇论文提出了 FMAP(Forward Multi-Agent Planning),这是一种完全分布式的多智能体规划方法,它结合了规划和协调,并通过前向链式部分排序规划器在代理商联合探索计划空间,然后应用隐私模型进行通讯。实验表明,FMAP 是一种通用方法,能够高效地解决紧密耦合的领域问题和普遍问题,并且在解决国际计划竞赛基准的复杂规划任务方面优于当前 MAP 系统。
Jan, 2015
本研究介绍了一种利用启发式算法解决定理证明和计划制定问题的方法,并将其应用于 situation calculus 中。该方法通过使用 A * 搜索算法排列一系列情境,并利用删除松弛法控制启发式规划器,获得较短的计划方案,并探索较少的状态。实验表明,该方法可以应用于较大规模的问题。
Mar, 2023
本文介绍了如何在 SAT 求解器中构建带有领域特定启发式信息的 MAPF 编码,并选择每个 agent 的备选路径来构建编码,实验结果表明这种启发式的 MAPF 求解器优于普通的 SAT 求解器。
Dec, 2022
提出了一种名为 Probabilistic-FF 的新的概率规划算法,该算法结合了 Conformant-FF 的技术和加权模型计数技术,可在具有概率部分不可观测性的问题上进行推理,并在各种概率域中显示出良好的可扩展性。
Oct, 2011