Document Open Access Logo

Energy-Efficient Delivery by Heterogeneous Mobile Agents

Authors Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Daniel Graf, Jan Hackfeld, Paolo Penna

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.10.pdf
  • Filesize: 0.71 MB
  • 14 pages

Document Identifiers

Author Details

Andreas Bärtschi
Jérémie Chalopin
Shantanu Das
Yann Disser
Daniel Graf
Jan Hackfeld
Paolo Penna

Cite AsGet BibTex

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 Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.STACS.2017.10

Abstract

We consider the problem of delivering m messages between specified source-target pairs in an undirected graph, by k mobile agents initially located at distinct nodes of the graph. Each edge has a designated length and each agent consumes energy proportional to the distance it travels in the graph. We are interested in optimizing the total energy consumption for the team of agents. Unlike previous related work, we consider heterogeneous agents with different rates of energy consumption (weights w_i). To solve the delivery problem, agents face three major challenges: Collaboration (how to work together on each message), Planning (which route to take) and Coordination (how to assign agents to messages). We first show that the delivery problem can be 2-approximated without collaborating and that this is best possible, i.e., we show that the benefit of collaboration is 2 in general. We also show that the benefit of collaboration for a single message is 1 / log 2 which is approximately 1.44. Planning turns out to be NP-hard to approximate even for a single agent, but can be 2-approximated in polynomial time if agents have unit capacities and do not collaborate. We further show that coordination is NP-hard even for agents with unit capacity, but can be efficiently solved exactly if they additionally have uniform weights. Finally, we give a polynomial-time c-approximation for message delivery with unit capacities.
Keywords
  • message delivery
  • mobile agents
  • energy optimization
  • approximation algorithms

Metrics

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

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. 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 Series in Applied Mathematics). Princeton University Press, Princeton, NJ, USA, 2007. Google Scholar
  3. Per Austrin and Jakub Onufry Wojtaszczyk. ACM ICPC World Finals 2015 solution sketches. http://www.csc.kth.se/~austrin/icpc/finals2015solutions.pdf, 2015.
  4. A. Bärtschi, J. Chalopin, S. Das, Y. Disser, B. Geissmann, D. Graf, A. Labourel, and M. Mihalák. Collaborative Delivery with Energy-Constrained Mobile Robots. In 23rd International Colloquium on Structural Information and Communication Complexity SIROCCO'16, 2016. Google Scholar
  5. A. Bärtschi, J. Chalopin, S. Das, Y. Disser, B. Geissmann, D. Graf, A. Labourel, and M. Mihalák. Collaborative Delivery with Energy-Constrained Mobile Robots, arXiv preprint, 2016. URL: http://arxiv.org/abs/1608.08500.
  6. A. Bärtschi, J. Chalopin, S. Das, Y. Disser, D. Graf, J. Hackfeld, A. Labourel, and P. Penna. Energy-efficient Delivery by Heterogeneous Mobile Agents, arXiv preprint, 2016. URL: https://arxiv.org/abs/1610.02361.
  7. Davide Bilò, Yann Disser, Luciano Gualà, Matús Mihalák, Guido Proietti, and Peter Widmayer. Polygon-constrained motion planning problems. In 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics ALGOSENSORS'13, pages 67-82, 2013. URL: http://dx.doi.org/10.1007/978-3-642-45346-5_6.
  8. 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.
  9. 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.
  10. Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, February 1976. Google Scholar
  11. 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. Google Scholar
  12. Erik D. Demaine, Mohammadtaghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveisgharan, and Morteza Zadimoghaddam. Minimizing movement. ACM Transactions on Algorithms (TALG), 5(3):1-30, 2009. URL: http://dx.doi.org/10.1145/1541885.1541891.
  13. 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.
  14. Jack Edmonds and Richard M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM), 19(2):248-264, 1972. Google Scholar
  15. Robert W. Floyd. Algorithm 97: shortest path. Communications of the ACM, 5(6):345, 1962. Google Scholar
  16. P. Fraigniaud, L. Gasieniec, D. Kowalski, and A. Pelc. Collective tree exploration. In 6th Latin American Theoretical Informatics Symposium LATIN'04, pages 141-151, 2004. Google Scholar
  17. Greg N. Frederickson, Matthew S. Hecht, and Chul E. Kim. Approximation algorithms for some routing problems. In Proceedings of the 17th Annual Symposium on Foundations of Computer Science (FOCS), 1976. Google Scholar
  18. J. A. Hoogeveen. Analysis of christofides' heuristic: Some paths are more difficult than cycles. Operations Research Letters, 10(5):291-295, July 1991. URL: http://dx.doi.org/10.1016/0167-6377(91)90016-I.
  19. ACM ICPC. World Finals 2015 Problems, Task C: Catering. https://icpc.baylor.edu/worldfinals/problems, May 2015.
  20. ICPCNews. ACM ICPC 2015 problem catering. https://www.youtube.com/watch?v=WxCgcI18_d8, May 2015.
  21. Alon Itai, Christos H Papadimitriou, and Jayme Luiz Szwarcfiter. Hamilton paths in grid graphs. SIAM Journal on Computing, 11(4):676-686, 1982. Google Scholar
  22. Marek Karpinski, Michael Lampis, and Richard Schmied. New inapproximability bounds for tsp. Journal of Computer and System Sciences, 81(8):1665-1677, 2015. Google Scholar
  23. Joseph B. Kruskal, Jr. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7:48-50, 1956. Google Scholar
  24. Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955. Google Scholar
  25. Chung-Lun Li, S. Thomas McCormick, and David Simchi-Levi. The point-to-point delivery and connection problems: Complexity and algorithms. Discrete Applied Mathematics, 36(3):267-292, 1992. Google Scholar
  26. David Lichtenstein. Planar formulae and their uses. SIAM Journal on Computing, 11(2):329-343, 1982. URL: http://dx.doi.org/10.1137/0211025.
  27. Stephen Warshall. A theorem on boolean matrices. Journal of the ACM (JACM), 9(1):11-12, 1962. Google Scholar
  28. Pawel Winter. Steiner problem in networks: A survey. Networks, 17(2):129-167, 1987. URL: http://dx.doi.org/10.1002/net.3230170203.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact