World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Mobile Robots with Uncertain Visibility Sensors: Possibility Results and Lower Bounds

    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 λ>0 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. I. Suzuki and M. Yamashita, Distributed anonymous mobile robots: Formation of geometric patterns, SIAM J. Comput. 28(4) (1999) 1347–1363. Crossref, ISIGoogle 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). CrossrefGoogle Scholar
    • 3. E. M. Mouaddib, R. Sagawa, T. Echigo and Y. Yagi, 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. CrossrefGoogle Scholar
    • 4. A. Honorat, M. Potop-Butucaru and S. Tixeuil, Gathering fat mobile robots with slim omnidirectional cameras, Theor. Comput. Sci. 557 (2014) 1–27. Crossref, ISIGoogle Scholar
    • 5. H. Ando, Y. Oasa, I. Suzuki and M. Yamashita, Distributed memoryless point convergence algorithm for mobile robots with limited visibility, IEEE Trans. Robotics and Automation 15(5) (1999) 818–828. CrossrefGoogle Scholar
    • 6. N. Gordon, Y. Elor and A. M. Bruckstein, 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. CrossrefGoogle Scholar
    • 7. N. Gordon, I. A. Wagner and A. M. Bruckstein, 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. CrossrefGoogle Scholar
    • 8. S. Souissi, X. Défago and M. Yamashita, 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, ISIGoogle Scholar
    • 9. P. Flocchini, G. Prencipe, N. Santoro and P. Widmayer, Gathering of asynchronous robots with limited visibility, Theor. Comput. Sci. 337(1–3) (2005) 147–168. Crossref, ISIGoogle Scholar
    • 10. J. Köhler, A. Pagani and D. Stricker, 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. N. Santoro and P. Widmayer, 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. CrossrefGoogle Scholar
    • 12. G. A. D. Luna, P. Flocchini, F. Poloni, N. Santoro and G. Viglietta, 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. G. Prencipe, Impossibility of gathering by a set of autonomous mobile robots, Theor. Comput. Sci. 384(2–3) (2007) 222–231. Crossref, ISIGoogle Scholar
    • 14. R. Cohen and D. Peleg, Convergence properties of the gravitational algorithm in asynchronous robot systems, SIAM J. Comput. 34(6) (2005) 1516–1528. Crossref, ISIGoogle Scholar
    • 15. T. Balabonski, A. Delga, L. Rieg, S. Tixeuil and X. Urbain, Synchronous gathering without multiplicity detection: A certified algorithm, Theory Comput. Syst. 63(2) (2019) 200–218. Crossref, ISIGoogle Scholar
    • 16. P. Flocchini, G. Prencipe, N. Santoro and G. Viglietta, Distributed computing by mobile robots: uniform circle formation, Distributed Computing 30(6) (2017) 413–457. Crossref, ISIGoogle Scholar
    • 17. M. Mamino and G. Viglietta, 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. I. Gupta, R. van Renesse and K. P. Birman, 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. CrossrefGoogle Scholar
    • 19. H. Attiya and J. L. Welch, Distributed Computing — Fundamentals, Simulations, and Advanced Topics, 2nd edn., Wiley Series on Parallel and Distributed Computing, Vol. 1 (Wiley, 2004). CrossrefGoogle Scholar
    • 20. M. Herlihy and J. M. Wing, Linearizability: A correctness condition for concurrent objects, ACM Trans. Program. Lang. Syst. 12(3) (1990) 463–492. Crossref, ISIGoogle Scholar
    • 21. D. Canepa and M. G. Potop-Butucaru, 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. CrossrefGoogle Scholar
    • 22. S. Das, P. Flocchini, G. Prencipe, N. Santoro and M. Yamashita, Autonomous mobile robots with lights Theor. Comput. Sci. 609 (2016) 171–184. Crossref, ISIGoogle Scholar
    • 23. G. Viglietta, 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. A. Heriban, X. Défago and S. Tixeuil, 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. CrossrefGoogle Scholar
    • 25. Z. Bouzid, S. Das and S. Tixeuil, 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. CrossrefGoogle Scholar
    • 26. Q. Bramas and S. Tixeuil, 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. CrossrefGoogle Scholar