Peter Stone's Selected Publications

Classified by TopicClassified by Publication TypeSorted by DateSorted by First Author Last NameClassified by Funding Source


Multi-Robot Planning with Conflicts and Synergies

Yuqian Jiang, Harel Yedidsion, Shiqi Zhang, Guni Sharon, and Peter Stone. Multi-Robot Planning with Conflicts and Synergies. Autonomous Robots, Springer, March 2019.
Official version from Publisher's Webpage

Download

[PDF]2.0MB  

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.

BibTeX Entry

@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 Wed Nov 25, 2020 21:30:58