abstract: Automated planning addresses the problem of generating a sequence of actions that enable a set of agents to achieve their goals.This work investigates two important topics from the field of automated planning, namely model-lite planning and multi-agent planning. For model-lite planning, I focus on a prominent model named Annotated PDDL and it's related application of robust planning. For this model, I try to identify a method of leveraging additional domain information (available in the form of successful plan traces). I use this information to refine the set of possible domains to generate more robust plans (as compared to the original planner) for any given problem. This method also provides us a way of overcoming one of the major drawbacks of the original approach, namely the need for a domain writer to explicitly identify the annotations. For the second topic, the central question I ask is ``{\em under what conditions are multiple agents actually needed to solve a given planning problem?}''. To answer this question, the multi-agent planning (MAP) problem is classified into several sub-classes and I identify the conditions in each of these sub-classes that can lead to required cooperation (RC). I also identify certain sub-classes of multi-agent planning problems (named DVC-RC problems), where the problems can be simplified using a single virtual agent. This insight is later used to propose a new planner designed to solve problems from these subclasses. Evaluation of this new planner on all the current multi-agent planning benchmarks reveals that most current multi-agent planning benchmarks only belong to a small subset of possible classes of multi-agent planning problems. / Dissertation/Thesis / Masters Thesis Computer Science 2016

In dynamic domains, the state of the world may change in unexpected ways during the generation or execution of plans. Regardless of the cause of such changes, they raise the question of whether they interfere with ongoing planning efforts. Unexpected changes during plan generation may invalidate the current planning effort, while discrepancies between expected and actual state of the world during execution may render the executing plan invalid or sub-optimal, with respect to previously identified planning objectives. In this thesis we develop a general monitoring technique that can be used during both plan generation and plan execution to determine the relevance of unexpected changes and which supports recovery. This way, time intensive replanning from scratch in the new and unexpected state can often be avoided. The technique can be applied to a variety of objectives, including monitoring the optimality of plans, rather then just their validity. Intuitively, the technique operates in two steps: during planning the plan is annotated with additional information that is relevant to the achievement of the objective; then, when an unexpected change occurs, this information is used to determine the relevance of the discrepancy with respect to the objective. We substantiate the claim of broad applicability of this relevance-based technique by developing four concrete applications: generating optimal plans despite frequent, unexpected changes to the initial state of the world, monitoring plan optimality during execution, monitoring the execution of near-optimal policies in stochastic domains, and monitoring the generation and execution of plans with procedural hard constraints. In all cases, we use the formal notion of regression to identify what is relevant for achieving the objective. We prove the soundness of these concrete approaches and present empirical results demonstrating that in some contexts orders of magnitude speed-ups can be gained by our technique compared to replanning from scratch.

In dynamic domains, the state of the world may change in unexpected ways during the generation or execution of plans. Regardless of the cause of such changes, they raise the question of whether they interfere with ongoing planning efforts. Unexpected changes during plan generation may invalidate the current planning effort, while discrepancies between expected and actual state of the world during execution may render the executing plan invalid or sub-optimal, with respect to previously identified planning objectives. In this thesis we develop a general monitoring technique that can be used during both plan generation and plan execution to determine the relevance of unexpected changes and which supports recovery. This way, time intensive replanning from scratch in the new and unexpected state can often be avoided. The technique can be applied to a variety of objectives, including monitoring the optimality of plans, rather then just their validity. Intuitively, the technique operates in two steps: during planning the plan is annotated with additional information that is relevant to the achievement of the objective; then, when an unexpected change occurs, this information is used to determine the relevance of the discrepancy with respect to the objective. We substantiate the claim of broad applicability of this relevance-based technique by developing four concrete applications: generating optimal plans despite frequent, unexpected changes to the initial state of the world, monitoring plan optimality during execution, monitoring the execution of near-optimal policies in stochastic domains, and monitoring the generation and execution of plans with procedural hard constraints. In all cases, we use the formal notion of regression to identify what is relevant for achieving the objective. We prove the soundness of these concrete approaches and present empirical results demonstrating that in some contexts orders of magnitude speed-ups can be gained by our technique compared to replanning from scratch.

Submitted by Pedro Henrique Rodrigues (pedro.henriquer@ufpe.br) on 2015-03-05T19:29:15Z No. of bitstreams: 2 phd-thesis-vfinal-rasd.pdf: 2993974 bytes, checksum: a924d1ac8059a7b4a6c2775d60d5a742 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-05T19:29:15Z (GMT). No. of bitstreams: 2 phd-thesis-vfinal-rasd.pdf: 2993974 bytes, checksum: a924d1ac8059a7b4a6c2775d60d5a742 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2012-03-13 / Service Composition is one of the most important features offered by Service Oriented Computing. The composition allows a new service to be created through the reuse of existing ones. The process of creating a composition involves discovering the necessary services and combining them in an appropriate manner using specific languages and tools. This process, however, is still carried out mainly by hand. Considering the dynamic nature of distributed services, manual composition may become too complex, affecting the productivity gains provided by reuse. Proposals to fully or partially automate this process already exist, most of them based on Automated Planning algorithms borrowed from Artificial Intelligence. Although functional, these approaches have practical problems that hinder their effective implementation in production scenarios. In this Thesis, we addressed some of the practical problems of automated composition, starting with the need for formal descriptions of services. These formal descriptions are necessary for the composition algorithms, however, are rarely available from services. This issue was addressed by means of reverse engineering a repository of service compositions. By analyzing how the services were related to each other in the compositions, it was possible to obtain the necessary information for the algorithms to work. We also evaluated the quality of the compositions generated by the algorithms and their similarity with respect to compositions created manually. Automated Planning algorithms from the literature have been modified in order to generate solutions closer to those expected by the developer. Finally, the composition algorithms were adapted to accept incomplete specifications, thus allowing the developer to obtain a solution even not knowing a priori all the composition details. Comparisons with automated planning tools were conducted in order to ascertain the effectiveness of the algorithms. The results show that the automated composition, as presented in the Thesis, can be an invaluable tool to the service developer.

Automated planning is a branch of AI that addresses the problem of generating a course of action to achieve a specified objective, given an initial state of the world. It is an area that is central to the development of intelligent agents and autonomous robots. In the last decade, automated planning has seen significant progress in terms of scalability, much of it achieved by the development of heuristic search approaches. Many of these advances, are only immediately applicable to so-called classical planning tasks. However, there are compelling applications of planning that are non-classical. An example is the problem of web service composition, in which the objective is to automatically compose web artifacts to achieve the objective of a human user. In doing so, not only the hard goals but also the \emph{preferences} of the user---which are usually not considered in the classical model---must be considered. % Also, the automated composition %should deal with abstract representations of the web %artifacts---which may also not adjust to the classical model. In this thesis we show that many of the most successful advances in classical planning can be leveraged for solving compelling non-classical problems. In particular, we focus on the following non-classical planning problems: planning with temporally extended goals; planning with rich, temporally extended preferences; planning with procedural control, and planning with procedural programs that can sense the environment. We show that to efficiently solve these problems we can use a common approach: reformulation. For each of these planning tasks, we propose a reformulation algorithm that generates another, arguably simpler instance. Then, if necessary, we adapt existing techniques to make the reformulated instance solvable efficiently. In particular, we show that both the problems of planning with temporally extended goals and with procedural control can be mapped into classical planning. Planning with rich user preferences, even after reformulation, cannot be mapped into classical planning and thus we develop specialized heuristics, based on existing heuristics, together with a branch-and-bound algorithm. Finally, for the problem of planning with programs that sense, we show that under certain conditions programs can be reduced to simple operators, enabling the use of a variety of existing planners. In all cases, we show experimentally that the reformulated problems can be solved effectively by either existing planners or by our adapted planners, outperforming previous approaches.

Automated planning in computer science consists of finding a sequence of actions leading from an initial state to a goal state. People who have expert knowledge of the specific problem domain work with experts in automated planning to define the domain states and actions. This knowledge engineering required to create complete and correct domain descriptions for planning problems is often very costly and difficult. Our goal with incomplete planning is to allow people to program domains without the need for planning experts. Throughout the process of instruction of intelligent systems, teachers can often leave out whole procedures and aspects of action descriptions. In such cases, the alternative to making domains complete is to plan around the incompleteness. That is, given knowledge of the possible action descriptions, we seek out plans that will succeed despite any incompleteness in the domain formulation. A state in a domain consists of a set of propositions that can be either true or false. Actions in a domain require specific propositions to be true for the action to occur. Actions then add and remove propositions from the state to create a subsequent state. A valid plan consists of a sequence of actions that, starting with the initial state, change to match the goal state. An incomplete domain contains the same qualities as a complete domain, with the additional abilities of actions to possibly require a proposition to be true to initiate the action, as well as possibly adding and possibly removing propositions in the subsequent state. Actions that have possible preconditions and effects are referred to as incomplete actions. Because no prior work exists for the purpose of empirical comparisons, we compare our incomplete action planner, which we call DeFAULT, with a traditional planner that assumes all good possibilities and no bad possibilities will occur. DeFAULT finds much better quality plans than the traditional planner while maintaining similar speed.

Automated planning as a satisfiability problem is a method developed in theearly nineties. It has some known disadvantages, such as its inefficient encod-ing of numbers. The field of Satisfiability Modulo Teories tries to connectalready established solvers for e.g. linear constraints into SAT-solvers in orderto make reasoning about numerical values more efficient. This thesis combines planning as satisfiability and SMT to perform efficientreasoning about actions that occupy realistic time in Temporal Action Logic,a formalism developed at Linköping University for reasoning about action andchange.

Automated planning is a branch of AI that addresses the problem of generating a course of action to achieve a specified objective, given an initial state of the world. It is an area that is central to the development of intelligent agents and autonomous robots. In the last decade, automated planning has seen significant progress in terms of scalability, much of it achieved by the development of heuristic search approaches. Many of these advances, are only immediately applicable to so-called classical planning tasks. However, there are compelling applications of planning that are non-classical. An example is the problem of web service composition, in which the objective is to automatically compose web artifacts to achieve the objective of a human user. In doing so, not only the hard goals but also the \emph{preferences} of the user---which are usually not considered in the classical model---must be considered. % Also, the automated composition %should deal with abstract representations of the web %artifacts---which may also not adjust to the classical model. In this thesis we show that many of the most successful advances in classical planning can be leveraged for solving compelling non-classical problems. In particular, we focus on the following non-classical planning problems: planning with temporally extended goals; planning with rich, temporally extended preferences; planning with procedural control, and planning with procedural programs that can sense the environment. We show that to efficiently solve these problems we can use a common approach: reformulation. For each of these planning tasks, we propose a reformulation algorithm that generates another, arguably simpler instance. Then, if necessary, we adapt existing techniques to make the reformulated instance solvable efficiently. In particular, we show that both the problems of planning with temporally extended goals and with procedural control can be mapped into classical planning. Planning with rich user preferences, even after reformulation, cannot be mapped into classical planning and thus we develop specialized heuristics, based on existing heuristics, together with a branch-and-bound algorithm. Finally, for the problem of planning with programs that sense, we show that under certain conditions programs can be reduced to simple operators, enabling the use of a variety of existing planners. In all cases, we show experimentally that the reformulated problems can be solved effectively by either existing planners or by our adapted planners, outperforming previous approaches.

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.

abstract: In this dissertation I develop a deep theory of temporal planning well-suited to analyzing, understanding, and improving the state of the art implementations (as of 2012). At face-value the work is strictly theoretical; nonetheless its impact is entirely real and practical. The easiest portion of that impact to highlight concerns the notable improvements to the format of the temporal fragment of the International Planning Competitions (IPCs). Particularly: the theory I expound upon here is the primary cause of--and justification for--the altered (i) selection of benchmark problems, and (ii) notion of "winning temporal planner". For higher level motivation: robotics, web service composition, industrial manufacturing, business process management, cybersecurity, space exploration, deep ocean exploration, and logistics all benefit from applying domain-independent automated planning technique. Naturally, actually carrying out such case studies has much to offer. For example, we may extract the lesson that reasoning carefully about deadlines is rather crucial to planning in practice. More generally, effectively automating specifically temporal planning is well-motivated from applications. Entirely abstractly, the aim is to improve the theory of automated temporal planning by distilling from its practice. My thesis is that the key feature of computational interest is concurrency. To support, I demonstrate by way of compilation methods, worst-case counting arguments, and analysis of algorithmic properties such as completeness that the more immediately pressing computational obstacles (facing would-be temporal generalizations of classical planning systems) can be dealt with in theoretically efficient manner. So more accurately the technical contribution here is to demonstrate: The computationally significant obstacle to automated temporal planning that remains is just concurrency. / Dissertation/Thesis / Ph.D. Computer Science 2012