Event Location: NSH 1305

Abstract: Many logistics problems require mobile agents to retrieve and deliver a set of items. For example, postal services and couriers retrieve and deliver letters and packages, while taxis pick up and drop off passengers. These problems are instances of the Pickup and Delivery Problem (PDP), in which a set of mobile agents retrieves and delivers a set of items. The goal is to find a schedule that minimizes fuel usage or delivery time, under constraints such as time, vehicle capacities, and task priorities. The PDP is a well-studied, NP-hard problem.

As autonomous mobile robots become increasingly capable and available, they offer new applications of the PDP. In fact, robots are already deployed in warehouses to retrieve and prepare goods for shipping, and our CoBot robots autonomously deliver mail to occupants of an office building.

In this thesis, I will introduce a novel approach to plan for PDPs with transfers (the PDP-T). Instead of having a single mobile agent retrieve and deliver each item, each agent can transfer items to other agents (or chains of agents) for delivery. By transferring items between mobile agents, a reduction in fuel cost and time is possible. Allowing transfers increases the number of possible delivery schedules exponentially, and leads to an especially challenging planning problem. In this thesis, I will address the PDP-T under various constraints, such as capacities, times, and task priorities. I will consider the offline, online and distributed PDP-T, and evaluate the algorithms both in simulation and on physical robots.

I have already accomplished several steps towards my overall thesis goal of planning to retrieve and deliver items with transfers. First, I have developed an approximation algorithm, based on the construction of a minimum spanning tree, for retrieving a set of items and delivering them to a central location, with transfers only at pickup and delivery points. I proved that this algorithm is two-approximate to the optimal solution, and showed that the optimal solution with transfers only at these fixed points in turn gives a two-approximation to the optimal solution with transfers that can occur anywhere. I showed that transferring items reduces the time taken and distance traveled, and demonstrated the algorithm on the CoBot and the CreBot robots. The CreBot robots transfer items autonomously by aligning their custom-built tilting trays. Second, I have developed algorithms to plan for ridesharing with transfers, in which passengers plan to catch rides from a sequence of driver
s. I demonstrated that transferring passengers between vehicles can reduce total fuel use on routes taken by San Francisco drivers. Furthermore, I have developed a distributed algorithm to dispatch mobile robots to handle events detected by a wireless sensor network. In this thesis, I will extend this work to develop a distributed algorithm to plan for deliveries with transfers.

My proposed remaining work for this thesis will include studying the online version of the problem, in which the delivery tasks are not known beforehand, and in which replanning is necessary in response to delays, cancellations and other unexpected events. I will study how to plan schedules with transfers using distributed algorithms and limited information, without a central controller. I will research how to plan for transfers under additional constraints, considering factors such as the time of both drivers and passengers, user preferences limiting the number of transfers, and task priorities. I will evaluate the effectiveness of the algorithms to plan to transfer items in simulation in both the ridesharing domain and the warehouse domain, in which robots deliver items in a warehouse to packing stations. I will also evaluate the planned schedules through execution on the CoBot and CreBot robots, executing user requests.

Committee:Manuela Veloso, Chair

Howie Choset

Stephen Smith

Daniele Nardi, Sapienza University of Rome