提出瞬态多智能体路径规划，提升密集环境下的长期导航效率。
Transient Multi-Agent Path Finding for Lifelong Navigation in Dense Environments
- 将多智能体路径规划改为允许智能体陆续到达目标，不强制同时抵达。
- 实验显示在密集场景下系统吞吐量提升显著，最高达37%。
- 适合需要持续任务的机器人协同系统，如仓储物流、无人机群组。
多智能体路径规划（MAPF）旨在为一组智能体从初始状态找到无冲突的路径至目标状态。长期多智能体路径规划（LMAPF）是其在线版本，当一个智能体抵达目标后，会获得新的目标。现有方法通常将其视为一系列独立的MAPF问题，周期性地重新规划。但此方法要求所有智能体必须同时到达目标，对LMAPF而言过于严格。已有技术试图间接缓解该问题，但我们指出其存在失效情形。为此，我们提出一种新范式：将LMAPF转化为一系列修改后的MAPF问题，目标是每个智能体最终访问其目标，但不要求全部同时完成。我们称此为瞬态多智能体路径规划（TMAPF），并基于现有算法设计了多个求解器。初步实验表明，在某些场景中，使用TMAPF算法相比传统方法可使系统吞吐量显著提升，最高达37%。
原文摘要 · Abstract (English)
Multi-Agent Path Finding (MAPF) deals with finding conflict-free paths for a set of agents from an initial configuration to a given target configuration. The Lifelong MAPF (LMAPF) problem is a well-studied online version of MAPF in which an agent receives a new target when it reaches its current target. The common approach for solving LMAPF is to treat it as a sequence of MAPF problems, periodically replanning from the agents' current configurations to their current targets. A significant drawback in this approach is that in MAPF the agents must reach a configuration in which all agents are at their targets simultaneously, which is needlessly restrictive for LMAPF. Techniques have been proposed to indirectly mitigate this drawback. We describe cases where these mitigation techniques fail. As an alternative, we propose to solve LMAPF problems by solving a sequence of modified MAPF problems, in which the objective is for each agent to eventually visit its target, but not necessarily for all agents to do so simultaneously. We refer to this MAPF variant as Transient MAPF (TMAPF) and propose several algorithms for solving it based on existing MAPF algorithms. A limited experimental evaluation identifies some cases where using a TMAPF algorithm instead of a MAPF algorithm with an LMAPF framework can improve the system throughput significantly.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。