Document Open Access Logo

Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets

Authors Heiko Hamann, Christine Markarian, Friedhelm Meyer auf der Heide, Mostafa Wahby

PDF
Thumbnail PDF

File

LIPIcs.FUN.2018.22.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Author Details

Heiko Hamann
  • Institute of Computer Engineering, University of Lübeck, Germany, https://www.iti.uni-luebeck.de
Christine Markarian
  • Heinz Nixdorf Institute, Paderborn University, Germany, https://www.uni-paderborn.de
Friedhelm Meyer auf der Heide
  • Heinz Nixdorf Institute, Paderborn University , Germany, https://www.uni-paderborn.de
Mostafa Wahby
  • Institute of Computer Engineering, University of Lübeck, Germany, https://www.iti.uni-luebeck.de

Cite As Get BibTex

Heiko Hamann, Christine Markarian, Friedhelm Meyer auf der Heide, and Mostafa Wahby. Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FUN.2018.22

Abstract

The modern warehouse is partially automated by robots. Instead of letting human workers walk into shelfs and pick up the required stock, big groups of autonomous mobile robots transport the inventory to the workers. Typically, these robots have an electric drive and need to recharge frequently during the day. When we scale this approach up, it is essential to place recharging stations strategically and as soon as needed so that all robots can survive. In this work, we represent a warehouse topology by a graph and address this challenge with the Online Connected Dominating Set problem (OCDS), an online variant of the classical Connected Dominating Set problem [Guha and Khuller, 1998]. We are given an undirected connected graph G = (V, E) and a sequence of subsets of V arriving over time. The goal is to grow a connected subgraph that dominates all arriving nodes and contains as few nodes as possible. We propose an O(log^2 n)-competitive randomized algorithm for OCDS in general graphs, where n is the number of nodes in the input graph. This is the best one can achieve due to Korman's randomized lower bound of Omega(log n log m) [Korman, 2005] for the related Online Set Cover problem [Alon et al., 2003], where n is the number of elements and m is the number of subsets. We also run extensive simulations to show that our algorithm performs well in a simulated warehouse, where the topology of a warehouse is modeled as a randomly generated geometric graph.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • connected dominating set
  • online algorithm
  • competitive analysis
  • geometric graph
  • robot warehouse
  • recharging stations

Metrics

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

References

  1. Sebastian Abshoff, Peter Kling, Christine Markarian, Friedhelm Meyer auf der Heide, and Peter Pietrzyk. Towards the price of leasing online. J. Comb. Optim., 32(4):1197-1216, 2016. URL: http://dx.doi.org/10.1007/s10878-015-9915-5.
  2. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The online set cover problem. In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 100-105. ACM, 2003. URL: http://dx.doi.org/10.1145/780542.780558.
  3. Farshad Arvin, Khairulmizam Samsudin, and Abdul Rahman Ramli. Swarm robots long term autonomy using moveable charger. In Future Computer and Communication, 2009. ICFCC 2009. International Conference on Future Computer and Communication, pages 127-130. IEEE, 2009. Google Scholar
  4. Manuele Brambilla, Eliseo Ferrante, Mauro Birattari, and Marco Dorigo. Swarm robotics: a review from the swarm engineering perspective. Swarm Intelligence, 7(1):1-41, 2013. URL: http://dx.doi.org/10.1007/s11721-012-0075-2.
  5. Alex Couture-Beil and Richard T. Vaughan. Adaptive mobile charging stations for multi-robot systems. In IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2009, pages 1363-1368. IEEE, 2009. Google Scholar
  6. Raffaello D'Andrea. Guest editorial: A revolution in the warehouse: A retrospective on Kiva systems and the grand challenges ahead. IEEE Transactions on Automation Science and Engineering, 9(4):638-639, 2012. Google Scholar
  7. Stephan Eidenbenz. Online Dominating Set and Variations on Restricted Graph Classes. Technical report, Department of Computer Science, ETH Zürich, 2002. Google Scholar
  8. Uriel Feige. A threshold of ln n for approximating set cover (preliminary version). In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 314-318. ACM, 1996. URL: http://dx.doi.org/10.1145/237814.237977.
  9. Michael R. Garey and David S. Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979. Google Scholar
  10. Sudipto Guha and Samir Khuller. Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374-387, 1998. URL: http://dx.doi.org/10.1007/PL00009201.
  11. Eric Guizzo. Three engineers, hundreds of robots, one warehouse. IEEE spectrum, 45(7):26-34, 2008. Google Scholar
  12. Andreas Kamagaew, Jonas Stenzel, Andreas Nettsträter, and Michael ten Hompel. Concept of cellular transport systems in facility logistics. In 5th International Conference on Automation, Robotics and Applications (ICARA), pages 40-45. IEEE, 2011. Google Scholar
  13. Balajee Kannan, Victor Marmol, Jaime Bourne, and M. Bernardine Dias. The autonomous recharging problem: Formulation and a market-based solution. In IEEE International Conference on Robotics and Automation (ICRA 2013), pages 3503-3510. IEEE, 2013. Google Scholar
  14. Simon Korman. On the use of randomization in the online set cover problem. In M.S. thesis, Weizmann Institute of Science, 2005. Google Scholar
  15. Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems. J. ACM, 41(5):960-981, 1994. URL: http://dx.doi.org/10.1145/185675.306789.
  16. Adam Meyerson. The parking permit problem. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pages 274-284. IEEE Computer Society, 2005. URL: http://dx.doi.org/10.1109/SFCS.2005.72.
  17. Joseph Naor, Debmalya Panigrahi, and Mohit Singh. Online node-weighted steiner tree and related problems. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 210-219. IEEE Computer Society, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.65.
  18. Giovanni Pini, Arne Brutschy, Gianpiero Francesca, Marco Dorigo, and Mauro Birattari. Multi-armed bandit formulation of the task partitioning problem in swarm robotics. In 8th Int. Conf. on Swarm Intelligence (ANTS), pages 109-120. Springer, 2012. Google Scholar
  19. Jonatan Schroeder, André Guedes, and Elias P. Duarte Jr. Computing the minimum cut and maximum flow of undirected graphs. Technical report, Federal University of Paraná, Department of Informatics, 2004. Google Scholar
  20. Peter R. Wurman, Raffaello D'Andrea, and Mick Mountz. Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI magazine, 29(1):9, 2008. Google Scholar
  21. Jiguo Yu, Nannan Wang, Guanghui Wang, and Dongxiao Yu. Connected dominating sets in wireless ad hoc and sensor networks - A comprehensive survey. Computer Communications, 36(2):121-134, 2013. URL: http://dx.doi.org/10.1016/j.comcom.2012.10.005.
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 About DROPS Imprint Privacy Contact