Job selection in UAV-based delivery services

Aerial delivery services using small unmanned aerial vehicles (UAVs) have been proposed by major online retailers, logistics companies, and startups. An interdisciplinary project team at the University of Klagenfurt aims at contributing to the architectural setup and distributed control of such future systems.

Small UAVs have found their way to civil applications. A broad variety of UAV models has been developed and commercialized in the past few years and is available today for end users. UAVs fly routes in an autonomous manner, carry cameras for aerial photography, and may transport goods from one place to another. The range of applications is broad, including aerial monitoring of industrial plants and agriculture fields as well as support for first time responders in case of disasters.

Minidrone delivers a parcel

Minidrone delivers a parcel

Delivering goods via a network of UAVs becomes an option if classical means of transportation, like trucks, trains, and planes are inappropriate. First, this comes about if roads, railway tracks, or landing facilities do not exist, if natural disasters make it impossible to use them, or if their use is too dangerous or too time-consuming. In this context, a compelling service would be the delivery of medicine, vaccinations, or laboratory samples for patients in remote areas and crisis regions. Second, such a service is also worthwhile in densely populated metropolitan areas, when congestion makes roads nearly impassable.

The architectural setup and control of such UAV-based delivery systems are the subject of research of the SOSIE project team at the University of Klagenfurt funded by Lakeside Labs.

Project team: Grippa, Behrens, Bettstetter, Wall

Project team: Grippa, Behrens, Bettstetter, Wall

Policies are analyzed that control how an interconnected team of UAVs resolves service requests that are randomly distributed in space and time. The entities of the system are goods, customers, vehicles, and depots. Customers request goods that are stored in depots and delivered by vehicles. Service requests, also denoted as jobs or customer demands, are not known in advance and arrive over time for certain locations according to a space-time stochastic process.

Instead of applying a centralized scheduler that intends to optimize the performance, the Klagenfurt team employs a set of rules to be run in each vehicle. “Such a distributed approach is required if no central control entity is available,” postdoctoral researcher Doris Behrens states. In this sense, the system’s “intelligence” is literally embedded into each vehicle, meaning that each vehicle decides by its own which job to select next, thus raising the autonomy of vehicles to a level that goes beyond autonomous flying.

The approach is to combine short-term decisions (e.g., job selection policy), mid-term decisions (e.g., number of vehicles), and long-term decisions (e.g., number of depots) into an integrated decision-making model.

Relation between infrastructure expenditure and average delivery time for certain parameters (see paper). Click to enlarge.

Expenditure for infrastructure over delivery time for certain parameters. Click to enlarge.

Taking into account the short and mid-term horizons, the delivery time of such a networked system experiences a threshold behavior: a stable system could lead to instability all of a sudden if one vehicle fails; adding vehicles has almost no positive influence on delivery time once the number of vehicles exceeds a certain threshold. The timing of job selection has significant impact on delivery time and stability and it depends on the used policy. Certain policies benefit from delayed job selection; others take advantage of instantaneous job selection.

A forthcoming publication of the project team introduces a methodological approach for decision-making support to set up a stable delivery system for efficiently resolving the tradeoff between expenditure and service quality. This approach reflects all three time horizons and includes an analytically derived service possibility frontier.

Publication
P. Grippa, D.A. Behrens, C. Bettstetter, F. Wall:
Job Selection in a Network of Autonomous UAVs for Delivery of Goods.
Under review. Preprint available on request, 2014.

This blog entry was written by the four authors; photos were made by Christian Philipp, Lakeside Labs.

Originally published: At the Website of C. Bettstetter.