Mobile Robots with Uncertain Visibility Sensors: Possibility Results and Lower Bounds
Abstract
We consider mobile robotic entities that have to cooperate to solve assigned tasks. In the literature, two models have been used to model their visibility sensors: the full visibility model, where all robots can see all other robots, and the limited visibility model, where there exists a limit such that all robots closer than are seen and all robots further than are not seen. We introduce the uncertain visibility model, which generalizes both models by considering that a subset of the robots further than cannot be seen. An empty subset corresponds to the full visibility model, and a subset containing every such robot corresponds to the limited visibility model.
Then, we explore the impact of this new visibility model on the feasibility of benchmarking tasks in mobile robots computing: gathering, uniform circle formation, luminous rendezvous, and leader election. For each task, we determine the weakest visibility adversary that prevents task solvability, and the strongest adversary that allows task solvability. Our work sheds new light on the impact of visibility sensors in the context of mobile robot computing, and paves the way for more realistic algorithms that can cope with uncertain visibility sensors.
A preliminary 6-pages extended abstract of this paper appeared in SIROCCO 2019.
References
- 1. , Distributed anonymous mobile robots: Formation of geometric patterns, SIAM J. Comput. 28(4) (1999) 1347–1363. Crossref, ISI, Google Scholar
- 2. P. FlocchiniG. PrencipeN. Santoro (eds.), Distributed Computing by Mobile Entities, Current Research in Moving and Computing,
Lecture Notes in Computer Science , Vol. 11340 (Springer, 2019). Crossref, Google Scholar - 3. , Stereovision with a single camera and multiple mirrors, in Proceedings of the 2005 IEEE International Conference on Robotics and Automation, ICRA 2005,
April 18–22, 2005 ,Barcelona, Spain (IEEE, 2005), pp. 800–805. Crossref, Google Scholar - 4. , Gathering fat mobile robots with slim omnidirectional cameras, Theor. Comput. Sci. 557 (2014) 1–27. Crossref, ISI, Google Scholar
- 5. , Distributed memoryless point convergence algorithm for mobile robots with limited visibility, IEEE Trans. Robotics and Automation 15(5) (1999) 818–828. Crossref, Google Scholar
- 6. , Gathering multiple robotic agents with crude distance sensing capabilities, in Ant Colony Optimization and Swarm Intelligence, 6th International Conference, ANTS 2008,
September 22–24, 2008 ,Brussels, Belgium , Proceedings, eds. M. DorigoM. BirattariC. BlumM. ClercT. StützleA. F. T. Winfield,Lecture Notes in Computer Science , Vol. 5217 (Springer, 2008), pp. 72–83. Crossref, Google Scholar - 7. , Gathering multiple robotic a(ge)nts with limited sensing capabilities, in Ant Colony Optimization and Swarm Intelligence, 4th International Workshop, ANTS 2004,
September 5–8, 2004 ,Brussels, Belgium , Proceedings, eds. M. DorigoM. BirattariC. BlumL. M. GambardellaF. MondadaT. Stützle,Lecture Notes in Computer Science , Vol. 3172 (Springer, 2004), pp. 142–153. Crossref, Google Scholar - 8. , Using eventually consistent compasses to gather memory-less mobile robots with limited visibility, ACM Trans. Auton. Adapt. Syst. 4(1) (2009) 9:1–9:27. Crossref, ISI, Google Scholar
- 9. , Gathering of asynchronous robots with limited visibility, Theor. Comput. Sci. 337(1–3) (2005) 147–168. Crossref, ISI, Google Scholar
- 10. , Detection and identification techniques for markers used in computer vision, in Visualization of Large and Unstructured Data Sets – Applications in Geospatial Planning, Modeling and Engineering (IRTG 1131 Workshop), VLUDS 2010,
March 19–21, 2010 ,Bodega Bay, CA, USA , eds. A. Middel, I. Scheler and H. Hagen, OASICS 19 (Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, Germany, 2010), pp. 36–44. Google Scholar - 11. , Time is not a healer, in STACS 89, 6th Annual Symposium on Theoretical Aspects of Computer Science,
February 16–18, 1989 ,Paderborn, FRG , Proceedings, eds. B. MonienR. Cori,Lecture Notes in Computer Science , Vol. 349 (Springer, 1989), pp. 304–313. Crossref, Google Scholar - 12. , The mutual visibility problem for oblivious robots, in Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG 2014,
2014 ,Halifax, Nova Scotia, Canada (Carleton University, Ottawa, Canada, 2014). Google Scholar - 13. , Impossibility of gathering by a set of autonomous mobile robots, Theor. Comput. Sci. 384(2–3) (2007) 222–231. Crossref, ISI, Google Scholar
- 14. , Convergence properties of the gravitational algorithm in asynchronous robot systems, SIAM J. Comput. 34(6) (2005) 1516–1528. Crossref, ISI, Google Scholar
- 15. , Synchronous gathering without multiplicity detection: A certified algorithm, Theory Comput. Syst. 63(2) (2019) 200–218. Crossref, ISI, Google Scholar
- 16. , Distributed computing by mobile robots: uniform circle formation, Distributed Computing 30(6) (2017) 413–457. Crossref, ISI, Google Scholar
- 17. , Square formation by asynchronous oblivious robots, in Proceedings of the 28th Canadian Conference on Computational Geometry, CCCG 2016,
August 3–5, 2016 ,Simon Fraser University, Vancouver, British Columbia, Canada , ed. T. C. Shermer (Simon Fraser University, Vancouver, British Columbia, Canada, 2016), pp. 1–6. Google Scholar - 18. , A probabilistically correct leader election protocol for large groups, in Distributed Computing, 14th International Conference, DISC 2000,
October 4–6, 2000 ,Toledo, Spain , Proceedings, ed. M. Herlihy,Lecture Notes in Computer Science , Vol. 1914 (Springer, 2000), pp. 89–103. Crossref, Google Scholar - 19. , Distributed Computing — Fundamentals, Simulations, and Advanced Topics, 2nd edn.,
Wiley Series on Parallel and Distributed Computing , Vol. 1 (Wiley, 2004). Crossref, Google Scholar - 20. , Linearizability: A correctness condition for concurrent objects, ACM Trans. Program. Lang. Syst. 12(3) (1990) 463–492. Crossref, ISI, Google Scholar
- 21. , Stabilizing flocking via leader election in robot networks, in Stabilization, Safety, and Security of Distributed Systems, 9th International Symposium, SSS 2007,
November 14–16, 2007 ,Paris, France , Proceedings, eds. T. MasuzawaS. Tixeuil,Lecture Notes in Computer Science , Vol. 4838 (Springer, 2007), pp. 52–66. Crossref, Google Scholar - 22. , Autonomous mobile robots with lights Theor. Comput. Sci. 609 (2016) 171–184. Crossref, ISI, Google Scholar
- 23. , Rendezvous of two robots with visible bits, in Algorithms for Sensor Systems – 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2013,
September 5–6, 2013 ,Sophia Antipolis, France , Revised Selected Paper, eds. P. FlocchiniJ. GaoE. KranakisF. M. auf der Heide,Lecture Notes in Computer Science , Vol. 8243 (Springer, 2013), pp. 291–306. Google Scholar - 24. , Optimally gathering two robots, in Proceedings of the 19th International Conference on Distributed Computing and Networking, ICDCN 2018,
January 4–7, 2018 ,Varanasi, India , eds. P. BellavistaV. K. Garg (ACM, 2018), pp. 3:1–3:10. Crossref, Google Scholar - 25. , Gathering of mobile robots tolerating multiple crash faults, in IEEE 33rd International Conference on Distributed Computing Systems, ICDCS 2013,
July 8–11, 2013 ,Philadelphia, Pennsylvania, USA (IEEE Computer Society, 2013), pp. 337–346. Crossref, Google Scholar - 26. , Wait-free gathering without chirality, in Structural Information and Communication Complexity – 22nd International Colloquium, SIROCCO 2015,
July 14–16, 2015 ,Montserrat, Spain , Post-Proceedings, ed. C. Scheideler,Lecture Notes in Computer Science , Vol. 9439 (Springer, 2015), pp. 313–327. Crossref, Google Scholar


