Publications

Sorted by DateClassified by Publication TypeClassified by Research Category

Effective Approximations for Multi-Robot Coordination in Spatially Distributed Tasks

Daniel Claes, Philipp Robbel, Frans A. Oliehoek, Daniel Hennes, Karl Tuyls, and Wiebe Van der Hoek. Effective Approximations for Multi-Robot Coordination in Spatially Distributed Tasks. In Proceedings of the Tenth AAMAS Workshop on Multi-Agent Sequential Decision Making in Uncertain Domains (MSDM), May 2015.

Download

pdf [382.0kB]  

Abstract

Although multi-robot systems have received substantial research attention in recent years, multi-robot coordination still remains a difficult task. Especially, when dealing with spatially distributed tasks and many robots, central control quickly becomes infeasible due to the exponential explosion in the number of joint actions and states. We propose a general algorithm that allows for distributed control, that overcomes the exponential growth in the number of joint actions by aggregating the effect of other agents in the system into a probabilistic model, called subjective approximations, and then choosing the best response. We show for a multi-robot grid-world how the algorithm can be implemented in the well studied Multiagent Markov Decision Process framework, as a sub-class called spatial task allocation problems (SPATAPs). In this framework, we show how to tackle SPATAPs using online, distributed planning by combining subjective agent approximations with restriction of attention to current tasks in the world. An empirical evaluation shows that the combination of both strategies allows to scale to very large problems, while providing near-optimal solutions.

BibTeX Entry

@inproceedings{Claes15MSDM,
    author    = {Daniel Claes and Philipp Robbel and  Frans A. Oliehoek and
                 Daniel Hennes and Karl Tuyls and Van der Hoek, Wiebe},
    title =     {Effective Approximations for Multi-Robot Coordination in Spatially Distributed Tasks},
    booktitle = MSDM15,
    year      = {2015},
    month =     may,
    keywords =  {workshop},
    abstract = {
    Although multi-robot systems have received substantial research attention
    in recent years, multi-robot coordination still remains a difficult
    task.  Especially, when dealing with spatially distributed tasks and
    many robots, central control quickly becomes infeasible due to the
    exponential explosion in the number of joint actions and states.  We
    propose a general algorithm that allows for distributed control, that
    overcomes the exponential growth in the number of joint actions by
    aggregating the effect of other agents in the system into a
    probabilistic model, called subjective approximations, and then
    choosing the best response.  We show for a multi-robot grid-world how
    the algorithm can be implemented in the well studied Multiagent Markov
    Decision Process framework, as a sub-class called spatial task
    allocation problems (SPATAPs).  In this framework, we show how to
    tackle SPATAPs using online, distributed planning by combining
    subjective agent approximations with restriction of attention to
    current tasks in the world.  An empirical evaluation shows that the
    combination of both strategies allows to scale to very large problems,
    while providing near-optimal solutions.        
    }
}

Generated by bib2html.pl (written by Patrick Riley) on Mon Oct 07, 2024 14:17:04 UTC