Randomized gathering of asynchronous mobile robots
| Autor: | Debasish Pattanayak, Partha Sarathi Mandal, John Augustine |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
TheoryofComputation_MISCELLANEOUS Theoretical computer science General Computer Science Computer science Computation Mobile robot 0102 computer and information sciences 02 engineering and technology Adversary 01 natural sciences Theoretical Computer Science Computer Science::Robotics Adversarial system Computer Science - Distributed Parallel and Cluster Computing 010201 computation theory & mathematics Asynchronous communication 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Distributed Parallel and Cluster Computing (cs.DC) Impossibility Computer Science::Cryptography and Security |
| Zdroj: | Theoretical Computer Science. 858:64-80 |
| ISSN: | 0304-3975 |
| Popis: | This paper revisits the widely researched gathering problem for two robots without any agreement on the coordinate system in a scenario which allows randomization in the asynchronous scheduling model. The scheduler is considered to be the adversary which determines the activation schedule of the robots. The adversary comes in three flavors, namely, adaptive offline, adaptive online, and oblivious, based on the knowledge of the outcome of random bits. The robots follow wait-look-compute-move cycle. In this paper, we classify the problems based on the capability of the adversary to control the parameters such as wait time, computation delay and the speed of robots and check the feasibility of gathering in terms of adversarial knowledge and capabilities. First, we show the impossibility of gathering under an adaptive offline adversary with non-negative wait time and non-negative computation delay. Gradually relaxing the adversarial capabilities, we present impossibility of gathering for finite random choices and improbability for infinite random choices for an adaptive online adversary. Under an oblivious adversary, we establish the possibility of gathering with zero computation delay. We improve the runtime of the algorithm by restricting the oblivious adversary to choose wait time and computation delay such that the sum of wait time and computation delay is more than a positive constant. Finally, we also extend our algorithm for multiple robots with merging. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect