In this paper, we consider the problem of optimally allocating tasks, expressed as global Linear Temporal Logic (LTL) specifications, to teams of heterogeneous mobile robots. The robots are classified in different types that capture their different capabilities, and each task may require robots of multiple types. The specific robots assigned to each task are immaterial, as long as they are of the desired type. Given a discrete workspace, our goal is to design paths, i.e., sequences of discrete states, for the robots so that the LTL specification is satisfied. To obtain a scalable solution to this complex temporal logic task allocation problem, we propose a hierarchical approach that first allocates specific robots to tasks using the information about the tasks contained in the Nondeterministic Buchi Automaton (NBA) that captures the LTL specification, and then designs low-level executable plans for the robots that respect the high-level assignment. Specifically, we first prune and relax the NBA by removing all negative atomic propositions. This step is motivated by "lazy collision checking" methods in robotics and allows to simplify the planning problem by checking constraint satisfaction only when needed. Then, we extract sequences of subtasks from the relaxed NBA along with their temporal orders, and formulate a Mixed Integer Linear Program (MILP) to allocate these subtasks to the robots. Finally, we define generalized multi-robot path planning problems to obtain low-level executable robot plans that satisfy both the high-level task allocation and the temporal constraints captured by the negative atomic propositions in the original NBA. We provide theoretical results showing completeness and soundness of our proposed method and present numerical simulations demonstrating that our method can generate robot paths with lower cost, considerably faster than existing methods.


翻译:在本文中, 我们考虑最佳分配任务的问题, 以全球直线性平流逻辑( LTL) 的规格表示, 给混杂移动机器人的团队分配任务。 机器人被分类为不同类型, 捕捉不同的能力, 每个任务都可能需要多种类型的机器人。 分配给每个任务的具体机器人并不重要, 只要它们属于想要的类型。 在一个离散的工作空间中, 我们的目标是设计路径, 即离散状态的序列, 使机器人能够满足 LTL 的规格 。 要找到一个可调整的解决方案, 复杂的时间逻辑任务分配问题, 我们建议一种等级方法, 首先分配特定的机器人, 使用Ndeministic Buchi Automaton (NBA) 中包含的任务信息。 只要它们符合LTL 的规格, 然后设计一个低层次的可执行计划。 具体地说, 我们先是制定离散状态的状态状态, 然后通过消除所有的负数原子参数来放松 NBA 。 这个步骤的动机是“ 平流式平流式平流法 ”, 我们只能通过不断校验 NBA 的平流路, 的平流规则, 的平流法, 的平流路的平流,, 使我们逐渐平流的平流的平流的平流法的平流的平流的平流的平流的平流的平流的平流的平流法 。

0
下载
关闭预览

相关内容

【CIKM2020】神经逻辑推理,Neural Logic Reasoning
专知会员服务
49+阅读 · 2020年8月25日
【Facebook AI】低资源机器翻译,74页ppt
专知会员服务
29+阅读 · 2020年4月8日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【泡泡一分钟】高动态环境的语义单目SLAM
泡泡机器人SLAM
5+阅读 · 2019年3月27日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Arxiv
0+阅读 · 2021年3月16日
Arxiv
0+阅读 · 2021年3月12日
Logically-Constrained Reinforcement Learning
Arxiv
3+阅读 · 2018年12月6日
VIP会员
相关VIP内容
【CIKM2020】神经逻辑推理,Neural Logic Reasoning
专知会员服务
49+阅读 · 2020年8月25日
【Facebook AI】低资源机器翻译,74页ppt
专知会员服务
29+阅读 · 2020年4月8日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【泡泡一分钟】高动态环境的语义单目SLAM
泡泡机器人SLAM
5+阅读 · 2019年3月27日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Top
微信扫码咨询专知VIP会员