Multi-Agent Path Finding (MAPF) is a problem of finding a sequence of movements for agents to reach their assigned location without collision. Centralized algorithms usually give optimal solutions, but have difficulties to scale without employing various techniques - usually with a sacrifice of optimality; but solving MAPF problems with the number of agents greater than a thousand remains a challenge nevertheless. To tackle the scalability issue, we present DMAPF - a decentralized and distributed MAPF solver, which is a continuation of our recently published work, ros-dmapf. We address the issues of ros-dmapf where it (i) only works in maps without obstacles; and (ii) has a low success rate with dense maps. Given a MAPF problem, both ros-dmapf and DMAPF divide the map spatially into subproblems, but the latter further divides each subproblem into disconnected regions called areas. Each subproblem is assigned to a distributed solver, which then individually creates an abstract plan - a sequence of areas that an agent needs to visit - for each agent in it, and interleaves agent migration with movement planning. Answer Set Programming, which is known for its performance in small but complex problems, is used in many parts including problem division, abstract planning, border assignment for the migration, and movement planning. Robot Operating System is used to facilitate communication between the solvers and to enable the opportunity to integrate with robotic systems. DMAPF introduces a new interaction protocol between the solvers, and mechanisms that together result in a higher success rate and better solution quality without sacrificing much of the performance. We implement and experimentally validate DMAPF by comparing it with other state-of-the-art MAPF solvers and the results show that our system achieves better scalability.


翻译:多代理路径定位(MAPF) 是一个问题, 要找到代理商在没有碰撞的情况下到达指定地点的移动序列。 中央化算法通常提供最佳的解决方案, 但难以在不使用各种技术的情况下进行规模化 — — 通常是以优化为牺牲; 但是, 解决MAPF问题, 代理商数量超过一千个, 但仍是一个挑战。 要解决可缩缩缩缩缩问题, 我们提出 DMAPF — 分散和分布的MAPF 解答器。 这是我们最近出版的工作( ros- dmapf ) 的继续。 我们处理的是ros- dmapf 的问题, 在那里, 它( 一) 只能用在地图上, 只能用不设障碍的地图; 和 (二) 低成功率与密集的地图; 鉴于MAPF 问题, 罗斯- dmapf 和 D MAPF 将地图在空间上分割成问题, 但后又将每个子相隔开。 每个子问题被指派给一个分布式的解算器, 然后单独创建一个解算算算出一个解决方案- —— 。 在一个小代理服务器需要访问的解算算出一个更小代理的系统之间的领域, 。 和内部的系统, 使用一个更好的运算算出一个更好的运算算出一个更好的运算算法, 。

0
下载
关闭预览

相关内容

【AAAI2021】对比聚类,Contrastive Clustering
专知会员服务
76+阅读 · 2021年1月30日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】视频目标分割基础
机器学习研究会
9+阅读 · 2017年9月19日
【推荐】图像分类必读开创性论文汇总
机器学习研究会
14+阅读 · 2017年8月15日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2021年11月5日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】视频目标分割基础
机器学习研究会
9+阅读 · 2017年9月19日
【推荐】图像分类必读开创性论文汇总
机器学习研究会
14+阅读 · 2017年8月15日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员