The Simultaneous Maze Solving Problem

Lade...
Vorschaubild
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2017
Autor:innen
Funke, Stefan
Nusser, Andre
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
DOI (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
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence. Palo Alto, California: AAAI Publications, 2017, pp. 808-814
Zusammenfassung

A grid maze is a binary matrix where fields containing a 0 are accessible while fields containing a 1 are blocked. A movement sequence consists of relative movements up, down, left, right – moving to a blocked field results in non-movement. The simultaneous maze solving problem asks for the shortest movement sequence starting in the upper left corner and visiting the lower right corner for all mazes of size n × m (for which a path from the upper left to the lower right corner exists at all). We present a theoretical problem analysis, including hardness results and a cubic upper bound on the sequence length. In addition, we describe several approaches to practically compute solving sequences and lower bounds despite the high combinatorial complexity of the problem.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
conformant planning; maze; universal traversal sequence; solving sequence
Konferenz
Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), 4. Feb. 2017 - 10. Feb. 2017, San Francisco
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690FUNKE, Stefan, Andre NUSSER, Sabine STORANDT, 2017. The Simultaneous Maze Solving Problem. Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17). San Francisco, 4. Feb. 2017 - 10. Feb. 2017. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence. Palo Alto, California: AAAI Publications, 2017, pp. 808-814
BibTex
@inproceedings{Funke2017Simul-43310,
  year={2017},
  title={The Simultaneous Maze Solving Problem},
  url={https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14617},
  publisher={AAAI Publications},
  address={Palo Alto, California},
  booktitle={Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence},
  pages={808--814},
  author={Funke, Stefan and Nusser, Andre 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/43310">
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Nusser, Andre</dc:contributor>
    <dcterms:issued>2017</dcterms:issued>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:language>eng</dc:language>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/43310"/>
    <dc:creator>Funke, Stefan</dc:creator>
    <dc:contributor>Funke, Stefan</dc:contributor>
    <dc:creator>Nusser, Andre</dc:creator>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <dcterms:title>The Simultaneous Maze Solving Problem</dcterms:title>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-09-18T15:11:13Z</dcterms:available>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:abstract xml:lang="eng">A grid maze is a binary matrix where fields containing a 0 are accessible while fields containing a 1 are blocked. A movement sequence consists of relative movements up, down, left, right – moving to a blocked field results in non-movement. The simultaneous maze solving problem asks for the shortest movement sequence starting in the upper left corner and visiting the lower right corner for all mazes of size n × m (for which a path from the upper left to the lower right corner exists at all). We present a theoretical problem analysis, including hardness results and a cubic upper bound on the sequence length. In addition, we describe several approaches to practically compute solving sequences and lower bounds despite the high combinatorial complexity of the problem.</dcterms:abstract>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-09-18T15:11:13Z</dc:date>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
Prüfdatum der URL
2018-09-07
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