Sage Journals: Discover world-class research

Abstract

This paper studies how logic-based reasoning about actions and change (RAC) with its problems of temporal projection and qualification can be formalised in terms of argumentation. In particular, we extend earlier work of translating the language $E$ for RAC into a logic-based argumentation framework, by introducing new types of arguments for (i) backward persistence and (ii) persistence from observations. This forms a conservative extension of the language $E$ that gives a semantic meaning to domains that cannot be interpreted under $E$ thus addressing further the frame and (exogenous) qualification problems. As such the paper strengthens the link between argumentation theory and RAC in artificial intelligence.

Keywords

argumentation reasoning about actions narratives

1. Introduction and motivation

Reasoning about actions and change (RAC) has been an important problem in the development of artificial intelligence (AI). Starting with the early and foundational work of the situation and event calculi (Kowalski and Sergot, 1986; McCarthy and Hayes, 1969) there has been a wide interest in understanding and solving the central problems that underly RAC, namely the frame, ramification and qualification problems leading to several ‘action languages’ such as the $A$ , $C$ and $E$ languages (Gelfond and Lifschitz, 1993; Kakas and Miller, 1997; McCain and Turner, 1997) and the fluent calculus (Thielscher, 1999).

The relatively recent realisation that non-monotonic reasoning can be addressed using argumentation (e.g. Bench-Capon and Dunne, 2007; Bondarenko, Dung, Kowalski, and Toni, 1997; Dung, 1995; Kakas, Kowalski, and Toni, 1992) has led to the study of RAC through argumentation in works such as (Kakas, Miller, and Toni, 1999; Vo and Foo, 2005). Hence given some narrative information we can use argumentation to capture temporal projection from this and general knowledge about the causal laws of our problem domain. As shown in Kakas et al. (1999), where the language $E$ (Kakas and Miller, 1997) for RAC was formalised in terms of argumentation, default persistence over time can be captured by assigning higher priority to arguments that are based on later events over arguments based on earlier events.

In this paper we extend this argumentation-based formulation of language $E$ by introducing arguments based on property observations that one typically finds in any given narrative. We will also introduce in the framework new arguments for backward persistence. This will allow us to recover and also extend language $E$ , giving a semantic meaning to domains that cannot be interpreted under $E$ . With this form of backward persistence the extended interpretation of the language $E$ comes closer to the spirit of the original event calculus (EC) (Kowalski and Sergot, 1986) which also includes notions for backward temporal conclusions. Our work can thus also be seen as a way of increasing the expressiveness of the original EC by allowing for example positive but also negative observations.

We will be mainly concerned with domains that language $E$ cannot give models and exogenous qualification is required. From a purely technical point of view, we extend the argumentation formulation of language $E$ giving a semantics to domains where $E$ fails to do so. From a conceptual point of view, we aim to address the qualification problem in RAC (see, e.g. Thielscher, 2001) in a natural and modular way. This will rely on capturing a relative strength between arguments where, for example, arguments based on observations are stronger than other types ofarguments.

RAC is an area that is concerned with the study of how (some of) the properties of our problem domain, normally called Fluents, change when new information is acquired such as the occurrence of Actions and how this view of the problem world is affected by the explicit observation of some properties holding or not at a particular stage (or time) in the flow of change. The change is governed by domain-specific causal laws that describe how the particular properties (or fluents) of interest are generated or terminated by actions and the domain-independent principle of frame inertia that properties do not change but rather persist, unless some action occurrence causes them to change via some causal law. The main aim of the reasoning is then to maintain, normally under the case of incomplete information, an accurate view of the problem world as things occur and/or are observed with the passage of time given in a specific narrative ofinterest.

To illustrate the types of problems that will concern us and the general approach that we will follow let us consider a standard example in RAC, that has the name the ‘ Car Park Domain’ (Kautz, 1986). This domain when expressed in the language $E$ contains one action constant ParkingCar and one property fluent CarInParkingSpace together with the causal law that ‘ parking the car causes the car to be in the parking space’. This causal law together with the specific narrative information that we park the car at time 4 and that later at time 8 we observe that the car is not where it was parked, is represented by the following domain description:

For domains like this, where a fluent (e.g. CarInParkingSpace) changes its truth value without any known causal explanation, language $E$ does not have a model. Our extended argumentation framework of the language $E$ that includes arguments for observations and for backwards persistence will allow arguments for both truth values of the fluent within the time interval $(4, 8)$ . Forwards persistence from the action ParkingCar ( $Δ_{2}$ ) that initiates CarInParkingSpace for every time point $t > 4$ ( $Δ_{1}$ ) comes into conflict with backwards persistence from the observation argument $\neg CarInParkingSpace$ ( $Δ_{3}$ ). Allowing the same priority between conflicting forward persistence and backwards persistence arguments will give the natural interpretation of unknown value for the fluent CarInParkingSpace for every $t \in (4, 8)$ .

Pictorially, the way our argumentation framework behaves as we update the domain description for the parking domain example, is illustrated in Figure 1 where KB denotes the domain description, PC the action ParkingCar and CPS the fluent CarInParkingSpace. The arrows in the pictures show the different arguments (for the fluent CSP and its negation) that exist in each case.

Figure 1.

Parking domain.

Suppose now that we extend the parking domain example by adding in the narrative another observation at time 12 of the form:

CarInParkingSpace holds at time 12 ( $Δ_{4}$ )

This will also result in an unknown value for the fluent CarInParkingSpace in the interval $(8, 12)$ . This arises analogously from conflicting arguments based on the two observation arguments ( $Δ_{3}$ ) and ( $Δ_{4}$ ). Forward persistence from $\neg CarInParkingSpace$ ( $Δ_{3}$ ) is equally strong to backwards persistence from CarInParkingSpace ( $Δ_{4}$ ) and hence we can build equally good (or strong) arguments both for the truth and falsity of the fluent at any time point in this interval. Finally, we note that by giving higher priority to conflicting forward persistence over backwards persistence we will see that our framework can fully recover language $E$ and hence in this respect it forms a conservative extension of $E$ .

The argumentation-based formalisation that we will develop in this paper is essentially a preference based (see, e.g. Modgil and Prakken, 2013) realisation of an abstract argumentation framework (Dung, 1995) under the admissibility semantics. Following the approach in Kakas et al. (1999), we will build the preference-based argumentation framework in terms of logic programming rules with a priority relation over these rules. Our work then can be seen as an example where the general theory of argumentation, that has been extensively and widely developed over the past two decades in AI (see, e.g. Bench-Capon and Dunne, 2007; Rahwan and Simari, 2009), finds concrete application in addressing the foundational problems of temporal persistence and knowledge qualification.

This synthesis of ideas opens up possibilities of extending the application of argumentation from ‘static problems’ to variations of these where the problem environment is dynamically changing as new information becomes available. Using argumentation for reasoning about changes in the problem's world domain offers a principled way to manage the changes in the argumentation framework under which the application problem is expressed, thus extending the use of argumentation from static to ‘dynamic problems’.

The rest of the paper is organized as follows. Section 2 gives a brief review of the language $E$ . In Section 3 we give the extended argumentation framework of language $E$ . Section 4 presents the formal results related to the semantics and the properties of the extended argumentation framework. Section 5 explores further the qualification problem based on this framework. Section 6 discusses related work and Section 7 concludes.

2. A brief review of language

E

Language $E$ (Kakas and Miller, 1997) is inspired by the EC (Kowalski and Sergot, 1986). As most other action languages, language $E$ has a set of action constants, $A C$ , that name actions that can occur and a set of fluent constants, $F$ , that name the different properties that can change in the problem domain. Fluent literals are either positive or negative fluent constants. It also has a set of time points, $T$ , such that for time points $T_{1}$ and $T_{2}$ , the notation $T_{1} < T_{2}$ indicates that time point $T_{1}$ comes before time point $T_{2}$ and $T_{1} \neq T_{2}$ .

The language uses three kinds of sentences or propositions defined as follows, where A is an action constant, F is a fluent constant, T is a time point, L is a fluent literal and C is a set of fluent literals:

c-propositions (c stands for causes), of the form ‘ A initiates F when C’ or ‘ A terminates F when C’,

h-propositions (h stands for happens) of the form ‘ A happens-at T’,

t-propositions (t stands for time point) of the form ‘ L holds-at T’.

The first type of sentence is used to express the causal laws of our domain, i.e. how action occurrences generate a property or stop a property from holding. The other two types of sentences are used to describe the particular narratives of interest. The first is used to state what actions have occurred while the latter type of sentences, namely the t-propositions, which will also be called observations, are used to represent properties of the world known to hold at particular time points.

A domain description D is a set of t-, h- and c-propositions. The c-propositions form the background world knowledge of the domain and the t- and h-propositions the narrative of the domain.

The semantics of language $E$ is given in terms of its models. These assign a truth value, $true or false$ to every fluent at every time point in the domain in a way that satisfies a set of constraints which reflect the axiom of persistence of the truth value of fluents. The following definitions (taken from Kakas and Miller, 1997) formalize the notion of a model.

Definition 2.1 interpretation

Given a domain description D, an interpretation of D is a mapping $H : F \times T \mapsto {true, false}$ where $F$ is the set of fluent constants in D and $T$ is the set of time points in $E$ . A fluent literal F (resp. $\neg F)$ is satisfied at T by H if and only if $H (F, T) = true$ (resp. $H (F, T) = false)$ .

An interpretation may or may not support the initiation or termination of a fluent property depending on whether the preconditions in the causal laws of the domain description are satisfied or not under the interpretation.

Definition 2.2 initiation-termination point

Given an interpretation H of a domain description D, a time point T is an initiation (resp. termination) point of a fluent F in H in D when, D contains a combination of a c-proposition ‘ A initiates (resp. terminates) F when C’ and an h-proposition ‘ A happens-at T’ , such that C at T is satisfied by the interpretation H.

An interpretation is then a model when it satisfies the property of persistence, namely that, within any time interval the truth value assigned by a model to any fluent remains the same or persists, changing from false to true (resp. from true to false) only at an initiation (resp. termination) point for that fluent that is supported by some action occurrence and associate causal law under which the action changes the fluent.

Definition 2.3 model

Let D be a domain description. An interpretation H is a model of D if and only if for every fluent constant F and time points $T_{1}, T_{2}, T_{3}$ the following properties hold:

If there is no initiation-point or termination-point $T_{2}$ for F in H in D such that $T_{1} ⩽ T_{2} < T_{3},$ then $H (F, T_{1}) = H (F, T_{3})$ .

If $T_{1}$ is an initiation-point for F in H in D, and there is no termination-point $T_{2}$ for F in H in D such that $T_{1} ⩽ T_{2} < T_{3},$ then $H (F, T_{3}) = true$ .

If $T_{1}$ is a termination-point for F in H in D, and there is no initiation-point $T_{2}$ for F in H in D such that $T_{1} ⩽ T_{2} < T_{3},$ then $H (F, T_{3}) = false$ .

For all t-propositions in D of the form ‘ F holds-at $T_{1}$ ’ , $H (F, T_{1}) = true,$ and for all t-propositions in D of the form ‘ $\neg F$ holds-at $T_{2}$ ’ , $H (F, T_{2}) = false$ .

The property of persistence is expressed by the first three conditions with the second and third conditions also capturing the semantic meaning of the causal laws expressed by the c-propositions. The fourth condition imposes the requirement that models must respect all the observations (t-propositions) of fluents literals contained in the narrative of the given domain description.

The above definition of a model is a slightly extended definition of the original definition in Kakas and Miller (1997) that allows non-deterministic models when we have domains where there exist time points that can be simultaneously initiation and termination points for the same fluent. For this we have replaced, in the second and third conditions of the original definition, the restriction on the intermediate time point, $T_{2}$ , to be strictly greater than $T_{1}$ , i.e. the restriction $T_{1} < T_{2}$ , by $T_{1} ⩽ T_{2}$ .

Given the notion of a model, entailment and consistency of formulae of the form ‘ L holds-at T’, where L is a fluent literal are then defined in the usual way. Hence ‘ L holds-at T’ is consistent in D iff there exists a model, M, of D such that $M (F, T) = true$ when $L = F$ and $M (F, T) = false$ when $L = \neg F$ . Similarly, ‘ L holds-at T’ is entailed by D when the above holds for every model, M, of D.

The following simple examples illustrate the (above variant of) language $E$ . Let us consider the domain descriptions $D, D^{'}$ and $D^{″}$ shown in Figure 2, where A and B are an action constants and $T_{1} < T_{2}$ are two time points.

Figure 2.

Example domains.

Example 2.4 domain D

A initiates F

A happens-at $T_{1}$

F holds-at $T_{2}$

In domain D we have an initiation point at time $T_{1}$ and at time $T_{2}$ we observe F. Models of language $E$ , for domain D, require F to be true for all $T > T_{1}$ whereas, for $T^{'} ⩽ T_{1}$ a model can assign F to be either true or false at all such time points. Suppose we replace the observation that F holds at $T_{2}$ with the observation that it does not hold, i.e. we have the domain $D^{'}$ given by

Example 2.5 domain $D^{'}$

A initiates F

A happens-at $T_{1}$

$\neg F$ holds-at $T_{2}$ .

Then this domain, which is similar to the car parking domain discussed in the introduction, does not have any models. The generation of F holding onwards from $T_{1}$ cannot be reconciled with the observation of $\neg F$ at $T_{2}$ . Similarly, for the domain $D^{″}$ , given by

Example 2.6 domain $D^{″}$

F holds-at $T_{1}$

$\neg F$ holds-at $T_{2}$

language

E

is inconsistent and has no models. The persistence of F holding onwards from

T_{1}

cannot be reconciled with the observation of

\neg F

T_{2}

. Finally, consider the domain

D^{‴}

given by

Example 2.7 domain $D^{‴}$

A initiates F

B terminates F

A happens-at $T_{1}$

B happens-at $T_{1}$

We have two possible models for times after time $T_{1}$ . In one F holds true for all such time points and in the other F is false for all time points after time $T_{1}$ . Hence if we extend this domain with either of the observations that F holds-at $T_{2}$ or $\neg F$ holds-at $T_{2}$ the extended domain remains consistent.

3. Argumentation formulation

The language $E$ has been reformulated in terms of argumentation (Kakas et al., 1999) within the preference-based argumentation framework of logic programs with priorities, LPwNF, under its admissibility semantics (Dimopoulos and Kakas, 1995; Kakas, Mancarella, and Dung, 1994). In this the information from t-propositions (observations) is not used in the argumentation process but rather these observations are imposed as a posteriori constraints on the argumentation formulation.

We will extend this reformulation so that t-propositions are taken into account directly within the argumentation. To do so we will generalize the original formulation by introducing new arguments that are rooted or based on observations. In addition, we will use backward temporal persistence arguments as well as forward ones to allow us to address the qualification problem.

To translate a given domain description D into an argumentation program in LPwNF, all individual h- and c-propositions translations are included in the background theory as follows. We will consider time to be discrete scalar.

Definition 3.1 background theory for D

The background theory for D is the theory $B (D)$ given by:

for all time points T and $T^{'}$ and action constants A:

$B (D) ⊢ T ⩽ T^{'}$ if and only if $T ⩽ T^{'},$

$B (D) ⊢ T < T^{'}$ if and only if $T < T^{'},$

$HappensAt (A, T) \in B (D)$ if and only if ‘ A happens-at T’ is in D, and

$Observation (L, T) \in B (D)$ if and only if ‘ L holds-at T’ is in D.

for each c-proposition ‘ A initiates F when ${L_{1}, \dots, L_{n}}$ ’ in D, $B (D)$ contains the rule

$Initiation (F, t) \leftarrow HappensAt (A, t), Λ (L_{1}), \dots, Λ (L_{n}),$ and

for each c-proposition $‘ A$ terminates F when ${L_{1}, \dots, L_{n}}$ ' in D, $B (D)$ contains the rule

$Termination (F, t) \leftarrow HappensAt (A, t), Λ (L_{1}), \dots, Λ (L_{n})$

where $Λ (L_{i}) = HoldsAt (F_{i}, t)$ if $L_{i} = F_{i},$ and $Λ (L_{i}) = \neg HoldsAt (F_{i}, t)$ if $L_{i} = \neg F_{i},$ for any fluent constant $F_{i},$

$B (D)$ contains no other rules.

The above definition is essentially the same as in Kakas et al. (1999) with the exception that the given observations are also added in $B (D)$ and hence the whole narrative forms part of the background knowledge. Any such background knowledge is then extended by the following logic program rules and priorities between these to give the fullargumentation logic program with priorities corresponding to a given domain description.

Definition 3.2 argumentation program of D

The argumentation program corresponding to a domain D is $A D \equiv (B (D), A, <)$ where:

1
PFP (resp. $PBP)$ stands for Positive Forward (resp. Backward) Persistence, NFP (resp. $NBP)$ stands for Negative Forward (resp. Backward) Persistence, ${PG}_{F}$ (resp. ${PG}_{B})$ stands for Positive Forward (resp. Backward) Generation, ${NG}_{F}$ (resp. ${NG}_{B})$ stands for Negative Forward (resp. Backward) Generation, PO (resp. $NO)$ stands for Positive (resp. Negative) Observation and finally PA (resp. $NA)$ stands for Positive (resp. Negative) Assumption.

This definition introduces four different types of arguments and the relative strength between them. These types of arguments express in a natural way the defeasible conclusions that we can draw or support from the non-defeasible information in $B (D)$ .

Let us explain the various parts of this definition. Consider first the various arguments rules.

Persistence rules : These rules express the possibility of fluent properties persisting forward and or backward in time. The first rule captures the forward persistence from a property holding at t to holding at a latter point $t_{2}$ , while the second rule captures the backward persistence from a property holding at t to holding at an earlier point $t_{1}$ . The other two rules are similar but for the persistence of properties not holding.

Local generation arguments : These are argument rules for the causation of a property by an event. The first rule says that the effect of an initiation point at time t starts at the very next time point, while the second rules say that from this initiation point we have an argument that its effect does not hold at the time of the event that generates the property. Analogously for the following two rules based on termination points.

Local observation arguments : Observations give directly arguments for fluents holding or not at the time of observation.

Initial assumptions : Assumptions can only be introduced at time 0 and can be for a property holding or not holding.

Let us now comment on the priority relation. We first note that the priority relation, <, in an argumentation program is independent of the domain description, D. It is a universal relation that will us capture the general principles of persistence and qualification.

Set 1: The first set of priorities in the above definition make forward persistence arguments that are based on a later time point stronger than conflicting forward persistence arguments that are based on an earlier time point. Analogously, backward persistence arguments that are based on earlier time points are stronger than conflicting backward persistence arguments that are based on later time points.

Set 2: This set of priorities expresses the fact that the generation of effects is stronger than opposing persistence.

Set 3–Set 5: The final three sets of priorities give, as expected, higher strength to observation arguments over any other type of conflicting arguments.

We note that included in the types of arguments are the two local generation arguments, ${NG}_{B} [f, t]$ and ${PG}_{B} [f, t]$ , which are not usually found in formulations of many RAC frameworks, with a notable exception of the original EC. It is important though to stress that these arguments only support the possibility for the occurrence of events and their initiation or termination of effects to affect the past. The argumentation formulation allows us to capture this possibility in a weak form, by saying that there exists an argument for something holding in the past due to the occurrence of events. Then depending on the priority we give to this argument over other arguments, its effect on the semantics would vary. For example, as we will see below if we assign forward persistence arguments to be stronger than these local generation arguments (or more generally stronger than backwards persistence arguments) then these arguments do not have any effect on the semantics, i.e. no maximal admissible extension can contain these local generation arguments.

In the priority relation there is no priority between conflicting forward and backward arguments. Such priorities can be additionally set when we wish to impose further properties on the temporal reasoning. Finally, we note that the assumption arguments are not chosen to be weaker than the conflicting backwards persistence arguments to allow the freedom of incomplete initial states.

The semantics of these LPwNF argumentation programs is given through the standard argumentation notion (see Dung, 1995; Kakas et al., 1994) of maximally admissible subsets of the given argumentation program, called admissible extensions, as follows.

Definition 3.3 background logic

The background monotonic logic is the tuple $(L, ⊢),$ where the language $L$ consists of all ground rules of the form $l_{0} \leftarrow l_{1}, l_{2}, \dots, l_{n}$ $(n ⩾ 0)$ that belong to $B (D)$ or $A$ with each $l_{i}$ a classical literal. $l_{0}$ is called the head of the rule and $l_{1}, l_{2}, \dots, l_{n}$ is called the body of the rule. ├ is obtained by the repeated application of the modus ponens rule.

The above definition expresses formally the logical reasoning that allows the link of the background knowledge with the argument rules so that arguments supporting a fluent literal conclusion can be constructed. These arguments are grounded on the narrative given in the domain description D and translated in the corresponding background knowledge B(D).

The attacking relation is then defined amongst sets of argument rules that have conflicting conclusions by taking into account the priorities on the argument rules as given in Definition 3.2.

Definition 3.4 attack

Let $G, W$ be two non empty sets of argument rules. G attacks W if and only if there exists a literal l of the form $HoldsAt (f, t)$ or $\neg HoldsAt (f, t)$ and sets $G_{1} \subseteq G$ and $W_{1} \subseteq W$ such that:

$B (D) \cup G_{1} ⊢_{min} l$ 2

2
$B (D) \cup X ⊢_{min} l$ if and only if $B (D) \cup X ⊢ l$ and there does not exist $X^{'} \subset X$ such that $B (D) \cup X^{'} ⊢ l$ .

and

B (D) \cup W_{1} ⊢_{min} \neg l

if there exist $r^{'} \in G_{1}, r \in W_{1}$ such that $r^{'} < r$ then there exist $r^{'} \in G_{1}, r \in W_{1}$ such that $r < r^{'}$ .

Hence the attacking relation is defined by lifting the priorities from the level of single argument rules to sets of these. For a set G of argument rules to attack another set W it must contain at least one rule of higher priority than a rule in the attacked set W or otherwise the set W must (also) not contain any rule of higher priority than some rule in the attacking set G. In this way we ensure that the attacking set is not ‘weaker’ than the attacked set as either it contains a stronger rule or the two sets are non-comparable. Note that if a set is inconsistent, i.e. it derives both a literal and its negation then it attacks itself as the second condition in the definition of the attacking relation is trivially satisfied.

The following definition introduces some technical conditions on sets of argument rules that are more specific to the use of argumentation to the particular application of RAC.

Definition 3.5 closed, complete and compact

A set Δ of argument rules is closed if all the bodies of its rules are derived via ├ from the background theory $B (D)$ extended by Δ. Δ is complete if for any fluent f and time point t, $Δ ⊢ HoldsAt (f, t)$ or $Δ ⊢ \neg HoldsAt (f, t)$ . Finally, Δ is compact if Δ is closed and does not contain a pair of argument rules, $PFP [f, t;_]$ and $PBP [f, t;_]$ or $NFP [f, t;_]$ and $NBP [f, t;_],$ for any fluent f and any time point t.

The condition of closeness is a technical condition to avoid considering unnecessarily argument sets that contain rules which cannot be used to support conclusions. Similarly, the compactness property imposes a uniqueness of support for the conclusions drawn through persistence arguments requiring that any such conclusion (timed fluent literal) is supported in a uni-directional way, i.e. either by a forwards persistence or by backwards persistence but not (redundantly) by both such arguments. These technical conditions are conditions that avoid redundancy and help to simplify the framework and the proofs of its formal properties, particularly the link with the model theory of language $E$ when the two approaches coincide.

Finally, the property of completeness is a desired property for the semantics of the approach so that the admissible extensions, that will define the semantics, are able to decide for any fluent at any time point its status, i.e. they can populate the whole time line with a decision on whether any fluent holds or not. This condition is also motivated by the technical consideration of relating the semantics to the model theory semantics of the language $E$ .

Definition 3.6 admissibility

Let D be a domain description and $A D \equiv (B (D), A, <)$ its corresponding argumentation program. Let S be a closed subset of $A$ . Then S is admissible if and only if:

$B (D) \cup S$ does not derive a literal l and its complement $\neg l$ and

for any $S^{'} \subseteq A$ if $S^{'}$ attacks S then S attacks $S^{'}$ .

This is the standard definition of admissibility. A subset of arguments is admissible if it does not derive both $HoldsAt (f, t)$ and $\neg HoldsAt (f, t)$ for any fluent and time point and therefore it does not attack itself and it can counter-attack any subset of arguments that attacks it.

The semantics of domain descriptions is then given by putting these notions together to define admissible extensions of the corresponding argumentation program.

Definition 3.7 admissible extension

Let D be a domain description and $A D \equiv (B (D), A, <)$ its corresponding argumentation program. Let S be a closed subset of $A$ . Then $Δ = B (D) \cup S$ is an admissible extension of AD if and only if S is a complete and compact admissible set.

We note that alternatively we could have omitted the explicit requirement of completeness and replaced this with the maximality condition as we normally have with the preferred semantics of argumentation. Nevertheless, remaining within the spirit of RAC and as complete extensions are maximal it is natural to define the semantics only in terms of the complete admissible extensions provided that complete extensions exist, which as we will see in the next section, is indeed the case. Complete admissible extensions then correspond more closely to the stable semantics of argumentation as they cannot be extended consistently (i.e. without self-conflict) by any other subset of argument rules that support a conclusion that is not already supported by the complete extension.

Conclusions from an admissible extension are then drawn using the derivability relation, ├, given in Definition 3.3, with credulous conclusions those that can be derived from at least one admissible extension and sceptical conclusions as those that are derived in every admissible extension.

To illustrate the above definition of the argumentation semantics let us consider our earlier example domains D (Example 2.4), $D^{'}$ (Example 2.5) and $D^{″}$ (Example 2.6) within the argumentation framework defined above (Figure 3). In domain D, for all $T > T_{1}$ the strongest (and hence admissible) argument is for F to hold through a local generation argument at $T_{1} + 1$ and then by forwards persistence arguments at any other time after $T_{1}$ . Otherwise, from $T_{2}$ onwards we can use the observation argument at $T_{2}$ and forwards persistence arguments from this to support strongly F for times greater than $T_{2}$ . For $T^{'} ⩽ T_{1}$ , we can have admissible arguments for F or its negation $\neg F$ depending on the assumption we make at the initial time point. Note also that the backwards persistence arguments for F from $T_{2}$ to some time point equal to or before $T_{1}$ would not be stronger than the forwards persistence of $\neg F$ starting from time 0 through an assumption argument for $\neg F$ . Nor would it be stronger than the backwards negative generation argument for $\neg F$ based on the initiation point $T_{1}$ for F.

Figure 3.

Example domains and arguments.

Figure 4.

Examples.

For the domain $D^{″}$ , the strongest argument for all time points $T ⩾ T_{2}$ is the observation argument for $\neg F$ at $T_{2}$ combined with a forward persistence argument from $T_{2}$ to any such time point T. For times between $T_{1}$ and $T_{2}$ , we have admissible arguments for either F or $\neg F$ : at some time point $T_{k}$ , $T_{1} ⩽ T_{k} < T_{2}$ , the fluent F changes from true to false at $T_{k + 1}$ . This indicates that the given narrative has some missing information within this time interval that would explain the change in F. Similar results hold for $D^{'}$ where also in this case there exists an admissible extension where $\neg F$ holds for all times T, such that $T_{1} ⩽ T ⩽ T_{2}$ . This captures the possibility that the generation of F at $T_{1}$ has failed through some exogenous qualification.

The examples that follow illustrate further the argumentation formulation. Let f be any fluent and $t, T$ time points:

Example 3.8.

Let $D_{1}$ be a domain with no h-propositions and t-propositions. The only possible admissible extensions is for f (resp. $\neg f$ ) to hold for all times t as there does not exist a stronger argument that attack the set $S = {PA [f, 0], PFP [f, t; 0]}$ , for all $t > 0$ . Possible attacks on S contain the argument $NA [f, 0]$ and S counterattacks it through $PA [f, 0]$ . Admissible extensions in this example domain are the same as the (maximally) admissible extensions of language $E$ .

Example 3.9.

Let $D_{2}$ be a domain with no t-propositions containing h-propositions so that it necessarily has two initiation points of f at $t_{1}, t_{2}$ such that $t_{2} > t_{1}$ . In this case, language $E$ models require f to hold for all $T > t_{1}$ . In our extended argumentation framework, f will hold for all $T > t_{2}$ in all admissible extensions. For time points $T^{'} \in (t_{1}, t_{2}]$ we can build an argument for f, ( ${PG}_{F} [f, t_{1}], PFP [f, T^{'}; t_{1} + 1]$ ) and an argument for its negation $\neg f$ , ( ${NG}_{B} [f, t_{2}], NBP [f, T^{'}; t_{2}]$ ) which are both admissible. Hence between the two initiation points we cannot conclude that f is entailed, like language $E$ , as f does not hold in all admissible extensions. We will see that our framework is closer to the original EC in this respect. Also we will see that if we wish to fully recover language $E$ we could do this by assigning higher priority to forward persistence arguments over conflicting backwards persistence arguments.

Note that if we additionally have in the domain $D_{2}$ a termination point for f at time $T^{″} \in (t_{1}, t_{2})$ then the second type of argument sets that derives $\neg f$ at points in between the two initiation points before $T^{″}$ would not be admissible anymore as it would be attacked by the stronger backward persistence argument for f from $T^{″}$ , namely from ( ${PG}_{B} [f, T^{″}], PBP [f, T^{'}; T^{″}]$ ). This can be understood as an indication that the given narrative in $D_{2}$ has some missing information between the time points $t_{1}$ and $t_{2}$ of the two initiation points.

4. Formal results

In this section we present a set of formal results that show the various properties that the argumentation formulation given above has with respect to persistence and qualification, how this formulation gives meaning to any domain description theory and how it relates to and extends the original model theoretic formulation of language $E$ .

Firstly, as expected, we show that admissible extensions are consistent with the observations in the given narrative. From now on we will consider only point-wise consistent domain descriptions, i.e. domain descriptions that do not contain any pair of t-propositions of the form ‘ f holds-at t’ and ‘ $\neg f$ holds-at t’.

Proposition 4.1.
Let D be a point-wise consistent domain description and E an admissible extension of the corresponding argumentation program $AD \equiv (B (D), A, <)$ . Then E is consistent with D, i.e. there does not exist a t-proposition, ‘ f holds-at t’ (resp. ‘ $\neg f$ holds-at t’ ) in D such that $E ⊢ \neg$ HoldsAt $(f, t)$ (resp. $E ⊢$ HoldsAt $(f, t))$ .
Proof.
see Appendix 2.

This is a simple basic result that is needed for the main result of showing the existence of admissible extensions for any description domain and for linking admissible extensions with the models of language $E$ , whenever such models exist. Indeed, it corresponds to the fourth condition in the definition of a model of language $E$ (see Definition 2.3).

The next result shows that the admissible extensions satisfy the important property of persistence of derivation of fluent properties along the time line. Informally, it says that if between two time points there is no information, either causal or observational in nature, that a fluent has changed value then an admissible extension will derive a constant value for the fluent in this time interval.
Lemma 4.2.
Let D be a point-wise consistent domain description and E an admissible extension of D. Let f be a fluent and $t_{n} < t_{m}$ two time points such that there does not exist an initiation point nor a termination point for the fluent f in E3
3
An initiation or termination point for a fluent f in an admissible extension E is defined as in Definition 2.2 where now the preconditions C of the c-proposition are satisfied at T in E when the corresponding HoldsAT conclusions are derived by E.

at any time $t_{1} \in [t_{n}, t_{m})$ nor there exists an observation point for the fluent f in E at any time $t_{2} \in (t_{n}, t_{m})$ . Then if $E ⊢$ HoldsAt $(f, t_{n})$ and $E ⊢$ HoldsAt $(f, t_{m})$ hold or (respectively, $E ⊢ \neg$ HoldsAt $(f, t_{n})$ and $E ⊢ \neg$ HoldsAt $(f, t_{m})$ hold) then $E ⊢$ HoldsAt $(f, t)$ (respectively, $E ⊢ \neg$ HoldsAt $(f, t))$ holds, for every $t \in [t_{n}, t_{m}]$ .
Proof.
see Appendix 1.

Therefore the notion of admissibility in argumentation helps us to capture the requirement of persistence. Admissible extensions must have this property of persistence as otherwise they will have attacks that they cannot counter-attack. This plays an important role in showing the next theorem which gives the central result of the argumentation formulation, namely that any domain description D (with a countable narrative) is always consistent, i.e. there always exists an admissible extension of the corresponding argumentation program of D.
Theorem 4.3.
Let D be a point-wise consistent domain description with time structure that of the natural numbers and a countable number of h- and t-propositions. Then there exists an admissible extension E of the corresponding argumentation program $A D \equiv (B (D), A, <)$ .
Proof.
see Appendix 3.

Hence any domain description D is given a meaning under the above argumentation semantics. For example, as we have seen above, the example domains $D^{'}$ (Example 2.5) and $D^{″}$ (Example 2.6) are consistent in our extended framework. These domains do not have any model in the language $E$ or an admissible extension in the earlier argumentation-based reformulation of $E$ in Kakas et al. (1999) .

The formal link of our argumentation formulation of the language $E$ with its original model theoretic semantics is given by the following theorem.
Theorem 4.4.
Let D be a point-wise consistent domain description with time structure that of the natural numbers and a countable number of h-propositions . Then for every language $E$ model, M, of D there exists an admissible extension, E, of the corresponding argumentation program $A D \equiv (B (D), A, <)$ such that E corresponds to M, i.e. E ├ $HoldsAt (f, T)$ if and only if $M (f, T) = true$ and $E ⊢ \neg$ HoldsAt $(f, T)$ if and only if $M (f, T) = false$ .
Proof.
see Appendix 3.

This theorem shows that when language $E$ models exist then our argumentation framework always has a corresponding admissible extension. Our formulation therefore forms a conservative extension of $E$ .

The next theorem provides an interpretation of how the extended argumentation formulation handles the qualification problem when it provides a semantics to any domain description. It shows that an admissible extension E of any domain D can be interpreted as a language $E$ model of D or of D extended by some h-propositions of unknown events.
Theorem 4.5.
Let D be a point-wise consistent domain description with a finite number of h-propositions and t-propositions. For every admissible extension E of D there exists a domain $D^{'}$ obtained from D by adding a (possibly empty) set of new h-propositions such that there exist a language $E$ model, M, of $D^{'}$ that corresponds to E (i.e. $E ⊢$ HoldsAt $(f, t)$ (resp. $E ⊢ \neg$ HoldsAt $(f, t))$ if and only if $M (f, t) = true$ (resp. $M (f, t) = false))$ .
Proof.
see Appendix 3.

For example consider the domain $D^{″}$ (Example 2.6) where we observe F at time $T_{1}$ and $\neg F$ at time $T_{2}$ . Then given any time point $T_{k} \in (T_{1}, T_{2})$ this domain has admissible extensions E where F is derived for any time point between $T_{1}$ up to $T_{k}$ and $\neg F$ is derived for all time points after $T_{k}$ up to $T_{2}$ . The domain $D^{″}$ does not have any language $E$ models. But by interpreting time $T_{k}$ as a termination point for F through an unknown (in D) new action that can terminate F we can ‘explain’ within $E$ the meaning given to $D^{″}$ by the above admissible extensions in the extended argumentation formulation of the language.
5. Qualification extensions

In this section we study in more detail how the argumentation semantics that we have provided for action theories addresses the qualification problem. In particular, we will examine how it helps us understand qualifications of action occurrences and how we can find, within the given domain description, explanations for exogenous qualifications.

The argumentation formulation allows us to identify exogenous qualifications imposed by the lack of information in the given narrative of the domain description.

Definition 5.1.
Let D be a domain description and E an admissible extension of D such that there exist time points $t_{1}, t_{2}$ with $t_{1} < t_{2}$ and a fluent F so that the following conditions hold:
The t-proposition ‘ $\neg F$ holds-at $t_{2}$ ’ (respectively ‘ F holds-at $t_{2}$ ’ ) belongs to D and there is no t-proposition ‘ F holds-at t’ (respectively ‘ $\neg F$ holds-at t’ ) in D for any t such that $t_{1} < t < t_{2}$ .

There exists an h-proposition ‘ A happens-at $t_{1}$ ’ and a c-proposition ‘ A initiates F when C’ (respectively ‘ A terminates F when C’ ) in D such that $t_{1}$ is an initiation (respectively termination) point for F in E, and there is no other initiation (respectively termination) point t for F in E such that $t_{1} < t < t_{2}$ .4
4
For simplicity of presentation we are assuming that there can only be one generating (initiating or terminating) action of a given fluent at any time point.

There exists no termination point for F at t in E such that $t_{1} ⩽ t < t_{2}$ .

Then E is called an exogenous qualification extension on F at $(t_{1}, t_{2}]$ of D. The exogenous qualification is said to be based on the t-proposition ‘ $\neg F$ holds-at $t_{2}$ ’(respectively ‘ F holds-at $t_{2}$ ’ ).

Furthermore, if there does not exist a time point $t \in (t_{1}, t_{2})$ such that $E ⊢ HoldsAt (F, t)$ (respectively $E ⊢ \neg HoldsAt (F, t))$ then E is called an exogenous qualification of the action occurrence of A at $t_{1}$ . Otherwise, E is anexogenous qualification of the persistence of F in $(t_{1}, t_{2}]$ .

Qualification extensions are therefore separated into two types. In the first case, the action occurrence of A at $t_{1}$ is exogenously qualified failing to generate its effect and consequently in the whole of the interval, $(t_{1}, t_{2}]$ , $\neg HoldsAt (F, t)$ (respectively $HoldsAt (F, t)$ ) holds in E. In the second case, the action occurrence of A has succeeded to initiate its effect but its persistence was terminated before $t_{2}$ by some unknown exogenous event.

The above definition of exogenous qualification captures instances of direct qualification in the sense that the qualification is linked directly to the fluent through which the disparity between what is observed and what is described by the domain and its semantic extensions, manifests itself. The domain description implies that F (respectively $\neg F$ ) should hold at $t_{2}$ but the opposite, i.e. $\neg F$ (respectively F), is observed at $t_{2}$ . In the first case of an exogenous qualification of an action, the failure of the action to produce its effect could be due to some exogenous reason for (at least) one of the preconditions of the c-proposition through which F would be initiated (respectively terminated), not to hold at the time $t_{1}$ of the action occurrence. For example, consider the following domain description, also depicted in Figure 5.
Figure 5.
Domain ${QD}_{1}$ .

Example 5.2 domain ${QD}_{1}$

A initiates F when L

A happens-at $T_{1}$

L holds-at $T_{0}$

$\neg F$ holds-at $T_{2}$

All the admissible extensions of this domain are exogenous qualification extensions on F. In particular, one of these extensions is an exogenous qualification of the action occurrence of A at $T_{1}$ . But the failure of the action A to produce its effect F might be due to some other exogenous reason for the precondition L, of the c-proposition that initiates F, not to hold at the time of occurrence of A.

We can thus translate or explain the exogenous qualification of the action A at $T_{1}$ endogenously by the hypothesis that $\neg L$ holds-at $T_{1}$ and transfer the exogenous qualification of the domain to the earlier persistence of L from $T_{0}$ to $T_{1}$ . Indeed, if we add in ${QD}_{1}$ this t-proposition then the extended domain description does not anymore have an exogenous qualification extension for F between $T_{1}$ and $T_{2}$ . Such extensions of a given domain description with additional t-propositions so that the exogenous qualification of actions is pushed back into the past in terms of exogenous qualifications of preconditions of c-propositions will be called qualification explanation domains and are defined as follows.

Definition 5.3.
Given a domain description D and E an exogenous qualification extension of an action occurrence A on F at $t_{1}$ a qualification explanation domain for A at $t_{1}$ is a domain $D^{'}$ obtained from D by adding a set H of t-propositions on the narrative time points of D such that
H is point-wise consistent with the t-propositions already in D and H does not contain a t-proposition of the form ‘ F holds-at t’ for $t > t_{1}$ .

E is no longer an exogenous qualification extension of the action occurrence A at $t_{1}$ in $D^{'}$ in the sense that starting from the same initial state as in E there is no admissible exogenous qualification extension of the action occurrence A at $t_{1}$ in $D^{'}$ .

H is called a qualification explanation (with respect to E) (or the initial state of $E)$ of the exogenous failure of action A at $t_{1}$ .

In addition, as is usual with abductive explanations, we can require that qualification explanations are minimal with respect to set inclusion.

Hence in the previous Example 5.2, $H = {\neg L$ holds-at $T_{1}}$ , is a qualification explanation of the exogenous failure of action A at $T_{1}$ . Suppose now that we extend the previous Example 5.2 as follows: Example 5.4 domain ${QD}_{2}$

A initiates F when L

A happens-at $T_{1}$

B initiates L when K

$B^{'}$ terminates L when $K^{'}$

B happens-at $T^{'}$

$\neg F$ holds-at $T_{2}$

where

T_{0} < T^{'} < T_{1} < T_{2}

. Depending on the initial value of the fluents K and L in an admissible extension, i.e. whether a positive or a negative assumption argument at time

T_{0}

for these fluent is included in an extension, this will determine whether the extension is an exogenous qualification of the action occurrence of A at

T_{1}

. This can happen in two cases (a) ‘ L holds-at

T_{0}

’ or (b) ‘ K holds-at

T_{0}

’ under which the action occurrence of A at

T_{1}

gives a generation (initiation) argument for F. Figure 6 depicts this example and three possible qualification explanations,

H, H^{'}, H^{″}

, for the exogenous qualification of the action occurrence of A at

T_{1}

, as will be discussed below.

Figure 6.

Qualification explanations for domain ${QD}_{2}$ .

Hence under either of these cases, as in the previous example, a qualification explanation for the exogenous qualification of the action occurrence of A at $T_{1}$ is given by ‘ $\neg L$ holds-at $T_{1}$ ’. The extended domain obtained from ${QD}_{2}$ by adding this t-proposition does not anymore have an exogenous qualification extension of A at $T_{1}$ because the potential initiation argument of F at $T_{1}$ cannot be applied. But this extended domain, in the case where we have ‘ K holds-at $T_{0}$ ’, will now have an exogenous qualification extension for L at $T^{'}$ based on the new t-proposition that we have now added to the domain5

When we have the other case of ‘L holds-at $T_{0}$ ’ the extended domain will have admissible extensions with an exogenous qualification of persistence of L in $(T_{0}, T_{1}]$ .

(see Figure 7).

Figure 7.

Qualification explanation H for domain ${QD}_{2}$ .

We can then explain this new exogenous qualification by adding the extra t-proposition, ‘ $\neg K$ holds-at $T^{'}$ ’, to the extended domain. This pushes the exogenous qualification back to the persistence of K from $T_{0}$ to $T^{'}$ .

Then if also the initial state is such that $\neg L$ is derived at $T_{0}$ , e.g. when ‘ $\neg L$ holds-at $T_{0}$ ’ is in the domain, there will be no exogenous qualification of A at $T_{1}$ in the domain extended by both ‘ $\neg L$ holds-at $T_{1}$ ’ and ‘ $\neg K$ holds-at $T^{'}$ ’ (see Figure 8). Note that Figure 8 shows ‘ $\neg L$ holds-at $T_{1}$ ’ as an additional observation.

Figure 8.

Qualification explanation $H^{'}$ for domain ${QD}_{2}$ .

Furthermore, the new t-proposition, ‘ $\neg K$ holds-at $T^{'}$ ’, is sufficient alone, without the need for the earlier explanation ‘ $\neg L$ holds-at $T_{1}$ ’, to explain the exogenous qualification of A at $T_{1}$ . In other words, starting from the explanation $H = {\neg L$ holds-at $T_{1}}$ for the exogenous qualification of A at $T_{1}$ we can replace (one of) its element(s), i.e. ‘ $\neg L$ holds-at $T_{1}$ ’, by an explanation, $H^{'} = {\neg K$ holds-at $T^{'}}$ , of the exogenous qualification of B at $T^{'}$ based on this element, resulting in a new (minimal) explanation of the exogenous qualification of A at $T_{1}$ .

In general, there are two types of qualification explanation domains: ones that block a generation point as we have seen in the examples above and explanations that activate an intermediate generation point to block persistence. Let us consider an example of the latter type. In the example domain ${QD}_{2}$ another explanation of the exogenous qualification of A at $T_{1}$ would be possible if we had in the domain a known occurrence of the action $B^{'}$ at some time point $T^{″} \in (T^{'}, T_{1})$ (shown in Figure 6 with a dotted line). So let us assume that the domain ${QC}_{2}$ also contains the h-proposition $B^{'}$ happens-at $T^{″}$ . Then $H^{″} = {K^{'}$ holds-at $T^{″}}$ is a qualification explanation of the exogenous qualification of B at $T^{'}$ as it enables a termination point for L at $T^{″}$ . In turn this means that $H^{″}$ is also a qualification explanation of the exogenous qualification of A at $T_{1}$ . In other words, again starting from the explanation $H = {\neg L$ holds-at $T_{1}}$ for the exogenous qualification of A at $T_{1}$ we can generate a new explanation $H^{″}$ for this by finding an explanation for an earlier action that is exogenous qualified by the addition of H in the domain.

Hence as we have seen in the example above, qualification explanations can be built iteratively by pushing the exogenous qualification they explain to an earlier action and replacing (elements of) the initial explanation by an explanation of the exogenous qualification of the earlier action. The following property linking the qualification explanations of actions holds in general.

Property: Let D be a domain, E an exogenous qualification extension of an action occurrence A at $t_{1}$ and H a qualification explanation of A with respect to E. Let also ‘ L holds-at T’ belong to H and $H^{'}$ be a qualification explanation with respect to E of an action occurrence $A^{'}$ at $T_{1}$ ( $T_{1} < T$ ) based on L holds-at T. Then given $H^{″} = (H - {$ L holds-at T $}) \cup H^{'}$ one of the following holds:

$H^{″}$ is also a qualification explanation of A at $t_{1}$ with respect to E

or $D \cup H^{″}$ has an admissible extension $E^{″}$ with the same initial state as that of E such that $E^{″}$ is an exogenous qualification extension of an action occurrence $A^{″}$ at $T_{2}$ with $T_{2} < T_{1}$ .

or $E ⊢ \neg HoldsAt (L, 0)$ and the persistence of the fluent literal $\neg L$ from 0 to T is exogenously qualified in $D \cup H$ with respect to E.

Hence as we have seen above in the example domain ${QD}_{2}$ $H = {\neg L$ holds-at $T_{1}}$ can be replaced by $H^{″} = {\neg K$ holds-at $T^{'}}$ to either give a new qualification explanation of A at $T_{1}$ in the case where $E ⊢ \neg HoldsAt (L, 0)$ or when $E ⊢ HoldsAt (L, 0)$ the persistence of L from 0 to $T_{1}$ is exogenously qualified in $D \cup H$ .

Based on this property we can then develop algorithms to find qualification explanations of action failures by systematically following backwards the time line from the time of an unexpected observation, such as ‘ $\neg F$ holds-at $T_{2}$ ’ in the above examples, and examining the preconditions of the possible initiation and termination points for F. These explanations can be further compared according to some criterium, e.g. that of minimality of the number of actions that are exogenously qualified. This issue of the minimisation of exogenous qualification (and its argumentation interpretation) is beyond the scope of this paper. It is important though to note that the computation of qualification explanations is made possible by the generality of the argumentation semantics and its ability to give meaning to any domain description.

6. Related work

Our work follows the EC approach for RAC and the realisation of this through argumentation. It extends the earlier argumentation-based approach for the EC language $E$ (Kakas and Miller, 1997) by allowing the observations in a domain description to be used directly in the argumentation process rather than to be imposed as a posteriori constraints. As a result any domain description in $E$ can be given a meaning under the extended argumentation framework.

Interestingly, our formulation comes closer to the original EC (Kowalski and Sergot, 1986) . Like the original EC it has a symmetrical treatment of forward and backward reasoning from events, unlike the later formulations of the simplified EC (Miller and Shanahan, 1999; Shanahan, 1997) where the emphasis is mainly on reasoning forward from events. The original EC is based upon the notion of events and time periods generated by the events. There are two types of time periods, $after (e u)$ and $before (e u)$ generated by an event e and during which a fluent u holds. The first of these names a time period after the occurrence of the event e while the second names a time period before the occurrence of the event e. The ends of these periods is initially undefined until extra information that can help us derive this is provided. These time periods are derived through the rules in the EC of the following form:

$Holds (after (e u)) if Initiates (e u)$

$Holds (before (e u)) if Terminates (e u)$

Such rules are analogous to the arguments ${{PG}_{F} [u, e]$ , $PFP [u, t; e]}$ , where t is any time point after the time of the event e and ${NG}_{B} [u, e]$ and $NBP [u, t; e]$ , where t is any time point before or equal to the time of the event e.

This symmetrical nature of reasoning with time in the EC is mirrored with the symmetry of forward and backwards persistence arguments in our formulation. Hence both formalisms have similar effects especially when reasoning in the past. To illustrate this consider the simple example:

Example 6.1 domain $D^{''''}$

A initiates F

B initiates F

A happens-at $T_{1}$

B happens-at $T_{2}$

In this domain the original EC concludes that there exists an end point i of the time period $after (A F)$ such that $A < i ⩽ B$ . After i the value of F is unknown. The effect of this is that the value of F cannot be concluded at any time point between the time of A, i.e. $T_{1}$ , and the time of B, i.e. $T_{2}$ (as the exact time of i is unknown). Similarly, in our formulation there exists admissible extensions of this domain such that for any time point $T_{i} \in (T_{1}, T_{2})$ the fluent F changes it truth value from true to false and hence the value of F within this time period cannot be sceptically determined.

Hence both formulations essentially conclude the existence of at least one unknown event at some intermediate time point $T_{i}$ between $T_{1}$ and $T_{2}$ that has terminated F and hence we cannot decide sceptically on F between $T_{1}$ and $T_{2}$ . Through different mechanisms, our argumentation and the original EC give the same end result in terms of properties holding. We also note that both formalisms allow that in these situations of ‘uncertainty’ between two time points, the possibility of several changes in the value of the fluent.

The above example may be a little specialised. The more natural case of this effect of incorporating backwards persistence is seen in Examples 2.5 and 2.6 where observations are involved. The observations indicate a change in the value of a fluent at some unknown time within a certain time period. This is captured by our formulation thus showing how the original EC could be extended to allow observations in its domain descriptions.

Another approach to RAC using argumentation is that of Vo and Foo (2005). This work addresses the main problems of RAC, in particular the frame, and qualification problems, using a formulation that is based on argumentation and in particular the ABA argumentation framework of Bondarenko et al. (1997). As in Bondarenko et al. (1997), it uses argumentation assumptions that complement the logical knowledge to draw inferences from a domain description. There are two types of assumptions associated with each fluent literal: frame and qualification assumptions. The frame assumptions allow the persistence of a fluent literal as these assumptions can be assumed at any time point. Unlike our approach which relies directly on argumentation to capture persistence through the use of persistence arguments, the effect of persistence in Vo and Foo (2005) is obtained indirectly by the freedom of their formalism to make these frame assumptions. This though imposes the need to control this freedom by additional requirements imposed on top of a first structure they obtain via the argumentation requirement of preferred frame assumptions, called pre-models, in order to narrow down the possibilities of frame assumptions. This extra requirement is outside the standard argumentation notions imposing a ‘minimisation of change’ on the pre-models.

Subsequently, in order to handle also the qualification problem another type of assumptions is introduced, the qualification assumptions. These are ‘externally’ linked with each of the causal rules that generate fluent literals and are thought off as encompassing all the exogenous (unknown) qualification conditions that can block the generation of the fluent literal through the causal law. Then again a further technical machinery is developed on top of this with notions such as, plausible, unsound and rejected sets of assumptions, which need to be imposed on the initial pre-models, i.e. outside the argumentation formulation. In this filtering it is also necessary to impose carefully a preference of qualification assumptions over frame assumptions in order to solve both the frame and qualification problems together.

Hence although the two approaches have similarities as they are both based on argumentation they have crucial differences which can have an effect both at the representation and computational level. For example, the assumption arguments in Vo and Foo (2005) are of various types and are operational in nature rather than expressing some declarative knowledge in the domain. In contrast, our approach works directly on the given declarative knowledge of the problem: assumptions can only made at the initial time point and importantly they are declarative statements.

Furthermore, our approach addresses the problem of RAC entirely within standard argumentation notions with no reliance on any other formal structure. One of the reasons why this is not the case for the case of Vo and Foo (2005) is the overly liberal freedom to make assumptions in the first place. In our case the arguments considered need to be grounded (or supported) by the given domain description and particularly the narrative it contains. We can thus apply the argumentation process directly on the given knowledge capturing the required reasoning in a natural and simple way. This difference in the two approaches is highlighted by the way each approach uses priorities between arguments. In Vo and Foo (2005), the priorities are used on top to filter pre-structures whose definition depends on notions of argumentation only at a first level whereas in our case the priority is integrated within the argumentation process allowing the notions of argumentation to be sufficient to directly capture the semantics and the reasoning required.

As Vo and Foo (2005) argue, one of the main advantages of an argumentation-based approach to the central challenges of RAC and default reasoning more generally, is that the reasoning can be made more explicit compared to other non-monotonic approaches. This is a general feature shared by most argumentation-based application frameworks including our own in this paper, whose relative simplicity and direct use of argumentation makes it easy to exploit this advantage.

7. Conclusions and further work

We have re-examined the argumentation reformulation of language $E$ and introduced backwards persistence as well as forward persistence arguments to deal uniformly with the frame and qualification problems. This has enabled us to extend in a meaningful way domains that the language $E$ could not interpret when observations are included in the narrative. This argumentation interpretation corresponds to the unknown occurrences of events that could resolve potential inconsistencies between properties at different time points. Our extended argumentation framework comes closer in spirit to the original EC. It shows how this could be extended to include positive and negative observations and addressing the qualification problem that these observations may bring about, thus increasing significantly the expressiveness of the original EC.

For future work we will examine how we can integrate our framework for reasoning about properties over time with argumentation-based approaches for decision-making so that these decisions can be context sensitive over time. This will allow us to develop applications of advisory or recommendation systems, as in Chesñevar, Maguitman, and Simari (2004), that can adapt themselves as their external environment evolves. Similarly, we want to apply our framework to planning problems and in particular to the revision of plans as new unexpected information is acquired.

In particular, as the dialectic nature of argumentation is close to human reasoning, with recent studies from cognitive psychology (Mercier and Sperber, 2011) reinforcing this view, our argumentation-based approach for RAC can help its integration with wider forms of human reasoning such as that of discourse comprehension, dialogue and debate. Recent work on story comprehension (Diakidoy, Kakas, Michael, and Miller, 2014) has shown how argumentation can play a significant role in formulating and automating the human process of comprehension. Similarly, in multi-agent systems interaction and communication several works, e.g. McBurney and Parsons (2009) and Kakas, Maudet, and Moraitis (2004), have shown the suitability of using argumentation to model agent dialogues by exploiting the dialectic and game theoretic form of argumentation.

The dynamic nature of dialogues then lends itself to a uniform argumentation-based formalisation for integrating reasoning about changes in the environment of communication with the various dialogue protocols. In particular, the incremental process of a dialogue can be modelled in terms of dynamic argumentation by generalising the proof and game theories of computation (Dung, Kowalski, and Toni, 2006; Modgil and Caminada, 2009) for static argumentation. Allowing arguments to be time dependent we can adapt over time by tracking the changes of arguments and the attacking relation between them. Real-life problems can then be mapped to argumentation frameworks, constructed incrementally from the dynamic knowledge of the problem, e.g. the information exchanged at different time points of a dialogue.

Another way to address these problems of dynamic development is to examine the link between our work and that of dynamic argumentation (see, e.g. Baumann and Brewka, 2010; Liao, Jin, and Koons, 2011) where RAC with new information in the time line of an application problem realizes a dynamic argumentation framework. New arguments and attacks between arguments are enabled as the information unfolds, particularly by observations causing exogenous qualification. We can also explore how various problems that have been studied in the general setting of dynamic abstract argumentation can help address problems in RAC such as overcoming an exogenous qualification by finding what actions need to occur so that some conclusion would necessarily follow.

Footnotes

Disclosure statement

No potential conflict of interest was reported by the authors.

Appendix 1. Lemma proofs

Appendix 2. Propositions proofs

Appendix 3. Theorems proofs

References

Baumann

, & Brewka

(2010). Expanding argumentation frameworks: enforcing and monotonicity results. Computational models of argument: Proceedings of COMMA 2010, Desenzano del Garda, Italy, September 8–10, 2010, pp. 75–86.

Bench-Capon

T. J. M.

, & Dunne

P. E.

(2007). Argumentation in artificial intelligence. Artificial Intelligence , 171, 619–641. doi: 10.1016/j.artint.2007.05.001

Bondarenko

, Dung

P. M.

, Kowalski

R. A.

, & Toni

(1997). An abstract, argumentation-theoretic approach to default reasoning. Artificial Intelligence , 93, 63–101. doi: 10.1016/S0004-3702(97)00015-5

Chesñevar

C. I.

, Maguitman

A. G.

, & Simari

G. R.

(2004). A first approach to argument-based recommender systems based on defeasible logic programming. Proceedings of the 10th international workshop on non-monotonic reasoning (NMR 2004), Whistler, Canada, June 6–8, 2004, pp. 109–117.

Diakidoy

I. A.

, Kakas

A. C.

, Michael

, & Miller

(2014). Story comprehension through argumentation. Proceedings of the 5th international conference on computational models of argument (COMMA 2014), September, Frontiers in artificial intelligence and applications (Vol. 266, pp. 31–42). Scottish Highlands: IOS Press.

Dimopoulos

, & Kakas

A. C.

(1995). Logic programming without negation as failure. Logic programming, proceedings of the 1995 international symposium, Portland, OR, USA, December 4–7, 1995, pp. 369–383.

Dung

P. M.

(1995). On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelligence , 77, 321–357. doi: 10.1016/0004-3702(94)00041-X

P. M.

Dung ,

R. A.

Kowalski , & Toni

(2006). Dialectic proof procedures for assumption-based, admissible argumentation. Artificial Intelligence , 170, 114–159. doi: 10.1016/j.artint.2005.07.002

Gelfond

, & Lifschitz

(1993). Representing action and change by logic programs. The Journal of Logic Programming , 17, 301–321. doi: 10.1016/0743-1066(93)90035-F

10.

Kakas

A. C.

, Kowalski

R. A.

, & Toni

(1992). Abductive logic programming. Journal of Logic and Computing , 2, 719–770. doi: 10.1093/logcom/2.6.719

11.

Kakas

A. C.

, Mancarella

, & Dung

P. M.

(1994). The acceptability semantics for logic programs. Logic programming, proceedings of the eleventh international conference on logic programming, Santa Marherita Ligure, Italy, June 13–18, 1994, pp. 504–519.

12.

Kakas

A. C.

, Maudet

, & Moraitis

(2004). Flexible agent dialogue strategies and societal communication protocols. Paper presented at the 3rd international joint conference on autonomous agents and multiagent systems (AAMAS 2004), New York, NY, USA, August 19–23, 2004, pp. 1434–1435.

13.

Kakas , & Miller

(1997). A simple declarative language for describing narratives with actions. Journal of Logic and Algebraic Programming , 31, 157–200. doi: 10.1016/S0743-1066(96)00138-0

14.

Kakas

A. C.

, Miller

, & Toni

(1999). An argumentation framework of reasoning about actions and change. LPNMR, El Paso, Texas, USA, pp. 78–91.

15.

Kautz

H. A.

(1986). The logic of persistence. Proceedings of the 5th national conference on artificial intelligence: Volume 1: Science, Philadelphia, PA, August 11–15, 1986, pp. 401–405.

16.

Kowalski , &

Sergot (1986). A logic-based calculus of events. New Generation Computing , 4, 67–95. doi: 10.1007/BF03037383

17.

Liao

, Jin

, & Koons

R. C.

(2011). Dynamics of argumentation systems: A division-based method. Artificial Intelligence , 175, 1790–1814. doi: 10.1016/j.artint.2011.03.006

18.

McBurney

, & Parsons

(2009). Dialogue games for agent argumentation. In G. Simari & I. Rahwan (Eds.), Argumentation in artificial intelligence (pp. 261–280). Springer.

19.

McCain

, & Turner

(1997). Causal theories of action and change. Proceedings of the AAAI-97, Providence, Rhode Island, pp. 460–465.

20.

McCarthy

, & Hayes

(1969). Some philosophical problems from the standpoint of artificial intelligence. Machine Intelligence , 4, 463–502.

21.

Mercier

, & Sperber

(2011). Why do humans reason? Arguments for an argumentative theory. Behavioral and Brain Sciences , 34, 57–74. doi: 10.1017/S0140525X10000968

22.

Miller

, & Shanahan

(1999). The event calculus in classical logic – alternative axiomatisations. Electronic Transaction of Artificial Intelligence , 3, 77–105.

23.

Modgil

, & Caminada

(2009). Proof theories and algorithms for abstract argumentation frameworks. In G. Simari & I. Rahwan (Eds.), Argumentation in artificial intelligence (pp. 105–129). Springer.

24.

Modgil

, & Prakken

(2013). A general account of argumentation with preferences. Artificial Intelligence , 195, 361–397. doi: 10.1016/j.artint.2012.10.008

25.

Rahwan

, & Simari

(2009). Argumentation in artificial intelligence . Springer Publishing Company, Incorporated.

26.

Shanahan

(1997). Solving the frame problem – a mathematical investigation of the common sense law of inertia . MIT Press.

27.

Thielscher

(1999). From situation calculus to fluent calculus: State update axioms as a solution to the inferential frame problem. Artificial Intelligence , 111, 277–299. doi: 10.1016/S0004-3702(99)00033-8

28.

Thielscher

(2001). The qualification problem: A solution to the problem of anomalous models. AIJ , 131, 1–37.

29.

Q. B.

, & Foo

N. Y.

(2005). Reasoning about action: An argumentation-theoretic approach. Journal of Artificial Intelligence Research , 24, 465–518.

Reasoning about actions and change in argumentation

Abstract

Keywords

1. Introduction and motivation

Definition 2.1 interpretation

Definition 2.2 initiation-termination point

Definition 2.3 model

Example 2.5 domain D ′

Example 2.6 domain D ″

Example 2.7 domain D ‴

3. Argumentation formulation

Definition 3.1 background theory for D

Definition 3.2 argumentation program of D

Definition 3.4 attack

2 B ( D ) ∪ X ⊢ min l if and only if B ( D ) ∪ X ⊢ l and there does not exist X ′ ⊂ X such that B ( D ) ∪ X ′ ⊢ l .

Definition 3.6 admissibility

Definition 3.7 admissible extension

Example 6.1 domain D ′ ′ ′ ′

7. Conclusions and further work

Footnotes

Disclosure statement

Appendix 1. Lemma proofs

Appendix 2. Propositions proofs

Appendix 3. Theorems proofs

References

Example 2.5 domain $D^{'}$

Example 2.6 domain $D^{″}$

Example 2.7 domain $D^{‴}$

2
$B (D) \cup X ⊢_{min} l$ if and only if $B (D) \cup X ⊢ l$ and there does not exist $X^{'} \subset X$ such that $B (D) \cup X^{'} ⊢ l$ .

Example 6.1 domain $D^{''''}$