Optimizing Robot Dispersion on Grids: with and without Fault Tolerance

التفاصيل البيبلوغرافية
العنوان: Optimizing Robot Dispersion on Grids: with and without Fault Tolerance
المؤلفون: Banerjee, Rik, Kumar, Manish, Molla, Anisur Rahaman
سنة النشر: 2024
المجموعة: Computer Science
مصطلحات موضوعية: Computer Science - Distributed, Parallel, and Cluster Computing
الوصف: The introduction and study of dispersing mobile robots across the nodes of an anonymous graph have recently gained traction and have been explored within various graph classes and settings. While optimal dispersion solution was established for {\em oriented} grids [Kshemkalyani et al., WALCOM 2020], a significant unresolved question pertains to whether achieving optimal dispersion is feasible on an {\em unoriented} grid. This paper investigates the dispersion problem on unoriented grids, considering both non-faulty and faulty robots. The challenge posed by unoriented grids lies in the absence of a clear sense of direction for a single robot moving between nodes, as opposed to the straightforward navigation of oriented grids. We present three deterministic algorithms tailored to our robot model. The first and second algorithms deal with the dispersion of faulty and non-faulty robots, ensuring both time and memory optimization in oriented and unoriented grids, respectively. Faulty robots that are prone to crashing at any time, causing permanent failure. In both settings, we achieve dispersion in $O(\sqrt{n})$ rounds while requiring $O(\log n)$ bits of memory per robot. The third algorithm tackles faulty robots prone to crash faults in an unoriented grid. In this scenario, our algorithm operates within $O(\sqrt{n} \log n)$ time and uses $O(\sqrt{n} \log n)$ bits of memory per robot. The robots need to know the value of $n$ for termination.
نوع الوثيقة: Working Paper
URL الوصول: http://arxiv.org/abs/2405.02002
رقم الأكسشن: edsarx.2405.02002
قاعدة البيانات: arXiv