I 专家产业专栏
Industry column
标。代理先被划分到组中，然后每个代理需要从 代 理 通 常 是 匿 名 的， 但 携 带 被 分 配 目 标 的
所在的组中被指定一个目标，以便得到代理从当 有 效 载 荷（ 包 裹）， 因 此 是 非 匿 名 的。 例 如，
前顶点到其目标的路径来优化成本函数。例如， 在 Kiva 仓库系统中，驾驶单元是匿名的，但是
在 Kiva 仓库系统中，将存储舱从仓库搬运到新 它们携带的存储舱被分配了存储位置，因此是非
存储位置的驾驶单元（drive unit）会形成一个组， 匿名的。如果每个代理都携带一个包裹，则该问
因为它们中的每一个需要被分配一个可用的存储 题相当于（标准）MAPF。实际上，包裹通常可
位置。以前的 MAPF 方法假设存在目标分配程 以在代理之间传递，这导致更一般的运输问题，
序，使得每个代理预先被分配一个目标，但是为 例 如， 带 有 换 乘 的 乘 客 共 享 乘 车［Coltin and
了实现最优性，我们建立了 TAPF 模型，它整合 Veloso， 2014］和在办公室中使用机器人的包
了目标分配和路径寻找问题并且为它们定义了一 裹递送［Veloso et al．， 2015］。我们已经
个共同的目标。在 TAPF 中，代理被分到各组 将 PERR 作为理解这些问题的第一步［Ma et
中，每个组的目标数量与该组中的代理数量相同。 al．， 2016］。在 PERR 中，每个代 理 运 载
TAPF 的任务是将目标分配给代理，并规划代理 一个包裹，相邻顶点中的任何两个代理可以交换
从当前顶点到其目标的不会发生碰撞的路径，使 其包裹，并且每个包需裹要被递送到给定目标。
得每个代理恰好移动到其所在组的一个目标，从 PERR 因此可以被视为（标准）MAPF 的改进版：
而组中的所有目标被访问，且最大完成时间（当
所有代理已经到达其目标并停止移动时的最早时 •PERR 中 的 包 裹 可 以 被 视 为 在（ 标 准）
间步长）被最小化。组中的每个代理都可以被分 MAPF 中的自己移动的代理。
配到所在组的目标，并且同一组中的代理因此是
可 交 换 的。 然 而， 不 同 组 中 的 代 理 不 可 交 换。 • 允许在相邻顶点中的两个包裹在 PERR
TAPF 可以被视为（标准）MAPF 和 MAPF 的 中交换它们的顶点，但是在相邻顶点中的两个代
匿名变体的一般化： 理不允许在（标准）MAPF 中交换它们的顶点。
• 来自 TAPF 的（标准）MAPF 结果，如 K － PERR 是 PERR 的一般化，其中包裹
果每个组仅由一个代理组成，则组的数量等于代 被分成 K 个类型，并且相同类型的包裹是可交换
理的数量。目标到代理的分配是预先确定的，因 的。因为在 TAPF 中，代理被分到组中，并且同
此代理是非匿名的（不可交换的）。 一团队中的代理是可交换的，所以 K － PERR
可以被视为对 K 个组的 TAPF 的改版，同样的
• 如 果 只 有 一 个 组（ 包 含 所 有 代 理 ）， 原理，PERR 可以被视为（标准）MAPF 的改版。
则 MAPF 的 匿 名 变 量（ 也 称 为 目 标 不 变 的 我们已经证明了近似最佳 PERR 和 K － PERR
MAPF）来自 TAPF。代理可以被分配任何目 解的困难性（对于 K ≥ 2）。我们的研究的一个
标，因此是可交换的。它可以在多项式时间内用 推论是：在任何因子小于 4 ／ 3 内的最大完工
基于流的 MAPF 方法（flow － based MAPF 时间最小化，近似 MAPF 和 TAPF 是 NP －
method） 得 到 最 优 解［Yu and LaValle， hard 的，即使是只有两个团队的 TAPF。我们
2013a； Turpin et al．， 2014］． 还证明了向 MAPF 添加交换操作不会在理论上
减少其复杂度，但使得 PERR 比 MAPF 更容
当 前 最 先 进 的 最 优 TAPF 方 法 —— 称 为 易解决。由此产生的在不同的实际场景中的连续
基 于 碰 撞 的 最 小 成 本 流（Conflict － Based 问题：「一个有很多包裹的代理」产生经典的农
Min － Cost Flow）［Ma and Koenig， 村 邮 递 员 问 题（rural postman problem）；
2016］——结合了搜索和基于流的 MAPF 方法。 「代理与包裹一样多」产生 MAPF、TAPF 或
它可以推广到几十个组和数百个代理。
32 新战略机器人网 www.xzlrobot.com
