| Dealing with uncertainty in dynamic environments is a basic challenge to autonomous systems. These systems are highly complex, involving large numbers of stochastic variables and many interacting nonlinear subsystems that operate at multiple time granularities. An autonomous system must be able to monitor the state of its components and environment to form informed plans of intelligent action. But monitoring is a challenge for large-scale systems, because the cost of exact inference grows exponentially with the number of state variables. Thus, approximate monitoring algorithms are needed.; Complex systems typically consist of loosely coupled subsystems. One approach to approximate monitoring exploits this idea by factoring the joint distribution of the system state into a product of marginal distributions over the subsystem states. However, sometimes this factoring approach is still computationally infeasible. An alternative approach to approximate monitoring is particle filtering (PF), in which the joint distribution over the system state is approximated by a set of samples or particles. In high dimensional spaces, the variance of PF is high and too many particles are required to provide good performance.; This thesis presents factored sampling, a new family of approximate monitoring algorithms, that combines the best qualities of these two methods. Instead of maintaining particles over the entire state of the system, we introduce factoring to the particle-based representation and maintain particles over clusters of state variables. This approach reduces the variance of PF, hence reducing its error. Maintaining factored particles also allows for tractable look-ahead prediction, so that the most recent evidence can be used to decide which particles to propagate, which dramatically improves accuracy.; This thesis also presents methods for continuous-time monitoring. For systems with intermittent events and observations, discrete-time monitoring is inefficient because inference is performed at fixed time steps, even when the system state remains unchanged. Thus, we present an algorithm for performing particle filtering in continuous time, such that reasoning is done only at the onset of interesting events, and show how learning of model parameters can be incorporated into this framework. A factored version of this algorithm, that uses the representation of factored particles, is also presented. |
