Energy consumption of group search on a line

Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny, Sunil Shende

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Consider two robots that start at the origin of the infinite line in search of an exit at an unknown location on the line. The robots can collaborate in the search, but can only communicate if they arrive at the same location at exactly the same time, i.e. they use the so-called face-to-face communication model. The group search time is defined as the worst-case time as a function of d, the distance of the exit from the origin, when both robots can reach the exit. It has long been known that for a single robot traveling at unit speed, the search time is at least 9d − o(d); a simple doubling strategy achieves this time bound. It was shown recently in [15] that k ≥ 2 robots traveling at unit speed also require at least 9d group search time. We investigate energy-time trade-offs in group search by two robots, where the energy loss experienced by a robot traveling a distance x at constant speed s is given by s2x, as motivated by energy consumption models in physics and engineering. Specifically, we consider the problem of minimizing the total energy used by the robots, under the constraints that the search time is at most a multiple c of the distance d and the speed of the robots is bounded by b. Motivation for this study is that for the case when robots must complete the search in 9d time with maximum speed one (b = 1; c = 9), a single robot requires at least 9d energy, while for two robots, all previously proposed algorithms consume at least 28d/3 energy. When the robots have bounded memory and can use only a constant number of fixed speeds, we generalize an algorithm described in [3, 15] to obtain a family of algorithms parametrized by pairs of b, c values that can solve the problem for the entire spectrum of these pairs for which the problem is solvable. In particular, for each such pair, we determine optimal (and in some cases nearly optimal) algorithms inducing the lowest possible energy consumption. We also propose a novel search algorithm that simultaneously achieves search time 9d and consumes energy 8.42588d. Our result shows that two robots can search on the line in optimal time 9d while consuming less total energy than a single robot within the same search time. Our algorithm uses robots that have unbounded memory, and a finite number of dynamically computed speeds. It can be generalized for any c, b with cb = 9, and consumes energy 8.42588b2d.

Original languageEnglish (US)
Title of host publication46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
EditorsChristel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771092
DOIs
StatePublished - Jul 1 2019
Event46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 - Patras, Greece
Duration: Jul 9 2019Jul 12 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume132
ISSN (Print)1868-8969

Conference

Conference46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
CountryGreece
CityPatras
Period7/9/197/12/19

Fingerprint

Energy utilization
Robots
Data storage equipment
Energy dissipation
Physics

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Evacuation
  • Exit
  • Face-to-face Communication
  • Line
  • Robots
  • Search

Cite this

Czyzowicz, J., Georgiou, K., Killick, R., Kranakis, E., Krizanc, D., Lafond, M., ... Shende, S. (2019). Energy consumption of group search on a line. In C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (Eds.), 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 [137] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 132). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2019.137
Czyzowicz, Jurek ; Georgiou, Konstantinos ; Killick, Ryan ; Kranakis, Evangelos ; Krizanc, Danny ; Lafond, Manuel ; Narayanan, Lata ; Opatrny, Jaroslav ; Shende, Sunil. / Energy consumption of group search on a line. 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. editor / Christel Baier ; Ioannis Chatzigiannakis ; Paola Flocchini ; Stefano Leonardi. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. (Leibniz International Proceedings in Informatics, LIPIcs).
@inproceedings{352aee76b62846818370b621ad641a51,
title = "Energy consumption of group search on a line",
abstract = "Consider two robots that start at the origin of the infinite line in search of an exit at an unknown location on the line. The robots can collaborate in the search, but can only communicate if they arrive at the same location at exactly the same time, i.e. they use the so-called face-to-face communication model. The group search time is defined as the worst-case time as a function of d, the distance of the exit from the origin, when both robots can reach the exit. It has long been known that for a single robot traveling at unit speed, the search time is at least 9d − o(d); a simple doubling strategy achieves this time bound. It was shown recently in [15] that k ≥ 2 robots traveling at unit speed also require at least 9d group search time. We investigate energy-time trade-offs in group search by two robots, where the energy loss experienced by a robot traveling a distance x at constant speed s is given by s2x, as motivated by energy consumption models in physics and engineering. Specifically, we consider the problem of minimizing the total energy used by the robots, under the constraints that the search time is at most a multiple c of the distance d and the speed of the robots is bounded by b. Motivation for this study is that for the case when robots must complete the search in 9d time with maximum speed one (b = 1; c = 9), a single robot requires at least 9d energy, while for two robots, all previously proposed algorithms consume at least 28d/3 energy. When the robots have bounded memory and can use only a constant number of fixed speeds, we generalize an algorithm described in [3, 15] to obtain a family of algorithms parametrized by pairs of b, c values that can solve the problem for the entire spectrum of these pairs for which the problem is solvable. In particular, for each such pair, we determine optimal (and in some cases nearly optimal) algorithms inducing the lowest possible energy consumption. We also propose a novel search algorithm that simultaneously achieves search time 9d and consumes energy 8.42588d. Our result shows that two robots can search on the line in optimal time 9d while consuming less total energy than a single robot within the same search time. Our algorithm uses robots that have unbounded memory, and a finite number of dynamically computed speeds. It can be generalized for any c, b with cb = 9, and consumes energy 8.42588b2d.",
keywords = "Evacuation, Exit, Face-to-face Communication, Line, Robots, Search",
author = "Jurek Czyzowicz and Konstantinos Georgiou and Ryan Killick and Evangelos Kranakis and Danny Krizanc and Manuel Lafond and Lata Narayanan and Jaroslav Opatrny and Sunil Shende",
year = "2019",
month = "7",
day = "1",
doi = "10.4230/LIPIcs.ICALP.2019.137",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi",
booktitle = "46th International Colloquium on Automata, Languages, and Programming, ICALP 2019",
address = "Germany",

}

Czyzowicz, J, Georgiou, K, Killick, R, Kranakis, E, Krizanc, D, Lafond, M, Narayanan, L, Opatrny, J & Shende, S 2019, Energy consumption of group search on a line. in C Baier, I Chatzigiannakis, P Flocchini & S Leonardi (eds), 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019., 137, Leibniz International Proceedings in Informatics, LIPIcs, vol. 132, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, Patras, Greece, 7/9/19. https://doi.org/10.4230/LIPIcs.ICALP.2019.137

Energy consumption of group search on a line. / Czyzowicz, Jurek; Georgiou, Konstantinos; Killick, Ryan; Kranakis, Evangelos; Krizanc, Danny; Lafond, Manuel; Narayanan, Lata; Opatrny, Jaroslav; Shende, Sunil.

46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. ed. / Christel Baier; Ioannis Chatzigiannakis; Paola Flocchini; Stefano Leonardi. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. 137 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 132).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Energy consumption of group search on a line

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

PY - 2019/7/1

Y1 - 2019/7/1

N2 - Consider two robots that start at the origin of the infinite line in search of an exit at an unknown location on the line. The robots can collaborate in the search, but can only communicate if they arrive at the same location at exactly the same time, i.e. they use the so-called face-to-face communication model. The group search time is defined as the worst-case time as a function of d, the distance of the exit from the origin, when both robots can reach the exit. It has long been known that for a single robot traveling at unit speed, the search time is at least 9d − o(d); a simple doubling strategy achieves this time bound. It was shown recently in [15] that k ≥ 2 robots traveling at unit speed also require at least 9d group search time. We investigate energy-time trade-offs in group search by two robots, where the energy loss experienced by a robot traveling a distance x at constant speed s is given by s2x, as motivated by energy consumption models in physics and engineering. Specifically, we consider the problem of minimizing the total energy used by the robots, under the constraints that the search time is at most a multiple c of the distance d and the speed of the robots is bounded by b. Motivation for this study is that for the case when robots must complete the search in 9d time with maximum speed one (b = 1; c = 9), a single robot requires at least 9d energy, while for two robots, all previously proposed algorithms consume at least 28d/3 energy. When the robots have bounded memory and can use only a constant number of fixed speeds, we generalize an algorithm described in [3, 15] to obtain a family of algorithms parametrized by pairs of b, c values that can solve the problem for the entire spectrum of these pairs for which the problem is solvable. In particular, for each such pair, we determine optimal (and in some cases nearly optimal) algorithms inducing the lowest possible energy consumption. We also propose a novel search algorithm that simultaneously achieves search time 9d and consumes energy 8.42588d. Our result shows that two robots can search on the line in optimal time 9d while consuming less total energy than a single robot within the same search time. Our algorithm uses robots that have unbounded memory, and a finite number of dynamically computed speeds. It can be generalized for any c, b with cb = 9, and consumes energy 8.42588b2d.

AB - Consider two robots that start at the origin of the infinite line in search of an exit at an unknown location on the line. The robots can collaborate in the search, but can only communicate if they arrive at the same location at exactly the same time, i.e. they use the so-called face-to-face communication model. The group search time is defined as the worst-case time as a function of d, the distance of the exit from the origin, when both robots can reach the exit. It has long been known that for a single robot traveling at unit speed, the search time is at least 9d − o(d); a simple doubling strategy achieves this time bound. It was shown recently in [15] that k ≥ 2 robots traveling at unit speed also require at least 9d group search time. We investigate energy-time trade-offs in group search by two robots, where the energy loss experienced by a robot traveling a distance x at constant speed s is given by s2x, as motivated by energy consumption models in physics and engineering. Specifically, we consider the problem of minimizing the total energy used by the robots, under the constraints that the search time is at most a multiple c of the distance d and the speed of the robots is bounded by b. Motivation for this study is that for the case when robots must complete the search in 9d time with maximum speed one (b = 1; c = 9), a single robot requires at least 9d energy, while for two robots, all previously proposed algorithms consume at least 28d/3 energy. When the robots have bounded memory and can use only a constant number of fixed speeds, we generalize an algorithm described in [3, 15] to obtain a family of algorithms parametrized by pairs of b, c values that can solve the problem for the entire spectrum of these pairs for which the problem is solvable. In particular, for each such pair, we determine optimal (and in some cases nearly optimal) algorithms inducing the lowest possible energy consumption. We also propose a novel search algorithm that simultaneously achieves search time 9d and consumes energy 8.42588d. Our result shows that two robots can search on the line in optimal time 9d while consuming less total energy than a single robot within the same search time. Our algorithm uses robots that have unbounded memory, and a finite number of dynamically computed speeds. It can be generalized for any c, b with cb = 9, and consumes energy 8.42588b2d.

KW - Evacuation

KW - Exit

KW - Face-to-face Communication

KW - Line

KW - Robots

KW - Search

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

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

U2 - 10.4230/LIPIcs.ICALP.2019.137

DO - 10.4230/LIPIcs.ICALP.2019.137

M3 - Conference contribution

AN - SCOPUS:85069201389

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019

A2 - Baier, Christel

A2 - Chatzigiannakis, Ioannis

A2 - Flocchini, Paola

A2 - Leonardi, Stefano

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

ER -

Czyzowicz J, Georgiou K, Killick R, Kranakis E, Krizanc D, Lafond M et al. Energy consumption of group search on a line. In Baier C, Chatzigiannakis I, Flocchini P, Leonardi S, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2019. 137. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPIcs.ICALP.2019.137