Bibliography |
Available in BibTeX.
|
Books |
Computational Music Synthesis |
- Author:
- Sean Luke
- Citation:
- Sean Luke. 2019. Computational Music Synthesis. Available for free at http://cs.gmu.edu/~sean/book/synthesis/
| Essentials of Metaheuristics |
- Author:
- Sean Luke
- Citation:
- Sean Luke. 2009. Essentials of Metaheuristics. Available for free at http://cs.gmu.edu/~sean/book/metaheuristics/
| Computational Creativity and Music Technology |
Computational Creativity as Dynamic, Multiobjective, Multiagent Optimization |
PDF
- Citation:
- Sean Luke. 2023. Computational Creativity as Dynamic, Multiobjective, Multiagent Optimization. In International Conference on Computational Creativity (ICCC).
- Abstract: Show / Hide
-
I propose a unified model of computational creativity which treats it as a dynamic, multiobjective, multiagent optimization process. I present an informal model, discuss its attributes and features, and argue for why these elements (optimization, dynamic change, multiple objectives, and multiple agents) are important to a framework in which computationally creative algorithms may be discussed, analyzed, and compared.
| Co-creative Music Synthesizer Patch Exploration |
PDF
- Citation:
- Sean Luke and Victoria Hoyle. 2023. Co-creative Music Synthesizer Patch Exploration. In International Conference on Computational Creativity (ICCC).
- Abstract: Show / Hide
-
We present an interactive evolutionary approach to exploring the space of synthesizer patches which combines an evolutionary optimizer with a variational autoencoder neural network. The objective is to work with musicians to explore the complex space of patches rather than program patches themselves, an often tedious and difficult task. The technique uses an algorithm to wander through the parameter space, while engaging the musician in assessing the quality of discoveries and providing real-time feedback to the algorithm. We describe the method and argue for it as a co-creative system.
| So You Want to Write a Patch Editor |
PDF
- Citation:
- Sean Luke. 2023. So You Want to Write a Patch Editor. Technical Report GMU-CS-TR-2023-1. Department of Computer Science, George Mason University..
- Abstract: Show / Hide
-
A patch editor is a software tool which assists in the programming of electronic music synthesizers. Synthesizers have a long history remote programmability via a communication protocol called MIDI, but there are many complexities involved in building a general-purpose patch editor tool for a large number of machines from a wide variety of manufacturers. This document introduces the reader to how synthesizers are remotely programmed, provides a tutorial with three example synthesizers, and discusses a variety of issues and challenges involved in building patch editors.
|
Stochastic Synthesizer Patch Exploration in Edisyn |
PDF
- Citation:
- Sean Luke. 2019. Stochastic Synthesizer Patch Exploration in Edisyn. In EvoMUSART (2019).
- Abstract Show / Hide
-
Edisyn is a music synthesizer program (or "patch") editor library which enables musicians to easily edit and manipulate a variety of difficult-to-program synthesizers. Edisyn sports a first-in-class set of tools designed to help explore the parameterized space of synthesizer patches without needing to directly edit the parameters. This paper discusses the most sophisticated of these tools, Edisyn's Hill-Climber and Constrictor methods, which are based on interactive evolutionary computation techniques. The paper discusses the special difficulties encountered in programming synthesizers, the motivation behind these techniques, and their design. It then evaluates them in an experiment with novice synthesizer users, and concludes with additional observations regarding utility and efficacy.
| Multiagent Behavior and Simulation |
Hybrid Agent-based and Discrete Event Simulation in MASON |
PDF
- Citation:
- Giuseppe D'Ambrosio and Sean Luke. 2023. Hybrid Agent-based and Discrete Event Simulation in MASON. In Society for Simulation and Modeling Annual Modeling and Simulation Conference (ANNSIM) .
- Note:
- This is an updated version of the paper, with some bugfixes corrected from the original ANNSIM publication.
- Abstract: Show / Hide
-
Agent-Based Modeling and Discrete Event Simulation are two of the most common simulation approaches, and are supported by many simulation tools. Recently, modelers have begun integrating these methods to simulate real-world situations which have some elements better represented by DES and others better represented by ABM. Hybrid ABM and DES simulation is a growing trend but there is a lack of simulation software supporting it, and effectively no open-source software at all. This paper introduces a new open-source DES extension to MASON, a widely used ABM tool, to implement both DES and hybrid ABM-DES models. The goal of the system is to help researchers realize hybrid simulations while exploiting the same characteristics that led to MASON's success, notably its efficiency, extensibility, and ease of integration with other tools. The MASON DES extension is still in its infancy but is already being employed in a large simulation project studying malicious attacks affecting supply chains.
| Simulation and Optimization Techniques for the Mitigation of Disruptions to Supply Chains |
PDF
- Citation:
- Rajhersh Patel and Abhisekh Rana and Sean Luke and Carlotta Domeniconi and Andrew Crooks and Hamdi Kavak and Jim Jones. 2023. Simulation and Optimization Techniques for the Mitigation of Disruptions to Supply Chains. In Society for Simulation and Modeling Annual Modeling and Simulation Conference (ANNSIM).
- Abstract: Show / Hide
-
The COVID-19 pandemic has clearly highlighted the importance of supply chains to the function of the world economy. Moreover, the global nature of most modern supply chains along with their complexity has left them vulnerable to a wide-ranging set of disruptive scenarios. This increase in complexity has also led to a corresponding increase in disruptions to supply chains from criminal networks. In this paper, we demonstrate how a generic pharmaceutical supply chain network can be successfully modeled using discrete event simulation. We outline how disruptions by criminal networks and mitigation strategies to counter them can be effectively incorporated into the same model. Finally, we show how optimization techniques, such as evolutionary computation, can be used to not only identify worst-case disruptions and find mitigations for them, but also be used to identify mitigation strategies that are effective against a diverse set of damaging disruption scenarios.
| Mitigation of Optimized Pharmaceutical Supply Chain Disruptions by Criminal Agents |
PDF
- Citation:
- Abhisekh Rana and Hamdi Kavak and Andrew Crooks and Sean Luke and Carlotta Domeniconi and Jim Jones. 2022. Mitigation of Optimized Pharmaceutical Supply Chain Disruptions by Criminal Agents. In International Conference on Social Computing, Behavioral-Cultural Modeling and Prediction, and Behavior Representation in Modeling and Simulation (SBP-BRiMS).
- Abstract: Show / Hide
-
Disruption to supply chains can significantly influence the operation of the world economy and this has been shown to permeate and affect a large majority of countries and their citizens. We present initial results from a model that explores the disruptions to supply chains by a criminal agent and possible mitigation strategies. We construct a model of a typical pharmaceutical manufacturing supply chain, which is implemented via discrete event simulation. The criminal agent optimizes its resource allocation to maximize disruption to the supply chain. Our findings show criminal agents can cause cascading damage and exploit vulnerabilities, which inherently exist within the supply chain itself. We also demonstrate how basic mitigation strategies can efficaciously alleviate this potential damage.
| Assisted Parameter and Behavior Calibration in Agent-based Models with Distributed Optimization |
PDF
- Note:
-
This is an extension of the following two-page poster.
- Citation:
- Matteo D'Auria, Eric O. Scott, Rajdeep Singh Lather, Javier Hilty, and Sean Luke. 2020. Assisted Parameter and Behavior Calibration in Agent-based Models with Distributed Optimization. In International Conference on Practical Applications of Agents and Multi-Agent Systems (PAAMS).
- Abstract: Show / Hide
-
Agent-based modeling (ABM) has many applications in the social sciences, biology, computer science, and robotics. One of the most important and challenging phases in agent-based model development is the calibration of model parameters and agent behaviors. Unfortunately, for many models this step is done by hand in an ad-hoc manner or is ignored entirely, due to the complexity inherent in ABM dynamics. In this paper we present a general-purpose, automated optimization system to assist the model developer in the calibration of ABM parameters and agent behaviors. This system combines two popular tools: the MASON agent-based modeling toolkit and the ECJ evolutionary optimization library. Our system distributes the model calibration task over very many processors and provides a wide range of stochastic optimization algorithms well suited to the calibration needs of agent-based models.
| Distributed, Automated Calibration of Agent-based Model Parameters and Agent Behaviors |
PDF
- Note:
-
This is a two-page poster which was expanded on considerably in the following paper.
- Citation:
- Matteo D'Auria, Eric O. Scott, Rajdeep Singh Lather, Javier Hilty, and Sean Luke. 2020. Distributed, Automated Calibration of Agent-based Model Parameters and Agent Behaviors. In Autonomous Agents and Multiagent Systems (AAMAS).
- Abstract: Show / Hide
-
Agent-based models can present special challenges to model calibration due in part to their high parameter count, tunable agent behaviors, complex emergent macrophenomena, and potentially long runtimes. However, due to this difficulty, these models are most often calibrated by hand, or with hand-coded optimization tools customized per-problem if at all. As simulations increase in complexity, we will require general-purpose, distributed model calibration tools tailored for the needs of agent-based models. In this paper, we present the results of a system we have developed which combines two popular tools, the MASON agent-based modeling toolkit, and the ECJ evolutionary optimization library. This system distributes the model calibration task over many processors, provides many stochastic optimization algorithms well suited to the calibration needs of agent-based models, and offers the ability to optimize not just model parameters but agent behaviors.
| Scalability in the MASON Multi-agent Simulation System |
PDF
- Citation:
- Haoliang Wang, Ermo Wei, Robert Simon, Sean Luke, Andrew Crooks, David Freelan, and Carmine Spagnuolo.
- Abstract: Show / Hide
-
This paper describes Distributed MASON, a distributed version of the MASON agent-based simulation tool. Distributed MASON is architected to take advantage of well known principles from Parallel and Discrete Event Simulation, such as the use of Logical Processes (LP) as a method for obtaining scalable and high performing simulation systems. We first explain data management and sharing between LPs and describe our approach to load balancing. We then present both a local greedy approach and a global hierarchical approach. Finally, we present the results of our implementation of Distributed MASON on an instance in the Amazon Cloud, using several standard multi-agent models. The results indicate that our design is highly scalable and achieves our expected levels of speed-up.
| The MASON Simulation Toolkit: Past, Present, and Future |
PDF
- Citation:
- Sean Luke, Robert Simon, Andrew Crooks, Haoliang Wang, Ermo Wei, David Freelan, Carmine Spagnuolo, Vittorio Scarano, Gennaro Cordasco, and Claudio Cioffi-Revilla.
- Abstract: Show / Hide
-
MASON is a widely-used open-source agent-based simulation toolkit that has been in constant development since 2002. MASON's architecture was cutting-edge for its time, but advances in computer technology now offer new opportunities for the ABM community to scale models and apply new modeling techniques. We are extending MASON to provide these opportunities in response to community feedback. In this paper we discuss MASON, its history and design, and how we plan to improve and extend it over the next several years. Based on user feedback will add distributed simulation, distributed GIS, optimization and sensitivity analysis tools, external language and development environment support, statistics facilities, collaborative archives, and educational tools.
| Dynamic Traveling Repairmen Bounty Hunters |
(Poster) PDF
(Extended Technical Report) PDF
- Citation:
- Drew Wicke, Ermo Wei, and Sean Luke. 2018. Dynamic Traveling Repairmen Bounty Hunters. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS) .
- Abstract: Show / Hide
-
Vehicle routing problems such as the multiagent dynamic traveling repariman problem (DTRP) are of interest to many fields and of increasing practical importance in light of advances in autonomous vehicles. DTRP is NP-hard, making approximation methods attractive. However, current approaches do not adequately consider issues special to DTRP, such as discontiguous-space scenarios or alternatives to equitably partitioning the task space. We tackle this problem in a novel way, using a multiagent task allocation technique called bounty hunting. In bounty hunting, agents compete to perform tasks non-exclusively in return for reward, and rapidly learn which agents are more adept at various tasks, implicitly splitting up the task space. We demonstrate that bounty hunting can perform efficiently in discontiguous environments, and Pareto-dominates the state-of-the-art heuristic technique, and is particularly good in large-scale scenarios.
| Bounty Hunting and Human-Agent Group Task Allocation |
PDF
- Citation:
- Drew Wicke and Sean Luke. 2017. Bounty Hunting and Human-Agent Group Task Allocation. In AAAI Fall Symposium on Human-Agent Groups.
- Abstract: Show / Hide
-
Much research has been done to apply auctions, markets, and negotiation mechanisms to solve the multiagent task allocation problem. However, there has been very little work on human-agent group task allocation. We believe that the notion of bounty hunting has good properties for human-agent group interaction in dynamic task allocation problems. We use previous experimental results comparing bounty hunting with auction-like methods to argue why it would be particularly adept at handling scenarios with unreliable collaborators and unexpectedly hard tasks: scenarios we believe highlight difficulties involved in working with humans collaborators.
| Throwing in the Towel: Faithless Bounty Hunters as a Task Allocation Mechanism |
PDF
- Citation:
- Drew Wicke, Ermo Wei, and Sean Luke. 2016. Throwing in the Towel: Faithless Bounty Hunters as a Task Allocation Mechanism. In IJCAI workshop on Interactions with Mixed Agent Types.
- Abstract: Show / Hide
-
Bounty hunting has been shown to solve the multiagent task allocation problem robustly in noisy and dynamic scenarios with multiple other agents of unknown quality. This bounty hunting model does not require task exclusivity, but does require task commitment. We examine eliminating this second requirement, thus allowing bounty hunters to commit to tasks but abandon them later (to jump ship) for more promising tasks, without telling other agents of their intent. Bounty hunting agents must use an adaptive valuation mechanism in order to avoid too much redundancy in working on tasks. We examine how one might revise this mechanism in the face of task abandonment. We compare jumping ship favorably against other bounty hunting methods and against methods which are more "auction-like" in that they permit exclusivity, and we do so under both static environments and ones in which agents, and task scenarios, change dynamically.
| Ant Geometers |
PDF
- Citation:
- Sean Luke, Katherine Russell, and Bryan Hoyle. 2016. Ant Geometers. In 15th International Conference on the Synthesis and Simulation of Living Systems (ALIFE 2016).
- Abstract: Show / Hide
-
Just how much can a pheromone-enabled swarm do? Motivated by robotic construction, we set out to show that a swarm of computationally simple ants, communicating only via pheromones, can in fact perform classic compass-straightedge geometry, and thus can make many shapes and perform many nontrivial geometric tasks. The ants do not need specially-designed stigmergic building materials, a prepared environment, local or global direct communication facilities (such as radio or line-of-sight signaling), or any localization beyond initial starting points for drawing. We describe the proof of concept in replicable detail. We then note that its accuracy and efficiency can be greatly improved through augmentation with a simple embeddable broadcast mechanism.
| Bounty Hunters and Multiagent Task Allocation |
PDF
- Citation:
- Drew Wicke, David Freelan, and Sean Luke. 2015. Bounty Hunters and Multiagent Task Allocation. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015).
- Abstract: Show / Hide
-
We propose a system for multiagent task allocation inspired by the model used by bounty hunters and bail bondsmen. A bondsman posts tasks for agents to complete, along with bounties to be collected by an agent on completion. Multiple agents, taking the role of the bounty hunters, compete to finish tasks and collect their bounties. While a task remains uncompleted, its bounty gradually rises, making it more and more desirable to pursue. Unlike auctions, this model does not assume rationality in agents’ bids (as there are none), and since tasks are not exclusive to given agents, the system is robust to highly noisy environments. We examine how agents may locally develop rational task valuations in such an environment, gradually adapting to dividing tasks according to the agents best suited to them. We compare different methods for building these valuations against approaches which are more “auction-like” in that they permit exclusivity, and we do so under both static environments and ones in which agents, and task details, change dynamically.
| Collaborative Foraging using Beacons |
PDF
- Note:
- This is an updated version of the paper, with some typos and bugfixes corrected from the original AAMAS publication.
- Citation:
- Brian Hrolenok, Sean Luke, Keith Sullivan, and Christopher Vo. 2010. Collaborative Foraging using Beacons. In Proceedings of the Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010). van der Hoek et al, eds. 1197–1204.
- Abstract: Show / Hide
-
A classic example of multiagent coordination in a shared environment involves the use of pheromone deposits as a communication mechanism. Due to physical limitations in deploying actual pheromones, we propose a sparse representation of the pheromones using movable beacons. There is no communication between the beacons to propagate pheromones; instead, robots make movement and update decisions based entirely on local pheromone values. Robots deploy the beacons throughout the environment, and subsequently move them and update them using a variation of value iteration. Simulation results show that our approach is effective at finding good trails, locally improving them, and adapting to dynamic changes in the environments.
| Can You Do Me A Favor? |
PDF
- Citation:
- Keith Sullivan, Sean Luke, and Brian Hrolenok. 2010. Can You Do Me A Favor? In AAMAS 2010 Workshop on Trust in Agent Societies.
- Abstract: Show / Hide
-
Multiagent systems often require coordination among the agents to maximize system utility. Using the notion of favors, we propose a technique, flexible reciprocal altruism, which determines when one agent should grant a favor to another agent based on past interactions. The desired rate of altruism is controllable, and as a result the loss associated with granting unmatched favors is bounded and amortized over all past interactions. In flexible reciprocal altruism the desired acceptable loss is independent of the cost and value of the favors. Experiments show that our technique performs well with different cost/value tradeoffs, numbers of agents, and load.
| History-based Traffic Control |
PDF
- Citation:
- Gabriel Balan and Sean Luke. 2006. History-based Traffic Control. In Proceedings of the Fifth International Conference on Autonomous Agents and Multi-Agent Systems.
- Abstract: Show / Hide
- What if traffic lights gave you a break after you've spent a long time waiting in traffic elsewhere? In this paper we examine a variety of multi-agent traffic light controllers which consider vehicles' past stopped-at-red histories. For example, a controller might distribute credits to cars as they wait and award the green light to lanes with the most credits, allowing cars to keep the credits they accumulate during travel. Such history-based controllers are intended to provide a kind of global fairness, reducing the variance in mean time spent waiting at lights during trips. We compare these controllers against other multi-agent controllers which only consider present information, and discover, among other things, that while the history-based controllers are among the most robust, they often unexpectedly provide more efficiency than fairness.
| Tunably Decentralized Algorithms for Cooperative Target Observation |
PDF
- Citation:
- Sean Luke, Keith Sullivan, Liviu Panait, and Gabriel Balan. 2005. Tunably Decentralized Algorithms for Cooperative Target Observation. In Proceedings of the 2005 Conference on Autonomous Agents and Multi-Agent Systems (AAMAS). Pages 911-917.
- Abstract: Show / Hide
- Multi-agent problem domains may require distributed algorithms for a variety of reasons: local sensors, limitations of communication, and availability of distributed computational resources. In the absence o f these constraints, centralized algorithms are often more efficient, simply because they are able to take advantage of more information. We introduce a variant of the cooperative target observation domain w which is free of such constraints. We propose two algorithms, inspired by K-means clustering and hill-climbing respectively, which are scalable in degree of decentralization. Neither algorithm consistently o outperforms the other across over all problem domain settings. Surprisingly, we find that hill-climbing is sensitive to degree of decentralization, while K-means is not. We also experiment with a combination n of the two algorithms which draws strength from each.
| Agent-based Dynamics of Social Complexity: Modeling Adaptive Behavior and Long-term Change in Inner Asia |
PDF
- Citation:
- Claudio Cioffi-Revilla, Sean Luke, Dawn C. Parker, J. D. Rogers, W. W. Fitzhugh, W. Honeychurch, B. Frohlich, P. DePriest, and Naran Bazarsad. 2006. Agent-based Dynamics of Social Complexity: Modeling Adaptive Behavior and Long-term Change in Inner Asia. In Proceedings of the First World Congress on Social Simulation.
- Abstract: Show / Hide
- We present a new international project to develop temporally and spatially calibrated agent-based models of the rise and fall of polities in Inner Asia (Central Eurasia) in the past 5,000 years. Gaps in theory, data, and computational models for explaining long-term sociopolitical change--both growth and decay--motivate this project. We expect three contributions: (1) new theoretically grounded simulation models validated and calibrated by the best available data; (2) a new long-term cross-cultural database with several data sets; and (3) new conceptual, theoretical, and methodological contributions for understanding social complexity and long-term change and adaptation in real and artificial societies. Our theoretical framework is based on explaining sociopolitical evolution by the process of "canonical variation".
| MASON: a Multi-agent Simulation Environment |
PDF
- Citation:
- Sean Luke, Claudio Cioffi-Revilla, Liviu Panait, Keith Sullivan, and Gabriel Balan. 2005. MASON: a Multi-agent Simulation Environment. Simulation: Transactions of the society for Modeling and Simulation International. 82(7):517-527.
- Abstract: Show / Hide
- We introduce MASON, a fast, easily extensible, discrete-event multi-agent simulation toolkit in Java. MASON was designed to serve as the basis for a wide range of multi-agent simulation tasks ranging from swarm robotics to machine learning to social complexity environments. MASON carefully delineates between model and visualization, allowing models to be dynamically detached from or attached to visualizers, and to change platforms mid-run. We describe the MASON system, its motivation, and its basic architectural design. We then compare MASON to related multi-agent libraries in the public domain, and discuss six applications of the system we have built over the past year to suggest its breadth of utility.
| Mnemonic Structure and Sociality: a Computational Agent-based Simulation Model |
PDF
- Citation:
- Claudio Cioffi-Revilla, Sean Paus, Sean Luke, James Olds, and Jason Thomas. 2004. Mnemonic Structure and Sociality: a Computational Agent-based Simulation Model. In Proceedings of the Conference on Collective Intentionality IV.
- Abstract: Show / Hide
- How does group memory affect sociality? Most computational multi-agent social simulation models are designed with agents lacking explicit internal information-processing structure in terms of basic cognitive elements. In particular, memory is usually not explicitly modeled. We present initial results from a new prototype called "Wetlands", designed to investigate the effect of group memory structures and interaction situations on emergent patterns of sociality or collective intentionality. Specifically, we report on initial computational experiments conducted on culturally-differentiated agents endowed with finite and degradable memory that simulate bounded mnemonic function and forgetfulness. Our main initial findings are that memory capacity and engram retention both promote sociality among groups, probably as nonlinear (inverse) functions. Wetlands 1.1 is implemented in the new MASON 3 (Multi- Agent Simulator of Networks and Neighborhoods) computational environment developed at George Mason University.
| A Pheromone-based Utility Model for Collaborative Foraging |
PDF
- Citation:
- Liviu Panait and Sean Luke. 2004. A Pheromone-based Utility Model for Collaborative Foraging. In Proceedings of the Third International Joint Conference on Autonomous Angents and Multi Agent Systems (AAMAS), pages 36-43.
- Abstract: Show / Hide
-
Multi-agent research often borrows from biology, where remarkable examples of collective intelligence may be found. One interesting example is ant colonies' use of pheromones as a joint communication mechanism. In this paper we propose two pheromone-based algorithms for artificial agent foraging, trail-creation, and other tasks. Whereas practically all previous work in this area has focused on biologically-plausible but ad-hoc single pheromone models, we have developed a formalism which uses multiple pheromones to guide cooperative tasks. This model bears some similarity to reinforcement learning. However, our model takes advantage of symmetries common to foraging environments which enables it to achieve much faster reward propagation than reinforcement learning does. Using this approach we demonstrate cooperative behaviors well beyond the previous ant-foraging work, including the ability to create optimal foraging paths in the presence of obstacles, to cope with dynamic environments, and to follow tours with multiple waypoints. We believe that this model may be used for more complex problems still.
| Ant Foraging Revisited |
PDF
- Citation:
- Liviu Panait and Sean Luke. 2004. Ant Foraging Revisited. In Proceedings of the Ninth
International Conference on the Simulation and Synthesis of Living Systems (ALIFE9), pages
569-574.
- Abstract: Show / Hide
-
Most previous artificial ant foraging algorithms have to date relied to some degree on a priori knowledge of the environment, in the form of explicit gradients generated by the nest, by hard-coding the nest location in an easily-discoverable place, or by imbuing the artificial ants with the knowledge of the nest direction. In contrast, the work presented solves ant foraging problems using two pheromones, one applied when searching for food and the other when returning food items to the nest. This replaces the need to use complicated nest-discovery devices with simpler mechanisms based on pheromone information, which in turn reduces the ant system complexity. The resulting algorithm is orthogonal and simple, yet ants are able to establish increasingly efficient trails from the nest to the food in the presence of obstacles. The algorithm replaces the blind addition of new amounts of pheromones with an adjustment mechanism that resembles dynamic programming.
| Learning Ant Foraging Behaviors |
PDF
- Citation:
- Liviu Panait and Sean Luke. 2004. Learning ant foraging behaviours. In Jordan Pollack, et al., editors, Artificial Life IX: Ninth International Conference on the Simulation and Synthesis of Living Systems, pages 575-580. The MIT Press.
- Abstract: Show / Hide
-
Insects are good at cooperatively solving many complex tasks. For example, foraging for food far away from a nest can be solved through relatively simple behaviors in combination with pheromones. As task complexity increases, however, it may become difficult to find individual agent rules which yield a desired emergent cooperative behavior, or to know if any such rules exist at all. For such tasks, machine learning techniques like evolutionary computation (EC) may prove a valuable approach to searching the space of possible rule combinations. This paper presents an application of genetic programming to search for foraging behaviors. The learned foraging behaviors use only pheromone information to find the path to the nest and to the food source.
| Ant Foraging Revisited |
PDF
- Note:
-
This one-page poster was considerably extended and improved in a better follow-on paper by the same name: Ant Foraging Revisited.
- Citation:
- Liviu Panait and Sean Luke, 2003. Ant Foraging Revisited. In Proceedings of the
Second International Workshop on the Mathematics and Algorithms of Social Insects, page 184.
- First Paragraph: Show / Hide
-
Previous artificial (non-biological) ant foraging models have to date relied to some degree on a priori knowledge of the environment, in the form of explicit gradients generated by the nest, by hard-coding the nest location in an easily-discoverable place, or by imbuing the artificial ants with the knowledge of the nest direction. In contrast, the work presented solves ant foraging problems using two pheromones, one applied when searching for food and the other when returning food items to the nest. This replaces the need for using complicated devices to locate the nest source with simpler mechanisms based on pheromone information, which in turn reduces the ant system complexity. The resulting algorithm is orthogonal and simple, yet ants are able to establish increasingly efficient trails from the nest to the food in the presence of obstacles.
| Evolving Foraging Behaviors |
PDF
- Note:
-
This small paper was considerably extended and improved in a better follow-on paper, Learning Ant Foraging Behaviors.
- Citation:
- Liviu Panait and Sean Luke, 2003. Evolving foraging behaviors. In Proceedings of the
Second International Workshop on the Mathematics and Algorithms of Social Insects, pages
131-138.
- First Paragraph: Show / Hide
-
Insects are particularly good at cooperatively solving multiple complex tasks. Some such tasks, such a foraging for food far away from the nest or clustering objects into piles, can be solved through relatively simple behaviors in combination with communication mechanisms using pheromones. As task complexity increases, however, it may become difficult to determine the proper simple rules which yield the desired emergent cooperative behavior; or to know if any such rules exist at all. For such tasks, machine learning techniques like evolutionary computation (EC) may prove a valuable approach to searching the space of possible rule combinations.
| MASON: A Multiagent Simulation Library |
PDF
- Citation:
- Sean Luke, Gabriel Catalin Balan, Liviu Panait, Claudio Cioffi-Revilla, and Sean Paus. 2003. MASON: A Multiagent Simulation Library. In Proceedings of the Agent 2003 Conference on Challenges in Social Simulation.
- Abstract: Show / Hide
- Agent-based modeling (ABM) has transformed social science research by allowing researchers to replicate or generate the emergence of empirically complex social phenomena from a set of relatively simple agent-based rules at the micro-level. Swarm, RePast, Ascape, and others currently provide simulation environments for ABM social science research. After Swarm -- arguably the first widely used ABM simulator employed in the social sciences -- subsequent simulators have sought to enhance available simulation tools and computational capabilities by providing additional functionalities and formal modeling facilities. Here we present MASON (Multi-Agent Simulator Of Neighborhoods), following in a similar tradition that seeks to enhance the power and diversity of the available scientific toolkit in computational social science. MASON is intended to provide a core of facilities useful not only to social science but to other agent-based modeling fields such as artificial intelligence and robotics. We believe this can foster useful "cross-pollination" between such diverse disciplines, and further that MASON's additional facilities will become increasing important as social complexity simulation matures and grows into new approaches. We illustrate the new MASON simulation library with a replication of HeatBugs and a demonstration of MASON applied to two challenging case studies: ant-like foragers and micro-aerial agents. Other applications are also being developed. The HeatBugs replication and the two new applications provide an idea of MASON's potential for computational social science and artificial societies.
| Replication of Sugarscape Using MASON |
PDF
- Citation:
- Anthony Bigbee, Claudio Cioffi-Revilla, and Sean Luke. 2005. Replication of Sugarscape Using MASON. In Agent-based Approaches in Economic and Social Complex systems IV: Post-Proceedings of the AESCS International Workshop. Vo. 3. 183-190. Springer.
- First Paragraph: Show / Hide
-
The purpose of this research was to replicate the Sugarscape model (Eptstein and Axtell 1996) and simulation outcomes as described in Growing Artificial Societies (GAS). Sugarscape is a classic agent-based model and contemporary simulation toolkits usually only have a very simple replication of a few core rules. There is scant evidence of significant replication of the rules and simulation outcomes; code supplied with Repast, Swarm, and NetLogo implement a minority of the rules in Sugarscape. In particular, the standard Repast distribution only implements Growback, Movement, and Replacement. Sugarscape implementations in these toolkits are clearly provided only as basic demonstrations of how wellknown social models might be implemented, rather than complete achievements of scientific replication.
| MASON: A New Multi-agent Simulation Toolkit |
PDF
- Citation:
- Sean Luke, Claudio Cioffi-Revilla, Liviu Panait, and Keith Sullivan. 2004. MASON: A New Multi-agent Simulation Toolkit. In Proceedings of the 2004 SwarmFest Workshop.
- Abstract: Show / Hide
-
We introduce MASON, a fast, easily extendable, discrete-event multi-agent simulation toolkit in Java. MASON was designed to serve as the basis for a wide range of multi-agent simulation tasks ranging from swarm robotics to machine learning to social complexity environments. MASON carefully delineates between model and visualization, allowing models to be dynamically detached from or attached to visualizers, and to change platforms mid-run. We describe the MASON system, its motivation, and its basic architectural design. We then discuss five applications of MASON we have built over the past year to suggest its breadth of utility.
| MASON: A Java Multi-agent Simulation Library |
PDF
- Citation:
- Sean Luke, Gabriel Catalin Balan, and Liviu Panait. 2003. MASON: A Java Multi-agent Simulation Library. In Proceedings of the
Second International Workshop on the Mathematics and Algorithms of Social Insects.
- First Paragraph: Show / Hide
-
We present MASON, a new multiagent simulation library written for Java.
MASON is a general-purpose, single-process, discrete-event simulation library in-
tended to support diverse multiagent experiments ranging from 3D continuous robotics
to social complexity networks to discretized ant foraging algorithms.
| Multiagent Learning and Fairness |
Scalable Heterogeneous Multiagent Learning from Demonstration |
PDF
- Citation:
- William Squires and Sean Luke. 2020. Scalable Heterogeneous Multiagent Learning from Demonstration. In International Conference on Practical Applications of Agents and Multi-Agent Systems (PAAMS).
- Abstract: Show / Hide
-
We present a method of supervised learning from demonstration for real-time, online training of complex heterogenous multiagent behaviors which scale to large numbers of agents in operation. Our learning method is applicable in domains where coordinated behaviors must be created quickly in unexplored environments. Examples of such problem domains includes disaster relief, search and rescue, and gaming environments. We demonstrate this training method in an adversarial mining scenario which coordinates four types of individual agents to perform six distinct roles in a mining task.
| Multiagent Soft Q-Learning |
PDF
- Citation:
- Ermo Wei, Drew Wicke, David Freelan, and Sean Luke. 2018. Multiagent Soft Q-Learning. In AAAI Spring Symposium on Data Efficient Reinforcement Learning.
- Abstract: Show / Hide
-
Policy gradient methods are often applied to reinforcement
learning in continuous multiagent games. These methods perform
local search in the joint-action space, and as we show,
they are susceptable to a game-theoretic pathology known
as relative overgeneralization. To resolve this issue, we propose
Multiagent Soft Q-learning, which can be seen as the
analogue of applying Q-learning to continuous controls. We
compare our method to MADDPG, a state-of-the-art approach,
and show that our method achieves better coordination
in multiagent cooperative tasks, converging to better local
optima in the joint action space.
| Hierarchical Approaches for Reinforcement Learning in Parameterized Action Space |
PDF
- Citation:
- Ermo Wei, Drew Wicke, and Sean Luke. 2018. Hierarchical Approaches for Reinforcement Learning in Parameterized Action Space. In AAAI Spring Symposium on Data Efficient Reinforcement Learning.
- Abstract: Show / Hide
-
We explore Deep Reinforcement Learning in a parameterized
action space. Specifically, we investigate how to achieve
sample-efficient end-to-end training in these tasks. We propose
a new compact architecture for the tasks where the parameter
policy is conditioned on the output of the discrete action
policy. We also propose two new methods based on the
state-of-the-art algorithms Trust Region Policy Optimization
(TRPO) and Stochastic Value Gradient (SVG) to train such an
architecture. We demonstrate that these methods outperform
the state of the art method, Parameterized Action DDPG, on
test domains.
| LfD Training of Heterogeneous Formation Behaviors |
PDF
- Citation:
- William Squires and Sean Luke. 2018. LfD Training of Heterogeneous Formation Behaviors. In AAAI Spring Symposium on Learning, Inference, and Control of Multi-Agent Systems.
- Abstract: Show / Hide
-
Problem domains such as disaster relief, search and rescue,
and games can benefit from having a human quickly train
coordinated behaviors for a diverse set of agents. Hierarchical
Training of Agent Behaviors (HiTAB) is a Learning from
Demonstration (LfD) approach that addresses some inherent
complexities in multiagent learning, making it possible to train
complex heterogeneous behaviors from a small set of training
samples. In this paper, we successfully demonstrate LfD
training of formation behaviors using a small set of agents
that, without retraining, continue to operate correctly when
additional agents are available. We selected training of formations
for the experiments because formations: require a great
deal of coordination between agents, are heterogenous due to
the differing roles of participating agents, and can scale as the
number of agents grows. We also introduce some extensions
to HiTAB that facilitate this type of training.
| Lenient Learning in Independent-Learner Stochastic Cooperative Games |
PDF
- Citation:
- Ermo Wei and Sean Luke. 2016. Lenient Learning in Independent-Learner Stochastic Cooperative Games. Journal of Machine Learning Research (17:84) 1–42
- Abstract: Show / Hide
-
We introduce the Lenient Multiagent Reinforcement Learning 2 (LMRL2) algorithm for independent-learner stochastic cooperative games. LMRL2 is designed to overcome a pathology called relative overgeneralization, and to do so while still performing well in games with stochastic transitions, stochastic rewards, and miscoordination. We discuss the existing literature, then compare LMRL2 against other algorithms drawn from the literature which can be used for games of this kind: traditional ("Distributed") Q-learning, Hysteretic Q-learning, WoLF-PHC, SOoN, and (for repeated games only) FMQ. The results show that LMRL2 is very effective in both of our measures (complete and correct policies), and is found in the top rank more often than any other technique. LMRL2 is also easy to tune: though it has many available parameters, almost all of them stay at default settings. Generally the algorithm is optimally tuned with a single parameter, if any. We then examine and discuss a number of side-issues and options for LMRL2.
Unlearning from Demonstration |
PDF
- Citation:
- Keith Sullivan, Ahmned ElMolla, Bill Squires, and Sean Luke. 2013. Unlearning from Demonstration. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI13).
- Abstract: Show / Hide
-
When doing learning from demonstration, it is often the case that the demonstrator provides corrective examples to fix errant behavior by the agent or robot. We present a set of algorithms which use this corrective data to identify and remove noisy examples in datasets which caused errant classifications, and ultimately errant behavior. The objective is to actually modify the source datasets rather than solely rely on the noise-insensitivity of the classification algorithm. This is particularly useful in the sparse datasets often found in learning from demonstration experiments. Our approach tries to distinguish between noisy misclassification and mere undersampling of the learning space. If errors are a result of misclassification, we potentially remove the responsible points and update the classifier. We demonstrate our method on UCI Machine Learning datasets at different levels of sparsity and noise, using decision trees, K-Nearest-Neighbor, and support vector machines.
Multiagent Supervised Training with Agent Hierarchies and Manual Behavior Decomposition |
PDF
- Citation:
- Keith Sullivan and Sean Luke. 2011. Multiagent Supervised Training with Agent Hierarchies and Manual Behavior Decomposition. In Proceedings of the IJCAI 2011 Workshop on Agents Learning Interactively from Human Teachers (ALIHT).
- Abstract: Show / Hide
-
We present a supervised learning from demonstration system capable of training stateful and recurrent behaviors, both in the single agent and multiagent case. Furthermore, behavior complexity due to statefulness and multiple agents can result in a high dimensional learning space, which can require many samples to learn properly. Our approach, which relies heavily on both per-agent behavior decomposition and structuring agents into a tree hierarchy, can significantly reduce the number of samples and make such training feasible. We demonstrate our system in a simulated collective foraging task where all the agents execute the same behavior set. We also discuss how to extend our approach to a heterogeneous case, where different subgroups of agents perform different behaviors.
| Long-term Fairness with Bounded Worst-case Losses |
(Early Workshop Paper) PDF
(Technical Report, Similar to Journal Article) PDF
- Note:
- This paper began as a workshop paper, then was revised into a journal article. Along the way we created a tech report which is very close to the journal article.
- Citation (Workshop Paper):
- Gabriel Balan and Dana Richards and Sean Luke. 2008. Long-term Fairness with Bounded Worst-case Losses. In Proceedings of AAAI Advances in Preference Workshop. 7-12.
- Citation (Journal Article):
- Gabriel Balan and Dana Richards and Sean Luke. 2011. Long-term fairness with bounded worst-case losses. Autonomous Agents and Multiagent Systems. 22(1) 43-63.
- Abstract: Show / Hide
-
How does one repeatedly choose actions so as to be fairest to multiple beneficiaries of those actions? We examine approaches to discovering sequences of actions for which the worst-off beneficiaries are treated maximally well, then secondarily the second-worst-off, and so on. We formulate the problem for the situation where the sequence of action choices continues forever; this problem may be reduced to a set of linear programs. We then extend the problem to situations where the game ends at some unknown finite time in the future. We demonstrate that an optimal solution is NP-hard, and present two good approximation algorithms.
| Theoretical Advantages of Lenient Learners: an Evolutionary Game Theoretic Perspective |
PDF
- Citation:
- Liviu Panait, Karl Tuyls, and Sean Luke. 2008. Theoretical Advantages of Lenient Learners: an Evolutionary Game Theoretic Perspective. Journal of Machine Learning Research. 9(March):423-457.
- Abstract: Show / Hide
- This paper presents the dynamics of multiple learning agents from an evolutionary game theoretic perspective. We provide replicator dynamics models for cooperative coevolutionary algorithms and for traditional multiagent Q-learning, and we extend these differential equations to account for lenient learners: agents that forgive possible mismatched teammate actions that resulted in low rewards. We use these extended formal models to study the convergence guarantees for these algorithms, and also to visualize the basins of attraction to optimal and suboptimal solutions in two benchmark coordination problems. The paper demonstrates that lenience provides learners with more accurate information about the benefits of performing their actions, resulting in higher likelihood of convergence to the globally optimal solution. In addition, the analysis indicates that the choice of learning algorithm has an insignificant impact on the overall performance of multiagent learning algorithms; rather, the performance of these algorithms depends primarily on the level of lenience that the agents exhibit to one another. Finally, the research herein supports the strength and generality of evolutionary game theory as a backbone for multiagent learning.
| An Overview of Cooperative and Competitive Multiagent Learning |
PDF
- Citation:
- Pieter Jan 't Hoen, Karl Tuyls, Liviu Panait, Sean Luke, and J. A. La Poutré. 2005. An Overview of Cooperative and Competitive Multiagent Learning. In Learning and Adaptation in Multi-Agent Systems, First International Workshop (LAMAS). 1-46. Springer.
- Abstract: Show / Hide
-
Multi-agent systems (MASs) is an area of distributed artificial intelligence that emphasizes the joint behaviors of agents with some
degree of autonomy and the complexities arising from their interactions.
The research on MASs is intensifying, as supported by a growing number of conferences, workshops, and journal papers. In this survey we give
an overview of multi-agent learning research in a spectrum of areas, including reinforcement learning, evolutionary computation, game theory,
complex systems, agent modeling, and robotics.
MASs range in their description from cooperative to being competitive
in nature. To muddle the waters, competitive systems can show apparent
cooperative behavior, and vice versa. In practice, agents can show a wide
range of behaviors in a system, that may either fit the label of cooperative
or competitive, depending on the circumstances. In this survey, we discuss current work on cooperative and competitive MASs and aim to make
the distinctions and overlap between the two approaches more explicit.
Lastly, this paper summarizes the papers of the first International
workshop on Learning and Adaptation in MAS (LAMAS) hosted at the
fourth International Joint Conference on Autonomous Agents and Multi
Agent Systems (AAMAS'05) and places the work in the above survey.
| Can Good Learners Always Compensate for Poor Learners? |
PDF
- Citation:
- Keith Sullivan, Liviu Panait, and Sean Luke. 2006. Can Good Learners Always Compensate for Poor Learners? In Proceedings of the 2006 Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).
- Note:
- A fuller version of this paper may be found in the following technical report (PDF).
- Abstract: Show / Hide
-
Can a good learner compensate for a poor learner when paired in a coordination game? Previous work has given an example where a special learning algorithm (FMQ) is capable of doing just that when paired with a specific less capable algorithm even in games which stump the poorer algorithm when paired with itself. In this paper, we argue that this result is not general. We give a straightforward extension to the coordination game in which FMQ cannot compensate for the lesser algorithm. We also provide other problematic pairings, and argue that another high-quality algorithm cannot do so either.
| Lenient Learners in Cooperative Multiagent Systems |
PDF
- Citation:
- Liviu Panait, Keith Sullivan, and Sean Luke. 2006. Lenient Learners in Cooperative Multiagent Systems. In Proceedings of the 2006 Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).
- Note:
- A fuller version of this paper may be found in the following technical report (PDF).
- Abstract: Show / Hide
- In concurrent learning algorithms, an agent's perception of the joint search space depends on the actions currently chosen by the other agents. These perceptions change as each agent's action selection is influenced by its learning. We observe that agents that show lenience to their teammates achieve more accurate perceptions of the overall learning task. Additionally, lenience appears more beneficial at early stages of learning, when the agent's teammates are merely exploring their actions, and less helpful as the agents start to converge. We propose two multiagent learning algorithms where agents exhibit a variable degree of lenience, and we demonstrate their advantages in several coordination problems.
| Collaborative Multi-agent Learning: The State of the Art |
PDF
- Citation:
- Liviu Panait and Sean Luke. 2005. Collaborative Multi-agent Learning: The State of the Art. Autonomous Agents and Multi-agent Systems 11:3 (November). 387-434.
- Abstract: Show / Hide
-
Cooperative multi-agent systems are ones in which several agents attempt, through their interaction, to jointly solve tasks or to maximize utility. Due to the interactions among the agents, multi-agent problem complexity can rise rapidly with the number of agents or their behavioral sophistication. The challenge this presents to the task of programming solutions to multi-agent systems problems has spawned increasing interest in machine learning techniques to automate the search and optimization process.
We provide a broad survey of the cooperative multi-agent learning literature. Previous surveys of this area have largely focused on issues common to specific subareas (for example, reinforcement learning or robotics). In this survey we attempt to draw from multi-agent learning work in a spectrum of areas, including reinforcement learning, evolutionary computation, game theory, complex systems, agent modeling, and robotics.
We find that this broad view leads to a division of the work into two categories, each with its own special issues: applying a single learner to discover joint solutions to multi-agent problems (team learning), or using multiple simultaneous learners, often one per agent (concurrent learning). Additionally, we discuss direct and indirect communication in connection with learning, plus open issues in task decomposition, scalability, and adaptive dynamics. We conclude with a presentation of multi-agent learning problem domains, and a list of multi-agent learning resources.
| Collaborative Multi-agent Learning: A Survey |
PDF
- Note:
-
This is an early version of the much improved survey Collaborative Multi-agent Learning: the State of the Art, which you should read instead.
- Citation:
- Liviu Panait and Sean Luke. 2004. Collaborative Multi-agent Learning: A Survey. In AAAI Fall Symposium on Multiagent Learning.
- Abstract: Show / Hide
-
The field of Multiagent Systems is concerned with domains where several agents interact while solving competitive or cooperative tasks. Increasingly complex problem domains involving non-trivial numbers of agents revealed inherent difficulties with creating such systems. As such, the field witnessed a recent increased interest in Machine Learning techniques, capable of easing the programming efforts for approaching more challenging domains.
Despite the relative youth of the field, there are already several hundreds of papers trying to answer interesting questions in domains where learning affects the behavior of more than a single agent. Such questions target issues as varied as learning to communicate, modeling other agents in the environment, learning to compete or cooperate with the other agents, analysis of optimality for the learning algorithms, and many others. The large variety of papers generates a desirability for good surveys categorizing previous work.
We argue that there are two alternatives for learning in multiagent systems. A first direction is to have each individual agent learn how to improve its performance. The alternative is to have a single learning process that improves the behavior of the entire team of agents. Because of scalability problems with respect to increased numbers of agents, the majority of machine learning techniques can not be realistically applied to learn team behaviors. We discovered that most previous surveys concentrate on individual agents' learning, but neglect approaches at the team level.
In this survey, we propose a new arrangement for multiagent learning papers. As such, there is an entire category of papers dealing with learning behaviors for the entire team and issues associated with scalability to non-trivial numbers of agents, such as the heterogeneity of the team. A second class of papers is concerned with individual agent learning in multiagent domains. Based on their main research focus, the papers are categorized in sections dealing with optimality of learned behaviors, impact of locality of reward information, cooperation or competition relations among agents, and modeling other agents.
Additionally, we identified two issues relatively perpendicular to the team or individual levels of learning: problem decomposition and communication. The former is concerned with techniques for decomposing either the problem to be solved or the collective behavior into simpler independent components that can be more easily handled by the learning process. An in-depth survey of the literature on the relationship between multiagent learning and communication revealed three approaches, each with its own particularities. The three such methods involve communication via either rapidly decaying information, slowly decaying information, or embodiment.
| Evolutionary Algorithms |
ECJ at 20: Toward a General Metaheuristics Toolkit |
PDF
- Citation:
- Eric Scott and Sean Luke. 2019. ECJ at 20: Toward a General Metaheuristics Toolkit. In GECCO (2019).
- Abstract Show / Hide
-
ECJ is now 20 years old. Begun as a genetic programming and evolutionary computation library in Java, it has since established itself as historically one of the most popular EC toolkits worldwide. In 2016 we received a National Science Foundation grant to improve ECJ in many ways with an eye toward making it a useful toolkit not just for EC but for the broader metaheuristics community. This paper is a report on our efforts to this end. We discuss new metaheuristics frameworks and representations added to ECJ and the design challenges that they raise for a general-purpose framework, as well as testing facilities and other support tools. We conclude with our future directions for the library.
|
ECJ Then and Now |
PDF
- Citation:
- Sean Luke. 2017. ECJ Then and Now. In GECCO (2017).
- Abstract Show / Hide
-
ECJ is a mature and widely used evolutionary computation library with particular strengths in genetic programming, massive distributed computation, and coevolution. In Fall of 2016 we received a three-year NSF grant to expand ECJ into a toolkit with wide-ranging facilities designed to serve the broader metaheuristics community. This report discusses ECJ’s history, capabilities, and architecture, then details our planned extensions and expansions.
|
Is the Meta-EA a Viable Optimization Method? |
PDF
- Citation:
- Sean Luke and AKM Khaled Ahsan Talukder. 2013. Is the Meta-EA a Viable Optimization Method? In Proceedings
of the 15th Annual Conference on Genetic and Evolutionary Computation
(GECCO 2013).
- Note:
- This version has a few very minor corrections made to the original conference publication.
- Abstract: Show / Hide
-
Meta-evolutionary algorithms have long been proposed as an approach to automatically discover good parameter settings to use in later optimization runs. In this paper we instead ask whether a meta-evolutionary algorithm makes sense as an optimizer in its own right. That is, we're not interested in the resulting parameter settings, but only in the final result. As it so happens, this use of meta-EAs make sense in the context of large numbers of parallel runs, particularly in massive distributed scenarios. A primary issue facing meta-EAs is the stochastic nature of the meta-level fitness function. We consider whether this poses a challenge to establishing a gradient in the meta-level search space, and to what degree multiple tests are helpful in smoothing the noise. We discuss the nature of the meta-level search space and its impact on local optima, then examine the degree to which exploitation can be applied. We find that meta-EAs perform well as optimizers, and very surprisingly that they do best with only a single test. More exploitation appears to reduce performance, but only slightly.
| Multiobjective Optimization of Co-Clustering Ensembles |
PDF
- Citation:
- Francesco Gullo, AKM Khaled Ahsan Talukder, Sean Luke, Carlotta Domeniconi, and Andrea Tagarelli. Multiobjective Optimization of Co-Clustering Ensembles. In GECCO '12: Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation. Pages 1495-1496. ACM.
- Note:
- A fuller version of this paper may be found in the following technical report (PDF).
- Abstract: Show / Hide
-
Co-clustering is a machine learning task where the goal is to simultaneously develop clusters of the data and of their respective features. We address the use of co-clustering ensembles to establish a consensus co-clustering over the data. In this paper we develop a new preference-based multiobjective optimization algorithm to compete with a previous gradient ascent approach in finding optimal co-clustering ensembles. Unlike the gradient ascent algorithm, our approach once tackles the co-clustering problem with multiple heuristics, then applies the gradient ascent algorithm's joint heuristic as a preference selection procedure. We are able to significantly outperform the gradient ascent algorithm on feature clustering and on problems with smaller datasets.
| Finding Interesting Things: Population-based Adaptive Parameter Sweeping |
PDF
- Citation:
- Sean Luke and Deepankar Sharma and Gabriel Catalin Balan. 2007. Finding Interesting Things: Population-based Adaptive Parameter Sweeping. In GECCO '07: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation. Pages 86-93. ACM.
- Abstract: Show / Hide
- Model- and simulation-designers are often interested not in the optimum output of their system, but in understanding how the output is sensitive to different parameters. This can require an inefficient sweep of a multidimensional parameter space, with many samples tested in regions of the space where the output is essentially all the same, or a sparse sweep which misses crucial "interesting" regions where the output is strongly sensitive. In this paper we introduce a novel population-oriented approach to adaptive parameter sweeping which focuses its samples on these sensitive areas. The method is easy to implement and model-free, and does not require any previous knowledge about the space. In a weakened form the method can operate in non-metric spaces such as the space of genetic program trees. We demonstrate the method on three test problems, showing that it identifies regions of the space where the slope of the output is highest, and concentrates samples on those regions.
| Opportunistic Evolution: Efficient Evolutionary Computation on Large-Scale Computational Grids |
PDF
- Citation:
- Keith Sullivan, Sean Luke, Curt Larock, Sean Cier, and Steven Armentrout. 2008. Opportunistic Evolution: Efficient Evolutionary Computation on Large-Scale Computational Grids. In Genetic and Evolutionary Computation Conference Late Breaking Papers.
- Abstract: Show / Hide
-
We examine opportunistic evolution, a variation of master-slave distributed evaluation designed for deployment of evolutionary computation to very large grid computing architectures with limited communications, severe evaluation overhead, and wide variance in evaluation node speed. In opportunistic evolution, slaves receive some N individuals at a time, evaluate them, and then run those individuals through their own mini evolutionary loop until some fixed wall clock time has been exceeded. Our implementation of opportunistic evolution may be used in conjunction with either a generational or, for maximum throughput, an asynchronous steady-state evolutionary model in the master. Opportunistic evolution is strongly exploitative. We perform initial experiments comparing the technique with a traditional master/slave model, and suggest possible classes of problems for which it might be apropos.
| An Application of Evolutionary Algorithms to Study the Extent of SLHF Anomaly Associated with Coastal Earthquakes |
PDF
- Citation:
- Guido Cervone, Liviu Panait, Ramesh Singh, and Sean Luke. 2004. An application of evolutionary algorithms to study the extent of SLHF anomaly associated with coastal earthquakes. In Late Breaking Papers of the Genetic and Evolutionary Computation Conference (GECCO). Springer.
- Abstract: Show / Hide
-
Multi sensor remote sensing provides real time high resolution data that can be used to study anomalous changes on land, in the
ocean, and in the atmosphere associated with an impending earthquake.
Anomalous behaviour in Surface Latent Heat Flux (SLHF) prior to large
coastal earthquakes has been recently found. However, an SLHF time series usually contains several sharp peaks that may be associated either
with earthquakes or with atmospheric perturbations. In this paper we
have used evolutionary algorithms to perform a search in a large space
bounded by longitude, latitude and time, to distinguish between signals associated with earthquakes and those associated with atmospheric
phenomena. The algorithm finds paths which delimit the extent of the
detected anomalies by optimizing an ob jective function that takes into
consideration several aspects, such as spatial and time continuity, the
magnitude of the anomalies, and the distance to the continental boundary. This search strategy is crucial for the development of a fully automated early warning system for providing information about impending
earthquakes in a seismically active coastal region.
Experiments have been performed over a 2000 km^2
area comprising a
part of the continental boundary between the African and Eurasian plate,
roughly corresponding to Italy and Greece, one of the most seismically
active regions. Using a 365-days-long time series, we identified three signals associated with seismic events. Additionally, it was possible to establish that the extent of the signal does not propagate further than 600
km from the epicenter of the earthquake.
| Coevolution |
Large Scale Empirical Analysis of Cooperative Coevolution |
PDF
- Citation:
- Sean Luke, Keith Sullivan, and Faisal Abidi. 2011. Large Scale Empirical Analysis of Cooperative Coevolution. In Proceedings of the 13th Annual Conference Companion on Genetic and Evolutionary Computation (GECCO 2011). Pages 151-152. ACM.
- Note:
- A much fuller version of this paper may be found in the following technical report (PDF).
- Note:
- This is part 1 of a two paper sequence. The second is Do Multiple Trials Help Univariate Methods?
- Abstract: Show / Hide
-
We present a study of cooperative coevolution applied to moderately complex optimization problems in large-population environments. The study asks three questions. First: what collaboration methods perform best, and when? Second: how many subpopulations are desirable? Third: is it worthwhile to do more than one trial per fitness evaluation? We discovered that parallel methods tended to work better than sequential ones, that “shuffling” (a collaboration method) predominated in performance in more complex problems, that more subpopulations generally did better, and that more trials performed marginally better.
| Do Multiple Trials Help Univariate Methods? |
PDF
- Citation:
- Daniel Rothman, Sean Luke, and Keith Sullivan. 2011. Do Multiple Trials Help Univariate Methods?
In Proceedings of the 2011 Congress of Evolutionary Computation, 2011. Pages 2391-2398. IEEE.
- Note:
- This is part 2 of a two paper sequence. The second is Large Scale Empirical Analysis of Cooperative Coevolution
- Abstract: Show / Hide
-
Cooperative Coevolutionary Algorithms (CCEAs) and Univariate Estimation of Distribution Algorithms (Univariate EDAs) are closely related algorithms in that both update marginal distributions/populations, and test samples of those distributions/populations by grouping them with collaborators drawn from elsewhere to form a complete solution. Thus the quality of these samples is context-sensitive and the algorithms assume low linkage among their variables. This results in well-known difficulties with these methods. While EDAs have commonly overcome these difficulties by examining multivariate linkage, CCEAs have instead examined basing the fitness of each marginal sample on the maximum of several trials. In this study we examine whether multiple-trial CCEA approach is really effective for difficult problems and large numbers of subpopulations; and whether this approach can be used to improve Univariate EDAs as well.
| Cooperative Coevolution and Univariate Estimation of Distribution Algorithms |
PDF
- Citation:
- Christopher Vo, Liviu Panait, and Sean Luke. 2007. Cooperative Coevolution and Univariate Estimation of Distribution Algorithms. In Proceedings of the 10th ACM SIGEVO Conference on Foundations of Genetic Algorithms (FOGA). Pages 141-150. ACM.
- Abstract: Show / Hide
- In this paper, we discuss a curious relationship between Cooperative Coevolutionary Algorithms (CCEAs) and univariate Estimation of Distribution Algorithms (EDAs). Specifically, the distribution model for univariate EDAs is equivalent to the infinite population EGT model common in the analysis of CCEAs. This relationship may permit cross- pollination between these two disparate fields. As an example, we derive a new EDA based on a known CCEA from the literature, and provide some preliminary experimental analysis of the algorithm.
| Biasing Coevolutionary Search for Optimal Multiagent Behaviors |
PDF
- Citation:
- Liviu Panait, Sean Luke, and R. Paul Wiegand. 2006. Biasing Coevolutionary Search for Optimal Multiagent Behaviors. IEEE Transactions on Evolutionary Computation. 10(6):629-645.
- Abstract: Show / Hide
- Cooperative coevolutionary algorithms offer great potential for concurrent multiagent learning domains and are of special utility to domains involving teams of multiple agents. Unfortunately, they also exhibit pathologies resulting from their game-theoretic nature, and these pathologies interfere with finding solutions that correspond to optimal collaborations of interacting agents. We address this problem by biasing a cooperative coevolutionary algorithm in such a way that the fitness of an individual is based partly on the result of interactions with other individuals (as is usual), and partly on an estimate of the best possible reward for that individual if partnered with its optimal collaborator. We justify this idea using existing theoretical models of a relevant subclass of coevolutionary algorithms, demonstrate how to apply biasing in a way that is robust with respect to parameterization, and provide some experimental evidence to validate the biasing approach. We show that it is possible to bias coevolutionary methods to better search for optimal multiagent behaviors.
| Archive-based Cooperative Coevolutionary Algorithms |
PDF
- Citation:
- Liviu Panait, Keith Sullivan, and Sean Luke. 2006. Archive-based Cooperative Coevolutionary Algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO).
- Abstract: Show / Hide
- Archive-based cooperative coevolutionary algorithms attempt to retain a set of individuals which act as good collaborators for other coevolved individuals in the evolutionary system. We introduce a new archive-based algorithm, called iCCEA, which compares favorably with other cooperative coevolutionary algorithms. We explain the current problems with cooperative coevolution which have given rise to archive methods, detail the iCCEA algorithm, compare it against other traditional and archive-based methods on basic problem domains, and discuss the reasons behind the performance of various algorithms.
| Selecting Informative Actions Improves Cooperative Multiagent Learning |
PDF
- Citation:
- Liviu Panait and Sean Luke. 2006. Selecting Informative Actions Improves Cooperative Multiagent Learning. In Proceedings of the 2006 Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).
- Abstract: Show / Hide
- In concurrent cooperative multiagent learning, each agent simultaneously learns to improve the overall performance of the team, with no direct control over the actions chosen by its teammates. An agent's action selection directly influences the rewards received by all the agents, resulting in a co-adaptation among the concurrent learning processes. Co-adaptation can drive the team towards suboptimal solutions because agents tend to select those actions that are rewarded better, without any consideration for how such actions may affect the search of their teammates. We argue that to counter this tendency, agents should also prefer actions that inform their teammates about the structure of the joint search space in order to help them choose from among various action options. We analyze this approach in a cooperative coevolutionary framework, and we propose a new algorithm, iCCEA, that highlights the advantages of selecting informative actions. We show that iCCEA generally outperforms other cooperative coevolution algorithms on our test problems.
| Time-dependent Collaboration Schemes for Cooperative Coevolutionary Algorithms |
PDF
- Citation:
- Liviu Panait and Sean Luke. 2005. Time-dependent Collaboration Schemes for Cooperative Coevolutionary Algorithms. In AAAI 2005 Fall Symposium on Coevolutionary and Coadaptive Systems. 18-25.
- Abstract: Show / Hide
-
Cooperative coevolutionary algorithms represent a popular approach to learning via problem decomposition. Since they were proposed more than a decade ago, their properties have been studied both formally and empirically. One important aspect of cooperative coevolutionary algorithms concerns how to select collaborators for computing the fitness of individuals in different populations. We argue that using a fixed number of collaborators during the entire search may be suboptimal. We experiment with a simple ad-hoc collaboration scheme that varies the numbers of collaborators over time. Empirical comparisons in a series of problem domains indicate that decreasing the numbers of collaborators over time fares better than fixed collaboration schemes. We conclude with a bried discussion of our findings and suggest directions for future research.
| A Visual Demonstration of Convergence Properties of Cooperative Coevolution |
PDF
- Citation:
- Liviu Panait, R. Paul Wiegand, and Sean Luke. 2004. A Visual Demonstration of Convergence Properties of Cooperative Coevolution. In Parallel Problem Solving from Nature (PPSN 2004). Springer. Pages 892-901.
- Abstract: Show / Hide
- We introduce a model for cooperative coevolutionary algorithms (CCEAs) using partial mixing, which allows us to compute the expected long-run convergence of such algorithms when individuals' fitness is based on the maximum payoff of some N evaluations with partners chosen at random from the other population. Using this model, we devise novel visualization mechanisms to attempt to qualitatively explain a difficult-to-conceptualize pathology in CCEAs: the tendency for them to converge to suboptimal Nash equilibria. We further demonstrate visually how increasing the size of N, or biasing the fitness to include an ideal-collaboration factor, both improve the likelihood of optimal convergence, and under which initial population configurations they are not much help.
| A Sensitivity Analysis of a Cooperative Coevolutionary Algorithm Biased for Optimization |
PDF
- Citation:
- Liviu Panait, R. Paul Wiegand, and Sean Luke. 2004. A Sensitivity Analysis of a Cooperative Coevolutionary Algorithm Biased for Optimization. In Genetic and Evolutionary Computation Conference (GECCO). Springer. Pages 587-584.
- Abstract: Show / Hide
- Recent theoretical work helped explain certain optimization-related pathologies in cooperative coevolutionary algorithms (CCEAs). Such explanations have led to adopting specific and constructive strategies for improving CCEA optimization performance by biasing the algorithm toward ideal collaboration. This paper investigates how sensitivity to the degree of bias (set in advance) is affected by certain algorithmic and problem properties. We discover that the previous static biasing approach is quite sensitive to a number of problem properties, and we propose a stochastic alternative which alleviates this problem. We believe that finding appropriate biasing rates is more feasible with this new biasing technique.
| Methods for Evolving Robust Programs |
PDF
- Citation:
- Liviu Panait and Sean Luke. 2003. Methods for Evolving Robust Programs. In Genetic and Evolutionary Computation (GECCO-2003). Springer. Pages 1740-1751.
- Abstract: Show / Hide
- Many evolutionary computation search spaces require fitness assessment through the sampling of and generalization over a large set of possible cases as input. Such spaces seem particularly apropos to Genetic Programming, which notionally searches for computer algorithms and functions. Most existing research in this area uses ad-hoc approaches to the sampling task, guided more by intuition than understanding. In this initial investigation, we compare six approaches to sampling large training case sets in the context of genetic programming representations. These approaches include fixed and random samples, and adaptive methods such as coevolution or fitness sharing. Our results suggest that certain domain features may lead to the preference of one approach to generalization over others. In particular, coevolution methods are strongly domain-dependent. We conclude the paper with suggestions for further investigations to shed more light onto how one might adjust fitness assessment to make various methods more effective.
| Improving Coevolutionary Search for Optimal Multiagent Behaviors |
PDF
- Citation:
- Liviu Panait, R. Paul Wiegand, and Sean Luke. 2003. Improving Coevolutionary Search for Optimal Multiagent Behaviors. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03). Georg Gottlob and Toby Walsh, editors. Pages 653-658.
- Abstract: Show / Hide
- Evolutionary computation is a useful technique for learning behaviors in multiagent systems. Among the several types of evolutionary computation, one natural and popular method is to coevolve multiagent behaviors in multiple, cooperating populations. Recent research has suggested that coevolutionary systems may favor stability rather than performance in some domains. In order to improve upon existing methods, this paper examines the idea of modifying traditional coevolution, biasing it to search for maximal rewards. We introduce a theoretical justification of the improved method and present experiments in three problem domains. We conclude that biasing can help coevolution find better results in some multiagent problem domains.
| Guaranteeing Coevolutionary Objective Measures |
PDF
- Citation:
- Sean Luke and R. Paul Wiegand. 2002. Guaranteeing Coevolutionary Objective Measures. In Foundations of Genetic Algorithms VII. Pages 237-251. Morgan Kaufman.
- Abstract: Show / Hide
- The task of understanding the dynamics of coevolutionary algorithms or com- paring performance between such algorithms is complicated by the fact the internal tness measures are subjective. Though several techniques have been proposed to use external or objective measures to help in analysis, there are clearly properties of fitness payoff , like intransitivity, for which these techniques are ineffective. We feel that a principled approach to this problem is to rst establish the theoretical bounds to guarantee objective measures in one CEA model; from there one can later examine the e ects of deviating from the assumptions made by these bounds. To this end, we present a model of compet- itive tness assessment with a single population and non-parametric selection (such as tournament selection), and show minimum conditions and examples under which an objective measure exists, and when the dynamics of the coevolutionary algorithm are identical to those of a traditional EA.
| A Comparison of Two Competitive Fitness Functions |
PDF
- Citation:
- Liviu Panait and Sean Luke. 2002. A Comparison of Two Competitive Fitness Functions. In GECCO-2002: Proceedings of the Genetic and Evolutionary Computation Conference. W. B. Langdon et al, eds. Morgan Kauffman. 503-511.
- Abstract: Show / Hide
-
Competitive fitness is the assessment of an individual's fitness in the context of competition with other individuals in the evolutionary system. This commonly takes one of two forms: one-population competitive fitness, where competition is solely between individuals in the same population; and N-population competitive fitness, often termed competitive coevolution. In this paper we discuss common topologies for one-population competitive fitness functions, then test the performance of two such topologies, Single-Elimination Tournament and K-Random Opponents, on four problem domains. We show that neither of the extremes of K-Random Opponents (Round Robin and Random-Pairing) gives the best results when using limited computational resources. We also show that while Single-Elimination Tournament usually outperforms variations of K-Random Opponents in noise-free problems, it can suffer from premature convergence in noisy domains.
| When Coevolutionary Algorithms Exhibit Evolutionary Dynamics |
PDF
- Citation:
- Sean Luke and R. Paul Wiegand. 2002. When Coevolutionary Algorithms Exhibit Evolutionary Dynamics. In the Workshop on Understanding Coevolution: Theory and Analysis of Coevolutionary Algorithms (at GECCO 2002). A. Barry, ed. 236-241.
- Abstract: Show / Hide
-
The task of understanding the dynamics of coevolutionary algorithms or comparing
performance between such algorithms is complicated by the fact the internal fitness
measures are subjective. Though a variety of techniques have been proposed to
use external or objective measures to help in analysis, there are clearly properties
of fitness payoff (e.g., intransitivity) which call such methods into question in certain
contexts. We present a model of competitive fitness assessment with a single
population and non-parametric selection (such as tournament selection), and show
minimum conditions and examples under which an objective measure exists,
and when the dynamics of the coevolutionary algorithm are identical to those of
a traditional EA.
We also discuss terminological difficulties in the coevolution
literature, and present a detailed description of external measures presently
in use in the literature.
| Genetic Programming |
Genetic Programming Needs Better Benchmarks |
PDF
- Note:
- This is the third version of the paper, and differs from the original publication slightly, by fixing a few errors in certain benchmark specifications.
- Note:
- This paper was produced in concert with gpbenchmarks.org
- Note:
- The symbolic regression benchmarks in this paper may be found in ECJ.
- Citation:
- James McDermott and David R. White and Sean Luke and Luca Manzoni and Mauro Castelli and Leonardo Vanneschi and Wojciech Jaśkowski and Krzysztof Krawiec and Robin Harper and Kenneth De Jong and Una-May O'Reilly. 2012. Genetic Programming Needs Better Benchmarks. In GECCO '12: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation. ACM.
- Abstract: Show
/ Hide
- Genetic programming (GP) is not a field noted for the rigor of its benchmarking. Some of its benchmark problems are popular purely through historical contingency, and they can be criticized as too easy or as providing misleading information concerning real-world performance, but they persist largely because of inertia and the lack of good alternatives. Even where the problems themselves are impeccable, comparisons between studies are made more difficult by the lack of standardization. We argue that the definition of standard benchmarks is an essential step in the maturation of the field. We make several contributions towards this goal. We motivate the development of a benchmark suite and define its goals; we survey existing practice; we enumerate many candidate benchmarks; we report progress on reference implementations; and we set out a concrete plan for gathering feedback from the GP community that would, if adopted, lead to a standard set of benchmarks.
| Evolving Kernels for Support Vector Machine Classification |
PDF
- Citation:
- Keith M. Sullivan and Sean Luke. 2007. Evolving Kernels for Support Vector Machine Classification. In GECCO '07: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation. Pages 1702-1707. ACM.
- Abstract: Show / Hide
- While support vector machines (SVMs) have shown great promise in supervised classification problems, researchers have had to rely on expert domain knowledge when choosing the SVM's kernel function. This project seeks to replace this expert with a genetic programming (GP) system. Using strongly typed genetic programming and principled kernel closure properties, we introduce a new algorithm, called KGP, which finds near-optimal kernels. The algorithm shows wide applicability, but the combined computational overhead of GP and SVMs remains a major unresolved issue.
| A Demonstration of Neural Programming Applied to Non-Markovian Problems |
PDF
- Citation:
- Gabriel Catalin Balan and Sean Luke. 2004. A Demonstration of Neural Programming Applied to Non-Markovian Problems. In Genetic and Evolutionary Computation Conference (GECCO). Springer. Pages 422-433.
- Abstract: Show / Hide
- Genetic programming may be seen as a recent incarnation of a long-held goal in evolutionary computation: to develop actual computational devices through evolutionary search. Genetic programming is particularly attractive because of the generality of its application, but it has rarely been used in environments requiring iteration, recursion, or internal state. In this paper we investigate a version of genetic programming developed originally by Astro Teller called neural programming. Neural programming has a cyclic graph representation which lends itself naturally to implicit internal state and recurrence, but previously has been used primarily for problems which do not need these features. In this paper we show a successful application of neural programming to various partially observable Markov decision processes, originally developed for the learning classifier system community, and which require the use of internal state and iteration.
| Population Implosion in Genetic Programming |
PDF
- Citation:
- Sean Luke, Gabriel Catalin Balan, and Liviu Panait. 2003. Population Implosion in Genetic Programming. In Genetic and Evolutionary Computation (GECCO-2003). Springer. Pages 1729-1739.
- Abstract: Show / Hide
- With the exception of a small body of adaptive-parameter literature, evolutionary computation has traditionally favored keeping the population size constant through the course of the run. Unfortunately, genetic programming has an aging problem: for various reasons, late in the run the technique become less effective at optimization. Given a fixed number of evaluations, allocating many of them late in the run may thus not be a good strategy. In this paper we experiment with gradually decreasing the population size throughout a genetic programming run, in order to reallocate more evaluations to early generations. Our results show that over four problem domains and three different numbers of evaluations, decreasing the population size is always as good as, and frequently better than, various fixed-sized population strategies.
| Is the Perfect the Enemy of the Good? |
PDF
- Citation:
- Sean Luke and Liviu Panait. 2002. Is the Perfect the Enemy of the Good? In GECCO-2002: Proceedings of the Genetic and Evolutionary Computation Conference. W. B. Langdon et al, eds. Morgan Kauffman. 820-828.
- Abstract: Show / Hide
-
Much of the genetic programming literature compares techniques using counts of ideal solutions found. These counts in turn form common comparison measures such as Koza's Computational Effort or cumulative Probability of Success. The use of these measures continues despite past warnings that they are not statistically valid. In this paper we too criticize the measures for serious statistical problems, and also argue that their motivational justification is faulty. We then present evidence suggesting that ideal solution counts are not necessarily positively related to best-fitness-of-run statistics: in fact they are often inversely correlated. Thus claims based on ideal solution counts can mislead readers into thinking techniques will provide superior final results, when in fact the opposite is true.
| When Short Runs Beat Long Runs |
PDF
- Citation:
- Sean Luke. 2001. When short runs beat long runs. In GECCO-2001: Proceedings of the Genetic and Evolutionary Computation Conference. Lee Spector et al, eds. Morgan Kaufmann. 74-80.
- Abstract: Show / Hide
-
What will yield the best results: doing one run n generations long or doing m runs n/m generations long each? This paper presents a technique-independent analysis which answers this question, and has direct applicability to scheduling and restart theory in evolutionary computation and other stochastic methods. The paper then applies this technique to three problem domains in genetic programming. It discovers that in two of these domains there is a maximal number of generations beyond which it is irrational to plan a run; instead it makes more sense to do multiple shorter runs.
| A Survey and Comparison of Tree Generation Algorithms |
PDF
- Citation:
- Sean Luke and Liviu Panait. 2001. A survey and comparison of tree generation algorithms. In GECCO-2001: Proceedings of the Genetic and Evolutionary Computation Conference. Lee Spector et al, eds. Morgan Kaufmann. 81-88.
- Abstract: Show / Hide
-
This paper discusses and compares five major tree-generation algorithms for genetic programming, and their effects on fitness: RAMPED HALF-AND-HALF, PTC1, PTC2, RANDOM-BRANCH, and UNIFORM. The paper compares the performance of these algorithms on three genetic programming problems (11-Boolean Multiplexer, Artificial Ant, and Symbolic Regression), and discovers that the algorithms do not have a significant impact on fitness. Additional experimentation shows that tree size does have an important impact on fitness, and further that the ideal initial tree size is very different from that used in traditional GP.
| Two Fast Tree-Creation Algorithms for Genetic Programming |
- PDF
- Citation:
- Sean Luke. 2000. Two fast tree-creation algorithms for genetic programming. In IEEE Transactions on Evolutionary Computation 4:3 (September 2000), 274-283. IEEE.
- Abstract: Show / Hide
-
Genetic programming is an evolutionary optimization method that produces functional programs to solve a given task. These programs commonly take the form of trees representing LISP s-expressions, and a typical evolutionary run produces a great many of these trees. For this reason, a good tree-generation algorithm is very important to genetic programming. This paper presents two new tree-generation algorithms for genetic programming and for "strongly-typed" genetic programming, a common variant. These algorithms are fast, allow the user to request specific tree sizes, and guarantee probabilities of certain nodes appearing in trees. The paper analyzes these two algorithms and compares them with traditional and recently proposed approaches.
| “Genetic” Programming |
PDF
- Citation:
- Sean Luke, Shugo Hamahashi, and Hiroaki Kitano. 1999. "Genetic" programming.
In GECCO-99: Proceedings of the Genetic and Evolutionary
Computation Conference, Banzhaf, W. et al, eds.
San Fransisco: Morgan Kaufmann.
- Abstract: Show / Hide
-
Much of evolutionary computation was inspired by Mendelian genetics.
But modern genetics has since advanced considerably, revealing that
genes are not simply parameter settings, but interactive cogs in a
complex chemical machine. At the same time, an increasing number of
evolutionary computation domains are evolving non-parameterized
mechanisms such as neural networks or symbolic computer programs.
As such, we think modern biological genetics offers much in helping
us understand how to evolve such things. In this paper, we present
a gene regulation model for Drosophila melanogaster. We
then apply gene regulation to evolve deterministic finite-state
automata, and show that our approach does well compared to past
examples from the literature.
| A Revised Comparison of Crossover and Mutation in Genetic Programming |
PDF
- Note:
-
This paper is a revision of a previous paper, with statistical correction and a considerable new set of data. However, the original also has some data that does not appear here, so you may want to consider getting both.
- Citation:
- Sean Luke and Lee Spector. 1998. A Revised Comparison of Crossover and Mutation in Genetic Programming. In Proceedings of the Third Annual Genetic Programming Conference (GP98). J. Koza et al, eds. 208-213. San Fransisco: Morgan Kaufmann.
- Abstract: Show / Hide
-
In [Luke and Spector 1997] we presented a comprehensive suite of data
comparing GP crossover and point mutation over four domains and a wide
range of parameter settings. Unfortunately, the results were marred by
statistical flaws. This revision of the study eliminates these flaws,
with three times as much the data as the original experiments had. Our
results again show that crossover does have some advantage over mutation
given the right parameter settings (primarily larger population sizes),
though the difference between the two surprisingly small. Further, the
results are complex, suggesting that the big picture is more complicated
than is commonly believed.
| A Comparison of Crossover and Mutation in Genetic Programming |
PDF
- Note:
- This paper has been superceeded by A Revised Comparison of Crossover and Mutation in Genetic Programming. The revised version has new data which corrects some statistical flaws in the original.
- Citation:
- Sean Luke and Lee Spector. 1997. A Comparison of Crossover and Mutation in Genetic Programming.
In Genetic Programming 1997: Proceedings of the Second Annual Conference (GP97).
J. Koza et al, eds. San Fransisco: Morgan Kaufmann. 240-248.
- Abstract: Show / Hide
-
This paper presents a large and systematic body of data on the relative
effectiveness of mutation, crossover, and combinations of mutation and
crossover in genetic programming (GP). The literature of traditional
genetic algorithms contains related studies, but mutation and crossover in
GP differ from their traditional counterparts in significant ways. In
this paper we present the results from a very large experimental data set,
the equivalent of approximately 12,000 typical runs of a GP system,
systematically exploring a range of parameter settings. The resulting
data may be useful not only for practitioners seeking to optimize
parameters for GP runs, but also for theorists exploring issues such as
the role of "building blocks" in GP.
|
Evolving Teamwork and Coordination with Genetic Programming |
PDF
- Citation:
- Sean Luke and Lee Spector. 1996. Evolving Teamwork and Coordination with Genetic Programming. In Genetic Programming 1996: Proceedings of the First Annual Conference.. J. Koza et al, eds. Cambridge: MIT Press. 141-149.
- Abstract: Show / Hide
- Some problems can be solved only by multi-agent teams. In using genetic
programming to produce such teams, one faces several design decisions.
First, there are questions of team diversity and of breeding strategy.
In one commonly used scheme, teams consist of clones of single individuals;
these individuals breed in the normal way and are cloned to form
teams during fitness evaluation. In contrast, teams could also consist of
distinct individuals. In this case one can either allow free interbreeding
between members of different teams, or one can restrict interbreeding
in various ways. A second design decision concerns the types of
coordination-facilitating mechanisms provided to individual team members;
these range from sensors of various sorts to complex communication systems.
This paper examines three breeding strategies (clones, free, and restricted)
and three coordination mechanisms (none, deictic sensing, and name-based
sensing) for evolving teams of agents in the Serengeti world, a simple
predator/prey environment. Among the conclusions are the fact that
a simple form of restricted interbreeding outperforms free interbreeding
in all teams with distinct individuals, and the fact that name-based
sensing consistently outperforms deictic sensing.
| Cultural Transmission of Information in Genetic Programming |
PDF
- Note:
-
Discussion of this paper appeared as part of the Scientific American (Oct. 96) column "Computing: Programming with Primordial Ooze" (p. 50).
- Citation:
- Lee Spector and Sean Luke. 1996. Cultural Transmission of Information in Genetic Programming. In Genetic Programming 1996: Proceedings of the First Annual Conference.. J. Koza et al, eds. Cambridge: MIT Press. 200-208.
- Abstract: Show / Hide
-
This paper shows how the performance of a genetic programming system
can be improved through the addition of mechanisms for non-genetic
transmission of information between individuals (culture). Teller
has previously shown how genetic programming systems can be enhanced
through the addition of memory mechanisms for individual programs
[Teller 1994]; in this paper we show how Teller's memory mechanism
can be changed to allow for communication between individuals within
and across generations. We show the effects of indexed memory and
culture on the performance of a genetic programming system on a symbolic
regression problem, on Koza's Lawnmower problem, and on Wumpus world
agent problems. We show that culture can reduce
the computational effort required to solve all of these problems.
We conclude with a discussion of possible improvements.
| Culture Enhances the Evolvability of Cognition |
PDF
- Citation:
- Lee Spector and Sean Luke. 1996. Culture Enhances the Evolvability of Cognition. In Cognitive Science 1996 Conference Proceedings (CogSci96).
- Abstract: Show / Hide
- This paper discusses the role of culture in the evolution of cognitive
systems. We define "culture" as any information transmitted between
individuals and between generations by non-genetic means. Experiments
are presented that use genetic programming systems that include special
mechanisms for cultural transmission of information. These systems
evolve computer programs that perform cognitive tasks including mathematical
function mapping and action selection in a virtual world. The data show
that the presence of culture-supporting mechanisms can have a clear
beneficial impact on the evolvability of correct programs. The implications
that these results may have for cognitive science are
briefly discussed.
| Evolving Graphs and Networks with Edge Encoding: Preliminary Report |
PDF
- Citation:
- Sean Luke and Lee Spector. 1996. Evolving Graphs and Networks with Edge encoding: Preliminary Report. In Late Breaking Papers at the Genetic Programming 1996 Conference (GP96). J. Koza, ed. Stanford: Stanford Bookstore. 117-124.
- Abstract: Show / Hide
-
We present an alternative to the cellular encoding
technique for evolving graph and network structures
via genetic programming. The new technique, called
edge encoding, uses edge operators rather than the node operators
of cellular encoding. While both cellular encoding and edge encoding
can produce all possible graphs, the two encodings bias
the genetic search process in different ways; each may therefore be most
useful for a different set of problems. The problems for which
these techniques may be used, and for which we think edge encoding may
be particularly useful, include the evolution of recurrent neural
networks, finite automata, and graph-based queries to symbolic knowledge
bases. In this preliminary report we present a technical description of
edge encoding and an initial comparison to cellular encoding.
Experimental investigation of the relative merits of these encoding
schemes is currently in progress.
| Code Bloat |
A Comparison of Bloat Control Methods for Genetic Programming |
PDF
- Citation:
- Sean Luke and Liviu Panait. 2006. A Comparison of Bloat Control Methods for Genetic Programming. Evolutionary Computation. 14(13):309-344.
- Abstract: Show / Hide
- Genetic programming has highlighted the problem of bloat, the uncontrolled growth of the average size of an individual in the population. The most common approach to dealing with bloat in tree-based genetic programming individuals is to limit their maximal allowed depth. An alternative to depth limiting is to punish individuals in some way based on excess size, and our experiments have shown that the combination of depth limiting with such a punitive method is generally more effective than either alone. Which such combinations are most effective at reducing bloat? In this article we augment depth limiting with nine bloat control methods and compare them with one another. These methods are chosen from past literature and from techniques of our own devising. Testing with four genetic programming problems, we identify where each bloat control method performs well on a per-problem basis, and under what settings various methods are effective independent of problem. We report on the results of these tests, and discover an unexpected winner in the cross-platform category.
| Alternative Bloat Control Methods |
PDF
- Citation:
- Liviu Panait and Sean Luke. 2004. Alternative Bloat Control Methods. In Genetic and Evolutionary Computation Conference (GECCO). Springer. Pages 630-641.
- Abstract: Show / Hide
- Bloat control is an important aspect of evolutionary computation methods, such as genetic programming, which must deal with genomes of arbitrary size. We introduce three new methods for bloat control: Biased Multi-Objective Parsimony Pressure (BMOPP), the Waiting Room, and Death by Size. These methods are unusual approaches to bloat control, and are not only useful in various circumstances, but two of them suggest novel approaches to attack the problem. BMOPP is a more traditional parsimony-pressure style bloat control method, while the other two methods do not consider parsimony as part of the selection process at all, but instead penalize for parsimony at other stages in the evolutionary process. We find parameter settings for BMOPP and the Waiting Room which are effective across all tested problem domains. Death by Size does not appear to have this consistency, but we find it a useful tool as it has particular applicability to steady-state evolution.
| Modification Point Depth and Genome Growth in Genetic Programming |
PDF
- Citation:
- Sean Luke. 2003. Modification Point Depth and Genome Growth in Genetic Programming. Evolutionary Computation. 11(1):67-106.
- Abstract: Show / Hide
- The evolutionary computation community has shown increasing interest in arbitrary-length representations, particularly in the field of genetic programming. A serious stumbling block to the scalability of such representations has been {\it bloat}: uncontrolled genome growth during an evolutionary run. Bloat appears across the evolutionary computation spectrum, but genetic programming has given it by far the largest attention. Most genetic programming models explain this phenomenon as a result of the growth of {\it introns}, areas in an individual which serve no functional purpose. This paper presents evidence which directly contradicts intron theories. The paper then uses data drawn from this evidence to propose a new model of genome growth. In this model, bloat in genetic programming is a function of the mean depth of the modification (crossover or mutation) point. Points far from the root are correspondingly less likely to hurt the child's survivability in the next generation. The modification point is in turn strongly correlated to average parent tree size and to removed subtree size, both of which are directly linked to the size of the resulting child.
| Fighting Bloat With Nonparametric Parsimony Pressure |
PDF
- Citation:
- Sean Luke and Liviu Panait. 2002. Fighting Bloat With Nonparametric Parsimony Pressure. In Parallel Problem Solving from Nature - PPSN VII (LNCS 2439). Juan Julian Merelo Guervos et al, eds. Springer Verlag. 411-421.
- Abstract: Show / Hide
-
Many forms of parsimony pressure are parametric, that is final fitness is a parametric model of the actual size and raw fitness values. The problem with parametric techniques is that they are hard to tune to prevent size from dominating fitness late in the evolutionary run, or to compensate for problem-dependent nonlinearities in the raw fitness function. In this paper we briefly discuss existing bloat-control techniques, then introduce two new kinds of non-parametric parsimony pressure, Direct and Proportional Tournament. As their names suggest, these techniques are based on simple modifications of tournament selection to consider both size and fitness, but not together as a combined parametric equation. We compare the techniques against, and in combination with, the most popular genetic programming bloat-control technique, Koza-style depth limiting, and show that they are effective in limiting size while still maintaining good best-fitness-of-run results.
| Lexicographic Parsimony Pressure |
PDF
- Citation:
- Sean Luke and Liviu Panait. 2002. Lexicographic Parsimony Pressure. In GECCO-2002: Proceedings of the Genetic and Evolutionary Computation Conference. W. B. Langdon et al, eds. Morgan Kauffman. 829-836.
- Abstract: Show / Hide
-
We introduce a technique called lexicographic parsimony pressure, for controlling the significant growth of genetic programming trees during the course of an evolutionary computation run. Lexicographic parsimony pressure modifies selection to prefer smaller trees only when fitnesses are equal (or equal in rank). This technique is simple to implement and is not affected by specific differences in fitness values, but only by their relative ranking. In two experiments we show that lexicographic parsimony pressure reduces tree size while maintaining good fitness values, particularly when coupled with Koza-style maximum tree depth limits.
| Code Growth Is Not Caused By Introns |
PDF
- Citation:
- Sean Luke. 2000. Code growth is not caused by introns. In Late Breaking Papers at the 2000 Genetic and Evolutionary Computation Conference (GECCO-2000). 228-235.
- Abstract: Show / Hide
-
Genetic programming trees have a strong tendency to grow rapidly and relatively independent of fitness, a serious flaw which has received considerable attention in the genetic programming literature. Much of this literature has implicated introns, subtree structures with no effect on the an individual's fitness assessment. The propagation of inviable code, a certain kind of intron, has been especially linked to tree growth. However this paper presents evidence which shows that denying inviable code the opportunity to propagate actually increases tree growth. The paper argues that rather than causing tree growth, a rise in inviable code is in fact an expected result of tree growth. Lastly, this paper proposes a more general theory of growth for which introns are merely a symptom.
| Robotics |
Exploring Planner-guided Swarms Running on Real Robots |
PDF
- Citation:
- Michael Schader and Sean Luke. 2023. Exploring Planner-guided Swarms Running on Real Robots. In International Conference on Practical Applications of Agents and Multi-Agent Systems (PAAMS).
- Abstract: Show / Hide
-
Robot swarms have been proposed as a way to take advantage of the scalability, robustness, and adaptability of natural large-scale multiagent systems in order to solve engineering challenges. However, accomplishing complex tasks while remaining flexible and decentralized has proven elusive. Our prior work on planner-guided robot swarms successfully combined a distributed swarm algorithm implementing low-level behaviors with automated parallel planners and executives selecting high-level actions for the swarm to perform as a whole, but had only been tested in simplistic grid-world simulations. Here we demonstrate our approach on physical robots augmented with experiments in continuous-space simulation, showing that it is an effective and efficient mechanism for achieving difficult task objectives to which swarms are rarely applied.
Retrograde Behavior Mitigation in Planner-Guided Robot Swarms |
PDF
- Citation:
- Michael Schader and Sean Luke. 2022. Retrograde Behavior Mitigation in Planner-Guided Robot Swarms. In International Conference on Practical Applications of Agents and Multi-Agent Systems (PAAMS).
- Abstract: Show / Hide
-
Using an automated planner to guide the behavior of a robot swarm is an effective way to control a decentralized multi-robotic system so that it can accomplish complex tasks. Although classical planning assumes that the actors are unitary agents performing atomic actions, the virtual agents in a planner-guided swarm are groups of individuals. When those individuals have differing beliefs about what step of the plan they are on, so-called retrograde behavior can occur, slowing or stopping progress and potentially causing catastrophic failure. We formally define this issue, explain several approaches to mitigate it, and report the results of experiments in simulation across three different swarm robotics scenarios. We determine that this problem can be solved by combining a plan analyzer with either offline programming changes or some form of additional online coordination, and present a decision tree for choosing the best mitigation method.
Fully Decentralized Planner-Guided Robot Swarms |
PDF
- Citation:
- Michael Schader and Sean Luke. 2021. Fully Decentralized Planner-Guided Robot Swarms. In International Conference on Practical Applications of Agents and Multi-Agent Systems (PAAMS).
- Abstract: Show / Hide
-
Robot swarms hold great potential for accomplishing missions in a robust, scalable, and flexible manner. However, determining what low-level agent behavior to implement in order to meet high-level objectives is an unsolved inverse problem. Building on previous work on partially-centralized planner-guided robot swarms, we present an approach that achieves total decentralization of executive and deliberator functions, adds robustness and performance optimization through dynamic task switching, and employs agent-initiated superrational planning to coordinate agent activity while responding to changes in the environment. We demonstrate the effectiveness of the technique with three swarm robotics scenarios.
| Planner-Guided Robot Swarms |
PDF
- Citation:
- Michael Schader and Sean Luke. 2020. Planner-Guided Robot Swarms. In International Conference on Practical Applications of Agents and Multi-Agent Systems (PAAMS).
- Abstract: Show / Hide
-
Robot swarms have many virtues for large-scale task execution: this includes redundancy, a high degree of parallel task implementation, and the potential to jointly complete jobs that a single agent could not do. But because of their distributed nature, robot swarms face challenges in large-scale coordination, task serialization or ordering, and synchronization. We investigate the use of a central automated planner to guide a robot swarm to perform complicated, multistep operations normally beyond the capabilities of purely decentralized swarms. The planner orchestrates the actions of task groups of agents, while preserving swarm virtues, and can operate over a variety of swarm communication and coordination modalities. We demonstrate the effectiveness of the technique in simulation with three swarm robotics scenarios.
| Portable Sensor Motes as a Distributed Communication Medium for Large Groups of Mobile Robots |
PDF
- Citation:
- Sean Luke and Katherine Russell. 2016. Portable Sensor Motes as a Distributed Communication Medium for Large Groups of Mobile Robots. In NATO Specialists Meeting on Swarm Centric Solution for Intelligent Sensor Networks (SET-222).
- Note:
- This is a short position paper summarizing our past work on using sensor motes as beacons for pheromone robotics.
- Abstract: Show / Hide
-
We argue for the use of swarms of distributed portable sensors as a support medium for a large number of autonomous mobile robots. Because of the scaling issues inherent in their multiplicity, and because they may operate in broadcast-denied environments, swarm robot architectures often focus on local and &lquot;indirect&rquo; communication methods such as breadcrumbs, pheromones, or messages left in the environment. We are interested in how far we can go with these models in real robots. To this end, our research investigates robots capable of deploying, retrieving, moving, and locally communicating with many embedded sensor motes. The mobile agents deploy and optimize the location of the motes, read historic and current sensor data from them, and store useful local information in them for other mobile agents to discover later. We have demonstrated the ability to do robot foraging in environments with significant noise and physical disruption, such as might occur in any deployment of a large sensor network. We have also demonstrated experiments using swarms and sensor motes to collectively build sophisticated, non-trivial swarm behaviors, such as laying out complex shapes using compass/straightedge geometry. In this paper we discuss these results and their limitations, and indicate where we think wireless sensor mote technology can help advance swarm robotics going forward.
| Supporting Mobile Swarm Robotics in Low Power and Lossy Sensor Networks |
PDF
- Citation:
- Kevin Andrea, Robert Simon, and Sean Luke. 2016. Supporting Mobile Swarm Robotics in Low Power and Lossy Sensor Networks. In NATO Specialists Meeting on Swarm Centric Solution for Intelligent Sensor Networks (SET-222).
- Abstract: Show / Hide
-
Wireless low-power and lossy networks (LLNs) are a key enabling technology for the deployment of massively scaled self-organizing sensor swarm systems. Supporting applications such as providing human users situational awareness across large areas requires that swarm-friendly LLNs effectively support communication between embedded and mobile devices, such as autonomous robots. The reason for this is that large scale embedded sensor applications such as unattended ground sensing systems typically do not have full end-to-end connectivity, but suffer frequent communication partitions. Further, it is desirable for many tactical applications to offload tasks to mobile robots. Despite the importance of support this communication pattern, there has been relatively little work in designing and evaluating LLN-friendly protocols capable of supporting such interactions.
This paper addresses the above problem by describing the design, implementation, and evaluation of the MoRoMi system. MoRoMi stands for Mobile Robotic MultI-sink. It is intended to support autonomous mobile robots that interact with embedded sensor swarms engaged in activities such as cooperative target observation, collective map building, and ant foraging. These activities benefit if the swarm can dynamically interact with embedded sensing and actuator systems that provide both local environmental or positional information and an ad-hoc communication system. Our paper quantifies the performance levels that can be expected using current swarm and LLN technologies.
|
Swarm Robot Foraging with Wireless Sensor Motes |
PDF
- Citation:
- Katherine Russell, Michael Schader, Kevin Andrea, and Sean Luke. 2015. Swarm Robot Foraging with Wireless Sensor Motes. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015).
- Abstract: Show / Hide
-
We investigate the use of wireless sensor motes as mobile deployable waypoints for swarm robot navigation in a foraging scenario. Each robot can deploy, retrieve, and optimize the location of the sensor motes. After deployment, the robots treat the sensor motes as nodes in a sparse graph, and store and retrieve multiple pheromones and flags locally in each of them. Pheromone information stored in the sensor motes allows the robots to build up gradients to different targets of interest, and to determine which sensor motes are good candidates to optimize location, or to harvest for reuse elsewhere. Unlike many earlier pheromone-based foraging techniques, our method must deal with the physical reality of deploying and manipulating sensor motes, including a limited mote supply both onboard and in total, robustly dealing with occlusion and interference from other robots, and handling noise and robot or mote failure. We demonstrate the effectiveness of the technique both on differential drive robots of our own design, and in simulation, to examine its ability to robustly deal with various failure modes and changes in environment.
|
Training Heterogeneous Teams of Robots |
PDF
- Citation:
- Keith Sullivan, Ermo Wei, Bill Squires, Drew Wicke, and Sean Luke. 2015. Training Heterogeneous Teams of Robots
In Autonomous Robots and Multibot Systems Workshop (ARMS).
- Abstract: Show / Hide
-
Heterogeneous multi-robot teams are common solutions to complex tasks, especially those that are inherently cooperative. Training robots, rather than coding them, to work together in these teams is an attractive prospect, but is very difficult due to the extremely large state space and the inherent inverse problem which separates the agents’ micro-level behaviors and the desired macro-level emergent phenomenon. We approach this problem with HiTAB, a learning from demonstration system which uses behavior decomposition to allow rapid training of teams with minimal samples. This paper presents and compares two approaches to training teams of heterogenous robots: first, forming a multiagent control hierarchy which scales to large numbers of robots but requires the training of additional virtual controller agents; and second, modifying each robot’s feature space to include information about other robots’ current behaviors or limited internal state.
|
RoboPatriots: George Mason University 2015 RoboCup Team |
PDF
- Citation:
- David Freelan, Drew Wicke, Chris Burns, Carl Walker, Laura Hovatter, Colin Ward, Daniel Lofaro, and Sean Luke. 2015. RoboPatriots: George Mason University 2015 RoboCup Team.
In Proceedings of the 2015 RoboCup Workshop.
- Abstract: Show / Hide
-
The RoboPatriots are a team of four DARwIn-OP robots from George Mason University which participate in the Kid-Size Humanoid League. RoboCup 2015 marks the sixth year of participation for the RoboPatriots. Our approach is very unusual in that our goal is to train our robots how to play cooperative soccer, rather than program them. We do this not at our laboratory, but at the RoboCup venue during the preparatory period. Then, we enter the learned robot behaviors into the competition. In 2014 we trained all three attackers, pairing them with a hard-coded goalie. This year we intend to train a full team of all four robots.
|
Towards Rapid Multi-robot Learning from Demonstration at the RoboCup Competition |
PDF
- Citation:
- David Freelan, Drew Wicke, Keith Sullivan, and Sean Luke. 2014. Towards Rapid Multi-robot Learning from Demonstration at the RoboCup Competition. In Proceedings of the 2014 RoboCup Workshop.
- Abstract: Show / Hide
-
We describe our previous and current efforts towards achieving an unusual personal RoboCup goal: to train a full team of robots directly through demonstration, on the field of play at the RoboCup venue, how to collaboratively play soccer, and then use this trained team in the competition itself. Using our method, HiTAB, we can train teams of collaborative agents via demonstration to perform nontrivial joint behaviors in the form of hierarchical finite-state automata. We discuss HiTAB, our previous efforts in using it in RoboCup 2011 and 2012, recent experimental work, and our current efforts for 2014, then suggest a new RoboCup Technical Challenge problem in learning from demonstration.
|
RoboPatriots: George Mason University 2014 RoboCup Team |
PDF
- Citation:
- David Freelan, Drew Wicke, Chau Thai, Joshua Snider, Anna Papadogiannakis, and Sean Luke. 2014. RoboPatriots: George Mason University 2014 RoboCup Team.
In Proceedings of the 2014 RoboCup Workshop.
- Abstract: Show / Hide
-
The RoboPatriots are a team of four DARwIn-OP robots from George Mason University which participate in the Kid-Size Humanoid League. RoboCup 2014 marks the fifth year of participation for the RoboPatriots: in 2009 and 2010, we advanced to the second round, and in 2011 we were eliminated in the first round. Our approach is unusual in that we aim to train our robots how to play soccer using learning from demonstration, then field those robots in the competition.
|
Real-Time Training of Team Soccer Behaviors |
PDF
- Citation:
- Keith Sullivan and Sean Luke. 2012. Real-Time Training of Team Soccer Behaviors.
In Proceedings of the 2012 RoboCup Workshop.
- Abstract: Show / Hide
-
Training robot or agent behaviors by example is an attractive alternative to directly coding them. However training complex behaviors can be challenging, particularly when it involves interactive behaviors involving multiple agents. We present a novel hierarchical learning from demonstration system which can be used to train both single-agent and scalable cooperative multiagent behaviors. The methodology applies manual task decomposition to break the complex training problem into simpler parts, then solves the problem by iteratively training each part. We discuss our application of this method to multiagent problems in the humanoid RoboCup competition, and apply the technique to the keepaway soccer problem in the RoboCup Soccer Simulator.
|
RoboPatriots: George Mason University 2012 RoboCup Team |
PDF
- Citation:
- Keith Sullivan, Katherine Russell, Kevin Andrea, Barak Stout, and Sean Luke. 2012. RoboPatriots: George Mason University 2012 RoboCup Team.
In Proceedings of the 2012 RoboCup Workshop.
- Abstract: Show / Hide
-
The RoboPatriots from George Mason University are a team of three humanoid robots. As we are interested in embodied AI, our robots are based on commercially available equipment. We use the three on-board computers for research into learning from demonstration, a supervised machine learning technique for training robot behavior. RoboCup 2012 marks the fourth year of participation for the RoboPatriots: in 2009 and 2010, we advanced to the second round, and in 2011 we were eliminated in the first round.
|
Learning from Demonstration with Swarm Hierarchies |
PDF
- Citation:
- Keith Sullivan and Sean Luke. 2012. Learning from Demonstration with Swarm Hierarchies.
In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
- Abstract: Show / Hide
-
We present a supervised learning from demonstration system capable of training stateful and recurrent collective behaviors for multiple agents or robots. A model space of this kind is often high-dimensional and consequently may require a large number of samples to learn. Furthermore, the inverse problem posed by emergent macrophenomena among multiple agents presents major challenges to supervised learning methods. Our approach reduces the size of the state space, and shortens the gap between individual behaviors and macrophenomena, by manually decomposing individual behaviors and arranging the agents into a tree hierarchy. This makes it possible to train potentially large numbers of agents using a small number of samples. We demonstrate our system using hundreds of agents in a simulated foraging task, and on real robots performing a collective patrolling task.
|
RoboPatriots: George Mason University 2011 RoboCup Team |
PDF
- Citation:
- Keith Sullivan, Christopher Vo, and Sean Luke. 2011. RoboPatriots: George Mason University 2011 RoboCup Team
In Proceedings of the 2011 RoboCup Workshop.
- Abstract: Show / Hide
-
The RoboPatriots are a team of three humanoid robots designed by the Computer Science Department at George Mason University. Each robot is based on the Kondo KHR-3HV, a customized Surveyor SVS camera, and a Gumstix embedded computer (see Figure 1(a)).
|
Hierarchical Learning from Demonstration on Humanoid Robots |
PDF
- Citation:
- Keith Sullivan, Sean Luke, and Vittorio Ziparo. 2010. Hierarchical Learning from Demonstration on Humanoid Robots. In Proceedings of the Humanoid Robots Learning from Interaction Workshop, at Humanoids 2010.
- Abstract: Show / Hide
-
Developing behaviors for humanoid robots is difficult due to the high complexity of programming these robots, which includes repeated trial and error cycles. We have recently developed a learning from demonstration system capable of training agent behaviors from a small number of training examples. Our system represents a complex behavior as a hierarchical finite automaton, permitting decomposition of the behavior into simple, easier-to-train sub-behaviors. The system was originally designed for swarms of virtual agents, but based on recent Robocup experience, we have ported the system to our humanoid robot platform. We discuss the system and the platform, and preliminary experiments involving both novice and expert users in a stateful visual servoing task.
|
RoboPatriots: George Mason University 2010 RoboCup Team |
PDF
- Citation:
- Keith Sullivan, Christopher Vo, Sean Luke, and Jyh-Ming Lien. 2010. RoboPatriots: George Mason University 2010 RoboCup Team
In Proceedings of the 2010 RoboCup Workshop.
- Abstract: Show / Hide
-
The RoboPatriots are a team of three humanoid robots sponsored by the Computer Science Department at George Mason University. Each robot is based on the Kondo KHR-3HV and a customized Surveyor SVS camera.
|
Learn to Behave! Rapid Training of Behavior Automata |
PDF
- Citation:
- Sean Luke and Vittorio Ziparo. 2010. Learn to Behave! Rapid Training of Behavior Automata. In Proceedings of the Adaptive and Learning Agents Workshop at AAMAS 2010. Marek Grześ and Matthew Taylor, editors. 61–68.
- Abstract: Show / Hide
-
Programming robot or virtual agent behaviors can be a challenging task, and makes attractive the prospect of automatically learning the behaviors from the actions of a human demonstrator. However, learning complex behaviors rapidly from a demonstrator may be difficult if they demand a large number of training samples. We describe an architecture for rapid learning of recurrent behaviors from demonstration. The architecture is based on deterministic hierarchical finite-state automata (HFAs) with classification algorithms taking the place of the state transition function. This architecture allows for task decomposition, statefulness, parameterized features and behaviors, per-behavior feature set customization, and storage of learned behaviors in libraries to be used later on as elements in more complex behaviors. We describe the system, then illustrate its application in a simple, but nontrivial, foraging task involving multiple behaviors.
| RoboPatriots: George Mason University 2009 RoboCup Team |
PDF
- Citation:
- Keith Sullivan, Brian Davidson, Christopher Vo, Brian Hrolenok, and Sean Luke. 2009. RoboPatriots: George Mason University 2009 RoboCup Team. In Proceedings of the 2009 RoboCup Workshop.
- Abstract: Show / Hide
-
The RoboPatriots are a team of three humanoid robots sponsored by George
Mason University. Each robot is built on a Kondo KHR-1HV humanoid base and
a customized Gumstix Verdex microcontroller. The two attackers share the same
behavior, and the goalie's is different. At present there is minimal communication
between the robots, but this may change by the competition.
RoboCup 2009 provides an opportunity for the Autonomous Robotics Lab
at George Mason University to apply its expertise in evolutionary algorithms
to robotics. Our research goals in developing the RoboPatriots have focused on
three elements: first, we are interested in the multiagent coordination aspects of
the problem. Second, we are simplifying the design of robot motion behaviors by
gathering human motion data, then converting this data to the humanoid servos.
Third, we are optimizing these motion behaviors in a massively distributed evo-
lutionary computation system attached to a custom humanoid robot simulator
of our own devising.
| RoboPatriots: George Mason University 2008 RoboCup Team |
PDF
- Citation:
- Keith Sullivan, Brian Davidson, Christopher Vo, Brian Hrolenok, and Sean Luke. 2008. RoboPatriots: George Mason University 2008 RoboCup Team. In Proceedings of the 2008 RoboCup Workshop.
- Abstract: Show / Hide
-
The Autonomous Robotics Laboratory was established at George Mason University in 2006 with the goal of collaborative research in robotics, multiagent
systems, computer vision, and sensor networks. While our previous work has
focused on differential drive robots, RoboCup 2008 represents our fist major effort with humanoid robots. The goal this year is modest: construct and program
a working team for RoboCup. Our primary focus is developing a basic hardware
and software platform to base future research initiatives on.
RoboPatriots has three robots: two attackers and one goalie. All three have
the same hardware. The two attackers have one behavior mechanism, and the
goalie has a different behavior mechanism. Presently, there is no communication
between the robots, but that may change prior to the competition.
| Three RoboCup Simulation League Commentator Systems |
PDF
- Citation:
- E. Elisabeth Andre, Kim Binsted, Kumiko Tanaka-Ishii, Sean Luke, Gerd Herzog, and Thomas Rist. 2000. Three RoboCup simulation league commentator systems. In AI Magazine, 21:1 (Spring 2000), 57-66. AAAI.
- Abstract: Show / Hide
-
Three systems which generate real-time natural language commentary on the RoboCup simulation league are presented, and their similarities, differences, and directions for the future discussed. Although they emphasize different aspects of the commentary problem, all three systems take simulator data as input, and generate appropriate, expressive, spoken commentary in real time.
| Character Design for Soccer Commentary |
PDF
- Citation:
- Kim Binsted and Sean Luke. 1998. Character design
for soccer commentary. In Robot Soccer World Cup II: Proceedings
of the second RoboCup Workshop, H. Kitano, ed. 23-35. Springer-Verlag.
- Abstract: Show / Hide
-
In this paper we present early work on an animated talking head
commentary system called Byrne. The goal of this project is to
develop a system which can take the output from the RoboCup soccer
simulator, and generate appropriate affective speech and facial
expressions, based on the character's personality, emotional state,
and the state of play. Here we describe a system which takes
pre-analysed simulator output as input, and which generates text
marked-up for use by a speech generator and a face animation
system. We make heavy use of inter-system standards, so that future
versions of Byrne will be able to take advantage of advances in the
technologies that it incorporates.
|
Genetic Programming Produced Competitive Soccer Softbot Teams for RoboCup97 |
PDF
- Note:
-
This paper is similar to an earlier workshop paper.
The key difference being that the workshop paper, which was not for a
Genetic Programming audience, is short on experimental details and long
on introductions to how GP works. There also exists a
short invited paper
detailing how this experiment could have been improved.
Also available is a short sidebar
for an AI Magazine article.
- Citation:
- Sean Luke. 1998. Genetic Programming Produced Competitive Soccer Softbot Teams for RoboCup97. In Proceedings of the Third Annual Genetic Programming Conference (GP98). J. Koza et al, eds. 204-222. San Fransisco: Morgan Kaufmann.
- Abstract: Show / Hide
-
At RoboCup, teams of autonomous robots or software softbots compete in
simulated soccer matches to demonstrate cooperative robotics techniques in
a very difficult, real-time, noisy environment. At the IJCAI/RoboCup97
softbot competition, all entries but ours used human-crafted cooperative
decision-making behaviors. We instead entered a softbot team whose
high-level decision making behaviors had been entirely evolved using
genetic programming. Our team won its first two games against
human-crafted opponent teams, and received the RoboCup Scientific
Challenge Award. This report discusses the issues we faced and the
approach we took to use GP to evolve our robot soccer team for this
difficult environment.
| Evolving SoccerBots: A Retrospective |
PDF
- Note:
- This short invited paper was meant to complement the more complete GP98 and RoboCup97 papers, and an AI Magazine sidebar, by discussing things that could have been improved from our previous attempt.
- Citation:
- Sean Luke. 1998. Evolving soccerbots: a retrospective. In Proceedings of 12th Annual Conference of the Japanese Society for Artificial Intelligence (JSAI).
- Abstract: Show / Hide
-
In the RoboCup97 robot soccer tournament, we entered a team of softbot programs whose player strategies had been entirely learned by computer. Our team beat other human-coded competitors and received the RoboCup97 Scientific Challenge award. This paper discusses our approach, and details various ways that, in retrospect, it could have been improved.
| Co-evolving Soccer Softbot Team Coordination with Genetic Programming |
PDF
- Note:
- Also available is a short sidebar for an AI Magazine article. There also exists a similar paper written for GP97 which discusses more of the project implementation details but spends little time explaining what Genetic Programming is and how it works. And finally, there exists a short invited paper detailing how this experiment could have been improved.
- Citation:
- Luke, Charles Hohn, Jonathan Farris, Gary Jackson, and James Hendler. 1998. Co-evolving Soccer Softbot Team Coordination with Genetic Programming. In RoboCup-97: Robot Soccer World Cup I (Lecture Notes in Artificial Intelligence No. 1395), H. Kitano, ed. Berlin: Springer-Verlag. 398-411.
- Abstract: Show / Hide
-
Genetic Programming is a promising new method for automatically generating functions and algorithms through natural selection. In contrast to other learning methods, Genetic Programming's automatic programming makes it a natural approach for developing algorithmic robot behaviors. In this paper we present an overview of how we apply Genetic Programming to behavior-based team coordination in the RoboCup Soccer Server domain. The result is not just a hand-coded soccer algorithm, but a team of softbots which have learned on their own how to play a reasonable game of soccer.
| Coevolving Soccer Softbots |
PDF
- Note:
- This is a short sidebar about the RoboCup project. A more complete paper can be found here.
- Citation:
- Sean Luke. 1998. Coevolving Soccer Softbots. In AI Magazine 19:3 (Fall 1998), pp. 54.
- First Paragraph: Show / Hide
-
The University of Maryland RoboCup simulator entry (Sean Luke, Charles hohn, Jonathan Farris, Gary Jackson, and James Hendler) consisted entirely of computer-evolved players developed with Genetic Programming. Genetic Programming is a branch of evolutionary computation which uses natural selection to optimize over the space of computer algorithms. Unlike other entrants who fashioned fine-tuned softbot teams from a battery of relatively well-understood robotics techniques, maryland's goal was to see if it was even possible to use evolutionary computation to develop high-level soccer behaviors that were competitive with the human-crafted strategies of other teams. While evolutionary computation has been successful in many fields, evolving a computer algorithm has proven challenging, especially in a domain like robot soccer.
| Biological Modeling |
| Evolutionary Computation and the C-value Paradox |
PDF
- Citation:
- Sean Luke. 2005. Evolutionary Computation and the C-value Paradox. In Proceedings of the 2005 Genetic and Evolutionary Computation Conference (GECCO). Pages 91-97.
- Abstract: Show / Hide
- The C-value Paradox is the name given in biology to the wide variance in and often very large amount of DNA in eukaryotic genomes and the poor correlation between DNA length and perceived organism complexity. Several hypotheses exist which purport to explain the Paradox. Surprisingly there is a related phenomenon in evolutionary computation, known as code bloat, for which a different set of hypotheses has arisen. This paper describes a new hypothesis for the Cvalue Paradox derived from models of code bloat. The new explanation is that there is a selective bias in preference of genetic events which increase DNA material over those which decrease it. The paper suggests one possible concrete mechanism by which this may occur: deleting strands of DNA is more likely to damage genomic material than migrating or copying strands. The paper also discusses other hypotheses in biology and in evolutionary computation, and provides a simulation example as a proof of concept.
| The Perfect C. elegans Project: An Initial Report |
PDF
- Citation:
- Hiroaki Kitano, Shugo Hamahashi, and Sean Luke. 1998. The perfect C. elegans project: an initial report. In Artificial Life, 4:2 (Spring 1998), 141-156. MIT Press.
- Abstract: Show / Hide
-
The soil nematode Caenorhabditis Elegans (C. elegans) is the most investigated of all multi-cellular organisms. Since the proposal to use it as a model organism, a series of research projects have been undertaken, investigating a wide range of on various aspects of this organism. As a result, the complete cell lineage, neural circuitry, and various genes and their functions have been identified. The complete C. elegans DNA sequencing and gene expression mapping for each cell at different times during embryogenesis will be identified in a few years. Given the abundance of collected data, we believe that the time is ripe to introduce synthetic models of C. elegans to further enhance our understanding of the underlying principles of its development and behavior. For this reason, we have started the Perfect C. elegans Project, which aims to ultimately produce a complete synthetic model of C. elegans cellular structure and function. This paper describes the goal, the approach, and the initial results of the project.
| Biology: See It Again — for the First Time |
PDF
- Citation:
- Sean Luke, Shugo Hamahashi, Koji Kyoda, and Hiroki Ueda. 1998. Biology: See It Again—for the First Time. In IEEE Intelligent Systems. 13:5 (September/October 1998). 6-8.
-
First Paragraph: Show / Hide
-
Computer science owes a huge debt to biological systems. The field itself came about largely as an attempt to understand and replicate the function and abilities of the brain, a complex biological creation. From this early lineage has sprung many subfields derived largely from biological metaphors: computer vision, neural networks, evolutionary computation, robotics, multi-agent studies, and much of artificial intelligence. In some areas, the computer has bested its biological counterparts in efficiency and simplicity. But for many domains, even after decades of hard work, the biological "real thing" is still superior to the artificial algorithms inspired by it.
| Knowledge Representation |
| SHOE: A Blueprint for the Semantic Web |
PDF
- Citation:
- Jeff Heflin, James Hendler, and Sean Luke. 2003. SHOE: A Blueprint for the Semantic Web. In Dieter Fensel, James Hendler, Henry Lieberman, and Wolfgang Wahlster, editors, Spinning the Semantic Web: Bringing the World Wide Web to Its Full Potential. Pages 29-64. MIT Press.
- Abstract: Show / Hide
- The term Semantic Web was coined by Tim Berners-Lee to describe his proposal for a "web of meaning" as opposed to a "web of links" that currently exists on the Internet. To achieve this vision, we need to develop languages and tools that enable machine understandable web pages. The SHOE project, begun in 1995, was one of the first efforts to explore these issues. In this paper, we describe our experiences developing and using the SHOE language. We begin by describing the unique features of the World Wide Web and how they must influence potential Semantic Web languages. Then we present SHOE, a language which allows web pages to be annotated with semantics, describe its syntax and semantics, and discuss our approaches to handling the problems of interoperability in distributed environments and ontology evolution. Finally, we provide an overview of a suite of toolls for the Semantic Web, and discuss the application of the language and tools to two different domains.
| Coping with Changing Ontologies in a Distributed Environment |
PDF
- Citation:
- Jeff Heflin, James Hendler, and Sean Luke. 1999. Coping with Changing Ontologies in a Distributed Environment. Ontology Management. Papers from the AAAI Workshop. WS-99-13. AAAI Press. pp. 74-79.
- Abstract: Show / Hide
-
We discuss the problems associated with versioning ontologies in distributed environments. This is an important issue because ontologies can be of great use in structuring and querying internet information, but many of the Internet's characteristics, such as distributed ownership, rapid evolution, and heterogeneity, make ontology management difficult. We present a scheme for classifying ontology revisions based upon the effect these changes would have on the data sources that reference the ontology. We also discuss how to manage these changes, especially when they are the result of integrating ontologies. Finally, we describe the simple elements of SHOE, a web-based knowledge representation language, that allow us to revise shared ontologies while maintaining consistency with web pages that already reference them.
| Applying Ontology to the Web: A Case Study |
PDF
- Citation:
- Jeff Heflin, James Hendler, and Sean Luke. 1999. Applying Ontology to the Web: A Case Study. In J. Mira, J. Sanchez-Andres (Eds.), International Work-Conference on Artificial and Natural Neural Networks (IWANN). Vol 2. Springer, Berlin. pp. 715-724.
- Abstract: Show / Hide
-
This paper describes the use of Simple HTML Ontology Extensions (SHOE) in a real world internet application. SHOE allows authors to add semantic content to web pages and to relate this content to common ontologies that provide contextual information about the domain. Using this information, query systems can provide more accurate responses than are possible with the search engines available on the Web. We have applied these techniques to the domain of Transmissible Spongiform Encephalopathies (TSEs), a class of diseases that include "Mad Cow Disease". We discuss our experiences and provide lessons learned from the process.
| SHOE: A Knowledge Representation Language for Internet Applications |
PDF
- Note:
- A revised version of this paper formed Chapter 2 ("SHOE: A Blueprint for the Semantic Web") of the book Spinning the Semantic Web, edited by Dieter Fensel, James Hendler, Henry Lieberman, and Wolfgang Wahlster. MIT Press. 2003. ISBN 0-262-06232-1
- Also Available As:
- UMCP-CSD Technical Report CS-TR-4078, or UMCP-UMIACS Technical Report UMIACS-TR-99-71, accessible online at the Library of the Department of Computer Science, University of Maryland at College Park.
- Citation:
- Jeff Heflin, James Hendler, and Sean Luke. 1999. SHOE: A Knowledge Representation Language for Internet Applications. Technical Report CS-TR-4078. Department of Computer Science, University of Maryland at College Park.
- Abstract: Show / Hide
-
It is our contention that the World Wide Web poses challenges to knowledge representation systems that fundamentally change the way we should design KR languages. In this paper, we describe the simple HTML Ontology Extensions (SHOE), a KR language which allows web pages to be annotated with semantics. We present a formalism for the language and discuss the features which make it well suited for the Web. We describe the syntax and semantics of this language, and discuss the differences from traditional KR systems that make it more suited to modern web applications. We also describe some generic tools for using the language and demonstrate its capabilities by describing two prototype systems that use it. We also discuss some future tools currently being developed for the language. The language, tools, and details of the applications are all available on the World Wide Web at http://www.cs.umd.edu/projects/plus/SHOE/
| Reading Between the Lines: Using SHOE to Discover Implicit Knowledge from the Web |
PDF
- Citation:
- Jeff Heflin, James Hendler, and Sean Luke. 1998. Reading between the lines: using SHOE to discover implicit knowledge from the web. In AI and Information Integration, Papers from the 1998 Workshop. (WS-98-14). AAAI Press. 51-57.
- Abstract: Show / Hide
-
This paper describes how SHOE, a set of Simple HTML Ontological Extensions, can be used to discover implicit knowledge from the World-Wide Wide Web (WWW). SHOE allows authors to annotate their pages with ontology-based knowledge about page contents. In previous papers, we discussed how the semantic knowledge provided by SHOE allows users to issue queries that are much more sophisticated than keyword search techniques, including queries that require retrieval of information from many sources. Here, we expand upon this idea by describing how SHOE's ontologies allow agents to understand more than what is explicitly stated in Web pages through the use of context, inheritance an dinference. We use examples to illustrate the usefulness of these features to Web agents and query engines.
| Web Agents That Work |
PDF
- Note:
- This article covers similar issues as the paper, Ontology-based Web Agents.
- Citation:
- Sean Luke and James Hendler. 1997. Web Agents That Work. In IEEE Multimedia. 4:3 (July-September 1997). IEEE Press. 76-80.
- First Paragraph: Show / Hide
-
There are two kinds of information-seekers currently wandering the World-Wide Web. First there are us humans, the web-surfers for whom the Web was designed. Second, there are increasing numbers of automated systems, Web agents, which gather information from the Web on our behalf. At the present time, humans far outnumber web agents, but this could soon change: as the sheer volume of information on the Web increases,and the ratio of junk to useful information continues to grow, we will increasingly rely on agents to dig through all that muck to find our gems for us.
| Ontology-based Web Agents |
PDF
- Citation:
- Sean Luke, Lee Spector, David Rager, and James Hendler. 1997. Ontology-based Web Agents. In Proceedings of the First International Conference on Autonomous Agents (AutonomousAgents97). W. L. Johnson, ed. New York: Association for Computing Machinery. 59-66.
- Abstract: Show / Hide
- This paper describes SHOE, a set of Simple HTML Ontology Extensions which
allow World-Wide Web authors to annotate their pages with semantic
knowledge such as "I am a graduate student" or "This person is my graduate advisor". These annotations are expressed in terms of ontological knowledge which can be generated by using or extending standard ontologies available on the Web. This makes it possible to ask Web agent queries such as "Find me all graduate students in Maryland who are working on a project funded by DoD initiative 123-4567", instead of simplistic keyword searches enabled by current search engines. We have also developed a web-crawling agent, Exposée, which interns SHOE knowledge from web documents, making these kinds queries a reality.
| Ontology-Based Knowledge Discovery on the World-Wide Web |
PDF
- Note:
- This paper has been superceeded by Ontology-based Web Agents
- Citation:
- Luke, Lee Spector, and David Rager. 1996. Ontology-Based Knowledge Discovery on the World-Wide Web. In Working Notes of the Workshop on Internet-Based Information Systems at the 13th National Conference on Artificial Intelligence (AAAI96). A. Franz and H. Kitano, eds. AAAI. 96-102.
- Abstract: Show / Hide
-
This paper describes SHOE, a set of Simple HTML Ontology Extensions. SHOE allows World-Wide Web authors to annotate their pages with ontology-based knowledge about page contents. We present examples showing how the use of SHOE can support a new generation of knowledge-based search and knowledge discovery tools that operate on the World-Wide Web.
| Using the Parka Parallel Knowledge Representation System (Version 3.2) |
PDF
- Also Available As:
- UMCP-CSD Technical Report CS-TR-3485, accessible online at the Library of the Department of Computer Science, University of Maryland at College Park.
- Citation:
- William Anderson, Brian Kettler, Sean Luke, and James Hendler. 1995. Using the Parka Parallel Knowledge Representation System (Version 3.2). Technical Report. Department of Computer Science, University of Maryland at College Park.
- Abstract: Show / Hide
- Parka is a symbolic, semantic network knowledge representation system that takes advantage of the massive parallelism of supercomputers such as the Connection Machine. The Parka language has many of the features of traditional semantic net/frame-based knowledge representation languages but also supports several kinds of rapid parallel inference mechanisms that scale to large knowledge-bases of hundreds of thousands of frames or more. Parka is intended for general-purpose use and has been used thus far to support A.I. systems for case-based reasoning and data mining. This document is a user manual for the current version of Parka, version 3.2. It describes the Parka language and presents some examples of knowledge representation using Parka. Details about the parallel algorithms, implementation, and empirical results are presented elsewhere.
| Dissertation |
Issues in Scaling Genetic Programming: Breeding Strategies, Tree Generation, and Code Bloat |
(Recommended) Double-Sided Version in PDF
Single-Sided Version in PDF
- Citation:
- Sean Luke. 2000. Issues in Scaling Genetic Programming: Breeding Strategies, Tree Generation, and Code Bloat. Ph.D. Dissertation, Department of Computer Science, University of Maryland, College Park, Maryland.
- Abstract: Show / Hide
- Genetic Programming is an evolutionary computation technique which searches for those computer programs that best solve a given problem. As genetic programming is applied to increasingly difficult problems, its effectiveness is hampered by the tendency of candidate program solutions to grow in size independent of any corresponding increases in quality. This bloat in solutions slows the search process, interferes with genetic programming's searching, and ultimately consumes all available memory. The challenge for scaling up genetic programming is to find the best solutions possible before bloat puts a stop to evolution. This can be tackled either by finding better solutions more rapidly, or by taking measures to delay bloat as long as possible.
This thesis discusses issues both in speeding the search process and in delaying bloat in order to scale genetic programming to tackle harder problems. It describes evolutionary computation and genetic programming, and details the application of genetic programming to cooperative robot soccer and to language induction. The thesis then compares genetic programming breeding strategies, showing the conditions under which each strategy produces better individuals with less bloating. It then analyzes the tree growth properties of the standard tree generation algorithms used, and proposes new, fast algorithms which give the user better control over tree size. Lastly, it presents evidence which directly contradicts existing bloat theories, and gives a more general theory of code growth, showing that the issue is more complicated than it first appears.
- Errata:
-
- In Algorithm 2 (p. 6), the line P<-P\{q} should read P<-P\{s}
- Figures 5.2 through 5.5 (p. 38-39) are not in proper evolutionary-time order. The proper order is 5.4, 5.5, 5.2, 5.3.
|
| |
|
Sean Luke
|