TY - JOUR

T1 - Time-energy tradeoffs for evacuation by two robots in the wireless model

AU - Czyzowicz, Jurek

AU - Georgiou, Konstantinos

AU - Killick, Ryan

AU - Kranakis, Evangelos

AU - Krizanc, Danny

AU - Lafond, Manuel

AU - Narayanan, Lata

AU - Opatrny, Jaroslav

AU - Shende, Sunil

N1 - Funding Information:
This research is supported by NSERC discovery grants, NSERC graduate scholarship, and NSF (grant # 1813940 ).
Publisher Copyright:
© 2020 Elsevier B.V.

PY - 2021/1/8

Y1 - 2021/1/8

N2 - 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 xs2. 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 bc≥3. For the case bc=3, we give an optimal algorithm, and give upper bounds on the energy for the case bc>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(d3/2logd), and this is optimal up to a logarithmic factor. When Δ is linear in d, we give upper bounds on the evacuation time.

AB - 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 xs2. 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 bc≥3. For the case bc=3, we give an optimal algorithm, and give upper bounds on the energy for the case bc>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(d3/2logd), and this is optimal up to a logarithmic factor. When Δ is linear in d, we give upper bounds on the evacuation time.

KW - Energy

KW - Evacuation

KW - Linear

KW - Robot

KW - Speed

KW - Time

KW - Trade-offs

KW - Wireless communication

UR - http://www.scopus.com/inward/record.url?scp=85096367862&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85096367862&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2020.11.014

DO - 10.1016/j.tcs.2020.11.014

M3 - Article

AN - SCOPUS:85096367862

SN - 0304-3975

VL - 852

SP - 61

EP - 72

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -