# Inferring Agents' Goals from Observing Successful Traces
## 3 Learning from Successful Traces  
As shown in the previous section, we can model the problem of inferring an agent's goal from the observation of a set of successful scenarios as a concept-learning problem by converting the set of successful traces \(\Sigma\) that we observed into the sets of states \(S_{\mathit{positive}}\) and \(S_{\mathit{negative}}\). In fact, the goal of the agent will be the concept that will be learned. To solve this problem, we will produce a hypothesis \(H\) in the form of a DNF and such that \(H\) is consistent with our data (i.e., satisfied by all the states in \(S_{\mathit{positive}}\) and none of the states in \(S_{\mathit{negative}}\)), as described in Section 2. In other words, for any state \(S_{i}\in S_{\mathit{positive}},\exists p_{j}\in H\) a prototype such as \(\mathit{cover}(p_{j},S_{i})\) and for every state \(S_{k}\in S_{\mathit{negative}},\
exists p_{j}\in H\) such as \(\mathit{cover}(p_{j},S_{k})\). Given this, using an existing symbolic concept-learning algorithm such as MGI, Ripper, or ID3 [26; 28; 31] would be possible. With an output close to the form we are looking for, MGI might be a good candidate. However, being a bottom-up algorithm, the least general generalization of some positive examples will provide the different conjunctive statements of the disjunctive hypothesis. Knowing that we will probably have many more negative examples than positive examples in our specific case, we adapted this algorithm using different biases that will favor the generation of general terms. We named this concept-learning process LFST (Learning From Successful Traces) and described it in Algorithm 1. ```
0:\(S_{\mathit{negative}}\), \(S_{\mathit{positive}}\)
0:\(listOfPotentialGoals=\text{list}()\), \(i=\text{integer}\), \(hypothesis=\text{list}()\)
0:\(hypothesis\)
1:for state in \(S_{\mathit{positive}}\)do
2:if\(\exists p\in hypothesis\) such as \(\mathit{cover}(p,state)\)then
3: skip to next state
4:else
5:\(listOfPotentialGoals=[\text{list of all the prototypes covering }state]\)
6:\(p_{\mathit{current}}=\text{the most general prototype }p\in listOfPotentialGoals[i]\) such as \(p\) covers as many states from \(S_{\mathit{positive}}\) as possible)
7:while\(\exists S\in S_{\mathit{negative}}\) such as \(\mathit{cover}(p_{\mathit{current}},S)\)do
8:\(listOfPotentialGoals[i].\text{remove}(p_{\mathit{current}})\)
9:\(p_{\mathit{current}}=\text{the most general prototype }p\in listOf PotentialGoals[i]\) such as \(p\) covers as many states from \(S_{\mathit{positive}}\) as possible)
10:endwhile
11:\(hypothesis.\text{append}(p_{\mathit{current}})\)
12:endif
13:endfor
```  
**Algorithm 1** Learning From Successful Traces. Two sets are given as input of the algorithm, the set of positive examples \(S_{\mathit{positive}}\) and the set of negative examples \(S_{\mathit{negative}}\), they are used for concept learning. We first use one of the positive examples to generate a potential goal that corresponds to a prototype covering this positive example. We start from the most general prototypes by selecting those that cover as many positive examples as possible. We then check if the potential goal is valid or not by using the set of negative examples and checking that none of this set's elements are covered by the prototype representing the potential goal. If it is the case, then the potential goal is valid. We keep repeating this process until, for every positive example, there is at least one potential goal that covers it. In the end, our algorithm will return a DNF corresponding to the one that we described in Section 2. Our algorithm will always finish, and in the worst-case generate a new potential goal for each of the positive examples and go through the whole set of negative examples for each potential goal.