Multi Agent Path Finding (MAPF) requires identification of conflict free paths for agents which could be point-sized or with dimensions. In this paper, we propose an approach for MAPF for spatially-extended agents. These find application in real world problems like Convoy Movement Problem, Train Scheduling etc. Our proposed approach, Decentralised Multi Agent Path Finding (DeMAPF), handles MAPF as a sequence of pathplanning and allocation problems which are solved by two sets of agents Travellers and Routers respectively, over multiple iterations. The approach being decentralised allows an agent to solve the problem pertinent to itself, without being aware of other agents in the same set. This allows the agents to be executed on independent machines, thereby leading to scalability to handle large sized problems. We prove, by comparison with other distributed approaches, that the approach leads to a faster convergence to a conflict-free solution, which may be suboptimal, with lesser memory requirement.


翻译:多代理路径定位( MAPF) 需要为可能具有点尺寸或尺寸的代理物确定无冲突路径 。 在本文中, 我们为MAPF 提出了一个空间扩展代理物设计的方法 。 这些方法在现实世界问题中找到了应用性, 比如 Convoy Move Commission, train Schluding 等 。 我们的拟议方法, 分散的多代理物路定位( DeMAPF), 将MAPF 作为路径规划和分配问题的序列处理, 由两组代理物旅行者和路由者分别解决, 超越多个迭代。 正在分散的方法允许代理物解决与自身相关的问题, 而不了解同一组中的其他代理物。 这样可以让代理物在独立机器上执行, 从而导致处理大范围的问题的可扩展性 。 我们与其他分布的方法相比, 证明该方法可以更快地实现无冲突解决方案的趋同, 后者可能是不优化的, 记忆要求较低 。

1
下载
关闭预览

相关内容

【AAAI2021】对比聚类,Contrastive Clustering
专知会员服务
76+阅读 · 2021年1月30日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
78+阅读 · 2020年7月26日
TensorFlow 2.0 学习资源汇总
专知会员服务
66+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
鲁棒机器学习相关文献集
专知
8+阅读 · 2019年8月18日
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
【泡泡前沿追踪】跟踪SLAM前沿动态系列之IROS2018
泡泡机器人SLAM
29+阅读 · 2018年10月28日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Arxiv
0+阅读 · 2021年8月4日
Arxiv
0+阅读 · 2021年7月31日
VIP会员
相关资讯
鲁棒机器学习相关文献集
专知
8+阅读 · 2019年8月18日
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
【泡泡前沿追踪】跟踪SLAM前沿动态系列之IROS2018
泡泡机器人SLAM
29+阅读 · 2018年10月28日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Top
微信扫码咨询专知VIP会员