TOAST  is a program that simulates a short-order cook in a reasonably detailed simulation of a kitchen (see Figure 3). In TOAST, the world consists of a set of objects such as ovens, pans, cutting boards, globs of pancake batter, individual eggs, and customers of the restaurant. Each object has a type (e.g., EGG) and all objects of a given type have a common set of possible states and a common set of possible operations that can be performed on them. An action involves a set of objects of given types. The action can require that the objects be in specified states and it may change the states of those objects, but no others. For example, the MIX operation would involve objects of type MIXING-BOWL, BATTER, and SPOON. It would require that the spoon be in the CLEAN state and its effects would be to put the batter in the MIXED state and the spoon in the DIRTY state. Objects can perform actions, so the TOAST agent, the oven, and the customers are each modeled as objects that perform the actions of cooking, transferring heat, and making orders, respectively.
Figure 3: Sample run of the breakfast program. The agent was given the goals of making an omelette, two pancakes, a slice of toast, and setting the table, then cleaning up. Our comments appear in square brackets.
TOAST divides most of the objects in its world into two important classes (see Figure 4). Informally, tools are objects that (1) are not end products of cooking and (2) are easily reset to their initial states. For example, knives and spoons are used and dirtied in the process of cooking, but they are not end products of cooking and they are easily reset to their clean state by washing. Materials are objects that are end products of cooking but have state graphs that form linear chains. In other words, for any state of the material, there is exactly one other state that it can be brought to and there is exactly one action that can bring it there. For example, an egg being scrambled always goes through the series of states UNBROKEN, BROKEN, BEATEN, COOKED. In the UNBROKEN state, the only action available on an egg is BREAK, after which the only action available will be BEAT.
Figure 4: Some object types in the current system.
TOAST is given a stock of each type of object. As it runs, the customers give it goals (orders) to prepare specific dishes. The goal specifies a type of material (e.g., ``EGG''). It is satisfied by putting some object of that type into its finished state. Which egg object is cooked does not matter. TOAST manages a dynamic set of these goals and opportunistically overlaps their preparation as processes finish and scarce resources, such as stove burners, become free. TOAST uses a surprisingly simple algorithm:
On each clock cycle of the simulator: Choose a material already being cooked Look up the action needed to advance it to the next state If the action requires additional tools, then choose objects of the proper types If those objects are in their reset states then perform the action else choose one of the unreset tool objects look up and perform its reset action
This algorithm is intentionally sketchy because we have implemented many versions of it which we find intuitively similar, but which have very different control structures and require very different correctness proofs. The task of the next section will be to draw out their similarities and produce a coherent theory of them.
The TOAST algorithm has two interesting features: