# Anticipatory Troubleshooting
## 2 Traditional Troubleshooting  
In this section, we formalize the troubleshooting problem. A system is composed of a set of components, denoted _COMPS_. At any given point in time, a component \(C\in COMPS\) can be either healthy or faulty, denoted by \(h(C)\) and \(\
eg h(C)\), respectively. The state of the system, denoted \(\xi\), is a conjunction of these health predicates, defining for every component whether it is healthy or not. A system is in a healthy state if all its components are healthy, and in a faulty state if at least one component is faulty. A troubleshooting agent is an agent tasked to return the system to a healthy state. The agent's belief about the state of the system \(\xi\), denoted \(B(\xi)\), is also a conjunction of health literals. We assume that the agent's knowledge is correct but possibly incomplete. That is, if \(h(C)\in B(\xi)\) or \(\
eg h(C)\in B(\xi)\) then \(h(C)\in\xi\) or \(\
eg h(C)\in\xi\), respectively. However, there may exist a component \(C\in COMPS\) such that neither \(h(C)\) nor \(\
eg h(C)\) is in \(B(\xi)\). That is, it always holds that \(B(\xi)\subseteq\xi\). Following [PERSON] et al. [3] we assume the troubleshooting agent has two types of actions: sense and repair. Each action is parametrized by a single component \(C\). A sense action, denoted \(\mathit{Sense}_{C}\), checks whether \(C\) is healthy or not. A repair action, denoted \(\mathit{Repair}_{C}\), results in \(C\) being healthy. (See [PERSON] et al. [6] for a discussion on actions that apply to a batch of components). That is, applying \(\mathit{Sense}_{C}\) adds \(h(C)\) to \(B(\xi)\) if \(h(C)\in\xi\), and adds \(\
eg h(C)\) to \(B(\xi)\) otherwise. Similarly, applying \(\mathit{Repair}_{C}\) adds \(h(C)\) to both \(B(\xi)\) and \(\xi\), and removes \(\
eg h(C)\) from \(B(\xi)\) and \(\xi\) if it is there. A troubleshooting problem arises if the system is identified as faulty. A solution to a troubleshooting problem is a sequence of actions performed by the troubleshooting agent, after which the system is returned to a healthy state. **Definition 1** (Troubleshooting Problem (TP)). : _A TP is defined by the tuple \(P=\langle COMPS,\xi,B,\mathcal{A}\rangle\) where (1) COMPS is the set of components in the system, (2) \(\xi\) is the state of the system, (3) \(B\) is the agent's belief about the system state, and (4) \(\mathcal{A}\) is the set of actions the troubleshooting agent is able to perform. A TP arises if \(\exists C\ \varsigma.t.\ \
eg h(C)\in\xi\). A solution to a TP is a sequence of actions that results in a system state in which all components are healthy._  
A troubleshooting algorithm (TA) is an algorithm for generating a sequence of actions that is a solution to a given TP. TAs are iterative: in every iteration the TA accepts the agent's current belief \(B\) as input and outputs a sense or repair action for the troubleshooting agent to perform. A TA halts when the sequence of actions it has outputted forms a solution to the TP. That is, if an agent performs these actions, then the system will be fixed. Both sense and repair actions incur costs. The cost of an action \(a\) is denoted by \(cost(a)\). The cost of solving a TP using a solution \(\pi\), denoted by \(cost(\pi)\), is the sum of the costs of all actions in \(\pi\): \(cost(\pi)=\sum_{a\in\pi}cost(a)\). TAs aim to minimize this cost. Consider the troubleshooting process example mentioned in Table 1, in which a car does not start: The car is composed of three relevant components that may be faulty: the radiator (\(C_{1}\)), the ignition system (\(C_{2}\)), and the battery (\(C_{3}\)). Assume that the radiator is the correct diagnosis, meaning the radiator is really faulty, and the agent knows that the battery is not faulty. The corresponding system state \(\xi\) and agent's belief \(B\) are: \(\xi=\{\
eg h(C_{1})\wedge h(C_{2})\wedge h(C_{3})\}\) and \(B=\{h(C_{3})\}\). Table 1 lists a solution to this TP, in which the agent first senses the ignition system, then the radiator, and finally repairs the radiator.