AAAIDec, 2023

分布式蒙特卡洛树搜索用于部分可观察多智体路径规划

PDF
TL;DR我们提出了一种基于分布式多智能体蒙特卡罗树搜索方法的多智能体路径规划算法，通过利用智能体的观察结果重新创建内在的马尔科夫决策过程，并结合针对多智能体任务的定制化神经蒙特卡罗树搜索算法进行路径规划，实验证明该方法优于现有的学习型多智能体路径规划器。
multi-agent pathfindingdecentralized mapflifelong variantmonte carlo tree searchneural mcts
发现论文，激发创造
  • 学习跟随：基于规划和学习的去中心化多智能体路径规划

    在这项工作中，我们研究了分布式多智能体路径规划问题的设置，通过集成启发式搜索和强化学习方法，提出了一种解决复杂的问题的方法。我们的方法在广泛的设置中得到了验证，并且在吞吐量和泛化能力上表现优越，同时比现有的基于规则和基于搜索的解决方法快一个数量级。

    Oct, 2023

  • 含延迟概率的多智能体路径规划

    该研究提出了一个基于 Multi-Agent Path Finding (MAPF) 的两层搜索的 MAPF-DP 解决方案，包括规划具有不完美执行计划的有效 MAPF-DP 解决方案，提出了具有鲁棒性的计划执行策略以控制每个代理的行动，展示了能够生成有效 MAPF-DP 计划的两层 MAPF-DP 求解器（称为期望值最小化近似）。

    Dec, 2016

  • 优化基于启发式搜索的学习局部 MAPF 策略

    多智能体路径规划是解决一组智能体到达目标位置的无碰撞路径问题。先进的经典多智能体路径规划求解器通常采用启发式搜索方法以找到数百个智能体的解决方案，但通常是集中式的，而在短时间内可能难以扩展。机器学习方法学习每个智能体的策略非常吸引人，因为它们可以实现分散式系统，并在保持良好解决方案质量的同时具备良好的扩展性。我们的主要思想是，我们可以通过使用启发式搜索方法来改进机器学习的局部策略，以解决死锁和实现完全水平的规划。我们展示了几种无模型方法来使用带有学习策略的启发式搜索，这些方法显著提高了策略的成功率和可扩展性。据我们所知，我们首次证明了基于机器学习的多智能体路径规划方法在高拥塞场景（例如，20％智能体密度）中的可扩展性。

    Mar, 2024

  • 连续时间下的多智能体路径规划

    提出了一种基于 Safe interval path planning (SIPP) 和 Conflict-based search (CBS) 算法的多智能体路径规划 (Multi-Agent Pathfinding, MAPF) 方法，不依赖于网格、时间步长和动作的同时，并具有保证最优解的特点。对该算法进行了分析、讨论优劣，并在多项标准基准测试中进行了实验评估。

    Jan, 2019

  • 交通流优化对于终生多智能体路径规划

    多智能体路径规划（Multi-Agent Path Finding）是机器人领域的一个基本问题，该研究提出了一种新方法来解决这个问题，该方法通过引导智能体按照避免拥堵的路径前往目的地，有效提高了解决方案质量，并在整体通量方面取得了显著改进。

    Aug, 2023

  • 缩放终身多智能体路径规划到更现实的环境中：研究挑战与机遇

    多智能体路径规划是将多个智能体从起点移动到目标点而无碰撞的问题，终身智能体路径规划通过不断为智能体分配新目标进一步扩展了多智能体路径规划。本文概述了三个主要的研究挑战，包括寻找在有限的规划时间内（例如，每步 1 秒）为大量智能体（例如，10,000 个）或极高智能体密度（例如，97.7%）搜索高质量的终身智能体路径规划（LMAPF）解决方案的挑战，缓解拥堵和短视行为在 LMAPF 算法中的影响的挑战，以及弥合文献中使用的 LMAPF 模型和实际应用之间的差距的挑战。

    Apr, 2024

  • 多代理路径规划的蒙特卡洛树搜索：初步结果

    研究了多智能体路径规划中如何利用蒙特卡洛树搜索（Monte-Carlo Tree Search）解决问题，提出了一种适用于多智能体路径规划的改进 MCTS 变种，通过计算个体路径和奖励来指导搜索过程，实验证明该方法优于基线规划算法。

    Jul, 2023

  • 多智能体造地：通过环境操作实现高效多智能体路径规划

    本文介绍了一种新的 MAPF 扩展，称为 Terraforming MAPF（tMAPF），其中一些代理负责移动障碍以为其他代理清除道路。我们介绍了两种先进算法 CBS 和 PBS 的扩展来解决 tMAPF 问题，并表明它们无论在哪种静态障碍条件下都可以持续超过最佳解决方案。

    Mar, 2022

  • 改进的匿名多智能体路径规划算法

    我们考虑投射在图上的匿名多智能体路径规划（AMAPF）问题，给定了一组目标顶点，每个顶点必须被某个智能体到达。本文针对寻找使得最短耗时的目标 - 智能体分配方案和无碰撞路径的问题，通过将其转化为特殊类型的图搜索问题，即在输入图引导下寻找最大流问题来求解。然后，我们提出了一种利用批量搜索状态的特定搜索算法，将搜索空间压缩、存储和扩展为单一状态，从而显著降低了运行时间和内存占用。实验证明，该 AMAPF 求解器在 30 秒内能够解决所有公开可用的来自知名 MovingAI 基准的 MAPF 实例，并表现出卓越的性能优势。

    Dec, 2023

  • 多智能体路径规划：定义、变体和基准测试

    该论文旨在通过提供统一的术语来描述常见的 MAPF 假设和目标，并指向两个 MAPF 基准，介绍了一个新的基于网格的 MAPF 基准，并试验性地证明它对当代 MAPF 算法提出了挑战。

    Jun, 2019