Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Near-Gathering of Energy-Constrained Mobile Agents

  • Conference paper
  • First Online:
Structural Information and Communication Complexity (SIROCCO 2019)

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

  • 348 Accesses

Abstract

We study the task of gathering k energy-constrained mobile agents in an undirected edge-weighted graph. Each agent is initially placed on an arbitrary node and has a limited amount of energy, which constrains the distance it can move. Since this may render gathering at a single point impossible, we study three variants of near-gathering:

The goal is to move the agents into a configuration that minimizes either (i) the radius of a ball containing all agents, (ii) the maximum distance between any two agents, or (iii) the average distance between the agents. We prove that (i) is polynomial-time solvable, (ii) has a polynomial-time 2-approximation with a matching NP-hardness lower bound, while (iii) admits a polynomial-time \(2(1-\tfrac{1}{k})\)-approximation, but no FPTAS, unless \(\text {P}=\text {NP}\). We extend some of our results to additive approximation.

This work was partially supported by the SNF (project 200021L_156620) and by the ANR (project ANCOR anr-14-CE36-0002-01), while A. Bärtschi was working at ETH Zürich, and E. Bampas and C. Karousatou were working at Aix-Marseille Université. The Los Alamos National Laboratory report number is LA-UR-19-23906.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /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
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • 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

Institutional subscriptions

Similar content being viewed by others

References

  1. Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. Kluwer, Boston (2003)

    MATH  Google Scholar 

  2. Anaya, J., Chalopin, J., Czyzowicz, J., Labourel, A., Pelc, A., Vaxès, Y.: Convergecast and broadcast by power-aware mobile agents. Algorithmica 74(1), 117–155 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  3. Awerbuch, B., Betke, M., Rivest, R.L., Singh, M.: Piecemeal graph exploration by a mobile robot. Inf. Comput. 152(2), 155–172 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bampas, E., Das, S., Dereniowski, D., Karousatou, C.: Collaborative delivery by energy-sharing low-power mobile robots. In: ALGOSENSORS 2017, pp. 1–12 (2017)

    Google Scholar 

  5. Bärtschi, A., et al.: Collaborative delivery with energy-constrained mobile robots. In: SIROCCO 2016, pp. 258–274 (2016)

    Chapter  Google Scholar 

  6. Bärtschi, A., et al.: Collaborative delivery with energy-constrained mobile robots. In: Theoretical Computer Science, SIROCCO 2016 (2017)

    Google Scholar 

  7. Betke, M., Rivest, R.L., Singh, M.: Piecemeal learning of an unknown environment. Mach. Learn. 18(2), 231–254 (1995)

    Google Scholar 

  8. Bilò, D., Disser, Y., Gualà, L., Mihalák, M., Proietti, G., Widmayer, P.: Polygon-constrained motion planning problems. In: ALGOSENSORS 2013, pp. 67–82 (2013)

    Google Scholar 

  9. Chalopin, J., Das, S., Mihalák, M., Penna, P., Widmayer, P.: Data delivery by energy-constrained mobile agents. In: ALGOSENSORS 2013, pp. 111–122 (2013)

    Google Scholar 

  10. Chalopin, J., Jacob, R., Mihalák, M., Widmayer, P.: Data delivery by energy-constrained mobile agents on a line. In: ICALP 2014, pp. 423–434 (2014)

    Chapter  Google Scholar 

  11. Cicerone, S., Stefano, G.D., Navarra, A.: Gathering of robots on meeting-points: feasibility and optimal resolution algorithms. Distrib. Comput. 31(1), 1–50 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  12. Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile robots: gathering. SIAM J. Comput. 41(4), 829–879 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  13. Cohen, R., Peleg, D.: Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 34, 1516–1528 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  14. Czyzowicz, J., Diks, K., Moussi, J., Rytter, W.: Communication problems for mobile agents exchanging energy. In: SIROCCO 2016 (2016)

    Chapter  MATH  Google Scholar 

  15. Czyzowicz, J., Labourel, A., Pelc, A.: How to meet asynchronously (almost) everywhere. ACM Trans. Algorithms 8(4), 37:1–37:14 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  16. Das, S., Dereniowski, D., Karousatou, C.: Collaborative exploration by energy-constrained mobile robots. In: SIROCCO 2015, pp. 357–369 (2015)

    Google Scholar 

  17. Demaine, E.D., Hajiaghayi, M., Mahini, H., Sayedi-Roshkhar, A.S., Oveisgharan, S., Zadimoghaddam, M.: Minimizing movement. ACM Trans. Algorithms 5(3), 30:1–30:30 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  18. Demaine, E.D., Hajiaghayi, M., Marx, D.: Minimizing movement: fixed-parameter tractability. ACM Trans. Algorithms 11(2), 14:1–14:29 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  19. Dereniowski, D., Disser, Y., Kosowski, A., Pająk, D., Uznański, P.: Fast collaborative graph exploration. Inf. Comput. 243, 37–49 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  20. Duncan, C.A., Kobourov, S.G., Kumar, V.S.A.: Optimal constrained graph exploration. ACM Trans. Algorithms 2(3), 380–402 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  21. Dynia, M., Korzeniowski, M., Schindelhauer, C.: Power-aware collective tree exploration. In: ARCS 2006, pp. 341–351 (2006)

    Chapter  Google Scholar 

  22. Dynia, M., Łopuszański, J., Schindelhauer, C.: Why robots need maps. In: SIROCCO 2007, pp. 41–50 (2007)

    Google Scholar 

  23. Flocchini, P., Prencipe, G., Santoro, N. (eds.): Distributed Computing by Mobile Entities, Current Research in Moving and Computing. Lecture Notes in Computer Science, vol. 11340. Springer, Switzerland (2019). https://doi.org/10.1007/978-3-030-11072-7

  24. Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theoret. Comput. Sci. 337(1–3), 147–168 (2005)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  26. Lin, J., Morse, A.S., Anderson, B.D.O.: The multi-agent rendezvous problem (parts 1 and 2). SIAM J. Control Optim. 46(6), 2096–2147 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  27. Pagli, L., Prencipe, G., Viglietta, G.: Getting close without touching: near-gathering for autonomous mobile robots. Distrib. Comput. 28(5), 333–349 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  28. Pelc, A.: Deterministic rendezvous in networks: a comprehensive survey. Networks 59(3), 331–347 (2012)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Center for Nonlinear Studies, Los Alamos National Laboratory, Los Alamos, NM, USA

    Andreas Bärtschi

  2. Laboratoire de Recherche en Informatique, Université Paris-Sud, Orsay Cedex, France

    Evangelos Bampas

  3. CNRS, Aix-Marseille Université and Université de Toulon, LIS, Toulon, France

    Jérémie Chalopin & Shantanu Das

  4. Department of Mathematics, TU Darmstadt, Darmstadt, Germany

    Christina Karousatou

  5. Department of Data Science and Knowledge Engineering, Maastricht University, Maastricht, The Netherlands

    Matúš Mihalák

Authors
  1. Andreas Bärtschi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Evangelos Bampas
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jérémie Chalopin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Shantanu Das
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Christina Karousatou
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Matúš Mihalák
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andreas Bärtschi .

Editor information

Editors and Affiliations

  1. Technion, Haifa, Israel

    Keren Censor-Hillel

  2. University of L'Aquila, L'Aquila, Italy

    Michele Flammini

Rights and permissions

Reprints and permissions

Copyright information

© 2019 This is a U.S. government work and not under copyright protection in the U.S.; foreign copyright protection may apply

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Bärtschi, A., Bampas, E., Chalopin, J., Das, S., Karousatou, C., Mihalák, M. (2019). Near-Gathering of Energy-Constrained Mobile Agents. In: Censor-Hillel, K., Flammini, M. (eds) Structural Information and Communication Complexity. SIROCCO 2019. Lecture Notes in Computer Science(), vol 11639. Springer, Cham. https://doi.org/10.1007/978-3-030-24922-9_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-24922-9_4

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-24921-2

  • Online ISBN: 978-3-030-24922-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation