key: cord-0604415-0pdfvkg9 authors: Shahzaad, Babar; Bouguettaya, Athman; Mistry, Sajib title: Robust Composition of Drone Delivery Services under Uncertainty date: 2021-07-18 journal: nan DOI: nan sha: c9a5c4e7edece5809eed27b09e33c405ff069a43 doc_id: 604415 cord_uid: 0pdfvkg9 We propose a novel robust composition framework for drone delivery services considering changes in the wind patterns in urban areas. The proposed framework incorporates the dynamic arrival of drone services at the recharging stations. We propose a Probabilistic Forward Search (PFS) algorithm to select and compose the best drone delivery services under uncertainty. A set of experiments with a real drone dataset is conducted to illustrate the effectiveness and efficiency of the proposed approach. Drones have created a myriad of new opportunities in various practical fields [1] . Commercial applications of drones include agriculture, healthcare, and delivery [2] . During the COVID-19 pandemic, several countries have leveraged drone technology to provide safe, contactless, and more resilient alternatives to deliver goods in remote locations [3] . Major competitors in the delivery service industry such as Amazon and Google are expanding the use of drones for delivery services as a complement to traditional delivery modes [4] . Drones offer fast, convenient, and cost-effective delivery services compared to land-based delivery [5] . The service paradigm [6] provides a powerful abstraction of the functional and non-functional or Quality of Service (QoS) properties of a drone termed as Drone-as-a-Service (DaaS) [7] . The functional property is expressed as the package delivery from a designated source (take-off) station (e.g., warehouse rooftop) to a destination (landing) station. The QoS properties of a DaaS include payload, battery capacity, and flight range. DaaS usually uses a skyway network to operate in a geographic area [8] . A skyway network is defined as joining a set of nodes (vertices) representing takeoff and/or landing and/or recharging stations. A line segment between any two nodes represents the service abstraction. An instantiation of this service representation is delivering a package between the two nodes of the segment under a set of requirements/constraints. DaaS composition is the process of selecting the best drone-based services that form a skyway path from a given source to a destination [9] . The composition is naturally fit to deliver packages considering different QoS requirements from the end-users, e.g., fastest, cost-efficient, safe, and contactless delivery. Existing DaaS composition approaches are deterministic in nature [9] , [10] , [11] . These compositions do not consider uncertainties that affect the QoS of the composition, e.g., failed deliveries, longer delivery time, and excessive battery recharging time at intermediate nodes. Uncertainty is an extrinsic part of the dynamic drone service environment. For example, uncertainty in the flight behavior is caused by realtime variations in environmental conditions such as wind conditions and temperature [12] . High-rise buildings greatly impact the amplification of wind speed and temperature in urban areas [13] . In this study, our particular focus is on the wind effects on drone delivery time, including "headwind" and "tailwind". Flying with strong wind could increase (tailwind) or decrease (headwind) energy consumption and drone speed [14] . The headwind reduces the flight range of a drone while tailwind extends the flight range. The accurate predictions of wind for a long-term period may not be possible due to its highly stochastic nature [15] . In addition, multiple drone delivery services which operate in the same network may cause congestion at certain charging stations, thus creating uncertainty. Congestion occurs due to the simultaneous arrival of other drones at the same station occupying all the available pads. We propose a robust DaaS composition framework to select and compose a set of best drone services. In this paper, the term robust refers to the algorithm's ability to resist the unwanted effects of uncertain environmental changes. We assume that no handover of packages occurs among drones in the air or at intermediate stations as each drone has its own delivery plan, i.e., the same drone delivers the package from source to destination. We focus on recharging constraints and changes in wind patterns as uncertainty factors in urban settings. We assume that intrinsic factors are deterministic, whereas extrinsic factors are stochastic. The payload, battery capacity, and flight range of each drone are known beforehand. The availability of recharging pads at each station and the wind conditions are assumed to be probabilistic in nature. We propose a Probabilistic Forward Search (PFS) algorithm to find the robust DaaS composition. The PFS approach uses a probabilistic distribution of predicted wind for the selection of drone services. The decision-making in the PFS approach is based on the recharging pads' availability at adjacent and next-to-adjacent recharging stations. In addition, the decision-making depends upon the wind conditions on the skyway segments leading to these recharging stations. Therefore, the PFS approach may provide better results than baseline approaches. The main contributions of this paper are as follows: • Designing an uncertainty-aware DaaS system model for drone-based services. • Developing a Probabilistic Forward Search (PFS)-based approach for the best drone service selection and composition. • Conducting experiments using a real drone dataset to illustrate the performance of the proposed probabilistic composition approach. In recent years, the routing and scheduling of drone services has become an active area of research. Most existing works focus on combined delivery of drones with ground vehicles. An adaptive large neighbourhood search method is developed to address the TSP with multiple drones [16] . The goal of this work is to reduce the delivery cost to serve all customers for both ground vehicle and drones. A greedy algorithm is used for generating an initial TSP solution. The proposed approach uses the initial solution to remove nodes from the vehicle route and adds them to the drone routes. A TSP solution with multiple drones is compared to a TSP solution with a single drone. It is concluded that more drones support the generation of efficient routes in comparison to a single drone. The proposed method uses a ground vehicle for deliveries which is not appropriate for locations with no road access. In addition, the proposed method does not take into account the recharging constraints and wind uncertainty. An energy consumption model is presented for automated drone delivery services in [17] . They assumed that drones can perform multi-package deliveries in a predefined service area. The drone fleet size is optimized by analyzing the impact of payload weight and flight range considering battery capacity. They explore the relationship between four variables (working period, drone speed, demand density of service area, and battery capacity) to minimize the total costs of the drone delivery system. The study indicated that the long hours of operation would benefit both service providers and customers. They found that drone deliveries are more cost-effective in areas with high demand densities. This study does not consider the dynamic congestion conditions at recharging stations and uncertain wind conditions. There is a paucity of literature concerning the wind effects on drone delivery. Selecky et al. [18] studied the wind effects which influences the flight direction of a drone. An accelerated A* algorithm is developed to incorporate the wind effects and generate reachable states. The wind is assumed to be constant which does not capture the realworld scenarios. The proposed approach does not consider the wind variation and wind uncertainty in different areas. The drone delivery problem is abstracted using service paradigm in [7] . The function of the drone is to deliver a package from one node to another node over a line segment in the skyway network. A service model is designed considering the spatio-temporal feature of drone services. A heuristic-based algorithm is developed to select and compose right drone services taking into account the QoS properties. The proposed approach focuses only on the deterministic properties of services which is not realistic. This work has been extended in [9] as a constraint-aware deterministic composition approach to incorporate the recharging constraints at stations. A lookahead heuristic-based algorithm is presented for selection and composition of optimal services. A resilient composition framework is proposed for drone delivery services considering congestion conditions at recharging stations [19] . The framework includes a formal service model for the representation of constraint-aware drone services. An initial offline drone service composition plan is generated using a deterministic lookahead algorithm. A heuristic-based resilient composition approach is proposed to adapt the runtime changes in the initial composition plan and update it to meet the delivery requirements of the user. The proposed approach does not consider the probabilistic nature of the wind, which changes with time. In addition, the robustness of the composition is not considered, which is of paramount importance for efficient service delivery. To the best of our knowledge, this paper is the first attempt to present a robust DaaS composition that considers the uncertain wind conditions. We propose an uncertainty-aware DaaS system model for drone delivery services. The proposed system model is divided into two sub-models: (1) DaaS Model and (2) DaaS Delivery Model under Uncertainty. The DaaS, composite DaaS service, and DaaS composition problem are defined as follows. id is a unique drone service ID, • DaaS f represents the delivery function of a drone over a line segment. The location and time of a DaaS are 2-tuples < loc s , loc e > and < t s , t e >, where loc s and loc e represent the pickup location and the delivery location, t s and t e represent the start time and the end time, • DaaS q is an n-tuple < q 1 , q 2 , . . . , q n >, where each q i represents a quality parameter of a DaaS, e.g., flight range. . . , f n (DaaS n )}, where each f i represents function of corresponding component DaaS DaaS i ∈ CS • CSQ is an m-tuple < Q 1 , Q 2 , . . . , Q m >, where each Q j denotes an aggregated value of j th quality parameter of component DaaS DaaS i ∈ CS. Definition 3: DaaS Composition Problem. We build upon and extend the drone service and quality model proposed in [7] . Given a set of DaaS services S DaaS = {DaaS 1 , DaaS 2 , ..., DaaS n }, the DaaS composition problem is to compose the services for delivering a package from the warehouse to the customer location in minimum time. In the existing DaaS model [7] , all the drone services and the service environment are deterministic, i.e., the availability and QoS-values of services are known beforehand. We extend this model by introducing the dynamic recharging constraints and incorporating the wind effects. The stochastic nature of wind has a significant nonlinear effect on the energy consumption rate and flight range of a drone [14] . The headwinds drain the drone's energy more quickly, while the tailwinds reduce energy consumption. We determine the impact of wind speed and direction (i.e., headwind and tailwind) on the travel time of the drone. We use the method in [20] to calculate the effects of headwind and tailwind on the travel time from node i to j as follows. where θ ij is the bearing from node i to j, θ W S is the wind bearing, δ is the course correction angle, W S is the wind speed, A is the headwind/tailwind, C and B are the wind adjustment angles, AS is the air speed, GS is the ground speed, d ij is the distance between nodes i and j, and T ij is the travel time from node i to j. When |δ| < 90, A is negative and denotes headwind. When 90 < |δ| ≤ 180, A is positive and denotes tailwind. A drone can take a finite set of actions at each node during its journey from source to destination. A drone can either wait, recharge, or travel from one node to another. The objective is to take the right actions to reach the destination faster. Based on the probability distribution of wind speed and direction, the actions create a huge set of state space. Therefore, we transform the problem of action selection at any node into probabilistic state transition tree. We formally define a state as follows. Definition 4: State. A state is a 3-tuple < N.id, T ST P, BP >, where • N.id is a unique node identifier, • T ST P is a timestamp which represents a recorded time snapshot of a state, • BP represents the number of busy recharging pads at a certain station. A single DaaS may not satisfy a user's long-distance delivery requirements. In such cases, a robust drone service composition is required from a large set of candidate services. The DaaS composition under uncertainty is a challenging task. An adjacent attractive drone service may lead to a highly time-expensive service. For instance, we are given a skyway network with the source location and destination location. Our target is to find the selection and composition of temporally optimal drone services considering wind conditions. In this context, temporally optimal refers to leading towards the destination faster. The wind conditions are time-variant which cause uncertainty for future drone services. We require to predict the future wind conditions and their effects on the overall delivery time. We focus on the uncertain wind conditions that may result in longer delays for delivery by drones. Informed Exhaustive Search (IES) approach is an allpaths search method [21] . In this approach, no uncertainty is involved during the service composition process, i.e., the actual information about wind speed and direction is known. IES computes all possible DaaS compositions from source to destination and selects an optimal composition based on QoS parameters (i.e., delivery time). Finding all possible DaaS compositions is computationally not feasible and limits the use of IES for large-scale problems. The time complexity of IES is exponential, which reduces its performance significantly. We propose a Probabilistic Forward Search (PFS) heuristic-based solution for robust DaaS composition under uncertainty. In the proposed approach, the term forward search refers to considering next-to-adjacent states (services) in decision making. The accuracy of the predicted probability distribution of wind affects the selection of an optimal drone service. Our predictive model is based on the historical data of wind speed and direction in a specific time slot. The prediction is made for each skyway segment to estimate the arrivals of other drone services in the future. Most of Figure 1 . State selection using PFS the existing prediction models focus on the shortest path from source to destination. Due to the wind uncertainty and congestion conditions at recharging stations, the shortest path's travel time may not guarantee the overall shortest time from source to destination. We compute the sum of the travel, waiting, and recharging times to select a service. Fig. 1 illustrates how the PFS approach favors the optimal service (state) selection. Using the PFS approach provides more information to guide the selection of overall optimal states. The principle of PFS-based tree exploration is similar to a depth-first search. However, we use the PFS approach to select only one service at a time. The details are given in Algorithm 1. In Algorithm 1, the output is a robust DaaS composition from a designated source to a destination. We first use the Block Nested Loop (BNL) [22] algorithm for selecting a set of optimal drones from a large set of delivery drones given the payload weight (Line 2). Multiple service providers offer drone services. Each provider has several drones with different quality attributes. The BNL approach helps select a set of drones determined to be a good fit for the delivery request. We then obtain a set of reachable stations by the selected drone considering the payload weight and predicted probability distribution of wind (Line 3). The get reachable stations function finds the nearby stations based on the travel distance from the current drone position. If the desired destination lies within reachable stations, the drone delivers the package without recharging (Line 4-7) . In such a case, service composition is not required (a single drone service fulfills the request). We compute the time to travel the skyway segment from source to destination considering wind conditions (Line 5). We compose optimal drone services from source to destination to serve longdistance areas (Lines 9-25). If the destination does not lie within reachable stations, we compute the time to each reachable station (Line 11). We select the optimal drone service based on the travel time (calculated using equation 6), its probability of occurrence, availability of the recharging pads, current waiting time, expected waiting time on the next node, and flight time to the destination (Lines 12-13). On each iteration, we add the selected optimal services to DaaS Comp (Line 15). We update the current location and time of the drone (Lines [16] [17] . This process continues till the destination node is discovered or the reachable stations' list is empty (i.e., no suitable composition found). In this section, we analyze the effectiveness of the Probabilistic Forward Search (PFS) approach. We develop a robust DaaS composition framework for delivery services to evaluate the performance of the PFS approach. We build a skyway network using the NetworkX python library, where each node can be a delivery target or a recharging station. We model multiple drone services from different drone service providers operating in the same network. The drone set consists of quality parameters of We use a real dataset of drone trajectories, including data for altitude, coordinates, and timestamps [23] . We augment a dataset for different types of drones considering the payload, speed, flight range, recharging time, and battery capacity. The experimental variables are described in Table I The PFS approach performs robust composition of the right drone services to deliver the package faster. 1) Average Execution Time: The time complexity is an important parameter to evaluate the performance of an algorithm. The IES approach is very computationally expensive compared to the proposed PFS approach. The execution time increases as the number of possible drone service compositions increase. The average execution times for IES and PFS approaches are presented in Fig. 2 . The execution time for the PFS approach is much less because it avoids The experiments indicate that when the nodes are above 40, the results' trends are similar. As a result, we set the maximum number of nodes at 40 for the skyway network. The use of the baseline approach is not practical in real-world scenarios for largescale problems because of its exhaustive nature. 2) Average Delivery Time: The delivery time of a drone is a summation of recharging, waiting, and flight times. The delivery time is mainly affected by the occupancy of certain recharging stations for long periods of time. Fig. 3 shows the delivery times of IES and PFS approaches. The IES approach always computes all possible drone service compositions, which in turn provides exact solutions. The decision-making of the proposed PFS approach relies on the congestion information from the next-to-adjacent nodes. Therefore, the PFS approach provides delivery solutions close to the IES approach. However, the PFS approach is significantly faster than the IES approach, as shown in Fig. 2 . We propose a novel framework for robust drone service composition considering uncertain wind conditions over the skyway segments in a skyway network. A Block Nested Loop algorithm is used for the selection of the right drone at the source location. The proposed approach incorporates the dynamic arrival of drone services at the recharging stations. We select and compose the optimal services using the Probabilistic Forward Search (PFS) approach to minimize the delivery time. We run a set of experiments to evaluate the efficiency of the proposed approach compared to IES approach. The experimental results prove that the proposed approach is computationally efficient than the IES approach. Moreover, our proposed approach is a practical solution for real-world scenarios of drone delivery services due to its computational efficiency and near-optimal solutions. Unmanned aerial vehicles (uavs): A survey on civil applications and key research challenges A game-theoretic drone-as-a-service composition for delivery A comprehensive review of the covid-19 pandemic and the role of iot, drones, ai, blockchain, and 5g in managing its impact Drones: Designed for product delivery Guest editorial can drones deliver? A service computing manifesto: The next 10 years Composing drone-as-a-service (daas) for delivery drone on: The sky's the limit, if the faa gets out of the way Constraint-aware drone-as-a-service composition Swarm-based drone-as-a-service (sdaas) for delivery Formation-based selection of drone swarm services Drone flight scheduling under uncertainty on battery duration and air temperature A review of urban wind energy research: Aerodynamics and other challenges A novel energy harvester for powering small uavs: Performance analysis, model validation and flight results Rough deep neural architecture for short-term wind speed forecasting Traveling salesman problem with multiple drones Optimization of multi-package drone deliveries considering battery capacity Wind corrections in flight path planning Resilient composition of drone services for delivery Dynamic routing of unmanned aerial vehicles using reactive tabu search A game of drones: Cyber-physical security of time-critical uav applications with cumulative prospect theory perceptions and valuations Skyline travel routes: Exploring skyline for trip planning Flight logs of drone swarms We plan to consider handover among drones at recharging stations in the future.ACKNOWLEDGMENT This research was partly made possible by DP160103595 and LE180100158 grants from the Australian Research Council. The statements made herein are solely the responsibility of the authors.