Optimal Routing Schedules for Robots Operating in Aisle-Structures
This addresses efficient routing for robots in constrained environments like warehouses, but it is incremental as it builds on known NP-hard problems with specific graph structures.
The paper tackles the Constant-cost Orienteering Problem (COP) for robots in aisle-graphs, optimally solving two special cases in polynomial time and introducing a heuristic for the general case that outperforms state-of-the-art algorithms, especially with unbalanced rewards.
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.