Almost universal anonymous rendezvous in the plane

DOI10.1007/S00453-023-01122-2MaRDI QIDQ6046947zbMATH OpenOpenAlexFDO

Authors Yoann Dieudonné, Andrzej Pelc, Franck Petit

Publication date 6 October 2023

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.00880

zbMATH Keywords

symmetry breaking rendezvous plane anonymous agent

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Abstract: Two mobile agents represented by points freely moving in the plane and starting at two distinct positions, have to meet. The meeting, called rendezvous, occurs when agents are at distance at most

r

of each other and never move after this time, where

r

is a positive real unknown to them, called the visibility radius. Agents are anonymous and execute the same deterministic algorithm. Each agent has a set of private attributes, some or all of which can differ between agents. These attributes are: the initial position of the agent, its system of coordinates (orientation and chirality), the rate of its clock, its speed when it moves, and the time of its wake-up. If all attributes (except the initial positions) are identical and agents start at distance larger than

r

then they can never meet. However, differences between attributes make it sometimes possible to break the symmetry and accomplish rendezvous. Such instances of the rendezvous problem (formalized as lists of attributes), are called feasible. Our contribution is three-fold. We first give an exact characterization of feasible instances. Thus it is natural to ask whether there exists a single algorithm that guarantees rendezvous for all these instances. We give a strong negative answer to this question: we show two sets

S_{1}

and

S_{2}

of feasible instances such that none of them admits a single rendezvous algorithm valid for all instances of the set. On the other hand, we construct a single algorithm that guarantees rendezvous for all feasible instances outside of sets

S_{1}

and

S_{2}

. We observe that these exception sets

S_{1}

and

S_{2}

are geometrically very small, compared to the set of all feasible instances: they are included in low-dimension subspaces of the latter. Thus, our rendezvous algorithm handling all feasible instances other than these small sets of exceptions can be justly called almost universal.

Cites work

Cited in

(1)

Deterministic Meeting of Sniffing Agents in the Plane*

This page was built for publication: Almost universal anonymous rendezvous in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046947)