INFERRING FINITE AUTOMATA WITH STOCHASTIC OUTPUT FUNCTIONS AND AN APPLICATION TO MAP LEARNING

It is often useful for a robot to construct a spatial representation o f its environment from experiments and observations, in other words, t o learn a map of its environment by exploration. In addition, robots, like people, make occasional errors in perceiving the spatial features of their environments. We formulate map learning as the problem of in ferring from noisy observations the structure of a reduced determinist ic finite automaton. We assume that the automaton to be learned has a distinguishing sequence. Observation noise is modeled by treating the observed output at each state as a random variable, where each visit t o the state is an independent trial and the correct output is observed with probability exceeding 1/2. We assume no errors in the state tran sition function. Using this framework, we provide an exploration algor ithm to learn the correct structure of such an automaton with probabil ity 1 - delta, given as inputs delta, an upper bound m on the number o f states, a distinguishing sequence s, and a lower bound alpha > 1/2 o n the probability of observing the correct output at any state. The ru nning time and the number of basic actions executed by the learning al gorithm are bounded by a polynomial in delta(-1), m, \s\, and (1/2 - a lpha)(-1). We discuss the assumption that a distinguishing sequence is given, and present a method of using a weaker assumption. We also pre sent and discuss simulation results for the algorithm learning several automata derived from office environments.