UC Merced

Contemporary vineyard management is in dire need of a way to make remote sensing data useful for irrigation purposes on the fine-grain scale. A robot can be used to adjust irrigation emitters within a vineyard, but first requires solving a difficult optimization problem, where a path must be planned that maximizes the cumulative adjustment of water emitters while the path's total length is limited by the battery life of the robot. This is formally called the Orienteering Problem, which is NP-hard. The physical structure of a vineyard constrains movement within it, and the colossal size of some vineyards means that special algorithms are needed to compute efficient solutions. Furthermore, useful extensions to this problem provide additional benefit for real-world vineyards. Solutions to the Team Orienteering Problem, which requires coordinated paths built for multiple agents, can make irrigation management more efficient using a team of robots. The Bi-Objective Orienteering Problem provides robot paths that can perform an additional task while adjusting water emitters, such as soil sampling for moisture content. These problems all assume deterministic movement costs, whereas robots traversing agricultural settings can encounter less desirable field conditions which reduce their speed. The Stochastic Orienteering Problem with Chance Constraints can be used to account for this uncertainty in path planning and provide a bound on the chance of failure. This problem is difficult to solve in large instances such as those encountered with agricultural routing, and therefore ways to speed up computation are needed. This dissertation addresses each of these variations of the Orienteering Problem within the context of vineyards. A special type of model is discussed called an Aisle Graph which represents the structure of a typical vineyard. For the mentioned variations of the Orienteering Problem, heuristic path planners are created which take advantage of this unique arrangement to provide highly economical paths for robots very quickly. Each of the heuristic planners is analyzed on real-world problem simulations constructed with datasets from commercial vineyards located in central California, and shown to be efficient at directing robots to adjust irrigation emitters in fields containing tens of thousands of vines.