Developing a Resource and Energy Efficient Real-time Delivery Scheduling Framework for a Network of Autonomous Drones
Abstract
The use of unmanned aerial vehicles (UAV) or drones appears to be a viable, low-cost solution to problems in many applications. However, the limited onboard computing resources and battery capacity make it challenging to deploy drones for long-distance missions.
Path planning capabilities are essential for autonomous control systems. An autonomous drone must be able to rapidly compute feasible, energy-efficient paths to avoid collisions. We first evaluate existing sampling-based algorithms' performance and present a hybrid sampling-based algorithm to generate a solution quicker, using less memory. We then introduce the notion of a layered graph, which accurately and efficiently models the search environment. Simulations show that when applying a modified A* algorithm on the layered graph, paths can be generated at least twice as fast, using significantly less memory than the sampling-based algorithm.
Finally, we propose a novel cell-based model that uses a network of drones to perform long-range tasks such as last-mile deliveries. Drone charging stations are strategically placed to ensure that drones can replenish their batteries. The genetic algorithm was implemented to solve the scheduling problem for multiple drones using this model. We show that this model can be used to deliver many packages within a short amount of time.