The Evolution of Strategies for Multiagent Environments

Abstract

SAMUEL is an experimental learning system that uses genetic algorithms and other learning methods to evolve reactive decision rules from simulations of multiagent environments. The basic approach is to explore a range of behavior within a simulation model, using feedback to adapt its decision strategies over time. One of the main themes in this research is that the learning system should be able to take advantage of existing knowledge where available. This has led to the adoption of rule representations that ease the expression of existing knowledge. A second theme is that adaptation can be driven by competition among knowledge structures. Competition is applied at two levels in SAMUEL. Within a strategy composed of decision rules, rules compete with one another to influence the behavior of the system. At a higher level of granularity, entire strategies compete with one another, driven by a genetic algorithm. This article focuses on recent elaborations of the agent model of SAMUEL that are specifically designed to respond to multiple external agents. Experimental results are presented that illustrate the behavior of SAMUEL on two multiagent predator-prey tasks.

Keywords

genetic algorithms sequential decision problems

Get full access to this article

View all access options for this article.

References

Agre, P.E. , & Chapman, D. (1987). Pengi: An implementation of a theory of activity . Proceedings of the Sixth National Conference on Artificial Intelligence, Vol. 1, pp. 268-272. Los Altos, CA: Morgan Kaufmann.

Barto, A.G. , Sutton, R.S. , & Watkins, C.J.C.H. (1990). Learning and sequential decision making. In M. Gabriel & J. W Moore (Eds.), Learning and computational neuroscience. Cambridge, MA: The MIT Press.

Booker, L.B. (1988). Classifier systems that learn internal world models . Machine Learning, 3(2) 161-192.

Booker, L.B. (1991). Representing attribute-based concepts in classifier systems. In G. J. E. Rawlins (Ed.), Foundations of genetic algorithms. San Mateo, CA: Morgan Kaufmann.

Carbonell, J.G. , Knoblock, C.A. , & Minton, S. (1990). Prodigy: An integrated architecture for planning and learning. In K. Van Lehn (Ed.), Architectures for intelligence. Hillsdale, NJ: Lawrence Erlbaum Associates.

Cobb, H.G. , & Grefenstette, J.J. (1991). Learning the persistence of actions in reactive control rules. Proceedings of the Eighth International Machine Learning Workshop (pp. 293-297). San Mateo, CA: Morgan Kaufmann.

De Jong, K.A. (1990). Genetic algorithm-based learning. In Y Kodratoff & R. Michalski (Eds.), Machine learning: An artificial intelligence approach , Vol. 3. San Mateo, CA: Morgan Kaufmann.

Gordon, D.F. (1991). An enhancer for reactive plans. Proceedings of the Eighth International Machine Learning Workshop , pp. 505-508. San Mateo, CA: Morgan Kaufmann.

Gordon, D.F. , & Grefenstette, J.J. (1990). Explanations of empirically derived reactive plans. Proceedings of the Seventh International Conference on Machine Learning, pp. 198-203. San Mateo, CA: Morgan Kaufmann.

10.

Gould, S.J. (1980). The panda's thumb. New York, NY: Norton & Co.

11.

Grefenstette, J.J. (1988). Credit assignment in rule discovery system based on genetic algorithms. Machine Learning, 3(2/3), 225-245.

12.

Grefenstette, J.J. (1991). Lamarckian learning in multi-agent environments . Proceedings of the Fourth International Conference of Genetic Algorithms (pp. 303-310). San Mateo, CA: Morgan Kaufmann.

13.

Grefenstette, J.J. , & Cobb, H.C. (1991). User's guide for SAMUEL (NRL Memorandum Report 6820). Washington, DC: Naval Research Laboratory.

14.

Grefenstette, J.J. , Ramsey, C.L. , & Schultz, A.C. (1990). Learning sequential decision rules using simulation models and competition. Machine Learning 5(4), 355-381.

15.

Holland, J.H. (1975). Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press.

16.

Holland, J.H. (1986). Escaping brittleness: The possibilities of general-purpose learning algorithms applied to parallel rule-based systems. In R. S. Michalski , J. G. Carbonell , & T. M. Mitchell (Eds.), Machine learning: An artificial intelligence approach (Vol. 2). Los Altos, CA: Morgan Kaufmann.

17.

Koza, J.R. (1989). Hierarchical genetic algorithms operating on populations of computer programs. Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, Vol. 1, 768-774. San Mateo, CA: Morgan Kaufmann.

18.

Michalski, R.S. (1983). A theory and methodology for inductive learning . Artificial Intelligence, 20(2), 111-161.

19.

Ramsey, C.L. , Schultz, A.C. , & Grefenstette, J.J. (1990). Simulation-assisted learning by competition: Effects of noise differences between training model and target environment. Proceedings of the Seventh International Conference on Machine Learning (pp. 211-215). San Mateo, CA: Morgan Kaufmann.

20.

Riolo, R.L. (1987). Bucket brigade performance II: Default hierarchies . Proceedings of the Second International Conference on Genetic Algorithms (pp. 196-201). Hillsdale, NJ: Lawrence Erlbaum Associates.

21.

Schoppers, M.J. (1987). Universal plans for reactive robots in unpredictable environments. Proceedings of the Tenth International Joint Conference on Artificial Intelligence (pp. 1039-1046). Los Altos, CA: Morgan Kaufmann.

22.

Schultz, A.C. (1991). Using a genetic algorithm to learn strategies for collision avoidance and local navigation. Proceedings of the Seventh International Symposium on Unmanned, Untethered Submersible Technology (pp. 213-225). Durham, NH: University of New Hampshire.

23.

Schultz, A.C. , & Grefenstette, J.J. (1990). Improving tactical plans with genetic algorithms. Proceeding of IEEE Conference on Tools for AI 90 (pp. 328-334). Washington, DC : IEEE.

24.

Smith, S.E. (1980). A learning system based on genetic adaptive algorithms . Unpublished doctoral dissertation, Department of Computer Science, University of Pittsburgh, Pittsburgh.

25.

Wilson, S.W. (1987a). Classifier systems and the animat problem. Machine Learning, 2(3), 199-228.

26.

Wilson, S.W. (1987b). Hierarchical credit allocation in a classifier system. In L. Davis (Ed.), Genetic algorithms and simulated annealing. London, Engl.: Pitman.