Mostrar el registro sencillo del ítem

dc.contributor.advisorBuriol, Luciana Saletept_BR
dc.contributor.authorPereira, André Grahlpt_BR
dc.date.accessioned2016-11-12T02:14:45Zpt_BR
dc.date.issued2016pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/149574pt_BR
dc.description.abstractIn this thesis, we study the class of moving-blocks problems. A moving-blocks problem consists of k movable blocks placed on a grid-square maze where there is an additional movable block called the man, which is the only block that can be moved directly. In particular, each moving-blocks problem is defined by the set of moves available, by the goal description and by what happens when the man attempts to move a block. Sokoban is the best known and researched moving-blocks problem. We study moving-blocks problems in theory and practice. We investigate the computational complexity of problems of moving-blocks. Prior to this thesis, most of the scientific literature addressed moving-blocks problems with PUSH moves only, in most of the cases proving that these problems are PSPACE-complete. We consider two sets of problems: PULL moves only, and PUSH and PULL moves combined. Our reductions are from Nondeterministic Constraint Logic. We prove that many problems with PULL moves only are PSPACE-complete. In addition, we prove that the entire set of PUSH and PULL moves is PSPACE-complete. Our contribution in this research line is to enhance the knowledge on the complexity landscape of moving-blocks problems. Our main objective in this thesis is to optimally solve moving-blocks problems with a focus on Sokoban. Methods based on heuristic search and abstraction heuristics such as pattern databases are the most effective approaches to optimally solve these problems. We make many contributions in this research line. We introduce novel heuristic functions using pattern databases with the idea of intermediate goal states. We propose a technique based on pattern databases to detect deadlocks. We propose tie-breaking rules that exploit the structure of the problem. Using these heuristic functions and tie-breaking rules we increase the number of optimally solved instances of Sokoban and other problems compared to previous methods.en
dc.description.abstractNesta tese, nós estudamos a classe de problemas de blocos-móveis. Um problema de blocos-móveis consiste em k blocos móveis dispostos em um labirinto em grade quadrangular onde há um bloco móvel adicional chamado de o homem, que é o único bloco que pode ser movido diretamente. Em particular, cada problema de blocos-móveis é definido pelo conjunto de movimentos disponíveis, pela descrição do objetivo e pelo o que acontece quando o homem tenta mover um bloco. Sokoban é o problema de blocos-móveis mais conhecido e pesquisado. Nós investigamos a complexidade computacional de problemas de blocos-móveis. Antes desta tese, a maior parte da literatura cientifica abordou problemas de blocos-móveis apenas com movimentos de EMPURRAR, na maioria dos casos provando que esses problemas são PSPACE-complete. Nós consideramos dois conjuntos de problemas: apenas movimentos de PUXAR, e movimentos de EMPURRAR e PUXAR combinados. Nossas reduções usam a Lógica de Restrições Não Determinística. Nós provamos que muitos problemas apenas com movimentos de PUXAR são PSPACE-complete. Além disso, nós provamos que o conjunto de problemas com movimentos de EMPURRAR e PUXAR é PSPACE-complete. A nossa contribuição nessa linha de pesquisa é aprimorar o conhecimento sobre o panorama da complexidade de problemas de blocos-móveis. Nosso principal objetivo com essa tese é resolver otimamente problemas de blocos-móveis com foco em Sokoban. Métodos baseados em busca heurística e heurísticas de abstrações como banco de dados de padrões são as abordagens mais efetivas para resolver otimamente esses problemas. Nós fazemos muitas contribuições nessa linha de pesquisa. Nós introduzimos novas funções heurísticas usando bancos de dados padrão com a ideia de estados objetivos intermediários. Propomos uma técnica baseada em bancos de dados padrão para detectar impasses. Propomos regras de desempate que exploram a estrutura do problema. Usando estas funções heurísticas e regras de desempate nós aumentamos o número de instâncias resolvidas de forma ótima de Sokoban e outros problemas em comparação com os métodos anteriores.pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.language.isoengpt_BR
dc.rightsOpen Accessen
dc.subjectHeuristic searchen
dc.subjectTeoria : Jogospt_BR
dc.subjectSingle-agent searchen
dc.subjectBanco : Dados orientados : Objetospt_BR
dc.subjectMoving-blocks problemen
dc.subjectSokobanen
dc.subjectPattern Databaseen
dc.subjectAbstraction heuristicen
dc.subjectComputational complexityen
dc.subjectNondeterministic constraint logicen
dc.titleSolving moving-blocks problemspt_BR
dc.title.alternativeResolvendo problemas de blocos movéis en
dc.typeTesept_BR
dc.contributor.advisor-coRitt, Marcus Rolf Peterpt_BR
dc.identifier.nrb001006106pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Informáticapt_BR
dc.degree.programPrograma de Pós-Graduação em Computaçãopt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2016pt_BR
dc.degree.leveldoutoradopt_BR


Ficheros en el ítem

Thumbnail
   

Este ítem está licenciado en la Creative Commons License

Mostrar el registro sencillo del ítem