Practical Argumentation Framework

Plan Argumentation Framework

Argumentation to compose plans

Author : Maxime Morge

Abstract

We propose in this paper a framework for inter-agents dialogue on actions, which formalize a deliberative process. This framework bounds a dialectics system in which argumentative agents arbitrate and play to reach a practical agreement. For this purpose, we propose an argumentation-based reasoning to manage the conflicts between plans having different strengths for different agents. Moreover, we propose a model of agents which justify the plans to which they commit and take into account the plans of their interlocutors. In the scope of our dialectics system, an agent is responsible of the final decision outcome which is taken according to the authority of the players, the uttered plans and her own rules and priorities.

keyword

Computer Science, Artificial Intelligence, Multi-agent system, Dialogue, Planification

Introduction

The collaboration between autonomous and social agents to solve complex tasks is an open problem with many application areas such as cooperative robotics or services composition. The conflicts in the interests and perspectives of agents is the main characteristic of such systems. In this paper, we aim at formalizing a deliberative process with a formal framework for inter-agents interaction. For this purpose, argumentation is a promising approach for reasoning with inconsistent information and conflicting objectives. Classically, argumentation has been mainly concerned with theoretical reasoning to check beliefs veracity~\cite{dung95acceptability,amgoud2002reasoning,bench-capon02value}.

A coherent framework has been proposed in~\cite{morge05ail} to reconcile, combine and extend these technics. Recent works are concerned with practical reasoning~\cite{bench03pratical,pellier05ceemas,rahwan06pratical}. In~\cite{pellier05ceemas}, Damien Pellier and Humbert Fiorino focus on a generic mechanism allowing agents to compose their competences in order to jointly elaborate a common plan. \cite{ferguson93cooperative} considers an agent to support the planification. In this paper, we consider that such plans are arguments and we focus here on a dialogical mechanism between software agents to reason, exchange and compose them.

Paper overview. Section Motivation introduces the example of dialogue that will illustrate our framework throught this paper. In section~\ref{def:lang}, we provide the syntax and the semantics of the planning language. Section~\ref{sec:AF} presents the argumentation framework which manages the interaction between conflicting plans. In accordance with this background, we describe in section~\ref{sec:argumentation_MAS} our model of agents. In the section~\ref{sec:dialectics}, we define the formal area in which the agents deliberate. The section~\ref{sec:persuasion} presents the protocol used to reach a practical agreement. %Section~\ref{sec:conc} concludes.

Motivation

A dialogue is a sequence of coherent move from an initial situation to reach the goals of participants~\cite{walton95commitment}. For instance, the goal of dialogues consists in resolving a conflict about a service composition. In the initial situation, two services providers do not share the same competence, \textit{i.e.} the same set of services, either because one of them is not qualified or because their services are concurrent. We propose here that two services providers and a buyer play deliberation to reach a practical agreement.

Before the formalization of such dialogues, let us introduce the following example in natural language:

buyer: Which services can I use to go from Lille to Ottawa?
sellerone: My service is suitable to go from Lille to Ottawa and cost 1050 euros.
sellertwo: My service is also suitable to go from Lille to Ottawa and only costs 800 euros.
buyer: Why your service is suitable?
sellerone: Because train to Paris costs 150 euros, Air France fly to Montreal costs 800 euros and the bus to Ottawa cost 100 euros .
sellertwo: OK, but the train to Bruxelles costs 100 euros, the Air Canada fly to Montreal costs 650 euros and the bus to Ottawa cost 50 euros.
\buyer: I accept to use the train to Paris, the Air France fly to Montreal and the bus to Ottawa which cost 50 euros proposed by the first provider.

In this dialogue, two service providers propose two concurrent transport services from Lille to Ottawa and the buyer compose these two services. This example will be used throughout this paper.

Planning Language

Goal

In this section, we present the syntax and the semantics of the formal language that we use to express automated planning problem instance : the Action Description Language (ADL). This is an extension of the STRIPS~\cite{fikes71strips} language (STanford Research Institute Problem Solver),

Classical planning environments

syntax

The classical planning environments are fully observable, deterministic (the result of actions are foreseeable), discrete (the environment states are finite) and static (changes happens only when the agents acts). Planners decompose the world into logical conditions and represent a state as a conjunction of positive literals. For example, $rich\wedge famous$ represents the state of an happy agent. Literals in first-order state descriptions must be ground and function-free. Contrary to $near(ag_{1},Ottawa)$ , literals such as $near(ag_{x},y)$ or $near(daughter(ag{x}),Lille)$ are not allowed. The close-world assumption is used, meaning that any conditions that any conditions that are not mentioned in a state are assumed false.

A planning problem instance is composed of an initial state, the specification of the goal which the planner is trying to reach, and a set of possible actions. Each action is defined in terms of preconditions and postconditions.

An instance is defined by an ordered pair Failed to parse (unknown function "\L"): {\displaystyle \S =\langle \L,C \rangle} where:

${\mathcal {L}}$ is the first-order logic language previously presented. We call condition a conjunction of claims. The empty conjunction (denoted $\emptyset$ ) is true;
$C=A\cup \{i_{\S },g_{\S }\}$ $C=A\cup \{i_{\S },g_{\S }\}$ is a \textbf{competence}, i.e. a set of rules such as:
- $A$ is a set of actions, each action $a$ is a 4-tuple of conditions $a:\langle \gamma ,\delta \rangle \leftarrow \langle \alpha ,\beta \rangle$ , where $\alpha$ must be true for the action to be executable, $\beta$ must be false, $\gamma$ is made true by the action and $\delta$ ones is made false. The empty action is denoted $\epsilon$ ;
- $i_{\S }:\langle \alpha _{i},\beta _{i}\rangle \leftarrow$ is the initial state, given as the pair of conditions, which are respectively true and false ;
- $g_{\S }:\langle \gamma _{g},\delta _{g}\rangle \leftarrow$ is the specification of the goal state given as a pair, which specify which conditions are true ( $\gamma _{g}$ ) and false ( $\delta _{g}$ ), respectively, in order for a state to be considered a goal state.

On one hand, a state a fortiori the initial state $i_{\S }$ is a totally specified state represented as a conjonction of positive ground literals ( $\gamma _{i}$ ) and negative ground literals ( $\delta _{i}$ ). On the other hand, the specification of a goal $g_{\mathcal {S}}$ is a partially specified state represented as a conjonction of positive ground literals ( $\gamma _{g}$ ) and negative ground literals ( $\delta _{g}$ ). A propositional state ( $s:\langle \alpha _{s},\beta _{s}\rangle \leftarrow$ ) satisfies a goal ( $g_{\S }:\langle \gamma _{g},\delta _{g}\rangle \leftarrow$ ) if $s$ contains all the atoms in $g$ and possibly others ( $\gamma _{g}\subseteq \alpha _{s}$ and $\delta _{g}\subseteq \beta _{s}$ ). An action $a$ is specified in terms of positive preconditions ( $\alpha$ ) and negative preconditions ( $\beta$ ) that must hold before it can be executed, the positive effects ( $\gamma$ ) and the negative effects $\delta$ ) that ensure when it is executed. For example, an action for flying a plane from one location to another is: $fly(from,to):\langle near(buyer,to),near(buyer,from)\rangle \leftarrow \langle near(buyer,from),\emptyset \rangle$

This rule is also called action schema, meaning that it represents a number of differents actions that can be derived by instantiating the variables Failed to parse (unknown function "\from"): {\displaystyle \from} , and $\to$ to different constants. The action name Failed to parse (unknown function "\fly"): {\displaystyle \fly(\from,\to)} serves to identify the action, Any variables in the preconditions or in the postconditions must also appear in the action's parameter list. One of the most important restrictions is that literals be function-free.

With this restriction, we can be sure that any action schema can be propositionalized, so turned into a finite collection of purely propositionnal action representations with no variables. For example, we could translate the Failed to parse (unknown function "\fly"): {\displaystyle \fly(\from,\to)} action schema for $5$ airports into $5\times 5$ purely propositionnal actions. Since the preconditions expressing the facts that a flight cannot be made from an airport to itself, cannot be expressed sunccintly in STRIPS, we prefer the Action Description Language to the STRIPS language. To improve readibility, we have divided the preconditions and the effects into lists for postive and negative literals. In ADL, the fly action could be written as : Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikiversity.org/v1/":): {\displaystyle \fly(\from,\to) : \langle \near(\buyer,\to) , \near(\buyer,\from) \rangle \leftarrow \langle \near(\buyer,\from), \from = \to \rangle }

semantics

Having defined the syntax for the representation of planning problems, we can now define the semantics. For this purpose, we specify a direct transition from a state ( $s:\langle \alpha _{s},\beta _{s}\rangle \leftarrow$ ) into successor-state axioms whose semantics come from first order logic. An action ( $a:\langle \gamma _{a},\delta _{a}\rangle \leftarrow \langle \alpha _{a},\beta _{a}\rangle$ ) is applicable in any state that satifies the preconditions; otherwise the action has no effect. More formaly: Failed to parse (unknown function "\si"): {\displaystyle s, a \vdash \left\{ \begin{array}{ll} \langle (\alpha_s \cup \gamma_a) - \delta_a ,(\beta_s \cup \delta_a) - \gamma_a \rangle &\si \alpha_a \subseteq \alpha_s \mbox{and}\\ &\beta_a \subseteq \beta_s\\ \langle \alpha_s, \beta_s \rangle &\mbox{else} \end{array} \right. }

Starting in a state $s$ , the result of executing an \textbf{applicable action} $a$ is a state $s'$ except that any positive literals in the effect are added to $s'$ and any negative literals are removed from $s'$ . For example, suppose the current state is described by: Failed to parse (unknown function "\near"): {\displaystyle s: \langle \near(\buyer,\Paris), \near(\buyer,\Lille) \rangle} . This state satifies the precondition: Failed to parse (unknown function "\near"): {\displaystyle \langle \near(buyer,\from), \from = \to \rangle} with substitution Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikiversity.org/v1/":): {\displaystyle \{ \Paris / \from, \Montreal / \to \}} . Thus, after the concrete action Failed to parse (unknown function "\fly"): {\displaystyle \fly(\buyer,\Paris,\Montreal)} the current state becomes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikiversity.org/v1/":): {\displaystyle s': \langle \near(\buyer,\Montreal) , \near(\buyer,\Paris) \et \near(\buyer,\Lille) \rangle \leftarrow} . Note that if a positive effect is already in $s$ it is not added twice, and if a negative effect is not in $a$ , then that part of the effect is ignored. This definition embodies the assumption that every literal not mentionned in the effects remains unchanged. In this way, we avoid the frame problem.

Since the states could be represented by a pair of conditions, two states $s_{1}:\langle \alpha _{1},\beta _{1}\rangle \leftarrow$ and $s_{2}:\langle \alpha _{2},\beta _{2}\rangle \leftarrow$ are \textbf{incompatible} (denoted $s_{1}\bot s_{2}$ ) iff: Failed to parse (unknown function "\inter"): {\displaystyle (\alpha_1 \inter \beta_2) \union (\alpha_2 \inter \beta_1) \neq \emptyset} .

Finaly we can define the solution for a planning problem. The transition relation can be extended such that: $c,\epsilon \vdash c$ and $c,(a_{1},a_{2},\ldots ,a_{n})\vdash (c,a_{1}\vdash ),(a_{2},\ldots ,a_{n})$ . A plan for an instance is a sequence of actions such that the state that results from executing the actions from the initial state satisfies the goal conditions. A plan $P=(a_{1},a_{2},\ldots ,a_{n})$ is a sequence of actions ( $\forall i~a_{i}\in A$ ) such as $i,P\vdash g$ . \textbf{ $P$ satisfies $S$ } iff $\alpha _{i}\subseteq \alpha _{i_{\S }},\beta _{i}\subseteq \beta _{i_{\S }},\gamma _{g_{\S }}\subseteq \gamma _{g},\delta _{g_{\S }}\subseteq \delta _{g}$ . In other words, a solution for a planning problem is just a plan that, when excecuted in the initial state, results in a state that satifies the goal. Below we will use this planning language within our argumentation framework.