1 Department of Applied Mathematics and Computer Science, Technical University of Denmark2 Algorithms and Logic, Department of Applied Mathematics and Computer Science, Technical University of Denmark3 Department of Informatics and Mathematical Modeling, Technical University of Denmark
This thesis is concerned with planning and logic, which are both core areas of Artificial Intelligence (AI). A wide range of research disciplines deal with AI, including philosophy, economy, psychology, neuroscience, mathematics and computer science. The approach of this thesis is based on mathematics and computer science. Planning is the mental capacity that allow us to predict the outcome of our actions, thereby enabling us to exhibit goal-directed behaviour. We often make use of planning when facing new situations, where we cannot rely on entrenched habits, and the capacity to plan is therefore closely related to the reflective system of humans. Logic is the study of reasoning. From certain fixed principles logic enables us to make sound and rational inferences, and as such the discpline is virtually impossible to get around when working with AI. The basis of automated planning, the term for planning in computer science, is essentially that of propositional logic, one of the most basic logical systems used in formal logic. Our approach is to expand this basis so that it is based on richer and and more expressive logical systems. To this end we work with logics for describing knowledge, beliefs and dynamics, that is, systems that allow us to formally reason about these aspects. By letting these elements be used in a planning context, we obtain a system that extends the degree to which goaldirected behaviour can, at present, be captured by automated planning. In this thesis we concretely apply dynamic epistemic logic to capture knowledge, and dynamic doxastic logic for capturing belief. Vi highlight two results of this thesis. The first pertains to how dynamic epistemic logic can be used to describe the (lack of) knowledge of an agent in the midst of planning. This perspective is already incorporated in automated planning, and seen in isolation this result appears mainly as an alternative to existing theory. Our second result underscores the strengths of the first. Here we show how the kinship between the aforementioned logics enable us to extend automated planning with doxastic elements. An upshot of expanding the basis of automated planning is therefore that it allows for a modularity, which facilitates the introduction of new aspects into automated planning. We round things o_ by describe what we consider to be the absolutely most fascinating perspective of this work, namely situations involving multiple agents. Reasoning about the knowledge and beliefs of others are essentialy to acting rationally. It enables cooperation, and additionally forms the basis for engaging in a social context. Both logics mentioned above are formalized to deal with multiple agents, and the first steps have been taken towards extending automated planning with this aspect. Unfortunately, the first results in this line of research have shown that planning with multiple agents is computationally intractable, and additional work is therefore necessary in order to identify meaningful and tractable fragments.