Publikation: Convexity Hierarchies in Grid Networks
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
Several algorithms for path planning in grid networks rely on graph decomposition to reduce the search space size; either by constructing a search data structure on the components, or by using component information for A* guidance. The focus is usually on obtaining components of roughly equal size with few boundary nodes each. In this paper, we consider the problem of splitting a graph into convex components. A convex component is characterized by the property that for all pairs of its members, the shortest path between them is also contained in it. Thus, given a source node, a target node, and a (small) convex component that contains both of them, path planning can be restricted to this component without compromising optimality. We prove that it is NP-hard to find a balanced node separator that splits a given graph into convex components. However, we also present and evaluate heuristics for (hierarchical) convex decomposition of grid networks that perform well across various benchmarks. Moreover, we describe how existing path planning methods can benefit from the computation of convex components. As one main outcome, we show that contraction hierarchies become up to an order of magnitude faster on large grids when the contraction order is derived from a convex graph decomposition.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
BLUM, Johannes, Ruoying LI, Sabine STORANDT, 2023. Convexity Hierarchies in Grid Networks. ICAPS 2023, the 33rd International Conference on Automated Planning and Scheduling. Prague, Czech Republic, 8. Juli 2023 - 13. Juli 2023. In: KOENIG, Sven, ed., Roni STERN, ed., Mauro VALLATI, ed.. Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling, 33(1). Palo Alto, CA: AAAI Press, 2023, pp. 52-60. ISSN 2334-0835. eISSN 2334-0843. ISBN 978-1-57735-881-7. Available under: doi: 10.1609/icaps.v33i1.27178BibTex
@inproceedings{Blum2023-07-01Conve-67658, year={2023}, doi={10.1609/icaps.v33i1.27178}, title={Convexity Hierarchies in Grid Networks}, isbn={978-1-57735-881-7}, issn={2334-0835}, publisher={AAAI Press}, address={Palo Alto, CA}, booktitle={Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling, 33(1)}, pages={52--60}, editor={Koenig, Sven and Stern, Roni and Vallati, Mauro}, author={Blum, Johannes and Li, Ruoying and Storandt, Sabine} }
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/67658"> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/67658"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-08-23T12:06:31Z</dc:date> <dc:creator>Blum, Johannes</dc:creator> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2023-08-23T12:06:31Z</dcterms:available> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:abstract>Several algorithms for path planning in grid networks rely on graph decomposition to reduce the search space size; either by constructing a search data structure on the components, or by using component information for A* guidance. The focus is usually on obtaining components of roughly equal size with few boundary nodes each. In this paper, we consider the problem of splitting a graph into convex components. A convex component is characterized by the property that for all pairs of its members, the shortest path between them is also contained in it. Thus, given a source node, a target node, and a (small) convex component that contains both of them, path planning can be restricted to this component without compromising optimality. We prove that it is NP-hard to find a balanced node separator that splits a given graph into convex components. However, we also present and evaluate heuristics for (hierarchical) convex decomposition of grid networks that perform well across various benchmarks. Moreover, we describe how existing path planning methods can benefit from the computation of convex components. As one main outcome, we show that contraction hierarchies become up to an order of magnitude faster on large grids when the contraction order is derived from a convex graph decomposition.</dcterms:abstract> <dcterms:issued>2023-07-01</dcterms:issued> <dcterms:title>Convexity Hierarchies in Grid Networks</dcterms:title> <dc:creator>Li, Ruoying</dc:creator> <dc:contributor>Blum, Johannes</dc:contributor> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:language>eng</dc:language> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:contributor>Li, Ruoying</dc:contributor> <dc:contributor>Storandt, Sabine</dc:contributor> <dc:creator>Storandt, Sabine</dc:creator> </rdf:Description> </rdf:RDF>