Stochastic Robot Behaviors through Hidden Markov Models with Inputs and Outputs

Abstract Hidden Markov models (HMMs) have found myriad uses. When employed in robotics, however, a conspicuous difference compared with finite-state machine emerges: HMMs lack a direct way of incorporating inputs. Although a sequence of observations can be viewed as input, we argue that it is desirable to extend HMMs with inputs in the vein of finite-state machines. As robot controllers, HMMs exhibit another salient feature: such models primarily focus on capturing uncertainty and stochasticity in the operational environment while maintaining deterministic actions based on the robot’s belief state. We propose extendin HMMs in this other direction as well, embracing uncertainty also in the reactive behavior of the robot, resulting in stochastic behavior, thus making the robot act differently under the same conditions. We argue that this produces rich information, often sufficient for effective navigation without explicit maps. In addition, this approach significantly reduces the computational burden on the agent and simultaneously mitigates undesirable behaviors arising from deterministic policies under uncertainty of environmental perception. An input output extended HMM (IOEHMM) can be regarded as a Moore machine with stochastic inputs and outputs. We build IOEHMM robot behaviors using a genetic algorithm to find the best models and compare this approach with robot behavior implemented with a Markov decision process (MDP), whose parameters are also found by a genetic algorithm. Our method outperforms MDPs in cases where obstacles are large or the robot is used for exploration.