Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Gathering Autonomous Mobile Robots with Dynamic Compasses: An Optimal Result

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 4731))

Included in the following conference series:

Abstract

Let considern autonomous mobile robots that can move in a two dimensional plane. The gathering problem is one of the most fundamental tasks of autonomous mobile robots. In short, given a set of robots with arbitrary initial locations, gathering must make all robots meet in finite time at a point that is not predefined. In this paper, we study about the feasibility of gathering by mobile robots that haveφ-absolute error dynamic compasses. While the direction of each local coordinate system is fixed in usual systems, the dynamic compass model allows the angle difference between a local coordinate system and the global coordinate system to vary with time in the range of [0,φ]. This paper proposes a semi-synchronous gathering algorithm forn robots with (π/2 − ε)-absolute error dynamic compasses, whereε is an arbitrary small constant larger than zero. To the best of our knowledge, the proposed algorithm is the first one that considers both inaccurate compass models and more than two robots. We also show the optimality of our algorithm. It is proved that for anyφ ≥ π/2, there is no algorithm to gather two robots withφ-absolute error dynamic compasses.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Agmon, N., Peleg, D.: Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM Journal of Computing 36(1), 56–82 (2006)

    Article MATH MathSciNet  Google Scholar 

  2. Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Solving the robots gathering problem. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 1181–1196. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  3. Cohen, R., Peleg, D.: Convergence of autonomous mobile robots with inaccurate sensors and movements. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 549–560. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  4. Défago, X., Gradinariu, M., Messika, S., Parvédy, P.R.: Fault-tolerant and self-stabilizing mobile robots gathering. In: Dolev, S. (ed.) DISC 2006. LNCS, vol. 4167, pp. 46–60. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  5. Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theoreical Computer Science 337(1-3), 147–168 (2005)

    Article MATH MathSciNet  Google Scholar 

  6. Imazu, H., Itoh, N., Inuzuka, K.Y.N., Wada, K.: A gathering problem for autonomous mobile robots with disagreement in compasses. In: Proc. of First Workshop on Theoretical Computer Science in Izumo, pp. 43–44 (2005) (in Japanese)

    Google Scholar 

  7. Katayama, Y., Tomida, Y., Imazu, H., Inuzuka, N., Wada, K.: Dynamic compass models and gathering algorithm for autonomous mobile robots. In: SIROCCO 2007. LNCS, vol. 4474, pp. 274–288 (2007)

    Google Scholar 

  8. Prencipe, G.: CORDA: distributed coordination of a set of autonomous mobile robots. In: Proc. of Fourth European Research Seminar on Advances in Distributed Systems (ESRADS) (2001)

    Google Scholar 

  9. Prencipe, G.: Distributed Coordination of a Set of Autonomous Mobile Robots. PhD thesis, University of Pisa (2002)

    Google Scholar 

  10. Prencipe, G.: On the feasibility of gathering by autonomous mobile robots. In: Pelc, A., Raynal, M. (eds.) SIROCCO 2005. LNCS, vol. 3499, pp. 246–261. Springer, Heidelberg (2005)

    Google Scholar 

  11. Souissi, S., Défago, X., Yamashita, M.: Gathering asynchronous mobile robots with inaccurate compasses. In: Shvartsman, A.A. (ed.) OPODIS 2006. LNCS, vol. 4305, pp. 333–349. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  12. Souissi, S., Défago, X., Yamashita, M.: Using eventually consistent compasses to gather oblivious mobile robots with limited visibility. In: Datta, A.K., Gradinariu, M. (eds.) SSS 2006. LNCS, vol. 4280, pp. 471–487. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  13. Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal of Computing 28(4), 1347–1363 (1999)

    Article MATH MathSciNet  Google Scholar 

  14. Yamashita, M., Souissi, S., Défago, X.: Tight bound on the gathering of obliviousmobile robots with inconsistent compasses. Unpublished (2007)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Nagoya Institute of Technology, Gokiso-cho, Showa-ku, Nagoya, Aichi 466-8555, Japan

    Taisuke Izumi, Yoshiaki Katayama, Nobuhiro Inuzuka & Koichi Wada

Authors
  1. Taisuke Izumi

    You can also search for this author inPubMed Google Scholar

  2. Yoshiaki Katayama

    You can also search for this author inPubMed Google Scholar

  3. Nobuhiro Inuzuka

    You can also search for this author inPubMed Google Scholar

  4. Koichi Wada

    You can also search for this author inPubMed Google Scholar

Editor information

Andrzej Pelc

Rights and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Izumi, T., Katayama, Y., Inuzuka, N., Wada, K. (2007). Gathering Autonomous Mobile Robots with Dynamic Compasses: An Optimal Result. In: Pelc, A. (eds) Distributed Computing. DISC 2007. Lecture Notes in Computer Science, vol 4731. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75142-7_24

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp