We study the problem of assigning robots with actions to track targets. The objective is to optimize the robot team's tracking quality which can be defined as the reduction in the uncertainty of the targets' states. Specifically, we consider two assignment problems given the different sensing capabilities of the robots. In the first assignment problem, a single robot is sufficient to track a target. To this end, we present a greedy algorithm (Algorithm 1) that assigns a robot with its action to each target. We prove that the greedy algorithm has a 1/2 approximation bound and runs in polynomial time. Then, we study the second assignment problem where two robots are necessary to track a target. We design another greedy algorithm (Algorithm 2) that assigns a pair of robots with their actions to each target. We prove that the greedy algorithm achieves a 1/3 approximation bound and has a polynomial running time. Moreover, we illustrate the performance of the two greedy algorithms in the ROS-Gazebo environment where the tracking patterns of one robot following one target using Algorithm 1 and two robots following one target using Algorithm 2 are clearly observed. Further, we conduct extensive comparisons to demonstrate that the two greedy algorithms perform close to their optimal counterparts and much better than their respective (1/2 and 1/3) approximation bounds.
翻译:我们研究指派机器人以追踪目标。 目标是优化机器人团队的跟踪质量, 可以被定义为减少目标状态的不确定性。 具体地说, 我们考虑两个任务问题, 因为机器人的感知能力不同。 在第一个任务问题中, 单机器人足以追踪目标。 为此, 我们提出了一个贪婪的算法( Agorithm 1 ), 给每个目标指定一个行动。 我们证明贪婪的算法有一个半近似约束, 并且运行于一个目标。 然后, 我们研究第二个任务问题, 需要两个机器人来跟踪目标。 我们设计另一个贪婪的算法( Algorithm 2 ), 给每个目标指派一对一对机器人的动作。 我们证明贪婪算法达到了1/ 3 的近似链接, 并有一个聚合运行时间。 此外, 我们用 ROS- Gazebo 环境中的两个贪婪的算法算法的性算法的性表现, 在那里, 一个机器人的追踪模式是使用一个目标, 并且用一个目标来跟踪一个目标。 我们设计另一个机器人, 两个机器人在一个目标之后, 用 Algorithm 1 和两个目标进行更接近一个目标的比较。 ( 1\ 2 ) 。</s>