## Computer Science

# Inferring Finite Automata with Stochastic Output Functions and an Application to Map Learning

## Document Type

Article

## Abstract

It is often useful for a robot to construct a spatial representation of its environment from experiments and observations, in other words, to 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 inferring from noisy observations the structure of a reduced deterministic 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 to the state is an independent trial and the correct output is observed with probability exceeding 1/2. We assume no errors in the state transition function. Using this framework, we provide an exploration algorithm to learn the correct structure of such an automaton with probability 1 − δ, given as inputs δ, an upper bound m on the number of states, a distinguishing sequence s, and a lower bound α > 1/2 on the probability of observing the correct output at any state. The running time and the number of basic actions executed by the learning algorithm are bounded by a polynomial in δ−l, m, | s|, and (1/2-α)−1. We discuss the assumption that a distinguishing sequence is given, and present a method of using a weaker assumption. We also present and discuss simulation results for the algorithm learning several automata derived from office environments. © 1995, Kluwer Academic Publishers. All rights reserved.

## Publication Title

Machine Learning

## Publication Date

1995

## Volume

18

## Issue

1

## First Page

81

## Last Page

108

## ISSN

0885-6125

## DOI

10.1023/A:1022874607797

## Keywords

Automata inference, distinguishing sequences, map learning, noisy outputs, spatial representation

## Repository Citation

Dean, Thomas; Angluin, Dana; Basye, Kenneth; Engelson, Sean; Kaelbling, Leslie; Kokkevis, Evangelos; and Maron, Oded, "Inferring Finite Automata with Stochastic Output Functions and an Application to Map Learning" (1995). *Computer Science*. 217.

https://commons.clarku.edu/faculty_computer_sciences/217

## APA Citation

Dean, T., Angluin, D., Basye, K., Engelson, S., Kaelbling, L., Kokkevis, E., & Maron, O. (1995). Inferring finite automata with stochastic output functions and an application to map learning. *Machine Learning*, *18*, 81-108.