Time-Optimal Multi-Quadrotor Trajectory Planning for Pesticide Spraying

Abstract

In this paper, we investigate the problem of generating time-optimal trajectories automatically for spraying pesticides to infected regions with varying degree of infections in an agricultural field using a collection of quad-rotors that have limited pesticide carrying capacity but are capable of refilling from the pesticide tanks stationed across the field. We consider the time of traversal between points, time for changing the direction of traversal, and time for spraying and refilling, explicitly in the problem formulation, and generate trajectories for the multiple quad-rotors to execute in parallel such that the total energy (time) for completion of the task is minimized. We present two methods namely, multiple traveling salesman based time-optimal trajectory generation, and clustering based de-compositional time-optimal trajectory generation, respectively. In the first method, our approach consists of reducing the time-optimal trajectory generation problem for the multiple quad-rotors to a version of the multiple traveling salesman problem on a weighted graph, and then encoding the problem into a mixed integer linear programming problem. In the second method, our approach consists of first decomposing the infected regions into k clusters corresponding to the k robots, placing each quad-rotor at the center of the corresponding clusters, and finally, independently solving time-optimal trajectory generation problem for each quad-rotor using the first method. We have implemented both the approaches and performed experimental comparison. We observe that the first method provides an optimal strategy, while the second method provides a sub-optimal strategy. However, the second method is computationally more efficient, and the loss of optimality is minimal, hence, it provides a better trade-off between the computational complexity and the optimality constraints.