1 Search Results for "Hamann, Heiko"


Document
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, and Mostafa Wahby

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)


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.

Cite as

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)


Copy BibTex To Clipboard

@InProceedings{hamann_et_al:LIPIcs.FUN.2018.22,
  author =	{Hamann, Heiko and Markarian, Christine and Meyer auf der Heide, Friedhelm and Wahby, Mostafa},
  title =	{{Pick, Pack, \& Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.22},
  URN =		{urn:nbn:de:0030-drops-88136},
  doi =		{10.4230/LIPIcs.FUN.2018.22},
  annote =	{Keywords: connected dominating set, online algorithm, competitive analysis, geometric graph, robot warehouse, recharging stations}
}
  • Refine by Author
  • 1 Hamann, Heiko
  • 1 Markarian, Christine
  • 1 Meyer auf der Heide, Friedhelm
  • 1 Wahby, Mostafa

  • Refine by Classification
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 competitive analysis
  • 1 connected dominating set
  • 1 geometric graph
  • 1 online algorithm
  • 1 recharging stations
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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