Dry-land algorithm

A less simple technique for belief revision that turns out to be necessary for some of the examples is one of searching for explanatory belief states when an agent executes an act. For example, an agent may choose not to say that it does not have a driver's license in a job interview, and although choosing not to tell has no direct preconditions, the interviewer should infer that the candidate probably does not have a license. There might be many candidate explanations. As another example, an agent may ask for some fruit. This may be explained by the agent's intention to make a fruit-salad. Equally well, the agent may intend to paint a still-life. There may be many supporting beliefs to these acts, such as all of the beliefs that satisfy the preconditions that support its subacts, which should be reinforced. Beliefs that support the agent's other alternatives may by the same principle be weakened. There might be many explanations, but the dry-land algorithm looks for the most simple one, searching the space of belief models for the most probable one given the previous belief model, in which the agent chooses the act. This is a case of Bayesian updating. Consider that a prior distribution over belief states is known, $P(B)$. The planner can determine whether an act will be chosen in each of these states, giving a value for $P(A\vert B)$. This value will be 1 or 0. To obtain the updated belief state, $P(B\vert A)$ is required. This is obtained using Bayes rule as follows:

$$P(B\vert A) = [ P(A\vert B).P(B)/P(A) ]$$ (3.1)

Since the most probable belief state is required, the P(A) factor cancels out when comparing $P(B\vert A)$ for pairs of belief states.

A straightforward way to calculate the dry-land belief state is to randomly sample the space of belief models, returning the most probable one in which the act is chosen. "Most probable" is defined heuristically as the euclidean distance when the $n$ probability values of the beliefs in the belief model are interpreted as a point in $n$-space. There will be illustrations of this algorithm later in the examples.

Bayesian updating has also been described by Gmytrasiewicz [26], who shows how beliefs are updated as choices are observed in Bayesian games.