Reasoning about actions and change in argumentation

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 ¬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 everyt∈(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 ¬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 ofE.

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, AC, 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 T1 and T2, the notation T1<T2 indicates that time point T1 comes before time point T2 andT1≠T2.

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:

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, trueorfalse 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.

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.

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.

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, T2, to be strictly greater than T1, i.e. the restriction T1<T2, byT1⩽T2.

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=¬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 T1<T2 are two time points.

Figure 2.

Example domains.

In domain D we have an initiation point at time T1 and at time T2 we observe F. Models of language E, for domain D, require F to be true for all T>T1 whereas, for T′⩽T1 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 T2 with the observation that it does not hold, i.e. we have the domain D′ given by

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 T1 cannot be reconciled with the observation of ¬F at T2. Similarly, for the domain D″, given by

We have two possible models for times after time T1. In one F holds true for all such time points and in the other F is false for all time points after time T1. Hence if we extend this domain with either of the observations that F holds-at T2 or ¬F holds-at T2 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.

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.

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 inB(D).

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

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.

We note that included in the types of arguments are the two local generation arguments,NGB[f,t] and PGB[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.

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.

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.

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.

This is the standard definition of admissibility. A subset of arguments is admissible if it does not derive both HoldsAt(f,t) and ¬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.

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>T1 the strongest (and hence admissible) argument is for F to hold through a local generation argument at T1+1 and then by forwards persistence arguments at any other time after T1. Otherwise, from T2 onwards we can use the observation argument at T2 and forwards persistence arguments from this to support strongly F for times greater than T2. For T′⩽T1, we can have admissible arguments for F or its negation ¬F depending on the assumption we make at the initial time point. Note also that the backwards persistence arguments for F from T2 to some time point equal to or before T1 would not be stronger than the forwards persistence of ¬F starting from time 0 through an assumption argument for ¬F. Nor would it be stronger than the backwards negative generation argument for ¬F based on the initiation point T1 for F.

Figure 3.

Example domains and arguments.

Figure 4.

Examples.

For the domain D″, the strongest argument for all time points T⩾T2 is the observation argument for ¬F at T2 combined with a forward persistence argument from T2 to any such time point T. For times between T1 and T2, we have admissible arguments for either F or ¬F: at some time point Tk, T1⩽Tk<T2, the fluent F changes from true to false at Tk+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 ¬F holds for all times T, such that T1⩽T⩽T2. This captures the possibility that the generation of F at T1 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:

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 languageE.

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 ‘ ¬f holds-at t’.

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.

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.

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.

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.

For example consider the domain D″ (Example 2.6) where we observe F at time T1 and ¬F at time T2. Then given any time point Tk∈(T1,T2) this domain has admissible extensions E where F is derived for any time point between T1 up to Tk and ¬F is derived for all time points after Tk up to T2. The domain D″ does not have any language E models. But by interpreting time Tk 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.

Qualification extensions are therefore separated into two types. In the first case, the action occurrence of A at t1 is exogenously qualified failing to generate its effect and consequently in the whole of the interval, (t1,t2], ¬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 t2 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 ¬F) should hold at t2 but the opposite, i.e. ¬F (respectively F), is observed at t2. 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 t1 of the action occurrence. For example, consider the following domain description, also depicted in Figure 5.

Figure 5.

Domain QD1.

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 T1. 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 T1endogenously by the hypothesis that ¬L holds-at T1 and transfer the exogenous qualification of the domain to the earlier persistence of L from T0 to T1. Indeed, if we add inQD1 this t-proposition then the extended domain description does not anymore have an exogenous qualification extension for F between T1 and T2. 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.

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={¬L holds-at T1}, is a qualification explanation of the exogenous failure of action A at T1. Suppose now that we extend the previous Example 5.2 as follows:

Figure 6.

Qualification explanations for domain QD2.

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 T1 is given by ‘ ¬L holds-at T1’. The extended domain obtained from QD2 by adding this t-proposition does not anymore have an exogenous qualification extension of A at T1 because the potential initiation argument of F at T1 cannot be applied. But this extended domain, in the case where we have ‘ K holds-atT0’, will now have an exogenous qualification extension for L at T′ based on the new t-proposition that we have now added to the domain55 (see Figure 7).

Figure 7.

Qualification explanation H for domain QD2.

We can then explain this new exogenous qualification by adding the extra t-proposition, ‘ ¬K holds-at T′’, to the extended domain. This pushes the exogenous qualification back to the persistence of K from T0 to T′.

Then if also the initial state is such that ¬L is derived at T0, e.g. when ‘ ¬L holds-at T0’ is in the domain, there will be no exogenous qualification of A at T1 in the domain extended by both ‘ ¬L holds-at T1’ and ‘ ¬K holds-at T′’ (see Figure 8). Note that Figure 8 shows ‘ ¬L holds-at T1’ as an additional observation.

Figure 8.

Qualification explanation H′ for domain QD2.

Furthermore, the new t-proposition, ‘ ¬K holds-at T′’, is sufficient alone, without the need for the earlier explanation ‘ ¬L holds-at T1’, to explain the exogenous qualification of A at T1. In other words, starting from the explanation H={¬L holds-at T1} for the exogenous qualification of A at T1 we can replace (one of) its element(s), i.e. ‘ ¬L holds-atT1’, by an explanation, H′={¬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 atT1.

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 QD2 another explanation of the exogenous qualification of A at T1 would be possible if we had in the domain a known occurrence of the action B′ at some time point T″∈(T′,T1) (shown in Figure 6 with a dotted line). So let us assume that the domain QC2 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 T1. In other words, again starting from the explanation H={¬L holds-at T1} for the exogenous qualification of A at T1 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 t1 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 T1 (T1<T) based on L holds-at T. Then given H″=(H−{ L holds-at T })∪H′ one of the following holds:

Hence as we have seen above in the example domain QD2 H={¬L holds-at T1} can be replaced by H″={¬K holds-at T′} to either give a new qualification explanation of A at T1 in the case where E⊢¬HoldsAt(L,0) or when E⊢HoldsAt(L,0) the persistence of L from 0 to T1 is exogenously qualified inD∪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 ‘ ¬F holds-at T2’ 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(eu) and before(eu) 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(eu))ifInitiates(eu)

Holds(before(eu))ifTerminates(eu)

Such rules are analogous to the arguments {PGF[u,e], PFP[u,t;e]}, where t is any time point after the time of the event e and NGB[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:

In this domain the original EC concludes that there exists an end point i of the time period after(AF) 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. T1, and the time of B, i.e. T2 (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 Ti∈(T1,T2) 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 Ti between T1 and T2 that has terminated F and hence we cannot decide sceptically on F between T1 and T2. 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.