We study a stochastic version of the classic orienteering problem where the time to traverse an edge is a continuous random variable. For a given temporal deadline B, our solution produces a policy, i.e., a function that, based on the current position along a solution path and the elapsed time, decides whether to continue along the path or take a shortcut to avoid missing the deadline. The solution is based on a formulation using constrained Markov decision processes to ensure that the deadline is met with a preassigned confidence level. To expedite the computation, a Monte Carlo simulation on an open loop policy is run to determine how to adaptively discretize the temporal dimension and therefore reduce the number of states and the number of optimization variables in the associated linear program. Our results show that the adaptive algorithm matches the performance of the non-adaptive one while taking significantly less time.

We consider the Stochastic Orienteering Problem with random traversal time for edges. In this scenario the length of the path is a random variable and we consider a formulation with chance constraints, i.e., a bound on the probability that the length of the path exceeds the allotted budget. Our proposed solution casts the problem as an instance of a suitably defined Constrained Markov Decision Process and uses a Lagrangian formulation to solve it. In particular, exploiting some structural properties of the associated decision process we can solve the Markov Decision Process using a Lagrangian approach and efficiently determine the optimal Lagrange multiplier. Our method is experimentally evaluated and demonstrated to be significantly faster than previous solutions using a linear programming approach to solve the Stochastic Orienteering Problem with chance constraints.

In this paper we consider the stochastic cost orienteering problem, i.e., a version of the classic orienteering problem where the cost associated with each edge is a random variable with known distribution. Such a model is relevant when travel costs are variable, e.g., when a robot moves in uncertain terrain conditions. We model this problem using a composite state space tracking both how much progress the robot has made towards the goal and how much time it has left. On top of this state space, we compute a time-aware policy that allows the robot to dynamically adjust its path and avoid missing the temporal deadline. This policy is determined using a Constrained Markov Decision Process that allows tuning the accepted failure probability upfront. This approach suffers from a significant growth in the composite state space, and to mitigate this problem we introduce an aggregation technique where nearby vertices are compounded together, effectively reducing the original routing problem to an instance with a smaller state space. We then analyze this approach over large scale problem instances associated with robotic irrigation on a commercial grade vineyard.

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.

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.