Robot Introspection through Learned Hidden Markov Models

Maria Fox, Malik Ghallab, Guillaume Infantes, Derek Long

Artificial Intelligence, vol 170, no 2, pp59-113 (to appear Feb 2006)

In this paper we describe a machine learning approach for acquiring a model of a robot behaviour from raw sensor data. We are interested in automating the acquisition of behavioural models to provide a robot with an introspective capability. We assume that the behaviour of a robot in achieving a task can be modelled as a finite stochastic state transition system.

Beginning with data recorded by a robot in the execution of a task, we use unsupervised learning techniques to estimate a hidden Markov model (HMM) that can be used both for predicting and explaining the behaviour of the robot in subsequent executions of the task. We demonstrate that it is feasible to automate the entire process of learning a high quality HMM from the data recorded by the robot during execution of its task.

The learned HMM can be used both for monitoring and controlling the behaviour of the robot. The ultimate purpose of our work is to learn models for the full set of tasks associated with a given problem domain, and to integrate these models with a generative task planner. We want to show that these models can be used successfully in controlling the execution of a plan. However, this paper does not develop the planning and control aspects of our work, focussing instead on the learning methodology and the evaluation of a learned model. The essential property of the models we seek to construct is that the most probable trajectory through a model, given the observations made by the robot, accurately diagnoses, or explains, the behaviour that the robot actually performed when making these observations. In the work reported here we consider a navigation task. We explain the learning process, the experimental setup and the structure of the resulting learned behavioural models. We then evaluate the extent to which explanations proposed by the learned models accord with a human observer's interpretation of the behaviour exhibited by the robot in its execution of the task.

The submitted version of the paper is here.

To compile: g++ -o exmax exmax.cpp

Useage: exmax <dimsFile> <initSM> <evFile> <evOutFile>
where (links to example files):

dimsFile

file containing the state structure;

initSM

file containing the initial sensor model;

evFile

file containing the evidence streams;

evOut

file used for output of generated evidence streams;

• The dimsFile has the following format:

  #states
  #observations
  #start states
  start state identifiers (ints)
  #end states
  end state identifiers (ints)
  singleton start? (0/1)
  singleton end? (0/1)
  

  For example:

  9
  13
  2
  2 3
  1
  5
  0
  1
  

• The initial sensor model, initSM, has the form of a rectangular matrix of double (#states rows by #observations columns) where each entry is the probability of the given observation for the given state.
• Evidence streams, evFile, are constructed as a sequence of (int) observation identifiers, with each run ended by the string "END OF RUN".
• The output file, evOutFile, contains a copy of the original input evidence streams and then some example output evidence streams generated from the learned transition model. The intention is to allow us to decide whether the learned model might generate evidence that looks like the original input evidence. The statistics compare means and standard deviations of, first, the variations in the sequences (how many times the observations change) and, second, the lengths of the sequences (original and generated).

This code accepts multiple evidence sequences and correctly implements the appropriate scaling mechanism. For details of this point, see the above paper.