Hannaneh Hajishirzi, Eyal Amir
Stochastic filtering is the problem of estimating the state of a dynamic system after time passes and given partial observations. It is fundamental to automatic tracking, planning, and control of real-world stochastic systems such as robots, programs, and autonomous agents. This paper presents a novel sampling-based filtering algorithm. Its expected error is smaller than sequential Monte Carlo sampling techniques given a fixed number of samples, as we prove and show empirically. It does so by sampling deterministic action sequences and then performing exact filtering on those sequences. These results are promising for applications in stochastic planning, natural language processing, and robot control.
Subjects: 3.4 Probabilistic Reasoning; 3.6 Temporal Reasoning
Submitted: Apr 24, 2007