Combining Stochastic and Greedy Search in Hybrid Estimation

Lars J Blackmore, Stanislav Funiak, Brian Williams

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.

Content Area: 5. Automated Reasoning

Subjects: 1.5 Diagnosis; 3.4 Probabilistic Reasoning

Submitted: May 10, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.