Michael Wellman
University of Michigan
<http://ai.eecs.umich.edu/people/wellman/>
Trading Agents Competing
Since its inception four years ago, the annual Trading Agent Competition has provided a forum for researchers to test their automated trading strategies in a challenging market game. These efforts have led to several new techniques, for such problems as bidding under uncertainty, and price prediction through learning conditional density distributions. Highlights of the TAC experience illustrate some of the key strategic and methodological lessons, and post-competition evaluations suggest a measure of progress. Michigan's entries--"Walverine" for the travel-shopping game, and "Deep Maize" for the supply-chain game--served as excellent vehicles for testing our own research ideas on competitive analysis and distributed feedback control (without embarrassing the university too much in the process).
Una-May O'Reilly
Computer Science and Artificial Intelligence Lab, MIT
<unamay@ai.mit.edu>
<http://www.ai.mit.edu/people/unamay/>
Engineering for Emergence: Robots and Creative Surfaces
Designing the software of a behavior-based robot is tricky. Why? Because one has to craft not only anticipated environmental and behavioral interactions, but also to design competent structures that will scaffold higher behaviors. Because of similar goals focused on emergence, evolutionary computation for creative design, despite compelling power, also presents design challenges. In the context of humanoid robots from our group (including a new robot, Cardea) and, Genr8, an architect's surface exploration tool, I will discuss how complex systems are both powerful and not without challenges when used for engineering purposes.
Melanie Mitchell
OGI School of Science and Engineering
<mm@cse.ogi.edu>
<http://www.cse.ogi.edu/~mm/>
Coevolutionary Learning
Coevolutionary learning is a biologically inspired machine learning
technique in which a population of learners coevolves with a
population of training examples. The biological inspiration comes
from host-parasite (or predator-prey) competitions, in which species A
evolves to thwart attacks from species B, only to see species B evolve
to outwit the adaptations of species A, and so on, in an ever
spiraling "biological arms race". Likewise (the hope goes), in
coevolutionary learning, learners will evolve to successfully classify
the current population of training examples, but in turn the training
examples will evolve to be increasingly challenging for the learners,
who in turn will become even more sophisticated, and so on. The
(hoped for) result will be more successful learning with a smaller
number of training examples than in traditional techniques.
Coevolutionary learning first achieved popularity in the 1990s with
the success of Danny Hillis's coevolving sorting networks. While the
idea is compelling and while there have been other successful
applications of coevolution on toy problems, there have also been
numerous failures of the method, and there is still no good
understanding of the conditions under which such methods will work
well, and whether such methods can scale to more complicated problems.
In this talk I will review the highlights of work on
coevolution---both successes and failures---and present new research
aimed at understanding the role of spatial distribution of populations
in successful applications of coevolutionary learning.
Raissa D'Souza, Microsoft
<raissa@microsoft.com>
<http://research.microsoft.com/users/raissa/>
Self-organization in phase transitions and geometric graphs
Many interesting behaviors can arise from simple, small scale interactions which give rise to large scale order. I will describe two examples, one from statistical physics, the other from network engineering. The first is a simple system of "traffic" moving on a lattice, which shows a sharp transition from free flowing to fully jammed as a function of the initial density of cars. Aside from exploring the jamming transition, I discuss the influence, that conserved quantities and the details of the kinetic pathway, can exert on determining the final state of the system. In a network context, simple algorithms will be presented for building up self-organized, fully connected networks made of rudimentary nodes which are free to move on a plane. Simple measures for quantifying the performance of such data networks, which rely only on local small scale data exchange, will also be discussed.
John Koza
Stanford University
<koza@cs.stanford.edu>
<http://www.genetic-programming.com/johnkoza.html>
Emergence of Creativity
Genetic and evolutionary computation, in the form of genetic programming, is now being routinely used as a invention machine to automatically create the designs for complex structures (analog electrical circuits, controllers, antennas, networks of chemical reactions, genetic networks). The same kind of creativity and logical discontinuity seen in human-created inventions has repeatedly emerged during this automated process for the synthesis of complex structures. Among the 38 human-competitive results produced so far, there are now 14 instances where genetic programming has created an entity that either infringes or duplicates the functionality of a previously patented 20th-century invention, 6 instances where genetic programming has done the same with respect to a post-2000 patented invention, and 2 instances where genetic programming has created a patentable new invention (controllers that outperform the Ziegler-Nichols and Astrom-Hagglund tuning rules for multiple families of plants). This automatic synthesis is performed by means of genetic programming with a de minimus amount of human-suppled knowledge, information, and analysis. In many cases, the feature identified by the human inventor as the "essence of the invention" has emerged during the automated process. In addition, genetic programming automatically identifies substructures that are to be reused(e.g., subroutines, iterations, and recursion) and information that is to be reused (e.g., storage) . Reuse avoids reinventing the wheel on each occasion requiring a particular sequence of already-learned steps. Architecture-altering operations automatically determine program architecture in a manner that parallels gene duplication, and the related operation of gene deletion, in nature. Taking a historical perspective over the past 15 years, genetic programming has delivered a progression of qualitatively more substantial results in synchrony with five approximately order-of-magnitude increases in the expenditure of computer time. The progression includes toy problems, human-competitive results not related to patented inventions, 20th century patented inventions, 21st century patented inventions, and patentable new inventions. In other words, genetic programming is Mooreware in that is profitably exploits the increasing availability of computer power.
Daniel Koditschek, Electrical Engineering and Computer Science
Artificial Intelligence Lab, University of Michigan
<kod@umich.edu>
<http://ai.eecs.umich.edu/people/kod/>
Toward a Synthesis of Form and Function: Notes from the Pre-Genomic Era of Robotics
Robotics - controlling the exchange of energy with the environment in
order to achieve a novel goal - is apparently harder than we really yet
understand; certainly harder than merely programming information. For
the present, robotics will gain at least as much insight and inspiration
from animal science as from engineering science. This talk will focus on
a case in point - the origins, implementation, analysis, and impending
commercial debut of a new bioinspired robot. Novel hypotheses from
biomechanics concerning sprawled posture animal runners prompted the
design of a new hexapedal robot, RHex, whose mobility exceeded by a
large margin the performance of previously documented autonomous legged
machines. At the same time, mathematical analysis along a spectrum of
relevant models has begun to shed some light on the principles
underlying the success of this revolutionary design. In turn, that
growing understanding, together with insights gained from extensive
robot experiments and empirically guided redesign has led to new
hypotheses about the interaction of animal neural and musculoskeletal
systems during running. Meanwhile, the robot has spun off into the
commercial world, and we are hopeful that its unusual capabilities will
usher in a renewed appreciation for the potential value of legged
machines in various settings of significant social importance.
In general, such insights as led to RHex will be hard won. Biological
systems exhibit highly modular conserved design that conflates form and
function, all parameterized by the genome. In contrast, engineering
systems science has traditionally abstracted form away from function and
focused on highly optimized design. We are barely started on the road to
a language by which to prescribe the algorithms of work; prescribing its
architecture is still less mature. Our design documents read as Babels
of competing representation that testify to the incompatible
parameterizations of mechanical, electrical and software engineering.
Rich, new mathematics and engineering principles will be required to
build a formal understanding of how to program work. Formal
understanding of robotics, conceived appropriately broadly in this
manner, can yield new hypotheses and methods for biology. Correctly
working robotic systems will inspire theoretical approaches to
generalized embedded computing with a social impact that will dwarf the
present sway of information technology.
John Laird
University of Michigan
<laird@umich.edu>
<http://ai.eecs.umich.edu/people/laird/>
Building Complex Human-level Synthetic Characters
In this talk I will give an overview of Soar, the architecture we have been
developing for the last twenty years to create human-level synthetic
characters. Using Soar, we have developed characters for use in training
using large-scale distributed training, and for playing with and against in
computer games.
I will discuss the challenges of creating such characters, engineering them
so that they perform according to appropriate doctrine and tactics, but also
are extremely flexible and have controlled variability. Creating such
characters by hand is possible but requires expert developers and is
extremely time consuming and prone to error. To meet those challenges, we
are developing a diagrammatic, example-driven tool that can be used directly
by subject matter experts for extremely fast, but validated knowledge
acquisition of procedural knowledge.
Satinder Singh, Computer Science & Engineering
University of Michigan
<baveja@umich.edu>
<http://www.eecs.umich.edu/~baveja/>
Predictive Models for Reinforcement Learning
The use of Markov decision process (MDP) models to represent agent-environment interaction has been very fruitful for reinforcement learning and for artificial intelligence in general. After briefly reviewing some of these "fruits" I will discuss the limitations of MDP models and the need to go beyond them. The standard extension of MDPs to partially-observable MDPs, or POMDPs, haven't served us well, at least so far. In this talk, I will present predictive state representations, or PSRs, a new class of predictive models for reinforcement learning. The key idea in PSRs is to use predictions of observable outcomes of tests or experiments the agent can do in its environment to represent the state of the environment. I will show that PSRs are more general than POMDPs and yet are at least as, and often more, compact than POMDPs. I will also present some results on learning PSR models from data and conclude with some reasons for optimism about PSR models as well as with directions for future work on PSRs.