Redundant Robot Assignment on Graphs with Uncertain Edge Costs
Redundant Robot Assignment on Graphs with Uncertain Edge Costs
复制标题
边缘成本不确定的图上的冗余机器人分配
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Amanda Prorok
中科院分区：
文献类型：
--
作者：
Amanda Prorok
我们提供了一个框架分配多个机器人的目标位置，当机器人的行程时间是不确定的。我们的前提是，时间是系统中最宝贵的资产。因此，我们利用冗余机器人来对抗不确定性的影响，并最大限度地减少在目的地的平均等待时间。我们将我们的框架应用于表示为图的运输网络，并考虑边缘成本的不确定性（即，传播时间）。由于解决冗余分配问题是强NP-难的，我们利用我们的问题的结构特性，提出了一个多项式时间的解决方案，可证明的次优界。我们的方法使用分布式聚合函数，这使我们能够有效地（即，增量地）计算分配冗余机器人的有效成本。随机图上的实验结果表明，通过我们的方法部署冗余机器人减少了等待时间在目标位置，当边缘遍历是不确定的。
We provide a framework for the assignment of multiple robots to goal locations, when robot travel times are uncertain. Our premise is that time is the most valuable asset in the system. Hence, we make use of redundant robots to counter the effect of uncertainty and minimize the average waiting time at destinations. We apply our framework to transport networks represented as graphs, and consider uncertainty in the edge costs (i.e., travel time). Since solving the redundant assignment problem is strongly NP-hard, we exploit structural properties of our problem to propose a polynomial-time solution with provable sub-optimality bounds. Our method uses distributive aggregate functions, which allow us to efficiently (i.e., incrementally) compute the effective cost of assigning redundant robots. Experimental results on random graphs show that the deployment of redundant robots through our method reduces waiting times at goal locations, when edge traversals are uncertain.