Multi-Agent Pickup and Delivery with Task Probability Distribution

Multi-Agent Pickup and Delivery (MAPD) consists in completing a set of tasks by having agents move to the pickup location and then to the delivery location of each task. In MAPD, new tasks are dynamically added to the system throughout its lifetime and existing algorithms usually assume either complete ignorance or full knowledge about the position and the time at which future tasks will appear until they are actually added to the system. This paper introduces a novel MAPD problem in which a spatial and temporal probability distribution of future tasks is known and defines algorithms that take advantage of this knowledge to reduce the average time required to execute tasks. In particular, we build on an existing MAPD algorithm, Token Passing (TP), proposing different ways to exploit a given task probability distribution. Experiments show that these methods can have a positive impact on the time required to complete the tasks.