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

Lade...
Vorschaubild
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2018
Autor:innen
Markarian, Christine
Meyer auf der Heide, Friedhelm
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Bookpart
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
ITO, Hiro, ed., Stefano LEONARDI, ed., Linda PAGLI, ed. and others. FUN 2018 : 9th International Conference on Fun with Algorithms. Wadern: Schloss Dagstuhl : Leibniz-Zentrum fuer Informatik, 2018, 22. Leibniz International Proceedings in Informatics (LIPIcs). 100. eISSN 1868-8969. ISBN 978-3-95977-067-5. Available under: doi: 10.4230/LIPIcs.FUN.2018.22
Zusammenfassung

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.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
connected dominating set, online algorithm, competitive analysis, geometric graph, robot warehouse, recharging stations
Konferenz
FUN 2018 : 9th International Conference on Fun with Algorithms, 13. Juni 2018 - 15. Juni 2018, La Maddalena, Italy
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690HAMANN, Heiko, Christine MARKARIAN, Friedhelm MEYER AUF DER HEIDE, Mostafa WAHBY, 2018. Pick, Pack, & Survive : Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets. FUN 2018 : 9th International Conference on Fun with Algorithms. La Maddalena, Italy, 13. Juni 2018 - 15. Juni 2018. In: ITO, Hiro, ed., Stefano LEONARDI, ed., Linda PAGLI, ed. and others. FUN 2018 : 9th International Conference on Fun with Algorithms. Wadern: Schloss Dagstuhl : Leibniz-Zentrum fuer Informatik, 2018, 22. Leibniz International Proceedings in Informatics (LIPIcs). 100. eISSN 1868-8969. ISBN 978-3-95977-067-5. Available under: doi: 10.4230/LIPIcs.FUN.2018.22
BibTex
@inproceedings{Hamann2018-06-04Survi-59865,
  year={2018},
  doi={10.4230/LIPIcs.FUN.2018.22},
  title={Pick, Pack, & Survive : Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets},
  number={100},
  isbn={978-3-95977-067-5},
  publisher={Schloss Dagstuhl : Leibniz-Zentrum fuer Informatik},
  address={Wadern},
  series={Leibniz International Proceedings in Informatics (LIPIcs)},
  booktitle={FUN 2018 : 9th International Conference on Fun with Algorithms},
  editor={Ito, Hiro and Leonardi, Stefano and Pagli, Linda},
  author={Hamann, Heiko and Markarian, Christine and Meyer auf der Heide, Friedhelm and Wahby, Mostafa},
  note={Article Number: 22}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/59865">
    <dcterms:abstract xml:lang="eng">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.</dcterms:abstract>
    <dcterms:title>Pick, Pack, &amp; Survive : Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets</dcterms:title>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-01-20T13:11:10Z</dcterms:available>
    <dc:creator>Markarian, Christine</dc:creator>
    <dc:language>eng</dc:language>
    <dc:contributor>Hamann, Heiko</dc:contributor>
    <dc:creator>Meyer auf der Heide, Friedhelm</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-01-20T13:11:10Z</dc:date>
    <dcterms:issued>2018-06-04</dcterms:issued>
    <dc:creator>Hamann, Heiko</dc:creator>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Wahby, Mostafa</dc:contributor>
    <dc:contributor>Meyer auf der Heide, Friedhelm</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:rights>terms-of-use</dc:rights>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/59865/1/Hamann_2-1r10n989svqfn7.pdf"/>
    <dc:contributor>Markarian, Christine</dc:contributor>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/59865/1/Hamann_2-1r10n989svqfn7.pdf"/>
    <dc:creator>Wahby, Mostafa</dc:creator>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/59865"/>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
Begutachtet
Diese Publikation teilen