  In this paper, we consider the Constant-cost Orienteering Problem (COP) where
a robot, constrained by a limited travel budget, aims at selecting a path with
the largest reward in an aisle-graph. The aisle-graph consists of a set of
loosely connected rows where the robot can change lane only at either end, but
not in the middle. Even when considering this special type of graphs, the
orienteering problem is known to be NP-hard. We optimally solve in polynomial
time two special cases, COP-FR where the robot can only traverse full rows, and
COP-SC where the robot can access the rows only from one side. To solve the
general COP, we then apply our special case algorithms as well as a new
heuristic that suitably combines them. Despite its light computational
complexity and being confined into a very limited class of paths, the optimal
solutions for COP-FR turn out to be competitive even for COP in both real and
synthetic scenarios. Furthermore, our new heuristic for the general case
outperforms state-of-art algorithms, especially for input with highly
unbalanced rewards.
