Publikation:

Convexity Hierarchies in Grid Networks

Lade...
Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2023

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen 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.27178

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)
004 Informatik

Schlagwörter

Classical planning techniques and analysis

Konferenz

ICAPS 2023, the 33rd International Conference on Automated Planning and Scheduling, 8. Juli 2023 - 13. Juli 2023, Prague, Czech Republic
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690BLUM, 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.27178
BibTex
@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>

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
Ja
Begutachtet
Diese Publikation teilen