Top

Published in:

2016 | OriginalPaper | Chapter

Collaborative Delivery with Energy-Constrained Mobile Robots

Authors : Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Barbara Geissmann, Daniel Graf, Arnaud Labourel, Matúš Mihalák

Published in: Structural Information and Communication Complexity

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider the problem of collectively delivering some message from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent has a limited energy which constrains the distance it can move. Hence multiple agents need to collaborate to move the message, each agent handing over the message to the next agent to carry it forward. Given the positions of the agents in the graph and their respective budgets, the problem of finding a feasible movement schedule for the agents can be challenging. We consider two variants of the problem: in non-returning delivery, the agents can stop anywhere; whereas in returning delivery, each agent needs to return to its starting location, a variant which has not been studied before. We first provide a polynomial-time algorithm for returning delivery on trees, which is in contrast to the known (weak) \(\mathrm {NP}\)-hardness of the non-returning version. In addition, we give resource-augmented algorithms for returning delivery in general graphs. Finally, we give tight lower bounds on the required resource augmentation for both variants of the problem. In this sense, our results close the gap left by previous research.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Universal Systems of Oblivious Mobile Robots

next chapter Communication Problems for Mobile Agents Exchanging Energy

In the nonreturning version we want agents to have the same “range”, hence we set their budget to \(\zeta \).

In the nonreturning version we assign a budget of \((1+\zeta )\) to clause agents.

We relocate a non-returning agent by adding an edge of length \((B-B_i)\).

Non-returning clause agents can do this if they are 3-resource-augmented; and we can prevent it for \((3-\varepsilon )\)-resource-augmentation by setting \(\zeta \) such that \((3-\varepsilon )\cdot (1+\zeta ) \ll 3\) (in fact the value of \(\zeta \) will be the same as for returning BudgetedDelivery, but we will use different bounds in the proof).

In the nonreturning version, variable agents have a budget of \(\zeta \) and clause agents a budget of \(1+\zeta \).

For non-returning agents we use (for \(\varepsilon < 2\)) the inequalities: \(\zeta = \tfrac{\varepsilon }{6-\varepsilon }< \tfrac{\varepsilon }{4} < \tfrac{\varepsilon }{2}\) and \((6-\varepsilon ) > 2(3-\varepsilon )\). Hence a non-returning \(\gamma \)-resource-augmented clause agent has a budget of \(\gamma (1+\zeta ) = (3-\varepsilon )(1+\zeta ) = 3-\varepsilon + \tfrac{(3-\varepsilon )\varepsilon }{6-\varepsilon }< 3-\tfrac{\varepsilon }{2} < 3-\zeta = 3\cdot (1-\tfrac{\zeta }{3})\), and thus cannot transport the message via its clause node.

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

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)MathSciNetCrossRefMATH

Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics). Princeton University Press, Princeton (2007)

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

Bärtschi, A., Chalopin, J., Das, S., Disser, Y., Geissmann, B., Graf, D., Labourel, A., Mihalák, M.: Collaborative Delivery with Energy-Constrained Mobile Robots, arXiv preprint. https://arxiv.org/abs/1606.05538 (2016)

Bender, M.A., Slonim, D.K.: The power of team exploration: two robots can learn unlabeled directed graphs. In: 35th Symposium on Foundations of Computer Science, FOCS 1994, pp. 75–85 (1994)

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

Biló, D., Disser, Y., Gualá, L., Mihal’ák, M., Proietti, G., Widmayer, P.: Polygon-constrained motion planning problems. In: Flocchini, P., Gao, J., Kranakis, E., der Heide, F.M. (eds.) ALGOSENSORS 2013. LNCS, vol. 8243, pp. 67–82. Springer, Heidelberg (2014)CrossRef

Chalopin, J., Das, S., Mihalák, M., Penna, P., Widmayer, P.: Data delivery by energy-constrained mobile agents. In: Flocchini, P., Gao, J., Kranakis, E., der Heide, F.M. (eds.) ALGOSENSORS 2013. LNCS, vol. 8243, pp. 111–122. Springer, Heidelberg (2014)CrossRef

10.

Chalopin, J., Jacob, R., Mihalák, M., Widmayer, P.: Data delivery by energy-constrained mobile agents on a line. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 423–434. Springer, Heidelberg (2014)

11.

Czyzowicz, J., Diks, K., Moussi, J., Rytter, W.: Communication problems for mobile agents exchanging energy. In: 23rd International Colloquium on Structural Information and Communication Complexity SIROCCO 2016 (2016)

12.

Das, S., Dereniowski, D., Karousatou, C.: Collaborative exploration by energy-constrained mobile robots. In: 22th International Colloquium on Structural Information and Communication Complexity SIROCCO 2015, pp. 357–369 (2015)

13.

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

14.

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

15.

Duncan, C.A., Kobourov, S.G., Kumar, V.S.A.: Optimal constrained graph exploration. In: 12th ACM Symposium on Discrete Algorithms, SODA 2001, pp. 807–814 (2001)

16.

Dynia, M., Korzeniowski, M., Schindelhauer, C.: Power-aware collective tree exploration. In: Grass, W., Sick, B., Waldschmidt, K. (eds.) ARCS 2006. LNCS, vol. 3894, pp. 341–351. Springer, Heidelberg (2006)CrossRef

17.

Dynia, M., Łopuszański, J., Schindelhauer, C.: Why robots need maps. In: Prencipe, G., Zaks, S. (eds.) SIROCCO 2007. LNCS, vol. 4474, pp. 41–50. Springer, Heidelberg (2007)CrossRef

18.

Edmonds, J., Johnson, E.L.: Matching, euler tours and the chinese postman. Math. Program. 5(1), 88–124 (1973)MathSciNetCrossRefMATH

19.

Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Morgan & Claypool, San Rafeal (2012)MATH

20.

Fraigniaud, P., Ga̧sieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. Networks 48(3), 166–177 (2006)MathSciNetCrossRefMATH

21.

Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)MathSciNetCrossRefMATH

22.

Ortolf, C., Schindelhauer, C.: Online multi-robot exploration of grid graphs with rectangular obstacles. In: 24th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2012, pp. 27–36 (2012)

23.

Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorithms 33(2), 281–295 (1999)MathSciNetCrossRefMATH

Title: Collaborative Delivery with Energy-Constrained Mobile Robots
Authors: Andreas Bärtschi
Jérémie Chalopin
Shantanu Das
Yann Disser
Barbara Geissmann
Daniel Graf
Arnaud Labourel
Matúš Mihalák
Publisher: Springer International Publishing
Book: Structural Information and Communication Complexity
Print ISBN: 978-3-319-48313-9

Electronic ISBN: 978-3-319-48314-6

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-48314-6_17

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner