Path planning for multiple robots (MRPP) represents a task of finding non-colliding paths for robots through which they can navigate from their initial positions to specified goal positions. The problem is usually modeled using undirected graphs where robots move between vertices across edges. Contemporary optimal solving algorithms include dedicated search-based methods, that solve the problem directly, and compilation-based algorithms that reduce MRPP to a different formalism for which an efficient solver exists, such as constraint programming (CP), mixed integer programming (MIP), or Boolean satisfiability (SAT). In this paper, we enhance existing SAT-based algorithm for MRPP via spartification of the set of candidate paths for each robot from which target Boolean encoding is derived. Suggested sparsification of the set of paths led to smaller target Boolean formulae that can be constructed and solved faster while optimality guarantees of the approach have been kept.


翻译:多机器人的路径规划( MRPP) 是一项为机器人找到非对称路径的任务, 机器人可以从最初的位置导航到指定的目标位置。 问题通常使用非定向图形模型, 机器人在边缘之间移动。 当代最佳解算法包括专门的搜索方法, 直接解决问题, 以及基于编译的算法, 将MRP降低为不同的形式主义, 并存在高效的解算法, 例如制约程序( CP)、 混合整流程序( MIP) 或 Boolean 相对性( SAT ) 。 在本文中, 我们通过分割每个机器人的候选路径集来强化基于 SAT MOPP 的现有算法, 从而生成目标 Boolean 编码 。 建议的路径集解压缩到小目标 Boolean 公式, 可以更快地构建和解决, 同时保存了方法的最佳性保证 。

0
下载
关闭预览

相关内容

Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【Manning新书】现代Java实战,592页pdf
专知会员服务
99+阅读 · 2020年5月22日
专知会员服务
60+阅读 · 2020年3月19日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
谷歌足球游戏环境使用介绍
CreateAMind
33+阅读 · 2019年6月27日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无人机视觉挑战赛 | ICCV 2019 Workshop—VisDrone2019
PaperWeekly
7+阅读 · 2019年5月5日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
大神 一年100篇论文
CreateAMind
15+阅读 · 2018年12月31日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
Arxiv
0+阅读 · 2021年4月29日
Arxiv
0+阅读 · 2021年4月29日
Arxiv
0+阅读 · 2021年4月28日
Arxiv
0+阅读 · 2021年4月28日
Arxiv
0+阅读 · 2021年4月28日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关VIP内容
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【Manning新书】现代Java实战,592页pdf
专知会员服务
99+阅读 · 2020年5月22日
专知会员服务
60+阅读 · 2020年3月19日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
谷歌足球游戏环境使用介绍
CreateAMind
33+阅读 · 2019年6月27日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无人机视觉挑战赛 | ICCV 2019 Workshop—VisDrone2019
PaperWeekly
7+阅读 · 2019年5月5日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
大神 一年100篇论文
CreateAMind
15+阅读 · 2018年12月31日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
相关论文
Arxiv
0+阅读 · 2021年4月29日
Arxiv
0+阅读 · 2021年4月29日
Arxiv
0+阅读 · 2021年4月28日
Arxiv
0+阅读 · 2021年4月28日
Arxiv
0+阅读 · 2021年4月28日
Arxiv
3+阅读 · 2018年2月24日
Top
微信扫码咨询专知VIP会员