Spatially Distributed Multiagent Path Planning
Spatially Distributed Multiagent Path Planning
复制标题
空间分布式多智能体路径规划
DOI：
10.1609/icaps.v24i1.13618
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Botea
中科院分区：
文献类型：
--
作者：
C. Wilt;A. Botea
在各个领域，多种路径规划很重要，从游戏到机器人和仓库管理。尽管联合行动空间中的集中控制可以提供最佳计划，但这通常是计算上的信息。解耦计划更加可扩展。传统的解耦方法执行以单位为中心的分解，通过一系列单一搜索代替多代理搜索，每个移动设备一个。我们引入了一种正交的，显着不同的方法，该方法是在空间分布将地图分配为高竞争，瓶颈区域和低颈部区域的空间分布之后。称为控制器的Lo-cal代理负责每个地方，将移动设备路由其相应区域的路由移动设备。分配整个地图上的知识，每个控制器只能观察其自己区域的状态。相邻的控制器可以通信以协商移动单元的传输。我们在真实的游戏地图上与较大区域和狭窄的瓶颈门户的混合物评估了实施算法SDP。结果表明，空间分布的计划在MakePAN质量和计算速度方面可以具有很大的好处。
Multiagent path planning is important in a variety of fields, ranging from games to robotics and warehouse management. Although centralized control in the joint action space can provide optimal plans, this often is computationally infeasi- ble. Decoupled planning is much more scalable. Traditional decoupled approaches perform a unit-centric decomposition, replacing a multi-agent search with a series of single-agent searches, one for each mobile unit. We introduce an orthogonal, significantly different approach, following a spatial distribution that partitions a map into high- contention, bottleneck areas and low-contention areas. Lo- cal agents called controllers are in charge with one local area each, routing mobile units in their corresponding area. Dis- tributing the knowledge across the map, each controller can observe only the state of its own area. Adjacent controllers can communicate to negotiate the transfer of mobile units. We evaluate our implemented algorithm, SDP, on real game maps with a mixture of larger areas and narrow, bottleneck gateways. The results demonstrate that spatially distributed planning can have substantial benefits in terms of makespan quality and computation speed.