Search

Any agent, either biological or artificial, understands how to behave in its environment according to its prior knowledge and to its prior experience. The process of deciding which actions to undertake and how to perform them so as to achieve some desired objective is called deliberation. In particular, planning is an abstract and explicit deliberation process that chooses and organizes actions, by anticipating their expected outcomes, with the aim to achieve, as best as possible, some pre-stated objectives called goals. Among the most widespread approaches to automated planning, the classical approach broadly pursues to the following definition of planning: starting from a description of the initial state of the world, a description of the desired goals, and a description of a set of possible actions, the planning problem consists in synthesizing a plan, i.e., a sequence of actions, that is guaranteed, when applied to the initial state, to generate a state, called a goal state, which contains the desired goals. In order to cope with computational complexity, however, the classical approach to planning introduces some restrictive assumptions. Among them, for example, there is no explicit model of time and concurrency is treated only roughly. Additionally, goals are specified as a set of goal states, therefore, objectives such as states to be avoided and constraints on state trajectories or utility functions are not handled. In order to relax these restrictions, some alternative approaches have been proposed over the years. The timeline-based approach to planning, in particular, represents an effective alternative to classical planning for complex domains requiring the use of both temporal reasoning and scheduling features. This thesis focuses on timeline-based planning, aiming at solving some efficiency issues which inevitably raise as a consequence of the drop out of these restrictions. Regardless of the followed approach, indeed, it turns out that automated planning is a rather complex task from a computational point of view. Furthermore, not all of the approaches proposed in literature can rely on effective heuristics for efficiently tackling the search. This is particularly true in the case of the more recent and hence less investigated timeline-based formulation. Most of the timeline-based planners, in particular, have usually neglected the advantages triggered in classical planning from the use of Graphplan and/or modern heuristic search, namely the capability of reasoning on the whole domain model. This thesis aims at reducing the performance gap between the classical approach at planning and the timeline-based one. Specifically, the overall goal is to improve the efficiency of timeline-based reasoners taking inspiration from techniques applied in more classical approaches to planning. The main contributions of this thesis, therefore, are a) a new formalism for timeline-based planning which overcomes some limitations of the existing ones; b) a set of heuristics, inspired by the classical approach, that improve the performance of the timeline-based approach to planning; c) the introduction of sophisticated techniques like the non-chronological backtracking and the no-good learning, commonly used in other fields such as Constraint Processing, into the search process;d) the reorganization of the existing solver architectures, of a new solver called ORATIO, that allows to push the reasoning process beyond the sole automated planning, winking at emerging fields like, for example, Explainable AI and e) the introduction of a new language for expressing timeline-based planning problems called RIDDLE.

The declarative approach has been widely accepted as an appropriate way to manage configurations of large scale systems - the administrators describe the specification of the "desired" configuration state of the system, and the tool computes and executes the necessary actions to bring the system from its current state into this desired state. However, none of state-of-the-art declarative configuration tools make any guarantees about the order of the changes across the system involved in implementing configuration changes. This thesis presents a technique that addresses this issue - it uses the SFP language to allow administrators to specify the desired configuration state and the global constraints of the system, compiles the specified reconfiguration task into a classical planning problem, and then uses an automated planning technique to automatically generate the workflow. The execution of the workflow can bring the system into the desired state, while preserving the global constraints during configuration changes. This thesis also presents an alternative approach to deploy the configurations - the workflow is used to automatically choreograph a set of reactive agents which are capable to autonomously reconfigure a computing system into a specified desired state. The agent interactions are guaranteed to be deadlock/livelock free, can preserve pre-specified global constraints during their execution, and automatically maintain the desired state once it has been achieved (self-healing). We present the formal semantics of SFP language, the technique that compiles SFP reconfiguration tasks to classical planning problems, and the algorithms for automatic generation and execution of the reactive agent models. In addition, we also present the formal semantics of core subset of SmartFrog language which is the foundation of SFP. Moreover, we present a domain-independent technique to compile a planning problem with extended goals into a classical planning problem. As a proof of concept, the techniques have been implemented in a prototype configuration tool called Nuri, which has been used to configure typical use-cases in cloud environment. The experiment results demonstrate that the Nuri is capable of planning and deploying the configurations in a reasonable time, with guaranteed constraints on the system throughout reconfiguration process.

Student mobility in the area of Higher Education (HE) is gaining more attention nowadays. It is one of the cornerstones of the Bologna Process being promoted at both national and international levels. However, currently there is no technical system that would support student mobility processes and assist users in authoring educational curricula involving student mobility. In this study, the problem of student mobility programmes generation based on existing modules and programmes is considered. A similar problem is being solved in an Intelligent Tutoring Systems field using Curriculum generation techniques, but the student mobility area has a set of characteristics limiting their application to the considered problem. One of main limiting factors is that mobility programmes should be developed in an environment with heterogeneous regulations. In this environment, various established routines and regulations are used to control different aspects of the educational process. These regulations can be different in different domains and are supported by different authors independently. In this thesis, a novel framework was developed for generation of student mobility programmes in an environment with heterogeneous regulations. Two core technologies that were coherently combined in the framework are hierarchical planning and policy-based management. The policy-based planner was designed as a central engine for the framework. It extends the functionality of existing planning technologies and provides the means to carry out planning in environments with heterogeneous regulations, specified as policies. The policy-based planner enforces the policies during the planning and guarantees that the resultant plan is conformant with all policies applicable to it. The policies can be supported by different authors independently. Using them, policy authors can specify additional constraints on the execution of planning actions and extend the pre-specified task networks. Policies are enforced during the planning in a coordinated manner: situations when a policy can be enforced are defined by its scope, and the outcomes of policy evaluation are processed according to the specially defined procedures. For solving the problem of student mobility programme generation using the policy-based planner, the planning environment describing the student mobility problem area was designed and this problem was formalised as a planning task. Educational processes valid throughout the HE environment were formalised using Hierarchical Task Network planning constructs. Different mobility schemas were encoded as decomposition methods that can be combined to construct complex mobility scenarios satisfying the user requirements. New mobility programmes are developed as detailed educational processes carried out when students study according to these programmes. This provides the means to model their execution in the planning environment and guarantee that all relevant requirements are checked. The postponed policy enforcement mechanism was developed as an extension of the policy-based planner in order to improve the planning performance. In this mechanism, future dead-ends can be detected earlier during the planning using partial policy requests. The partial policy requests and an algorithm for their evaluation were introduced to examine policies for planning actions that should be executed in the future course of planning. The postponed policy enforcement mechanism was applied to the mobility programme generation problem within the descending policy evaluation technique. This technique was designed to optimise the process of programme components selection. Using it, policies for different domains can be evaluated independently in a descending order, gradually limiting the scope for the required component selection. The prototype of student mobility programme generation solution was developed. Two case studies were used to examine the process of student mobility programmes development and to analyse the role of policies in this process. Additionally, four series of experiments were carried out to analyse performance gains of the descending policy evaluation technique in planning environments with different characteristics.

Multiagent systems offer a design paradigm used to conceptualise and implement systems composed of autonomous agents. Autonomy facilitates proactive independent behaviour yet in practice agents are constrained in order to ensure the system satisfies a desired social objective. Explicit constraints on agent behaviour, in the form of social norms, encourage this desirable system behaviour, yet research has largely focused on norm representation languages and protocols for norm proposal and adoption. The fundamental problem of how to automate the process of norm synthesis has largely been overlooked with norms assumed provided by the designer. Previous work has shown that automating the design of social norms is intractable in the worst case. Existing approaches, relying on state space enumerations, are effective for small systems but impractical for larger ones. Furthermore, they do not produce a set of succinct, general norms but rather a large number of state-specific restrictions. This work presents conflict-rooted synthesis, an automated norm synthesis approach that utilises a planning-based action schemata to overcome these limitations. These action schemata facilitate localised searches around specifications of undesirable states, using representations of sets of system states to avoid a full state enumeration. The proposed technique produces concise, generalised social norms that are applicable in multiple system states while also providing guarantees that agents are still able to achieve their original goals in the constrained system. To improve efficiency a set of theoretically sound, domain-independent optimisations are presented that reduce the state space searched without compromising the quality of the norms synthesised. A comparison with an alternative model checking based technique illustrates the advantages and disadvantages of our approach, while an empirical evaluation highlights the improved efficiency and quality of norms it produces at the cost of a less expressive specification of undesirable states. We empirically investigate the effectiveness of each of the proposed optimisations using a set of benchmark domains, quantifying how successful each of them is at reducing search complexity in practice. The results show that, with all optimisations enabled, conflict-rooted synthesis produces more generally applicable and succinct norms and consumes fewer system resources. Additionally, we show that this approach synthesises norms in systems where the competing approach is intractable. We provide a discussion of our approach, highlighting the impact our abstract search approach has on the fields of multiagent systems and automated planning, and discuss the limitations and assumptions we have made. We conclude with a presentation of future work.

Autonomous agents in a multi-agent system coordinate to achieve their goals. However, in a partially observable world, current multi-agent systems are often less effective in achieving their goals. In much part, this limitation is due to an agent's lack of reasoning about other agents and their mental states. Another factor is the agent's inability to share required knowledge with other agents and the lack of explanations in justifying the reasons behind the goal. This research addresses these problems by presenting a general approach for agent goal management in unexpected situations. In this approach, an agent applies three main concepts: goal reasoning - to determine what goals to pursue and share; theory of mind - to select an agent(s) for goal delegation; explanation - to justify to the selected agent(s) the reasons behind the delegated goal.Our approach presents several algorithms required for goal management in multi-agent systems. We demonstrate that these algorithms will help agents in a multi-agent context better manage their goals and improve their performance. In addition, we evaluate the performance of our multi-agent system in a marine life survey domain and a rover domain. Finally, we compare our work to different multi-agent systems and present empirical results that support our claim.

This thesis presents a novel approach to solving decision-making problems in discrete, stochasticdomains. The method for solving these problems is often dictated by the availability of informationabout how the environment responds to actions taken by the agent. When the agentis given a model of the environment, it can plan out its actions beforehand, whereas an agentwithout a model must learn to differentiate good and bad decisions through direct experience.Until now, little attention has been paid to situations in which a model is only available for apart of the environment. We propose an algorithm which combines automated planning withhierarchical reinforcement learning in order to take advantage of the model when it is availableand sample from the environment when it is not. We prove that the same guarantees of optimalitythat apply to hierarchical reinforcement learning also apply to to this approach. Usingexperiments performed in two different domains, we demonstrate that hierarchically integratedplanning and reinforcement learning outperforms pure RL and pure planning hierarchies andthat this approach can scale to larger problems than are reasonably computable by other approaches.

A key characteristic of intelligence is the use of ecient problem-solving strategies when faced with unfamiliar tasks. Enabling machines to do autonomous problem-solving is thus a major milestone on the path to developing intelligent systems. Automated planning is a discipline in artificial intelligence research that studies this topic, specifically the process of automatically computing strategies for using actions to achieve a desired outcome. Given a declarative description of a task, a planning system finds an action sequence (a plan) that leads from a given initial state to a state that satisfies a specified goal description. The quality of a plan is measured via its length or, in cost-based planning, via associated costs of the actions it comprises. While the planning problem in general is computationally intractable, many planning tasks can be solved eciently due to some inherent structure of the task. Knowledge about such structure or certain properties of a planning task, so-called control knowledge, can often be extracted automatically from the problem description. This thesis makes several contributions to improve the eciency of automated planning. We focus on forward-chaining heuristic search in the state space of a planning task, currently the most widely used approach to planning. In the first part of this thesis, we detail novel methods for extracting landmarks, a particular type of control knowledge, from planning tasks. We then propose a way of using these landmarks as a heuristic estimator for judging progress during planning, and show empirically that this leads to shorter plans and allows solving more tasks in unit-cost planning. We furthermore analyse the performance gain achieved via landmarks in cost-based planning and find that landmarks can be particularly helpful in this setting, making up for the bad performance of other (cost-sensitive) heuristics. In the second part of this thesis, we focus on improving the underlying search algorithms to increase coverage (the number of tasks solved) and solution quality in planning. We conduct a detailed study of two popular search-control techniques, preferred operators and deferred evaluation, and demonstrate their respective usefulness for improving coverage and solution quality under various conditions. We also consider anytime planning to find high-quality plans given limited time. In anytime planning, the aim is to compute an initial solution quickly, and then iteratively improve on this solution while time remains. We demonstrate that the greediness that is necessary to find an initial plan quickly can impede the planning system in finding better solutions later, unless the system abandons previous eort and restarts the search. We then combine the methods analysed in the previous chapters and incorporate them into one planning system. The resulting planner LAMA, winner of the 2008 International Planning Competition, is presented in detail and compared with other state-of-the art planners. We study the interactions of various techniques employed in the system and show how much each feature contributes to the overall performance. We find that both landmarks and restarting anytime search contribute to the good performance on the set of benchmark tasks considered. Furthermore, the two techniques interact beneficially in some cases. Lastly, we provide an outlook on possible extensions of our work by investigating more complex types of landmarks. We show that using higher-order landmarks can significantly improve the heuristic estimates obtained from a landmark heuristic. However, the additional eort required for finding and using such landmarks does not necessarily pay off.