Networks Do Matter: The Socially Motivated Design of a 3D Race Controller Using Cultural Algorithms

Networks Do Matter: The Socially Motivated Design of a 3D Race Controller Using Cultural Algorithms

Robert G. Reynolds (Wayne State University, USA) and Leonard Kinniard-Heether (Wayne State University, USA)
Copyright: © 2012 |Pages: 23
DOI: 10.4018/978-1-4666-1592-2.ch014
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

This article describes a socially motivated evolutionary algorithm, Cultural Algorithms, to design a controller for a 3D racing game for use in a competitive event held at the 2008 IEEE World Congress. The controller was modeled as a state machine and a set of utility functions were associated with actions performed in each state. Cultural Algorithms are used to optimize these functions. Cultural Algorithms consist of a Population Space, a collection of knowledge sources in the Belief Space, and a communication protocol connecting the components together. The knowledge sources in the belief space vie to control individuals in the population through the social fabric influence function. Here the population is a network of chromosomes connected by the LBest topology. This LBest configuration was employed to train the system on an example oval track prior to the contest, but it did not generalize to other tracks. The authors investigated how other topologies performed when learning on each of the contest tracks. The square network (a type of small world network) worked best at distributing the influence of the knowledge sources, and reduced the likelihood of premature convergence for complex tracks.
Chapter Preview
Top

Introduction

This article investigates the use of Computational Intelligence techniques to generate socially motivated behavior in a controller for a 3D racing game. The resultant controller was submitted to the Car Racing Competition at the 2008 World Congress held in Hong Kong China (Loiacono et al., 2008). The goal was to design a controller that can take advantage of the social context in which the race is run. That is, the driver/controller is part of a “pack” of racers during the race as can be seen in the Figure 1.

Figure 1.

Example of the “pack” rounding a turn in close formation during a simulated race

In order to do this certain aspects of the “individual” were minimized in order to allow for more computational support for the social component. For example, while the controller can get in-race information about the location nearby track edges, if they are aware of the position of the adjacent cars then they can “infer” track boundaries as well as other pieces of information without having to process specific sensory information. This will give the controller more time to aggregate its behavioral experience into its knowledge base in order to make higher-level strategic decisions.

Given this “tabula raza” the intent was to gradually add in higher levels of social knowledge and behavior over time. The key was then to identify a social learning technique that can support learning at a variety of different spatial and temporal scales. Recently, a number of socially motivated algorithms have been used to solve optimization problems. Some of the example algorithms are the Particle Swarm Algorithm (Kennedy & Eberhart, 1995), the Ant Colony Algorithm (Dorigo, Maniezzo, & Colorni, 1996), and the Cultural Algorithm (Reynolds, 1978). These three algorithms all use a population-based model as the backbone of the algorithm, and solve problems by sharing information via social interaction among agents in the population. The difference between them is the diversity of scales over which social learning and interaction can take place.

Since Cultural Algorithms encompass the scale of activities for each of the other social learning systems, we selected that as the learning framework here. In this article we will demonstrate how the social learning process will take place by examining how to optimize a low level aspect of the system using Cultural Algorithms. In doing so, aspects of particular swarm optimization technology will be used. In future work, we anticipate using techniques that will support the integration of higher level strategic actions such as co-evolution as suggested by Togelius and Lucas (2006).

Specifically, we start with our minimal state machine framework for a controller. Each of its states employs a set of functions in order to accomplish its goals. There are some utility functions that are shared across all of the states and employ a basic set of variables. Our goal is to use Cultural Algorithms with a network of problem solvers in its population to learn to optimize performance. The network employed initially to train the system for the competition was “Lbest”. However, it was of interest to examine the impact that the use of other network topologies will have on the learning process if any.

In section II the basic design of the controller is presented. Then, in section III the instantiation of the Cultural Algorithm used to “train” the system offline is described. Next, section IV gives the results of the learning activities. The emergence (see Figure 2) of “bridging” performance levels in the system during the initial learning process is highlighted. Next, how the results generalize to the new tracks during the competition is discussed. Finally, the system is used to learn the control parameters for each of the competition tracks using different social topologies. We demonstrate that the square topology, a kind of “small world network” outperforms the Lbest and Gbest topologies in the complex tracks. Section V presents our conclusions.

Figure 2.

Scales of social interaction: The emergent properties depend upon the scale at which the interaction takes place.

Complete Chapter List

Search this Book:
Reset