# On-Demand Delivery Using Fleets of UAVs with Unknown, Heterogeneous Energy Storage

Mohamed S. Talamali, Genki Miyauchi, Thomas Watteyne, Roderich Gross

► To cite this version:

Mohamed S. Talamali, Genki Miyauchi, Thomas Watteyne, Roderich Gross. On-Demand Delivery Using Fleets of UAVs with Unknown, Heterogeneous Energy Storage. ANTS 2024 - IEEE International Conference on Advanced Networks and Telecommunications Systems, Dec 2024, Assam, India. . [hal-04723692](https://hal.inria.fr/hal-04723692v1)

HAL Id: hal-04723692

https://inria.hal.science/hal-04723692v1

Submitted on 7 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On-Demand Delivery Using Fleets of UAVs with Unknown, Heterogeneous Energy Storage

**Abstract**— Using UAVs for goods delivery can reduce costs, increase speed, and cut emissions. To achieve these benefits, optimising UAV deployment is crucial. Here, we focus on on-demand delivery where orders arrive stochastically and should be processed promptly—neither too late, which would prolong delivery times, nor too early, which could increase the risk of failed deliveries due to insufficient battery level. Unlike previous studies, we do not rely on a specific UAV energy model and consider unknown hardware conditions. We propose a decentralised auction-based strategy that enables UAVs, given their current battery level, to decide whether and how much to bid for an order. Our multi-agent simulations demonstrate that this approach outperforms methods that require UAVs to reach a specific battery level before deployment.

## I. PROBLEM FORMULATION

A Fulfillment Center (FC) operates a fleet of delivery UAVs $U = \{u_1, \dots, u_S\}$. During period $T$, the FC receives orders $O = \{o_1, o_2, \dots\}$, with an average inter-arrival time $\bar{\tau}$. Each order $o_i$ has an arrival time $t_i$, weight $w_i$, and delivery distance $d_i$. At any time $t \le T$, a subset of UAVs $U_a(t) \subset U$ is available with a battery state-of-charge $SoC_j(t)$. Orders queued for delivery at $t$ form the set $O_q(t) \subset O$, with $o_n(t)$ the next in line.

The goal is to develop a strategy to decide at each $t$ whether to deploy a UAV from $U_a(t)$ for $o_n(t)$ or delay deployment. This strategy aims to minimise (i) average delivery time and (ii) the occurrence of Low-Battery Return-To-Home (LRBTH) events. Deploying a UAV immediately reduces delivery times but increases LRBTH likelihood, while delaying deployment decreases LRBTH likelihood but extends delivery times. The decision is complicated by uncertain UAVs' energy models and hardware conditions.

## II. METHODS

a) **Decentralised deployment strategy:** This study presents a decentralised auction-based UAV deployment strategy implemented using the finite state machine of Fig. 1.a. UAVs with sufficient SoC enter the *Waiting* state. When orders are available, they use their bidding policy $\pi(\cdot)$ to decide whether to bid and, if so, move to the *Evaluating-Bids* state. Winning UAVs collect parcels and attempt delivery while losing UAVs return to *Waiting*. If the UAV's state of charge (SoC) drops to half the take-off value during transit, it aborts the delivery and returns. Otherwise, it will deliver the parcel before returning. Upon arrival to the FC, UAVs with low SoC enter the *Charging* state; otherwise, they enter the *Waiting* state.

This document is issued within the frame and for the purpose of the OpenSwarm project (European Union's Horizon Europe Framework Grant Agreement No. 101093046).

<figure><img src="image_2.png" /><figcaption>Fig. 1. (a) Finite state machine implementing the proposed deployment strategy. (b) Illustration of the online learning of the bidding policy.</figcaption></figure>

b) **Online learning a bidding policy:** To address the deployment problem, each UAV learns a bidding policy $\pi(\cdot)$ online. The UAV uses this policy to assess if it can complete the order $o_n(t)$ given its current state-of-charge. If capable, the UAV places a bid according to its confidence value; otherwise, it abstains. After each delivery attempt, the UAV updates its policy using details such as parcel weight, delivery distance, take-off SoC, and the attempt's outcome (successful delivery or LBRTH). Following this process (illustrated in Fig. 1b), the UAV indirectly learns its own energy model, considering its hardware condition.

## III. RESULTS

We evaluated our deployment strategy using multi-agent simulations with a standard UAV battery model [1]. We compared it to a strategy requiring UAVs to reach a minimum SoC before deployment. As shown in Fig. 2, the proposed strategy delivers faster and reduces LBRTH events for $S = 25$, $T = 8$ weeks, and $\bar{\tau} = \{5, 10, 15\}$ minutes.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Pareto optimality plot. Markers show the median values, and error bars show the 95% Confidence Interval of the median absolute deviation.</figcaption></figure>

## REFERENCES

[1] K. Dorling, J. Heinrichs, G. G. Messier, and S. Magierowski, "Vehicle routing problems for drone delivery," *IEEE Transactions on Systems, Man, and Cybernetics: Systems*, vol. 47, no. 1, pp. 70-85, 2017.
# On-Demand Delivery Using Fleets of UAVs with Unknown, Heterogeneous Energy Storage

<figure><img src="image_4.png" /></figure>

Inria

Mohamed S. Talamali<fnref n="1" />, Genki Miyauchi<fnref n="1" />, Thomas Watteyne<fnref n="2" />, Roderich Groß<fnref n="1" />,<fnref n="3" />

<figure><img src="image_5.png" /></figure>

## SCENARIO

### Online orders

<figure><img src="image_6.png" /></figure>

Stochastic
arrival times

<figure><img src="image_7.png" /></figure>

Parcel
weight

<figure><img src="image_8.png" /></figure>

Delivery
distance

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

### Fleet of delivery UAVs

<figure><img src="image_11.png" /></figure>

**Task:** a parcel of mass *m* to be delivered to a distance *d*

**Resource:** a set of UAVs, each with given charge levels *c*

### Questions:

1. Is there UAVs ready for the task?

2. If multiple, which one to deploy?

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

Unknown energy
consumption models

<figure><img src="image_15.png" /></figure>

Unknown and heterogeneous
battery health

## PROBLEM

## METHODS

<figure><img src="image_16.png" /></figure>

Each UAV:

<figure><img src="image_17.png" /></figure>

Decides whether to bid or not given parcel weight *m*, delivery distance *d* and its current charge *c*

<figure><img src="image_18.png" /></figure>

Places confidence-based bids

<figure><img src="image_19.png" /></figure>

Aborts delivery attempts when necessary

<figure><img src="image_20.png" /></figure>

Adjusts bidding policy based on experience

<figure><img src="image_21.png" /></figure>

### Auction-based task allocation + Online learning

<figure><img src="image_22.png" /></figure>

<figure><img src="image_23.png" /><figcaption>Deploying least confident bidding
UAV maximise performance</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Deploying least confident
allows better learning</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>Learning-based strategy
outperforms fixed waiting</figcaption></figure>

## RESULTS

<footnote n="1">¹ School of Electrical and Electronic Engineering, The University of Sheffield, UK, m.s.talamali@sheffield.ac.uk</footnote>

<footnote n="2">² Inria AIO team, Paris, France</footnote>

<footnote n="3">³ Department of Computer Science, Technical University of Darmstadt, Germany</footnote>

<footnote>* This document is issued within the frame and for the purpose of the OpenSwarm project. This project has received funding from the European Union's Horizon Europe Framework Programme under Grant Agreement No. 101093046. Views and opinions expressed are however those of the author(s) only and the European Commission is not responsible for any use that may be made of the information it contains.</footnote>