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 𝑚 paths (rows) of 𝑛 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 𝒪 ⁡ ( 𝑚 1 0 ⁢ 𝑛 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.