The Simultaneous Maze Solving Problem

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

FUNKE, Stefan, Andre NUSSER, Sabine STORANDT, 2017. The Simultaneous Maze Solving Problem. Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17). San Francisco, Feb 4, 2017 - Feb 10, 2017. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence. Palo Alto, California:AAAI Publications, pp. 808-814

@inproceedings{Funke2017Simul-43310, title={The Simultaneous Maze Solving Problem}, url={https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14617}, year={2017}, address={Palo Alto, California}, publisher={AAAI Publications}, 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 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/rdf/resource/123456789/43310"> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:creator>Nusser, Andre</dc:creator> <dc:creator>Storandt, Sabine</dc:creator> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:contributor>Nusser, Andre</dc:contributor> <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> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:contributor>Funke, Stefan</dc:contributor> <dc:creator>Funke, Stefan</dc:creator> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/43310"/> <dc:contributor>Storandt, Sabine</dc:contributor> <dc:language>eng</dc:language> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-09-18T15:11:13Z</dcterms:available> <dcterms:issued>2017</dcterms:issued> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-09-18T15:11:13Z</dc:date> <dcterms:title>The Simultaneous Maze Solving Problem</dcterms:title> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


Browse

My Account