Generation and Selection of Abductive Explanations for Non-Omniscient Agents

Abstract

Among the non-monotonic reasoning processes, abduction is one of the most important. Usually described as the process of looking for explanations, it has been recognized as one of the most commonly used in our daily activities. Still, the traditional definitions of an abductive problem and an abductive solution mention only theories and formulas, leaving agency out of the picture. Our work proposes a study of abductive reasoning from an epistemic and dynamic perspective. In the first part we explore syntactic definitions of both an abductive problem in terms of an agent’s information and an abductive solution in terms of the actions that modify the agent’s information. We look at diverse kinds of agents, including not only omniscient ones but also those whose information is not closed under logical consequence and those whose reasoning abilities are not complete. In the second part, we look at an existing logical framework whose semantic model allows us to interpret the previously stated formulas, and we define two actions that represent forms of abductive reasoning.

1 Abductive Reasoning

Among the non-monotonic reasoning processes, abduction (Aliseda 2006) is one of the most important. The concept, introduced into modern logic by Charles S. Peirce, is usually described as the process of looking for an explanation, and it has been recognized as one of the most commonly used in our daily activities. Observing that Mr. Wilson’s right cuff is very shiny for five inches and that his left one has a smooth patch near the elbow, Holmes assumes that he (Mr. Wilson) has done a considerable amount of writing lately. Karen knows that when it rains, the grass gets wet, and that the grass is wet right now; then, she suspects that it has rained. There are also cases in science: in classical mechanics, rules are introduced in order to explain macroscopical movements. In Peirce’s own words (Hartshorne and Weiss 1934), abduction can be described in the following way:

The surprising fact $\chi$ is observed.

But if $\psi$ were true, $\chi$ would be a matter of course.

Hence, there is reason to suspect that $\psi$ is true.

But though traditional examples of abductive reasoning are given in terms of an agent’s information and its changes, classic definitions of an abductive problem and its solutions are given in terms of theories and formulas, without mentioning the agent’s information and how it is modified.

The present work proposes a study of abductive reasoning from an epistemic and dynamic perspective, and it is divided into two parts. The first one follows recent developments in Epistemic Logic [EL; Hintikka (1962)] and Dynamic Epistemic Logic [DEL; Ditmarsch et al. (2007), Benthem (2011)], and focuses on providing formulas defining what an abductive problem is in terms of an agent’s information as well as what an abductive solution is in terms of the actions that modify it. We explore not only the case of omniscient agents, but also the cases of agents whose information is not closed under logical consequence and whose reasoning abilities are not complete. The second part focuses on a framework in which the provided formulas can be interpreted. We extend the ideas presented in Velázquez-Quesada et al. (2013), Nepomuceno-Fernández et al. (2013) in order to deal with non-omniscient agents, and we define two actions that allow us to represent certain forms of abductive reasoning. We finish with a summary and further research points.

2 From a Classical to a Dynamic Epistemic Approach

Traditionally, it is said that an abductive problem arises when there is a formula $\chi$ that does not follow from the theory $\varPhi$. The intuitive idea is that $\varPhi$ represents the current information about the world, and observing a situation $\chi$ that is not entailed by $\varPhi$ shows that the theory is incomplete. Then we should look for extra information that ‘fills the gap’.

But even if the theory $\varPhi$ does not entail the observed $\chi$, it may as well be the case that it entails the negation of $\chi$. This case, extensively studied in belief revision (Gärdenfors 1992; Williams and Rott 2001), has been recently incorporated as an abductive case.

All in all, the key ingredient for an abductive problem is the existence of a $\chi$ that is not entailed by the current information $\varPhi$. This situation generates two forms of abductive problems, according to what the information predicts about $\lnot \chi$ (Aliseda 2006).

Definition 1

(Abductive problem) Let $\varPhi$ and $\chi$ be a theory and a formula, respectively, in some language $\mathcal {L}$. Let $\vdash$ be a consequence relation on $\mathcal {L}$.

• The pair $(\varPhi ,\chi )$ forms a novel abductive problem when neither $\chi$ nor $\lnot \chi$ are consequences of $\varPhi$, i.e., when

  $$\begin{aligned} \varPhi \, \not \vdash \, \chi \qquad \text {and}\qquad \varPhi \, \not \vdash \, \lnot \chi \end{aligned}$$

• The pair $(\varPhi ,\chi )$ forms an anomalous abductive problem when, though $\chi$ is not a consequence of $\varPhi$, $\lnot \chi$ is, i.e., when

  $$\begin{aligned} \varPhi \, \not \vdash \, \chi \qquad \text {and}\qquad \varPhi \, \vdash \, \lnot \chi \end{aligned}$$

It is typically assumed that the theory $\varPhi$ is a set of formulas closed under logical consequence, and that $\vdash$ is a truth-preserving consequence relation.

Consider a novel abductive problem. The observation of a $\chi$ about which the theory does not have any opinion shows that the theory is incomplete, and then we should look for information that ‘completes’ it, making $\chi$ a consequence of it. This solves the problem because now the theory is strong enough to explain $\chi$. Consider now an anomalous abductive problem. The observation of a $\chi$ whose negation is entailed by the theory shows that the theory contains a mistake, and now we need two steps to solve this. First, perform a theory revision that stops $\lnot \chi$ from being a consequence of $\varPhi$; after this we are now in a novel abductive case, and we can look for information that ‘completes’ the theory, making $\chi$ a consequence of it. Here are the formal definitions.

Definition 2

(Abductive solution)

• Given a novel abductive problem $(\varPhi , \chi )$, the formula $\psi$ is said to be an abductive solution if

  $$\begin{aligned} \varPhi \cup \{{\psi }\} \, \vdash \, \chi \end{aligned}$$

• Given an anomalous abductive problem $(\varPhi , \chi )$, the formula $\psi$ is an abductive solution if it is possible to perform a theory revision to get a novel problem $(\varPhi ', \chi )$ for which $\psi$ is a solution.

This definition of an abductive solution is often considered as too weak, since $\psi$ can take many ‘trivial’ forms, like anything that contradicts $\varPhi$ (then everything, including $\chi$, follows from $\varPhi \cup \{{\psi }\}$) and even $\chi$ itself (we clearly have $\varPhi \cup \{{\chi }\} \vdash \chi$). Further conditions can be imposed in order to define more satisfactory solutions; here are some of them (Aliseda 2006).

Definition 3

(Classification of abductive solutions) Let $(\varPhi , \chi )$ be an abductive problem. An abductive solution $\psi$ is

consistent iff	$\varPhi , \, \psi$ $\not \vdash$ $\, \bot$
explanatory iff	$\psi$ $\not \vdash$ $\, \chi$
minimal iff, for every other solution $\varphi$,	$\psi$ $\, \vdash \varphi$	implies   $\varphi \, \vdash \, \psi$

The consistency requirement discards those $\psi$ inconsistent with $\varPhi$, since a reasonable explanation should not be in contradiction with the theory. In a similar way, the explanatory requirement discards those explanations that would justify $\chi$ by themselves, since it is preferred that the explanation only complements the current theory. Finally, the minimality requirement works as the Occam’s razor, looking for the simplest explanation: a solution $\psi$ is minimal if it is in fact logically equivalent to any other solution it implies.

2.1 From an Agent’s Perspective

Abduction, like other forms of non-monotonic inference, is classified as commonsense reasoning rather than mathematical one, and most of its classic examples involve ‘real’ agents and their information. It is Holmes who observes that Mr. Wilson’s right cuff is very shiny; it is Karen who observes that the grass is wet; it is the scientific community who wants to explain the movement of objects. Nevertheless, the classic definitions of an abductive problem and an abductive solution do not mention agents at all. More important, an abductive solution is typically defined as a piece of information that will produce certain results when incorporated into the current information. But, again, the definition of abductive solutions focuses on the properties a formula should satisfy in order to be a solution, but not in the different forms it can be incorporated into an agent’s information.

Epistemic logic deals with agents, their information, and properties of this information. Its dynamic counterpart, Dynamic Epistemic Logic, allows us to reason about the way the agent’s information changes as consequence of different informational actions. The following three ideas are, from our perspective, the most important of this methodology. First, the notion of information should be closely related to the notion of agency. When we talk about information, there is always an abstract agent (a human being, a computer program, etc.) involved: the one that owns and uses the information. Second, though in mathematical reasoning there is only one notion of information, true information, in commonsense ‘human’ reasoning there are several of them. We usually deal not only with information that is true (what we know), but also with information that though not certain is very plausible (what we believe), information that we entertain (what we are aware of) and so on. And even inside each one of these notions we can make further refinements, like distinctions between implicit and explicit forms. As interesting as it is to study each notion in isolation, it is more interesting to study them together to observe the relations between them and the way they interact with each other. And third, notions of information are not static: we are continuously performing informational actions that modify them. Actions are important, and deserve to appear explicitly in the analysis.

Based on these ideas, our work proposes a dynamic epistemic approach to abductive reasoning, proposing definitions of abductive problem and abductive solution in terms of an agent’s information and the way it changes [cf. Velázquez-Quesada et al. (2013)]. The first step is, then, to answer the question: when does an agent have an abductive problem?

When we put an agent in the picture, the theory $\varPhi$ becomes the agent’s information. Then the key ingredient for an abductive problem, a formula $\chi$ that does not follow from the theory $\varPhi$, becomes a formula that is not part of the agent’s information. The following definitions use formulas in EL style, with ${\mathrm{Inf }}\,{\varphi }$ read as “$\varphi$ is part of the agent’s information”.

Definition 4

(Subjective abductive problems) Let $\chi$ be a formula.

• An agent has a novel $\chi$ -abductive problem when neither $\chi$ nor $\lnot \chi$ are part of her information, i.e., when the following formula holds:

  $$\begin{aligned} \lnot {\mathrm{Inf }}\,{\chi } \;\wedge \; \lnot {\mathrm{Inf }}\,{\lnot \chi } \end{aligned}$$

• An agent has an anomalous $\chi$ -abductive problem when $\chi$ is not part of her information but $\lnot \chi$ is, i.e., when the following formula holds:

  $$\begin{aligned} \lnot {\mathrm{Inf }}\,{\chi } \;\wedge \; {\mathrm{Inf }}\,{\lnot \chi } \end{aligned}$$

We have identified $\varPhi$ with the agent’s information. Then, a solution for the subjective novel case is a formula $\psi$ that, when added to the agent’s information, makes the agent informed about $\chi$. This highlights the fact that the requisites of a solution involve an action; an action that changes the agent’s information by adding $\psi$ to it.

We will express changes in the agent’s information by using formulas in DEL style. In particular, we will use formulas of the form $\langle \mathrm{Add }_{\psi }\rangle \,\varphi$ (“$\psi$ can be added to the agent’s information and, after that, $\varphi$ is the case”) and formulas of the form $\langle \mathrm{Rem }_{\psi }\rangle \,\varphi$ (“$\psi$ can be removed from the agent’s information and, after that, $\varphi$ is the case”).¹

Definition 5

(Subjective abductive solution) Suppose an agent has a novel $\chi$-abductive problem, that is, $\lnot {\mathrm{Inf }}\,{\chi } \wedge \lnot {\mathrm{Inf }}\,{\lnot \chi }$ holds. A formula $\psi$ is an abductive solution to this problem iff, when added to the agent’s information, the agent becomes informed about $\chi$. In a formula,

$$\begin{aligned} \langle \mathrm{Add }_{\psi }\rangle \,{\mathrm{Inf }}\,{\chi } \end{aligned}$$

Now suppose the agent has an anomalous $\chi$-abductive problem, that is, $\lnot {\mathrm{Inf }}\,{\chi } \wedge {\mathrm{Inf }}\,{\lnot \chi }$ holds. A formula $\psi$ is an abductive solution to this problem iff the agent can revise her information to remove $\lnot \chi$ from it, producing in this way a novel $\chi$-abductive problem for which $\psi$ is a solution. In a formula,

$$\begin{aligned} \langle \mathrm{Rem }_{\lnot \chi }\rangle \,\big ( \lnot {\mathrm{Inf }}\,{\lnot \chi } \;\wedge \; \langle \mathrm{Add }_{\psi }\rangle \,{\mathrm{Inf }}\,{\chi }\big ) \end{aligned}$$

We can also provide formulas that characterize properties of abductive solutions.

Definition 6

(Classification of subjective abductive solutions) Suppose an agent has a $\chi$-abductive problem. A solution $\psi$ is

• consistent iff it is a solution and can be added to the agent’s information without making it inconsistent:

  $$\begin{aligned} \langle \mathrm{Add }_{\psi }\rangle \,\big ({\mathrm{Inf }}\,{\chi } \wedge \lnot {\mathrm{Inf }}\,{\bot } \big ) \end{aligned}$$

• explanatory iff it is a solution and it does not entail $\chi$, that is, it only complements the agent’s information to produce $\chi$:

  $$\begin{aligned} \psi \rightarrow \chi \;\; \text {is not valid},\quad \hbox {and}\;\; \langle \mathrm{Add }_{\psi }\rangle \,{\mathrm{Inf }}\,{\chi } \end{aligned}$$

• minimal iff it is a solution and, for any other solution $\varphi$, if $\varphi$ is incorporated into the agent’s information after $\psi$ is added, then $\psi$ is also incorporated into the agent’s information after $\varphi$ is added.

  $$\begin{aligned} \langle \mathrm{Add }_{\psi }\rangle \,{\mathrm{Inf }}\,{\chi } \wedge \Big ( \big (\langle \mathrm{Add }_{\varphi }\rangle \,{\mathrm{Inf }}\,{\chi } \wedge \langle \mathrm{Add }_{\psi }\rangle \,{\mathrm{Inf }}\,{\varphi }\big ) \rightarrow \langle \mathrm{Add }_{\varphi }\rangle \,{\mathrm{Inf }}\,{\psi }\Big ) \end{aligned}$$

Our just provided formulas are straightforward translations of the classic definitions of an abductive problem and an abductive solution. But in these classic definitions the set of formulas $\varPhi$ is understood as closed under logical consequence: we have provided definitions just for omniscient agents. Of course, non-omniscient agents can also face abductive problems.

3 Different Problems for Different Kinds of Agents

Though examples of abductive reasoning involve agents and their information, not all abductive problems have the same form. For example, while in the Holmes’ example what Sherlock is missing is a premise that would allow him to derive Mr. Wilson cuff’s status, in the mechanics’ one what is missing is a relation between facts (that is, a rule). And we can even think on situations in which what is missing is not some piece of information, but rather a reasoning step (see Subsect. 3.1).

Pierce himself did not remain quite convinced that one logical form covers all cases of abductive reasoning (Peirce 1911). In fact, different forms of abductive problems arise when we consider agents with different abilities, and even more appear when we combine different notions of information. In this section we will discuss some examples, presenting formulas stating that certain $\chi$ poses an abductive problem, and that certain $\psi$ is a solution to it.²

3.1 Adding Reasoning to the Picture

Suppose that Karl is in his dining room and sees smoke going out of the kitchen. Karl does not understand why there would be smoke, but then he realizes that the chicken he put on the fire has been there for a long time, and it should be burnt by now. Though initially Karl did not have any explanation about the smoke, he did not need any additional information in order to find a reason for the fire: a simple reasoning step was more than enough.

This case does not correspond to any of the abductive problems described before (Definition 4), and the reason is that Karl is not an omniscient agent: he does not have all logical consequences of his information, and therefore he did not realize that the information he had before seeing the smoke was enough to predict it (i.e, to infer that there would be smoke). This shows that non-omniscient agents can face at least a new kind of abductive problem.

In order to provide formal definitions for abductive problems and solutions involving non-omniscient agents, we need to distinguish between the information the agent actually has, her explicit information (${\mathrm{Inf }_{\mathrm{Ex }}}\,{}$), and what follows logically from it, her implicit information (${\mathrm{Inf }_{\mathrm{Im }}}\,{}$) [see, e.g., Levesque (1984), Vardi (1986)]. Based on this distinction we can say that, for a non-omniscient agent to have an $\chi$-abductive problem, $\chi$ should not be part of her explicit information. Then, just as there are two abductive problems according to whether the agent is informed about $\lnot \chi$ or not, a non-omniscient agent can face eight different abductive problems, according to whether the agent has explicit information about $\lnot \chi$ or not, and whether she has implicit information about $\chi$ and $\lnot \chi$ or not (Table 1). However, not all these cases are possible: according to our intuition, explicit information should be also implicit information, that is, we should have

$$\begin{aligned} {\mathrm{Inf }_{\mathrm{Ex }}}\,{\varphi } \rightarrow {\mathrm{Inf }_{\mathrm{Im }}}\,{\varphi } \end{aligned}$$

Then we can discard the cases in which this formula does not hold.³

Table 1 Abductive problems for non-omniscient agents

Definition 7

(Non-omniscient abductive problems) A non-omniscient agent can face six different abductive problems, each one of them characterized by a formula in Table 1.

The smoke example corresponds to the case (1.2). Though the observation is surprising before it takes place (that is, the agent is not explicitly informed about the smoke in the kitchen), she had this information implicitly, and she could have predicted it by the proper reasoning step(s).

Abductive solutions. A solution for a $\chi$-abductive problem has now as a goal to make the agent explicitly informed about $\chi$, without having neither implicit nor explicit information about $\lnot \chi$. Each one of the different cases admits different kinds of solutions; let us briefly review the possibilities for the consistent cases, leaving (1.4) and (2.4) for future work.

In case (1.1) the agent needs extra external information; this is because $\chi$ is not even part of her implicit information. If the extra information $\psi$ makes $\chi$ already explicit, nothing else is needed; otherwise, if it makes it only implicit, then the agent will need to perform a further reasoning step. In case (1.2), the one of our example, reasoning is enough and extra information is not essential. Cases (1.3) and (2.3) contain an anomaly: in the first, the anomaly is implicit and the agent needs to make it explicit before solving it; in the second, the anomaly is already explicit, and after solving it the agent will be in case (1.1). In each case there is more than one strategy (i.e., more than one sequence of actions) that solves the abductive problem; for simplicity we will focus on the most representative one for each one of them.

What is interesting here is how, though cases (1.1) and (2.3) are essentially the novel and anomalous abductive cases from before (see Definition 4), cases (1.2) and (1.3) are truly new, and their solutions involve an action that typically is not considered for solving abductive problems: a reasoning step that makes explicit information that was only implicit before. For example, though external information can solve case (1.2), the agent does not really need that: a reasoning step is enough. And for case (1.3), though the agent only sees a novel abductive problem, she has in fact an anomalous one that should be made explicit via reasoning before it can be properly solved.

In the following definition, formulas of the form $\langle \alpha \rangle \,\varphi$ indicate that the agent can perform some reasoning step $\alpha$ after which $\varphi$ is the case.

Definition 8

(Non-omniscient abductive solutions) Representative solutions for consistent non-omniscient abductive problems appear in Table 2.

Classification of abductive solutions. The extra requisites of Definition 6 can be adapted to this non-omniscient case. The consistency and the explanatory requirements do not have important changes (for the first we ask for the agent’s implicit information to be consistent at the end of the sequence of actions: $\lnot {\mathrm{Inf }_{\mathrm{Im }}}\,{\bot }$). The minimality requirement now gives us more options. We can define it over the action $\langle \mathrm{Add }_{\psi }\rangle \,$, looking for the weakest formula $\psi$, but it can also be defined over the action $\langle \mathrm{Rem }_{\lnot \chi }\rangle \,$, looking for the revision that removes the smallest amount of information. It can even be defined over the action $\langle \alpha \rangle \,$, looking for the shortest reasoning chain.

Table 2 Solutions for consistent non-omniscient abductive problems

3.2 Not Only Formulas But Also Rules

Consider now the mechanics example. At some stage in history, the scientific community, our ‘agent’, observed the trajectory described by cannonballs, and become interested in explaining this and other related phenomena. But rather than a plain piece of information, the found explanation was an equation that relates initial speed, initial angle and gravity with the described trajectory. In other words, the found explanation was a rule that, given the initial conditions, returns us the movement of the projectile.⁴

Again, this case does not fit any of the abductive problems described before. The difference is that our ‘agent’ is not only non-omniscient in the sense that not all her implicit information is also explicit; she also lacks of the necessary reasoning tools that would allow her to make explicit her implicit information. To put it in other words, besides not having all the logical consequences of her explicit information automatically, the agent might not be able to even derive them. This gives us another kind of agent, and therefore a new and finer classification of abductive problems and abductive solutions.

In order to classify the new abductive problems, we need to make a further distinction: we need to distinguish between what follows logically from the agent’s explicit information, the objectively implicit information (${\mathrm{Inf }_{\mathrm{Im }}}\,{}$), and what the agent can actually derive, the subjectively implicit information (${\mathrm{Inf }_{\mathrm{Der }}}\,{}$). With this refinement, each one of the six abductive problems of Table 1 turns into four cases, according to whether the agent can derive or not what follows logically from her explicit information, that is, according to whether ${\mathrm{Inf }_{\mathrm{Der }}}\,{\chi }$ and ${\mathrm{Inf }_{\mathrm{Der }}}\,{\lnot \chi }$ hold or not. However, we can also make further reasonable assumptions: explicit information is derivable (by the do-nothing action) and derivable information is also implicit (this assumes that the agent’s inferential tools are sound). Then we have

$$\begin{aligned} {\mathrm{Inf }_{\mathrm{Ex }}}\,{\varphi } \rightarrow {\mathrm{Inf }_{\mathrm{Der }}}\,{\varphi } {\qquad \quad \text {and}\quad \qquad } {\mathrm{Inf }_{\mathrm{Der }}}\,{\varphi } \rightarrow {\mathrm{Inf }_{\mathrm{Im }}}\,{\varphi } \end{aligned}$$

Definition 9

(Extended abductive problems) A non-omniscient agent without complete reasoning abilities can face eleven different abductive problems, each one of them characterized by a formula in Table 3.

The mechanics example corresponds to the case (1.2.a). The trajectory of a projectile is fixed (that is, it is implicit information) once the initial conditions are given; nevertheless, the scientific community could not predict (i.e., derive) the trajectory without knowing the relevant equations.

Table 3 Abductive problems with subjectively/objectively implicit information

Abductive solutions. As in Subsect. 3.1, introducing agents with new limitations allows us to explore other actions for solving abductive problems. For example, though case (1.2.b) can be solved by reasoning steps ($\chi$ is subjective implicit information so the agent can derive it), this is not possible in case (1.2.a): $\chi$ is objectively but not subjectively implicit information, so the agent cannot derive it. This case can be solved with a formula that, when added to the agent’s explicit information, makes $\chi$ explicit. More interestingly, it can be also solved by extending the agent’s reasoning abilities with a formula/rule that allows her to derive $\chi$. The same happens with other cases.

As before, different epistemic actions allow us to move between the abductive problems of Table 3. Again, we will focus on the consistent cases, discarding (1.4.$*$) and (2.4.d); again, though some abductive problems accept more than one sequence of steps as a solution, in each case we will focus on the most representative one. In Table 4, the action $\langle \mathrm{Add }_{\psi /\alpha }\rangle \,$ extends the agent’s explicit information by adding a formula $\psi$ or some inference resource $\alpha$ (e.g., a rule) that increases the agent’s subjectively implicit information.

Table 4 Solutions for consistent extended abductive problems

Definition 10

(Extended abductive solutions) Solutions for consistent extended abductive problems are provided in Table 4, which should be read as a transition table that provides actions and conditions that should hold in order to move from one abductive problem to another.

Table 4 establishes a natural path to solve the new abductive problems. The longest path corresponds to case (1.3.a) in which the agent does not have explicit information about neither $\chi$ nor $\lnot \chi$ and, though $\lnot \chi$ follows logically from her explicit information, she cannot derive it. In this case, the agent should first get enough information to derive $\lnot \chi$, thus going into case (1.3.c). Then, after reasoning to derive $\lnot \chi$, she will have an explicit anomaly, case (2.3.c). Once there she needs to revise her information to remove $\lnot \chi$ from it and, when done (case (1.1.a)), she needs to extend her information with some $\psi$ that will make her be explicitly informed about $\chi$.

Collapsing the cases. From a subjective point of view, the agent does not need to solve an anomaly that she cannot detect. What guides the process of solving an abductive problem is the explicit information and what she can derive from it. In other words, inaccessible anomalies should not matter.

Following this observation, we can notice that some problems in Table 3 are in fact indistinguishable for the agent. Without further external interaction, she can only access her explicit information and eventually what she can derive from it; the rest, the implicit information that is not derivable, is also not relevant. For example, abductive problems (1.{1,2,3,4}.a) are in fact the same from the agent’s perspective. Then, by grouping indistinguishable problems, we get the following.

Note how these classes correspond to abductive problems in Table 1 in which ${\mathrm{Inf }_{\mathrm{Der }}}\,{}$ appears in place of ${\mathrm{Inf }_{\mathrm{Im }}}\,{}$.

3.3 Explaining Explicit Information

Abduction is usually defined as the problem of explaining a surprising observation. Novelty is an important characteristic of the fact to explain. So, what is the purpose of explaining the information the agent already has explicitly? This information (knowledge or belief) is not supposed to be surprising at all.

But let us look at this from another perspective. When we make a (truthful) observation, as surprising as it can be, it automatically becomes part of our explicit information. After observing Mr. Wilson’s cuffs, Holmes knows that while one is very shiny on some area, the other one has a smooth patch; after observing the grass, Karen knows it is wet. What makes this explicit information special (that is, what makes the agent look for an explanation) is that it cannot be justified with the rest of the explicit information the agent possesses. For example, the fifth postulate is an obvious piece of explicit information in Euclidean geometry. But, can it be proved from the first four postulates?⁵ This generates a variant of an abductive problem that does not depend of recent observations but rather from unjustified information. The agent identifies a piece of explicit information she has and, when she realizes that it cannot be supported by the rest of her information, she tries to find an explanation for it.

One way of stating abductive problems of this form is the following. We introduce the modality $\mathrm{Dis }_{\varphi }$, representing the action through which the formula $\varphi$ is discarded from the agent’s explicit information. Note how this action differs from $\mathrm{Rem }_{\varphi }$: while the latter removes $\varphi$ from the agent’s implicit information, making $\varphi$ inaccessible without further external interaction, the former removes $\varphi$ only from the agent’s explicit information, and therefore $\varphi$ will be derivable whenever the agent has the proper tools to do it. This ‘discarding’ action intends to satisfy

$$\begin{aligned} {\mathrm{Inf }_{\mathrm{Ex }}}\,{\varphi } \;\rightarrow \; [\mathrm{Dis }_{\varphi }]\, ({\mathrm{Inf }_{\mathrm{Im }}}\,{\varphi } \wedge \lnot {\mathrm{Inf }_{\mathrm{Ex }}}\,{\varphi }) \end{aligned}$$

With this modality we can now make a further distinction in the agent’s explicit information, splitting it in what she knows and can actually justify (for example, if no one provides us the quadratic formula, we can still derive it by using the method of completing squares), and what she knows but cannot derive if she would have not observed it (if Holmes had not seen Mr. Wilson, he had not known the status of his cuffs). More precisely, we say that $\varphi$ is observed explicit information if, after being discarded, becomes not derivable:

$$\begin{aligned} {\mathrm{Inf }_{\mathrm{Ex }}}\,{\varphi } \;\wedge \; \langle \mathrm{Dis }_{\varphi }\rangle \, \lnot {\mathrm{Inf }_{\mathrm{Der }}}\,{\varphi } \end{aligned}$$

On the other hand, we say that $\varphi$ is entailed explicit information if, after being discarded, the agent can still derive it:

$$\begin{aligned} {\mathrm{Inf }_{\mathrm{Ex }}}\,{\varphi } \;\wedge \; \langle \mathrm{Dis }_{\varphi }\rangle \, {\mathrm{Inf }_{\mathrm{Der }}}\,{\varphi } \end{aligned}$$

Abductive problems of Table 3 in which $\lnot {\mathrm{Inf }_{\mathrm{Der }}}\,{\chi }$ is the case (i.e., abductive problems ($*$.$*$.{a,c})) can be adapted for observed explicit information. If $\Omega$ is the formula that represents the abductive problem labelled as n, then:

$$\begin{aligned} {\mathrm{Inf }_{\mathrm{Ex }}}\,{\chi } \;\wedge \; \langle \mathrm{Dis }_{\chi }\rangle \, \Omega \end{aligned}$$

is the formula that represents the version of abductive problem n for observed explicit information. The solutions of these problems start with $\langle \mathrm{Dis }_{\chi }\rangle \,$ and then proceed as in Table 4.

3.4 Different Notions of Information

Some of the cases we have reviewed in this section can be dropped by asking for additional requirements, now on the agent’s information. Two are the main constrains we can impose. The strongest one is to assume that the information is true; a weaker assumption is to assume that the information is simply consistent.

The first assumption, truth, corresponds syntactically to ${\mathrm{Inf }}\,{\varphi } \rightarrow \varphi$ in the case of omniscient agents, and to ${\mathrm{Inf }_{\mathrm{Im }}}\,{\varphi } \rightarrow \varphi$ in the case of non-omniscient ones. Under this assumption, the agent can face novel abductive problems because she does not need to have complete information about the real situation, and therefore there may be a fact $\chi$ that is not part of her information. Solutions in these cases should satisfy the further requirement of preserving the information’s properties, so a solution $\psi$ for a $\chi$-abductive problem needs to be true.⁶ But anomalous abductive problems are not possible: the agent’s information is true, so if she faces a $\chi$ contradicting it, she can be sure that $\chi$ is not true, and therefore can simply discard it.

The second assumption, consistency, corresponds syntactically to $\lnot {\mathrm{Inf }}\,{\bot }$ in the case of omniscient agents, and $\lnot {\mathrm{Inf }_{\mathrm{Im }}}\,{\bot }$ in the case of non-omniscient ones. With this assumption, novel abductive problems are possible, but also anomalous ones since the agent’s information does not need to be true. As in the previous cases, a solution should preserve the relevant property of the agent’s information, that is, the solution should not create an inconsistency when added to the agent’s information. This makes all solutions consistent.

Although other requirements can be imposed, these two allow us to deal with two of the most important notions of information: knowledge, often assumed to be true, and beliefs, often assumed to be just consistent.

4 A Semantic Model

Through the discussion in Sects. 2 and 3 we have observed how considering particular kinds of agents and particular notions of information gives us different forms of abductive problems. We have identified formulas expressing the existence of diverse forms of abductive problems and also expressing that certain formula is indeed a solution. This section makes part of the discussion concrete by providing a semantic model in which some the proposed cases can be evaluated. In order to make the discussion precise, we will work with the following variation of a classic example (Aliseda 2006).

Mary arrives late to her apartment. She presses the light switch but the light does not turn on. Knowing that the electric line is outdated, Mary assumes that it might have failed.

Let us analyse the situation. The first step in Mary’s reasoning is her irrefutable observation that the light does not turn on. After observing it, this fact becomes part of Mary’s knowledge, but it is knowledge that is not justified (i.e., supported) by the rest of her information. In other words, before the observation, Mary did not have any piece of information that would have allowed her to predict that indeed the light would not turn on. Nevertheless, she knows that the line is outdated, and therefore after observing that the light does not work, it is reasonable for her to assume that the line has failed: if she had known that before, she would have expected the lack of light. More precisely, Mary knows a piece of information (the light does not turn on) and she also knows how she could have predicted it (if the electric line has failed, then there will be no light). Then, Mary has reasons to suspect that what she would have needed to make the prediction is actually the case (she believes that the electric line has failed).⁷

This shows us the needed ingredients for a semantic representation of this form of abductive reasoning. First, we need to represent not only an agent’s knowledge but also her beliefs. Second, we need to represent the tools the agent has to perform inferences: these tools are precisely the ones that provide her with the possible explanations for her observation.

There are several frameworks in the literature that allow us to represent an agent’s knowledge and beliefs [e.g., Kraus and Lehmann (1986), Hoek (1993), Voorbraak (1993), Baltag and Smets (2008)]. The plausibility models of Baltag and Smets (2008) [cf. Benthem (2007)] have the further advantage of allowing us to represent the actions that transform these notions, as observations in the case of knowledge and revision in the case of beliefs. For the last ingredient, the agent’s inferential tools, we can look at the approach of Velázquez-Quesada (2010) which extends plausibility models with ideas from Fagin and Halpern (1988) and Jago (2006) in order to deal with the notions of implicit and explicit information. The resulting framework allows us to represent an agent’s implicit/explicit knowledge/beliefs not only about formulas but also about rules.

4.1 Plausibility-Access Models

Definition 11

(PA language (Velázquez-Quesada 2010)) Given a set of atomic propositions $\mathtt {P}$, formulas $\varphi , \psi$ and rules $\rho$ of the plausibility-access (PA) language $\mathcal {L}$ are given by

$$\begin{aligned} \varphi&\;\;::= p \mid \mathrm{A }{\varphi } \mid \mathrm{R }{\rho } \mid \lnot \varphi \mid \varphi \vee \psi \mid \langle \sim \rangle \,{\varphi } \mid \langle \le \rangle \,{\varphi } \\ \rho&\;\;::= (\{{\psi _1, \dots , \psi _{n_\rho }}\}, \varphi ) \end{aligned}$$

where $p$ is an atomic proposition in $\mathtt {P}$. For the first component of the language, formulas of the form $\mathrm{A }{\varphi }$ are read as “the agent has access to formula $\varphi$”, and formulas of the form $\mathrm{R }{\rho }$ as “the agent has access to rule $\rho$”. For the modalities, $\langle \le \rangle \,{\varphi }$ is read as “there is an at least as plausible world where $\varphi$ holds”, and $\langle \sim \rangle \,{\varphi }$ as “there is an epistemically indistinguishable world where $\varphi$ holds”. Other boolean connectives as well as the universal modalities $[\sim ]\,{}$, $[\le ]\,{}$ are defined as usual. For the second component, a rule $\rho$ is a pair $(\{{\psi _1, \dots , \psi _{n_\rho }}\}, \varphi )$, sometimes represented as $\{{\psi _1, \dots , \psi _{n_\rho }}\} \Rightarrow \varphi$ ($\psi \Rightarrow \varphi$ in case the first component is a singleton), where $\{{\psi _1, \dots , \psi _{n_\rho }}\}$ is a finite set of formulas, the rule’s premises $\mathsf {pm}(\rho )$, and $\varphi$ is a formula, the rule’s conclusion $\mathsf {cn}(\rho )$. We denote by ${{\mathcal {L}_{f}}}$ the set of formulas of $\mathcal {L}$, and by ${{{\mathcal {L}}_{r}}}$ its set of rules.

The language $\mathcal {L}$ is the propositional one extended with four new kinds of formulas. Formulas of the form $\langle \sim \rangle \,{\varphi }$ and $\langle \le \rangle \,{\varphi }$ will allow us to deal with the notions of knowledge and belief, respectively. Formulas of the form $\mathrm{A }{\varphi }$ and $\mathrm{R }{\rho }$ will allow us to deal with the agent’s explicit beliefs/knowledge about formulas and rules.

The intuitive ideas behind the semantic model for $\mathcal {L}$ are the following. First, the agent’s epistemically indistinguishable worlds are not given by a plain set but rather by a set with a plausibility ordering; then, while knowledge is defined in terms of all epistemically indistinguishable worlds, beliefs are defined only in terms of the most plausible (i.e., the maximal) ones (Grove 1988; Boutilier 1994; Segerberg 2001). Second, a non-omniscient agent may not have access to all formulas and rules that are true and truth-preserving at each world; then, explicit knowledge/beliefs are defined in terms of what the agent has actually access to (Fagin and Halpern 1988; Jago 2006). Formally, the semantic model extends the plausibility models of Baltag and Smets (2008) with two functions, indicating the formulas and the rules the agent has access to at each possible world.

Definition 12

(PA model (Velázquez-Quesada 2010)) Let $\mathtt {P}$ be a set of atoms. A plausibility-access (PA) model is a tuple $M=\langle W,\le ,V,\mathsf {A},\mathsf {R} \rangle$ where

• $W$ is a non-empty set of possible worlds;

• $\le \; \subseteq (W \times W)$ is a well pre-order (a locally connected and a conversely well-founded preorder), the plausibility relation, representing the plausibility order of the worlds from the agent’s perspective ($w \le u$ is read as “$u$ is at least as plausible as $w$”);

• $V:W \rightarrow \wp (\mathtt {P})$ is an atomic valuation function, indicating the atomic propositions in $\mathtt {P}$ that are true at each possible world;

• $\mathsf {A}:W \rightarrow \wp ({\mathcal {L}_{f}})$ is the access set function, indicating the set of formulas the agent has access to at each possible world;

• $\mathsf {R}:W \rightarrow \wp ({{\mathcal {L}}_{r}})$ is the rule set function, indicating the set of rules the agent has access to at each possible world.

A pointed PA model $(M, w)$ is a PA model with a distinguished world $w \in W$.

The plausibility relation $\le$ will allow us to define the agent’s beliefs as what is true in the most plausible worlds. For defining the agent’s knowledge, the indistinguishability relation $\sim$ is defined as the union of $\le$ and its converse, that is, $\sim \,:=\, \le \cup \ge$. ⁸

For the semantic interpretation, the two modalities $\langle \le \rangle \,{}$ and $\langle \sim \rangle \,{}$ are interpreted via their respective relations in the standard way; the two ‘access’ formulas $\mathrm{A }{\varphi }$ and $\mathrm{R }{\rho }$ simply look at the $\mathsf {A}$- and $\mathsf {R}$-set of the evaluation point.

Definition 13

(Semantic interpretation) Let $(M, w)$ be a pointed PA model with $M=\langle W, \le , V, \mathsf {A}, \mathsf {R} \rangle$. Atomic propositions and boolean operators are interpreted as usual. For the remaining cases,

$$\begin{aligned}&(M, w) \Vdash \mathrm{A }{\varphi }\,\hbox { iff }\,\varphi \in \mathsf {A}(w) \\&(M, w) \Vdash \mathrm{R }{\rho }\quad \hbox { iff }\quad \rho \in \mathsf {R}(w) \\&(M, w) \Vdash \langle \le \rangle \,{\varphi }\,\hbox { iff }\quad \hbox { there is a }u \in \hbox { W such that }w \le u\quad \hbox { and }(M, u) \Vdash \varphi \\&(M, w) \Vdash \langle \sim \rangle \,{\varphi }\,\hbox { iff }\quad \hbox { there is a }u \in W\hbox { such that }w \sim u\quad \hbox { and }(M, u) \Vdash \varphi \\ \end{aligned}$$

Defining the notions. For the notion of implicit knowledge, the classic EL approach is used: the agent knows $\varphi$ implicitly iff $\varphi$ is true in all the worlds she considers possible from the evaluation point. For $\varphi$ to be explicitly known, the agent needs to have access to it in all such worlds:

The agent knows implicitly the formula $\varphi$	${K_{\mathrm{Im }}}{\varphi }:=[\sim ]\,{\varphi }$
The agent knows explicitly the formula $\varphi$	${K_{\mathrm{Ex }}}{\varphi }:=[\sim ]\,{(\varphi \wedge \mathrm{A }{\varphi })}$

On the other hand, the notion of beliefs does not need to look at all the epistemically indistinguishable worlds, just to those that are the most likely to be the case: an agent believes $\varphi$ implicitly iff $\varphi$ is true in the most plausible worlds under the agent’s plausibility order. Given the properties of the plausibility relation, $\varphi$ is true in the most plausible worlds from the evaluation point iff there is a more plausible world from which all better ones are $\varphi$-worlds (Stalnaker 2006; Baltag and Smets 2008). For its explicit form, it is asked for the agent to have access to $\varphi$ in these maximal worlds.

The agent believes implicitly the formula $\varphi$	${B_{\mathrm{Im }}}{\varphi }:=\langle \le \rangle \,{[\le ]\,{\varphi }}$
The agent believes explicitly the formula $\varphi$	${B_{\mathrm{Ex }}}{\varphi }:=\langle \le \rangle \,{[\le ]\,{(\varphi \wedge \mathrm{A }{\varphi })}}$

We have now the notions of implicit/explicit knowledge/beliefs for formulas. For the case of rules, in the implicit case, a rule $\rho$ is translated into an implication $\mathsf {tr}(\rho )$ whose antecedent is the (finite) conjunction of the rule’s premises and whose consequent is the rule’s conclusion ($\bigwedge _{\psi \in \mathsf {pm}(\rho )} \psi \rightarrow \mathsf {cn}(\rho )$); in the explicit case, the ‘access to rule’ formulas are used:

The agent knows implicitly the rule $\rho$	${K_{\mathrm{Im }}}{\rho }:=[\sim ]\,{\mathsf {tr}(\rho )}$
The agent knows explicitly the rule $\rho$	${K_{\mathrm{Ex }}}{\rho }:=[\sim ]\,{\big (\mathsf {tr}(\rho ) \wedge \mathrm{R }{\rho }\big )}$
The agent believes implicitly the rule $\rho$	${B_{\mathrm{Im }}}{\rho }:=\langle \le \rangle \,{[\le ]\,{\mathsf {tr}(\rho )}}$
The agent believes explicitly the rule $\rho$	${B_{\mathrm{Ex }}}{\rho }:=\langle \le \rangle \,{[\le ]\,{\big (\mathsf {tr}(\rho ) \wedge \mathrm{R }{\rho }\big )}}$

Details of this framework can be found in Velázquez-Quesada (2010). We now move on to a definition of two actions and how they can be used to represent some forms of abductive reasoning.

4.2 Operations Over Plausibility-Access Models

In a PA model, the agent’s beliefs are given by the plausibility relation. Then, changes in beliefs can be represented by changes in this relation (Ditmarsch 2005; Benthem 2007; Baltag and Smets 2008). In particular, the act of revising beliefs with the aim to believe a given $\phi$ can be seen as a change that puts $\phi$-worlds at the top of the plausibility order. There are several ways in which such a new order can be defined; each one of them can be seen as a different policy for revising beliefs. Here is one of the many possibilities.

Definition 14

(Upgrade operation) Let $M=\langle W, \le , V, \mathsf {A}, \mathsf {R} \rangle$ be a PA model; let $\phi$ be a formula in ${{\mathcal {L}_{f}}}$. The upgrade operation yields the PA model ${M}_{{\phi }\Uparrow } = \langle W, \le ', V, \mathsf {A}, \mathsf {R} \rangle$, differing from $M$ just in the plausibility order:

$$\begin{aligned} \le ' := (\le ;\phi ? ) \;\cup \; (\lnot \phi ?;\le ) \;\cup \; (\lnot \phi ?;\sim ;\phi ? ) \end{aligned}$$

The new plausibility relation, given in a Propositional Dynamic Logic style, states that after an explicit upgrade with $\phi$, “all $\phi$ -worlds become more plausible than all $\lnot \phi$ -worlds, and within the two zones the old ordering remains” (Benthem 2007). More precisely, we will have $w \le ' u$ iff (1) $w \le u$ and $u$ is a $\phi$-world, or (2) $w$ is a $\lnot \phi$-world and $w \le u$, or (3) $w \sim u$, $w$ is a $\lnot \phi$-world and $u$ is a $\phi$-world.

PA models also have syntactic components: a set of formulas and a set of rules at each possible world. Here is an operation that modifies the first.

Definition 15

(Uncovering operation) Let $M=\langle W, \le , V, \mathsf {A}, \mathsf {R} \rangle$ be a PA model; let $\varPhi$ be a set of formulas. Define $T_{\varPhi }(M,w)$ as

$$\begin{aligned} T_{\varPhi }(M,w) := \{{\phi \mid \phi \in \varPhi \hbox { and }(M, w) \Vdash \phi }\} \;\cup \; \{{\lnot \phi \mid \phi \in \varPhi \hbox { and }(M, w) \not \Vdash \phi }\} \end{aligned}$$

that is, $T_{\varPhi }(M, w)$ is a set of formulas that contains, for each $\phi \in \varPhi$, $\phi$ itself if $\phi$ holds at $(M, w)$, and $\lnot \phi$ if $\phi$ does not hold at $(M, w)$.

The uncovering operation produces the PA model ${M}_{+{\varPhi }}=\langle W, \le , V, \mathsf {A}', \mathsf {R} \rangle$, differing from $M$ just in the access set function, given now for each $w \in W$ by:

$$\begin{aligned} \mathsf {A}'(w) := \mathsf {A}(w) \;\cup \; T_{\varPhi }(M,w) \end{aligned}$$

This operation makes explicit the formulas in $\varPhi$. More precisely, for every $w \in W$, $\mathsf {A}(w)$ will be extended with the formulas in $\varPhi$ that $w$ satisfies and with the negations of the formulas in $\varPhi$ that it does not satisfy.

For the language, we introduce the modalities $\langle {\phi }\Uparrow \rangle \,\varphi$ and $\langle +{\varPhi }\rangle \,\varphi$, with their semantic interpretation given below.

Definition 16

Let $M=\langle W, \le , V, \mathsf {A}, \mathsf {R} \rangle$ be a PA model. Then,

$$\begin{aligned}&(M, w) \Vdash \langle {\phi }\Uparrow \rangle \,\varphi \quad \hbox {iff}\quad ({M}_{{\phi }\Uparrow }, w) \Vdash \varphi \\&(M, w) \Vdash \langle +{\varPhi }\rangle \,\varphi \quad \hbox {iff}\quad ({M}_{+{\varPhi }}, w) \Vdash \varphi \end{aligned}$$

Based on these two operations, we will now provide an action that represents an abductive reasoning step.

4.3 An Action Representing Abductive Reasoning

The key observation of the discussed Mary’s example is that the described form of abductive reasoning can be seen as a form of belief revision guided by the agent’s inferential abilities: if the agent knows explicitly a rule and its conclusion, then it is reasonable for her to believe explicitly all the rule’s premises. Following this idea, here is our proposal for an action representing this form of abductive reasoning.

Definition 17

(Abductive reasoning with rule $\sigma$) In order to represent abductive reasoning with a given rule $\sigma$, we introduce a new modality that allows us to build formulas of the form $\langle \mathrm{Abd_\sigma }\rangle \,\varphi$, read as “the agent can perform an abductive step with rule $\sigma$ after which $\varphi$ is the case”. The semantic interpretation of formulas of this form is defined in the following way:

$$\begin{aligned} \big (M, w\big ) \Vdash \langle \mathrm{Abd_\sigma }\rangle \,\varphi \quad \hbox {iff}\,\, \big (M, w\big ) \Vdash {K_{\mathrm{Ex }}}{\sigma }\wedge {K_{\mathrm{Ex }}}{\mathsf {cn}(\sigma )}\hbox { and }\big ({({M}_{+{\mathsf {pm}(\sigma )}})}_{{P_\sigma }\Uparrow }, w\big ) \Vdash \varphi \end{aligned}$$

where the formula $P_{\sigma } := \bigwedge _{\psi \in \mathsf {pm}(\sigma )} \psi$ is the conjunction of all premises of $\sigma$ (if $\mathsf {pm}(\sigma )$ is empty, then $P_{\sigma }:=\top$).

Let us spell out this definition. The agent can perform an abductive step with rule $\sigma$ after which $\varphi$ is the case, $(M, w) \Vdash \langle \mathrm{Abd_\sigma }\rangle \,\varphi$, if and only if she knows explicitly the rule and its conclusion, $(M, w) \Vdash {K_{\mathrm{Ex }}}{\sigma } \;\wedge \; {K_{\mathrm{Ex }}}{\mathsf {cn}(\sigma )}$, and, after making explicit the premises of $\sigma$ and then putting on top of the plausibility order those worlds that satisfy all of them, $\varphi$ is the case, $({{M}_{+{\mathsf {pm}(\sigma )}}}_{{P_\sigma }\Uparrow }, w) \Vdash \varphi$. In other words, an abductive step with a rule $\sigma$ is an action that, provided that the rule and its premises are explicitly known, makes explicit $\sigma$’s premises and then lifts those worlds satisfying all of them. In the particular case in which $\sigma$’s premises are propositional formulas, after this sequence of operations, the agent will believe $\sigma$’s premises.⁹

4.4 An Example

In the PA model below, each possible world shows the atomic propositions that are true at it, and its $\mathsf {A}$- and $\mathsf {R}$-sets appear below it. In the model, Mary knows explicitly both that the light does not turn on ($\lnot l$) and that if the electric line fails ($\lnot e$), then there will be no light (this rule is abbreviated as $\lnot e \Rightarrow \lnot l$). Nevertheless, Mary does not believe, neither explicitly nor implicitly, that the electric line fails. The formulas on the right of the diagram express all this; they are true in every world in the model, so no evaluation point is specified.

If we understand information as knowledge, this is a case of an abductive problem with explicit knowledge of the observation $\lnot l$, as explained in Subsect. 3.3. The modality $\langle \mathrm{Dis }_{\chi }\rangle \,$ represents an action that removes $\chi$ from the explicit (but not from the implicit) knowledge, so we can define it in the PA framework as an operation that removes $\chi$ from the $\mathsf {A}$-sets of the worlds in the model [cf. the dropping operation of Benthem and Velázquez-Quesada (2010)]. Then, by applying $\langle \mathrm{Dis }_{\lnot l}\rangle \,$ to the PA model above, we get a similar model in which all $\mathsf {A}$-sets are empty, therefore representing a situation in which, though Mary does not have explicit knowledge of $\lnot l$, she has implicit knowledge about it. Now, if we understand inference as the application of explicitly known rules with explicitly known premises (Grossi and Velázquez-Quesada 2009), then Mary cannot make $\lnot l$ explicit only by inference (that is, only by applying the rule $\lnot e \Rightarrow \lnot l$) because, even though she knows explicitly the rule, she does not know explicitly the single premise. Hence, $\lnot l$ is objectively (${\mathrm{Inf }_{\mathrm{Im }}}\,{\lnot l}$) but not subjectively ($\lnot {\mathrm{Inf }_{\mathrm{Der }}}\,{\lnot l}$) implicit knowledge (Subsect. 3.2). In summary, the abductive problem she faces is given by

$$\begin{aligned} \langle \mathrm{Dis }_{\lnot l}\rangle \,\big ( \lnot {\mathrm{Inf }_{\mathrm{Ex }}}\,{\lnot l} \,\wedge \, \lnot {\mathrm{Inf }_{\mathrm{Ex }}}\,{l} \;\wedge \; \lnot {\mathrm{Inf }_{\mathrm{Der }}}\,{\lnot l} \,\wedge \, \lnot {\mathrm{Inf }_{\mathrm{Der }}}\,{l} \,\wedge \, {\mathrm{Inf }_{\mathrm{Im }}}\,{\lnot l} \;\wedge \; \lnot {\mathrm{Inf }_{\mathrm{Im }}}\,{l}\big ) \end{aligned}$$

This corresponds to case (1.2.a) on Table 3 with the modification introduced in Subsect. 3.3 ($\chi$ becomes $\lnot l$ and $\lnot \chi$ becomes $l$).¹⁰ According to Table 4 plus the modification described in Subsect. 3.3, in order for $\lnot e$ to be a solution, it should satisfy

$$\begin{aligned} \langle \mathrm{Dis }_{\lnot l}\rangle \,\langle \mathrm{Add }_{\lnot e}\rangle \,\langle \lnot e \Rightarrow \lnot {l}\rangle \,{\mathrm{Inf }_{\mathrm{Ex }}}\,{\lnot {l}} \end{aligned}$$

While the effect of $\langle \mathrm{Dis }_{\lnot l}\rangle \,$ has been already described, $\langle \mathrm{Add }_{\lnot e}\rangle \,$ can be understood as a form of public announcement (Plaza 1989; Gerbrandy 1999) of $\lnot e$ that removes the worlds where $\lnot e$ is false (that is, $w_1$) and adds $\lnot e$ to the $\mathsf {A}$-sets of the remaining worlds in which the formula is true [cf. the explicit seeing operation of Benthem and Velázquez-Quesada (2010)]. Then, by applying $\langle \mathrm{Dis }_{\lnot l}\rangle \,$ and then $\langle \mathrm{Add }_{\lnot e}\rangle \,$ to the initial PA-model, we get:

Now Mary’s information state is given by

$$\begin{aligned} \lnot {\mathrm{Inf }_{\mathrm{Ex }}}\,{\lnot l} \;\wedge \; \lnot {\mathrm{Inf }_{\mathrm{Ex }}}\,{l} \;\wedge \; {\mathrm{Inf }_{\mathrm{Der }}}\,{\lnot l} \;\wedge \; \lnot {\mathrm{Inf }_{\mathrm{Der }}}\,{l} \;\wedge \; {\mathrm{Inf }_{\mathrm{Im }}}\,{\lnot l} \;\wedge \; \lnot {\mathrm{Inf }_{\mathrm{Im }}}\,{l} \end{aligned}$$

which corresponds to the abductive problem (1.2.b) of Table 3, as indicated in Table 4. Mary has now subjectively implicit information of $\lnot l$; hence she only needs to apply her reasoning abilities to make ${\mathrm{Inf }_{\mathrm{Ex }}}\,{\lnot l}$ true. Thus, $\lnot e$ is indeed an abductive solution for the problem.

Following a classic terminology in Philosophy of Science, by proving that $\lnot e$ satisfies all the requisites to be a good explanation we have only dealt with the context of justification of abductive reasoning. There are three important points still to be discussed. First, where should the agent look for the possible explanations of the surprising observation (what is commonly called the context of discovery of abductive reasoning)? Our proposal is that candidates for solutions of a given $\chi$-abductive problem can be found in the premises of those rules that would have allowed the agent to derive $\chi$. Second, though in our example there is only one candidate for a solution, in general there will be more than one explanation for a given abductive problem, and in such cases the agent has to choose one (some) of them. Our proposal for dealing with this stage of the abductive process will be presented in Sect. 5. Third, once that the agent has chosen her explanation(s), she should somehow incorporate it(them) into her information. For this we will use the abductive operation of Definition 17 in which the explanation is not incorporated as knowledge (though plausible, the chosen explanation does not need to be the case) but rather as belief.

Back in our story, Mary has observed that the light does not turn on, therefore reaching an information state described in the left model of the diagram below. In order to explain the lack of light, Mary applies abductive reasoning with the rule $\lnot e \Rightarrow \lnot l$ (we have already justified why $\lnot e$ is a good candidate for an explanation). The model that results from this reasoning appears on the right.

There are two changes in the new model with respect to the original one. First, the unique premise of the chosen rule has been made explicit by adding it to the $\mathsf {A}$-set of $w_2$ and by adding its negation to the $\mathsf {A}$-set of $w_1$. Second, there is a new plausibility ordering: now the unique $\lnot e$-world, $w_2$, has become more plausible than the unique $e$-world, $w_1$. In this resulting model Mary still knows explicitly that there is no light (${K_{\mathrm{Ex }}}{\,\lnot l}$) and still knows explicitly the rule that links that with the failure of the electric line (${K_{\mathrm{Ex }}}{(\lnot e \Rightarrow \lnot l)}$). But, as a result of abductive reasoning, Mary now believes (both implicitly and explicitly) that the electric line has failed (${B_{\mathrm{Ex }}}{\,\lnot e} {\;\,\wedge \,\;} {B_{\mathrm{Im }}}{\,\lnot e}$).

Note how even if the original model had $w_2$ above $w_1$ as the sentence “Knowing that the electric line is outdated ...” in the original statement (page 14) may suggest, the operation does makes a difference since it makes explicit the premises of the chosen rule.

5 Selecting the Best Explanation

So far our proposal does not deal with the process of choosing the best explanation. In general, there will be more than one solution for a given abductive problem: Mary observed the lack of light with a failure in the electric line, but it could be also the case that the switch or even the bulb was broken. The selection of the best explanation is a fundamental problem in abductive reasoning [see, e.g. Lipton (1991) and Hintikka (1998)], and in fact many authors consider it the heart of abductive reasoning. But beyond logical requisites to avoid triviality [e.g., Definition 3], the definition of suitable criteria is still an open problem. In this section we adapt the ideas presented in Nepomuceno-Fernández et al. (2013) to our non-omniscient agents case.

Some typical selection criteria are restrictions on the logical form of the solutions, so that only abducible formulas are selected as possible explanations. For example, if we only allow conjunctions of literals as abductive solutions, a criterion for minimal explanation can be established on the length of these conjuncts. But finer criteria to select between two equally valid solutions require contextual aspects (Aliseda 2006). A typical option is the use of preferential models (e.g., Makinson (2003)), but such approaches are often criticized because they introduce an external resource.

Our subjective approach to abductive reasoning gives us a different perspective. The electric line in Mary’s house is outdated; knowing this, Mary considers its failure more likely than other possible explanation, and hence she explains the lack of light by assuming that the electric line has failed. But Mary’s friend Gaby does not know that the line is old, and therefore she explains the same fact by assuming what she considers more likely to happen: the bulb has failed. The two explanations are equally “logical” since a failure on the electric line or a broken bulb would be enough to explain why the light does not turn on; what makes Mary to choose the first and Gaby choose the second is that they have different knowledge and different beliefs. This suggests that instead of looking for criteria to select the best explanation, we should rather look for criteria to select the agent’s best explanation.

More precisely, and as the example shows, the explanation an agent will choose for a given observation depends not only on the logical properties of the candidates, but also on what the agent herself knows and considers more likely to be the case. This criteria is not “logical” in the classical sense, since it is not based exclusively on what can be derived from the explanation or even the number of needed inference steps. Nevertheless, it is logical in a broader sense since it depends on the agent’s information: her knowledge and her beliefs.

Here is how this idea reflects on the previous section’s proposal. We have suggested that the agent’s reasonable candidates for explanation of an observed $\chi$ are the premises of those rules that would allow her to derive $\chi$. In general, the agent might have several ways in which she could have derived the observed $\chi$ (she might have several rules with $\chi$ as conclusion). But the agent already has knowledge and beliefs, so she already considers, implicitly or explicitly, some of these explanations more likely than the others. In our example, Mary explains the light problem by assuming that the line is failing not because she does not consider the possibility that the bulb might be broken, but because after the light does not turn on, the failure on the line is, from her perspective, more likely to be the case. Consider this extended version of Mary’s adventure.

Mary arrives late to her apartment. She presses the light switch but the light does not turn on. Knowing that the electric line is outdated, Mary assumes that it might have failed, but then she takes a quick look at the alarm clock on her night table and realizes that it is working. This makes her to change her mind, and now she assumes that the bulb is broken.

After observing that the light does not turn on, Mary has two hypotheses: “the electric line fails” and “the bulb is broken”. She chooses the first as her explanation because at her apartment it is more common than the second. But then she observes that the alarm clock works; since this contradicts her first hypothesis, she discards the first and selects the second.

In order to show how we can capture Mary’s reasoning in the described framework, consider the PA model shown below, representing Mary’s knowledge and beliefs immediately after she observes (and therefore knows explicitly) that the light is not working. In the model (with reflexive arrows omitted), she has also explicit knowledge of the following rules: “if the electric line fails ($\lnot e$) then the light does not work ($\lnot l$)” ($\lnot e \Rightarrow \lnot l$) and “if the bulb is broken ($\lnot b$) then the light does not work ($\lnot l$)” ($\lnot b \Rightarrow \lnot l$).

The most plausible world ($w_4$) is the one in which nothing fails, as it is usual at Mary’s apartment. Nevertheless, from Mary’s perspective, a problem with the bulb is less plausible than a failure in the electric line ($w_3$ is below $w_2$), and the least plausible situation is the one in which both fail ($w_1$ is at the bottom). This is Mary’s personal plausibility ordering, according to her previous experience, and it will be the key for selecting her best explanation. Observe also how though Mary believes that nothing fails ($w_1$ is the most plausible world), this belief is just implicit and not explicit: the information about the failure of the electric line or the failure of the bulb is just implicit because the $\mathsf {A}$-sets do not contain formulas about them.

After the observation, Mary does not have an explanation for $\lnot l$: she does not know/believe explicitly anything that entails $\lnot l$ with the rules she knows (in particular, she knows/believes explicitly neither $\lnot e$ nor $\lnot b$). Thus, there is an abductive problem, and in order to solve it Mary can perform an abductive step with any of the two rules she knows explicitly: $\lnot e\Rightarrow \lnot l$ or $\lnot b\Rightarrow \lnot l$. Our proposal here is that Mary does not need to choose one of these rules; what she can do is to consider all of them, and then allow her previous plausibility order to decide which will be the chosen explanation, that is, which explanation she will believe explicitly. This solution is simpler but nevertheless more natural since the selection of the best explanation relies on Mary’s previous beliefs. In the following section we provide the definitions to make precise this idea.

5.1 A General Action Representing Abductive Reasoning

Definition 18

(Abductive reasoning) In order to represent general abductive reasoning, we introduce a new modality that allows us to build formulas of the form $\langle \mathrm{Abd_\chi }\rangle \,\varphi$, read as “the agent can perform an abductive step for formula $\chi$ after which $\varphi$ is the case”. In order to provide the semantic interpretation of these formulas, we first make the following definitions.

Denote by $R_\chi$ the set of the rules explicitly known by the agent at the pointed model $(M, w)$ that have $\chi$ as conclusion, that is,

$$\begin{aligned} R_\chi := \Big \{\sigma \in {{{\mathcal {L}}_{r}}} \mid \, (M, w) \Vdash {K_{\mathrm{Ex }}}{\sigma } \, \text { and }\, \mathsf {cn}(\sigma )=\chi \, \Big \} \end{aligned}$$

Then denote by $P_{R_\chi }$ the disjunction of the conjunction of all premises of each rule in $R\chi$, that is,

$$\begin{aligned} P_{R_\chi } := {\mathop {\bigvee }_{\sigma \in R_\chi }} {\mathop {\bigwedge }_{\psi \in \mathsf {pm}(\sigma )}} \psi \end{aligned}$$

Finally, denote by $\mathsf {pm}(R_\chi )$ the set of all premises of rules in $R\chi$:

$$\begin{aligned} \mathsf {pm}(R_\chi ) := {\mathop {\bigcup }_{\sigma \in R_\chi }} \mathsf {pm}(\sigma ) \end{aligned}$$

If $R_\chi \ne \emptyset$, the semantic interpretation of formulas of the form $\langle \mathrm{Abd_\chi }\rangle \,\varphi$ is defined in the following way:

$$\begin{aligned} \big (M, w\big ) \Vdash \langle \mathrm{Abd_\chi }\rangle \,\varphi \,\,\hbox { iff }\,\, \big (M, w\big ) \Vdash {K_{\mathrm{Ex }}}{\chi } \quad \hbox { and }\quad \big ({({M}_{+{\mathsf {pm}(R_\chi )}})}_{{P_{R_\chi }}\Uparrow }, w\big ) \Vdash \varphi \end{aligned}$$

Let us spell out the semantic interpretation. If the agent knows explicitly at least one rule with $\chi$ as conclusion (the $R_\chi \ne \emptyset$ requirement), then she can perform an abductive step for formula $\chi$ after which $\varphi$ is the case, $(M, w) \Vdash \langle \mathrm{Abd_\chi }\rangle \,\varphi$, if and only if she knows explicitly $\chi$, $(M, w) \Vdash {K_{\mathrm{Ex }}}{\chi }$, and after making explicit the all premises of all rules for $\chi$ she knows explicitly and then lifting those worlds that satisfy all the premises of at least one such rule, $\varphi$ is the case, $({{M}_{+{\mathsf {pm}(R_\chi )}}}_{{P_{R_\chi }}\Uparrow }, w) \Vdash \varphi$.

Observe the effect of this abductive step (i.e., of the sequence uncovering then upgrade), again for the case in which the premises of all such rules are propositional formulas. It will make explicit the premises of all the relevant rules and then it will lift those worlds that satisfy the conjunction of all the premises of at least of one of such rules (that is, $P_{R_\chi }$). But recall the effect of the upgrade operation with $P_{R_\chi }$: “all $P_{R_\chi }$ -worlds become more plausible than all $\lnot P_{R_\chi }$ -worlds, and within the two zones the old ordering remains”. Then, in the upper zone, the worlds that will be at the top will be those that satisfy $P_{R_\chi }$ and were already more plausible than the rest. Hence, the agent will believe the premises that were already more plausible for her.

5.2 The Example Revisited

We left Mary trying to explain why the light does not work. She has two rules with $\lnot l$ as conclusion, $\lnot e \Rightarrow \lnot l$ and $\lnot b \Rightarrow \lnot l$. Hence, after $\langle \mathrm{Abd_{\lnot l} }\rangle \,$, the formulas $\lnot e$, $e$, $\lnot b$, $b$ will become explicit and, more importantly, there will be a new plausibility ordering among the worlds: those satisfying $\lnot e \vee \lnot b$ ($w_1$, $w_2$ and $w_3$) become more plausible than those satisfying its negation ($w_4$). Still, within the upper zone, the old ordering will be kept: $w_2$ will be still the most plausible among these three. This gives us the following model:

Observe how $\langle \mathrm{Abd_{\lnot l} }\rangle \,{B_{\mathrm{Ex }}}{\lnot e}$ holds: now Mary believes that an electric problem is responsible for the lack of light.

Mary’s best explanation relies on her previous beliefs. This can lead to incorrect explanations, as in our case: when she observes the alarm clock working, she realizes that the electric line has not failed. This observation of $\lnot \lnot e$ can be represented by $\langle \mathrm{Add }_{\lnot \lnot e}\rangle \,$ ¹¹, thus producing the following model:

The failed hypothesis emphasizes the fact that abduction is a non-monotone form of reasoning: the explanation chosen as the best can be refuted by further information, as Mary knows now. But note how in the model that results from observing $\lnot \lnot e$, the abductive problem $\lnot l$ is still explained, only this time the explanation is $\lnot b$. Before observing $\lnot \lnot e$, Mary explicitly believed $\lnot e$ as the explanation of $\lnot l$, but after the observation she believes explicitly $\lnot b$. She does not need a further abductive step, as the first one reordered her beliefs to make more plausible the worlds where some explanation for $\lnot l$ is true. Then, just as the original explanation was chosen according to her previous beliefs, once these beliefs change, a new explanation appears.

This does not happen if we apply the action $\langle \mathrm{Abd_{\sigma } }\rangle \,$ of the previous section. If Mary chooses $\lnot e\Rightarrow \lnot l$ (according to her original preference for $\lnot e$ over $\lnot b$), the model that results from applying $\langle \mathrm{Abd_{\lnot e\Rightarrow \lnot l} }\rangle \,$ is:

Then, a further observation of $\lnot \lnot e$ produces the following model in which $\lnot l$ is unexplained, that is, Mary does not have any explicit information that would allow her to derive $\lnot l$.

This example shows two characteristics of $\langle \mathrm{Abd_{\chi } }\rangle \,$. First, the ‘best explanation’ is selected according to the previous beliefs of the agent, thus given us the agent’s best explanation. Second, as these beliefs change, the best explanation changes too, without needing further abductive steps. In fact, if $[\psi !]\,$ represents the observation of a propositional formula $\psi$ (modelled as a public announcement), and the rules that the agent knows for $\chi$ contain only propositional formulas, the following holds:

$$\begin{aligned} \Vdash \langle \mathrm{Abd_\chi }\rangle \,[\psi !]\,\varphi \, \, \leftrightarrow \, \, [\psi !]\,\langle \mathrm{Abd_\chi }\rangle \,\varphi \end{aligned}$$

The formula is valid, first because $\langle \mathrm{Abd_\chi }\rangle \,$ does not affect the truth-value of propositional formulas, and thus the worlds $[\psi !]\,$ removes when applied after $\langle \mathrm{Abd_\chi }\rangle \,$ are exactly those it removes when applied before $\langle \mathrm{Abd_\chi }\rangle \,$; second, because the plausibility order among $\psi$-worlds is not affected by $[\psi !]\,$, so $\langle \mathrm{Abd_\chi }\rangle \,$ has the same effect regardless whether it takes place before or after $[\psi !]\,$; third, because the effect of these two actions on $\mathsf {A}$-sets is the same, regardless of the order in which they are applied; fourth, because none action changes the rules the agent explicitly knows.¹²

The possibility of interchanging abductive steps and observations is a very interesting property. As the example of Mary shows, new observations after the abductive step may change the hypothesis that is believed as the best explanation. The just shown property guarantees that after new observations there is no need of further abductive steps: the agent’s information (and so her beliefs about the best explanation) is the same if she performs the abductive operations before or after observing new information.

6 Summary and Future Work

We have presented definitions of abductive problem and abductive solution in terms of an agent’s information and the way it changes, showing how different examples of abductive reasoning correspond to different kinds of agents (e.g., those whose information is not closed under logical consequence, or those whose reasoning abilities are not complete). Then we have shown how a syntactic extension of the possible worlds model allows us to represent certain forms of abductive reasoning.

Our work is just an initial exploration of abductive reasoning for non-omniscient agents, and there are many aspects yet to be studied. The most important one is the semantic representation of abductive reasoning, and though we have shown that certain forms can be represented, a deep study of the diverse types that can be described is still pending. In order to achieve this, we first should provide a proper semantic definition for the actions we have sketched through the work: $\mathrm{Add }_{\varphi /\alpha }$, $\mathrm{Rem }_{\varphi }$, $\alpha$ and $\mathrm{Dis }_{\varphi }$. Natural candidates can be found in the current DEL literature (Plaza 1989; Gerbrandy 1999; Benthem 2007; Baltag and Smets 2008; Velázquez-Quesada 2010). Once a full setting has been formally defined, the next step is a proper comparison between it and other approaches to abductive reasoning, in order to identify strengths and weaknesses and, more importantly, in order to obtain a better picture of the abductive process.