Sampling in Factored Dynamic Systems
In many real-world situations, we are interested in monitoring the evolution of a complex situation over time. For example, we may be monitoring a patient’s vital signs in an intensive care unit (Dagum and Galper 1995), analyzing a complex freeway traffic scene with the goal of controlling a moving vehicle (Huang, Koller, Malik, Ogasawara, Rao, Russell and Weber 1994), localizing a robot in a complex environment (Fox, Burgard and Thrun 1999) (see also Murphy and Russell (2001: this volume)), or tracking motion of non-rigid objects in a cluttered visual scene (Isard and Blake 1998a). We treat such systems as being in one of a possible set of states, where the state changes over time. We model the states as changing at discrete time intervals, so that x t is the state of the system at time t. In most systems, we model the system states as having some internal structure: the system state is typically represented by some vector of variables X = (X 1,...,X n ), where each X i takes on values in some space Dom[X i ]. The possible states x are assignments of values to the variables X. In a traffic surveillance application, the state might contain variables such as the vehicle position, its velocity, the weather, and more.