The thesis of this dissertation is that automating domain remodeling in AI planning using macro operators and making remodeling more flexible and applicable can improve the planning performance and can enrich planning. In this dissertation, we present three novel ideas: (1) we present an instance-specific domain remodeling framework, (2) we recast the planning domain remodeling with macros as a parameter optimization problem, and (3) we combine two domain remodeling approaches in the instance-specific remodeling context. In the instance-specific domain remodeling, we choose the best macro-augmented domain model for every incoming problem instance using a predictor that relies on previously solved problem instances to estimate the macros to be added the domain. Training the predictor is achieved off-line based on the observed relation between the instance features and the planner performance in the macro-augmented domain models. On-line, the predictor is used to find the best remodeling of the domain based on the problem instance features. Our empirical results over a number of standard benchmark planning domains demonstrate that our predictors can speed up the fixed-remodeling method that chooses the best set of macros by up to 2.5 times. The results also show that there is a large room for improving the performance using instance-specific over fixed remodeling approaches. The second idea is recasting the domain remodeling with macros as a parameter optimization. We show that this remodeling approach can outperform standard macro learning tools, and that it can significantly speed up the domain evaluation preprocessing required to train the predictors in instance-specific remodeling, while maintaining similar performance. The final idea applies macro addition and operator removal to the instance-specific domain remodeling. While maintaining an acceptable probability of solubility preservation, we build a predictor that adds macros and removes original operators based on the instance’s features. The results show that this new remodeling significantly outperforms the macro-only fixed remodeling, and that it is better than the fixed domain models in a number of domains.

The thesis of this dissertation is that automating domain remodeling in AI planning using macro operators and making remodeling more flexible and applicable can improve the planning performance and can enrich planning. In this dissertation, we present three novel ideas: (1) we present an instance-specific domain remodeling framework, (2) we recast the planning domain remodeling with macros as a parameter optimization problem, and (3) we combine two domain remodeling approaches in the instance-specific remodeling context. In the instance-specific domain remodeling, we choose the best macro-augmented domain model for every incoming problem instance using a predictor that relies on previously solved problem instances to estimate the macros to be added the domain. Training the predictor is achieved off-line based on the observed relation between the instance features and the planner performance in the macro-augmented domain models. On-line, the predictor is used to find the best remodeling of the domain based on the problem instance features. Our empirical results over a number of standard benchmark planning domains demonstrate that our predictors can speed up the fixed-remodeling method that chooses the best set of macros by up to 2.5 times. The results also show that there is a large room for improving the performance using instance-specific over fixed remodeling approaches. The second idea is recasting the domain remodeling with macros as a parameter optimization. We show that this remodeling approach can outperform standard macro learning tools, and that it can significantly speed up the domain evaluation preprocessing required to train the predictors in instance-specific remodeling, while maintaining similar performance. The final idea applies macro addition and operator removal to the instance-specific domain remodeling. While maintaining an acceptable probability of solubility preservation, we build a predictor that adds macros and removes original operators based on the instance’s features. The results show that this new remodeling significantly outperforms the macro-only fixed remodeling, and that it is better than the fixed domain models in a number of domains.

Classical planning is the problem of finding a sequence of actions for achieving a goal from an initial state assuming that actions have deterministic effects. The most effective approach for finding such plans is based on heuristic search guided by heuristics extracted automatically from the problem representation. In this thesis, we introduce alternative approaches for performing inference over the structure of planning problems that do not appeal to heuristic functions, nor to reductions to other formalisms such as SAT or CSP. We show that many of the standard benchmark domains can be solved with almost no search or a polynomially bounded amount of search, once the structure of planning problems is taken into account. In certain cases we can characterize this structure in terms of a novel width parameter for classical planning. / Los problemas en planificación clásica consisten en encontrar la secuencia de acciones que lleve a un agente a su objetivo desde un estado inicial, asumiendo que los efectos de las acciones son determinísticos. El enfoque más efectivo para encontrar dichos planes es la búsqueda heurística, extrayendo de la representación del problema de forma automática heurísticas que guien la búsqueda. En esta tesis, introducimos enfoques alternativos para realizar inferencias sobre la estructura del los problemas de planificación, sin apelar a funciones heurísticas, reducciones a SAT o CSP. Demostramos que la mayoría de problemas estándares pueden ser resueltos casi sin búsqueda o con una cantidad de búsqueda polinomialmente limitada, en algunos casos, caracterizando la estructura de los problemas en término de un nuevo parámetro de complejidad para la planificación clásica.

This thesis deals with the knowledge engineering for Automated Planning. The concept of state variables has been recently used with benefits for representation of planning problems. In this thesis the same concept is used in a novel formalism for planning domain and problem modeling. A proof-of-concept knowledge modeling tool is developed based on the new formalism. This tool is then used for modeling of example classical planning domain to show its capabilities. The export to standard domain modeling language is also implemented in the tool in order to provide connection to existing planning systems.

In this thesis I describe a method where an experience manager chooses actions for non-player characters (NPCs) in intelligent interactive narratives through story graph representation and pruning. The space of all stories can be represented as a story graph where nodes are states and edges are actions. By shaping the domain as a story graph, experience manager decisions can be made by pruning edges. Starting with a full graph, I apply a set of pruning strategies that will allow the narrative to be finishable, NPCs to act believably, and the player to be responsible for how the story unfolds. By never pruning player actions, the experience manager can accommodate any player choice. This experience management technique was first implemented on a training simulation, where participants’ performance improved over repeated sessions. This technique was also employed on an adventure game where players generally found the NPCs’ behaviors to be more believable than the control.

We have designed a simulation that can be used to train police officers. Digital simulations are more cost-effective than a human role play. Use of force decisions are complex and made quickly, so there is a need for better training and innovative methods. Using this simulation, we are measuring the degree of presence that a human experience in a virtual environment. More presence implies better training. Participants are divided into two groups in which one group performs the experiment using a screen, keyboard, and mouse, and another uses virtual reality controls. In this experiment, we use subjective measurements and physiological measurements. We offer a questionnaire to participants before and after play. We also record the participants change in heart rate, skin conductivity and skin temperature using Empatica device. By comparing the data collected from both groups, we prove that people experience more presence in the virtual environment.

La planification automatique est un domaine de recherche de l’Intelligence Artificielle qui vise à calculer automatiquement une séquence d’actions menant d’un état initial donné à un but souhaité. Cependant, résoudre des problèmes réalistes est généralement difficile car trouver un chemin solution peut demander d’explorer un nombre d’états croissant exponentiellement avec le nombre de variables. Pour faire face à cette explosion combinatoire, les algorithmes performants ont recours aux heuristiques ou à des solutions hiérarchiques, décomposant le problème en sous-problèmes plus petits et plus simples. Dans une grande majorité des cas, le planificateur doit prendre en compte un certain nombre de contraintes telles que des phases d’actions prédéfinies ou des protocoles. Ces contraintes aident à résoudre le problème en élaguant un grand nombre de branches de l’arbre de recherche. Nous proposons alors une nouvelle méthode pour modéliser et résoudre des problèmes de planification déterministe en se basant sur une approche hiérarchique et heuristique. Nous nous sommes inspirés des formalismes de programmation structurée afin de fournir à l’utilisateur un cadre de travail plus intuitif pour la modélisation des domaines de planification hiérarchique. D’autre part, nous avons proposé un algorithme de planification capable d’exploiter ce formalisme et composer des stratégies à différents niveaux de granularité, ce qui lui permet de planifier rapidement une stratégie globale, tout en étant en mesure de pallier aux difficultés rencontrées à plus bas niveau. Cet algorithme a fait ses preuves face au principal planificateur HTN, SHOP2, sur des problèmes de planification classique. / Automated planning is a field of Artificial Intelligence which aims at automatically computing a sequence of actions that lead to some goals from a given initial state. However, solving realistic problems is challenging because finding a solution path may require to explore an exponential number of states with regard to the number of state variables. To cope with this combinatorial explosion, efficient algorithms use heuristics, which guide the search towards optimistic or approximate solutions. Remarkably, hierarchical methods iteratively decompose the planning problem into smaller and much simpler ones. In a vast majority of problems, the planner must deal with constraints, such as multiple predefined phases or protocols. Such constraints generally help solving the planning problem, because they prune lots of search paths where these constraints do not hold. In this thesis, we assume that these constraints are known and given to the planner. We thus propose a new method to model and solve a deterministic planning problem, based on a hierarchical and heuristic approach and taking advantage of these constraints. We inspired ourselves from structured programming formalisms in order to offer a more intuitive modeling framework in the domain of hierarchical planning to the user. We also proposed a planning algorithm able to exploit this formalism and build strategies at various levels of granularity, thus allowing to plan quickly a global strategy, while still being able to overcome the difficulties at lower level. This algorithm showed its performances compared with the main HTN planner, SHOP2, on classical planning problems.

Many contemporary computer games can be described as dynamic real-time simulations inhabited by autonomous intelligent virtual agents (IVAs) where most of the environment structure is immutable and navigating through the environment is one of the most common activities. Though controlling the behaviour of such agents seems perfectly suited for action planning techniques, planning is not widely adopted in existing games. This paper attempts to answer the question whether the current academic planning technology is ready for integration to existing games and under which conditions. The paper compares reactive techniques to classical planning in handling the action selection problem for IVAs in game-like environments. Several existing classical planners that occupied top positions in the International Planning Competition were connected to the virtual environment of Unreal Development Kit via the Pogamut platform. Performance of IVAs employing those planners and IVAs with reactive architecture was measured on a class of game like test environments under different levels of external interference. It was shown that agents employing classical planning outperform reactive agents only if the size of the planning problem is small or if the environment changes are either hostile to the agent or not very frequent.

Conformant planning is the problem of finding a sequence of actions for achieving a goal in the presence of uncertainty in the initial state and state transitions. While few practical problems are purely conformant, the ability to find conformant plans is needed in planning with observations where conformant situations are an special case and where relaxations into conformant planning yield useful heuristics. In this dissertation, we introduce new formulations for tackling the conformant planning problem with deterministic actions using translations. On the one hand, we propose a translation in propositional logic and two schemes for obtaning conformant plans for it, one based on boolean operations of projection and model counting, the other based on projection and satisfiability. On the other hand, we introduce translations of the conformant planning problem into classical problems that are solved by a modern and effective classical planner. We analyze the formal properties of the translations into classical planning and evaluate the performance of the resulting conformant planners. / La planificación conformante es el problema de encontrar una secuencia de acciones para lograr un objetivo en presencia de información incompleta sobre el estado inicial y en las transiciones entre estados. Aunque pocos problemas son de carácter puramente conformante, la posibilidad de encontrar planes conformantes es necesaria en planificación con observaciones, donde las situaciones conformantes son un caso particular, y donde las relajaciones a planificación conformante dan heurísticas útiles. En esta tesis atacamos el problema de la planificación conformante con acciones determinísticas mediante dos formulaciones basadas en traducciones. Por un lado, proponemos una traducción a lógica proposicional y dos esquemas para obtener planes conformantes a partir de ésta, uno basado en operaciones booleanas de projección y conteo de modelos, y otro basado en projección y satisfacción proposicional. Por otro lado, introducimos traducciones que permiten transformar un problema de planificación conformante en un problema de planificación clásica que es luego resuelto usando planificadores clásicos. También analizamos las propiedades formales de las traducciones y evaluamos el rendimiento de los planificadores obtenidos.

ITSs (Intelligent Tutoring Systems) provide a way of addressing some of the issues that the more traditional CAI (Computer Aided Instruction) systems do not address - the individual learning needs and individual learning abilities and levels of users - so that the user is in control of their learning experience. An ITS needs to be able to provide an explanation, for a real world situation, that successfully meets the needs of the user. To ensure relevant explanation content requires the ITS be based on sound planning principles and tutoring knowledge as well as knowledge of the domain and the user. To ensure a coherent explanation structure requires that the tutoring knowledge be applied with full recognition of the knowledge of the domain and the user. For a model of the user's knowledge to be effective, the system should be able to use it to enhance the flexibility and responsiveness of explanations generated. A user model should guide the generation of explanations so they are pitched at the correct level of the user's existing knowledge; models should be able to actively support the needs of the user so that the user's efforts in seeking out information are minimised. The aim of this research is to generate effective, flexible and responsive explanations, in educational software systems, through developing better explanation facilities than exist in currently available ITS software. In achieving this aim, I am advancing research into dialogue planning and user modelling. The explanation facilities described meet the requirements of an explanation that is tailored to the user's needs, a sound theory from which particular explanations are constructed, and a user model that can accurately represent the behaviour and beliefs of the user. My research contributions include explicitly and formally representing discourse planning / reasoning, from both the user's view and the tutor's view so that they can be clearly understood and represented in the ITS. More recent planners have adopted approaches that can be characterised as using adaptations of the classical planning approach, with informally specified planning algorithms and planning languages. Without clear, explicit and full descriptions of actions and the planning algorithm we can not be certain of the plans that such planners produce. I adopt a theoretically rigorous approach based on classical planning theory - the actions available to the planner, the planning language and algorithm should be explicitly represented to ensure that plans are complete and consistent. Classical regression planning uses dynamic planning thus enabling the system to be flexible in a variety of situations and providing the responsiveness required for an ITS. I take a theoretically rigorous approach in constructing a well specified model of discourse, building upon existing research in the area. I present a tutoring module that is able to find a way to motivate the user to take a recommended action, by relating the action to the user's goals, and that is able to reason about the text structure to generate an effective explanation - putting together several clauses of text whilst maintaining coherency. As part of developing such constructs for motivating, enabling and recommending, as well as constructs for structuring text, I use a pedagogic model based on the principled approach of (i) advising the user to take an action (ii) motivating the user to want to take the action and (iii) ensuring the user knows how to do the action. I take a clear and realistic approach to user modelling, making explicit models of the user's behaviour and beliefs. I adopt a theoretically rigorous approach, formally distinguishing between the user's reasoning and their actions, so they can be focused on separately. Formally making this distinction, more easily enables models of the user's reasoning to be tailored to the individual user. To enable the tutor to consider the full impact on the user, of the information to be delivered to the user, I use different plan spaces. I explicitly identify the different perspectives of the user and the tutor so that they can be focused on separately to generate an explanation that is tailored to the user. In my approach, reasoning about the user's skills, rules and knowledge is independent from reasoning about those of the tutor.