Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

The Beachcombers’ Problem: Walking and Searching with Mobile Robots

  • Conference paper

Abstract

We introduce and study a new problem concerning the exploration of a geometric domain by mobile robots. Consider a line segment [0,I] and a set ofn mobile robotsr1,r2,…,rn placed at one of its endpoints. Each robot has asearching speedsi and awalking speedwi, wheresi < wi. We assume that every robot is aware of the number of robots of the collection and their corresponding speeds.

At each time moment a robotri either walks along a portion of the segment not exceeding its walking speedwi, or it searches a portion of the segment with speed not exceedingsi. A search of segment [0,I] is completed at the time when each of its points have been searched by at least one of then robots. We want to develop efficientmobility schedules (algorithms) for the robots which complete the search of the segment as fast as possible. More exactly we want to maximize thespeed of the mobility schedule (equal to the ratio of the segment length versus the time of the completion of the schedule).

We analyze first the offline scenario when the robots know the length of the segment that is to be searched. We give an algorithm producing a mobility schedule for arbitrary walking and searching speeds and prove its optimality. Then we propose an online algorithm, when the robots do not know in advance the actual length of the segment to be searched. The speedS of such algorithm is defined as\( S = \inf_{I_L} S(I_L) \) whereS(IL) denotes the speed of searching of segmentIL = [0,L]. We prove that the proposed online algorithm is 2-competitive. The competitive ratio is shown to be better in the case when the robots’ walking speeds are all the same, approaching 1.29843 asn goes to infinity.

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

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Koopman, B.O.: Search and screening. Operations Evaluation Group, Office of the Chief of Naval Operations, Navy Department (1946)

    Google Scholar 

  2. Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. In: Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pp. 355–361. IEEE (1990)

    Google Scholar 

  3. Fomin, F.V., Thilikos, D.M.: An annotated bibliography on guaranteed graph searching. Theor. Comput. Sci. 399(3), 236–245 (2008)

    Article MATH MathSciNet  Google Scholar 

  4. Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164–1188 (2000)

    Article MATH MathSciNet  Google Scholar 

  5. Alpern, S., Gal, S.: The theory of search games and rendezvous, vol. 55. Kluwer Academic Publishers (2002)

    Google Scholar 

  6. Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching in the plane. Information and Computation 106, 234 (1993)

    Article MATH MathSciNet  Google Scholar 

  7. Czyzowicz, J., Ilcinkas, D., Labourel, A., Pelc, A.: Worst-case optimal exploration of terrains with obstacles. Inf. Comput. 225, 16–28 (2013)

    Article MATH MathSciNet  Google Scholar 

  8. Deng, X., Kameda, T., Papadimitriou, C.H.: How to learn an unknown environment (extended abstract). In: FOCS, pp. 298–303 (1991)

    Google Scholar 

  9. Bellman, R.: An optimal search problem. Bull. Am. Math. Soc., 270 (1963)

    Google Scholar 

  10. Beck, A.: On the linear search problem. Israel Journal of Mathematics 2(4), 221–228 (1964)

    Article MATH MathSciNet  Google Scholar 

  11. Demaine, E.D., Fekete, S.P., Gal, S.: Online searching with turn cost. Theoretical Computer Science 361(2), 342–355 (2006)

    Article MATH MathSciNet  Google Scholar 

  12. Albers, S.: Online algorithms: a survey. Math. Program. 97(1-2), 3–26 (2003)

    MATH MathSciNet  Google Scholar 

  13. Albers, S., Schmelzer, S.: Online algorithms - what is it worth to know the future? In: Algorithms Unplugged, pp. 361–366 (2011)

    Google Scholar 

  14. Berman, P.: On-line searching and navigation. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms 1996. LNCS, vol. 1442, pp. 232–241. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  15. Fleischer, R., Kamphans, T., Klein, R., Langetepe, E., Trippen, G.: Competitive online approximation of the optimal search ratio. SIAM J. Comput. 38(3), 881–898 (2008)

    Article MATH MathSciNet  Google Scholar 

  16. Dereniowski, D., Disser, Y., Kosowski, A., Pająk, D., Uznański, P.: Fast collaborative graph exploration. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol. 7966, pp. 520–532. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  17. Chalopin, J., Flocchini, P., Mans, B., Santoro, N.: Network exploration by silent and oblivious robots. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol. 6410, pp. 208–219. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  18. Das, S., Flocchini, P., Kutten, S., Nayak, A., Santoro, N.: Map construction of unknown graphs by multiple agents. Theor. Comput. Sci. 385(1-3), 34–48 (2007)

    Article MATH MathSciNet  Google Scholar 

  19. Fraigniaud, P., Gasieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. Networks 48(3), 166–177 (2006)

    Article MATH MathSciNet  Google Scholar 

  20. Higashikawa, Y., Katoh, N., Langerman, S., Tanigawa, S.: Online graph exploration algorithms for cycles and trees by multiple searchers. J. Comb. Optim. (2012)

    Google Scholar 

  21. Wang, G., Irwin, M.J., Fu, H., Berman, P., Zhang, W., Porta, T.L.: Optimizing sensor movement planning for energy efficiency. ACM Transactions on Sensor Networks 7(4), 33 (2011)

    Article  Google Scholar 

  22. Beauquier, J., Burman, J., Clement, J., Kutten, S.: On utilizing speed in networks of mobile agents. In: Proceeding of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 305–314. ACM (2010)

    Google Scholar 

  23. Czyzowicz, J., Gąsieniec, L., Kosowski, A., Kranakis, E.: Boundary patrolling by mobile agents with distinct maximal speeds. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 701–712. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  24. Kawamura, A., Kobayashi, Y.: Fence patrolling by mobile agents with distinct speeds. In: Chao, K.-M., Hsu, T.-S., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 598–608. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department d’Informatique, Université du Québec en Outaouais, Gatineau, Québec, Canada

    Jurek Czyzowicz

  2. Department of Computer Science, University of Liverpool, Liverpool, UK

    Leszek Gąsieniec

  3. Dept. of Combinatorics & Optimization, University of Waterloo, Waterloo, Ontario, Canada

    Konstantinos Georgiou

  4. School of Computer Science, Carleton University, Ottawa, Ontario, Canada

    Evangelos Kranakis & Fraser MacQuarrie

Authors
  1. Jurek Czyzowicz

    You can also search for this author inPubMed Google Scholar

  2. Leszek Gąsieniec

    You can also search for this author inPubMed Google Scholar

  3. Konstantinos Georgiou

    You can also search for this author inPubMed Google Scholar

  4. Evangelos Kranakis

    You can also search for this author inPubMed Google Scholar

  5. Fraser MacQuarrie

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Computer Science, Reykjavik University, Menntavegur 1, 101, Reykjavik, Iceland

    Magnús M. Halldórsson

Rights and permissions

Copyright information

© 2014 Springer International Publishing Switzerland

About this paper

Cite this paper

Czyzowicz, J., Gąsieniec, L., Georgiou, K., Kranakis, E., MacQuarrie, F. (2014). The Beachcombers’ Problem: Walking and Searching with Mobile Robots. In: Halldórsson, M.M. (eds) Structural Information and Communication Complexity. SIROCCO 2014. Lecture Notes in Computer Science, vol 8576. Springer, Cham. https://doi.org/10.1007/978-3-319-09620-9_4

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

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