Time-energy tradeoffs for evacuation by two robots in the wireless model
Time-energy tradeoffs for evacuation by two robots in the wireless model
复制标题
无线模型中两个机器人疏散的时间与能量权衡
DOI：
10.1016/j.tcs.2020.11.014
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Shende, Sunil
中科院分区：
文献类型：
--
作者：
Czyzowicz, Jurek;Georgiou, Konstantinos;Killick, Ryan;Kranakis, Evangelos;Krizanc, Danny;Lafond, Manuel;Narayanan, Lata;Opatrny, Jaroslav;Shende, Sunil
两个机器人站在无限线的起点，任务是合作寻找线上未知位置的出口。它们可以以最大速度B行驶，并且可以随时改变速度或方向。这两个机器人可以在任何距离和任何时间相互通信。当最后一个机器人到达出口并撤离时，任务完成。我们研究了上述疏散问题的时间-能量权衡。疏散时间是最后一个机器人到达出口所需的时间。机器人以速度s移动距离x所需的能量被测量为xs 2。总疏散能量和最大疏散时间分别是两个机器人执行疏散算法时所消耗能量的总和和最大值。假设最大速度为B，疏散时间至多为cd，其中d为出口到原点的距离，c为某个正的真实的数，研究了机器人总能耗最小化问题。我们证明了该问题只有当B c≥ 3时才可解。对于B c= 3的情形，我们给出了一个最优算法，并对B c> 3的情形给出了能量上界。我们还考虑了当可用能量以Δ为界时最小化疏散时间的问题。令人惊讶的是，当Δ是一个常数，独立的距离d的出口从原点，我们证明了疏散是可能的时间O（d 3/2 log d），这是最佳的对数因子。当Δ与d成线性关系时，给出了疏散时间的上界.
Two robots stand at the origin of the infinite line and are tasked with searching collaboratively for an exit at an unknown location on the line. They can travel at maximum speed b and can change speed or direction at any time. The two robots can communicate with each other at any distance and at any time. The task is completed when the last robot arrives at the exit and evacuates. We study time-energy tradeoffs for the above evacuation problem. The evacuation time is the time it takes the last robot to reach the exit. The energy it takes for a robot to travel a distance x at speed s is measured as x s 2. The total and makespan evacuation energies are respectively the sum and maximum of the energy consumption of the two robots while executing the evacuation algorithm. Assuming that the maximum speed is b, and the evacuation time is at most cd, where d is the distance of the exit from the origin and c is some positive real number, we study the problem of minimizing the total energy consumption of the robots. We prove that the problem is solvable only for b c≥ 3. For the case b c= 3, we give an optimal algorithm, and give upper bounds on the energy for the case b c> 3. We also consider the problem of minimizing the evacuation time when the available energy is bounded by Δ. Surprisingly, when Δ is a constant, independent of the distance d of the exit from the origin, we prove that evacuation is possible in time O (d 3/2 log d), and this is optimal up to a logarithmic factor. When Δ is linear in d, we give upper bounds on the evacuation time.