Next: IMPLEMENTING POLICIES AND BINDINGS Up: MODELING THE TOAST WORLD Previous: MULTIPLE GOALS: METABOLISM

## MULTIPLE GOALS: INTERLEAVED EXECUTION

Metabolism involves performing the same transformation uniformly to instances of the same type of object: cooking all the eggs, or cleaning/dirtying all the forks. Often times, however, an agent will work toward different kinds of goals at once. This can often be done by interleaving the actions from solutions to the individual goals. We will say that an interleaving I is a function that returns one or the other of its first two arguments, depending on a third state argument:

When the last two arguments of I are policies, the result is itself a policy, so we will define the notation:

If we wanted to simultaneously make toast and cook an egg, then a good interleaving of a toast-making policy and an egg-cooking policy would be one that chose the egg-making policy whenever the egg had finished its current cooking step (and so was ready to be flipped or removed from the pan) and chose the toast-making policy when the egg was busy cooking. A bad interleaving would be one that always chose the toast-making policy.

An interleaving I is fair for and if starting from any state, will after some finite number of steps have executed both and at least once. Finally, we will say that two bindings are independent if they map disjoint sets of components to their images. Binding independence is a special case of subgoal independence: two policies can't possibly interfere if they alter distinct state components. Fairness and binding independence are sufficient conditions for an interleaving to solve a conjunctive goal:

Proof: Since I is a fair interleaving, each of the two policies will be executed in finite time, regardless of starting state. By induction, for any n, there is a number of steps after which I is guaranteed to have executed at least n steps of each policy.

The policy is the composition of a policy for a state space with a binding. If solves and halts, then it must do so by having solve and halt in some finite number of steps n. During execution, the environment goes through a series of states

which project under to a series of states

we claim that any execution of the interleaving must bring the environment through a sequence of states that project under to

that is, a string of states in which appears at least once, then , appears at least once, and so on. The only state transitions that appear are from some to itself or to . Suppose it were otherwise. Then there must be a point at which this series is broken:

where s is neither nor . We have two cases. Case 1: executed the transition. Then we have that , a contradiction. Case 2: executed the transition. Then has changed one of the state components mapped by and so and are not independent, a contradiction. Thus the interleaving solves . By the same reasoning, it must halt in , since halts in . Also by the same reasoning, it must solve and halt, and hence, must solve the intersection and halt.

A useful corollary to this is that when the same policy is applied under two independent bindings, the bindings can be safely interleaved, that is, interleaving commutes with binding:

Next: IMPLEMENTING POLICIES AND BINDINGS Up: MODELING THE TOAST WORLD Previous: MULTIPLE GOALS: METABOLISM

Ian Horswill
Wed Apr 2 15:17:20 CST 1997