Abstract
We study the problem of how a computer program can learn, by interacting with an environment, to return an algorithm for solving a class of problems. The two example domains studied in this paper are Blocks World stacking problems and Rubik’s Cube. Our approach is to simulate the evolution of an artificial economy of computer programs called “agents”. Simple rules imposed on the economy result in credit assignment, factoring the problem of evolving an overall program for the class of problems into simpler problems of evolving agents that specialize on aspects of the problem and collaborate to solve the overall class. In this paper our agents are Post Production Systems. Our system, called Hayek4, has learned from random examples a program that solves arbitrary block stacking problems. The program essentially consists of about 5 learned rules and some learned control information. Solution of an instance with n blocks in its goal stack requires the automatic chaining of the rules in correct sequence about 2n deep. Hayek4 has also learned to correct Rubik’s cubes scrambled with up to about 7 random rotations. These results can also be seen in the automatic theorem proving context as a way to learn domain knowledge allowing one to automatically generate compact proofs
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
Sutton, R. S. & Barto, A. G. Reinforcement Learning, an introduction. MIT Press, Cambridge, (1998).
Tesauro, G. Temporal difference learning and td-gammon. CACM 38(3), 58 (1995).
Whitehead, S. & Ballard, D. Learning to perceive and act. Machine Learning 7(1), 45 (1991).
Baum, E. & Durdanovic, I. Evolution of cooperative problem-soving in an artificial economy. Neural Computation 12(12) (2000).
Koza, J. Genetic Programming. MIT Press, Cambridge, (1992).
Dzeroski, S., Blockeel, H. & De Raedt, L. Relational reinforcement learning. in Proc. 12th ICML, (Shavlik, J., ed) (Morgan Kaufman, San Mateo, CA, 1998).
Korf, R. E. Planning as search: A quantitative approach. AIJ 33, 65 (1987).
Holland, J. H. Escaping brittleness: the possibilities of general purpose learning algorithms applied to parallel rule-based systems. in Machine Learning, vol.2 p.593, (Michalski, R. S., Carbonell, J. G. & Mitchell, T. M., eds). Morgan Kauffman, Los Altos, CA (1986).
Wilson, S. & Goldberg, D. A critical review of classifier systems. in Proc. 3rd ICGA, p 244 (Morgan Kauffman, San Mateo, CA, 1989).
Baum, E. B. Toward a model of mind as a laissez-faire economy of idiots, extended abstract. in Proc. 13th ICML’ 96, p28, (Saitta, L., ed) (Morgan Kaufman, San Francisco, CA, 1996). and in Machine Learning (1999)v35n2.
Baum, E. B. Manifesto for an evolutionary economics of intelligence. in Neural Networks and Machine Learning, p.285, (Bishop, C. M., ed). Springer-Verlag (1998).
Lettau, M. & Uhlig, H. Rule of thumb and dynamic programming. American Economic Review, (1999). in press.
Forrest, S. Implementing semantic network structures using the classifiersystem. in Proc. First International Conference on Genetic Algorithms, 188–196 (Lawrence Erlbaum Associates, Hillsdale, NJ, 1985).
Minsky, M. Computation: Finite and Infinite Machines. Prentice-Hall Inc, Englewood Cliffs, NJ, (1967).
Post, E. L. Formal reductions of the general combinatorial decision problem. American Journal of Math 52, 264–268 (1943).
Minsky, M. The Society of Mind. Simon and Schuster, New York, (1986).
Wilson, S. Zcs: a zeroth level classifier system. Evolutionary Computation 2(1), 1–18 (1994).
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
Baum, E.B., Durdanovic, I. (2001). An Artificial Economy of Post Production Systems. In: Luca Lanzi, P., Stolzmann, W., Wilson, S.W. (eds) Advances in Learning Classifier Systems. IWLCS 2000. Lecture Notes in Computer Science(), vol 1996. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44640-0_1
Download citation
DOI: https://doi.org/10.1007/3-540-44640-0_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42437-6
Online ISBN: 978-3-540-44640-8
eBook Packages: Springer Book Archive