Abstract
Finite state machines (FSM) have been successfully used to implement the control of an agent to solve particular sequential tasks. Nevertheless, finite state machines must be hand-coded by the engineer, which might be very difficult for complex tasks. Researchers have used evolutionary techniques to evolve finite state machines and find automatic solutions to sequential tasks. Their approach consists on encoding the state-transition table defining a finite state machine in the genome. However, the search space of such approach tends to be innecesarily huge. In this article, we propose an alternative approach for the automatic design of finite state machines using artificial evolution and learning techniques: the SOS-algorithm. We have obtained very impresive results on experimental work solving partially observable problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P.J. Angeline, G.M. Saunders, and J. Pollack. A evolutionary algorithm that constructs recurrent neural networks. IEEE Transactions on Neural Networks, 5(1):54–65, January 1994.
A.R. Cassandra. Exact and Approximate Algorithms for Partially Observable MarkovDe cision Processes. PhD thesis, Brown University, 1998.
Thomas G. Dietterich. The MAXQ method for hierarchical reinforcement learning. In Proc. 15th International Conf. on Machine Learning, pages 118–126. Morgan Kaufmann, San Francisco, CA, 1998.
L.J. Fogel and A.J. Owens. Artificial Intelligence through Simulated Evolution. John Wiley and sons, New York, 1966.
M. Hauskrecht. Planning and Control in Stochastic Domains with Imperfect Information. PhD thesis, MIT, Cambridge, MA, 1997.
C. Jacob. Illustrating Evolutionary Computing with Mathematica. Morgan Kaufmann, San Francisco, 2001.
J.R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. The MIT Press, Cambridge, Massachusetts, 1992.
J.L. Lin and T.M. Mitchell. Reinforcement learning with hidden states. In JA. Meyer, H.L. Roitblat, and S.W. Wilson, editors, From Animals to Animats: Proceedings of the Second International Conference on Simulation of Adaptive Behavior (SAB92), pages 281–290, 1992.
N. Meuleau, L. Peshkin, K.E. Kim, and L.P. Kaebling. Learning Finite-State Controllers for Partially Observable Environments. In Proceedings of the Conference on Uncertainty and Artificial Intelligence UAI’99, Stockholm, Sweden, 1999.
Z. Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 1992.
A. Pérez-Uribe. Structure-Adaptable Digital Neural Networks, Ph.D Thesis 2052. PhD thesis, Swiss Federal Institute of Technology-Lausanne, 1999.
D. Precup, R.S. Sutton, and S. Singh. Theoretical Results on Reinforcement Learning with Temporally Abstract Behaviors. In Proceedings of the 10th European Conference on Machine Learning ECML’98, pages 382–393, Chemnitz, Germany, 1998.
M.B. Ring. Continual learning in reinforcement environments. PhD thesis, The University of Texas at Austin, August 1994.
E. Sanchez. An Introduction to Digital Systems. In D. Mange and M. Tomassini, editors, Bio-Inspired Computing Machines: Toward Novel Computational Machines, pages 13–48. Presses Polytechniques et Universitaires Romandes, Lausanne, Switzerland, 1998.
Satinder P. Singh, Tommi Jaakkola, and Michael I. Jordan. Reinforcement learning with soft state aggregation. In G. Tesauro, D. Touretzky, and T. Leen, editors, Advances in Neural Information Processing Systems, volume 7, pages 361–368. The MIT Press, 1995.
R. Sun and T. Peterson. Multi-agent reinforcement learning with bidding for segmenting action sequences. In J-A. Meyer, A. Bethoz, D. Floreano, D. Roitblat, and S. Wilson, editors, From Animals to Animats: Proceedings of the Sixth International Conference on Simulation of Adaptive Behavior (SAB2000), pages 325–332, 2000.
R.S. Sutton. Learning to predict by the methods of Temporal Differences. Machine Learning, 3:9–44, 1988.
R.S. Sutton and A.G. Barto. Reinforcement Learning: An Introduction. The MIT Press, 1998.
S.D. Whitehead and D.H. Ballard. Learning to Perceive and Act by Trial. Machine Learning, 7(1):45–83, 1991.
M. Wiering and J. Schmidhuber. HQ-Learning. Adaptive Behavior, 6(2), 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sanchez, E., Pérez-Uribe, A., Mesot, B. (2001). Solving Partially Observable Problems by Evolution and Learning of Finite State Machines. In: Liu, Y., Tanaka, K., Iwata, M., Higuchi, T., Yasunaga, M. (eds) Evolvable Systems: From Biology to Hardware. ICES 2001. Lecture Notes in Computer Science, vol 2210. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45443-8_24
Download citation
DOI: https://doi.org/10.1007/3-540-45443-8_24
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42671-4
Online ISBN: 978-3-540-45443-4
eBook Packages: Springer Book Archive