# Inferring Agents' Goals from Observing Successful Traces
## 2 Problem Formalization  
We want to infer an agent's possible goals by observing a series of successful attempts by the agent to achieve them. We, therefore, assume a training process in different scenarios during which we observe the agent performing actions until it achieves one of its goals. We will model these observed scenarios as a set of traces describing the succession of states of the environment as well as the actions of the agent. We consider environments without exogenous events and with discrete-time: an action performed by the agent always leads to a state change. The state of the environment is modeled as a series of attributes with discrete values: \(N\) variables \(var_{i}\) for \(i\in\{1,\ldots,N\}\) taking values in domains \(D_{j}=\{val_{1}^{i},\ldots,val_{N_{i}}^{i}\}\). An atomic representation is construct by converting all the couples \(var_{i}=val_{j}^{i}\) into atoms \(var_{i}^{val_{j}^{i}}\), we denote by \(\mathcal{L}\) this set of atoms. We define a _state_\(S\) as a set of atoms \(var_{i}^{val_{j}^{i}}\) from \(\mathcal{L}\) with each \(var_{i}\) only appearing once, and we define a _trace_ as a sequence of couples \((S_{i},a_{i})\)with \(S_{i}\subset\mathcal{L}\) being a state and \(a_{i}\) an action (taken from \(\mathcal{A}\), a finite set of actions). Traces can be of different lengths as they rely on the number of actions performed by the agent to reach its goal. We will not go into the details of the environment's dynamics, but they can be abstracted away using a function \(next\) from \(2^{\mathcal{L}}\times\mathcal{A}\) to \(2^{2^{\mathcal{L}}}\) which will, given a state \(S\) and an action \(a\) provides the set of potentially reachable states from \(S\) by performing \(a\). If the environment is deterministic, \(next(S,a)\) will correspond to a single state. Since they come from observations, the traces are assumed to follow this dynamic, meaning that if the index \(i\) is not the last one of the trace, we have: \(S_{i+1}\in next(S_{i},a_{i})\). We define successful traces using a special action success that has no effects (\(\forall S,next(S,success)=\{S\}\)), performed by the agent whenever it reaches its goal. Thus, a successful trace is a trace \(T=(S_{0},a_{0}),\ldots,(S_{k},a_{k})\) with \(a_{k}=\)success and \(a_{i}\
eq\)success for \(i<k\). A successful trace is therefore a trace ending in the first state where the agent achieves its goal. Given a trace \(T=(S_{0},a_{0}),\ldots,(S_{k},a_{k})\), we denote the last state \(S_{k}\) of this trace by \(endS(T)\) and the set of intermediate states \(\{S_{0},\ldots,S_{k-1}\}\) by \(intS(T)\). Our problem takes as input a set of successful traces: \(\Sigma=\{T_{0},\ldots,T_{l}\}\) and we seek to infer from it a hypothesis about the agent's goals expressed as a propositional formula over \(\mathcal{L}\), this hypothesis must be satisfied by specific states (when interpreting states as a conjunction of atoms) if and only if a goal is achieved in these states. It is assumed here that the goal does not depend on the way it is reached, only the final state matters. The agent only needs to reach a state satisfying its goal. To cover several goals, we want the hypothesis written as a DNF (Disjunctive Normal Form). More exactly, we want a hypothesis of the form \(H=C_{0}\lor C_{1}\lor...\lor C_{m}\) with each \(C_{i}=x_{0}\wedge...\wedge x_{n}\) being a conjunction of atoms from \(\mathcal{L}\). Then, given \(H=C_{0}\lor C_{1}\lor...\lor C_{m}\), a state \(S=\{y_{0},\ldots,y_{N}\}\) satisfies \(H\) if and only if \(\bigwedge_{y_{i}\in S}y_{i}\models H\), i.e., if and only if there exists \(i\in\{0,\ldots,m\}\) such that \(C_{i}\subseteq S\) (an assignment \(\mathcal{A}\) is a model of a formula \(F\) if \(F\) is true under this assignment, \(\mathcal{A}\models F\)). Even without knowledge about the dynamics of the system or the agent's behavior, these observations provide a series of states where it is known whether or not the agent's goals are being reached.