Multiagent Pickup and Delivery for Capacitated Agents

Çilden E., POLAT F.

20th International Conference on Practical Applications of Agents and Multi-Agent Systems , PAAMS 2022, L'Aquila, Italy, 13 - 15 July 2022, vol.13616 LNAI, pp.76-87 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 13616 LNAI
  • Doi Number: 10.1007/978-3-031-18192-4_7
  • City: L'Aquila
  • Country: Italy
  • Page Numbers: pp.76-87
  • Keywords: MAPD with Capacities (MAPDC), Multiagent Pickup and Delivery (MAPD), Warehouse automation
  • Middle East Technical University Affiliated: Yes


© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.In Multi-Agent Pickup and Delivery (MAPD), multiple robots continuously receive tasks to pick up packages and deliver them to predefined destinations in an automated warehouse. If the capacity of agents is increased, agents can pick up more than one item on their way, which will presumably reduce the time required to accomplish all deliveries–that is, makespan. In this paper, we propose two algorithms for MAPD with Capacities (MAPDC) that are complete and scalable: Token Passing with Multiple Task Assignments (TPMT) and Token Passing with Multiple Capacity (TPMC). Both of the methods are based on the Token Passing (TP) algorithm, one of the suboptimal and complete solutions by Ma et al. [6]. The performance of the algorithms is analyzed in terms of makespan, service time, and throughput. TPMC turns out to be more effective than TPMT at utilizing capacitated agents.