Robots meet reliably using fixed distance despite disoriented views
Rendezvous under Variable Disorientation:The Algorithmic Power of Fixed Unit Distance
Distributed, Parallel, and Cluster Computing
Summary
This paper studies how two simple robots can find each other (rendezvous) even when each one sees the world differently – sometimes rotated, flipped, or stretched. The researchers show that if each robot keeps a fixed idea of unit distance, they can use this consistent measure as a kind of memory to coordinate their moves. They design color-based light signals and movement rules that let robots meet under varied conditions, including unpredictable schedules and limited visibility. Their work also clarifies the limits of such rendezvous strategies when this fixed distance information is missing or weaker.
What this means in practice
- •For robotics engineers: Design coordination protocols for simple robots that must meet without reliable orientation but with a stable distance measure.
- •For distributed systems developers: Develop algorithms for synchronized actions in systems where agents have inconsistent views but can measure consistent distance units.
A theory result. No direct application yet.
Authors
Toshimitsu Masuzawa, Yuichi Sudo, Koichi Wada
Abstract
We study deterministic Rendezvous of two robots with lights under weak geometric and synchronization assumptions. Our focus is on Variable Disorientation (VD), where each robot may arbitrarily rotate, reflect, and rescale its local coordinate system at every \Look, and on VD+Fixed-Unit-Distance (FUD), where each robot's local unit distance remains fixed. We consider the one-sided visibility models FSTA and FCOM, and schedulers ranging from the energy-restricted RSYNCH and R-RSYNCH to fully asynchronous executions. Under VD, we prove color-independent impossibility results for FSTA under SSYNCH and for FCOM under ASYNCH, and establish sharp two-color boundaries under RSYNCH and R-RSYNCH. Under VD+FUD, we introduce periodic distance classes, which turn multiplicative changes of the physical distance into predictable cyclic phase shifts. This technique yields a two-color self-stabilizing non-$L$-Rendezvous algorithm for both FSTA and FCOM under RSYNCH and R-RSYNCH even with Non-Rigid movement. Under Rigid movement, periodic distance classes further yield an optimal three-color non-quasi-self-stabilizing algorithm for FSTA under SSYNCH, a four-color FSTA algorithm under $M$-atomic ASYNCH, and a four-color FCOM algorithm under CM-atomic ASYNCH. By guarding the latter phase mechanism with two additional colors and replacing its initial swap by passive initialization, we obtain a six-color FCOM algorithm under full ASYNCH, improving the previous twelve-color upper bound by a factor of two. These results show that a fixed local metric can serve as persistent cyclic memory, and clarify how metric stability, one-sided visibility, and scheduler atomicity jointly determine Rendezvous solvability and color complexity.