Learning Strategic Behavior in Sequential Decision Tasks
Active from 2009 - 2014
Many routine tasks in the real world can be seen as sequential decision tasks. For instance, navigating a robot through a complex environment, driving a car in congested traffic, and routing packets in a computer network requires making a sequence of decisions that together minimize time and resources used. It would be desirable to automate these tasks, yet it is difficult because the optimal decisions are generally not known. Approximating them by finite-state machines or learning them based on reinforcement leads to reactive behaviors that perform well in short term, but do not amount to intelligent high-level behavior in the long term. The goal of this project is to develop the technology that makes learning such strategic high-level behavior possible.

The main technical challenge is to devise a method that extends sequential decision learning from reactive to strategic behaviors. Such a method needs to be able to (1) retain information from past states, (2) learn multimodal behavior, (3) choose between the different behaviors based on crucial detail, and (4) implement a sequential high-level strategy based on those behaviors. The neuroevolution methods developed in prior work solve the first problem by evolving (through genetic algorithms) recurrent neural networks to represent the behavior. To solve the remaining problems, these methods will be extended with multi-objective optimization, local nodes with cascaded structure, and with evolution of modules and their combinations. Preliminary results indicate that this approach is indeed feasible. In this project, it will be first characterized fully in supervised learning tasks as well as in synthetic sequential decision tasks. It will then be scaled up to a robotic soccer simulation in OpenNERO, and evaluated in two ways: In an objective comparison with other hand-coded and learned soccer teams, and through a subjective analysis (by human evaluators) of the learned strategies. The end result will be a systematic approach to learning strategic high-level behavior in sequential decision tasks.

In the long term, the technology should make it possible to build robust sequential decision systems for real-world tasks. It should lead to safer and more efficient vehicle, traffic, and robot control, improved process and manufacturing optimization, and more efficient computer and communication systems. It should also make the next generation of video games possible, with characters that exhibit realistic, strategic behaviors: Such technology should lead to more effective educational and training games in the future.

This research is supported by the National Science Foundation under grant IIS-0915038.

Also show archived content
     [Expand to show all 22][Minimize]
Risto Miikkulainen Faculty risto [at] cs utexas edu
Jacob Schrum Ph.D. Alumni schrum2 [at] cs utexas edu
Nate Kohl Ph.D. Alumni nate [at] natekohl net
Vinod Valsalam Ph.D. Alumni vkv [at] alumni utexas net
Chern Han Yong Masters Alumni cherny [at] nus edu sg
Padmini Rajagopalan Ph.D. Student padmini [at] cs utexas edu
Aditya Rawal Ph.D. Student aditya [at] cs utexas edu
Bryan Silverthorn Ph.D. Alumni bsilvert [at] cs utexas edu
Alan J. Lockett Ph.D. Alumni alan lockett [at] gmail com
Igor V. Karpov Ph.D. Student ikarpov [at] gmail com
Adam C. Dziuk Undergraduate Alumni
Chris Bush Undergraduate Alumni
Matthew Johnston Undergraduate Alumni
Timothy Nodine Undergraduate Alumni
David Robson Undergraduate Alumni
Eliana Feasley Former Ph.D. Student elie [at] cs utexas edu
Wesley Tansey Ph.D. Student tansey [at] cs utexas edu
Anand Subramoney Masters Alumni anands [at] cs utexas edu
Dan Lessin Ph.D. Student dlessin [at] cs utexas edu
Joel Lehman Postdoctoral Fellow joel [at] cs utexas edu
Julian Bishop Ph.D. Student julian [at] cs utexas edu
Matthew de Wet Undergraduate Alumni
     [Expand to show all 20][Minimize]
Multimodal Behavior in Imprison Ms. Pac-ManJacob Schrum2014
Multimodal Behavior in Multiple Lives Ms. Pac-ManJacob Schrum2014
Multimodal Behavior in One Life Ms. Pac-ManJacob Schrum2014
Trading Control Intelligence for Physical Intelligence: Muscle Drives in Evolved Virtual CreaturesDan Lessin, Don Fussell, Risto Miikkulainen2014
A Neuroevolution Approach to General Atari Game PlayingMatthew Hausknecht2013
Open-Ended Behavioral Complexity for Evolved Virtual CreaturesDan Lessin, Don Fussell, Risto Miikkulainen2013
Egalitarian Social Learning (ESL) in Robot ForagingWesley Tansey2012
Evolution of a Communication Code in Cooperative TasksAditya Rawal, Padmini Rajagopalan, Risto Miikkulainen, Kay Holekamp2012
UT^2: Winner of 2012 BotPrize in Unreal Tournament 2004Jacob Schrum, Igor Karpov2012
Evolving Controllers for Physical Multilegged RobotsVinod Valsalam2011
Multi-modal Approaches to Evolving Behavior for Multi-task GamesJacob Schrum2011
The Role of Reward Structure, Coordination Mechanism and Net Return in the Evolution of CooperationPadmini Rajagopalan, Aditya Rawal2011
Emergence of Competitive and Cooperative Behavior and Arms Race Through CoevolutionAditya Rawal, Padmini Rajagopalan2010
Evolving Controller Symmetry for Multilegged RobotsVinod Valsalam2010
Fitness-based Shaping in Multi-objective DomainsJacob Schrum2010
Learning in Fractured DomainsNate Kohl2009
Multi-modal Behavior in NPCsJacob Schrum2009
Modular Neuroevolution for Multilegged LocomotionVinod Valsalam2008
Multi-objective Neuroevolution of NPCsJacob Schrum2008
Evolving Cooperation in Multiagent SystemsChern Yong2007
     [Expand to show all 50][Minimize]
A Measure-Theoretic Analysis of Stochastic Optimization Alan J. Lockett and Risto Miikkulainen In Proceedings of the 12th International Workshop on Foundations of Genetic Algorithms (FOGA-2013... 2013

A Neuroevolution Approach to General Atari Game Playing Matthew Hausknecht and Joel Lehman and Risto Miikkulainen and Peter Stone In IEEE Transactions on Computational Intelligence and AI in Games, 2013. 2013

Boosting Interactive Evolution using Human Computation Markets Joel Lehman and Risto Miikkulainen To Appear In Proceedings of the 2nd International Conference on the Theory and Practice of Natura... 2013

Effective Diversity Maintenance in Deceptive Domains Joel Lehman, Kenneth O. Stanley and Risto Miikkulainen To Appear In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2013,... 2013

Evolutionary Annealing: Global Optimization in Arbitrary Measure Spaces Alan J Lockett and Risto Miikkulainen Journal of Global Optimization:1--34, April 2013. 2013

Measure-Theoretic Analysis of Performance in Evolutionary Algorithms Alan J Lockett In Proceedings of the 2013 IEEE Congress on Evolutionary Computation (CEC-2013), 2013. IEEE P... 2013

Neuroannealing: Martingale-Driven Optimization for Neural Networks Alan J Lockett and Risto Miikkulainen In Proceedings of the 2013 Genetic and Evolutionary Computation Conference (GECCO-2013), 2013... 2013

Neuroevolution Joel Lehman and Risto Miikkulainen Scholarpedia, 8(6):30977, 2013. 2013

Open-Ended Behavioral Complexity for Evolved Virtual Creatures Dan Lessin, Don Fussell, Risto Miikkulainen In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2013, 2013. 2013

Using Symmetry and Evolutionary Search to Minimize Sorting Networks Vinod K. Valsalam and Risto Miikkulainen Journal of Machine Learning Research, 14(Feb):303--331, 2013. 2013

Accelerating Evolution via Egalitarian Social Learning Wesley Tansey, Eliana Feasley, and Risto Miikkulainen In Proceedings of the 14th Annual Genetic and Evolutionary Computation Conference (GECCO 2012) 2012

Architecture of a Cyberphysical Avatar Song Han, Aloysius K. Mok, Jianyong Meng, Yi-Hung Wei, Pei-Chi Huang, Xiuming Zhu, Luis Sentis, Kan ... In Proceedings of the International Workshop on Real-Time and Distributed Computing in Emerging A... 2012

Believable Bot Navigation via Playback of Human Traces Igor V. Karpov, Jacob Schrum, Risto Miikkulainen In Philip F. Hingston, editors, Believable Bots, 151--170, 2012. Springer Berlin Heidelberg. 2012

Constructing Controllers for Physical Multilegged Robots using the ENSO Neuroevolution Approach Vinod K. Valsalam, Jonathan Hiller, Robert MacCurdy, Hod Lipson and Risto Miikkulainen Evolutionary Intelligence, 5(1):1--12, 2012. 2012

Evaluating Modular Neuroevolution in Robotic Keepaway Soccer Anand Subramoney Masters Thesis, Department of Computer Science, The University of Texas at Austin, Austin, TX, 2012.... 2012

Evaluation Methods for Active Human-Guided Neuroevolution in Games Igor Karpov, Leif Johnson, Vinod Valsalam and Risto Miikkulainen In 2012 AAAI Fall Symposium on Robots Learning Interactively from Human Teachers (RLIHT), Nov... 2012

Evolution of a Communication Code in Cooperative Tasks Aditya Rawal, Padmini Rajagopalan, Risto Miikkulainen and Kay Holekamp In Artificial Life (13th International Conference on the Synthesis and Simulation of Living Syste... 2012

Evolving Multimodal Networks for Multitask Games Jacob Schrum and Risto Miikkulainen IEEE Transactions on Computational Intelligence and AI in Games, 4(2):94--111, June 2012. IEE... 2012

General-Purpose Optimization Through Information-Maximization Alan J Lockett PhD Thesis, Department of Computer Sciences, The University of Texas at Austin, 2012. Tech Report AI... 2012

Humanlike Combat Behavior via Multiobjective Neuroevolution Jacob Schrum, Igor V. Karpov and Risto Miikkulainen In Philip F. Hingston, editors, Believable Bots, 119--150, 2012. Springer Berlin Heidelberg. 2012

HyperNEAT-GGP: A HyperNEAT-based Atari General Game Player Matthew Hausknecht, Piyush Khandelwal, Risto Miikkulainen, Peter Stone In Genetic and Evolutionary Computation Conference (GECCO) 2012, 2012. 2012

Multiagent Learning through Neuroevolution Risto Miikkulainen, Eliana Feasley, Leif Johnson, Igor Karpov, Padmini Rajagopalan, Aditya Rawal, an... In J. Liu et al., editors, Advances in Computational Intelligence, LNCS 7311, 24-46, Berlin, ... 2012

Task decomposition with neuroevolution in extended predator-prey domain Ashish Jain, Anand Subramoney, Risto Miikkulainen In Proceedings of Thirteenth International Conference on the Synthesis and Simulation of Living S... 2012

An Integrated Neuroevolutionary Approach to Reactive Control and High-level Strategy Nate Kohl, Risto Miikkulainen IEEE Transactions on Evolutionary Computation, 2011. 2011

Avoiding Premature Convergence in NeuroEvolution by Broadening the Evolutionary Search Matthew de Wet Technical Report HR-11-02, Department of Computer Science, The University of Texas at Austin, 2011. 2011

Creating Intelligent Agents through Shaping of Coevolution Adam Dziuk Technical Report HR-11-01, Department of Computer Science, The University of Texas at Austin, 2011. 2011

Creating Intelligent Agents through Shaping of Coevolution Adam Dziuk and Risto Miikkulainen In Proceedings of the Congress on Evolutionary Computation, New Orleans, LA, 2011. IEEE. 2011

Evolving Multimodal Networks for Multitask Games Jacob Schrum and Risto Miikkulainen In Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG 2011), 102... 2011

Evolving Symmetry for Modular System Design Vinod K. Valsalam and Risto Miikkulainen IEEE Transactions on Evolutionary Computation, 15(3):368--386, 2011. 2011

Human-Assisted Neuroevolution Through Shaping, Advice and Examples Igor V. Karpov, Vinod K. Valsalam and Risto Miikkulainen In Proceedings of the 13th Annual Genetic and Evolutionary Computation Conference (GECCO 2011) 2011

Measure-Theoretic Evolutionary Annealing Alan J. Lockett and Risto Miikkulainen In Proceedings of the 2011 IEEE Congress on Evolutionary Computation, 2011. 2011

Real-Space Evolutionary Annealing Alan J Lockett and Risto Miikkulainen In Proceedings of the 2011 Genetic and Evolutionary Computation Conference (GECCO-2011), 2011... 2011

The Role of Reward Structure, Coordination Mechanism and Net Return in the Evolution of Cooperation Padmini Rajagopalan, Aditya Rawal, Risto Miikkulainen, Marc A. Wiseman and Kay E. Holekamp In Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG 2011), Seo... 2011

Utilizing Symmetry and Evolutionary Search to Minimize Sorting Networks Vinod K. Valsalam and Risto Miikkulainen Technical Report AITR-11-09, Department of Computer Sciences, The University of Texas at Austin, Aus... 2011

UT^2: Human-like Behavior via Neuroevolution of Combat Behavior and Replay of Human Traces Jacob Schrum, Igor V. Karpov and Risto Miikkulainen In Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG 2011), 329... 2011

An Analysis of Automated Decision Making Methodologies in Role Playing Video Games: Centralized Approach Christopher Bush Technical Report HR-10-03, Department of Computer Science, The University of Texas at Austin, 2010. 2010

An Analysis of Distributed Decision Making Methodologies in Role Playing Video Games Matthew Johnston Technical Report HR-10-09, Department of Computer Science, The University of Texas at Austin, 2010. 2010

Coevolution of Role-Based Cooperation in Multi-Agent Systems Chern Han Yong and Risto Miikkulainen IEEE Transactions on Autonomous Mental Development, 1:170--186, 2010. 2010

Constructing Competitive and Cooperative Agent Behavior Using Coevolution Aditya Rawal, Padmini Rajagopalan and Risto Miikkulainen In IEEE Conference on Computational Intelligence and Games (CIG 2010), Copenhagen, Denmark, A... 2010

Evolving Agent Behavior In Multiobjective Domains Using Fitness-Based Shaping Jacob Schrum and Risto Miikkulainen In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2010), 439--446,... 2010

Hierarchical Neural Networks for Behavior-Based Decision Making David Robson Technical Report HR-10-02, Department of Computer Science, The University of Texas at Austin, 2010. 2010

Latent Class Models for Algorithm Portfolio Methods Bryan Silverthorn and Risto Miikkulainen In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010. 2010

Neuroevolution Risto Miikkulainen In Encyclopedia of Machine Learning, New York, 2010. Springer. 2010

Speciation in NEAT Timothy Nodine Technical Report HR-10-06, Department of Computer Science, The University of Texas at Austin, 2010. 2010

Utilizing Symmetry in Evolutionary Design Vinod Valsalam PhD Thesis, Department of Computer Sciences, The University of Texas at Austin, Austin, TX, 2010. Te... 2010

Evolving Neural Networks for Strategic Decision-Making Problems Nate Kohl and Risto Miikkulainen In Neural Networks, Special issue on Goal-Directed Neural Systems, 2009. 2009

Evolving Symmetric and Modular Neural Network Controllers for Multilegged Robots Vinod K. Valsalam and Risto Miikkulainen In xploring New Horizons in Evolutionary Design of Robots: Workshop at the 2009 IEEE/RSJ Internat... 2009

Evolving Symmetric and Modular Neural Networks for Distributed Control Vinod K. Valsalam and Risto Miikkulainen In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), 731--738, 200... 2009

Learning in Fractured Problems for Constructive Neural Network Algorithms Nate Kohl PhD Thesis, Department of Computer Sciences, University of Texas at Austin, Austin, TX, 2009. 2009

Temporal Convolution Machines for Sequence Learning Alan J Lockett and Risto Miikkulainen Technical Report AI-09-04, Department of Computer Sciences, the University of Texas at Austin, 2009. 2009

ESL This is the C# source code for the experiments with Egalitarian Social Learning (ESL) in a robot foraging domain. The re... 2012

UT^2: Winning Botprize 2012 Entry The Botprize Competition is an annual competition to program bots that appear human-l... 2012

PyEC Python package containing source code for Evolutionary Annealing along with a number of other evolutionary and stochasti... 2011

BREVE Monsters BREVE is a system for designing Artificial Life simulations available at http://spiderlan... 2010

ENSO This package contains software implementing the ENSO approach for evolving symmetric modular neural networks. It also in... 2010

NEAT C++ The NEAT package contains source code implementing the NeuroEvolution of Augmenting Topologies method. The source code i... 2010

OpenNERO OpenNERO is a general research and education platform for artificial intelligence. The platform is based on a simulatio... 2010

Sorting Networks This package contains software utilizing an approach based on symmetry and evolution to minimize the number of comparato... 2010

rtNEAT C++ The rtNEAT package contains source code implementing the real-time NeuroEvolution of Augmenting Topologies method. In ad... 2006

SANE-C The SANE-C package contains the source code for the Hierarchical SANE system, written in C. This package has been rewrit... 1997