Combining stochastic and greedy search in hybrid estimation

Abstract

Techniques for robot monitoring and diagnosis have been developed that perform state estimation using probabilistic hybrid discrete/continuous models. Exact inference in hybrid dynamic systems is, in general, intractable. Approximate algorithms are based on either 1) greedy search, as in the case of k-best enumeration or 2) stochastic search, as in the case of Rao-Blackwellised Particle Filtering (RBPF). In this paper we propose a new method for hybrid state estimation. The key insight is that stochastic and greedy search methods, taken together, are often particularly effective in practice. The new method combines the stochastic methods of RBPF with the greedy search of k-best in order to create a method that is effective for a wider range of estimation problems than the individual methods alone. We demonstrate this robustness on a simulated acrobatic robot, and show that this benefit comes at only a small performance penalty.