Multirobot Routing Algorithms for Robots Operating in Vineyards

摘要

We consider the problem of multirobot routing in vineyards, a task motivated by our ongoing project aiming at creating a corobotic system to implement precision irrigation on large-scale commercial vineyards. The problem is related to a combinatorial optimization problem on graphs called “team orienteering.” Team orienteering is known to be NP-hard, thus motivating the development of heuristic solutions that can scale to large problem instances. We propose three different parameter-free approaches informed by the domain we consider and compare them against a general purpose heuristic developed previously. In numerous benchmarks derived from data gathered in a commercial vineyard, we demonstrate that our solutions outperform the general purpose heuristic and are scalable, thus allowing us to solve instances with tens of thousands of vertices in the graphs. Note to Practitioners-Routing problems with budget and motion constraints are pervasive to many applications. In particular, the structural constraints considered in this problem are found not only in agricultural environments but also in warehouse logistics and other domains where goods are arranged along regular linear structures. This article proposes and analyzes algorithms that can be applied when multiple agents must be coordinated in these environments. In particular, by utilizing domain-specific knowledge, the solutions proposed in this article outperform general purpose approaches that poorly scale with the size of the environment. The algorithms we present also ensure that no collisions occur between robots-an aspect normally neglected in algorithms previously proposed to solve the team orienteering problem.