Geração de estados iniciais difíceis e solucionáveis para Sokoban

Abstract

Nesse trabalho lidamos com a tarefa de geração de estados difíceis e solucionáveis para problemas de busca em espaço de estados, mais especificamente para o domínio de Sokoban. O foco principal está na geração de estados iniciais, que tem aplicações em aprendizagem de máquina e humana, assim como na avaliação de sistemas de planejamento. Introduzimos métricas de dificuldade baseadas em base de dados de padrões, que aproximam métricas conhecidas por correlacionar com o tempo neces- sário para humanos resolverem problemas de busca em espaço de estados. Além disto, propomos o uso de informação estrutural de problemas de busca por meio do conceito de novidade para aumentar a exploração do espaço de estados enquanto é realizada a busca por estados iniciais. Nós então apresentamos um sistema cha- mado β que usa nossas métricas de dificuldade e a informação estrutural do espaço de busca do problema para guiar uma busca para a geração de estados iniciais. Resultados empíricos em labirintos de Sokoban mostram que β é capaz de superar substancialmente o atual estado da arte em geração de estados iniciais. Nossa abor- dagem gera estados iniciais com quase cinco vezes mais variáveis do que os métodos existentes. Os estados iniciais gerados por β têm comprimento de solução maior e são tão difíceis de serem solucionados por um solver especializado em problemas de Sokoban, quanto os estados iniciais projetados por especialistas humanos.

In this work we deal with the task of generating hard and solvable state-space search problems, with a focus on the generation of initial states for the domain of Sokoban. The automatic generation of initial states has applications in machine and human learning as well as in the evaluation of planning systems. We introduce hardness metrics based on pattern databases that approximate metrics known to correlate with the time required by humans to solve state-space search problems. We then propose a search algorithm that uses our hardness of metrics and the state-space structural information to generate and select hard initial states. We then present a system called β that uses our metrics and the structural information of the problem’s space to guide a search for generating hard and solvable initial states. Empirical results on Sokoban puzzle show that β substantially outperforms current methods for generating initial states. Our approach generates initial states with almost five times more variables than existing methods. The initial states generated by β have longer solution length and are as difficult to solve by a solver specializing in Sokoban problems as the initial states designed by human specialists.