In this paper, we demonstrate how topological constraints, as well as other abstract constraints, can be integrated into task allocation by applying the combinatorial theory of matroids. By modeling problems as an intersection of matroid constraints, arbitrary combinatorial relationships can be achieved in the task allocation space. To illustrate the expressiveness of the framework, we model a novel task allocation problem that couples abstract per-robot constraints with a communication spanning tree constraint. As our problem is cast as a matroid intersection, provable optimality bounds with simple greedy algorithms follows immediately from theory. Next, we present a decentralized algorithm that applies auction methods to task allocation with matroid intersections. Simulations of task allocation for surveillance in urban environments demonstrate our results. Finally, Monte Carlo results are provided that indicate greedy task allocations can be highly competitive even with near-optimal solutions in practice.

Williams, R.K., Gasparri, A., Ulivi, G. (2017). Decentralized matroid optimization for topology constraints in multi-robot allocation problems. In Proceedings - IEEE International Conference on Robotics and Automation (pp.293-300). Institute of Electrical and Electronics Engineers Inc. [10.1109/ICRA.2017.7989038].

Decentralized matroid optimization for topology constraints in multi-robot allocation problems

Gasparri, Andrea;Ulivi, Giovanni
2017-01-01

Abstract

In this paper, we demonstrate how topological constraints, as well as other abstract constraints, can be integrated into task allocation by applying the combinatorial theory of matroids. By modeling problems as an intersection of matroid constraints, arbitrary combinatorial relationships can be achieved in the task allocation space. To illustrate the expressiveness of the framework, we model a novel task allocation problem that couples abstract per-robot constraints with a communication spanning tree constraint. As our problem is cast as a matroid intersection, provable optimality bounds with simple greedy algorithms follows immediately from theory. Next, we present a decentralized algorithm that applies auction methods to task allocation with matroid intersections. Simulations of task allocation for surveillance in urban environments demonstrate our results. Finally, Monte Carlo results are provided that indicate greedy task allocations can be highly competitive even with near-optimal solutions in practice.
2017
9781509046331
Williams, R.K., Gasparri, A., Ulivi, G. (2017). Decentralized matroid optimization for topology constraints in multi-robot allocation problems. In Proceedings - IEEE International Conference on Robotics and Automation (pp.293-300). Institute of Electrical and Electronics Engineers Inc. [10.1109/ICRA.2017.7989038].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/332640
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 37
  • ???jsp.display-item.citation.isi??? ND
social impact