We use a naval simulation game engine to design and evaluate two versions of a target angle recognition serious game or training simulation. Such a serious game offers a safe, immersive, controlled, and affordable platform for training essential nautical skills. The Target Angle Recognition System or TARS is designed to refresh and teach target angle recognition, a skill that is pre-requisite to learning to drive ships at sea in accordance with the nautical rules of the road. In order to improve user engagement and experience, we then used the principles of adaptive training to implement an adaptive version of TARS, Smart TARS or STARS, and conducted a study to compare the two versions. We show that using either version led to significant learning as evidenced in post-test scores. Furthermore, after exposure to both training systems, surveys show that more than $63 \%$ of participants preferred STARS. This paper describes the architecture and design of the training simulation game, the differences between TARS and STARS, and preliminary results from a user study comparing the two.

Recent advances in AI indicate that the future of cybersecurity workforce development lies in professionals working in Human-AI teams to defend online resources from opposing Human-AI teams of malicious attackers. However, there is little research on how human biases and attitudes affects the performance of human-AI teams in cybersecurity. To help explore this new research area, we describe a simulation game that helps students (future professionals) understand the concept of firewalls while enabling us to probe attitudes towards cybersecurity and AI, as well as trust and cooperation in HumanAI teams. Early study prototyping results indicate that students prefer an AI-teammate over a human in this simulation game setting. In addition, students seem to engage well with the game play, pointing towards this research platform’s suitability for exploring trust and cooperation in human-AI teams for game-based cybersecurity training, and to support our prior results on differing perspectives on cybersecrity risk.

In this paper, we focus on the field of maritime simulation games, also known as serious games or simulators, which serve as a vital tool for maritime education and training. These simulations offer a controlled and risk-free platform to mimic real-world situations, thereby aiding seafarers in learning essential skills such as ship maneuverability, collision prevention, and understanding other naval agents’ intentions. We present an implementation of a Unity-based naval simulator that enables the development of complex, multi-vessel navigation scenarios and provides multiple key capabilities relevant to the naval domain. First, the agent vessels are equipped with mathematical models to assess their capabilities and vulnerabilities. Second, a vulnerability heatmap is developed to illustrate the sensor and defense coverage of an agent or a group of agents. Third, a Closest Point of Approach (CPA) based action heatmap is developed to explore potential threats from the surrounding agents. Furthermore, these heatmaps are fused into a threat heatmap that encodes in real time an agent’s overall coverage and potential threats. In addition, vessel agents are equipped with Hidden Markov Model-based intent recognition models, to analyze the behavior of other agents around them. This paper describes the naval simulator with its capabilities and illustrates its main capabilities in various naval scenarios.

This Innovate Practice Full Paper presents a new game for cybersecurity learning. Cybersecurity education is critical to personal media consumption, privacy protection, and national infrastructure. We live in a world that is increasingly connected; the majority of people, particularly young people, engage with technology and social media for multiple hours per day, using the internet as a source of news, entertainment, and connection to the outside world. However, threats on the internet, including misinformation, disinformation, phishing, and multiple other cybersecurity threats grow each year. Because of this, cybersecurity is an essential skill for K-12 and all undergraduate students to learn in public schools. In this study, we asked K-12 teachers to analyze a specific game, NetDefense, designed to teach students basic cybersecurity concepts related to networking. NetDefense specifically addresses concepts within the network communications component of the core theme of computing systems from the K-12 cybersecurity standards released by cyber.org. Before and after engaging with the game, we asked teachers a series of survey questions to determine their perceptions of the game and its utility in classrooms. Findings indicate that NetDefense improved teachers’ knowledge of network concepts. Participating teachers believed that NetDefense would help students learn these concepts and that NetDefense is an appropriate tool for this type of learning. Finally, teachers believed that student motivation to learn about and use cybersecurity concepts would increase upon playing the game. We plan to improve the game using feedback from our participants, disseminate the open source, publicly available game to all interested educators for classroom and laboratory use, and gather more data on game effectiveness.

Recent large wildfires and subsequent damage have increased the importance of wildfire monitoring and tracking. However, human monitoring on the ground or in the air may be too dangerous and we thus investigate deploying Unmanned Aerial Vehicles (UAVs) to track wildfires. Specifically, we attack the problem of distributed autonomous control of UAVs using a set of potential fields to track wildfire boundaries. A multiobjective evolutionary algorithm searches through the space of potential field parameters to maximize fire coverage while minimizing energy consumption. Fire spread is modelled by the well known FARSITE fire model. Preliminary simulation results show that our potential fields approach to UAV control leads to 100% coverage of the boundary by UAVs and 78.1% energy remaining on three testing scenarios.

We use potential fields tuned by genetic algorithms to dynamically reconFigure unmanned aerial vehicles networks to serve user bandwidth needs. Such flying network base stations have applications in the many domains needing quick temporary networked communications capabilities such as search and rescue in remote areas and security and defense in overwatch and scouting. Starting with an initial deployment that covers an area and discovers how users are distributed across this area of interest, tuned potential fields specify subsequent movement. A genetic algorithm tunes potential field parameters to reposition UAVs to create and maintain a mesh network that maximizes user bandwidth coverage and network lifetime. Results show that our evolutionary adaptive network deployment algorithm outperforms the current state of the art by better repositioning the unmanned aerial vehicles to provide longer coverage lifetimes while serving bandwidth requirements. The parameters found by the genetic algorithm on four training scenarios with different user distributions lead to better performance than achieved by the state of the art. Furthermore, these parameters also lead to superior performance in three never before seen scenarios indicating that our algorithm finds parameter values that generalize to new scenarios with different user distributions.

In this paper, we propose a new hybrid structure learning method that incorporates case-injected genetic algorithms as a score-and-search method for determining Bayesian network structure from data. In our approach, we first find the probabilistic dependencies among variables to constrain the search space and then employ case-injected genetic algorithms in the score-and-search phase to find a quality structure from the reduced search space. The novelty of our work lies with the introduction of combining case-based reasoning with genetic algorithms to evolve a near-optimal Bayesian network in fewer generations compared to a randomly initialized genetic algorithm. Our case-injected genetic algorithms enhance Bayesian network structure learning performance over a sequence of similar problems by extracting and storing knowledge from previously solved problems and utilizing the accumulated knowledge to solve subsequent similar problems. To evaluate the viability of our proposed approach, we conducted a series of experiments by generating a sequence of similar problems based on using data sets obtained randomly from three well-known benchmark Bayesian networks. We also compared the performance of our proposed approach with the state-of-the-art algorithm. Our preliminary results show that case-injected genetic algorithms provide better performance in learning Bayesian network structure compared to GA and the state-of-the-art algorithm. Our proposed approach has applications in real-world domains such as e-commerce system and health care.

We investigate a multi-objective, cooperative, co-evolutionary algorithm to evolve control tactics for groups composed from multiple types of units in real-time strategy games. Such tactical control or micromanagement of units is called micro. Building on prior work, we cooperatively co-evolve micro for a ranged unit using a parameterized control algorithm along with micro for a melee unit using a pure potential fields approach and show that we can simultaneously co-evolve micro for melee and ranged units. These cooperatively co-evolved control algorithms for melee and ranged units evolve to work well together to defeat the default Starcraft II AI, even when outnumbered. We are also able to generate manually co-evolved AI that is significantly better than the default Starcraft II AI and defeat it to generate human competitive micro for controlling multiple types of units. Furthermore, using a multi-objective fitness function leads to a pareto front of near-optimal micro behaviors that range from fleeing while sustaining minimal damage to fighting and maximizing damage to opponents. Such a pareto front naturally provides a user or AI player a variety of micro behaviors suitable for the different types of situations encountered in real-time strategy games. We believe these results indicate the potential of our method for generating effective micro for multiple types of units in real-time strategy games with application in multi-agent control, robotics, and other heterogeneous system control problems.

We compare three promising approaches to micromanaging units in real-time strategy games. These approaches span the range from easily understandable meta-search, which uses genetic algorithms to search through the space of parameters of a human specified control algorithm to pure potential fields, which searches through a space of less human understandable potential field parameter values, to neuro-evolution of augmented topologies which evolves an opaque difficult to understand neural network. All three approaches use a two-objective pareto optimal fitness function that maximizes damage done to opponent units and minimizes damage received by friendly units. We first show that all three approaches can quickly evolve micro superior to the default AI for Starcraft 2, a popular real-time strategy game and research testbed. We then manually co-evolve micro against previously evolved micro to produce micro that plays well against good (gold level) human Starcraft 2 players. Furthermore, we can integrate the micro produced by different approaches to control a single group of units composed from multiple types. These results indicate that we may choose our approach based on our need to understand unit control behavior and thus provides another bridge to transferring research results from autonomous units in simulation games to autonomous agents (robots) in the real world.

Advances in high-throughput technologies have generated enormous amounts of high-throughput genomic data. Cluster analysis is often the first step to gain insights into genomic data. K-means, the most widely used clustering algorithm, is known to produce sub-optimal clusters depending on the choice of initialized centers. In this paper, we propose a genetic algorithm-based unsupervised clustering method that searches for the optimal centers of clusters based on the concept of k-means. The genetic algorithm reduces k-means sensitivity to randomly initialized centers and reduces the probability of converging to local minima. Two clustering validity indexes are introduced to the selection process to automatically determine the appropriate number of clusters. The proposed algorithm is applied to 16 disease datasets and four single-cell datasets to demonstrate its performance. Results show that our approach outperforms the current state of the art algorithms on a majority of the datasets.

Learning the structure of a Bayesian network from data is complex because the number of possible structures increases super-exponentially with the increase in the number of nodes. To address this problem, we propose a hybrid approach comprised of two phases: the constraint-based phase that identifies dependencies among variables to minimize the search space, followed by a score-and-search phase which employs a genetic algorithm to evolve the Bayesian network from the reduced search space. We evaluate the performance of our approach by comparing it with existing algorithms on a limited amount of data sets generated from three benchmark networks. The results illustrate that the proposed algorithm achieves good performance in learning the structure particularly for medium to large networks. Next, we apply our method to a new data set generated from a hand-designed network - the RoRSS (Rules of the Road Ship Simulator). The preliminary results indicate that our method is also satisfactory for small networks with a limited amount of data. The work presented here is a proof-of-concept for our proposed approach aimed at discovering knowledge from data samples of varying sizes and in the presence of small to high number of nodes. Based on the results obtained so far, we are confident that our method is suitable to efficiently learn the structure of the RoRSS network from a large data set.

A genetic algorithm (GA), is used to optimize the many parameters of a convolutional neural network (CNN) that control the structure of the network. CNNs are used in image classification problems where it is necessary to generate feature descriptors to discern between image classes. Because of the deep representation of image data that CNNs are capable of generating, they are increasingly popular in research and industry applications. With the increasing number of use cases for CNNs, more and more time is being spent to come up with optimal CNN structures for different applications. Where one CNN might succeed at classification, another can fail. As a result, it is desirable to more easily find an optimal CNN structure to increase classification accuracy. In the proposed method, a GA is used to evolve the parameters that influence the structure of a CNN. The GA compares CNNs by training them on images of concrete containing cracks. The best CNN after several generations of the GA is then compared to the state-of-the-art CNN for crack detection. This work shows that it is possible to generalize the process of optimizing a CNN for image classification through the use of a GA.

We attack the problem of controlling teams of autonomous units during skirmishes in real-time strategy games. Earlier work had shown promise in evolving control algorithm parameters that lead to high performance team behaviors similar to those favored by good human players in real-time strategy games like Starcraft. This algorithm specifically encoded parameterized kiting and fleeing behaviors and the genetic algorithm evolved these parameter values. In this paper we investigate using influence maps and potential fields alone to compactly represent and control real-time team behavior for entities that can maneuver in three dimensions. A two-objective fitness function that maximizes damage done and minimizes damage taken guides our multi-objective evolutionary algorithm. Preliminary results indicate that evolving friend and enemy unit potential field parameters for distance, weapon characteristics, and entity health suffice to produce complex, high performing, three-dimensional, team tactics.

Operating System (OS) detection significantly impacts network management and security. Current OS classification systems used by administrators use human-expert generated network signatures for classification. In this study, we investigate an automated approach for classifying host OS by analyzing the network packets generated by them without relying on human experts. While earlier approaches look for certain packets such as SYN packets, our approach is able to use any TCP/IP packet to determine the host systems' OS. We use genetic algorithms for feature subset selection in three machine learning algorithms (i.e., OneR, Random Forest and Decision Trees) to classify host OS by analyzing network packets. With the help of feature subset selection and machine learning, we can automatically detect the difference in network behaviors of OSs and also adapt to new OSs. Results show that the genetic algorithm significantly reduces the number of packet features to be analyzed while increasing the classification performance.

In this paper, a modification of steady state genetic algorithm, called dual-population scheme, is proposed to improve its execution speed on electronic hardware. It utilizes two memories to store two interactive populations on them. The system, inherently interchanges chromosomes between these populations. In this manner, it can fully benefit from the pipeline processing on hardware. It is shown that the proposed method performs much faster than the standard steady state and canonical genetic algorithms on pipelined genetic hardware. Moreover, the searching performance, repeatability and convergence properties of the proposed technique were tested. They show dual-population scheme performs similarly to the regular genetic algorithms while achieves better results than the present hardware-oriented genetic algorithm models.

We attack the problem of evolving high performance micro behaviors in 3D RTS-game-like simulations. Prior work had shown the potential for the Meta-Search approach to evolve high performance micro for RTS games like StarCraft. We extend this work by moving to 3D and by moving to more realistic physics for simulating the movement of entities in our RTS-game-like simulation. We compare the evolved micro performance of our entities with different physics models of motion on the same scenarios against identical opponent units in a 3D RTS simulation. Results show that our genetic algorithm approach works to reliably evolve high quality 3D micro behaviors for entities independent of the physics model used. Furthermore, experiments show that the entity's acceleration has more of an effect on performance than rotation speed. Our work provides evidence for the generalizability of an evolutionary approach to generating complex behavior for 3D RTS games, training simulations, and real-world unmanned vehicles.

We propose to use a genetic algorithm to evolve novel reconfigurable hardware to implement elliptic curve cryptographic combinational logic circuits. Elliptic curve cryptography offers high security-level with a short key length making it one of the most popular public-key cryptosystems. Furthermore, there are no known sub-exponential algorithms for solving the elliptic curve discrete logarithm problem. These advantages render elliptic curve cryptography attractive for incorporating in many future cryptographic applications and protocols. However, elliptic curve cryptography has proven to be vulnerable to non-invasive side-channel analysis attacks such as timing, power, visible light, electromagnetic, and acoustic analysis attacks. In this paper, we use a genetic algorithm to address this vulnerability by evolving combinational logic circuits that correctly implement elliptic curve cryptographic hardware that is also resistant to simple timing and power analysis attacks. Using a fitness function composed of multiple objectives - maximizing correctness, minimizing propagation delays and minimizing circuit size, we can generate correct combinational logic circuits resistant to non-invasive, side channel attacks. To the best of our knowledge, this is the first work to evolve a cryptography circuit using a genetic algorithm. We implement evolved circuits in hardware on a Xilinx Kintex-7 FPGA. Results reveal that the evolutionary algorithm can successfully generate correct, and side-channel resistant combinational circuits with negligible propagation delay.

We attack the problem of predicting nitrate concentrations in a stream by using a genetic algorithm to minimize the difference between observed and predicted concentrations on hydrologic nitrate concentration model based on a US Geological Survey collected data set. Nitrate plays a significant role in maintaining ecological balance in aquatic ecosystems and any advances in nitrate prediction accuracy will improve our understanding of the non-linear interplay between the factors that impact aquatic ecosystem health. We compare the genetic algorithm tuned model against the LOADEST estimation tool in current use by hydrologists, and against a random forest, generalized linear regression, decision tree, and gradient booted tree and show that the genetic algorithm does statistically significantly better. These results indicate that genetic algorithms are a viable approach to tuning such non-linear, hydrologic models.

We are interested in using genetic algorithms to generate winning maneuvering behaviors (or micro) in skirmish scenarios for three dimensional Real-Time Strategy games. In prior work, we encoded parameterized 3D micro behaviors like target selection and kiting into an algorithm for controlling friendly units in battle. Genetic algorithms then tuned these parameters to guide unit maneuvering in order to win skirmishes. In this study, we investigate a new representation for micro behaviors that uses only an influence map and a combination of thirteen potential fields. Genetic algorithms then tune influence map and potential field parameters to evolve winning micro behaviors. We compare the performance of both representations on identical scenarios against identical opponents in a full 3D RTS game environment called FastEcslent. The results show that the genetic algorithm using our new representation using less domain knowledge, reliably evolved high quality 3D micro behaviors that slightly, but significantly, outperformed behaviors from our prior work. Our work thus provides evidence for the viability of using potential fields for generating high quality, complex, micro for three dimensional RTS games.

We investigate and develop a coevolutionary approach to finding strong, robust build orders for real-time strategy games. Which units to produce and the order in which to produce them is one important aspect of real-time strategy gameplay. In real-time strategy games, creating plans to address unit production problems are called “build orders.” Our research compares build orders produced from a coevolutionary algorithm, genetic algorithm (GA), and hill climber (HC) to exhaustive search. GAs find the strongest build orders, while coevolution produces more robust build orders than a genetic algorithm or HC. Case injection into the coevolutionary teachset and population can be used to bias coevolution into producing build orders that beat specific opponents or play like specific players, while maintaining robustness. Finally, in this paper, we extend our representation by adding branching and iteration to the build-action sequence and show that this more complex representation enables coevolution to find stronger build orders. We believe this study is a start toward a promising approach for creating strong, robust build orders for RTS games.

We investigate heuristic search algorithms to generate high-quality micromanagement in combat scenarios for real-time strategy (RTS) games. Macro- and micromanagement are two key aspects of RTS games. While good macro helps a player collect more resources and build more units, good micro helps a player win skirmishes and battles against equal numbers and types of opponent units or win even when outnumbered. In this paper, we use influence maps and potential fields as a basis representation to evolve short-term positioning and movement tactics. Unit microbehaviors in combat are compactly encoded into 14 parameters. A genetic algorithm evolves good microbehaviors by manipulating these 14 parameters. We compared the performance of our evolved ECSLBot with two other state-of-the-art bots, UAlbertaBot and Nova, on several skirmish scenarios in a popular RTS game StarCraft. The results show that the ECSLBot tuned by genetic algorithms outperforms UAlbertaBot and Nova in kiting efficiency, target selection, and fleeing. Further experiments show that the parameter values evolved in one scenario work well in other scenarios and that we can switch between preevolved parameter sets to perform well in unseen scenarios containing more than one type of opponent unit. We believe our representation and approach applied to each unit type of interest can result in effective microperformance against melee and ranged opponents and provides a viable approach toward complete RTS bots.

This paper investigates the use of Genetic Algorithms (GAs) to evolve defensive strategies against iterated and memory enabled induction attacks in cognitive radio networks. Security problems in cognitive radio networks have been heavily studied in recent years. However, few studies have considered the effect of memory size on attack and defense strategies. We model cognitive radio network attack and defense as a zero-sum stochastic game. Our research focuses on using GAs to recognize attack patterns from different attackers and evolving defensive strategies against the attack patterns so as to maximize network utility. We assume attackers are not only able to attack high utility channels, but are also capable of attacking based on the history of high utility channel usage by the secondary user. In our simulations, different memory lengths are used by the secondary user against memory enabled attackers. Results show that the best performance strategies evolved by GAs gain more payoff, on average, than the Nash equilibrium. Against our baseline memory enabled attackers, GAs quickly and reliably found the theoretically globally optimal defensive strategy. These results indicate that GAs is a viable approach for generating strong defenses against arbitrary memory based attackers.

This paper compares two approaches for predicting air temperature from historical pressure, humidity, and temperature data gathered from meteorological sensors in Northwestern Nevada. We describe our data and our representation and compare a standard neural network against a deep learning network. Our empirical results indicate that a deep neural network with Stacked Denoising Auto-Encoders (SDAE) outperforms a standard multilayer feed forward network on this noisy time series prediction task. In addition, predicting air temperature from historical air temperature data alone can be improved by employing related weather variables like barometric pressure, humidity and wind speed data in the training process.

This paper investigates three approaches to the problem of identity recognition in real-world unconstrained environments. We describe a new and challenging face recognition dataset captured in a laboratory environment with no strong constraints on lighting, motion, or subject pose, orientation, distance, or facial expression. We then evaluate three approaches to identity recognition on this new dataset. We find that a deep neural network with stacked denoising auto-encoders significantly outperforms a standard feedforward neural network and a baseline eigenfaces approach from the OpenCV library. Despite the 66 million plus parameters in the best trained deep network, it significantly outperforms the other two methods even on the relatively small number (relative to the number of deep network parameters) of 8,895 training samples. We believe our work adds to the growing empirical and theoretical evidence that deep networks provide a promising approach to unconstrained recognition problems.

This paper evaluates the performance of real-time strategy game strategies produced by coevolution. Specifically, we evaluate the robustness of coevolution solutions by having them compete against solutions produced by a genetic algorithm, three hand-tuned baselines, and a human opponent. Our earlier work has shown that genetic algorithms routinely find optimal solutions for defeating the opponents used in training. In this paper, our results show that coevolution finds strategies that defeat genetic algorithm strategies and two of our baselines, without seeing any of the baselines or genetic algorithm solutions during evaluation. A human player who competed against these strategies found that the coevolutionary strategy was the most challenging to defeat, but could be easily defeated using strategies not previously encountered by coevolution. This work informs our research on improving the robustness of real-time strategy players through coevolutionary approaches.

We compare genetic algorithms against hill-climbers for generating competitive unit micro-management for winning real-time strategy game skirmishes. Good group positioning and movement, which are part of unit micro-management can help win skirmishes against equal numbers and types of opponent units or even when outnumbered. In this paper, we use influence maps to generate group positioning and potential fields to guide unit movement. We tested the behaviors obtained from genetic algorithm and two types of hill-climbing search against the default Starcraft AI using the brood war API. Preliminary results show that while our hill-climbers quickly find influence maps and potential fields that generate quality positioning and movement in our simulations, they only find quality solutions fifty to seventy percent of the time. On the other hand, genetic algorithms evolve high quality solutions a hundred percent of the time, but take significantly longer.

This paper compares genetic algorithms against bit-setting hill-climbers for generating competitive plans to beat an opponent in the initial stages of real-time strategy games. Specifically, we search for build-orders that generate the right mix of entities and attack orders and compare the algorithms' performance against optimal plans from exhaustive search. Since multiple possible global optima exist, three hand-coded opponents that follow different strategies serve to provide a baseline for plan comparisons. Our results show that while our hill-climber takes three hours to produce optimal plans against our three hard-coded baselines, it only finds these plans six percent of the time. On the other hand, genetic algorithms routinely find the best plans against our baselines but take significantly longer. This work helps game artificial intelligence designers evaluate the strengths of these types of heuristic search algorithms and serves to inform our research on improving evolutionary approaches to real-time strategy game player design.

This paper investigates the evolution of group tactics and counter tactics for wargaming and real-time strategy games. Inspired by potential field methods in robotics, we compactly represent group behavior as a combination of several potential fields and evolve potential field parameters against hand-coded opponent groups. A novel real-coded evolutionary algorithm encourages tactic diversity by using a new diversity metric to mediate parent selection for recombination. Preliminary results indicate that we can quickly evolve counter tactics that beat hard coded opponent groups.

Teams of robots can utilize formations to accomplish a task, such as maximizing the observability of an environment while maintaining connectivity. In a cluttered space, however, it might be necessary to automatically change formation to avoid obstacles. This work proposes a path planning approach for non-holonomic robots, where a team dynamically switches formations to reach a goal without collisions. The method introduces a multi-level graph, which can be constructed offline. Each level corresponds to a different formation and edges between levels allow for formation transitions. All edges satisfy curvature bounds and clearance requirements from obstacles. During the online phase, the method returns a path for a virtual leader, as well as the points along the path where the team should switch formations. Individual agents can compute their controls using kinematic formation controllers that operate in curvilinear coordinates. The approach guarantees that it is feasible for the agents to follow the trajectory returned. Simulations show that the online cost of the approach is small. The method returns solutions that maximize the maintenance of a desired formation while allowing the team to rearrange its configuration in the presence of obstacles.

Social networking sites employ recommendation systems in contribution to providing better user experiences. The complexity in developing recommendation systems is largely due to the heterogeneous nature of social networks. This paper presents an approach to friend recommendation systems by using complex network theory, cognitive theory and a Pareto>optimal genetic algorithm in a two>step approach to provide quality, friend recommendations while simultaneously determining an individual's perception of friendship. Our research emphasizes that by combining network topology and genetic algorithms, better recommendations can be achieved compared to each individual counterpart. We test our approach on 1,200 Facebook users in which we observe the combined method to outper> form purely social or purely network>based approaches. Our preliminary results represent strong potential for developing link recommendation systems using this combined approach of personal interests and the underlying network.

This paper describes a general geometric method for planar formations of non-holonomic systems. The approach directly provides the feasible controls that each individual robot has to execute in order for the team to maintain the formation based on the controls of a reference agent, either a real leader-robot or a virtual one. In order to directly satisfy the non-holonomic constraints, the geometric reasoning takes place in curvilinear coordinates, defined by the curvature of the reference trajectory, instead of the typical rectilinear coordinates. The generality of the approach lies on the ability to define dynamic formations so as to smoothly switch between static ones, where the robots can change both of their relative coordinates as they move, and the ability to acquire a desired formation given an initial random configuration. Furthermore, it is possible to correct errors in the achieved configuration of the vehicles on the fly. Simulated experiments are presented to verify the correctness of the provided derivations.

In this paper we successfully demonstrate the use of coevolving Influence Maps (IM)s to generate coordinating team tactics for a Real Time Strategy (RTS) game. Each entity in the team is assigned their own IM generated with evolved parameters. The individual IMs allows each entity to act independently of the team and team coordination is then achieved by evolving all team entities' IM parameters together as a single chromosome with a single evaluation. These evolved parameters are then evaluated by measuring performance against another coevolving population of individuals. Using this method we have generated some interesting strategies, and have demonstrated the potential of using IMs for coevolving team tactics. In the future, coevolved tactics could then be used to provide a challenging opponent for human players.

Real Time Strategy (RTS) games provide a representation of spatial tactics with group behaviour. Often tactics will involve using groups of entities to attack from different directions and at different times of the game, using coordinated techniques. Our goal in this research is to learn tactics which are challenging for human players. The method we apply to learn these tactics, is a coevolutionary system designed to generate effective team behavior. To do this, we present a unique Influence Map representation, with a coevolutionary technique that evolves the maps together for a group of entities. This allows the creation of autonomous entities that can move in a coordinated manner. We apply this technique to a naval RTS island scenario, and present the successful creation of strategies demonstrating complex tactics.

We investigate whether XCS, a genetic algorithm based learning classifier system, can harness information from a user's environment to help desktop applications better personalize themselves to individual users. Specifically, we evaluate XCSs ability to predict user-preferred actions for a calendar and a media player. Results from three real-world user studies indicate that XCS significantly outperforms a decision-tree learner to successfully predict user preferences for these two desktop interfaces. Our results also show that removing external user-related contextual information degrades XCSs performance. This performance degradation emphasizes the need for desktop applications to access external contextual information to better learn user preferences. Our results highlight the potential for a learning classifier systems based approach for personalizing desktop applications to improve the quality of human-computer interaction.

We present a computational model of creative design based on collaborative interactive genetic algorithms. We test our model on floorplanning. We guide the evolution of floorplans based on subjective and objective criteria. The subjective criteria consists of designers picking the floorplan they like the best from a population of floorplans, and the objective criteria consists of coded architectural guidelines. We support collaboration by allowing individual designers to view each others' designs during the evolutionary process and the sharing of designs via case injection. This methodology supports team design, and reflects the view of creativity that collaboration accounts for much of our intelligence and creativity. We present a description of the model and a comparative study of floorplans created individually versus collaboratively. Our results show that floorplans created collaboratively were considered to be more ldquorevolutionaryrdquo and ldquooriginalrdquo than those created individually.

We evolve a neural network controller for a boat that learns to maintain a given bearing and range with respect to a moving target in the Lagoon 3D game environment. Simulating realistic physics makes maneuvering boats difficult and thus makes an evolutionary approach an attractive alternative to hand coded methods. We evolve the weights of simple recurrent neural networks trained with a fitness function designed to combine multiple fitness objectives based on speed, heading, and position to create a robust maintain station behavior. Results with an enforced subpopulation neural-evolution genetic algorithm indicate that we can consistently evolve robust maintain controllers for realistically simulated boats in Lagoon.

We attack the problem of game balancing by using a coevolutionary algorithm to explore the space of possible game strategies and counter strategies. We define balanced games as games which have no single dominating strategy. Balanced games are more fun and provide a more interesting strategy space for players to explore. However, proving that a game is balanced mathematically may not be possible and industry commonly uses extensive and expensive human testing to balance games. We show how a coevolutionary algorithm can be used to test game balance and use the publicly available continuous state, capture-the-flag CaST game as our testbed. Our results show that we can use coevolution to highlight game imbalances in CaST and provide intuition towards balancing this game. This aids in eliminating dominating strategies, thus making the game more interesting as players must constantly adapt to opponent strategies.

We present IGAP, a peer to peer interactive genetic algorithm which reflects the real world methodology followed in team design. We apply our methodology to floorplanning. Through collaboration users are able to visualize designs done by peers on the network, while using case injection to allow them to bias their populations and the fitness function to adapt to subjective preferences.

This paper presents a recursive clustering scheme that uses a genetic algorithm-based search in a dichotomous partition space. The proposed algorithm makes no assumption on the number of clusters present in the dataset; instead it recursively uncovers subsets in the data until all isolated and separated regions have been classified as clusters. A test of spatial randomness serves as a termination criteria for the recursive process. Within each recursive step, a genetic algorithm searches the partition space for an optimal dichotomy of the dataset. A simple binary representation is used for the genetic algorithm, along with classical selection, crossover and mutation operators. Results of clustering on test cases, ranging from simple datasets in 2-D to large multidimensional datasets compare favorably with state of the art approaches in genetic algorithm-driven clustering.

We attack the problem of user fatigue in using an interactive genetic algorithm to evolve user interfaces in the XUL interface definition language. The interactive genetic algorithm combines computable user interface design metrics with subjective user input to guide evolution. Individuals in our population represent interface specifications and we compute an individual's fitness from a weighted combination of user input and user interface design guidelines. Results from our preliminary study involving three users indicate that users are able to effectively bias evolution towards user interface designs that reflect both user preferences and computed guideline metrics. Furthermore, we can reduce fatigue, defined by the number of choices needing to be made by the human designer, by doing two things. First, asking the user to pick just two (the best and worst) user interfaces from among a subset of nine shown. Second, asking the user to make the choice once every t generations, instead of every single generation. Our goal is to provide interface designers with an interactive tool that can be used to explore innovation and creativity in the design space of user interfaces.

This paper investigates the role of selection in the acquisition of mutational robustness for two test problems: rONEMAX and SAW. Three different selection methods: tournament, fitness proportionate, and ranking, were implemented in a geerational genetic algorithm and applied to both problems. The effect of altering the selection pressure for the tournament selection method was investigated by varying the tournament size. For the rONEMAX problem the tournament and ranking selection based algorithms found optimal solutions which were significantly more robust to point mutation than those found by either the fitness proportionate selection algorithm or random sampling of the optimal solution space. Altering the selection pressure had no significant effect on the robustness of the solutions located by tournament selection algorithm for the rONEMAX problem. For the SAW problem, however, tournament selection with a tournament size of four found solutions which were significantly more robust than those located by larger tournament sizes. For the majority of the problem variants explored here the tournament and ranking selection methods proved more effective at locating robust optimal solutions than fitness proportionate selection.

This paper describes a new approach to finding a global solution for the fuzzy least trimmed squares clustering. The least trimmed squares (LTS) estimator is known to be a high breakdown estimator, in both regression and clustering. From the point of view of implementation, the feasible solution algorithm is one of the few known techniques that guarantees a global solution for the LTS estimator. The feasible solution algorithm divides a noisy data set into two parts -the non-noisy retained set and the noisy trimmed set, by implementing a pairwise swap of datum between the two sets until a least squares estimator provides the best fit on the retained set. We present a novel genetic algorithm-based implementation of the feasible solution algorithm for fuzzy least trimmed squares clustering, and also substantiate the efficacy of our method by three examples.

We attack the problem of user fatigue by using an interactive genetic algorithm to evolve user interfaces in the XUL interface definition language. The interactive genetic algorithm combines a set of computable user interface design metrics with subjective user input to guide the evolution of interfaces. Our goal is to provide user interface designers with a tool that can be used to explore innovation and creativity in the design space of user interfaces and make it easier for end-users to further customize their user interface without programming knowledge. User interface specifications are encoded as individuals in an interactive genetic algorithm's population and their fitness is computed from a weighted combination of user interface design guidelines and user input. This paper shows that we can reduce human fatigue in interactive genetic algorithms (the number of choices needing to be made by the designer), by 1) only asking the user to pick two user interfaces from among ten shown on the display and 2) by asking the user to make the choice once every t generations.

We outline our context learning framework that harnesses information from a user's environment to learn user preferences for application actions. Within this framework, we employ XCS in a real world application for personalizing user-interface actions to individual users. Sycophant, our context aware calendaring application and research test-bed, uses XCS to adaptively generate user-preferred alarms for ten users in our study. Our results show that XCS' alarm prediction performance equals or surpasses the performance of One-R and a decision tree algorithm for all the users. XCS' average performance is close to $90$ percent on the alarm prediction task for all ten users. These encouraging results further highlight the feasibility of using XCS for predictive data mining tasks and the promise of a classifier systems based approach to personalize user interfaces.

We investigate the trade off between investing effort in improving the features of a research environment that increases productivity and investing such effort in actually conducting the research experiments using a less elaborated, albeit sufficiently operational environment. The study case presented is an interactive genetic algorithm environment we created to evolve user interfaces designs. We present three productivity improvements integrated in our environment and examine whether on the long run the research productivity can be in fact increased by spending development time on enhancing the research tools rather than on performing the research itself. The three improvements are the integration of the entire system interface into a main wxPython window, the addition of a runs manager for setting up multiple experiments, and the creation of a data manager for effective exploration and visualization of data produced in the experiment runs. We also discuss several guidelines for transitioning a research environment such as ours from a researcher's tool to an end-user's tool.

Research in context-aware user interfaces aims to improve human-computer interaction by providing more effective, smarter and user-friendlier solutions for computer applications. Currently, software available for performing such research and developing context-aware interfaces is very limited both in scope and possibilities of extension. Sycophant was designed with two objectives in mind: first, to allow easy insertion of new features and capabilities needed for conducting research and, second, to provide a reusable, readily available programming resource for developing new context-aware interactive software applications. Available as open source software, Sycophant's API and the calendaring application we created using it are presented in this paper in terms of functional capabilities, high level architecture, detailed design, and results of use. Procedural steps for developing new context-aware user interfaces using our API are also described in the paper.

We present results from an empirical user-study with ten users which investigates if information from a user's environment helps a user interface to personalize itself to individual users to better meet usability goals and improve user-experience. In our research we use a microphone and a web-camera to collect this information (user-context) from the vicinity of a subject's desktop computer. Sycophant, our context-aware calendaring application and research test-bed uses machine learning techniques to successfully predict a user-preferred alarm type. Discounting user identity and motion information significantly degrades Sycophant's performance on the alarm prediction task. Our user study emphasizes the need for user-context for personalizable user interfaces which can better meet effectiveness and utility usability goals. Results from our study further demonstrate that contextual information helps adaptive interfaces to improve user-experience.

In this article we present a computational approach to developing effective training systems for virtual simulation environments. In particular, we focus on a Naval simulation system, used for training of conning officers. The currently existing training solutions require multiple expert personnel to control each vessel in a training scenario, or are cumbersome to use by a single instructor. The inability of current technology to provide an automated mechanism for competitive realistic boat behaviors thus compromises the goal of flexible, anytime, anywhere training. In this article we propose an approach that reduces the time and effort required for training of conning officers, by integrating novel approaches to autonomous control within a simulation environment. Our solution is to developintelligent, autonomous controllersthat drive the behavior of each boat. To increase the system's efficiency we provide a mechanism for creating such controllers, from the demonstration of a navigation expert, using a simple programming interface. In addition, our approach deals with two significant and related challenges: therealism of behaviorexhibited by the automated boats and theirreal‐time response to changesin the environment. In this article, we describe the control architecture we developed that enables the real‐time response of boats and the repertoire of realistic behaviors we designed for this application. We also present our approach for facilitating the automatic authoring of training scenarios and we demonstrate the capabilities of our system with experimental results.

Behavior based architectures have many parameters that must be tuned to produce effective and believable agents. The authors used genetic algorithms to tune simple behavior based controllers for predators and prey. First, the predator tries to maximize area coverage in a large asymmetric arena with a large number of identically tuned peers. Second, the GA tunes the predator against a single prey agent. Then, two predators were tuned against a single prey. The prey evolves against a default predator and an evolved predator. The genetic algorithm finds high-performance controller parameters after a short length of time and outpaces the same controllers hand tuned by human programmers after only a small number of evaluations.

Current computer applications and user interfaces lack user context and are not successful in learning user preferences to improve user interaction. We present Sycophant, a context learning calendaring application program which is designed to learn a mapping from user-related contextual features to reminder actions. In this paper, we consider the feasibility of using a genetics-based machine learning technique, XCS, for the purpose of learning this mapping from a set of context features to reminder actions as a predictive data-mining task. We compare XCS's performance with a decision tree algorithm on this learning task and show that XCS outperforms the decision tree learner.

We explore several different techniques in our quest to improve the overall model performance of a genetic algorithm calibrated probabilistic cellular automata. We use the Kappa statistic to measure correlation between ground truth data and data predicted by the model. Within the genetic algorithm, we introduce a new evaluation function sensitive to spatial correctness and we explore the idea of evolving different rule parameters for different subregions of the land. We reduce the time required to run a simulation from 6 hours to 10 minutes by parallelizing the code and employing a 10-node cluster. Our empirical results suggest that using the spatially sensitive evaluation function does indeed improve the performance of the model and our preliminary results also show that evolving different rule parameters for different regions tends to improve overall model performance.

We use a parallel multi-objective genetic algorithm to drive a search and reconstruction spectroscopic analysis of plasma gradients in inertial confinement fusion (ICF) implosion cores. In previous work, we had shown that our serial multi-objective Genetic Algorithm was a good method to solve two-criteria X-ray spectroscopy diagnostics problems. However, this serial version was slow and we therefore could not incorporate better physics and more criteria to solve larger problems and handle larger data sets. In this paper, we develop and use a parallel multi-objective genetic algorithm based on a master-slave model to solve three criteria spectroscopic analysis problems. The algorithm works well in reconciling experimental observations with theoretical physics model parameters. In addition, theoretical analysis and experimental results on the parallelized version show good scalability with up to 150 processors. This reduces the time for running the GA from 9.6 hours to 5.9 minutes.

We use case-injected genetic algorithms (CIGARs) to learn to competently play computer strategy games. CIGARs periodically inject individuals that were successful in past games into the population of the GA working on the current game, biasing search toward known successful strategies. Computer strategy games are fundamentally resource allocation games characterized by complex long-term dynamics and by imperfect knowledge of the game state. CIGAR plays by extracting and solving the game's underlying resource allocation problems. We show how case injection can be used to learn to play better from a human's or system's game-playing experience and our approach to acquiring experience from human players showcases an elegant solution to the knowledge acquisition bottleneck in this domain. Results show that with an appropriate representation, case injection effectively biases the GA toward producing plans that contain important strategic elements from previously successful strategies.

First-person shooter robot controllers (bots) are generally rule-based expert systems written in C/C++. As such, many of the rules are parameterized with values, which are set by the software designer and finalized at compile time. The effectiveness of parameter values is dependent on the knowledge the programmer has about the game. Furthermore, parameters are non-linearly dependent on each other. This paper presents an efficient method for using a genetic algorithm to evolve sets of parameters for bots which lead to their playing as well as bots whose parameters have been tuned by a human with expert knowledge about the game's strategy. This indicates genetic algorithms as being a potentially useful method for tuning bots.

We use case injected genetic algorithms to learn how to competently play computer strategy games. Strategic computer games involve long range planning across complex dynamics and imperfect knowledge presented to players requires them to anticipate opponent moves and adapt their strategies accordingly. This work addresses the problem of acquiring and using knowledge from human players for such games. Specifically, we learn general routing information from a human player and use case-injected genetic algorithms to incorporate this acquired knowledge in subsequent planning. Results from a strike planning game show that with an appropriate representation, case injection effectively biases the genetic algorithm toward producing plans that contain important strategic elements used by human players.

This paper presents a new approach to acquiring and using problem specific knowledge during a genetic algorithm (GA) search. A GA augmented with a case-based memory of past problem solving attempts learns to obtain better performance over time on sets of similar problems. Rather than starting anew on each problem, we periodically inject a GA's population with appropriate intermediate solutions to similar previously solved problems. Perhaps, counterintuitively, simply injecting solutions to previously solved problems does not produce very good results. We provide a framework for evaluating this GA-based machine-learning system and show experimental results on a set of design and optimization problems. These results demonstrate the performance gains from our approach and indicate that our system learns to take less time to provide quality solutions to a new problem as it gains experience from solving other similar problems in design and optimization.

While previous work on case injected genetic algorithms has shown an improvement in solution quality and time to solution when solving a sequence of similar problems, we believe there has been no prior investigation of using case injection to intentionally alter convergence away from the most fit solution and toward another slightly suboptimal solution that is favored for reasons external to the numerical problem formulation (for example, based on similarity to a human expert's solution). We investigate the use of case injection to bias the results of a genetic algorithm (GA) toward a desired but slightly suboptimal solution, in two scenarios. First, when the problem we are attempting to bias by case injection is identical to the problem from which the injected cases were gathered. Second, when the problem we are attempting to bias is different (to varying degree) from the problem from which the injected cases were gathered. In the first scenario, we find that injection of cases does lead to preferential convergence to solutions similar to the runs from which the cases are gathered. We find that the more similar the injected problem is to the problem from which the cases were gathered, the more marked is the solution bias effect, though the technique can still be used to bias GA results even when the problems differ markedly. This technique has application where we wish a GA to derive solutions similar to (for example) known "good" solutions or human derived solutions, when, because of incomplete modeling information, the numerical formulation of the problem itself and its fitness function do not necessarily contain all information about the problem. This has potential applications in human modeling and in developing quality opponents in gaming applications.

This paper describes a technique for combining genetic algorithm with a long term memory of past problems solving attempts to obtain better performance over time on sets of similar design problems. Rather than starting anew on each design, we periodically inject a genetic algorithm's population with appropriate intermediate design solutions to similar, previously solved problems. Experimental results on a configuration design problem; the design of an adder and circuits similar to adders, demonstrate the performance gains from our approach and show that our system learns to take less time to provide quality solutions to a new design problem as it gains experience from solving other similar design problems. We hope that this simple technique will help in implementing evolutionary computing applications in industry.

We use a genetic algorithm to calibrate a spatially and temporally resolved cellular automata to model mining activity on public land in Idaho and Western Montana. The genetic algorithm searches through a space of transition rule parameters of a two dimensional cellular automata model to find rule parameters that fit observed mining activity data. Previous work by one of the authors in calibrating the cellular automaton took weeks - the genetic algorithm takes a day and produces rules leading to about the same (or better) fit to observed data. These preliminary results indicate that genetic algorithms are a viable tool in calibrating cellular automata for this application. Experience gained during the calibration of this cellular automata suggests that mineral resource information is a critical factor in the quality of the results. With automated calibration, further refinements of how the mineral resource information is provided to the cellular automaton will probably improve our model.

We use a Pareto optimal genetic algorithm to determine plasma temperature and density through X-ray spectroscopic diagnostics. Pareto selection provides better solutions compared with linear combinations of the two optimization criteria. Parallelizing the genetic algorithm achieves linear speed-up and allows larger populations resulting in improved reliability in reasonable running time.

We consider the problem of gender classification from frontal facial images using genetic feature subset selection. We argue that feature selection is an important issue in gender classification and demonstrate that Genetic Algorithms (GA) can select good subsets of features (i.e., features that encode mostly gender information), reducing the classification error. First, Principal Component Analysis (PCA) is used to represent each image as a feature vector (i.e., eigen-features) in a low-dimensional space. Genetic Algorithms (GAs) are then employed to select a subset of features from the low-dimensional representation by disregarding certain eigenvectors that do not seem to encode important gender information. Four different classifiers were compared in this study using genetic feature subset selection: a Bayes classifier, a Neural Network (NN) classifier, a Support Vector Machine (SVM) classifier, and a classifier based on Linear Discriminant Analysis (LDA). Our experimental results show a significant error rate reduction in all cases. The best performance was obtained using the SVM classifier. Using only 8.4% of the features in the complete set, the SVM classifier achieved an error rate of 4.7% from an average error rate of 8.9% using manually selected features.

Investigates the application of genetic algorithms (GAs) for recognizing real 2D or 3D objects from 2D intensity images, assuming that the viewpoint is arbitrary. Our approach is model-based (i.e. we assume a pre-defined set of models), while our recognition strategy relies on the theory of algebraic functions of views. According to this theory, the variety of 2D views depicting an object can be expressed as a combination of a small number of 2D views of the object. This implies a simple and powerful strategy for object recognition: novel 2D views of an object (2D or 3D) can be recognized by simply matching them to combinations of known 2D views of the object. In other words, objects in a scene are recognized by "predicting" their appearance through the combination of known views of the objects. This is an important idea, which is also supported by psychophysical findings indicating that the human visual system works in a similar way. The main difficulty in implementing this idea is determining the parameters of the combination of views. This problem can be solved either in the space of feature matches among the views ("image space") or the space of parameters ("transformation space"). In general, both of these spaces are very large, making the search very time-consuming. In this paper, we propose using GAs to search these spaces efficiently. To improve the efficiency of genetic searching in the transformation space, we use singular value decomposition and interval arithmetic to restrict the genetic search to the most feasible regions of the transformation space. The effectiveness of the GA approaches is shown on a set of increasingly complex real scenes where exact and near-exact matches are found reliably and quickly.

X-ray spectroscopy diagnostics have been widely used as a standard technique to determine the temperature and density of astrophysical and laboratory plasmas. Traditional techniques have relied on performing an interactive search with a graphical user interface to select theoretical model parameters that best fit the data. We use a Pareto optimal genetic algorithm to drive a search of model parameters that produce high-quality simultaneous fits of spectra and spatially-resolved emissivity profiles. Preliminary results indicate that our Pareto optimal genetic algorithm is able to quickly find physically meaningful solutions.

We use genetic algorithms to find geologically plausible sub-surface models from seismic travel-time data. Given a sub-surface model, the physics of wave propagation through refractive media can be used to compute travel times for seismic waves. However, in practice, we have to solve the inverse problem: travel-times are available and the problem is to infer sub-surface structure. This inverse problem is fundamental to seismology. To determine the suitability and applicability of genetic algorithms to this seismic inversion problem, we tested a number of different genetic algorithm parameters and operators. Experiments with two synthetic seismic models shows that large population sizes are critical to generating good seismic velocity models and that our two-dimensional crossover operators always performed better than one-dimensional crossover. The genetic algorithms also produces models that fit the data better than models produced by simulated annealing. We believe that our results together with the easy parallelizability of genetic algorithms make a strong case for their use in seismic inversion.

We use genetic algorithm to attack the vehicle routing problem with time windows. Previous work has shown that although merge crossover works better than traditional cross operators for this problem, it does poorly on problems with non-random customer locations. We modify the merge crossover operator to achieve better performance on problems with clustered customer locations. Our algorithm optimally solved three out of six benchmark problems and came within 0.23% of the optimal on the rest.

We reduce stability robustness analysis for linear, time-invariant, discrete-time systems to a search problem and attack the problem using genetic algorithms. We describe the problem framework and the modifications that needed to be made to the canonical genetic algorithm for successful application to robustness analysis. Our results show that genetic algorithms can successfully test a sufficient condition for instability in uncertain linear systems with nonlinear polynomial structures. Three illustrative examples demonstrate the new approach.

This paper describes a system for explaining solutions generated by genetic algorithms (GAs) using tools developed for case-based reasoning (CBR). In addition, this work empirically supports the building block hypothesis (BBH) which states that genetic algorithms work by combining good sub-solutions called building blocks into complete solutions. Since the space of possible building blocks and their combinations is extremely large, solutions found by GAs are often opaque and cannot be easily explained. Ironically, much of the knowledge required to explain such solutions is implicit in the processing done by the GA. Our system extracts and processes historical information from the GA by using knowledge acquisition and analysis tools developed for case-based reasoning. If properly analysed, the resulting knowledge base can be used: to shed light on the nature of the search space; to explain how a solution evolved; to discover its building blocks; and to justify why it works. Such knowledge about the search space can be used to tune the GA in various ways. As well as being a useful explanatory tool for GA researchers, our system serves as an empirical test of the building block hypothesis. The fact that it works so well lends credence to the theory that GAs work by exploiting common genetic building blocks.