MAPF笔记11

MAPF 基础

文档作者：李 拥 祺

1. MAPF 是什么？

multi-agent pathfinding problem

1.1 定义

Multi-Agent Path Finding (MAPF) is the problem of computing collision-free paths for a

team of agents from their current locations to given destinations

MAPF 问题是多智能体规划问题中很重要的一类问题；

全局路径规划

局部路径优化

1.2 经典 MAPF 问题数学描述

1.2.1 问题描述

个 agent

Input ：tuple

无向图

映射 表示每个 agent 都对应一个源节点；

映射 表示每个 agent 对应的目标节点；

假设 时间是离散的，在每一个时间步长，每一个 agent 都分别位于图 上一个节点上，并且可以

即 ，其中 表示 的源节点位置。

表示 agent 执行了一系列动作 之后到达目标节点 ，我们称动作序列 是

agent 的一条单智能体规划路径（single-agent plan ）。

Output ：k 条 single-agent plan 集合。