key: cord-0541570-naui1w50 authors: Patchou, Manuel; Sliwa, Benjamin; Wietfeld, Christian title: Flying Robots for Safe and Efficient Parcel Delivery Within the COVID-19 Pandemic date: 2021-01-19 journal: nan DOI: nan sha: 2c5025465f9d82c5891d1ff62cdbb56d1eddf012 doc_id: 541570 cord_uid: naui1w50 The integration of small-scale Unmanned Aerial Vehicles (UAVs) into Intelligent Transportation Systems (ITSs) will empower novel smart-city applications and services. After the unforeseen outbreak of the COVID-19 pandemic, the public demand for delivery services has multiplied. Mobile robotic systems inherently offer the potential for minimizing the amount of direct human-to-human interactions with the parcel delivery process. The proposed system-of-systems consists of various complex aspects such as assigning and distributing delivery jobs, establishing and maintaining reliable communication links between the vehicles, as well as path planning and mobility control. In this paper, we apply a system-level perspective for identifying key challenges and promising solution approaches for modeling, analysis, and optimization of UAV-aided parcel delivery. We present a system-of-systems model for UAV-assisted parcel delivery to cope with higher capacity requirements induced by the COVID-19. To demonstrate the benefits of hybrid vehicular delivery, we present a case study focusing on the prioritization of time-critical deliveries such as medical goods. The results further confirm that the capacity of traditional delivery fleets can be upgraded with drone usage. Furthermore, we observe that the delay incurred by prioritizing time-critical deliveries can be compensated with drone deployment. Finally, centralized and decentralized communication approaches for data transmission inside hybrid delivery fleets are compared. The integration of small-scale UAVs into future ITS [1] has been an emerging topic in recent years. Due to the unique mobility potential of these airborne vehicles, significant efficiency improvements in applications such as aerial traffic monitoring [2] and parcel delivery [3] have been anticipated. Despite promising initial case studies, the existing approaches have been dominated by academic analyses. However, the public interest in implementing mobile robotics-based delivery systems has been massively increased after the outbreak of the COVID-19 pandemic [4] . In this paper, we present a system-of-systems approach for implementing the various aspects of hybrid vehicular delivery systems, which consist of collaborating vehicles on the ground and in the air. Our work is motivated by the following core observation in the context of COVID-19, which are also illustrated in Fig.1 : • Human-to-human interactions should be minimized in order to avoid the further spread of the virus. Mobile robotic vehicles can serve as non-infective delivery agents. • Capacity enhancement of delivery services is required to cope with the increasing demand for delivered goods. • Time-critical goods such as medical equipment need to be prioritized over standard consumer goods. Aerial vehicles are not affected by traffic jams and can be utilized for rapid shipment even in highly crowded innercity scenarios. • Reliable communications are required for the safe operation and monitoring of the hybrid delivery fleet and networking of the delivery truck and the UAV while proposing command and control features. Due to the resulting complexity, the systems thinking is applied to propose a solution. The contributions are summarized as follows: • A system-of-systems concept for an optimized UAVenabled last-mile delivery platform. • A proof-of-concept study in a real-world scenario to analyze capacity gains and suitable network approaches. • The prioritization of time-critical deliveries such as medical goods and its effects on the delivery performance. The remainder of the paper is structured as follows. After discussing the related work in Sec. II, the proposed system model is presented in Sec. III. Afterwards, an overview of the methodological aspects is given in Sec. IV. Finally, detailed results about conducted case studies are provided in Sec. V. II. RELATED WORK UAV-assisted delivery systems: Last-mile delivery is often completed by trucks driving over relatively short distances in an urban setting. The number and the variety of shipments, the complexity, and frequent congestion of the urban environment pose a challenge in terms of reliability and efficiency. The inclusion of UAVs in the last mile delivery fleet is now under active consideration and testing. A novel approach in this direction lets the delivery truck carry the drones when leaving the depot center. These are then dispatched along the route to autonomously deliver parcels up to a certain distance from the truck. This approach requires finding an optimal route for the delivery truck, taking into account the mobility range of its associated delivery drones, which is limited by their battery capacity thereby leading to a new class of hybrid Travelling Salesman Problem (TSP). This optimization problem was labeled the Flying Sidekick Travelling Salesman Problem (FSTSP) in one of its earliest formulations as a Mixed Integer Programming (MIP) problem and presented with a heuristic solution approach in [5] . The initial TSP tour is iteratively updated by checking whether the next node shall be served by a drone and assigning it accordingly. The work in [6] derived several worst-case results on the hybrid routing problem with drones, such as the maximal savings, which can be obtained by their usage. A dynamic pickup and delivery approach, allowing aerial vehicles to pick up packets from a moving truck and autonomously complete deliveries, was investigated in [7] . Comparing this approach to the more traditional one, where the drones deliveries may only be started when the truck stops to complete a delivery, shows further performance improvements. Drone aided parcel delivery must be, like all autonomous vehicles applications, guaranteed sufficient networking resources for monitoring, safety, and operational purposes. As such, providing cellular connectivity to low altitude UAVs has gathered increasing interest from the industry [8] 3rd Generation Partnership Project (3GPP). The variation in resource availability is also of importance, for example, forecasting the data rate along vehicular trajectories. Use cases and standard mechanisms proposals for predictive Quality of Service (QoS) are presented in [9] . An overview of distinct communication QoS requirements for UAV applications, differentiated, among other criteria, by the nature of transmitted data is given in [10] . An additional UAV enabled application is presented in [11] , where a ground vehicular network is enhanced with multiple UAVs forming an aerial sub-network through Air-to-Air (A2A) and Air-to-Ground (A2G) links. Simulation of UAV networks: Simulation is still the leading approach for validating and evaluating vehicular network solutions, as shown in [12] . Different simulation frameworks for UAV networks have already been proposed. CommUnicationS-Control distribUted Simulator (CUSCUS) [13] provides interconnection of ns-3 and Framework libre AIR (FL-AIR) based on Linux containers with some limitations regarding simulated network connectivity, as Long Term Evolution (LTE), is currently not supported. FlyNetSim [14] is a Hardware-in-the-Loop (HIL) focused platform, which follows a middleware-based approach to couple ns-3 with Ardupilot. LIghtweight ICT-centric Mobility Simulation (LIMoSim) [15] applies a shared codebase approach, thus avoiding Inter-Process Communications (IPC) overhead, to couple ns-3 with the LIMoSim mobility kernel supporting hybrid combinations of ground and aerial vehicles. A dedicated extension was provided in [3] to bring native simulation support of UAV-aided parcel delivery mobility and communications. Machine learning: Data-Driven Network Simulation (DDNS) [16] is a novel concept for analyzing the end-toend performance of anticipatory mobile networking systems while leveraging an accurate and fast network simulation, based on the observation of concrete environments in combination with machine learning models. The generated network behavior's accuracy is comparable to what system-level simulations provide without the usual overhead associated to protocol simulation. [17] proposes a lightweight alternative to computationally expensive ray tracing evaluations often based on extensive knowledge of scenario topology. The model aided deep learning extracts radio propagation characteristics from aerial images of the receiver environment. A comprehensive summary of machine learning methods and their different communication networks related applications is provided in [18] . In this section, we present a hybrid vehicular delivery service concept to cope with increasing demand, which can be induced by special situations such as the COVID-19 pandemic, and we identify requirements and promising solution approaches. The overall system-of-systems architecture model of the proposed hybrid vehicular delivery service is shown in Fig. 2 . It consists of three closely related building blocks which are explained in further details in the following paragraphs. The core delivery system provides the interfaces of service which can be used to provision and interact with consumer facing applications or internal service provider tools. It is further divided into two specialized subsystems for delivery and fleet management. Delivery management subsystem: One major requirement of the service is a channel through which delivery jobs can be created. The service must offer interfaces allowing external provisioning of deliveries with additional metadata specification to allow categorization. These interfaces must support common communication protocols and standards for flexible integration. The aforementioned job categorization is used to classify delivery requests into time-critical (e.g., for medical applications) and best-effort deliveries. This classification is used by the job scheduling algorithm to increase service performance and meet the deadlines of time-critical deliveries by respecting a set of prioritization rules for the final job assignment process. Fleet management subsystem: Operating such a decentralized system requires monitoring in order to assess the system's performance, detect optimization potential or bottlenecks, and provide tracking features. One very common feature directed to consumers in last-mile delivery is parcel tracking, allowing them to follow the journey of their parcel. Tracking of delivery agents is important to the service provider and is provided as well. In addition to the monitoring feature, remote command and control is needed to constantly watch over the delivery fleet and promptly react to unforeseen events. Control can be exerted in a soft way, using path planning to reroute delivery agents, by defining waypoints to which they autonomously navigate. A strict control mode is provided as well to allow taking full remote control of the delivery drones in urgent and delicate circumstances. While path planning may only consist of sending waypoints amounting to a few bytes to the delivery UAVs, full vehicle teleoperation requires guaranteeable network performance for the end-to-end latency, data rate, and Packet Delivery Ratio (PDR). As a consequence, the usage of drones as delivery agents has specific requirements which are discussed next. The availability of a reliable and efficient means of communication between the different agents and the command and control service is one of the prerequisites for implementing UAV enabled delivery services and autonomous vehicular applications in general. Taken from [10] , general network requirements for typical UAV applications are shown in the table Tab. I, while more network requirements for more specific UAV use cases can be seen from Tab. II. For establishing and maintaining communication links with the delivery fleet, we propose the exploitation of two network optimization principles, which are further introduced in the following paragraphs. Anticipatory mobile networking: Opportunistic data transfer for delay-tolerant data allows saving network resources by transmitting large data chunks in a context-aware manner, preferably during connectivity hotspots [19] . This improves power consumption, which is critical for battery-constrained devices. The context-aware transmission predicts the network quality based on the variation of network indicators and the vehicle's position over time. An advanced version uses machine learning models to produce more accurate predictions. Inversely, local routing decisions [20] can be made using these predictions, thereby preferring the routes with better network conditions. Using these models on the delivery agents requires rapid prototyping of the targeted systems and a suitable methodology to migrate high-level machine learning models to resource-constrained Internet of Things (IoT) platforms. LIghtweight Machine learning for IoT System (LIMITS) [21] allows automating high-level machine learning tasks and automatically deriving C/C++ implementations of trained prediction models that can be executed on real-world platforms as well as in system-level network simulations such as Network Simulator 3 (ns-3). Multi-Radio Access Technology (RAT) allows utilizing redundant communication interfaces for network communications, thus freeing systems from a critical dependency on the network infrastructure of a sole provider. This approach can be implemented within a defined communication technology standard, for example, by bundling the networks of multiple Mobility Network Operators (MNOs) together to offer reliable network access, while even including complimentary base station deployments [22] . Technology switching, e.g. through joint usage of ad-hoc networks and cellular, harnessing the advantages of both centralized and decentralized network approaches, is also possible. SKATES [23] is a multi-link capable communication module that fully aggregates the available RATs and offers such switching capabilities by using a Multi-Path Transmission Control Protocol (MPTCP) Linux kernel to seamlessly distribute traffic over all available network interfaces without connection interruption. Connectivity is given so long as one interface still has network access. Such a device is a suitable candidate to equip delivery drones, and more generally, autonomously operating or remote-controlled agents. Strong interdependency between environment, mobility, and communication calls for joint consideration of these aspects and their influence on one another. Environment: Knowledge about the static and mobile obstacles is of crucial importance for the collision avoidance and mobility control of autonomous UAVs. These obstacles can also act as attenuators which impact the radio propagation effects. Importing map data from OpenStreetMap (OSM) in a simulator offers real environment models with urban obstacles. A further obstacle, often not considered in most network simulations, is the ground. We can account for terrain profile in the simulation by extracting it from the OSM database as well. This accurate representation of real-world scenarios can be used to create Radio Environmental Maps (REMs) for a preparatory analysis for strategic service deployment. Mobility: The physical and logistical characteristics of the agents are a prominent factor in delivery performance and define their suitable usage in the fleet. The traditional truck has a high parcel capacity and is used to deliver multiple parcels in one tour. Its performance is, however, constrained by the road network rules and eventual traffic congestion. A UAV is, on the contrary, free of such constraints as it can maneuver in three dimensions. Its capacity is, however, limited as it can only carry one parcel. The reach is limited as well, due to its battery capacity. Combining these two vehicle types in a hybrid delivery fleet brings performance benefits when applying a joint path planning of aerial-and ground-based vehicles [3] . An optimal path can be found by solving the resulting hybrid TSP with drones. A cross-layer approach that leverages knowledge from the mobility control routines for proactive optimization of the communication performance is envisaged. On the one hand, mobility-aware communication methods allow considering the estimations about the future mobility of the vehicles to proactively schedule data transmissions. On the other hand, communication-aware mobility approaches actively perform navigation while privileging routes with better network conditions estimates. Reinforcement learning can be used to train an agent to this effect and create a complex navigation behavior that can combine or alternate priorities between taking the shortest path to the target and experiencing optimized network conditions along the way. In this section, we present the methodological aspects of the simulation-based performance analysis. In order to jointly analyze the mobility behavior of the different vehicles and the corresponding communication between the logical entities, we utilize the LIMoSim [15] mobility simulator in combination with ns-3. We use the LIMoSim extension presented in [3] to simulate last-mile parcel delivery. The en-route scheme was applied to allow drone dispatching and recovery along the truck's route without stopping due to its confirmed time gains. This framework transforms the delivery problem in a TSP, which is then solved using an adequate algorithm. The simulations are run while using different communication technologies. Two global approaches are compared for indicated usage in droneaided parcel delivery communications. Deliveries may be prioritized differently, based on various criteria and factors. Even more so, during pandemics where medical supply is of great importance. We consider this fact by applying a simple scheme for prioritizing important deliveries, further labeled as medical over normal deliveries. The delivery list is divided between medical deliveries and normal ones. the medical delivery set is considered as a standalone problem and solved first. The last delivery of the medical delivery set is then used as the starting point for finding the optimal delivery path for the normal delivery set as shown in Fig 3. To observe the performance of the delivery process, we consider the waiting time for each delivery. The communication technologies are evaluated using performance metrics such as latency for responsiveness and PDR for reliability. The evaluations are performed within a suburban environment around a university campus. A map of the considered simulation scenario within LIMoSim is shown in Fig. 4 . Tab. III summarizes the key simulation parameters. In this section, we present initial results for the proof-ofconcept evaluation of different aspects of the overall delivery system. First, the characteristics of the delivery sets which were generated for the evaluations are analyzed in Fig.5 . The delivery distribution nearly overlapping with the buildings' shows the deliveries were equally distributed over the available possible recipients in the scenario. The delivery performance with different fleet compositions ranging from only a truck to a hybrid fleet composed of a truck aided by up to 6 drones is shown in Fig. 6 . The simple prioritization of medical deliveries shortens their waiting time by at least 50%. This, however, delays normal deliveries. In our case study, the noticed waiting time increase for normal deliveries is up to 30%. Furthermore, it shortens when an increasing number of drones is deployed to assist the truck and is almost compensated when six drones are used. This variation in waiting times suggests an increase in delivery capacity, which we illustrated in Fig. 6 by analyzing the waiting time distribution with increased drone usage in the fleet. In our example, 80% of the deliveries can be completed in under 20 minutes when the truck is assisted by 4 delivery drones. Next, we compare centralized and decentralized approaches in their suitability for connecting the delivery fleet and in their satisfaction of the requirements presented in Sec. III-B, for UAV applications and especially drone aided parcel delivery. These are a maximal delay of 50 ms and nearly 99% PDR. LTE is used as benchmark technology to represent centralized and coordinated medium access approaches. Cellular Vehicleto-Everything (C-V2X) and Wireless Access for Vehicular Environment (WAVE)-based IEEE 802.11p are used as representatives of decentralized medium access approaches. The simulated traffic is a 100 ms periodic transmission of 190 Bytes Cooperation Awareness Messages (CAMs) to the delivery truck. The results for latency and PDR of the investigated communication technologies are shown in Fig. 7 . It can be seen that each technology can provide robust communication links. Still, a higher latency can be observed in the centralized approach represented by LTE, which handles resource allocations centrally. The decentralized approaches, which implement direct medium access strategies, yield a smaller latency. The decentralized approaches also show more promising reliability with a PDR very close to 1. The direct transmission path between sender and receiver gives a higher probability for Line of Sight (LOS) situations than when using LTE, where the base station -the evolved NodeB (eNB) -must be involved in the communication process. Newer LTE releases may however perform better in this regard. It can be further observed that C-V2X offers slightly better reliability than WAVE. This can be explained by the Semi-Persistent Scheduling (SPS)-based medium access which takes previous resource reservations into account to avoid resource conflicts in future reservation periods. In this paper, we elaborate on the potential of UAVs to help meet the surging demand brought about by the sanitary measures taken to mitigate the COVID-19 pandemic. We presented a system concept to enhance existing last-mile delivery services with drone usage using advances in various research areas. Within different case studies, we presented our groundwork results of various system aspects, namely the delivery capacity gains deriving from the enhanced mobility that hybrid delivery fleets of aerial and ground vehicles offer and the network communications requirements to operate such a fleet. A simple scheduling strategy is used to prioritize time-critical deliveries such as medical goods, and its effects on overall delivery performance are observed. Furthermore, a comparison between centralized and decentralized approaches for communications between hybrid delivery fleet members is carried out. Similar to other services and applications (such as video conferencing), the unforeseen outbreak of the pandemic creates unexpected demands that will catalyze the development of solutions beyond the COVID-19 pandemic's scope. In future work, we will focus on the development of scheduling algorithms to better balance short waiting times for time-critical deliveries with minimal additional delay to the normal ones while using a small number of drones. The development of communication-aware-mobility strategies is also considered. UAV-enabled intelligent transportation systems for the smart city: Applications and challenges System-of-systems modeling, analysis and optimization of hybrid vehicular traffic Unmanned aerial vehicles in logistics: Efficiency gains and communication performance of hybrid combinations of ground and aerial vehicles A comprehensive review of the COVID-19 pandemic and the role of IoT, drones, AI, blockchain, and 5G in managing its impact The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery The vehicle routing problem with drones: Several worst-case results En route truck-drone parcel delivery for optimal vehicle routing strategies 3GPP TR 36.777 -Study on Enhanced LTE Support for Aerial Vehicles White paper: Making 5G proactive and predictive for the automotive industry Accessing from the sky: A tutorial on UAV communications for 5G and beyond Multi-UAV-aided networks: Aerial-ground cooperative vehicular networking architecture VANETs' research over the past decade: Overview, credibility, and trends The CUSCUS simulator for distributed networked control systems FlyNetSim: An open source synchronized UAV network simulator based on ns-3 and ardupilot Lightweight simulation of hybrid aerial-and ground-based vehicular communication networks Data-driven network simulation for performance analysis of anticipatory vehicular communication systems Deep learningbased signal strength prediction using geographical images and expert knowledge Thirty years of machine learning: The road to pareto-optimal wireless networks Boosting vehicle-to-cloud communication by machine learning-enabled context prediction PARRoT: Predictive ad-hoc routing fueled by reinforcement learning and trajectory knowledge LIMITS: Lightweight machine learning for IoT systems with resource limitations Reliable long-range multi-link communication for unmanned search and rescue aircraft systems in beyond visual line of sight operation SKATES: Interoperable multi-connectivity communication module for reliable search and rescue robot operation ACKNOWLEDGMENT Part of the work on this paper has been supported by the German Federal Ministry of Education and Research (BMBF) in the project A-DRZ (13N14857) as well as by the Deutsche Forschungsgemeinschaft (DFG) within the Collaborative Research Center SFB 876 "Providing Information by Resource-Constrained Analysis", projects A4 and B4.