Optimal and approximated path planning for a robot moving on aisle-graphs

In this paper, we study the Constant-cost Orienteering Problem on Aisle-Graphs (COPAG) on aisle-graphs, where a robot with limited travel budget seeks a profit-maximizing tour. An aisle-graph consists of m paths (rows) of n vertices, with inter-row movement possible only at the endpoints. This setting models real-world layouts such as orchards, vineyards, and warehouses, where structural constraints prevent traversal between rows in the middle. While the Orienteering Problem (OP) is NP-hard in general graphs, we show that COPAG on aisle-graphs is solvable in polynomial time, contrary to claims in previous literature. We first introduce COPAG-FR, a restricted case allowing only full-row traversal, and solve it optimally. Then, for the general version with partial-row traversal, we present a dynamic programming algorithm running in O(m^10n^4). Since this complexity may be impractical for large inputs, we also design a 1/3-approximation algorithm and a heuristic refinement, achieving effective performance on the tested synthetic instances.