Temporal Defeasible Argumentation in Multi-Agent Planning

1 Introduction

In classical planning, intelligent agents must be able to set goals and achieve them, they have a perfect and complete knowledge of the world, and they assume their view of the world can only be changed through the execution of the planning actions. However, in many real-world applications, agents often have contradictory information about the environment and their deductions are not always certain information, but plausible, since the conclusions can be withdrawn when new pieces of knowledge are posted by other agents.

On the one hand, Multi-Agent Planning (MAP) generalizes the problem of planning in domains where several agents plan and act together, and have to share resources, activities, and goals. In a cooperative approach, the emphasis is placed on how planning can be extended to a distributed environment. On the other hand, argumentation, which has recently become a very active research field in computer science [BenchCapon and Dunne, 2007], can be viewed as a powerful tool for reasoning about inconsistent information through a rational interaction of arguments for and against some conclusion.

DeLP framework [Garc´ıa and Simari, 2004] applies defeasible reasoning for the generation and evaluation of arguments to build applications that deal with incomplete and contradictory information in dynamic domains. DeLP-POP framework in [Garc´ıa et al., 2008] extends POP (PartialOrder Planning) 1 [Penberthy and Weld, 1992], with DeLP

1 We also believe that POP, or also known as least commitment

inference based on interactions between arguments. A DeLPPOP planner can enforce goals with a combination of actions and undefeated arguments, if their conditions (are known to) apply. Thus, arguments will not only occur to intentionally support some step of a plan, but also they will happen to defeat or defend such supporting argument and the plan containing it.

The work in [Belesiotis et al., 2010] presents a dialogue based on an argumentation process to reach agreements on plan proposals, which is aimed at handling the interdependencies between agents' plans. Other research work in [Pardo et al., 2011] proposes a formal model of argumentative dialogues for multi-agent planning, with a focus on cooperative planning. This latter work is aimed at extending DeLP-POP framework to multi-agent planning, thus resulting in a framework named DeLP-MAP. In this cooperative scenario, we have a team of agents aware of a common set of goals, but ignorant of others' abilities and beliefs (defeasible rules), who must find a common plan. Unlike centralized DeLP-POP, a DeLP-MAP framework implements dialogues for argumentative plan search which are applied to cooperative scenarios. A dialogue consists in a series of exchanges (dialogues are turn-based) of plan proposals addressing the current goal, plus arguments for or against of these proposals.

2 Motivation

This thesis proposes a temporal DeLP-MAP, i.e. a temporal argumentation framework whereby agents take into account the time element in the argumentative dialogues. Little work has been done in the way of temporal argumentation for multi-agent planning. Temporal argumentation has been used for ramification analysis in dynamic, changeable domains with contradictory sources of information such as news reporting [Hunter, 2001; Mann and Hunter, 2008]. There have also been proposals to construct argumentation systems based on temporal defeasible reasoning to reason about the justification of truths in the system [Augusto and Simari, 2001] but it is not particularly concerned with the task of MAP.

One of the hypotheses of this work is that time is a crucial element in any theory of action and change in order to address a changing world. In a temporal setting, valid arguments may be no longer valid after a certain period of time, arguments that hold at some point may persist over time, and new reasons to infer further conclusions or support previous conclusions may also arise over time. For instance, imagine an argument which justifies that we should not consider an action -moving plane from location 'j' to 'k'- in the plan under construction because there is a threat of strike in the airport. It has not the same validity in a time instant where air traffic controllers are against the sector's new labour regulations and an instant where they are comfortable with their work. Time also plays a key role in DeLP-MAP framework because what is not realizable at a time, it may become realizable sooner or later. We believe that our first step is to define a temporal model which allow us to represent explicit temporal references by means of instants and intervals.

planning, is the best planning approach concerned with the dynamic multi-agent nature due to the ease to join several plan proposals into a single joint plan.

Another important aspect is how argumentative dialogues change in a DeLP-MAP framework over time. The agents are continually learning new facts, beliefs and actions over time, so they find it easier to build new temporal arguments as time passes because their knowledge bases are continuously growing. Thereby, the progress of time also influences on how these dialogues are carried out.

Therefore, two important aspects to consider in the argumentative dialogues are to arguing both about the time and over time. We believe that exploiting temporal argumentation in a DeLP-MAP framework would report important benefits not only as for what to do but also when to do it in order to achieve a temporally consistent set of goals. As far as we know, there are not studies addressing the temporal defeasible argumentation in planning. Our aim is to apply it in multiagent planning, specifically in a DeLP-MAP framework.

3 PhD Thesis Abstract

The objective of this thesis is to propose and implement a model of temporal argumentation for DeLP-MAP. The contributions of this work are organized on different levels.

On the theoretical and formal level, we propose a temporal argumentation framework (extending DeLP-MAP framework) which allows agents to dialogue about the temporal plan under construction based on the utilization of temporal arguments.

On the implementation level, our main aim is to provide agents of DeLP-MAP with the ability of generating temporal arguments, selecting the best ones to pose and evaluating incoming arguments as well as the argumentation process itself in the plan under construction. Here, the first step is to decide how agents represent temporal arguments. There are some requirements that should be met to make a suitable choice for the structure to represent arguments in our DeLP-MAP framework: 1) be computationally tractable and designed to make automated reasoning efficiently; 2) be rich enough to represent both temporal knowledge about the environment as temporal defeasible information and diverse abilities of the agents; 3) be generic enough to represent different types of temporal arguments; and 4) comply with the technological standards of data and argument interchange on the web. Moreover, we will implement the temporal reasoning process that agents perform to generate, select and evaluate temporal arguments taking into account their temporal beliefs.

On the practical level, the objective of this thesis is to develop a protocol which allows agents to exchange (1) temporal plan proposals that achieve the current goal, plus (2) temporal arguments for or against (1), with the aim to get a joint plan.

Finally, the hypothesis and proposals of the thesis will be implemented and tested in different case studies: a multiagent system of travel agents, a planning model for e-learning and a system for the water-right transfer management in a real Spanish river basin.

Acknowledgments

This work is supported by FPU grant reference AP2009-1896 awarded to Sergio Pajares-Ferrando and projects TIN200806701-C03-01, Consolider Ingenio 2010 CSD2007-00022, and PROMETEO/2008/051.