Optimal Routing Schedules for Robots Operating in Aisle-Structures
Optimal Routing Schedules for Robots Operating in Aisle-Structures
复制标题
在过道结构中运行的机器人的最佳路线安排
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
M. C. Pinotti
中科院分区：
文献类型：
--
作者：
Francesco Betti Sorbelli;Stefano Carpin;Federico Coró;A. Navarra;M. C. Pinotti
在本文中，我们考虑了固定成本定向问题(COP)，其中机器人在有限旅行预算的约束下，目标是在过道图中选择一条回报最大的路径。过道图由一组松散连接的行组成，机器人只能在两端改变车道，而不能在中间改变车道。即使考虑到这种特殊类型的图形，定向问题也是众所周知的棘手的。我们在多项式时间内最优地解决了两种特殊情况，COP-FR，其中机器人只能遍历整行，以及COP-SC，其中机器人只能从一侧访问行。为了解决一般的COP问题，我们应用了我们的特例算法以及一种新的启发式算法，将它们适当地结合在一起。尽管COP-FR的计算复杂性很低，并且限于非常有限的路径类别，但事实证明，即使对于COP，COP-FR的最优解决方案在获得的回报方面也具有竞争力。这是通过在真实和合成场景中执行的扩展模拟来说明的。此外，我们针对一般情况的新启发式算法优于最先进的算法，特别是对于具有高度不平衡回报的输入。
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 intractable. 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 in terms of achieved rewards even for COP. This is shown by means of extended simulations performed on 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.