Mission Planning for Sensor Network Deployment using a Fleet of Drones

Abstract

Various methods for route planning of on-road vehicles to serve transportation requests have been developed in the literature in order to reduce transportation and operational costs. The applicability and thus development of these methods is primarily motivated by the field of application. This article deals with the mission planning for a fleet of drones to deploy sensors in a network. In particular, they are conceived to complete the task of delivering geophones in the seismic surveys. Unlike conventional on-road vehicles used for delivery purposes, every drone in the fleet is constrained to make a frequent return trip back to the depot to pick-up a new payload and restore its battery. A centralized planner is proposed in this article due to this constraint. The problem of planning is decomposed into two phases: route formation and route scheduling. The first phase is handled using the extensive formulation of Multi-Trip Vehicle Routing Problem (MTVRP) aiming at minimizing the overall journey time. A heuristic method is also proposed for this phase which provides near-optimal solutions in a computationally efficient manner. The second phase of the planning algorithm deals with the unaddressed problem of depot congestion arising due to the frequent visits of each drone to the depot. This problem is expressed in the form of a Mixed-Integer Linear Program (MILP) that can be solved using available software. This phase is computationally intensive and comparatively slow which restricts the usage of this mission planner in the re-planning phase to the cases involving longer journeys with limited number of routes. The results from a flight-test are also presented in order to demonstrate the mission planner.