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

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

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 [10]. 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 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 Ω(log n log m) [14] for the related Online Set Cover problem [2], 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. © Heiko Hamann, Christine Markarian, Friedhelm Meyer auf der Heide, and Mostafa Wahby; licensed under Creative Commons License CC-BY 9th International Conference on Fun with Algorithms (FUN 2018).
Original languageEnglish
Title of host publication9th International Conference on Fun with Algorithms (FUN 2018)
EditorsHiro Ito, Stefano Leonardi, Linda Pagli, Giuseppe Prencipe
Number of pages13
Volume100
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Publication date01.06.2018
Pages221-2213
ISBN (Print)978-3-95977-067-5
DOIs
Publication statusPublished - 01.06.2018
Event9th International Conference on Fun with Algorithms - La Maddalena Island, Italy
Duration: 13.06.201815.06.2018
Conference number: 137010

Fingerprint

Dive into the research topics of 'Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets'. Together they form a unique fingerprint.

Cite this