Online Pickup and Delivery Planning with Transfers for Mobile Robots

We have deployed a fleet of robots that pickup and deliver items requested by users in an office building. Users specify time windows in which the items should be picked up and delivered, and send in requests online. Our goal is to form a schedule which picks up and delivers the items as quickly as possible at the lowest cost. We introduce an auction-based scheduling algorithm which plans to transfer items between robots to make deliveries more efficiently. The algorithm can obey either hard or soft time constraints. We discuss how to replan in response to newly requested items, cancelled requests, delayed robots, and robot failures. We demonstrate the effectiveness of our approach through execution on robots, and examine the effect of transfers on large simulated problems