Multi-agent Pick and Delivery with Capacities: Action Planning Vs Path Finding

Tajelipirbazari N., Yildirimoglu C. U., Sabuncu O., Arici A. C., Ozen I. H., Patoglu V., ...Daha Fazla

24th International Conference on Practical Aspects of Declarative Languages, PADL 2022, Pennsylvania, Amerika Birleşik Devletleri, 17 - 18 Ocak 2022, cilt.13165 LNCS, ss.24-41 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 13165 LNCS
  • Doi Numarası: 10.1007/978-3-030-94479-7_3
  • Basıldığı Şehir: Pennsylvania
  • Basıldığı Ülke: Amerika Birleşik Devletleri
  • Sayfa Sayıları: ss.24-41
  • Anahtar Kelimeler: Action planning, Answer set programming, Multi-agent path finding, Pick and delivery with capacities
  • TED Üniversitesi Adresli: Evet

Özet

© 2022, Springer Nature Switzerland AG.Motivated by autonomous warehouse applications in the real world, we study a variant of Multi-Agent Path Finding (MAPF) problem where robots also need to pick and deliver some items on their way to their destination. We call this variant the Multi-Agent Pick and Delivery with Capacities (MAPDC) problem. In addition to the challenges of MAPF (i.e., finding collision-free plans for each robot from an initial location to a destination while minimizing the maximum makespan), MAPDC asks also for the allocation of the pick and deliver tasks among robots while taking into account their capacities (i.e., the maximum number of items one robot can carry at a time). We study this problem with two different approaches, action planning vs path finding, using Answer Set Programming with two different computation modes, single-shot vs multi-shot.