The Simultaneous Maze Solving Problem

Funke, Stefan; Nusser, Andre; Storandt, Sabine

The Simultaneous Maze Solving Problem

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2017

Autor:innen

Funke, Stefan

Nusser, Andre

Storandt, Sabine

Sammlungen

Informatik und Informationswissenschaft

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.

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

Zitieren

ISO 690

FUNKE, 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>

URL der Originalveröffentl.

https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14617

Prüfdatum der URL

2018-09-07

Universitätsbibliographie

Nein