Multi-Agent Pickup and Delivery Problems in Uncertain Environments

Abstract

The aging of society, population growth and chronic under-investments in education of healthcare workers have all led to a major imbalance between the demand for healthcare and the supply of healthcare. Autonomous robots can be used to relieve overqualified healthcare workers of their repetitive transportation tasks, allowing them to spend more time on actual patient care, hence reducing this imbalance. One of the greatest challenges that must be overcome is the dynamic changes in the environment, which affects the traversability of corridors and thus travel times. This challenge also arises in other human-centric and urban areas where constantly arriving delivery tasks have to be completed such as autonomous mobility-on-demand systems, autonomous warehouses and same-day delivery services. In the hospital environment these dynamic changes occur naturally and can only be observed on-site, which makes them difficult to model. This thesis attempts to fill this gap in literature and therefore studies the online Multi-Agent Pickup and Delivery (MAPD) problem with binary, recoverable and stochastic blockages. The task is twofold in that both the tasks have to be assigned to the agents and the shortest paths for each agent have to be found. The stochastic, binary blockages result in parts of the environment becoming untraversable for a random amount of time. First, an observation model is created that records the blockages and uses the input parameters of the blockage model to estimate the current expected travel times of the edges affected by a blockage. These estimates are then incorporated into the graph used to compute the agents' routes, and an online centralized MAPD algorithm is derived. A waiting state is introduced that allows agents to wait at blockages instead of replanning their paths, and it is demonstrated why replanning is necessary after each observation. This thesis presents numerous experiments on different maps with various blockage parameter configurations to show that the proposed algorithm is more effective than naive algorithms even with noisy blockage parameter estimates. Furthermore, if the initial blockage model parameters are unknown we show that the maximum likelihood estimates can be used as inputs of the blockage model and still outperform the naive methods.