Team Orienteering Coverage Planning with Uncertain Reward
Team Orienteering Coverage Planning with Uncertain Reward
复制标题
团队定向覆盖范围规划，奖励不确定
DOI：
10.1109/iros51168.2021.9636288
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
P. Stone
中科院分区：
文献类型：
--
作者：
Bo Liu;Xuesu Xiao;P. Stone
许多城市和大型组织都有车队需要协调，以执行垃圾收集或基础设施检查等任务。在这一需求的推动下，本文重点研究了一个公共子问题，即车辆团队需要规划协调的路线，以便在迭代中巡逻一个区域，同时最小化时间和空间相关的成本。具体地说，在特定位置(例如，图上的顶点)，我们假设成本随时间累积并且其增长率是具有固定但未知平均值的随机变量，并且每当任何车辆访问该顶点时，成本被重置为零(表示机器人为该顶点提供服务)。我们用图的术语来描述这个问题，称之为具有不确定回报的团队定向覆盖计划(TOCPUR)。我们提出通过同时估计图上每个顶点的累积成本和迭代地求解团队定向问题的一个新变体来解决TOCPUR，我们称之为团队定向覆盖问题(TOCP)。我们提供了TOCP的第一个混合整数规划公式，作为对原始TOP的重要适应。我们引入了一个由数百个随机生成的图组成的新基准来比较不同的方法。我们证明了所提出的解决方案的性能优于精确顶点解和贪婪算法。此外，我们还在真实环境中的一个由三个物理机器人组成的团队上演示了我们的方法。该代码可在https://github.com/Cranial-XIX/TOCPUR.git.上公开获得
Many municipalities and large organizations have fleets of vehicles that need to be coordinated for tasks such as garbage collection or infrastructure inspection. Motivated by this need, this paper focuses on the common subproblem in which a team of vehicles needs to plan coordinated routes to patrol an area over iterations while minimizing temporally and spatially dependent costs. In particular, at a specific location (e.g., a vertex on a graph), we assume the cost accumulates over time and its growth rate is a random variable with a fixed but unknown mean, and the cost is reset to zero whenever any vehicle visits the vertex (representing the robot "servicing" the vertex). We formulate this problem in graph terminology and call it Team Orienteering Coverage Planning with Uncertain Reward (TOCPUR). We propose to solve TOCPUR by simultaneously estimating the accumulated cost at every vertex on the graph and solving a novel variant of the Team Orienteering Problem (TOP) iteratively, which we call the Team Orienteering Coverage Problem (TOCP). We provide the first mixed integer programming formulation for the TOCP, as a significant adaptation of the original TOP. We introduce a new benchmark consisting of hundreds of randomly generated graphs for comparing different methods. We show the proposed solution outperforms both the exact TOP solution and a greedy algorithm. In addition, we provide a demo of our method on a team of three physical robots in a real-world environment. The code is publicly available at https://github.com/Cranial-XIX/TOCPUR.git.