Mostrar registro simples

dc.contributor.advisorPereira, André Grahlpt_BR
dc.contributor.authorBoelter, Jean Persipt_BR
dc.date.accessioned2019-04-09T02:34:44Zpt_BR
dc.date.issued2018pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/190174pt_BR
dc.description.abstractIn this thesis, we present an approach for deadlock detection in Sokoban based on neural networks. Sokoban is a challenging state space problem in artificial intelligence due to many characteristics, being the presence of deadlocks one of them. A deadlock is a state reachable from the initial state which cannot reach any goal state. An informed search algorithm aims to find in a state space an ordered sequence of actions that transform the initial state into a goal state. Deadlock detection is essential to increase the performance of an informed search algorithm. Pattern databases are the current state of the art heuristic for deadlock detection in Sokoban. We present methods to generate a training set and train a neural network to detect deadlocks. Our approach has a similar performance to a pattern database. When compared to the standard heuristic function of Sokoban we solved two more instances while exploring an order of magnitude fewer states.en
dc.description.abstractNesta tese, apresentamos uma abordagem para detecção de deadlocks em Sokoban baseada em redes neurais. Sokoban é um problema de espaço de estados desafiador na inteligência artificial devido a muitas características, sendo a presença de deadlocks uma delas. Um deadlock é um estado alcançável a partir do estado inicial que não consegue atingir nenhum estado de objetivo. Um algoritmo de busca informada visa encontrar em um espaço de estados uma sequência ordenada de ações que transformam o estado inicial em um estado objetivo. A detecção de deadlocks é essencial para aumentar o desempenho de um algoritmo de busca informada. Pattern databases são a atual heurística estado da arte para detecção de deadlock em Sokoban. Apresentamos métodos para gerar um conjunto de treinamento e treinar uma rede neural para detectar deadlocks. Nossa abordagem tem um desempenho semelhante a pattern databases. Quando comparado com a função heurística padrão do Sokoban resolvemos duas instâncias a mais enquanto exploramos uma ordem de grandeza menos estados.pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.language.isoengpt_BR
dc.rightsOpen Accessen
dc.subjectSokobanen
dc.subjectRedes neuraispt_BR
dc.subjectDeadlocksen
dc.subjectHeuristic Searchen
dc.subjectNeural Networksen
dc.titleLearning deadlocks in sokobanpt_BR
dc.title.alternativeAprendendo Deadlocks em Sokoban pt
dc.typeTrabalho de conclusão de graduaçãopt_BR
dc.identifier.nrb001088740pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Informáticapt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2018pt_BR
dc.degree.graduationCiência da Computação: Ênfase em Ciência da Computação: Bachareladopt_BR
dc.degree.levelgraduaçãopt_BR


Thumbnail
   

Este item está licenciado na Creative Commons License

Mostrar registro simples