The next generation of autonomous NASA explorers will be mobile instruments that must navigate difficult terrains. These vehicles will move beyond the current use of wheeled robots to include highly agile legged vehicles. Controlling these complex systems robustly is inherently difficult, and relies heavily on the ability to estimate the state of the vehicle. For example, estimating the location and operational state of the vehicle is essential in order to plan future actions.

Figure 1. LittleDog legged robot.

Previous Work

Techniques have been developed for robot monitoring and diagnosis that carry out hybrid discrete/continuous state estimation with probabilistic hybrid models. Probabilistic hybrid models such as Probabilistic Hybrid Automata [1] and Dynamic Bayes Nets [2] are convenient modeling tools for robotic applications. However, exact inference with dynamic hybrid systems is NP-hard [1]. Several approaches have been implemented for approximate inference [2] [3][4].

Figure 2. Approximate hybrid estimation using k-best enumeration.		Figure 3. Approximate hybrid estimation using Rao-Blackwellized Particle Filtering.

Robust Hybrid Estimation

The existing approaches for approximate inference are, in many cases, not sufficiently robust. Firstly, by approximating the belief state, the hybrid estimator can lose track of the operational state of the system completely, in a manner analogous to divergence in a Kalman Filter. In our work we have shown that this can occur in relatively simple fault detection scenarios, in which case detection is particularly critical. In situations where the computational resources available to estimation are highly constrained, such as in a NASA exploration vehicle, this problem is particularly acute.

Second, hybrid estimation is critically dependent on accurate models of the underlying system. However accurate modeling cannot be guaranteed, and in classical methods for fault detection for purely continuous dynamic systems it has been shown that relying on fixed system models leads to estimation techniques that are not robust at all to modelling errors.

Our current work addresses these problems. In order to increase robustness to the nature of the estimation problem, we have developed a new algorithm for hybrid estimation. The key insight behind the new algorithm is that, in many AI methods, a combination of stochastic and greedy search methods can be effective in practice. This is analogous to the `exploration vs. exploitation' tradeoff, which has been used with great success in Constraint Satisfaction Problems (CSP), for example. The new algorithm uses Rao-Blackwellized particle filtering (RBPF) to generate, stochastically, additional candidates for k-best enumeration that would not have been tracked by a purely greedy approach. The algorithm maintains a set of particles, which are updated using RBPF, and a set of hypotheses with the highest posterior probability, generated by both RBPF and search-based successor enumeration. This algorithm makes use of the efficient properties of both k-best enumeration and RBPF, while being probabilistically sound.

Figure 4. Combined greedy and stochastic search using new method.

We have demonstrated, using a simulated acrobatic robot, that the mixed algorithm is effective for both a dispersed posterior belief state and a concentrated posterior belief state, showing a dramatic increase in robustness for a relatively small performance penalty.

Ongoing work addresses the other robustness issues mentioned previously. We are currently working on new algorithms that incorporate ideas in the fields of control and learning in order to achieve unprecedented levels of estimation robustness. These capabilities will be demonstrated using the Whole Arm Manipulators to carry out a cooperative construction task.

Figure 5. Whole Arm Manipulator and ATRV rover.

References:

[1] M. Hofbaur and B. C. Williams. Mode estimation of probabilistic hybrid systems. In International Conference on Hybrid Systems Computation and Control 2002.

[2] U. Lerner and R. Parr. Inference in hybrid networks: Theoretical limits and practical algorithms. In Proc. 17th Annual Conference on Uncertainty in Artificial Intelligence 2001.

[3] V. Verma, S. Thrun and R. Simmons. Variable resolution particle filter. In Proc. International Joint Conference on Artificial Intelligence 2003.

[3] A. Doucet, J. de Freitas, K. Murhpy and S. Russell. Rao-Blackwellized particle filtering for dynamic bayesian networks. In Proceedings of the Conference on Uncertainty in Artificial Intelligence 2000.