Les algorithmes permettant la création de stratégies efficaces pour la résolution d’ensemble de problèmeshétéroclites ont toujours été un des piliers de la recherche en Intelligence Artificielle. Dans cette optique,la planification de tâches a pour objectif de fournir à un système la capacité de raisonner pour interagiravec son environnement de façon autonome afin d’atteindre les buts qui lui ont été assignés. À partir d’unedescription de l’état initial du monde, des actions que le système peut exécuter, et des buts qu’il doit atteindre,un planificateur calcule une séquence d’actions dont l’exécution permet de faire passer l’état du monde danslequel évolue le système vers un état qui satisfait les buts qu’on lui a fixés. Le problème de planification esten général difficile à résoudre (PSPACE-difficile), cependant certaines propriétés des problèmes peuvent êtreautomatiquement extraites permettant ainsi une résolution efficace.Dans un premier temps, nous avons développé l’algorithme LMBFS (Landmark-based Meta Best-First Search).À contre-courant des planificateurs state-of-the-art, basés sur la recherche heuristique dans l’espace d’états,LMBFS est un algorithme qui réactualise la technique de décomposition des problèmes de planification baséssur les landmarks. Un landmark est un fluent qui doit être vrai à un certain moment durant l’exécutionde n’importe quel plan solution. L’algorithme LMBFS découpe le problème principal en un ensemble desous-problèmes et essaie de trouver une solution globale grâce aux solutions trouvées pour ces sous-problèmes.Dans un second temps, nous avons adapté un ensemble de techniques pour améliorer les performances del’algorithme. Enfin, nous avons testé et comparé chacune de ces méthodes permettant ainsi la création d’unplanificateur efficace. / The algorithms allowing on-the-fly computation of efficient strategies solving aheterogeneous set of problems has always been one of the greatest challengesfaced by research in Artificial Intelligence. To this end, classical planningprovides to a system reasoning capacities, in order to help it to interact with itsenvironment autonomously. Given a description of the world current state, theactions the system is able to perform, and the goal it is supposed to reach, a plannercan compute an action sequence yielding a state satisfying the predefined goal. Theplanning problem is usually intractable (PSPACE-hard), however some propertiesof the problems can be automatically extracted allowing the design of efficientsolvers.Firstly, we have developed the Landmark-based Meta Best-First Search (LMBFS)algorithm. Unlike state-of-the-art planners, usually based on state-space heuristicsearch, LMBFS reenacts landmark-based planning problem decomposition. Alandmark is a fluent appearing in each and every solution plan. The LMBFSalgorithm splits the global problem in a set of subproblems and tries to find aglobal solution using the solutions found for these subproblems. Secondly, wehave adapted classical planning techniques to enhance the performance of ourbase algorithm, making LMBFS a competitive planner. Finally, we have tested andcompared these methods.

A busca progressiva no espaço de estados é uma das abordagens mais populares de Planejamento Automatizado. O desempenho dos algoritmos de busca progressiva é influenciado pela heurística independente de domínio utilizada para guiá-lo. Nesse contexto, o foco do presente trabalho consiste em investigar técnicas de aprendizado de máquina supervisionadas que possibilitaram agregar à heurística do plano relaxado, comumente utilizada em abordagens atuais de planejamento, informações sobre o domínio em questão que viessem a ser úteis ao algoritmo de busca. Essas informações foram representadas por meio de um espaço de características do problema de planejamento e uma rede neural MLP foi aplicada para estimar uma nova função heurística para guiar a busca por meio de um processo de regressão não linear. Uma vez que o conjunto de características disponíveis para a construção da nova função heurística é grande, foi necessário a definição de um processo de seleção de características capaz de determinar qual conjunto de características de entrada da rede resultaria em melhor desempenho para o modelo de regressão. Portanto, para a seleção de características, aplicou-se uma abordagem de algoritmos genéticos. Como principal resultado, tem-se uma análise comparativa do desempenho entre a utilização da heurística proposta neste trabalho e a utilização da heurística do plano relaxado para guiar o algoritmo de busca na tarefa de planejamento. Para a análise empírica foram utilizados domínios de diferentes complexidades disponibilizados pela Competições Internacionais de Planejamento. Além dos resultados empíricos e análises comparativas, as contribuições deste trabalho envolvem o desenvolvimento de um novo planejador independente de domínio, denominado LearnInPlanner. Esse planejador utiliza a nova função heurística estimada por meio do processo de aprendizado e o algoritmo de Busca Gulosa para solucionar os problemas de planejamento. / The forward state-space search is one of the most popular Automated Planning approaches. The performance of forward search algorithms is affected by the domain-independent heuristic being used. In this context, the focus of this work consisted on investigating techniques of supervised machine learning that make possible to agregate to the relaxed plan heuristic, commonly used in current planning approaches, information about the domain which could be useful to the search algorithm. This information has been represented through a feature space of planning problem and a MLP neural network has been applied to estimate a new heuristic function for guiding the search through a non-linear regression process. Once the set of features available for the construction of the new heuristic function is large, it was necessary to define a feature selection process capable of determining which set of neural network input features would result in the best performance for the regression model. Therefore, for selecting features, an approach of genetic algorithms has been applied. As the main result, one has obtained a comparative performance analysis between the use of heuristic proposed in this work and the use of the relaxed plan heuristic to guide the search algorithm in the planning task. For the empirical analysis were used domains with different complexities provided by the International Planning Competitions. In addition to the empirical results and comparative analysis, the contributions of this work involves the development of a new domain-independent planner, named LearnInPlanner. This planner uses the new heuristic function estimated by the learning process and the Greedy Best-First search algorithm to solve planning problems.

A busca progressiva no espaço de estados é uma das abordagens mais populares de Planejamento Automatizado. O desempenho dos algoritmos de busca progressiva é influenciado pela heurística independente de domínio utilizada para guiá-lo. Nesse contexto, o foco do presente trabalho consiste em investigar técnicas de aprendizado de máquina supervisionadas que possibilitaram agregar à heurística do plano relaxado, comumente utilizada em abordagens atuais de planejamento, informações sobre o domínio em questão que viessem a ser úteis ao algoritmo de busca. Essas informações foram representadas por meio de um espaço de características do problema de planejamento e uma rede neural MLP foi aplicada para estimar uma nova função heurística para guiar a busca por meio de um processo de regressão não linear. Uma vez que o conjunto de características disponíveis para a construção da nova função heurística é grande, foi necessário a definição de um processo de seleção de características capaz de determinar qual conjunto de características de entrada da rede resultaria em melhor desempenho para o modelo de regressão. Portanto, para a seleção de características, aplicou-se uma abordagem de algoritmos genéticos. Como principal resultado, tem-se uma análise comparativa do desempenho entre a utilização da heurística proposta neste trabalho e a utilização da heurística do plano relaxado para guiar o algoritmo de busca na tarefa de planejamento. Para a análise empírica foram utilizados domínios de diferentes complexidades disponibilizados pela Competições Internacionais de Planejamento. Além dos resultados empíricos e análises comparativas, as contribuições deste trabalho envolvem o desenvolvimento de um novo planejador independente de domínio, denominado LearnInPlanner. Esse planejador utiliza a nova função heurística estimada por meio do processo de aprendizado e o algoritmo de Busca Gulosa para solucionar os problemas de planejamento. / The forward state-space search is one of the most popular Automated Planning approaches. The performance of forward search algorithms is affected by the domain-independent heuristic being used. In this context, the focus of this work consisted on investigating techniques of supervised machine learning that make possible to agregate to the relaxed plan heuristic, commonly used in current planning approaches, information about the domain which could be useful to the search algorithm. This information has been represented through a feature space of planning problem and a MLP neural network has been applied to estimate a new heuristic function for guiding the search through a non-linear regression process. Once the set of features available for the construction of the new heuristic function is large, it was necessary to define a feature selection process capable of determining which set of neural network input features would result in the best performance for the regression model. Therefore, for selecting features, an approach of genetic algorithms has been applied. As the main result, one has obtained a comparative performance analysis between the use of heuristic proposed in this work and the use of the relaxed plan heuristic to guide the search algorithm in the planning task. For the empirical analysis were used domains with different complexities provided by the International Planning Competitions. In addition to the empirical results and comparative analysis, the contributions of this work involves the development of a new domain-independent planner, named LearnInPlanner. This planner uses the new heuristic function estimated by the learning process and the Greedy Best-First search algorithm to solve planning problems.

In terms of classical planning, planners objectives are generate a sequence of actions that converts an initial conguration (state) into another state that attends a goal. Planning systems have been used in solving a variety of problems with success. However, no planner is capable of outperforming all the others when applied to distinct problems. Probabilistic planning is an extension of classical planning that works with stochastic environments. Just as in classical planning, several planners were proposed to solve probalistic planning problems. However, no planner is capable of outperform all others when applied to distinct problems. In this work we describe our approach that is capable of extracting features of a planning problem and determining a classical or probabilistic planner from a portfolio that can solve the problem. We use machine learning algorithms to determine the best planner from the porfolio that solves a problem. Our approach showed good results in the experiments. Our approach outperformed the best planners from a recent planning competition in both areas (classical and probabilistic planning). / Em termos de abordagem clássica, sistemas de planejamento ou planejadores concentramse em gerar automaticamente uma sequência de ações que transforma uma conguração (estado) inicial de objetos em outro estado em que um dado objetivo é satisfeito. Sistemas de planejamento foram utilizados para resolver uma variedade de problemas com sucesso. Apesar disso, nenhum planejador é melhor que todos os outros quando aplicados a problemas distintos. O planejamento probabilístico é uma extensão do planejamento clássico que trabalha sobre um ambiente não determinístico. Assim como no planejamento clássico, diversos planejadores foram propostos para resolver problemas, porém nenhum planejador é capaz de superar totalmente os outros em todos os problemas. Neste trabalho, descreve-se uma abordagem que consiste em extrair características do problema a ser resolvido e determinar, a partir de um conjunto de planejadores clássicos e probabilísticos, um que seja capaz de resolver o problema com eciência. Em nossa abordagem, são utilizados algoritmos de aprendizado de máquina para determinar o melhor planejador dentre o portfólio que resolve o problema. A seleção dos planejadores se mostrou eciente nos testes tendo mostrado bons resultados nos experimentos ao superar os planejadores de portfólio que conseguiram os melhores resultados nas competições de planejamento em ambas as áreas (planejamento clássico e probabilístico). / Mestre em Ciência da Computação

The field of classical planning deals with designing algorithms for generating plans or squences of actions that achieve specific goals. It involves representing a problem domain as a set of state variables, actions and goals, and then developing search algorithms that can explore the state of possible plans to find the one that satisfies the specified goal. Classical planning domains are often NP-hard, meaning that their worst-case complexity grows exponentially with the size of the problem. This means that as the number of state variables, actions and goals in the problem domain increases, the search space grows exponentially, making it very difficult to find a plan that satisfies the specified goal. This thesis is concerned with investigating these NP-hard domains, specifically by simplifying these domains into ones that have a polynomial solving time, creating a general policy of conditions and rules for which actions to take for the simplified domain, and then attempting to apply this policy onto the original domain. This creates a partial policy for the original domain, and the performance of this policy can be measured in order to judge its effectiveness. This can be explained as simplifying an intractable domain into a tractable one, creating a general policy for the tractable domain and then measuring its performance as a partial policy for the intractable domain.

Classical planning is the problem of nding a sequence of actions that take an agent from an initial state to a desired goal situation, assuming deter- ministic outcomes for actions and perfect information. Satis cing planning seeks to quickly nd low-cost solutions with no guarantees of optimality. The most e ective approach for satis cing planning has proved to be heuristic search using non-admissible heuristics. In this thesis, we introduce several such heuristics that are able to take into account costs on actions, and there- fore try to minimize the more general metric of cost, rather than length, of plans, and investigate their properties and performance. In addition, we show how the problem of planning with soft goals can be compiled into a classical planning problem with costs, a setting in which cost-sensitive heuristics such as those presented here are essential. / La plani caci on cl asica es el problema que consiste en hallar una secuencia de acciones que lleven a un agente desde un estado inicial a un objetivo, asum- iendo resultados determin sticos e informaci on completa. La plani caci on \satis cing" busca encontrar una soluci on de bajo coste, sin garant as de op- timalidad. La b usqueda heur stica guiada por heur sticas no admisibles es el enfoque que ha tenido mas exito. Esta tesis presenta varias heur sticas de ese g enero que consideran costes en las acciones, y por lo tanto encuentran soluciones que minimizan el coste, en lugar de la longitud del plan. Adem as, demostramos que el problema de plani caci on con \soft goals", u objetivos opcionales, se puede reducir a un problema de plani caci on clasica con costes en las acciones, escenario en el que heur sticas sensibles a costes, tal como las aqu presentadas, son esenciales.