The problem of Multi-Agent Path Finding (MAPF) calls for finding a set of conflict-free paths for a fleet of agents operating in a given environment. Arguably, the state-of-the-art approach to computing optimal solutions is Conflict-Based Search (CBS). In this work we revisit the complexity analysis of CBS to provide tighter bounds on the algorithm's run-time in the worst-case. Our analysis paves the way to better pinpoint the parameters that govern (in the worst case) the algorithm's computational complexity. Our analysis is based on two complementary approaches: In the first approach we bound the run-time using the size of a Multi-valued Decision Diagram (MDD) -- a layered graph which compactly contains all possible single-agent paths between two given vertices for a specific path length. In the second approach we express the running time by a novel recurrence relation which bounds the algorithm's complexity. We use generating functions-based analysis in order to tightly bound the recurrence. Using these technique we provide several new upper-bounds on CBS's complexity. The results allow us to improve the existing bound on the running time of CBS for many cases. For example, on a set of common benchmarks we improve the upper-bound by a factor of at least $2^{10^{7}}$.


翻译:多重代理路径定位( MAPF) 问题要求为在特定环境中运行的代理团队寻找一套无冲突路径。 可以说, 计算最佳解决方案的最先进的方法是基于冲突搜索( CBS ) 。 在这项工作中, 我们重新审视了 CBS 的复杂分析, 为算法运行时间提供了最坏的更紧密的界限。 我们的分析为更好地确定算法复杂程度的参数铺平了道路。 我们的分析基于两种互补方法: 在第一个方法中, 我们使用多值决定图( MDD) 的大小来约束运行时间 -- -- 一个层次图, 精密地包含两个给定的垂直之间的所有可能的单一代理路径, 具体路径长度。 在第二个方法中, 我们用新的重现关系来表达运行时间。 我们用基于功能的分析来严格约束重现。 我们用这些技术在 CBS 的复杂程度上提供了几个新的上方位。 允许我们改进现有的C- 10 标准中的许多 C- 的上位基准。

0
下载
关闭预览

相关内容

专知会员服务
25+阅读 · 2021年4月2日
专知会员服务
50+阅读 · 2020年12月14日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
计算机 | ICDE 2020等国际会议信息8条
Call4Papers
3+阅读 · 2019年5月24日
人工智能 | SCI期刊专刊/国际会议信息7条
Call4Papers
7+阅读 · 2019年3月12日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
人工智能 | 国际会议截稿信息9条
Call4Papers
4+阅读 · 2018年3月13日
carla 学习笔记
CreateAMind
9+阅读 · 2018年2月7日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2021年6月8日
Arxiv
0+阅读 · 2021年6月6日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关资讯
计算机 | ICDE 2020等国际会议信息8条
Call4Papers
3+阅读 · 2019年5月24日
人工智能 | SCI期刊专刊/国际会议信息7条
Call4Papers
7+阅读 · 2019年3月12日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
人工智能 | 国际会议截稿信息9条
Call4Papers
4+阅读 · 2018年3月13日
carla 学习笔记
CreateAMind
9+阅读 · 2018年2月7日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员