Feb, 2024

导向图优化的多智能体路径规划的终身学习

PDF
TL;DR我们研究了如何利用引导来提高终身多智能体路径规划（MAPF）的吞吐量。我们提出了两种 GGO 算法来自动生成适用于任意终身 MAPF 算法和地图的引导，并通过实验证明我们的引导图能够提高三个典型终身 MAPF 算法在四个基准地图上的吞吐量。
guidancethroughputmulti-agent path findinglifelong mapfggo algorithms
发现论文，激发创造
  • 交通流优化对于终生多智能体路径规划

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

    Aug, 2023

  • 学习跟随：基于规划和学习的去中心化多智能体路径规划

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

    Oct, 2023

  • 面向终身多智能体路径规划的公路研究

    本文主要研究如何在 lifelong MAPF 中使用 highway 方法解决地图规模增大、密度增大等问题，以减少 deadlocks 现象并优化 throughput，实验证明 runtime 得到改进。

    Apr, 2023

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

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

    Apr, 2024

  • 通过图嵌入的最优多智能体路径规划算法选择

    多智能体路径规划问题（MAPF）是寻找多个智能体不发生碰撞的路径的问题，该研究论文提出了一种基于图嵌入的解决方案，称为 MAPF 算法选择图嵌入（MAG），通过对 MAPF 问题进行图形编码并利用现代图嵌入算法，该方法在多个 MAPF 算法选择任务上表现出与现有方法相当或显著更好的性能。

    Jun, 2024

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

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

    Dec, 2023

  • 缓存增强的终身多智能体路径规划

    本文介绍了一种名为 Caching-Augmented Lifelong MAPF（CAL-MAPF）的新机制，用于改善 Lifelong MAPF 的性能，并通过实验证明了在某些任务分布、地图和代理配置下，CAL-MAPF 具备提升性能的潜力。

    Mar, 2024

  • MapGo: 面向目标任务的模型辅助策略优化

    本文提出了一种名为 FGI 的新的重标记策略用于改善回报稀疏性问题，并通过引入动态模型来生成模拟轨迹来提高采样效率，提出了一种名为 MapGo 框架用于目标导向任务的模型辅助策略优化， 并在复杂任务上的实验证明了 FGI 策略相比后见策略的有效性，并且 MapGo 框架相对于无模型的基线表现出更高的采样效率。

    May, 2021

  • SOCIALMAPF：面向社交导航的战略智能多智能体路径规划

    本文提出了一种名为 SocialMAPF 的路径规划算法，该算法适用于考虑代理人个体私人的激励因素的约束环境。我们使用机制设计提高了个体的私人效用和全局系统目标，从而使得机器人能够在考虑到自身私人激励情况下达到更高的整体效用。实验表明，这种算法比传统方法更加高效，而且机制设计算法还能应用于静态环境中，具有很高的研究价值。

    Oct, 2022

  • 使用超图世界模型中的最大似然路径进行目标无关规划

    本研究提出了一种基于超图的机器学习算法，一种数据结构驱动的维护方法，以及一种基于概率应用 Dijkstra 算法的规划算法，从而形成了一个目标不可知的自动化学习代理计划引擎，该引擎结合了经典机器学习和传统人工智能的有益特性。我们证明了该算法能够在问题空间内确定最优解，在数学上限制了学习性能，并提供了一种数学模型，分析了系统状态在时间上的进展，从而得出了学习曲线、目标实现率和抽象和不确定性响应的明确预测。为了验证性能，我们展示了将代理应用于三个典型的计划问题的结果，并突出了阐明的特性的实证结论。

    Oct, 2021