Wireless autonomous robot evacuation from equilateral triangles and squares

J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, S. Shende

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

30 Scopus citations

Abstract

Consider an equilateral triangle or square with sides of length 1. A number of robots starting at the same location on the perimeter or in the interior of the triangle or square are required to evacuate from an exit which is located at an unknown location on its perimeter. At any time the robots can move at identical speed equal to 1, and they can cooperate by communicating with each other wirelessly. Thus, if a robot finds the exit it can broadcast “exit found” to the remaining robots which then move in a straight line segment towards the exit to evacuate. Our task is to design robot trajectories that minimize the evacuation time of the robots, i.e., the time the last robot evacuates from the exit. Designing such optimal algorithms turns out to be a very demanding problem and even the case of equilateral triangles turns out to be challenging. We design optimal evacuation trajectories (algorithms) for two robots in the case of equilateral triangles for any starting position and for squares for starting positions on the perimeter. It is shown that for an equilateral triangle, three or more robots starting on the perimeter cannot achieve better evacuation time than two robots, while there exist interior starting points from which three robots evacuate faster than two robots. For the square, three or more robots starting at one of the corners cannot achieve better evacuation time than two robots, but there exist points on the perimeter of the square such that three robots starting from such a point evacuate faster than two robots starting from this same point. In addition, in either the equilateral triangle or the square it can be shown that a simple algorithm is asymptotically optimal (in the number k of robots, as k → ∞), provided that the robots start at the centre of the corresponding domain.

Original languageEnglish (US)
Title of host publicationAd-hoc, Mobile, and Wireless Networks - 14th International Conference, ADHOC-NOW 2015, Proceedings
EditorsSymeon Papavassiliou, Stefan Ruehrup
PublisherSpringer Verlag
Pages181-194
Number of pages14
ISBN (Print)9783319196619
DOIs
StatePublished - 2015
Event14th International Conference on Ad-Hoc Networks and Wireless, ADHOC-NOW 2015 - Athens, Greece
Duration: Jun 29 2015Jul 1 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9143

Other

Other14th International Conference on Ad-Hoc Networks and Wireless, ADHOC-NOW 2015
Country/TerritoryGreece
CityAthens
Period6/29/157/1/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Evacuation
  • Mobile robots
  • Square
  • Triangle
  • Wireless communication

Fingerprint

Dive into the research topics of 'Wireless autonomous robot evacuation from equilateral triangles and squares'. Together they form a unique fingerprint.

Cite this