Most formal models of environments use state-space descriptions of the environment, usually finite-state machines. Rosenschein and Kaelbling used finite state machines to represent both agent and environment [31, 32, 33]. Their formalization allowed specialized mechanisms to be directly synthesized from descriptions of desired behavior and a formalization of the behavior of the environment. The formalization was powerful enough to form the basis of a programming language used to program a real robot. Later, Rosenschein developed a method for synthesizing automata whose internal states had provable correlations to the state of the environment given a set of temporal logic assertions about the dynamics of the environment. Donald and Jennings [12] use a geometric, but similar, approach for constructing virtual sensors. Lyons and Arbib [25] model both organisms and robots using process algebras, and Beer [8] employs the formalisms of dynamic systems theory.
Wilson [42] has specifically proposed the classification of simulated environments based on the types of mechanisms which can operate successfully within them. Wilson also used a finite state formalization of the environment. He divided environments into three classes based on properties such as determinacy. Todd and Wilson [41] and Todd et al. [40] taxonomized grid worlds in terms of the behaviors that were successful in them. Littman [24] used FSM models to classify environments for reinforcement learning algorithms. Littman parameterized the complexity of RL agents in terms of the amount of local storage they use and how far into the future the RL algorithm looks. He then empirically classified environments by the the minimal parameters that still allowed an optimal control policy to be learned.
There is also an extensive literature on discrete-event dynamic systems [21], which also model the environment as a finite state machine, but which assume that transition information (rather than state information) is visible to the agents.
An alternative to the state-machine formalism can be found in the work of Dixon [11]. Dixon derives his semantics from first order logic, in which the world comes individuated into objects and relations, rather than on the state-space methods used here. Dixon's ``open'' approach also avoids the need to define the environment as a single mathematical structure. Like this work, Dixon's work attempts to formally model the assumptions a system makes about its environment. Dixon's interest, however, is on what an individual program means rather than on comparing competing programs.