# Speeding up Routing Schedules on Aisle-Graphs with Single Access

arXiv: https://arxiv.org/abs/2102.05733 · HTML: https://mlsanity.com/paper/2102.05733/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2021.

## Built on by (most cited first, 4 of 4)

- [Solving Stochastic Orienteering Problems with Chance Constraints Using a GNN Powered Monte Carlo Tree Search](https://mlsanity.com/paper/2409.04653/) (2024)
- [Scalable Hierarchical Reinforcement Learning for Hyper Scale Multi-Robot Task Planning](https://mlsanity.com/paper/2412.19538/) (2024)
- [Pro-Routing: Proactive Routing of Autonomous Multi-Capacity Robots for Pickup-and-Delivery Tasks](https://mlsanity.com/paper/2503.24325/) (2025)
- [Model-Based Reinforcement Learning for Heterogeneous Multi-Robot Task Assignment Under Distribution Shifts](https://mlsanity.com/paper/2608.21554/) (2026)

## Abstract (arXiv)

In this paper, we study the Orienteering Aisle-graphs Single-access Problem (OASP), a variant of the orienteering problem for a robot moving in a so-called single-access aisle-graph, i.e., a graph consisting of a set of rows that can be accessed from one side only. Aisle-graphs model, among others, vineyards or warehouses. Each aisle-graph vertex is associated with a reward that a robot obtains when visits the vertex itself. As the robot's energy is limited, only a subset of vertices can be visited with a fully charged battery. The objective is to maximize the total reward collected by the robot with a battery charge. We first propose an optimal algorithm that solves OASP in O(m^2 n^2) time for aisle-graphs with a single access consisting of m rows, each with n vertices. With the goal of designing faster solutions, we propose four greedy sub-optimal algorithms that run in at most O(mn (m+n)) time. For two of them, we guarantee an approximation ratio of 1/2(1-1/e), where e is the base of the natural logarithm, on the total reward by exploiting the well-known submodularity property. Experimentally, we show that these algorithms collect more than 80% of the optimal reward.