Domain dependent heuristics and tie breakers : topics in automated planning

Abstract

Automated planning is an important general problem solving technique in Artificial Intelligence (AI). In planning, given a initial state of the world, a goal and a set of actions, we want to find a sequence of these actions leading us to the goal. What makes planning interesting is that we can model several different domains into planning tasks and solve them using a single method (e.g. Sokoban, logistic problems, security verification, etc). In this thesis, we will approach two different aspects of planning. First, we study domain-dependent heuristics in the context of the airport ground traffic problem and compare them to the state-of-the-art heuristics in literature. We present heuristics that over perform any other known method. Also, we show that simple domaindependent heuristics can still be superior than the state-of-the-art domain-independent ones. These proposed heuristics resulted in a conference paper published (CORRÊA; PEREIRA; RITT, 2016) previously. The second part of this work treats about tie-breakers for A search algorithm. In a more theoretical fashion, we study the current tie-breakers in literature (ASAI; FUKUNAGA, 2016; ASAI; FUKUNAGA, 2017) and show that all these techniques can mislead the search. We propose a new method based on operator (transition) cost adaptation that is proved to be the best possible tie-breaker in the perfect scenario. We also show that the methods proposed can solve more instances – i.e., increase coverage – than the “canonical” methods in literature. We believe that the analysis on domain-dependent heuristics and the tie-breaking strategies proposed are valuable not only to the automated planning community. Anyone interested in search, general AI topics, general problem solving or even just puzzles and games can benefit from this work.

Planejamento automatizado é uma importante técnica genérica de solução de problemas em Inteligência Artificial (IA). Em planejamento, dado um estado inicial do mundo, um objetivo e um conjunto de ações, queremos encontrar a sequência destas ações que nos leva para o objetivo. O que torna planejamento interessante é o fato de que podemos modelar diversos domínios em tarefas de planejamento e resolvê-los usando um único método (e.g. Sokoban, problemas de logística, verificação de segurança, etc.). Nesta tese, abordamos dois aspectos diferentes de planejamento. Primeiro, estudamos heurísticas dependentes de domínio no contexto do problema de tráfego de aeroportos em solo e comparamos estas com as principais heurísticas da literatura. Nós apresentamos heurísticas que superam qualquer outro método conhecido. Mostramos também que simples heurísticas dependentes de domínio ainda podem ser superiores as principais heurísticas independentes de domínio. As heurísticas propostas resultaram em um artigo publicado anteriormente em uma conferência (CORRÊA; PEREIRA; RITT, 2016). A segunda parte deste trabalho trata sobre regras de desempate em planejamento. De uma maneira mais teórica, estudamos os atuais métodos de desempate na literatura e mostramos que tais técnicas apresentam problemas. Nós propomos um novo método baseado na adaptação de custos que é provado ser o melhor possível. Também demonstramos que tais métodos propostos podem solucionar mais instâncias que os métodos padrões na literatura. Acreditamos que os resultados apresentados sobre heurísticas independentes de domínio e regras de desempate têm valor não só para a comunidade do planejamento automatizado. Qualquer um interessado em busca, IA em geral, soluções de problemas em geral ou até mesmo apenas em jogos pode se beneficiar deste trabalho.