Adaptive Filtering Prediction and Control. Complexity of automation identification from given sets. System identification via state characterization. Technical Report RBCV-TR-88-23, University of Toronto. Robotic exploration as graph construction. Technical Report CU-CS-TR, Cornell University Computer Science Department.ĭudek, G., Jenkins, M., Milios, E., & Wilkes, D. Sensor interpretation and task-directed planning using perceptual equivalence classes. Coping with uncertainty in a control system for navigation and exploration. Technical report, Brown University Department of Computer Science, Providence, RI.ĭean, T., Basye, K., Chekaluk, R., Hyun, S., Lejter, M., & Randazza, M. Learning dynamics: System identification for perceptually challenged agents.
In Proceedings of the Fifth Workshop on Uncertainty in AI. Map learning with indistinguishable locations. Technical Report 92-6, University of Massachusetts at Amherst Department of Computer and Information Science.īasye, K., & Dean, T. Connectionist modeling and control of finite state environments. Information and Computation 75:87–106.Īslam, J.A., & Rivest, R.L. Learning regular sets from queries and counterexamples. Information and Control 39:337–350.Īngluin, D. On the complexity of minimum inference of regular sets. We also present and discuss simulation results for the algorithm learning several automata derived from office environments.Īngluin, D. We discuss the assumption that a distinguishing sequence is given, and present a method of using a weaker assumption. The running time and the number of basic actions executed by the learning algorithm are bounded by a polynomial in δ −1, m, | s|, and (1/2−α) −1. 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. We assume no errors in the state transition function.
#Finite state automata stochastic trial#
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 that the automaton to be learned has a distinguishing sequence. We formulate map learning as the problem of inferring from noisy observations the structure of a reduced deterministic finite automaton. In addition, robots, like people, make occasional errors in perceiving the spatial features of their environments. 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.