Show simple item record

Position Discovery for a System of Bouncing Robots

hal.structure.identifierDépartement d'Informatique et d'Ingénierie [DII]
dc.contributor.authorCZYZOWICZ, Jurek
hal.structure.identifierDepartment of Computer Science [Liverpool]
dc.contributor.authorGASIENIEC, Leszek
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorKOSOWSKI, Adrian
hal.structure.identifierSchool of Computer Science (Carleton, Ottawa)
dc.contributor.authorKRANAKIS, Evangelos
hal.structure.identifierSchool of Computer Science (Carleton, Ottawa)
dc.contributor.authorMORALES PONCE, Oscar
hal.structure.identifierSchool of Computer Science (Carleton, Ottawa)
dc.contributor.authorPACHECO, Eduardo
dc.date.accessioned2024-04-15T09:44:34Z
dc.date.available2024-04-15T09:44:34Z
dc.date.issued2012
dc.date.conference2012
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197857
dc.description.abstractEnA collection of $n$ anonymous mobile robots is deployed on a unit-perimeter ring or a unit-length line segment. Every robot starts moving at constant speed, and bounces each time it meets any other robot or segment endpoint, changing its walk direction. We study the problem of {\em position discovery}, in which the task of each robot is to detect the presence and the initial positions of all other robots. The robots cannot communicate or perceive information about the environment in any way other than by bouncing. Each robot has a clock allowing it to observe the times of its bounces. The robots have no control on their walks, which are determined by their initial positions and the starting directions. Each robot executes the same \emph{position detection algorithm}, which receives input data in real-time about the times of the bounces, and terminates when the robot is assured about the existence and the positions of all the robots. Some initial configuration of robots are shown to be {\em infeasible} --- no position detection algorithm exists for them. We give complete characterizations of all infeasible initial configurations for both the ring and the segment, and we design optimal position detection algorithms for all feasible configurations. For the case of the ring, we show that all robot configurations in which not all the robots have the same initial direction are feasible. We give a position detection algorithm working for all feasible configurations. The cost of our algorithm depends on the number of robots starting their movement in each direction. If the less frequently used initial direction is given to $k \leq n/2$ robots, the time until completion of the algorithm by the last robot is $\frac{1}{2}\lceil \frac{n}{k} \rceil$. We prove that this time is optimal. By contrast to the case of the ring, for the unit segment we show that the family of infeasible configurations is exactly the set of so-called {\em symmetric configurations}. We give a position detection algorithm which works for all feasible configurations on the segment in time $2$, and this algorithm is also proven to be optimal.
dc.language.isoen
dc.title.enPosition Discovery for a System of Bouncing Robots
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-642-33651-5_24
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
bordeaux.page341-355
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleDISC - 26th International Symposium on Distributed Computing
bordeaux.countryBR
bordeaux.conference.citySalvador
bordeaux.peerReviewedoui
hal.identifierhal-00735828
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00735828v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2012&rft.spage=341-355&rft.epage=341-355&rft.au=CZYZOWICZ,%20Jurek&GASIENIEC,%20Leszek&KOSOWSKI,%20Adrian&KRANAKIS,%20Evangelos&MORALES%20PONCE,%20Oscar&rft.genre=unknown


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record