• Classified by Topic • Classified by Publication Type • Sorted by Date • Sorted by First Author Last Name • Classified by Funding Source •
Multi-Robot Planning with Conflicts and Synergies.
Yuqian Jiang, Harel
Yedidsion, Shiqi Zhang, Guni
Sharon, and Peter Stone.
Autonomous Robots, Springer, March 2019.
Official version from Publisher's Webpage
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.
@ARTICLE{AURO19-jiang,
author = {Yuqian Jiang and Harel Yedidsion and Shiqi Zhang and Guni Sharon and Peter Stone},
title = {Multi-Robot Planning with Conflicts and Synergies},
journal = {Autonomous Robots},
year = {2019},
month = {March},
publisher={Springer},
abstract = {
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.
},
wwwnote = {Official version from <a href="https://link.springer.com/article/10.1007%2Fs10514-019-09848-1">Publisher's Webpage</a>},
}
Generated by bib2html.pl (written by Patrick Riley ) on Tue Nov 19, 2024 10:24:39