Multi-Robot Routing Algorithms for Robots Operating in Vineyards

摘要

In this paper we consider the problem of multi-robot routing in vineyards, a task motivated by our ongoing project aiming at creating a co-robotic system to implement precision irrigation on large scale commercial vineyards. The problem is related to a combinatorial optimization problem on graphs known as the “team orienteering problem”. 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 approaches informed by the domain we consider, and compare them against a general purpose heuristic formerly developed and widely used. In various 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 hundred of thousands of vertices in the graphs.