Collective Fast Delivery by Energy-Efficient Agents

Authors Andreas Bärtschi, Daniel Graf, Matús Mihalák



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.56.pdf
  • Filesize: 0.81 MB
  • 16 pages

Document Identifiers

Author Details

Andreas Bärtschi
  • Department of Computer Science, ETH Zürich, Switzerland
Daniel Graf
  • Department of Computer Science, ETH Zürich, Switzerland
Matús Mihalák
  • Department of Data Science and Knowledge Engineering, Maastricht University, Netherlands

Cite AsGet BibTex

Andreas Bärtschi, Daniel Graf, and Matús Mihalák. Collective Fast Delivery by Energy-Efficient Agents. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 56:1-56:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.MFCS.2018.56

Abstract

We consider k mobile agents initially located at distinct nodes of an undirected graph (on n nodes, with edge lengths). The agents have to deliver a single item from a given source node s to a given target node t. The agents can move along the edges of the graph, starting at time 0, with respect to the following: Each agent i has a weight omega_i that defines the rate of energy consumption while travelling a distance in the graph, and a velocity upsilon_i with which it can move. We are interested in schedules (operating the k agents) that result in a small delivery time T (time when the item arrives at t), and small total energy consumption E. Concretely, we ask for a schedule that: either (i) Minimizes T, (ii) Minimizes lexicographically (T,E) (prioritizing fast delivery), or (iii) Minimizes epsilon * T + (1-epsilon)* E, for a given epsilon in (0,1). We show that (i) is solvable in polynomial time, and show that (ii) is polynomial-time solvable for uniform velocities and solvable in time O(n+k log k) for arbitrary velocities on paths, but in general is NP-hard even on planar graphs. As a corollary of our hardness result, (iii) is NP-hard, too. We show that there is a 2-approximation algorithm for (iii) using a single agent.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • delivery
  • mobile agents
  • time/energy optimization
  • complexity
  • algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Julian Anaya, Jérémie Chalopin, Jurek Czyzowicz, Arnaud Labourel, Andrzej Pelc, and Yann Vaxès. Convergecast and Broadcast by Power-Aware Mobile Agents. Algorithmica, 74(1):117-155, 2016. See also DISC'12. URL: http://dx.doi.org/10.1007/s00453-014-9939-8.
  2. David L. Applegate, Robert E. Bixby, Vasek Chvatal, and William J. Cook. The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton, NJ, USA, 2007. ISBN: 978-0-691-12993-8. Google Scholar
  3. Evangelos Bampas, Jurek Czyzowicz, Leszek Gasieniec, David Ilcinkas, Ralf Klasing, Tomasz Kociumaka, and Dominik Pająk. Linear Search by a Pair of Distinct-Speed Robots. In 23rd International Colloquium on Structural Information and Communication Complexity SIROCCO'16, pages 195-211, 2016. URL: http://dx.doi.org/10.1007/978-3-319-48314-6_13.
  4. Gerth Stølting Brodal and Riko Jacob. Dynamic Planar Convex Hull. In 43rd Symposium on Foundations of Computer Science FOCS'02, pages 617-626, 2002. URL: http://dx.doi.org/10.1109/SFCS.2002.1181985.
  5. Andreas Bärtschi. Efficient Delivery with Mobile Agents. PhD thesis, ETH Zürich, 2017. URL: http://dx.doi.org/10.3929/ethz-b-000232464.
  6. Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Barbara Geissmann, Daniel Graf, Arnaud Labourel, and Matúš Mihalák. Collaborative Delivery with Energy-Constrained Mobile Robots. In 23rd International Colloquium on Structural Information and Communication Complexity SIROCCO'16, pages 258-274, 2016. URL: http://dx.doi.org/10.1007/978-3-319-48314-6_17.
  7. Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Barbara Geissmann, Daniel Graf, Arnaud Labourel, and Matúš Mihalák. Collaborative delivery with energy-constrained mobile robots. Theoretical Computer Science, 2017. To appear. See also SIROCCO'16. URL: http://dx.doi.org/10.1016/j.tcs.2017.04.018.
  8. Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Daniel Graf, Jan Hackfeld, and Paolo Penna. Energy-efficient Delivery by Heterogeneous Mobile Agents. In 34th International Symposium on Theoretical Aspects of Computer Science STACS'17, pages 10:1-10:14, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2017.10.
  9. Andreas Bärtschi, Daniel Graf, and Paolo Penna. Truthful Mechanisms for Delivery with Agents. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems ATMOS'17, pages 2:1-2:17, 2017. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2017.2.
  10. Andreas Bärtschi and Thomas Tschager. Energy-Efficient Fast Delivery by Mobile Agents. In 21st International Symposium on Fundamentals of Computation Theory FCT'2017, pages 82-95, 2017. URL: http://dx.doi.org/10.1007/978-3-662-55751-8_8.
  11. Jérémie Chalopin, Shantanu Das, Matús Mihalák, Paolo Penna, and Peter Widmayer. Data Delivery by Energy-Constrained Mobile Agents. In 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics ALGOSENSORS'13, pages 111-122, 2013. URL: http://dx.doi.org/10.1007/978-3-642-45346-5_9.
  12. Jérémie Chalopin, Riko Jacob, Matús Mihalák, and Peter Widmayer. Data Delivery by Energy-Constrained Mobile Agents on a Line. In 41st International Colloquium on Automata, Languages, and Programming ICALP'14, pages 423-434, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_36.
  13. Jurek Czyzowicz, Krzysztof Diks, Jean Moussi, and Wojciech Rytter. Communication Problems for Mobile Agents Exchanging Energy. In 23rd International Colloquium on Structural Information and Communication Complexity SIROCCO'16, 2016. URL: http://dx.doi.org/10.1007/978-3-319-48314-6_18.
  14. Jurek Czyzowicz, Leszek Gasieniec, Konstantinos Georgiou, Evangelos Kranakis, and Fraser MacQuarrie. The Beachcombers' Problem: Walking and searching with mobile robots. Theoretical Computer Science, 608:201-218, 2015. URL: http://dx.doi.org/10.1016/j.tcs.2015.09.011.
  15. Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, and Evangelos Kranakis. Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds. In 19th European Symposium on Algorithms ESA'11, pages 701-712, 2011. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_59.
  16. Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Fraser MacQuarrie, and Dominik Pająk. Fence patrolling with two-speed robots. In 5th International Conference on Operations Research and Enterprise Systems ICORES'16, pages 229-241, 2016. URL: http://dx.doi.org/10.5220/0005687102290241.
  17. Erik D. Demaine, Mohammadtaghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveisgharan, and Morteza Zadimoghaddam. Minimizing movement. ACM Transactions on Algorithms, 5(3):1-30, 2009. See also SODA'07. URL: http://dx.doi.org/10.1145/1541885.1541891.
  18. Herbert Edelsbrunner. Algorithms in Combinatorial Geometry, volume 10 of EATCS Monographs on Theoretical Computer Science. Springer, Heidelberg, Germany, 1987. URL: http://dx.doi.org/10.1007/978-3-642-61568-9.
  19. Jack Edmonds and Ellis L. Johnson. Matching, euler tours and the chinese postman. Mathematical Programming, 5(1):88-124, 1973. URL: http://dx.doi.org/10.1007/BF01580113.
  20. Greg N. Frederickson, Matthew S. Hecht, and Chul E. Kim. Approximation Algorithms for Some Routing Problems. SIAM Journal on Computing, 7(2):178-193, 1978. See also FOCS'76. URL: http://dx.doi.org/10.1137/0207017.
  21. Woburn Collegiate Institute’s Programming Enrichment Group. Convex hull trick. PEGWiki, September 2016. URL: http://wcipeg.com/wiki/Convex_hull_trick.
  22. Riko Jacob. Dynamic planar convex hull. PhD thesis, Department of Computer Science, University of Aarhus, Denmark, 2002. BRICS Dissertation Series DS-02-3. URL: http://www.brics.dk/DS/Ref/BRICS-DS-Ref/BRICS-DS-Ref.html#BRICS-DS-02-3.
  23. David Lichtenstein. Planar Formulae and Their Uses. SIAM Journal on Computing, 11(2):329-343, 1982. URL: http://dx.doi.org/10.1137/0211025.
  24. Swiss Post. Swiss Post delivery robots in use by Jelmoli. Press release, August 2017. URL: https://www.post.ch/en/about-us/company/media/press-releases/2017/swiss-post-delivery-robots-in-use-by-jelmoli.
  25. Paolo Toth and Daniele Vigo, editors. The Vehicle Routing Problem. SIAM Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2001. ISBN: 0-89871-498-2. Google Scholar
  26. Elizabeth Weise. Amazon delivered its first customer package by drone. USA Today, December 2016. URL: http://usat.ly/2hNgf0y.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail