Peter Stone's Selected Publications

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


SCRAM: Scalable Collision-avoiding Role Assignment with Minimal-makespan for Formational Positioning

Patrick MacAlpine, Eric Price, and Peter Stone. SCRAM: Scalable Collision-avoiding Role Assignment with Minimal-makespan for Formational Positioning. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI), January 2015.
Accompanying videos at http://www.cs.utexas.edu/~AustinVilla/sim/3dsimulation/AustinVilla3DSimulationFiles/2013/html/scram.html

Download

[PDF]260.3kB  [postscript]676.5kB  [slides.pdf]40.3MB  

Abstract

Teams of mobile robots often need to divide up subtasks efficiently. In spatial domains, a key criterion for doing so may depend on distances between robots and the subtasks' locations. This paper considers a specific such criterion, namely how to assign interchangeable robots, represented as point masses, to a set of target goal locations within an open two dimensional space such that the makespan (time for all robots to reach their target locations) isminimized while also preventing collisions among robots. We present scaleable (computable in polynomial time) role assignment algorithms that we classify as being SCRAM (Scalable Collision-avoiding Role Assignment with Minimal-makespan).SCRAM role assignment algorithms use a graph theoretic approach to map agents to target goal locations such that our objectives for both minimizing the makespan and avoiding agent collisions are met. A system using SCRAM role assignment was originally designed to allow for decentralized coordination among physically realistic simulated humanoid soccer playing robots in the partially observable, non-deterministic, noisy, dynamic, and limited communication setting of the RoboCup 3D simulation league. In its current form,SCRAM role assignment generalizes well to many realistic and real-world multiagent systems, and scales to thousands of agents.

BibTeX Entry

@InProceedings{AAAI15-MacAlpine,
  author = {Patrick MacAlpine and Eric Price and Peter Stone},
  title = {{SCRAM}: Scalable Collision-avoiding Role Assignment with Minimal-makespan for Formational Positioning},
  booktitle = {Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI)},
  location = {Austin, Texas, USA},
  month = {January},
  year = {2015},
  abstract={
     Teams of mobile robots often need to divide up subtasks efficiently.  In 
spatial domains, a key criterion for doing so may depend on distances  between 
robots and the subtasks' locations.  This paper considers a specific such 
criterion, namely how to assign interchangeable robots, represented as point 
masses, to a set of target goal locations within an open two dimensional space 
such that the makespan (time for all robots to reach their target locations) is
minimized while also preventing collisions among robots.  We present scaleable 
(computable in polynomial time) role assignment algorithms that we classify as 
being SCRAM (Scalable Collision-avoiding Role Assignment with Minimal-makespan).
SCRAM role assignment algorithms use a graph theoretic approach to map agents 
to target goal locations such that our objectives for both minimizing the 
makespan and avoiding agent collisions are met.  A system using SCRAM role 
assignment was originally designed to allow for decentralized coordination 
among physically realistic simulated humanoid soccer playing robots in the 
partially observable, non-deterministic, noisy, dynamic, and limited 
communication setting of the RoboCup 3D simulation league.  In its current form,
SCRAM role assignment generalizes well to many realistic and real-world 
multiagent systems, and scales to thousands of agents.
  },
  wwwnote={Accompanying videos at <a href="http://www.cs.utexas.edu/~AustinVilla/sim/3dsimulation/AustinVilla3DSimulationFiles/2013/html/scram.html">http://www.cs.utexas.edu/~AustinVilla/sim/3dsimulation/AustinVilla3DSimulationFiles/2013/html/scram.html</a>},
}

Generated by bib2html.pl (written by Patrick Riley ) on Wed Nov 08, 2017 15:02:40