07-10-2016, 12:00 PM
1458191349-10.1.1.475.7971.pdf (Size: 2.75 MB / Downloads: 4)
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 services a set of
spatially-located requests. 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 general 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. Approximation algorithms and heuristics exist
for some variants of the PDP, with varying levels of effectiveness.
In this thesis, I will introduce a novel approach to plan for multi-agent retrievals
and deliveries with transfers. 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 problem of planning with transfers under various constraints, such
as capacities, times, and task priorities. I will consider both the offline and the online
cases, where the tasks are not known beforehand. I will evaluate the algorithms for
planning with transfers 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
dropoff 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, which perform
delivery tasks requested by users in an office building. The CreBot robots transfer
items autonomously by aligning their custom-built tilting trays. Second, I have developed
three algorithms to plan for ridesharing with transfers, in which passengers
plan to catch rides from a sequence of drivers: a greedy algorithm, an auction algorithm,
and an algorithm based on finding the shortest path in a graph. Each of these
algorithms provides a tradeoff between computational cost and solution effectiveness.
I demonstrated on routes taken by San Francisco drivers that transferring passengers
between vehicles can reduce total fuel use. 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 (and the vehicle routes themselves, in the ridesharing domain) 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, 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
Introduction
1.1 Motivation
Many types of logistics problems require mobile agents to retrieve and deliver a set of
objects. For example, taxis pick up and drop off passengers, mail services retrieve and
deliver letters and packages, and airplanes deliver passengers and freight. All of these
problems are instances of the Pickup and Delivery Problem (PDP), in which a set of
mobile agents services a set of spatially-located requests. Given a set of object pickup
and dropoff locations, along with a set of mobile agents, the goal is to find a schedule
for the agents to minimize energy consumed or delivery time, under constrains such
as time windows, vehicle capacities, and task priorities. The PDP is a well-studied,
NP-hard problem, so approximation algorithms and heuristics have been developed to
address variants of the PDP.
As autonomous mobile robots become increasingly capable and available, they offer
new applications of the PDP. Our multiple CoBot robots currently deliver items, such
as mail, autonomously to occupants of an office building in response to user requests.
These robots localize and navigate robustly, and are capable of using the elevator to
move between floors and deliver items by using symbiotic autonomy, the idea that
robots and humans can complement one another’s shortcomings (see Figure 1. Since
the CoBots have no arms, humans help by pushing elevator buttons and placing items
in their baskets. To deliver items as effectively as possible, algorithms are needed
to address the PDP and form schedules of tasks for the robots. These schedules must
account for robot capacities, time constraints, limited battery life, and more, and plans
must be created and modified online in response to delays, cancellations, and new task
requests. Immediate applications of the PDP to autonomous robots are not limited
to the CoBot robots: autonomous robots are already deployed to retrieve and deliver
items for distribution in warehouses.
In this thesis, we introduce and contribute a novel extension to the PDP: allowing
agents to transfer items to other agents before delivery. We call this problem the
Pickup and Delivery Problem with Transfers (PDP-T). With transfers, one robot may
pick up an object and transfer it a different robot (or a chain of robots) for delivery.
Transferring items enables a reduction in battery / fuel cost and delivery time for many
problem instances.
Figure 2 shows an example of the benefits of transferring items. In Figure 2a, one
robot picks up and then delivers all the items A, B, C and D. The robot travels six
corridors of distance over a corresponding six units of time. In Figure 2b, a second
robot is introduced. With two robots delivering the items, each picks up the items near
its starting position and delivers one to each of the two delivery points. An increased
eight units of distance are travelled, but delivery now only takes four units of time.
Next, in Figure 2c we consider two robots that can transfer items. At the intersection
of the two corridors, the robots swap items B and C. Now, each robot only needs to
travel to the end of a single corridor to deliver both of its items. By transferring items,
we reduce the total distance travelled to four units and the delivery time to two units.
Transferring empowers us to make deliveries more efficiently because items heading in
the same direction can be routed to the same vehicle, dividing the transportation cost
between the items. While this simple example demonstrates the benefits of transferring
items in the PDP-T, there are many algorithmic challenges that must be addressed to
effectively plan for deliveries with transfers.
We are especially interested in the problem of transfers because, unlike in traditional
multi-robot task allocation, the individual tasks are tightly coupled. The cost of a
schedule with transfers depends highly on the combination of tasks assigned to all of
the robots. Planning for transfers requires multi-robot coordination and cooperation
in the fullest sense, rather than simply the execution of tasks independently in parallel.
1.2 Thesis Approach
In this thesis, I will introduce a novel approach to plan for multi-agent retrievals and
deliveries with transfers. Instead of requiring a single mobile agent to retrieve and
deliver each item, an 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
delivery time is possible. Allowing transfers increases the number of possible delivery
schedules exponentially, and leads to an especially challenging planning problem.
The work in this thesis will have four major components:
1. Planning for transfers when the tasks are known beforehand (the offline problem),
2. Planning and replanning for transfers when the tasks are not known beforehand
(the online problem),
3. Planning for transfers with distributed algorithms, and
4. Evaluating plans with transfers on multiple domains, both in simulation and on
physical robots.
We will discuss each component of the thesis in greater detail.
Offline Planning for Transfers Under Constraints First, in this thesis we
will seek to develop algorithms to solve the PDP-T when the items to be retrieved and
delivered are known beforehand. Allowing transfers increases the number of possible
schedules exponentially, so practically useful scheduling algorithms will be approximations
or heuristics which do not necessarily give the optimal schedule in terms of
execution cost or time. However, in certain special cases we can provide bounds on an
algorithm’s suboptimality, as will be discussed in our previous work.
We will consider planning for transfers under various problem-dependent constraints.
These constraints include properties such as vehicular capacities and budgets,
time windows for pickups and deliveries, task priorities, and consideration of the cost of
transferring. We will evaluate the effectiveness of these plans, especially in comparison
to plans which do not include transfers.
Online Planning for Transfers with Replanning The second part of this
thesis will consider the PDP-T when the items to be transported are not known beforehand.
Examples of this problem in the real world include delivering passengers
on demand with a fleet of taxis, or servicing instantaneous requests with the CoBot
robots. For the online problem, an optimal solution is not possible. It is also important
to plan for agents to be available to handle requests in areas which are expected to
have high demand.
When deploying robots in the real world, we can expect that things will not go as
planned. The same is true of pickup and delivery problems with transfers. We will
examine how to replan when robots are late, when robots are early, and when online
requests are cancelled or changed. When replanning, we will attempt to change the
pickup and delivery times for the other items as little as possible.