In this paper, we propose a distributed version of the Hungarian method to solve the well-known assignment problem. In the context of multirobot applications, all robots cooperatively compute a common assignment that optimizes a given global criterion (e.g., the total distance traveled) within a finite set of local computations and communications over a peer-to-peer network. As a motivating application, we consider a class of multirobot routing problems with “spatiotemporal” constraints, i.e., spatial targets that require servicing at particular time instants. As a means of demonstrating the theory developed in this paper, the robots cooperatively find online suboptimal routes by applying an iterative version of the proposed algorithm in a distributed and dynamic setting. As a concrete experimental test bed, we provide an interactive “multirobot orchestral” framework, in which a team of robots cooperatively plays a piece of music on a so-called orchestral floor.

A Distributed Version of the Hungarian Method for Multirobot Assignment / Chopra Smriti; Notarstefano Giuseppe; Rice Matthew; Egerstedt Magnus. - In: IEEE TRANSACTIONS ON ROBOTICS. - ISSN 1552-3098. - STAMPA. - 33:4(2017), pp. 932-947. [10.1109/TRO.2017.2693377]

A Distributed Version of the Hungarian Method for Multirobot Assignment

Notarstefano Giuseppe;
2017

Abstract

In this paper, we propose a distributed version of the Hungarian method to solve the well-known assignment problem. In the context of multirobot applications, all robots cooperatively compute a common assignment that optimizes a given global criterion (e.g., the total distance traveled) within a finite set of local computations and communications over a peer-to-peer network. As a motivating application, we consider a class of multirobot routing problems with “spatiotemporal” constraints, i.e., spatial targets that require servicing at particular time instants. As a means of demonstrating the theory developed in this paper, the robots cooperatively find online suboptimal routes by applying an iterative version of the proposed algorithm in a distributed and dynamic setting. As a concrete experimental test bed, we provide an interactive “multirobot orchestral” framework, in which a team of robots cooperatively plays a piece of music on a so-called orchestral floor.
2017
A Distributed Version of the Hungarian Method for Multirobot Assignment / Chopra Smriti; Notarstefano Giuseppe; Rice Matthew; Egerstedt Magnus. - In: IEEE TRANSACTIONS ON ROBOTICS. - ISSN 1552-3098. - STAMPA. - 33:4(2017), pp. 932-947. [10.1109/TRO.2017.2693377]
Chopra Smriti; Notarstefano Giuseppe; Rice Matthew; Egerstedt Magnus
File in questo prodotto:
File Dimensione Formato  
2017tro_chopra_post.pdf

accesso aperto

Tipo: Postprint
Licenza: Licenza per accesso libero gratuito
Dimensione 13.35 MB
Formato Adobe PDF
13.35 MB Adobe PDF Visualizza/Apri

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/11585/671765
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 111
  • ???jsp.display-item.citation.isi??? 81
social impact