3.1.1 Data-driven approaches

Data-driven approaches adopt primarily a probabilistic and statistical view of information and widely rely on the enormous impact of machine-learning techniques in real-world applications. Although further classification can be made, for example, based on whether supervised or unsupervised methods are being used, one distinctive characteristic of data-driven activity recognition algorithms is their capacity to model uncertainty. They apply quantitative measures to evaluate plausibility of observed data, which renders them a popular solution for deciding how best to resolve contradictory sensor inputs. For instance, the problem of domestic activity recognition for a single user was approached by training multiple naive Bayesian models enhanced with ranking features and reliability factors to detect interleaved activities and unexpected sensor malfunction (Lu & Fu, Reference Lu and Fu2009). The same topic for multiple users was investigated with the application of Hidden Markov Models that can benefit the process of recognition taking into consideration temporal patterns of data (Singla et al., Reference Singla, Cook and Schmitter-Edgecombe2010).

The ability to learn from data sets is a big leverage for data-driven models for tackling conflicts at the sensor level, but often becomes their main point of weakness when attempting to address problems related to the recognition of high-level context. The performance of data-driven approaches is largely dependent on the availability of big amounts of—labelled or unlabelled—training data, thus compromising their capacity to offer scalable, reusable, and portable solutions. Due to the pragmatic difficulty to monitor the behaviour of different humans for a long period of time while they perform everyday activities, the models produced exclusively from data-driven techniques are often prone to domain-dependent performance, limiting their reusability and portability (Ye et al., Reference Ye, Dobson and McKeever2012).

Moreover, for abnormal or exceptional behaviours, such as for recognizing a heart attack, specialized equipment is needed (e.g. heartbeat/pulse sensors), which is often considered too intrusive for the daily activities of ordinary users. Without such equipment though it is difficult to train a typical AmI system properly, which is why, for instance, the applicability of certain approaches, like the one proposed by Jakkula et al. (Reference Jakkula, Crandall and Cook2009), is limited to frequent and predictable behaviours only. For less common situations, there is also the problem of overfitting, that is, when the training of a system is based on a small set of annotated data, which cannot be disregarded, as understood in the work of Lester et al. (Reference Lester, Choudhury, Kern, Borriello and Hannaford2005). Table 3 summarizes the main points of these approaches.

Table 3

Characteristic features of data-driven context recognition fields

3.1.2 Knowledge-based approaches

With knowledge-based approaches the rules of inference are modelled from first principles, rather than learned from raw data, and typically rely on formal specifications of their syntax and semantics, exploiting symbolic modelling and logic-based reasoning techniques. The expressive power, along with the capacity to verify the properties of their axiomatizations, are key advantages of these methodologies. Among knowledge-based approaches for context recognition, ontology-based models are arguably the most popular ones.

Ontology languages have rich and formal semantics that enables them to express complex knowledge using a wide set of primitives. These languages are utilized in modelling high-level contextual information, due to their ability to incorporate rich domain knowledge and heuristics in a machine processable way, thus offering a number of advantages in terms of expressiveness and quality of representation, automation and interoperability, composition and level of formality (Strang & Linnhoff-Popien, Reference Strang and Linnhoff-Popien2004; Bettini et al., Reference Bettini, Brdiczka, Henricksen, Indulska, Nicklas, Ranganathan and Riboni2010). The most elaborate recent studies in the field of ontology-based context recognition are probably Riboni and Bettini (Reference Riboni and Bettini2011b) and Springer and Turhan (Reference Springer and Turhan2009). Based on expressive languages (i.e. OWL 2 description logic (DL) and OWL DL, respectively) and decidable reasoners, they enable a context-aware system to detect inconsistencies, infer out activities occurring in the environment, and reproduce knowledge to model activities that share similar characteristics.

Although a multitude of pervasive computing systems have applied ontologies in modelling and reasoning on context knowledge (Preuveneers et al., Reference Preuveneers, den Bergh, Wagelaar, Georges, Rigole, Clerckx, Berbers, Coninx, Jonckers and De Bosschere2004; Ye et al., Reference Ye, Coyle, Dobson and Nixon2007; Patkos et al., Reference Patkos, Chrysakis, Bikakis, Plexousakis and Antoniou2010), most of them try to avoid the generation of conflicts relying on centralized solutions, whereas only few try to explicitly incorporate a solution for resolving conflicts about context within a distributed environment. An early example is Semantic Space (Wang et al., Reference Wang, Dong, Chin, Hettiarachchi and Zhang2004; Tan et al., Reference Tan, Zhang, Wang and Cheng2005), a context infrastructure for building smart spaces that investigates a variety of issues, such as context modelling, storage, inference, querying, and dynamic discovery of available context providers (wrappers). Context wrappers that obtain raw context information from various software and hardware sources transform them into semantic knowledge (markups) based on the system’s context model and store this knowledge in the KB. As an attempt to avoid potential conflicts generated by application-specific inferences, the higher-level context inferred from markups using general purpose reasoners is not explicitly stored in the KB; instead, when needed, specific rulesets are applied to obtain the required knowledge on-the-fly. While this approach may be sufficient for restricted domains, it can be problematic for the general AmI setting, where the different entities often need to obtain a ubiquitous and commonly agreed view of the current situation, in order to decide the best actions to perform and support humans accordingly.

Similar approaches that perform rule-based reasoning are also proposed by Fuchs et al. (Reference Fuchs, Hochstatter, Krause and Berger2005), as well as in the SOCAM system (Gu et al., Reference Gu, Pung and Zhang2005), where first-order logic (FOL) rules are applied to reason about the context data and resolve possible conflicts between data coming from different sources. Sets of rules are defined for the classification and evaluation of the quality of the observed context data.

One serious limitation and a key reason for the superiority of data-driven approaches over ontology-based ones is the limited support for temporal reasoning by ontology-based languages, according to Riboni et al. (Reference Riboni, Pareschi, Radaelli and Bettini2011). Nevertheless, temporal extensions of Semantic Web languages start to become popular (Gutierrez et al., Reference Gutierrez, Hurtado and Vaisman2007; Batsakis et al., Reference Batsakis, Stravoskoufos and Petrakis2011). More importantly, the inherent uncertainty of the information that exists in ubiquitous domains is difficult to handle at the pure symbolic level. While context recognition with respect to coherent incoming information is where most of the aforementioned studies are focussing on, the resolution of information that is conflicting has not been extensively considered so far. Indeed, Semantic Web-based approaches mostly deal with the problem of context disambiguation up to the point of acknowledging that certain parameters can be regarded as unknown.

The problem becomes more pronounced when the recognition task involves high-level complex situations, which ultimately leads in having to resolve the two other types of conflicts defined in Section 2.3, namely goal and action conflicts. For instance, Sadri (Reference Sadri2010) proposes an approach to recognize the intentions of a user by means of identifying plans using action graphs. Human intentions are often unclear, cannot be directly measured with physical devices, and may be the result of controversial desires. Committing to specific potential human intentions typically means for an agent to decide which of the conflicting knowledge to keep and which to drop. Considering the fact that often multiple and heterogeneous entities are employed in a smart space to perform such reasoning tasks, it becomes evident that dealing with the resolution of the conflicting viewpoints adopted will be inevitable in the next generation of smart systems. This aspect is starting to become an important research topic by considering the integration of techniques from other fields, such as argumentation, as it often requires extra logical information, as we will see in the following sections. Table 4 gives an overview of the main features of the approaches belonging to this category.

Table 4

Characteristic features of knowledge-based context recognition fields

3.1.3 Hybrid and other approaches

Although data-driven methods are currently the mainstream choice to activity recognition, with most effective being the supervised learning methods, numerous recent studies justify the attention that knowledge-based approaches have attracted over the last years. Yet, experience showed that both lines of investigation suffer from limitations that restrict the former to the lower levels of data abstraction and the latter to high-level knowledge. A seamless integration of methodologies for all levels is essential for the materialization of AmI objectives. Much of current research is working towards this end. The COSAR system (Riboni & Bettini, Reference Riboni and Bettini2011a), for example, loosely couples ontological OWL DL reasoning with statistical inferencing, where the latter predicts the set of possible activities without considering context parameters, in order to make the task manageable, while the former is applied to refine the results. In a similar style, the approach by Roy et al. (Reference Roy, Giroux, Bouchard, Bouzouane, Phua, Tolstikov and Biswas2011) applies possibility theory to model qualitatively incomplete knowledge, coupled with a DL representation of context to characterize the subsumption relation of actions, whereas the one by Helaoui et al. (Reference Helaoui, Riboni, Niepert, Bettini and Stuckenschmidt2012) presents a first attempt to use probabilistic DL for activity recognition. Still, these frameworks provide only limited or no support for temporal reasoning, inheriting some of the deficiencies of ontological reasoning in expressiveness, as discussed before.

A coupling of uncertainty with rich temporal relations is presented by Helaoui et al. (Reference Helaoui, Niepert and Stuckenschmidt2011) that uses Markov logic networks (MLNs), a statistical relational framework, to introduce uncertainty measures in logical statements to recognize simultaneous and nested activities. Skarlatidis et al. (Reference Skarlatidis, Paliouras, Vouros and Artikis2011) go even further to combine MLNs with the event calculus, a theory for reasoning about action and change, in order to exploit certain properties of the latter, such as the persistence of activities, and soften them as appropriate. Closely related to MLNs is the approach presented by Augusto et al. (Reference Augusto, Liu, McCullagh, Wang and Jian-Bo2008) that integrates confidence values to event-condition-action rules. The authors define a new syntax for expressing temporal relations among events, with Dempster–Shafer theory being used to assign confidence values to both antecedents and conclusions of rules. The belief rules they define can be used both to monitor a user’s interactions and to recognize exceptional situations.

3.1.4 Summarizing

Although the domain of AmI environments demands the generation of collective context-aware applications for group of users, where individual agents with personal goals seek collaborative execution of tasks (see, for instance, Muñoz Ortega et al., Reference Muñoz Ortega, Blaya, Clemente, Pérez and Skarmeta2010; Braga Silva et al., Reference Braga Silva, Ruiz and Loureiro2011; Muñoz et al., Reference Muñoz, Augusto, Villa and Botía2011), relevant literature on collective context conflict resolution is rather scarce. A large portion of contemporary approaches, summarized in Table 5, rely largely on centralized architectures, where a single reasoning entity handles conflict resolution. Those that deploy distributed settings, on the other hand, either try to avoid conflict occurrences (Muñoz Ortega et al., Reference Muñoz Ortega, Blaya, Clemente, Pérez and Skarmeta2010) or focus primarily on policy conflict detection, that is, establishing behaviour schemes that guarantee acceptable system states (Resendes et al., Reference Resendes, Carreira and Santos2014).

Table 5

Context modelling approaches

HMM=Hidden Markov Models.

The heterogeneity of the reasoning entities inhabiting smart spaces, as well as the processing load required to reason about context renders unreasonable the assumption that full perception is owed by all agents in a smart environment for describing the world state and the situation the users are involved in. Similarly, the need to combine context inference with actuation cannot be overlooked. As evidenced by Pecora et al. (Reference Pecora, Cirillo, Dell’Osa, Ullberg and Saffiotti2012), inference, sensing, and actuation must operate in close cooperation, in order to manage an effective integration of the cognitive capabilities of an intelligent system to be both context-aware and proactive. As the various smart entities need to interact and negotiate with one another, individually or collectively, in order to make decisions and synchronize their actions, conflicts inevitably emerge at the actuation level as well, a topic that only recently started to attract attention by current research in smart spaces, as we see in later sections and especially in Section 3.5.

3.2.1 Multi-context systems

This interesting problem was pursued by Giunchiglia (Reference Giunchiglia1993) and Giunchiglia and Serafini (Reference Giunchiglia and Serafini1994), who proposed MCS. In MCS, we deal with a collection of KBs ${\cal K}_{1} ,\:\,\ldots\,\:,\,{\cal K}_{n} $ . Each of the KBs ${\cal K}_{i} $ is a collection of formulae in its own language $${\cal L}_{i} $$ . The KBs of an MCS, commonly called contexts, represent different pieces of knowledge that are to be combined in a unified reasoning system. The contexts may represent different knowledge sources, KBs of communicating and cooperating agents, etc. The issue of multi-contextuality is captured by MCS in various ways. Not only with different languages that the contexts may possibly use, but also with the fact that each context may be respective to a different situation and, therefore, may contain diverse facts. Each context may even represent similar information differently. The combination of these assumptions renders MCS very flexible in modelling scenarios of diverse levels of knowledge heterogeneity, from completely homogeneous, up to ones involving largely heterogeneous knowledge sources/agents.

Logical semantics of the contexts is assumed, in the sense that we have either entailment or a proof system by which we can derive when a formula $$\phi \in {\cal L}_{i} $$ is true in ${\cal K}_{i} $ . The knowledge from different contexts is combined with bridge rules of the form $i:\phi \leftarrow j:\psi $ , meaning that if the formula $$\psi \in {\cal L}_{j} $$ is true in ${\cal K}_{j} $ then also the formula $$\phi \in {\cal L}_{i} $$ must be true in ${\cal K}_{i} $ . That is, bridge rules allow to derive consequences in one context (target context) based on premises previously proven in some other context (source context). Hence, bridge rules allow to characterize knowledge transfer between contexts, but also to translate from the language used in one context to that of another, which may be necessary given their possible heterogeneity. That is, given the bridge rule $i:\phi \leftarrow j:\psi $ , the recipient agent ${\cal K}_{i} $ upon receipt of information ψ from the sender agent ${\cal K}_{j} $ concludes ϕ, where ϕ represents the recipient’s own representation and interpretation of the senders statement ψ. A more general form of bridge rules allows more assumptions coming from different contexts on the right hand side (e.g. i:ϕ←j ₁:ψ ₁, … , j _n:ψ _n). Such rules fire if ψ _k is derived in ${\cal K}_{{j_{k} }} $ for all j _k.

Inference in MCS was first characterized by a proof theory, where bridge rules are used as calculus rules, that are combined with the local calculus of each context (Giunchiglia, Reference Giunchiglia1993; Giunchiglia & Serafini, Reference Giunchiglia and Serafini1994). A model theoretical semantics for MCS, called local mod el semantics, was introduced by Giunchiglia and Ghidini (Reference Giunchiglia and Ghidini1998) and Ghidini and Giunchiglia (Reference Ghidini and Giunchiglia2001). In this semantics, the model of a whole MCS is a collection of local models over which additional semantic constraints are asserted that are derived from the bridge rules. Local model semantics was particularly influential and formed the base for further research. We will now survey the main areas of research associated with MCS.

3.2.2 Distributed logics and distributed ontologies

Due to their capacity to combine logical reasoning over multiple knowledge sources, MCS have been used to formalize distributed FOL (Ghidini & Serafini, Reference Ghidini and Serafini1998), and later Distributed Description Logic (DDL) (Borgida & Serafini, Reference Borgida and Serafini2003). The latter approach, in particular, proved to be influential and sparked considerable interest in distributed ontologies, where the power of MCS is used either to make alignments between heterogeneous and possibly ambiguous ontologies that are to be combined in reasoning (Ghidini & Serafini, Reference Ghidini and Serafini2008; Ghidini et al., Reference Ghidini, Serafini and Tessaris2008), or to facilitate truly distributed inference (Serafini & Tamilin, Reference Serafini and Tamilin2004; Serafini et al., Reference Serafini, Borgida and Tamilin2005; Homola & Serafini, Reference Homola and Serafini2010). Both directions may be useful in AmI systems, in cases when more than one ontology is employed within a system, possibly governed by independent agents. Other related approaches to distributed ontologies include ${\cal E} $ -connections (Kutz et al., Reference Kutz, Wolter and Zakharyaschev2002, Reference Kutz, Lutz, Wolter and Zakharyaschev2003; Cuenca Grau et al., Reference Cuenca Grau, Parsia and Sirin2004), context OWL (Bouquet et al., Reference Bouquet, Giunchiglia, van Harmelen, Serafini and Stuckenschmidt2004), integrated DDLs, and package-based DLs (Bao et al., Reference Bao, Voutsadakis, Slutzki and Honavar2009). For a comparison of their expressive power, we refer the interested reader to Homola (Reference Homola2010: Ch. 6).

3.2.3 Non-monotonic multi-context systems

Logic-based MAS often rely on non-monotonic logics, in which the agents are able to reason with assumption, and derive new consequences from assumptions as long as they are not disproven. In order to plug non-monotonic contexts into MCS, it was desirable to enable also non-monotonic bridge rules. Such rules are of the from $i:\phi \leftarrow j_{1} :\psi _{1} ,\:\,\ldots\,\,j_{k} :\psi _{k} ,\,{\rm not}\ k{\rm {\plus}1:}\,\psi _{{k{\plus}1}} ,\:\,\ldots\,\,{\rm not}\,l\,{\rm :}\,\psi _{l} $ , and they allow to assert consequences in some context also based on the fact that some evidence is not proven in a source context of the bridge rule. For example, consider a situation in which the control agent is instructed to switch lights on during the night if a person is present and switch them off if a person is not present, using knowledge from the calendar and detector agents. While the former case is easily captured by a monotonic bridge rule (1), the latter is not; we need a non-monotonic bridge rule (2) for that:

(1) $$ctrl:lights\_on\leftarrow cal:night,\,det:preson\_\,present$$

(2) $$ctrl:lights\_off\leftarrow cal:night,\,{\rm not}\ det:preson\_\,present$$

Local model semantics was not sufficient to handle non-monotonic bridge rules. First steps towards such extensions were taken by Roelofsen and Serafini (Reference Roelofsen and Serafini2005) and Brewka et al. (Reference Brewka, Roelofsen and Serafini2007), but the semantics which later became generally accepted as a de facto standard for non-monotonic MCSs is the equilibrium semantics given by Brewka and Eiter (Reference Brewka and Eiter2007).

The expressive power of MCS is further increased in Managed Multi-Context Systems (mMCS) (Brewka et al., Reference Brewka, Eiter, Fink and Weinzierl2011). While so far we dealt with bridge rules, which always result in addition of a formula into the target context, mMCS introduce new operations, such as deletion of a formula, revision by a formula (in the sense of belief revision, cf. Section 3.3).

3.2.4 Contextual knowledge representation

While bridge rules allow to change and accommodate information transferred between contexts in arbitrary way, they do not suggest how this should be done. The reason is that MCS enable to connect KBs pertaining to different contexts, but do not provide any apparent means to capture the characteristics of these differing contexts. Already in his early work on contextual reasoning, McCarthy (Reference McCarthy1993) described transfer of information between contexts as knowledge lifting. This operation, which in MCS is implemented with bridge rules, was also studied under other names, such as knowledge push and pop (Benerecetti et al., Reference Benerecetti, Bouquet and Ghidini2000). It is understood that the knowledge is changed or adjusted during the transfer, in order to fit into the target context. What is more, these changes are influenced by the characteristics of the source and the target context, sometimes also called contextual meta knowledge. This meta knowledge may refer, for example, to a particular location, period of time, topic, etc., associated with a context. Once such meta information is assigned to contexts, contextual relations between them are studied, for example, one context preceding another in time, or, is associated with a broader topic, and so on. Thanks to these relations, contexts can be organized into a contextual space (Lenat, Reference Lenat1998; Benerecetti et al., Reference Benerecetti, Bouquet and Ghidini2001). Thus, for instance, the statement President(Bill_Clinton) associated with the context of United States in year 2000 may be changed to ExPresident(Bill_Clinton) when lifted into another context associated with some future period of time.

Contextualized Knowledge Repositories (CKR) (Serafini & Homola, Reference Serafini and Homola2012) can be seen as extension of MCS that addresses this issue. In CKR, users may initialize a number of contextual dimensions, with respective values and their relations. Such dimensional values are then assigned to contexts as a form of meta knowledge. Thus, we can have a context associated with, for example, US politics 2000, similarly as illustrated above. CKR relies on the mechanism of knowledge importing, which enables to reuse the knowledge of a context in another one. For example, in any context we can access the predicate President _{US,politics,2000}(), which will import relevant instances respective to President() from the context of US politics in 2000. Or to give a very simple example from the AmI domain, consider that we divide a smart home into separate rooms and we use a single dimension location, which takes values, such as kitchen, living room, etc. In the context of the living room, we can access the relevant users present in the kitchen as instances of UserPresent _kitchen. This way we transfer the knowledge from one context to another. This way, the user does not deal directly with bridge rules. Further versions of CKR extend the framework with more expressive meta theories than just simple dimensional properties (Bozzato & Serafini, Reference Bozzato and Serafini2013) and also with non-monotonic defeasible reasoning capabilities (Bozzato et al., Reference Bozzato, Eiter and Serafini2014). Similarly, DLs of context (Klarman & Gutiérrez-Reference Klarman and Gutiérrez-BasultoBasulto, to appear) allow to model a set of contexts and a meta theory that describes their relations, and information between contexts is then accessed using dedicated modal operators.

CKR and similar formalisms may particularly be useful to AmI applications to develop agents, which need to combine numerous amounts of knowledge imported from various sources. This can be information from sensors and other agents, or external knowledge available in the form of linked data data sets from the Web. Each piece of information can be associated with respective contextual metadata and then seamlessly combined in reasoning.

3.2.5 Conflict resolution and argumentation in multi-context systems

Apart from resolving sensory input conflicts, MCS can potentially be applied to resolve any types of conflicts that may arise between the agents in AmI environments. However, their main efficacy lies with resolving or avoiding contextual conflicts between the agents, as documented by the studies of Serafini and Homola (Reference Serafini and Homola2012), Bikakis and Antoniou (Reference Bikakis and Antoniou2010a), Benerecetti et al. (Reference Benerecetti, Bouquet and Ghidini2000), Ghidini et al. (Reference Ghidini, Serafini and Tessaris2008). It is also apparent from the foundational works that MCS were built upon Lenat (Reference Lenat1998).

MCS immediately allow for localized conflict resolution, that is, if a context ${\cal K}_{i} $ imports mutually conflicting information from some other contexts ${\cal K}_{j} $ , ${\cal K}_{l} $ , this can be resolved within ${\cal K}_{i} $ . For instance, we may choose to prefer the information from ${\cal K}_{j} $ and neglect the one from ${\cal K}_{l} $ , or vice versa, or we may decide to ignore it entirely, or to react in some other appropriate way.

A global view on inconsistency handling in MCS was studied by Eiter et al. (Reference Eiter, Fink, Schüller and Weinzierl2010b) who looked at MCS systems, which have no equilibrium and propose possible explanations why this happens. Confining local inconsistencies and preventing them from polluting the entire system was also one of the design goals of DDL (Serafini et al., Reference Serafini, Borgida and Tamilin2005) and CKR (Serafini & Homola, Reference Serafini and Homola2012).

The problem with localized conflict resolution is that two separate, autonomous agents may face the same conflict differently, choosing two different resolutions and act upon them. This may possibly disturb the overall coordination of agents in the system. Negotiating about conflicting knowledge between autonomous entities has been studied in the argumentation theory (see Section 3.5). Combining MCS with argumentation therefore seems to be a particularly promising direction in this respect. Already Parsons et al. (Reference Parsons, Sierra and Jennings1998) propose to use argumentation within an MCS-based agent architecture in order to resolve conflicts that arise between agents. More recently, Bikakis and Antoniou (Reference Bikakis and Antoniou2010a) study an application of MCS and argumentation in the context of AmI systems. They proposed so called contextual defeasible logic, built as an MCS with defeasible logic used inside contexts that uses argumentation to resolve conflicts in each context. Such an approach, however, is still localized: each context resolves the conflicts locally, based on its local preferences. Brewka and Eiter (Reference Brewka and Eiter2009) introduce argumentation context systems. This approach takes further steps towards reaching a certain level of agreement between the agents, in order to resolve mutual conflicts: MCS are enriched with so called mediators, which import relevant information from other contexts using bridge rules that resolve any conflicts relying on an argumentation semantics.

3.2.6 Towards applicability of multi-context systems in ambient intelligence

Some of the systems described above were also developed into working prototypes. Support for ${\cal E} $ -connections is implemented in the Pellet reasoner (Sirin et al., Reference Sirin, Parsia, Cuenca Grau, Kalyanpur and Katz2007). A distributed reasoner prototype for DDL was released under the name DRAGO (Serafini & Tamilin, Reference Serafini and Tamilin2005). It enables to combine and reason with OWL ontologies with expressive power up to ${\cal S}{\cal H}{\cal I}{\cal Q}$ DL (Horrocks et al., Reference Horrocks, Sattler and Tobies2000). It was developed as an extension of the Pellet reasoner (Sirin et al., Reference Sirin, Parsia, Cuenca Grau, Kalyanpur and Katz2007). The DDL framework and the DRAGO system were consecutively employed in tasks such as debugging of automatically generated ontology mappings (Meilicke et al., Reference Meilicke, Stuckenschmidt and Tamilin2007) and also providing reasoning support for manual ontology mapping revisions (Meilicke et al., Reference Meilicke, Stuckenschmidt and Tamilin2009).

An implementation of an Resource Description Framework (RDF)-based CKR was showed by Joseph and Serafini (Reference Joseph and Serafini2011). It is an extension of the OWLIM semantic data store (Bishop et al., Reference Bishop, Kiryakov, Ognyanoff, Peikov, Tashev and Velkov2011). A use case-based exploration of practical applicability of contextualized modelling with CKR was published by Bozzato et al. (Reference Bozzato, Ghidini and Serafini2013).

A working prototype of an MCS system was developed by Bögl et al. (Reference Bögl, Eiter, Fink and Schüller2010), in order to demonstrate the method for finding explanations for inconsistency in MCS by Eiter et al. (Reference Eiter, Fink, Schüller and Weinzierl2010b). This implementation is based on the tool named dlvhex (Eiter et al., Reference Eiter, Ianni, Schindlauer and Tompits2006).

Regarding the question of what role should MCS actually play in AmI applications, they were proposed as basis of agent architectures. Parsons et al. (Reference Parsons, Sierra and Jennings1998), Casali et al. (Reference Casali, Godo and Sierra2005), and Sabater et al. (Reference Sabater, Sierra, Parsons and Jennings2002) use MCS to develop the internal architecture of an agent. While Parsons et al. and Casali et al. essentially design an MCS implementation of the BDI architecture, Sabater et al. propose a more elaborate, modular architecture, which extends BDI. Other works (Cimatti & Serafini, Reference Cimatti and Serafini1995; Bikakis & Antoniou, Reference Bikakis and Antoniou2010a) use the notion of context to encapsulate an agent and exploit bridge rules to implement inter-agent exchange of knowledge. This enables to reason about the knowledge distributed in the whole MAS. While such an approach can be used within each agent to model its perception of the other agents’ knowledge, Parsons et al. (Reference Parsons, Sierra and Jennings1998) envisaged that bridge rules could potentially be exploited also for capturing the actual inter-agent communication and thus the MCS would take the role of a fully fledged multi-agent architecture.

Above, we highlighted the application of MCS in resolving conflicts, especially when referring to contextual conflicts. Recently, work has been done towards integrating also normative reasoning into MCS (Knorr et al., Reference Knorr, Slota, Leite and Homola2014), which can further enhance the capabilities of AmI systems relying upon the MCS architecture.

As mentioned above, Bikakis and Antoniou (Reference Bikakis and Antoniou2010a) studied contextual defeasible logic, which is capable of conflict resolution using argumentation. Basing the approach on MCS, they yield a fully distributed contextual platform suitable for AmI applications. The authors compared their solution with a centralized one (Bikakis & Antoniou, Reference Bikakis and Antoniou2010b). This approach was also experimentally evaluated by an implementation (Bikakis et al., Reference Bikakis, Antoniou and Hassapis2011), in which various conflict resolution strategies were studied. The communication complexity of these strategies was evaluated, shown to be ranging from polynomial to exponential, depending on their expressiveness. Further implementation details were given by Moawad et al. (Reference Moawad, Bikakis, Caire, Nain and Le Traon2013).

Yet another extension to MCS that may be potentially useful in AmI applications as it allows to deal with uncertainty is the possibilistic extension of MCS (dubbed poss-MCS, Jin et al., Reference Jin, Wang and Wen2012). This work is still preliminary, offering a basic framework with an equilibria-based semantics and an initial decision algorithm. The authors envisage work on more efficient algorithms in the future.

The works from the area of MCS and distributed knowledge representation are summarized in Table 6, where we compare them with respect to the local language of the contexts, type of interconnection between contexts, whether they are non-monotonic or not, and whether a practical implementation is known.

Table 6

MCS: comparison of approaches

MCS=multi-context systems; DFOL=distributed first-order logic; FOL=first-order logic; DL=description logic; mMCS=managed multi-context systems.

3.3.1 Classical belief change

Belief change is important in the context of conflict resolution, because it prevents inconsistencies (and therefore conflicts) from arising, by taking appropriate actions during changes, that is, during the process of adding into the KB the new knowledge that came from sensors or other agents. Thus, following the classification of Resendes et al. (Reference Resendes, Carreira and Santos2014), belief change falls under the ‘conflict avoidance’ type. A recent survey of the field (Fermé & Hansson, Reference Fermé and Hansson2011) shows that the problem is very challenging, both from the theoretical and the practical perspective.

In terms of the classification of conflict types appearing in Section 2.3, one could say that belief change can, in principle, deal with all types. However, belief change approaches are most suitable for contextual conflicts, as they were designed to deal with conflicts in agents’ models and beliefs. Some types of conflicts, namely goal and action conflicts, would require special variations or applications of belief change theories into languages that they were not in their original focus, for example, BDI models or action languages, whereas others (e.g. sensory input and domain and background knowledge conflicts) may require assumptions that are usually considered in subfields of belief change (rather than the mainstream), such as the assumptions considered in non-prioritized belief change. Further issues that restrict the applicability of belief change theories in AmI environments are provided in the analysis below.

As far as the theoretical perspective is concerned, the main challenges arise from the fact that it is often difficult, even in toy examples, to identify the appropriate result of a change operation, and several philosophical considerations need to be taken into account (such as the debate related to the adoption of coherence or the foundational viewpoint (Gärdenfors, Reference Gärdenfors1990), the use of belief sets or belief bases (Hansson, Reference Hansson1991), the differences between static-world and dynamic-world changes (Katsuno & Mendelzon, Reference Katsuno and Mendelzon1991), the semantics of minimal change (Makinson, Reference Makinson1987; Fuhrmann, Reference Fuhrmann1991; Hansson, Reference Hansson1996, and others). As already mentioned, most of the belief change field is focussing on understanding and resolving those challenges, that is, identifying the optimal way to resolve conflicts (logical inconsistencies) arising due to the introduction of new, conflicting information.

From the practical perspective, the main challenges are related to the fact that belief change algorithms are usually intractable. This is partly attributed to the types of languages considered (propositional and FOL) whose reasoning problems are intractable (at best). However, intractability should also be attributed to the inherent difficulty of the problem itself and the difficult challenges that it poses. Unfortunately, most of the works in belief change are not dealing with the practical aspects of the problem.

All the works related to belief change can be broadly classified in three different categories: postulation approaches, construction approaches, and explicit definition of concrete operators. These are defined in detail below:

• ∙ Postulation amounts to defining a set of formal requirements (postulates) that determine whether any given operator behaves in a ‘rational’ manner. Depending on the application at hand, the engineer can choose the exact semantics of the operator to use; as long as the postulates are satisfied, the operator is guaranteed to produce rational results and have certain desirable properties. Not surprisingly, there is no single set of postulates that works well for all cases (Flouris et al., Reference Flouris, Plexousakis and Antoniou2004; Ribeiro et al., Reference Ribeiro, Wassermann, Flouris and Antoniou2013), even though there are some proposals that are more widely accepted than others (Alchourrón et al., Reference Alchourrón, Gärdenfors and Makinson1985; Hansson, Reference Hansson1991).

• ∙ A set of postulates tells us the desired properties of a rational change operator, but gives us no clue as to how to construct one. The latter is the role of construction approaches, which essentially define a construction methodology for change operators satisfying a particular set of postulates. At the heart of such approaches is usually a representation theorem that proves that the constructed family coincides with the family of operators that satisfy the intended postulates.

• ∙ The explicit definition of concrete operators is a more direct approach to belief change, where a specific change operator is provided, often for use in a certain application or context. Such operators usually employ some kind of application-specific hard-coded or parameterized methodology to define the result, as this usually involves extra logical considerations. In addition, such operators are often shown to satisfy certain postulates or are based on some construction method.

The most seminal work on belief change is that of Alchourrón et al. (Reference Alchourrón, Gärdenfors and Makinson1985), a postulation attempt for the operators of contraction and revision. These postulates are often referred to as the AGM postulates by the initials of the authors. The AGM postulates formed the cornerstone of later approaches on belief change. Alchourrón et al. considered three operators: expansion, which is the trivial addition of information without regards to possible inconsistencies that could arise; revision, which deals with adding information consistently; and contraction, which deals with removing information.

These operators deal with the assumption of a static world, that is, in cases where a new observation, experiment, or other information forces us to change our conceptualization of the world; the world itself does not change, but our modelling of the world does. On the other hand, under the dynamic world assumption a belief change operation is caused by a change in the world itself; in this case, there is nothing wrong with our original conceptualization, but the world itself is evolving and we need to keep our conceptualization up-to-date. These two settings have different semantics, so another pair of operations (update and erasure), along with a set of postulates, were defined by Katsuno and Mendelzon (Reference Katsuno and Mendelzon1991). These are the dynamic counterparts of revision and contraction, respectively. Note that the dynamic setting is more relevant for the AmI domain.

The presence of postulates allowed to formally show a number of interesting results for these operators. In particular, the operations of contraction and revision were shown to be interdefinable in the presence of the postulates (Alchourrón et al., Reference Alchourrón, Gärdenfors and Makinson1985). Further results showed that update and erasure are also interdefinable, and revealed connections between the static-world operations and their dynamic-world counterparts (Katsuno & Mendelzon, Reference Katsuno and Mendelzon1991). In most contexts, including the AmI context, revision and update are the most relevant operators; however, due to contraction/erasure being simpler, and in the light of the above results, most works in the literature deal with contraction.

Obviously, the intuition behind the AGM postulates is not valid for all settings. The most controversial postulate in the AGM set was the postulate of recovery, which captures the informal principle of minimal change for contraction; this principle states that change operators should have the minimal possible effect (or ‘impact’) on the original KB. The recovery postulate was criticized as non-intuitive by several authors (Fuhrmann, Reference Fuhrmann1991; Hansson, Reference Hansson1996), and its status was the subject of several debates (e.g. Makinson, Reference Makinson1987). Alternative postulates were proposed, the most prominent one being the postulate of relevance (Hansson, Reference Hansson1991), which captured the intuition of minimality in a different way. Surprisingly, relevance, despite being proposed as a more intuitive alternative to recovery, was formally shown to be equivalent to recovery in the presence of the other postulates under the assumptions considered by the AGM work (Hansson, Reference Hansson1991).

All the above works (and most of the works related to belief change in general) are dealing with prioritized belief change, that is, they assume that the new information is unconditionally accepted (an assumption known as the principle of primacy of new information (Dalal, Reference Dalal1988) or the principle of success (Alchourrón et al., Reference Alchourrón, Gärdenfors and Makinson1985)), and this is also captured in one of the AGM postulates. The effects of dropping this assumption were studied in the subfield of non-prioritized belief change (Hansson, Reference Hansson1997; Hansson et al., Reference Hansson, Fermé, Cantwell and Falappa2001; Shakarian et al., Reference Shakarian, Simari and Falappa2014). Non-prioritized belief change is important for the AmI setting, where the cause of a conflict may be found in the input, for example, a faulty sensor reading (sensory input conflict), and not in the agent’s KB.

Most construction approaches are based on the AGM postulates, in the sense that they show that the resulting family of operators coincides with the family of operators satisfying the AGM postulates. One such construction was provided by Alchourrón et al. themselves in their original paper (Alchourrón et al., Reference Alchourrón, Gärdenfors and Makinson1985), but others were proposed as well (Alchourrón & Makinson, Reference Alchourrón and Makinson1985; Gärdenfors & Makinson, Reference Gärdenfors and Makinson1988; Grove, Reference Grove1988; Rott, Reference Rott1992; Hansson, Reference Hansson1994).

Works that explicitly propose a concrete belief change operator are rather scarce in the belief change literature. Unfortunately, this makes the application of belief revision methods to practical domains (like AmI) more difficult. Works that propose an explicit belief change operator are based on the idea of ‘closeness’ between (sets of) models: they view a KB as a set of models (i.e. those that the KB satisfies), and the result of a change application (e.g. contraction or revision) is the KB (i.e. set of models) that satisfies the required postulates, while being the ‘closest’ to the set of models satisfied by the original KB. The difference in these works stems from the different definition of ‘closeness’ between models. Two of the most important concrete operators that have been proposed are those of Dalal (Reference Dalal1988) and Chou and Winslett (Reference Chou and Winslett1994).

Another family of works, known as truth maintenance systems, provide explicit operators via a step-wise, formula-based approach, where a set of rules determines the facts to be added/removed from the KB in each step, towards reaching a KB satisfying a set of conditions (i.e. requirements that correspond to the considered postulates). Eventually, a state is reached where no more facts need to be added/removed to achieve the required properties, at which point the result is returned (Doyle, Reference Doyle1979).

Note that most of the above works are not touching practical issues such as efficient implementation of the related algorithms. This is an inherent problem of belief change methods, as they are dealing with logics which are intractable at best. However, most of the employed techniques are also problematic when used in less expressive logics, as they involve identifying minimal sets of formulae that cause conflicts and selecting one of them in an optimal manner, a process that is also (usually) intractable.

An additional drawback of belief change techniques, as related to their applicability in the AmI setting, is the fact that they do not deal with distributed, multi-agent settings, but consider scenarios where a single agent autonomously collects information from its environment and incorporates some information in its own KB, without regards to the existence (or not) of other cooperating (or competing) agents.

For these reasons, belief change techniques were only rarely considered in AmI settings so far, for example, by Bosse and Sharpanskykh (Reference Bosse and Sharpanskykh2010). Nevertheless, we argue that belief change techniques should be viewed (and used) for what they offer, namely a robust understanding of the process of change and evolution (which includes conflict resolution as an integral process) and a rich set of theoretical results that describe this process. Under this light, belief change literature could be re-used to understand and describe the intricacies of the conflict resolution process in AmI settings, but this would require revisiting existing belief change approaches under this prism.

3.3.2 Belief change in Semantic Web and other non-classical logics

The AGM approach, as well as most belief change approaches, are based on some relatively strong assumptions regarding the underlying language; this essentially limits their applicability to KBs represented using the so-called classical logics, which basically amount to propositional and FOL. For a complete list of these assumptions, as well as their effects on the supported languages, see the works of Alchourrón et al. (Reference Alchourrón, Gärdenfors and Makinson1985), Ribeiro et al. (Reference Ribeiro, Wassermann, Flouris and Antoniou2013), Creignou et al. (Reference Creignou, Papini, Pichler and Woltran2014), and Cuenca Grau et al. (Reference Cuenca Grau, Kharlamov and Zheleznyakov2012).

However, changes also happen in different settings, where other knowledge representation languages are used. For example, we could mention handling of changes in logic programming (Lloyd, Reference Lloyd1984), MCS (Giunchiglia, Reference Giunchiglia1993), Horn logic (Horn, Reference Horn1951), or data sets based on Semantic Web languages (such as DLs (Baader et al., Reference Baader, Calvanese, McGuinness, Nardi and Patel-Schneider2003) or OWL (OWL Working Group, 2009)).

For addressing dynamicity in logic programming, different approaches have been considered, some of which consider a non-standard set of postulates that is more suitable for the characteristics of logic programming and its different variants (Leite & Pereira, Reference Leite and Pereira1998; Alferes et al., Reference Alferes, Leite, Pereira, Przymusinska and Przymusinski2000; Leite, Reference Leite2002; Shakarian et al., Reference Shakarian, Simari and Falappa2014). In MCS, different variants have been proposed addressing changes in the knowledge itself (Gonçalves et al., Reference Gonçalves, Knorr and Leite2014b), or in the corresponding bridge rules (Gonçalves et al., Reference Gonçalves, Knorr and Leite2014a). The field of belief change for Horn KBs has been addressed in various papers (Delgrande, Reference Delgrande2008; Langlois et al., Reference Langlois, Sloan, Szörényi and Turán2008; Booth et al., Reference Booth, Meyer and Varzinczak2009, Reference Booth, Meyer, Varzinczak and Wassermann2011; Delgrande & Wassermann, Reference Delgrande and Wassermann2010; Zhuang & Pagnucco, Reference Zhuang and Pagnucco2010, Reference Zhuang and Pagnucco2012; Adaricheva et al., Reference Adaricheva, Sloan, Szörényi and Turán2011), where most approaches are again trying to adapt belief change ideas to apply for the reduced expressiveness of Horn KBs. A more general approach appears in Creignou et al. (Reference Creignou, Papini, Pichler and Woltran2014); in that work, the authors assume any given fragment of propositional logic where the models of the formulas are closed under a Boolean function (such as Horn logic), and propose a general approach for adapting standard operators (e.g. the revision operators presented in Dalal (Reference Dalal1988), Chou & Winslett (Reference Chou and Winslett1994)) in a way that the result of the revision remains in the fragment under consideration.

The case of changes in Semantic Web data sets and ontologies is much more relevant for this survey, as there is an increasing volume of works that employ Semantic Web languages to address AmI-related problems and/or exploit data in the linked data cloud for AmI applications (Celino et al., Reference Celino, Contessa, Corubolo, Dell’Aglio, Valle, Fumeo and Krüger2012; Emaldi et al., Reference Emaldi, Lazaro, Laiseca and Lopez-de Ipina2012; Lécué et al., Reference Lécué, Schumann and Sbodio2012; Daly et al., Reference Daly, Lécué and Bicer2013). For this reason, this subsection is mostly focussing on the dynamics of Semantic Web data sets. In that context, the problem has been addressed in the field of ontology evolution, where it has been argued that the adaptation of belief change methods and ideas in ontology evolution would provide several benefits (Flouris & Plexousakis, Reference Flouris and Plexousakis2006).

The idea of applying belief change theories in the ontological setting was introduced in a series of works that studied the feasibility and consequences of applying the AGM postulates in the ontological setting (Flouris et al., Reference Flouris, Plexousakis and Antoniou2004, Reference Flouris, Plexousakis and Antoniou2005, Reference Flouris, Huang, Pan, Plexousakis and Wache2006a; Flouris, Reference Flouris, Huang, Pan, Plexousakis and Wache2006a, Reference Flouris2006b; Flouris & Plexousakis, Reference Flouris and Plexousakis2006). Even though the AGM postulates can be easily reformulated to apply for ontological languages, it so happens that most DLs are not closed with respect to updates, in the sense that one can find examples where none of the ‘expected results’ (per the postulates) is expressible in the underlying DL.

Subsequent work by the same authors proposed new postulates, like optimal recovery (Flouris et al., Reference Flouris, Plexousakis and Antoniou2006b) or a generalized form of relevance (Ribeiro et al., Reference Ribeiro, Wassermann, Flouris and Antoniou2013), which share most of the good properties of the standard AGM postulates, while being more widely applicable. The latter (generalized relevance) was shown to be applicable for a large class of logics, which includes all compact logics (Ribeiro et al., Reference Ribeiro, Wassermann, Flouris and Antoniou2013). Given that most Semantic Web languages are compact, this work is very relevant for the AmI domain (and non-classical logics in general). Other works provided further insights on why certain Semantic Web languages cannot comply with belief change methods (that were developed for classical logics), resulting in the so-called inexpressibility results (Cuenca Grau et al., Reference Cuenca Grau, Kharlamov and Zheleznyakov2012). Other similar negative results appear in De Giacomo et al. (Reference De Giacomo, Lenzerini, Poggi and Rosati2007), Liu et al. (Reference Liu, Lutz, Miličić and Wolter2006), and Calvanese et al. (Reference Calvanese, Kharlamov, Nutt and Zheleznyakov2010).

These results motivated the search for ways to circumvent this problem. One approach used approximation techniques, that is, evolution approaches resulting to an ontology whose set of models is as close as possible to the desired one (De Giacomo et al., Reference De Giacomo, Lenzerini, Poggi and Rosati2007; Wang et al., Reference Wang, Wang and Topor2010; Qi et al., Reference Qi, Wang, Wang, Fu and Zhuang2015). Others chose to develop new DLs, which provably avoid such problems (Liu et al., Reference Liu, Lutz, Miličić and Wolter2006; De Giacomo et al., Reference De Giacomo, Lenzerini, Poggi and Rosati2009).

Some works adopt a more direct approach by proposing specific operators (inspired by belief change ideas), which are applicable for certain DLs. For example, Lee and Meyer (Reference Lee and Meyer2004) deal with ontologies represented in the ${\cal A}{\cal L}{\cal U}$ DL fragment; OWL ontologies are handled by Halaschek-Wiener and Katz (Reference Halaschek-Wiener and Katz2006); Qi and Du (Reference Qi and Du2009) propose three different revision operators for DLs; and Ribeiro and Wassermann (Reference Ribeiro and Wassermann2007) deal in general with knowledge representation formalisms that do not support negation (making it applicable to Resource Description Framework Schema (RDF/S) ontologies, as well as ontologies represented using certain DL fragments).

The maxi-adjustment algorithm (Benferhat et al., Reference Benferhat, Kaci, Le Berre and Williams2004) is an approach for repairing inconsistencies in stratified propositional KBs in a minimal manner; the works by Qi et al. (Reference Qi, Liu and Bell2006a, Reference Qi, Liu and Bell2006b), based on this approach, develop evolution algorithms that guarantee the validity of the result in the context of stratified ontologies. Note, however, that this line of work assumes that ontologies are expressed using disjunctive DLs (Meyer et al., Reference Meyer, Lee and Booth2005), an extension of standard DLs that supports disjunction of axioms.

Gutierrez et al. (Reference Gutierrez, Hurtado and Vaisman2006) consider the operator of erasure for RDF/S ontologies. Due to the simplicity of the underlying language, the main problem considered by Gutierrez et al. (Reference Gutierrez, Hurtado and Vaisman2006) is how to prevent the removed triple from reappearing in the ontology as the result of RDF/S entailment. The approach of Gutierrez et al. (Reference Gutierrez, Hurtado and Vaisman2006) addresses this problem using a technique inspired by belief revision.

The resolution of conflicts in the Semantic Web languages is a critical task for the AmI setting, as more and more works are employing such languages to address AmI-related problems. In addition, the wealth of information existing in the Semantic Web (as linked open data) is increasingly being exploited in various AmI applications, especially in the context of smart cities (Celino et al., Reference Celino, Contessa, Corubolo, Dell’Aglio, Valle, Fumeo and Krüger2012; Emaldi et al., Reference Emaldi, Lazaro, Laiseca and Lopez-de Ipina2012; Lécué et al., Reference Lécué, Schumann and Sbodio2012; Daly et al., Reference Daly, Lécué and Bicer2013). As a result, resolving the conflicts that appear in the underlying data, represented using Semantic Web languages, will become increasingly important, and one possible approach in this direction is the application of belief change technologies in such languages (as advocated by the works presented in this subsection).

The works related to the generalization of belief change approaches to Semantic Web (or other) languages are mainly focussing on the feasibility of such an application, and are thus not concerned with the tractability properties of the corresponding approach. More work is needed in this respect to verify that these approaches can scale when applied to practical situations. Therefore, as with classical belief change approaches, one should view the works presented here as a means to understand the process of change and conflict resolution in representation languages that are useful in AmI settings.

3.4.1 Ontology evolution

Ontology evolution deals with the process of modifying an ontology in response to a certain change in the domain or its conceptualization (Flouris et al., Reference Flouris, Manakanatas, Kondylakis, Plexousakis and Antoniou2008), and its main objective is to prevent conflicts from appearing in the ontology during the evolution process (where the term ‘ontology’ refers to both the data and the schema). Thereby, ontology evolution falls under conflict avoidance with respect to the classification of conflicts given by Resendes et al. (Reference Resendes, Carreira and Santos2014). Given the popularity of ontology-based methods in the AmI field, ontology evolution is highly relevant for this survey, as it could be directly adapted for conflict resolution in smart spaces. Recent surveys on ontology evolution were done by Flouris et al. (Reference Flouris, Manakanatas, Kondylakis, Plexousakis and Antoniou2008) and Zablith et al. (Reference Zablith, Antoniou, d’Aquin, Flouris, Kondylakis, Motta, Plexousakis and Sabou2015).

As with belief change, all the conflict types appearing in Section 2.3 are relevant for ontology evolution. However, since many of the approaches are dealing with the data part of the ontology, they are only applicable to sensory input and contextual conflicts, but some of the more recent works are also dealing with the schema part, making them applicable for the other types of knowledge conflicts as well.

In ontology evolution, two different types of conflicts are considered, namely incoherency and inconsistency. Incoherency appears when a class is unsatisfiable (Flouris et al., Reference Flouris, Huang, Pan, Plexousakis and Wache2006a). Inconsistency is closer to the notion of logical inconsistency and appears when an ontology has no models (Flouris et al., Reference Flouris, Huang, Pan, Plexousakis and Wache2006a).

In early approaches to ontology evolution, the application of changes upon ontologies was performed manually by the editor/curator using ontology editors (e.g. Protégé (Noy et al., Reference Noy, Fergerson and Musen2000, Reference Noy, Chugh, Liu and Musen2006), OilEd (Bechhofer et al., Reference Bechhofer, Horrocks, Goble and Stevens2001)) and reasoners used to pinpoint conflicts. Later on, more specialized tools appeared, which can identify the changes to be performed to guarantee validity, possibly with some user interaction. User interaction may be direct, through an intuitive interface (Lam et al., Reference Lam, Sleeman and Vasconcelos2005b), or indirect through parameters, like evolution strategies (e.g. Stojanovic et al., Reference Stojanovic, Maedche, Motik and Stojanovic2002). Examples of such tools are KAON (Gabel et al., Reference Gabel, Sure and Voelker2004), OntoStudio (formerly OntoEdit, Sure et al., Reference Sure, Angele and Staab2003), and ReTax++ (Lam et al., Reference Lam, Sleeman and Vasconselos2005a, Reference Lam, Sleeman and Vasconcelos2005b). It is obvious that such approaches cannot be applied in the AmI setting, because it is assumed that agents should resolve conflicts (and inconsistencies/incoherencies) in an automated manner.

RUL (Magiridou et al., Reference Magiridou, Sahtouris, Christophides and Koubarakis2005) is a declarative language for data updating in RDF/S ontologies, which takes into account RDF/S semantics, as well as a fixed set of constraints on the resulting RDF/S ontology. For every change requested by the user, the language automatically checks whether the application of said change would cause any problems related to the above constraints (taking into account RDF/S semantics), and, if so, it automatically adds further changes (side-effects) to guarantee that the end result will have no conflicts.

In EvoPat (Rieß et al., Reference Rieß, Heino, Tramp and Auer2010), the identification of conflicts is performed using SPARQL queries; each conflict is associated with one or more SPARQL Update statements that resolve it. The same idea of identifying conflicting patterns (in various ways) and resolving them (in a user-defined way, or using some hard-coded, predetermined process) was employed in various works (e.g. Roger et al., Reference Roger, Simonet and Simonet2002; Liu et al., Reference Liu, Lutz, Miličić and Wolter2006; Djedidi & Aufaure, Reference Djedidi and Aufaure2009, Reference Djedidi and Aufaure2010).

A formal method for applying changes in the presence of custom validity rules was proposed by Konstantinidis et al. (Reference Konstantinidis, Flouris, Antoniou and Christophides2008a, Reference Konstantinidis, Flouris, Antoniou and Christophides2008b) and Flouris et al. (Reference Flouris, Konstantinidis, Antoniou and Christophides2013), where the incorporation of changes is performed automatically, taking care that the validity rules are not violated at the end of the process (see also the discussion on invalidity in Section 3.4.2).

Ontology evolution approaches are, by conception, meant to be applied in real settings where ontologies are used, and often the intended application area is the Semantic Web. As a result, scalability and tractability is generally an objective for these approaches, and sometimes applicability and formal rigour are sacrificed to achieve good tractability properties. The main drawback for many evolution approaches is the fact that they rely on manual or semi-automatic processes, which makes them unsuitable for the AmI setting. Therefore, further research efforts towards a fully automated ontology evolution process would be highly relevant for AmI.

Table 7 shows the works related to the evolution of ontologies and includes works presented in this section, as well as related works presented in Section 3.3.2. The referenced works have been grouped according to their properties. The second column in the table mentions the language(s) that the corresponding works consider (OWL, RDF/S, various types of DLs, or arbitrary logics). The third column specifies the properties that the corresponding method respects during evolution: some works support the definition of custom (provided by the user) constraints to be respected during evolution, whereas others focus on preserving coherence and/or consistency. Finally, the fourth column determines the resolution method, which can be manual, semi-automatic, or automatic; approximate; or inspired by/reusing other methodologies/fields, such as belief change approaches or the maxi-adjustment algorithm.

Table 7

Summary of ontology evolution approaches

RDF/S=Resource Description Framework Schema; DL=description logic.

3.4.2 Ontology debugging

The field of ontology debugging addresses conflicts after they have already appeared in the KB (cf. Section 2.3). In contrast to ontology evolution, the reason that caused the conflict is unknown (or irrelevant) in this field, that is, it is not considered during the resolution of the conflict. Works in ontology debugging are not only dealing with inconsistencies and incoherencies, but also with invalidities, which are violations of one or more custom validity rules that express application- or domain-specific requirements on the underlying ontology (Roussakis et al., Reference Roussakis, Flouris and Christophides2011). For a related survey see the one by Flouris et al. (Reference Flouris, Manakanatas, Kondylakis, Plexousakis and Antoniou2008).

Several recent works have acknowledged the need for imposing custom, application-specific or user-defined requirements (in the form of validity rules) upon ontologies (Serfiotis et al., Reference Serfiotis, Koffina, Christophides and Tannen2005; Lausen et al., Reference Lausen, Meier and Schmidt2008; Motik et al., Reference Motik, Horrocks and Sattler2009; Tao et al., Reference Tao, Sirin, Bao and McGuinness2010). Thus, identifying and resolving cases where an ontology violates the imposed requirements, either after a reckless change or for other reasons, is paramount for the seamless functionality of the associated applications. Such validity rules are also important for smart spaces, where agents can employ commonsense background knowledge (in the form of rules) to improve their performance in supporting the user in the smart space, for context recognition, or to overrule unreasonable data (e.g. sensor readings); such rules should be respected by the agents’ KB at all times.

Validity rules are often encoded as part of the ontological schema (e.g. as OWL rules (Horrocks et al., Reference Horrocks, Patel-Schneider, Bechhofer and Tsarkov2005)); however, in some cases the ontological language is not rich enough to encode the necessary rules, so another ‘rule layer’ is considered on top of the ontology, encoded in some more expressive logical language. In both cases, an important invariant in ontology debugging is that the rules are considered fixed and do not change. Thus, in the former case (rules in the schema) ontology debugging only applies changes in the data part (instance level) of the ontology to resolve a conflict, whereas in the latter (rules in an external layer) it may affect both the schema and the data. Due to this invariant, ontology debugging is not suitable for resolving conflicts related to the rule level, which typically encodes (parts of) the domain and background knowledge.

Regardless of the type of conflicts considered (coherency, consistency, or custom validity rules), ontology debugging comprises of two different stages. The first, called diagnosis, refers to the identification of the conflicts, as well as the possible causes behind such conflicts; the second, called repair, refers to the determination of the best way to resolve the identified conflicts. Essentially, diagnosis provides the necessary information for repair to resolve the conflicts.

Standard reasoners are of little help for the task of diagnosis, because, even though they can identify the existence of a contradiction, they provide little support for resolving and eliminating it (cf. Section 2.3, the solvability dimension (Resendes et al., Reference Resendes, Carreira and Santos2014)). On the other hand, manual identification of the sources of a conflict (contradiction) is not feasible, especially in a smart space setting. Therefore, a more powerful approach is required in order to identify the part(s) of the ontology that led to the contradiction (Flouris et al., Reference Flouris, Manakanatas, Kondylakis, Plexousakis and Antoniou2008).

Repairing is even more difficult, because, in addition to identifying the causes of a conflict (diagnosis), one must determine the ‘optimal’ (under some measure of optimality) way to resolve such a conflict. This process is very similar to the process of identifying the ‘minimal change’ in the belief change/ontology evolution context, and often requires some kind of user feedback, as the choice involves non-logical considerations. Due to this fact, most of the works related to the field of ontology debugging actually deal with the problem of diagnosis only, leaving the problem of repairing to human experts. However, this is not enough for most AmI applications.

Many approaches use some tableau-based algorithm for diagnosis. One of the most influential approaches was given by Schlobach and Cornet (Reference Schlobach and Cornet2003), where a tableau-based algorithm for identifying the causes of an incoherency for a specific DL was presented. Similar tableaux-based algorithms for diagnosis were also proposed (Wang et al., Reference Wang, Horridge, Rector, Drummond and Seidenberg2005; Meyer et al., Reference Meyer, Lee, Booth and Pan2006; Plessers & Troyer, Reference Plessers and De Troyer2006). In all these techniques, diagnosis reports the axioms responsible for a conflict; a more fine-grained approach would be to identify the parts of the axioms that are responsible for the conflict (see the works of Kalyanpur et al. (Reference Kalyanpur, Parsia, Sirin and Cuenca Grau2006) and Lam et al. (Reference Lam, Sleeman, Pan and Vasconcelos2008) for such approaches).

As already mentioned, the process of repairing usually employs some kind of user interaction. In some cases (e.g. in ontology editors such as Protégé (Noy et al., Reference Noy, Fergerson and Musen2000, Reference Noy, Chugh, Liu and Musen2006), or in the case of reasoners, such as Stardog (http://stardog.com/), or QuOnto (Acciarri et al., Reference Acciarri, Calvanese, De Giacomo, Lembo, Lenzerini, Palmieri and Rosati2005)), this interaction is direct, that is, the user is presented with the conflicts (possibly with some support regarding the results of the diagnosis) and asked to manually resolve them. In the ORE tool (Lehmann & Bühmann, Reference Lehmann and Bühmann2010) a similar interactive approach is used, where the system presents the user with a set of suggestions for resolving the conflict. Such approaches are not useful in the AmI context, where agents need to decide how to resolve conflicts in an automated manner.

Automated approaches for repairing either employ ad hoc solutions for resolving conflicts (e.g. Masotti et al., Reference Masotti, Rosati and Ruzzi2011; Chortis & Flouris, Reference Chortis and Flouris2015), or take advantage of some kind of implicit user feedback (e.g. Meyer et al., Reference Meyer, Lee and Booth2005; Qi & Pan, Reference Qi and Pan2007; Roussakis et al., Reference Roussakis, Flouris and Christophides2011). For example, Qi and Pan (Reference Qi and Pan2007) and Meyer et al. (Reference Meyer, Lee and Booth2005) take into account external information related to the stratification of knowledge to identify the optimal resolution option, whereas Roussakis et al. (Reference Roussakis, Flouris and Christophides2011) relies on user feedback that is provided at input time via a set of user-defined ‘preferences’. These preferences act as high-level declarative specifications for the ‘ideal’ repair, based on which the system is able to automatically determine the optimal resolution of conflicts in order to produce a repair that is as close as possible to the ‘ideal’ one, as specified by the preferences. The same technique, using preferences based on metadata (such as trust or provenance) was applied in a real setting by Flouris et al. (Reference Flouris, Roussakis, Poveda-Villalon, Mendes and Fundulaki2012).

In an effort to achieve scalability, some works consider ontological languages with a limited expressiveness, such as $DL{\minus}Lite_{{\cal A}} $ (a tractable DL). Examples include the works of Masotti et al. (Reference Masotti, Rosati and Ruzzi2011) and Chortis and Flouris (Reference Chortis and Flouris2015), both of which provide algorithms for automated repairing of $DL{\minus}Lite_{{\cal A}} $ KBs.

A rather original approach for repairing, proposed by Moguillansky et al. (Reference Moguillansky, Rotstein and Falappa2008), employs ideas from argumentation frameworks to identify and resolve conflicts. In particular, a conflict is defined as an ‘attack’ between arguments (which can be easily identified using logical reasoning), whereas repairing consists in determining accepted/rejected ontological axioms based on the standard acceptability semantics of argumentation frameworks. This approach can be used both for ontology evolution and for ontology debugging.

An alternative approach to repairing, originally proposed for relational databases, but also applied in the ontological setting, is consistent query answering (Arenas et al., Reference Arenas, Bertossi and Chomicki1999). Consistent query answering advocates the use of query rewriting techniques that allow ‘hiding’ the conflict from the user by providing consistent answers over a conflicting data set. This is an indirect approach to repairing, as the conflicts are allowed to persist in the data set, rather than being resolved.

In the context of relational databases, consistent query answering approaches have been proposed in various works dealing with different classes of constraints, mainly key constraints (e.g. Chomicki & Marcinkowski, Reference Chomicki and Marcinkowski2005; Grieco et al., Reference Grieco, Lembo, Rosati and Ruzzi2005; Haase et al., Reference Haase, van Harmelen, Huang, Stuckenschmidt and Sure2005; Wijsen, Reference Wijsen2009). Recently, there has also been some relevant research for KBs expressed in DLs, such as the works of Lembo et al. (Reference Lembo, Lenzerini, Rosati, Ruzzi and Savo2010, Reference Lembo, Lenzerini, Rosati, Ruzzi and Savo2011), which deal with different variants of inconsistency-tolerant semantics to reach a good compromise between expressive power of the semantics and computational complexity of inconsistency-tolerant query answering. In Martinez et al. (Reference Martinez, Ariel, Deagustini, Falappa and Simari2014) the Datalog^± language (Cali et al., Reference Cali, Gottlob and Lukasiewicz2009) is extended with defeasible semantics. This essentially allows the incorporation of inconsistency-tolerant semantics for Datalog^± ontologies.

Ontology debugging approaches are also concerned with the scalability properties of the proposed algorithms. In most of the works presented (both for repairing and for consistent query answering), one can find experimental results, as well as theoretical analyses of their computational complexity. Of course, the scalability of approaches for ontology debugging is greatly depending on the expressiveness of the considered underlying language and integrity constraints; when considering expressive DLs or expressive integrity constraints, the problem of diagnosis/repair is inherently intractable.

Ontology debugging is very relevant to the AmI setting where agents should make sure that their KBs satisfy the imposed validity rules at all times; this is especially relevant for recognizing the context and for reacting appropriately to its changes. For the same reason, ontology debugging is mostly useful for contextual conflicts, but also for the other types of conflicts which are identifiable through a set of rationality constraints (validity rules) based on the background knowledge about the domain.

Table 8 shows the works related to the problem of ontology debugging, grouped according to their properties. The table shows the supported language for the input KB per case, the type of problem considered (diagnosis, diagnosis, and repair, or consistent query answering), as well as some details on the methodology used (manual, semi-automatic, automatic, etc.).

Table 8

Summary of ontology debugging approaches

RDF/S=Resource Description Framework Schema; DL=description logic.

3.5.1 Abstract argumentation

The most influential work on abstract argumentation is by Dung (Reference Dung1995), where abstract argumentation frameworks (AFs) have been introduced. Abstract argumentation does not consider any structure of arguments or conditions defining the conflict (attack) between arguments.

An argument in abstract argumentation is an atomic term that is understood as anything that a rational agent can argue with/about and the attack between arguments is an arbitrary binary relation representing any inconsistency between these arguments. The advantages of this abstract approach are simple elegant semantics and generality. The main issue in abstract argumentation is to determine which arguments are accepted, which are rejected, and which are left undecided. Generally, if an argument a attacks an argument b then arguments a and b cannot be accepted together, and b is rejected whenever a is accepted.

Intuitively, an argumentation semantics prescribes a set of sets of arguments, called extensions, to each argumentation framework. Different semantics have been proposed by Dung (Reference Dung1995), based on the notion of admissibility, and several of them have been defined with different motivations in mind. An argument a is defended by a set of arguments S if S attacks all arguments attacking a. An extension is said to be admissible if it is conflict free (i.e. it does not contain any pair of attacking arguments) and defends all its members. For example, given the AF shown in Figure 3, the admissible extensions are $\emptyset$ , {a}, {c}, {d}, {a, c}, and {a, d}.

Figure 3

Nodes denote arguments and arrows denote the attack relation (e.g. a attacks b)

In our example, not all admissible sets are relevant as an intended meaning of the argumentation framework. Various semantics based on admissibility have been proposed by Dung (Reference Dung1995), and others, with the aim to capture the notion of relevant extensions. For example, admissible extensions {c}, {d} do not provide intuitive meaning, since they do not contain all the arguments they defend (argument a namely). The semantics requiring such property is called complete. There are three complete extensions {a}, {a, c}, {a, d} for the given AF. As it can be seen, complete extensions can be included in one another resulting in two different semantics: skeptical and credulous. The skeptical semantics is the most careful one, where arguments cannot be defended by themselves. The extension corresponding to the skeptical semantics is called grounded and we can see that {a} is the grounded extension. On the other hand, there are two credulously accepted extensions {a, c}, {a, d} called preferred. The last semantics proposed by Dung (Reference Dung1995), is called stable and requires all arguments outside of an extension to be attacked by an argument in the extension. The only stable extension of our AF is {a, d}. Note, however, that stable semantics is not always defined—there are AFs with no stable extensions, such as the AF consisting of only one self-attacking argument. As sometimes this is unsatisfactory, a weaker semantics called semi-stable have been defined (Caminada et al., Reference Caminada, Carnielli and Dunne2012), which is universally defined and coincides with the stable semantics if stable extensions exist.

Given an arbitrary complete extension E, a justification status in, out, undec can be assigned to arguments (Caminada & Gabbay, Reference Caminada and Gabbay2009). Intuitively, an argument is:

• ∙ in if it is defended by E;

• ∙ out if it is attacked by E;

• ∙ undec otherwise.

Arguments that are in are included in the extension and are always accepted. Rejected arguments (status out) are attacked by the extension and, consequently, are never accepted. Finally, the acceptance of undecided arguments (status undec) is not determined, since they are attacked by undecided arguments only.

Argumentation can be described as a discussion between two players: a proponent trying to justify his claim and an opponent who counter-argues. The inclusion of an argument in some of the semantics described above can be decided procedurally by creating and evaluating such discussions, called argument games. Intuitively, a player wins a discussion if she has the last word.

Dung (Reference Dung1995) also studied the relationship of argumentation with other non-monotonic formalisms, such as default logic (Reiter, Reference Reiter1980), inductive defeasible system (Pollock, Reference Pollock1995), stable (Gelfond & Lifschitz, Reference Gelfond and Lifschitz1988), and well-founded (Van Gelder et al., Reference Van Gelder, Ross and Schlipf1988) semantics for logic programming. Furthermore, significant research has been conducted on studying proof theories (Modgil & Caminada, Reference Modgil and Caminada2009), and complexity analysis (Dunne & Wooldridge, Reference Dunne and Wooldridge2009) for the varying semantics. In Table 9 we summarize the complexity results of Dunne and Wooldridge (Reference Dunne and Wooldridge2009), for different abstract argumentation semantics and for both the credulous and the skeptical case (the trailing ‘-c’ means that the given problem is complete for the given class).

Table 9

Complexity of abstract argumentation

Dunne and Wooldridge (Reference Dunne and Wooldridge2009).

Various extensions of abstract AFs have been studied. For instance, Dung’s AF only features the single relation attack between arguments—the attack relation. But when a ₁ attacks a ₂, and a ₂ attacks a ₃, then in a sense a ₁ indirectly and implicitly supports a ₃. However, as argued by Cayrol and Lagasquie-Schiex (Reference Cayrol and Lagasquie-Schiex2009), in certain application domains also explicit support relations between arguments may be present. To capture this, they present Bipolar AFs featuring both attack and support.

Abstract dialectical frameworks (ADF), a generalization of abstract AFs, were introduced by Brewka and Woltran (Reference Brewka and Woltran2010). Acceptance conditions are added to arguments in ADF. They allow to specify different types of interactions between arguments. Both attack and support are expressible in ADF. ADFs are characterized by Brewka and Woltran (Reference Brewka and Woltran2010) in terms of dependency graphs together with acceptance conditions.

Assumption-based frameworks (ABF) were introduced in Bondarenko et al. (Reference Bondarenko, Dung, Kowalski and Toni1997). ABFs understand non-monotonic reasoning as a deduction from assumptions. The structure of ABF is an abstraction of well-known non-monotonic formalisms and it was shown that many of them are instances of ABF. Argumentation semantics were applied to (sub)sets of assumptions. It was shown that traditional semantic characterizations of non-monotonic theories, for example, stable models of logic programs or extensions of default theories, correspond to argumentation semantic characterizations. Assumption-based argumentation (Dung et al., Reference Dung, Kowalski and Toni2009) has been later developed over the basis of ABF.

Other extensions of AFs include the addition of preferences (Amgoud & Vesic, Reference Amgoud and Vesic2011), or weighted attacks (Dunne et al., Reference Dunne, Hunter, McBurney, Parsons and Wooldridge2011; Coste-Marquis et al., Reference Coste-Marquis, Konieczny, Marquis and Ouali2012) into the context of abstract argumentation. This is often required by various application domains, and therefore it considerably extends the flexibility and applicability of abstract argumentation.

3.5.2 Structured argumentation

For certain application areas Dung’s approach may be too abstract to be directly used in practice. Take, for example, the legal domain, where problems can be naturally formalized in a logical language comprising facts, implications, or rules, etc. In abstract argumentation, the arguments are just atomic ‘letters’ but here the formulae are more complex and the notion of attack will depend on their structure and the semantics of the language.

The usual methodology in order to employ argumentation in such cases is to instantiate an AF (e.g. Dung’s AF). This is often done by defining the following four notions: a logical language, the structure of an argument, the attack relation, and the status of an argument (Prakken & Vreeswijk, Reference Prakken and Vreeswijk2002). Each one of these notions can be expressed by means of the previous. The status of an argument depends on the notion of arguments and the attack relation. The attack relation depends on the notion of arguments and the underlying logical language. The structure of arguments is defined with respect to the underlying logical language.

Once the instantiation is done, extensions may be computed treating the result as abstract AF (e.g. using one of Dung’s semantics). The semantics of the structured argumentation framework is then derived from the arguments present in the extensions.

As for the logical language, classical propositional language may be used (Besnard & Hunter, Reference Besnard and Hunter2001). More often the language of Defeasible Logic Programming (DeLP) (García & Simari, Reference García and Simari2004) or other logic programming or defeasible logic languages (Prakken & Sartor, Reference Prakken and Sartor1997; Governatori et al., Reference Governatori, Maher, Antoniou and Billington2004; Prakken, Reference Prakken2010) are considered. If the system uses a language of classical logic (Besnard & Hunter, Reference Besnard and Hunter2001) then we speak of deductive argumentation. On the other hand, the languages that feature both strict and defeasible rules are also called defeasible theories (Caminada & Amgoud, Reference Caminada and Amgoud2007).

The language of DeLP is particularly interesting, as its semantics is usually derived from argumentation frameworks. Two kinds of rules are distinguished in the language of DeLP: strict (→) and defeasible (⇒). While strict rules are used to represent some kind of deductive reasoning (i.e. whenever the preconditions hold, we accept the conclusion), defeasible rules formalize tentative, uncertain knowledge, where the validity of the precondition of a rule usually (but not necessary) implies the validity of the head of the rule. Thus, defeasible rules can be defeated, in light of some conflicting evidence.

Let us demonstrate this on a very simple example from the intelligent household domain. We want to encode the following rules: the heating is generally turned on before the user usually arrives (for simplicity, assume that arrival_time becomes true at the right moment). However, if based on the events scheduled in the user’s calendar we know that the user is having a meeting in a remote location (for simplicity, in_meeting is true in such case) then the first rule should be overridden and the heating is not turned on). We may encode such rules in a DeLP program, specifically the first two rules below:

(3) $$arrival\_time\Rightarrow heating\_on$$

(4) $$\,\quad in\_meeting\to\neg heating\_on$$

(5) $$\quad \ \,\, \qquad \qquad \to arrival \_time$$

(6) $$\qquad\ \ \,\, \qquad \to in\_meeting$$

Rule (3) is defeasible, it represents knowledge that is usually valid. Rule (4) is strict, it represents knowledge that is always valid. There are also two (strict) facts (5–6) representing that both arrival_time and in_meeting are true in the current instance. In DeLP, arguments are actually constructed through the chaining of the rules. For example, in the program above, we may construct the following arguments: A ₁=[→arrival_time], A ₂=[→in_meeting], A ₃=[A ₁⇒heaing_on], and A ₄=[A ₁, A ₂→¬heating_on]. We can see that arguments have an inherently recursive structure. Based on conflicting conclusions of the arguments we can construct the attack relation: there will be a single attack, A ₄ attacking A ₃, intuitively due their conflicting conclusions and due to the fact that the strict rule overrides the defeasible one. Thus we have constructed an abstract AF and we can use any of the Dung’s semantics to compute the extensions and consequently also the meaning of the given DeLP. Taking, for example, the grounded semantics, there is a single extension E={A ₁, A ₂, A ₄} (in fact, in this simple case the complete, preferred, and stable semantics give also the very same result). Finally, we derive the semantics of the DeLP program as the conclusions of the arguments present in the extension, that is, the set of literals {arrival_time, in_meeting, ¬heating_on}.

García and Simari (Reference García and Simari2004) deal with the language of defeasible logic. The semantics is determined by the set of literals, which is computed procedurally via an argument game. However, the argument game is not admissibility based and therefore it departs from Dung’s semantics. It is interesting to note though that an online solver has been implementedFootnote ¹.

On the other hand, Prakken and Sartor (Reference Prakken and Sartor1997) directly instantiate Dung’s AF. They define an argument as a sequence of derivations and apply argumentation games to compute the grounded semantics. According to the authors, several non-standard design decisions were motivated by the legal domain.

A more recent work by Prakken (Reference Prakken2010) introduces an argumentation framework with structured arguments, called ASPIC⁺. It is basically a framework for structured argumentation rather than a particular system, where a particular language and argument ordering (preferences on arguments used in conflict resolutions) is left to be determined by the user. The online Java system TOAST that implements ASPIC⁺ has been developed by Snaith and Reed (Reference Snaith and Reed2012).

A different methodology was applied by Baláž et al. (Reference Baláž, Frtús and Homola2014a), where the status of an argument does not depend on attacks between arguments, but instead on attacks between conflict resolutions. Intuitively, a conflict resolution is a recipe describing how a conflict is resolved. Within the language containing defeasible rules and default literals a conflict may be resolved by either attacking a default literal or a defeasible rule.

Some approaches working with defeasible theories (Prakken & Sartor, Reference Prakken and Sartor1997; García & Simari, Reference García and Simari2004; Governatori et al., Reference Governatori, Maher, Antoniou and Billington2004) fail to meet the so called rationality postulates, as Caminada and Amgoud (Reference Caminada and Amgoud2007) pointed out. Specifically, properties known as indirect consistency (i.e. conclusions of extensions and conclusions of the intersection of all extensions must be consistent) and closure under strict rules (i.e. conclusions of extensions are closed under strict rules) are violated. Violation of these postulates can result into justification of absurdities or incomplete results, where some conclusions are missing.

While ASPIC⁺ (Prakken, Reference Prakken2010) satisfies the aforementioned postulates, it relies on transposition of rules. As pointed out by Baláž et al. (Reference Baláž, Frtús and Homola2014a), this is not in line with the intuitions of some non-monotonic rule-based formalisms, like logic programming, where the rules are treated as unidirectional. Hence, using such a framework with the aim to derive a semantics for DeLP may lead to some undesirable consequences. Baláž et al. (Reference Baláž, Frtús and Homola2014a, Reference Baláž, Frtús, Flouris, Homola and Sefránek2015) propose alternate approaches which avoid transposition and the associated problems while still satisfying the desired postulates. Both works extend ABF. Baláž et al. (Reference Baláž, Frtús, Flouris, Homola and Sefránek2015) extend ABF with a formal notion of conflict resolution strategy (CRS), with the idea that this component should not be fixed or limited to a small number of strategies, but rather an input parameter that can change from one application to another. It is showed that the postulates are satisfied for any given input CRS.

In a related work, Baláž et al. (Reference Baláž, Frtús, Homola, Sefránek and Flouris2014b) study the relationship between the argumentation semantics of DeLP (i.e. defeasible reasoning) and more traditional Generalized Logic Programs (GLP) (i.e. default reasoning). They show a transformation by which it is possible to compute a number of the argumentation semantics of DeLP in terms of a transformed GLP, relying on existing GLP semantics and solvers.

Table 10 summarizes several approaches and their properties with the focus on the underlying language (classical theory or some defeasible theory), the satisfaction of all relevant postulates, theoretical complexity, and whether there is a practical implementation of the given approach. If the reader is interested in further details regarding structured argumentation, we suggest to refer to the special issue of Argument & Computation dedicated to this topic (A&C, 2014).

Table 10

Structured argumentation-based formalisms

GLP=Generalized Logic Programs.

3.5.3 Applications in ambient intelligence

Argumentation has already been applied in AmI as a KR paradigm for dealing with both incomplete (partial) and inconsistent (contradictory) knowledge (Moraitis & Spanoudakis, Reference Moraitis and Spanoudakis2007; Bikakis & Antoniou, Reference Bikakis and Antoniou2010a; Muñoz et al., Reference Muñoz, Botía and Augusto2010, Reference Muñoz, Augusto, Villa and Botía2011; Muñoz Ortega et al., Reference Muñoz Ortega, Blaya, Clemente, Pérez and Skarmeta2010; Pajares Ferrando & Onaindia, Reference Pajares Ferrando and Onaindia2012). The approach presented by Muñoz et al. (Reference Muñoz, Botía and Augusto2010), for instance, uses argumentation techniques, in order to tailor services to the preferences of multiple users that share the same resources (i.e. a TV set). An internal dialogue is structured whenever conflicting preferences arise.

Notable are also the studies of Pajares Ferrando and Onaindia (Reference Pajares Ferrando and Onaindia2012), Bikakis and Antoniou (Reference Bikakis and Antoniou2010a), and Moraitis and Spanoudakis (Reference Moraitis and Spanoudakis2007) that respect the distributed nature of contextual information, where different entities possess locally a partial and tentative view of the actual world state. In these studies, defeasible rules are defined to represent uncertainty during context recognition, while techniques from the argumentation theory are applied in an attempt to resolve conflicts and reach a consensus about the actual context. Argumentation techniques are well tailored to resolving such types of contextual conflicts. In particular, Pajares Ferrando and Onaindia (Reference Pajares Ferrando and Onaindia2012) implemented and experimentally evaluated a DeLP multi-agent partial order planning framework. Their objective is to choose a plan respecting both the desire to minimize the computational overhead and to maximize the quality of the solution plan. Bikakis and Antoniou (Reference Bikakis and Antoniou2010a) aimed primarily at representation and reasoning issues. They defined a contextual defeasible logic (MCS instantiated with defeasible logic in each of the contexts), providing a decentralized platform and a set of distributed algorithms for query evaluation. To resolve all possible conflicts, a total preference ordering on the system contexts is assumed. Further, Bikakis and Antoniou (Reference Bikakis and Antoniou2011) study also partial preferences as well as different conflict resolution techniques (ambiguity blocking, ambiguity propagation, team defeat).

Although not directly applied in an AmI setting, an interesting application of argumentation techniques was proposed by Leite and Martins (Reference Leite and Martins2011) in the social Web area where the social voting determine arguments strength and consequently also the semantics of the system (valuation of all arguments).

As we may observe, applications in AmI will often require to consider certain levels of uncertainty, preference, or weights on arguments and attacks. Therefore, the studies extending argumentation frameworks with these capabilities (as discussed above) are quite relevant to this domain. But also other relevant directions, for example, investigating applications of argumentation for decision making (Amgoud & Prade, Reference Amgoud and Prade2009; Amgoud & Vesic, Reference Amgoud and Vesic2012) may be relevant.

To conclude, argumentation is a well-investigated field and one of its advantages over the other KR formalisms is its user-friendliness; argumentation-based semantics can be intuitively explained for both researchers in the KR domain and people not familiar with formal logic.

3.6.1 General considerations on interrelation of argumentation and belief change

Standard argumentation theory deals with a set of arguments and an attack relation. However, when argumentation becomes dynamic by adding or removing new arguments/attacks, interesting problems arise. Belief change methods are helpful in such situations. On the other hand, a variety of argumentation semantics exists, representing different views on compatible sets of arguments, which set the basis for a more flexible approach to belief change.

In works by Baroni et al. (Reference Baroni, Giacomin and Simari2013) and Fermé et al. (Reference Fermé, Gabbay and Simari2013), argumentation and belief change are considered as reasoning process and are thoroughly compared for commonalities and differences. They conclude that both fields capture partially distinct but overlapping research problems, and identify a number of interesting open research questions, posed by their comparison (e.g. they note the rising importance of postulates in argumentation which were long considered central in belief change, and call for proposals of ‘reasoning benchmarks’ which could be used to evaluate different approaches in both fields).

According to Falappa et al. (Reference Falappa, Garca, Kern-Isberner and Simari2011), some argumentation formalisms can be used to define belief change operators, and belief change techniques have been used for modelling the dynamics of beliefs in such argumentation formalisms. Complementary roles of belief change and argumentation in understanding and modelling complex reasoning processes are stressed. The analysis of connections between argumentation and belief change within a complex reasoning process is based mainly on the ideas of Falappa et al. (Reference Falappa, Kern-Isberner and Simari2009). A complex reasoning process consists usually of the following basic reasoning steps: (1) reception of new information, (2) evaluation of it, (3) change of beliefs, and (4) inference. Basically, argumentation can be used mainly in step 2 and belief change can be used in step 3. However, a more detailed analysis shows that there are complex interrelations between argumentation and belief change within the different reasoning steps.

Rotstein et al. (Reference Rotstein, Moguillansky, Garca and Simari2010) propose dynamic argumentation framework, in which a new feature, evidence, is introduced. Evidence enables to distinguish valid arguments. Change is represented at different levels: change on evidence, on arguments, on conflicts, or on a preference relation.

The works surveyed so far study the general connections between belief change and argumentation. Next, more technical approaches follow, categorized in two directions: those, applying methods of belief change to argumentation and those, that use the argumentation viewpoint to introduce some new features about belief change.

3.6.2 Belief change applied to argumentation

Computational aspects of argumentation frameworks updating are studied by Liao et al. (Reference Liao, Jin and Koons2011). A modular approach to updates is implemented as follows: if an update operation is specified for a given argumentation framework, the updated argumentation framework is divided into three parts: arguments affected by the update, arguments unaffected, and conditioning arguments. The latter are unaffected arguments, which attack affected arguments.

The role of conditioning arguments is essential from the computational point of view. Computation of the status of arguments can be divided in two parts. The status of unaffected arguments is the same as in the original argumentation framework; it is not changed by the update. The status of affected arguments is computed in a conditioned argumentation framework, where attacks of conditioning arguments against affected arguments influence the status of the second. An algorithm implementing this method is described.

The next works focus on elementary change operations in AFs. They provide a view on the change of basic components of argumentation frameworks. Different basic change operations are considered.

Cayrol et al. (Reference Cayrol, de Saint-Cyr and Lagasquie-Schiex2010) defined four basic change operations on argumentation frameworks: adding an attack between arguments, removing an attack, adding an argument together with attacks involving it, and removing an argument together with the involved attacks. The case of adding one argument is studied in details. The main focus is on the impact that the changes cause on the structure of extensions and on the status of some particular arguments.

Boella et al. (Reference Boella, Kaci and van der Torre2009b) are focussed on impact from adding attack relations to the semantics of an AF. The work is continued in Boella et al. (Reference Boella, Kaci and van der Torre2009a), where the removal of attacks and arguments is studied. Only the case of a semantics with precisely one extension is considered. The main focus is on principles for the argumentation dynamics.

Coste-Marquis et al. (Reference Coste-Marquis, Konieczny, Mailly and Marquis2014) and Mailly (Reference Mailly2013) study revision of attack relations in argumentation as minimal change of the arguments status. The principle of minimal change plays an important role in the belief change research: it states that it is appropriate to preserve as much from the given knowledge set as possible. It is further shown how AGM belief revision postulates (Alchourrón et al., Reference Alchourrón, Gärdenfors and Makinson1985) can be translated to the case of argumentation systems.

A different approach was undertaken by Baumann and Brewka (Reference Baumann and Brewka2010, 2012, Reference Baumann and Brewka2013). So called enforcing problem was described and solved by Baumann and Brewka (Reference Baumann and Brewka2010). It poses the question whether it is possible, given a specific set of allowed operations, to modify a given argumentation framework ${\cal A}$ into ${\cal A}'$ such that a desired set of arguments E is contained in some extension of the modified AF. Some conditions, under which enforcements are possible, were identified.

An important special case of the enforcing problem—how to reach that goal by a minimal change—was studied by Baumann (Reference Baumann2012). Given an argumentation framework A and a set of arguments E, the minimal number of additions or removals of attacks needed to reach an enforcement of E is called the characteristic of E. This number depends on the underlying semantics and the type of allowed modifications. It was shown that in certain cases there are local criteria, allowing to determine the characteristic. Local in the sense that the criteria are based on properties of the underlying argumentation framework and they enable to determine the characteristic in a finite number of steps.

The spectrum problem is studied by Baumann and Brewka (Reference Baumann and Brewka2013). Given a set of semantics and a modification type, the task is to determine for the pairs (σ, Φ), where σ is a semantics and Φ is a modification type, the set of all natural numbers which are characteristics of arbitrarily argumentation framework A and a set of arguments E. Surprisingly, this rather abstract problem yields interesting insights into relations of stable, semi-stable, and preferred semantics: it may be arbitrarily more difficult to enforce arguments using stable rather than semi-stable semantics, and also using semi-stable rather than preferred semantics.

Some researchers addressed problems connected to belief change in instantiated argumentation systems (structured argumentation frameworks with a subargument relation). Moguillansky et al. (Reference Moguillansky, Rotstein, Falappa, Garca and Simari2013) studied argumentation within DeLP. They defined prioritized argument revision operators for a given DeLP. The newly inserted argument becomes undefeated after the revision, hence its conclusion becomes warranted. In order to ensure this warrant, the program has to be changed in accordance with a minimal change principle.

3.6.3 Argumentation applied to belief change

A relatively smaller part of research is devoted to this aspect of interrelations between belief change and argumentation. As already mentioned, Moguillansky et al. (Reference Moguillansky, Rotstein and Falappa2008) employed argumentation to belief change in ontologies (particularly, ontology debugging). They build an argumentation framework, in which mutually inconsistent ontological axioms attack each other, and argumentation semantics thus determines possible repairs.

Liao (Reference Liao2013) constructed a layered (abstract) argumentation framework with subargument relation (AFwS). The semantics of AFwS provide a basis for the study of updating a layered AFwS and its properties. Among motivations for this research is a scenario as follows. An argumentation component is put before a belief revision component. Suppose that a new piece of (updating) information is given. The argumentation component serves as a filter: a set of accepted arguments (and therefore, their conclusions) is obtained by means of argumentation. As a consequence, only new information justified by the argumentation process inputs into the process of belief change. This can serve as a contribution to standard implementations of belief change.

Krümpelmann et al. (Reference Krümpelmann, Thimm, Falappa, Garca, Kern-Isberner and Simari2012) proposed a way how to distinguish whether new information should be accepted. Deductive argumentation (Besnard & Hunter, Reference Besnard and Hunter2001) is used to assess the value of new information. Hereby is obtained a revision operator which accepts new information only if the new information is justifiable.

3.6.4 Summary

Understanding the mutual interrelations between belief change and argumentation presents a contribution to both these fields, which we previously found relevant for AmI applications. In particular, it may contribute to develop more flexible argumentation frameworks, capable of updating, and thus reflecting the necessary changes that may be required by a change of a situation faced by a particular AmI application. On the other hand, it may contribute to the development of more flexible and more effective belief change operators implemented with argumentation procedures.

Given that this research direction is fairly new, most of the proposals are yet at the theoretical level, lacking reasoning support and implementations. We see this as a notable research challenge, especially for the KR community. Out of these theoretical works we would like to particularly highlight the notion of complex reasoning processes (Falappa et al., Reference Falappa, Kern-Isberner and Simari2009), which highlights interactions between related reasoning tasks of a rational agent and which is fairly in line with the reasoning cycle of agents in AmI systems (cf. Figure 1). The only work with more practical implications in this area is that of Liao et al. (Reference Liao, Jin and Koons2011). In Table 11 the overviewed approaches are classified with respect to whether they are an application of belief change in argumentation, or an application of argumentation to belief change (columns ‘BC of AF’ and ‘BC by AF’, respectively). Some of the approaches fall into both categories. The main focus of each work is also summarized.

Table 11

Belief change and argumentation: comparison of works

3.7.1 Preferences on rules

Consider we have a rule encoding that an agent should execute an action A, and a second rule encoding that the agent should not execute the action A. If the ‘if’ parts of both rules are satisfied, we have a conflict. This conflict can be resolved using preferences and preferential reasoning. Assuming that we prefer the second rule, for example, because it is based on more specific information, preferential reasoning makes the first rule inapplicable whenever the second one is applicable.

One of the standard semantics for logic programming is the answer set semantics (Gelfond & Lifschitz, Reference Gelfond and Lifschitz1991). It assigns to a logic program a collection of answer sets, each corresponding to an alternative set of beliefs an agent can accept. The so-called selective preference handling approaches studied, for example, by Brewka and Eiter (Reference Brewka and Eiter1999), Wang et al. (Reference Wang, Zhou and Lin2000), Delgrande et al. (Reference Delgrande, Schaub and Tompits2003), Zhang and Foo (Reference Zhang and Foo1997), Sakama and Inoue (Reference Sakama and Inoue2000), Šefránek (Reference Šefránek2008), and Šimko (Reference Šimko2013) select a subset of standard answer sets as preferred. They do so in order to stay compatible with the answer set semantics, instead of inventing a completely new semantics.

The approaches studied by Delgrande et al. (Reference Delgrande, Schaub and Tompits2003), Wang et al. (Reference Wang, Zhou and Lin2000), and Brewka and Eiter (Reference Brewka and Eiter1999)can be characterized as prescriptive (Delgrande et al., Reference Delgrande, Schaub, Tompits and Wang2004b). Preferences on rules are interpreted as the order, in which rules are applied. As a consequence, a less preferred rule cannot defeat a preferred rule. Each of the approaches puts slightly different conditions on the order in which rules have to be applied. Schaub and Wang (Reference Schaub and Wang2003) showed that the approaches form a hierarchy. The biggest difference between the approaches is that the one by Brewka and Eiter (Reference Brewka and Eiter1999) handles only direct conflicts, while those by Delgrande et al. (Reference Delgrande, Schaub and Tompits2003) and Wang et al. (Reference Wang, Zhou and Lin2000) handle indirect conflicts. Delgrande et al. (Reference Delgrande, Schaub and Tompits2003), Eiter et al. (Reference Eiter, Faber, Leone and Pfeifer2003a), Grell et al. (Reference Grell, Konczak and Schaub2005), and Asuncion and Zhang (Reference Asuncion and Zhang2009) deal with the issue of computing the semantics.

On the opposite side of prescriptive approaches lie descriptive (Delgrande et al., Reference Delgrande, Schaub, Tompits and Wang2004b) approaches. They do not see preferences as the order of application of rules, instead preferences are handled in a more declarative fashion. Zhang and Foo (Reference Zhang and Foo1997) view preference handling as a removal of less preferred rules. Sakama and Inoue (Reference Sakama and Inoue2000) define preference handling as a comparison of the rules that generate answer sets. Sefránek (Reference Šefránek2008) and Šefránek and Šimko (Reference Šefránek and Šimko2011, Reference Šefránek and Šimko2013) look at preference handling as a form of argumentation. Šimko (Reference Šimko2013) uses preferences to transform conflicting rules into rules defining exceptions: a preferred rule defines exception to a less preferred rule, but not the other way around.

The computational complexity of various decision problems for the aforementioned semantics has been studied. While for some semantics the decision problems are polynomially decidable, the decision problems for the remaining approaches are NP-complete, or lie on a higher level of the polynomial hierarchy. This is expressed by the values ‘P’ and ‘NP-c/worse’ in Table 12.

Table 12

Preferential reasoning: preferences on rules

Besides the answer set semantics, the well-founded semantics is the second standard semantics for logic programs. It can be computed in polynomial time. Brewka (Reference Brewka1996), Schaub and Wang (Reference Schaub and Wang2002), and Wang et al. (Reference Wang, Zhou and Lin2000) defined preferred well-founded semantics for logic programs with preferences, which can also be computed in polynomial time.

Delgrande et al. (Reference Delgrande, Schaub and Tompits2003) and Zhang and Foo (Reference Zhang and Foo1997) consider dynamic preferences. Preferences not only change the semantics of logic programs, they are also subject of reasoning.

The main shortcoming of the literature in the field is that it provides little or no insight into which semantics to use in a domain at hand. The study of principles for preferential reasoning can help to fill this gap. Some development was done by Brewka and Eiter (Reference Brewka and Eiter1999), Šefránek (Reference Šefránek2008), and Šefránek and Šimko (Reference Šefránek and Šimko2013). Ideally, given an application domain, a suitable semantics is selected based on a subset of relevant principles. However, work in this direction is still needed. So far, existing principles do not sufficiently differentiate between the approaches and are unable to guide in selecting a right semantics for a task at hand.

Table 12 summarizes the approaches for reasoning with preferences on rules. The values in the column ‘practicality’ have the following meaning: (i) native—a solver with an algorithm specifically tailored for the approach is implemented, algorithm—there is an algorithm specifically tailored for the approach, but no implementation is available, reduction—reduction of an approach to logic programming without preferences exist.

3.7.2 Preferences on literals

If the answer set programming methodology is used, a problem is encoded into a program in a way that the answer sets of the program correspond to the solutions of the problem, for example, using answer set programming for planning, each answer set of the program corresponds to a valid plan. In some situations, having multiple solutions means a conflict, for example, as we can execute only one plan of actions, we need to select one of the valid plans. While there is always an option of selecting a random plan, we usually have additional preferences that need to be taken into account. For example, if it is possible we want to select a plan containing non-destructive actions. Preferences on literals and preferential reasoning allow us to express and reason with exactly this kind of preferences. Usually, an order on answer sets is computed based on the preferences, and maximal answer sets with respect to the order are selected.

Sakama and Inoue (Reference Sakama and Inoue2000) extend logic programs with a preference relation on literals. The relation is then transferred to a relation on answer sets and maximal answer sets are selected as preferred. In this way, preferred answer sets contain preferred literal. Sakama and Inoue also showed how preferences on literals can be applied to various forms of commonsense reasoning: minimal abduction, prioritized abduction, default reasoning, prioritized default reasoning, circumscription, and prioritized circumscription.

Brewka (Reference Brewka2002) introduces logic programs with ordered disjunction, in which preference of a literal is given by its position in a disjunction. The intuition behind the rule with ordered disjunction A×B←C is as follows. If C is contained in an answer set S, then A is in S if possible. But if it is not possible, then (at least) B is in S (Brewka, Reference Brewka2002). Brewka also shows how programs with ordered disjunction can be used in the configuration domain.

Brewka et al. (Reference Brewka, Niemelä and Truszczynski2003) consider answer set optimization programs consisting of two parts. The generating program produces answer sets representing solutions of a problem. The preference program expresses user preferences using the rules of the form A ₁> ··· >A _n←B ₁, … , B _m. A preference relation on the answer sets of the generating program is based on the degree in which the rules of the preference program are satisfied.

Complexity of various decision problems for the aforementioned semantics have been studied. The decision problems for all the reviewed approaches are NP-complete, or lie on a higher level of the polynomial hierarchy. This is expressed by the value ‘NP-c/worse’ in Table 13.

Table 13

Preferential reasoning: preferences on literals

Table 13 summarizes the approaches for reasoning with preferences on rules. The column ‘practicality’ contains a unique value ‘algorithm’—there is an algorithm specifically tailored for the approach.

Related to the aforementioned approaches are CP-nets (Boutilier et al., Reference Boutilier, Brafman, Hoos and Poole1999, Reference Boutilier, Brafman, Domshlak, Hoos and Poole2004). They deal with the problem of inferring preferences on vectors of feature values given conditional preferences on feature values. This problem can be very naturally expressed by all the reviewed approaches for preferences on literals. The benefits of these logic programming-based approaches are (i) the availability of default negation allows to represent defeasible information, and (ii) while CP-nets are concerned only with one fixed space of vectors, the answer set optimization programs have a substantial flexibility in defining the space (Brewka et al., Reference Brewka, Niemelä and Truszczynski2003). The same holds also for the Sakama and Inoue’s preferences on literals, and logic programs with ordered disjunction. Brewka et al. (Reference Brewka, Niemelä and Truszczynski2003) also show that (i) the semantics of the CP-nets and the answer set optimization programs are different, mainly due to the different interpretations of the phrase ‘other things being equal’, which lies at the heart of both semantics, and preferences inferred by CP-nets can be approximated by preferences inferred by answer set optimization programs.

Closely related to logic programming are relational databases, which are also relevant for AmI. It has been explored how to extend relational databases with preferences on database rows, which are preferences on literals in logic programming terminology. For the survey of the approaches adding preferences to relational databases we refer the reader to Stefanidis et al. (Reference Stefanidis, Koutrika and Pitoura2011). Another interesting approach is Lukasiewicz et al. (Reference Lukasiewicz, Martinez and Simari2013). It extends Datalog+/−, a family of ontology languages, with preferences. Syntactically the preferences are on literals, similar to that of Brewka et al.’s answer set optimization programs, but the semantics follows the database approaches.

3.7.3 Summary

We have given an overview of the approaches for preference handling in logic programming. In this section we give some pointers how the approaches can be used in AmI.

In Section 2.3, five types of conflicts with respect to the knowledge-type dimension were introduced. With a suitable encoding, all conflicts seem to be solvable using preference handling. However, some might feel little unnatural, and probably other approach would be more appropriate.

Preferences on literals are especially suitable for handling conflicting goals and plans. If answer sets correspond to different goals/plans, we can select preferred ones. Preferences on literals can, for example, prefer literals representing non-destructive actions over destructive ones, or actions using less expensive resources. For the issue of incorporating domain-specific preferences in planning systems we refer the reader to Delgrande et al. (Reference Delgrande, Schaub and Tompits2004a).

Preferences on rules are usable for handling both conflicts inside an agent and conflicts between agents. One way at looking at preferences on rules is as a handy way of encoding exceptions between rules. When writing logic programs, we usually use general rules with exceptions. Preferences on rules allow us to express exceptions in a more easily and change tolerant way. Preferences on rules were already used in AmI. Bikakis and Antoniou (Reference Bikakis and Antoniou2010a) use trust level of agents to determine preferences on conflicting rules, although they use a different formalism than we discuss in this section.

Regarding the applicability of the approaches in real environments, algorithms and prototypical solvers exists. However, additional work needs to be done as no production ready solver for preferences exists.

3.8.1 Propositional case

Paraconsistent logic can be split into several types (Bertossi et al., Reference Bertossi, Hunter and Schaub2005): signed systems, which involve the renaming of literals and then restoring the non-conflicting part of the original theory by adding equivalences with their renamings; weakly negative logics and quasi-classical logic, which use a restricted subset of classical proof theory, or rely on natural deduction to apply the proof rules more carefully, in order not to avoid the explosive derivation of all conclusions; and multi-valued logics, which employ a dedicated semantics, in which the truth and the falsity of each statement are considered independently.

Besnard and Schaub (Reference Besnard and Schaub1998) define a paraconsistent semantics for propositional theories by a signed system, in which they represent each positive literal a as a ⁺ and each negative literal ¬a as a ⁻. They employ default logic (Reiter, Reference Reiter1980), which allows to interpret a ⁺ as a and a ⁻ as ¬a, but only as long as the equivalence between a ⁺ and ¬a ⁻ can be assumed, that is as long as it does not cause the conflict between a ⁺ and a ⁻ to occur. Thus, a consistent part of the original theory is effectively reconstructed. Unlike some other paraconsistent logics, in the consistent case the entailment within such a system coincides with classical entailment. Decision procedures for default logics (e.g. Junker & Konolige, Reference Junker and Konolige1990; Ben-Eliyahu & Dechter, Reference Ben-Eliyahu and Dechter1991; Niemelä, Reference Niemelä1995) can be used, although even in propositional case default entailment is known to be complete with respect to the second level of the polynomial hierarchy (Gottlob, Reference Gottlob1992). This stream of development has largely gave way to (answer set) logic programming, with relevant paraconsistent extensions being discussed in Section 3.8.2.

Besnard and Hunter (Reference Besnard and Hunter1995) and Hunter (Reference Hunter2000b) proposed and developed quasi-classical logic, which they show to possess useful properties to reason with inconsistent knowledge. A number of interesting applications have been studied (e.g. Hunter, Reference Hunter2000a; Byrne and Hunter, Reference Byrne and Hunter2004), and the logic is known to be decidable (Hunter, Reference Hunter2000b); however, no implementations are known.

The four-valued propositional logic was developed by Belnap (Reference Belnap1977). This logic works independently with truth and falsity, yielding two new truth values of a statement (apart from the classical true and false), namely unknown and inconsistent. This approach was later generalized for more than four truth values (Ginsberg, Reference Ginsberg1988; Fitting, Reference Fitting1991a). Translations of this logic into FOL are known (Rodrigues & Russo, Reference Rodrigues and Russo1998), which enable the use of classical first-order provers, for example, VAMPIRE (Riazanov & Voronkov, Reference Riazanov and Voronkov2002), for reasoning.

Arieli and Denecker (Reference Arieli and Denecker2003) also investigate on paraconsistent propositional logic with multi-valued semantics and its translation to classical logic. In addition, they employ preferential reasoning (cf. Section 3.7), with the help of which they accept only models in which the inconsistent part of the KB is minimized. They provide a polynomial translation, yielding a first-order theory with an addition of circumscriptive second-order formulae (McCarthy, Reference McCarthy1980) representing the preferential criteria. This allows to use known translations of circumscriptive (Gustafsson, Reference Gustafsson1996; Ohlbach, Reference Ohlbach1996; Doherty et al., Reference Doherty, Lukaszewicz and Szalas1997), finally yielding a first-order theory and again enabling to resort to classical first-order provers.

Besnard et al. (Reference Besnard, Schaub, Tompits and Woltran2005) encode various paraconsistent systems (maximal-consistent subsets, signed systems, and multi-valued approaches) into quantified propositional logic (QBF). This enables their comparison, but also the use of QBF (e.g. Feldmann et al., Reference Feldmann, Monien and Schamberger2000; Giunchiglia et al., Reference Giunchiglia, Narizzano and Tacchella2001; Letz, Reference Letz2002) for reasoning. This paves the way towards more practical applications, given the recent increased interest and developments in the area of QBF solvers.

3.8.2 Paraconsistent logic programs

The logic programming paradigm has been successfully applied in agent-based applications. Development of paraconsistent semantics for logic programs has been driven by the ability of agents (and other systems) to deal with situations, in which inconsistent information simply cannot be ruled out. Real-time applications, and distributed systems with autonomous entities and decentralized information sources fall under this category.

Paraconsistent semantics for logic programming was largely built on top of multi-valued logics (Belnap, Reference Belnap1977; Ginsberg, Reference Ginsberg1988; Fitting, Reference Fitting1991a). First, such semantics for logic programs was developed by Blair and Subrahmanian (Reference Blair and Subrahmanian1987, Reference Blair and Subrahmanian1989); other early studies in this area include those of Fitting (Reference Fitting1991b) and Kifer and Lozinskii (Reference Kifer and Lozinskii1992). All use four-valued semantics and only work with classical negation.

Sakama (Reference Sakama1992) concentrates on extended logic programs (ELP, Gelfond & Lifschitz, Reference Gelfond and Lifschitz1991), which feature both classical and default negation, and possibly negation in the head. Sakama proposes a paraconsistent version of the well-founded semantics (Van Gelder et al., Reference Van Gelder, Ross and Schlipf1991) for this class of logic programs, where in order to distinguish between the classical and the default negation he resorts to the seven-valued semantics of Ginsberg (Reference Ginsberg1988).

This work is further extended by Sakama and Inoue (Reference Sakama and Inoue1995) who developed a paraconsistent stable-model semantics for extended disjunctive logic programs. This semantics was also implemented on top of the MGTP reasoner (Inoue et al., Reference Inoue, Koshimura and Hasegawa1992). Further evaluation of this semantics was done by Alcântara et al. (Reference Alcântara, Damásio and Pereira2004) and Odintsov and Pearce (Reference Odintsov and Pearce2005).

An alternative paraconsistent version of the well-founded semantics for ELP, dubbed WFSX _p, was proposed by Alferes et al. (Reference Alferes, Damásio and Pereira1995). This semantics is based on the principles of coherence and introspection (Damásio & Pereira, Reference Damásio and Pereira1995), ensuring, for example, that the default negation of an atom (i.e. the weaker one) is always entailed from the classical negation of the same atom. A dedicated decision procedure called SLX, which uses a procedure similar to the standard PROLOG SLDNF procedure (Lloyd, Reference Lloyd1984) was described and implemented (Alferes et al., Reference Alferes, Damásio and Pereira1995). Further extensions of WFSX _p towards other common logic programming semantics are proposed by Damásio and Pereira (Reference Damásio and Pereira1995).

In the same paper discussed above, Sakama and Inoue (Reference Sakama and Inoue1995) proposed also the so called semi-stable semantics, which has the feature that it is able to derive consequences in cases when the classical stable-model semantics has no model, but coincides with it in cases when it has models. Such an approach, dubbed paracoherent is not intended to draw conclusions from truly inconsistent KBs, but merely to overcome non-existence of models in some cases due to some rather technical reasons (e.g. cyclic dependencies). This line of work was further extended by Eiter et al. (Reference Eiter, Fink and Moura2010a) who provided a model-theoretic characterization, and proposed several improvements. They show the complexity of reasoning, which is one level up in the polynomial hierarchy when compared with the classical stable-model semantics. Finally, they briefly describe a prototype implementation.

3.8.3 Other paraconsistent logics

Given the popularity of Semantic Web ontology languages such as RDF and OWL 2 in AmI applications, their paraconsistent variants may contribute to the ability of AmI systems to deal with inconsistent information sources. Four-valued paraconsistent extensions of DLs (i.e. the family of logics which provides the formal semantics for OWL 2) were already investigated by Patel-Schneider (Reference Patel-Schneider1989) and Straccia (Reference Straccia1997). The approach of Ma et al. (Reference Ma, Hitzler and Lin2007) who propose ${\cal A}{\cal L}{\cal C}4$ , a four-valued extension of ${\cal A}{\cal L}{\cal C}$ (cf. Baader et al., Reference Baader, Calvanese, McGuinness, Nardi and Patel-Schneider2003), is particularly interesting to us as paraconsistent reasoning is obtained with no additional computational cost by reduction to classical DL. In the follow-up work, Ma and Hitzler (Reference Ma and Hitzler2009)extended this approach towards the ${\cal S}{\cal R}{\cal O}{\cal I}{\cal Q}$ DL (Horrocks et al., Reference Horrocks, Kutz and Sattler2006), reaching the full expressivity of OWL 2. They also investigate the tractable fragments of OWL 2. Their approach has been implemented into the RaDON plug-in (Ji et al., Reference Ji, Haase, Qi, Hitzler and Stadtmüller2009) of the NeOn ontology engineering toolkit (Erdmann & Waterfeld, Reference Erdmann and Waterfeld2012).

A quasi-classical variant of DL was developed by Zhang and Lin (Reference Zhang and Lin2012). A tableau algorithm was also described by Zhang et al. (Reference Zhang, Xiao and Lin2009). These studies carry over the quasi-classical approach into the area of ontologies.

Hybrid KBs feature both ontologies and rules, a combination which is often required by practical applications, as ontologies carry the terminological knowledge, while rules are a more powerful tool for implementing reasoning. Paraconsistent reasoning has been investigated for each component separately, but recently also for hybrid KBs by Kaminski et al. (Reference Kaminski, Knorr and Leite2015) who have investigated two multi-valued semantics in this context.

Another approach to inconsistency is based on estimating the amount of contradicting knowledge within a given information source or between different information sources with suitable inconsistency measures (Hunter & Konieczny, Reference Hunter and Konieczny2005). Such an approach may provide agents with more fine-grained assessment of diverse information sources with respect to their degree of inconsistency in comparison with the current agent’s belief and/or their degree of self-contradiction. Some sources may be rejected straight ahead, while some, more valuable sources, may be integrated with the agent’s beliefs directly or by suitable conflict resolution methods. See the work of Hunter and Konieczny (Reference Hunter and Konieczny2005) for an overview of this area.

3.8.4 Applicability of paraconsistent reasoning

Paraconsistent reasoning has found applications in databases (Arieli et al., Reference Arieli, Denecker, Van Nuffelen and Bruynooghe2004), including medical KBs (da Costa & Subrahmanian, Reference da Costa and Subrahmanian1989), and its applications in spatial databases were also conceived (Rodríguez, Reference Rodríguez2005).

Paraconsistent reasoning has been further applied for inconsistency management in areas, such as software engineering, and on problems, such as combining inconsistent specifications (Hunter & Nuseibeh, Reference Hunter and Nuseibeh1998) and requirements (Ernst et al., Reference Ernst, Borgida, Mylopoulos and Jureta2012).

Quasi-classical logic has been applied in dealing with inconsistency in structured text excerpts (Hunter, Reference Hunter2000a), for example, structured news reports (Byrne & Hunter, Reference Byrne and Hunter2004). A similar approach may be valuable in AmI applications with the need to process textual inputs from multiple users. An interesting observation in these works is that the presence of inconsistency need not necessarily be an indicator of error; for instance, if multiple news reports are found inconsistent with the background knowledge, then this may be an indicator of interesting new developments in the domain, that have to be accommodated and processed (Byrne & Hunter, Reference Byrne and Hunter2004).

We are not aware of any direct application or case study of paraconsistent reasoning in AmI. Nevertheless, these approaches can be applied to any type of conflict resolution, most notably sensory input conflicts, and also for resolving conflicts between new observations and background knowledge (Byrne & Hunter, Reference Byrne and Hunter2004; Ernst et al., Reference Ernst, Borgida, Mylopoulos and Jureta2012).

As already noted above, current AmI applications already make use of ontologies. If inconsistency handling of ontological data becomes needed, paraconsistent OWL (Ma et al., Reference Ma, Hitzler and Lin2007; Ma and Hitzler, Reference Ma and Hitzler2009) may become handy (or alternatively some of the ontology debugging approaches surveyed in Section 3.4.2 may be applied).

While all the approaches surveyed in previous sections mostly aim at removing conflicts and repairing the KB, paraconsistent reasoning shifts the point of view into simply being able to reason also with inconsistent knowledge, without necessarily requiring some kind of repair. This point of view may be useful in certain AmI scenarios, where agents need to react based on their inputs while maintaining the KB is of secondary interest. Many of the logics which we surveyed have favourable (polynomial) reasoning complexity (Coste-Marquis & Marquis, Reference Coste-Marquis and Marquis2005). Many of the paraconsistent logic programming extensions have developed into experimental implementations, and some of them are also known to be tractable (e.g. WFSX _p, Alferes et al., Reference Alferes, Damásio and Pereira2003). Further research may be however needed in order to make them effective enough for real-time AmI applications.

3.8.5 Summary

In this section we have discussed approaches that allow to reason also with inconsistent KBs, evaluate them and draw conclusions from sound parts of the knowledge. Most of them are summarized and compared in Table 14 where we distinguish them based on the underlying representation language and different type of paraconsistent reasoning. We also point out practical results achieved in this area. Measures of inconsistency (cf. Hunter & Konieczny, Reference Hunter and Konieczny2005) are not included as the main focus in this area is different from the rest of the surveyed works, as explained above.

Table 14

Paraconsistent reasoning: comparison of approaches

FOL=first-order logic; QBF=quantified propositional logic; EDLP=extended disjunctive logic programs; ELP=extended logic programs; DL=description logic; KB=knowledge base.