We focus on the Multi-Robot pickup and delivery problem for logistic scenarios that recently received significant attention from the research community. In particular we consider an innovative variant of the pickup and delivery problem where robots can deliver, in a single travel, multiple items. We propose a decentralized coordination algorithm based on a token passing approach. Our algorithm allocates delivery tasks (i.e., an aggregation of items to be delivered by a single robot) to the Multi-Robot System avoiding conflicts among the robots. In more detail, we show that our approach generates conflict-free paths for the Multi-Robot system requiring weaker assumptions on the operational area compared to previous approaches. We empirically evaluate the proposed method on three different scenarios, including the production line of a smart factory, comparing the performance of our decentralized method against two centralized approaches. Results show that our approach finds solutions of similar quality (in terms of makespan and travel distance) reducing the associated computational effort. (C) 2021 Elsevier B.V. All rights reserved.

Coordination approaches for multi-item pickup and delivery in logistic scenarios

Antonello Contini;Alessandro Farinelli
2021

Abstract

We focus on the Multi-Robot pickup and delivery problem for logistic scenarios that recently received significant attention from the research community. In particular we consider an innovative variant of the pickup and delivery problem where robots can deliver, in a single travel, multiple items. We propose a decentralized coordination algorithm based on a token passing approach. Our algorithm allocates delivery tasks (i.e., an aggregation of items to be delivered by a single robot) to the Multi-Robot System avoiding conflicts among the robots. In more detail, we show that our approach generates conflict-free paths for the Multi-Robot system requiring weaker assumptions on the operational area compared to previous approaches. We empirically evaluate the proposed method on three different scenarios, including the production line of a smart factory, comparing the performance of our decentralized method against two centralized approaches. Results show that our approach finds solutions of similar quality (in terms of makespan and travel distance) reducing the associated computational effort. (C) 2021 Elsevier B.V. All rights reserved.
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: http://hdl.handle.net/11562/1060874
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact