## Computer Science

# Inferring finite automata with stochastic output functions and an application to map learning

## Document Type

Conference Paper

## Abstract

We assume that it is useful for a robot to construct a spatial representation of its environment for navigation purposes. In addition, we assume that robots, like people, make occasional errors in perceiving the spatial features of their environment. Typical perceptual errors include confusing two distinct locations or failing to identify the same location seen at different times. We are interested in the consequences of perceptual uncertainly in terms of the time and space required to learn a map with a given accuracy. We measure accuracy in terms of the probability that the robot correctly identifies a particular underlying spatial configuration. We derive considerable power by providing the robot with routines that allow it to identify landmarks on the basis of local features. We provide a mathematical model of the problem and algorithms that are guaranteed to learn the underlying spatial configuration for a given class of environments with probability 1 - δ in time polynomial in 1/δ and some measure of the structural complexity of the environment and the robot's ability to discern that structure. Our algorithms apply to a variety of environments that can be modeled as labeled graphs or deterministic finite automata.

## Publication Title

Proceedings Tenth National Conference on Artificial Intelligence

## Publication Date

1992

## First Page

208

## Last Page

214

## ISBN

262510634

## DOI

10.5555/1867135.1867168

## 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" (1992). *Computer Science*. 219.

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

## APA Citation

Dean, T., Angluin, D., Basye, K., Engelson, S. P., Kaelbling, L. P., Kokkevis, E., & Maron, O. (1992, July). Inferring finite automata with stochastic output functions and an application to map learning. In *AAAI* (pp. 208-214).