Routing Algorithms for Robot Assisted Precision Irrigation

Abstract

When robots navigate through vineyards to perform irrigation adjustments, an optimization problem emerges whereby robots are tasked with performing adjustments having the highest cumulative outcome within a given temporal budget due to limited battery charge. To this end, the robot needs to reach a set of spatially distributed sites, and the specific structure of the vineyard imposes various constraints on possible motions. In this paper we first demonstrate that this type of orienteering problem remains NP-hard even for the restricted class of graphs associated with precision irrigation. Then, we devise and analyze two greedy heuristics informed by the problem we consider. Finally, these algorithms are evaluated on settings associated with a commercial vineyard and we show that our methods favorably compare to solutions proposed in the past.