Digging through the dirt

Abstract

Autonomous robots are often successfully deployed in controlled environments. Operation in uncontrolled situations remains challenging; it is hypothesized that the detection of abstract discrete states (ADS) can improve operation in these circumstances. ADS are high-level system states that are not directly detectable and influence system dynamics. An example of a typical ADS problem that is used in this thesis is that of a wheeled robot driving through puddles of mud that, when entered, alters the velocity of the robot. When the robot is in such a puddle, it is in an ADS 'mud', and when it is not, it is in an ADS 'free'. ADS can be indirectly inferred through the analysis of lower-level data such as the velocity of the robot.

The goal of this thesis is to design a general abstract discrete state estimator (ADSE) operating with limited prior knowledge. An ADSE is a hierarchical system for detecting changes in ADS. The ADSE should be general; applicable to multiple ADSE problems. The ADSE should further operate under limited prior knowledge: only assuming that the amount of ADS and the ADS that describes the regular operation are known. The basis for the ADSE designed in this thesis is a Gaussian hidden Markov model (GHMM), a hidden Markov model enhanced with Gaussian emissions.

Randomly generated experiments are done on a simple but general ADSE problem. Two unsupervised learning methods derived from Expectation Maximization are evaluated, namely Baum-Welch (BW) and forward extraction (FWE). FWE is introduced in this thesis and is a simpler implementation of Viterbi extraction, leveraging assumptions of ADSE to in theory gain computational efficiency. We found that both BW and FWE exhibit superior performance compared to a likelihood-based baseline estimator when the maximum score of the learning curve is considered. When the final score is considered, in some cases, FWE displays a deteriorating learning curve, resulting in worse final scores compared to the baseline. Furthermore, it was found that the lower the overlap coefficient (therefore the less similar the ADS), the higher the maximum reached score. It was further shown that BW exhibits better convergence than FWE to the true model parameters. Besides this, FWE obtained comparable or in some cases even superior scores compared to BW.

In general, from the results, the diversity of the experiments conducted, and the assumptions made we can conclude that the GHMM can be a general method for an ADSE with limited prior knowledge. To quantify the suitability of the GHMM for ADSE, further research should include the evaluation of different ADSE methods on the same problem. There exists a tradeoff between the lower computational cost FWE and the more stable but more computationally intensive BW learning. Therefore, future research can include a combination of these methods. Other extensions include extending the GHMM to a Gaussian mixture hidden Markov model to allow for the modeling of more complex distributions, or the application to multiple states or a changing environment.