Multi-robot planning with conflicts and synergies
Multi-robot planning with conflicts and synergies
复制标题
冲突与协同的多机器人规划
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
P. Stone
中科院分区：
文献类型：
--
作者：
Yuqian Jiang;Harel Yedidsion;Shiqi Zhang;Guni Sharon;P. Stone
多机器人规划（mrp）的目标是计算计划，每个计划以一系列动作的形式，为一组机器人实现各自的目标，同时使总成本最小化。解决mrp问题需要对有限的域资源（例如，每次最多允许一个机器人的走廊），以及动作协同的可能性（例如，多个机器人在单个开门动作之后通过门）。最佳解决MRP问题是困难的，因为它是一个推广的单代理规划域，这是已知的NP-难，并经常需要考虑所有的机器人的状态，导致指数增长的联合状态和动作空间。在许多mrp领域中，机器人会遇到这样的情况：它们对有限资源的需求相互冲突，或者它们可以利用彼此正在做的事情来形成协同效应。在这篇文章中，我们提出了多机器人冲突和协同规划问题，并开发了一个多机器人规划框架，称为迭代相互依赖规划（iidp），用于表示和解决mrpcs问题。在iidp架构下，我们发展出增加相依性与最佳选择的演算法，在规划品质与计算效率之间呈现不同的折衷。广泛的实验，涵盖了建议的算法已经进行了使用抽象域模拟器，在那里我们可以自动生成各种域配置，和一个实际的mrpcs实例，侧重于多机器人导航。在导航领域，我们的模型计划成本与时间的不确定性，并提出了一种新的移位泊松分布的时间不确定性积累行动。在基线方法相比，我们的算法产生显着降低整体计划成本，同时避免在联合状态空间搜索。此外，我们提出了一个完整的示范模型的实施团队的真实的机器人。
Multi-robot planning (mrp) aims at computing plans, each in the form of a sequence of actions, for a team of robots to achieve their individual goals, while minimizing overall cost. Solving mrp problems requires modeling limited domain resources (e.g., corridors that allow at most one robot at a time), and the possibility of action synergy (e.g., multiple robots going through a door after a single door-opening action). Optimally solving mrp problems is hard as it is a generalization of the single agent planning domain which is known to be NP-hard, and frequently requires considering the states of all the robots, resulting in an exponentially growing joint state and action space. In many mrp domains, robots encounter situations where they have conflicting needs for constrained resources, or where they can take advantage of what each other is doing to form synergies. In this article, we formulate the problem of multi-robot planning with conflicts and synergies (mrpcs), and develop a multi-robot planning framework, called iterative inter-dependent planning (iidp), for representing and solving mrpcs problems. Within the iidp framework, we develop the algorithms of increasing dependency and best alternative which exhibit different trade-offs between plan quality and computational efficiency. Extensive experiments covering the suggested algorithms have been performed using both an abstract-domain simulator, where we can automatically generate a variety of domain configurations, and a practical mrpcs instantiation that focuses on multi-robot navigation. In the navigation domain, we model plan costs with temporal uncertainty, and present a novel shifted-Poisson distribution for accumulating temporal uncertainty over actions. In comparison to baseline approaches, our algorithms produce significant reductions in overall plan cost, while avoiding search in the joint state space. In addition, we present a complete demonstration of the implementation of the model on a team of real robots.
DOI：
--
发表时间：
2016
期刊：
Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems
影响因子：
--
作者：
Hoang, Khoi;Fioretto, Ferdinando;Hou, Ping;Yokoo, Makoto;Yeoh, William;Zivan, Roie
通讯作者：
Zivan, Roie