Learning Collaborative Behaviors
Adaptive Team Formations
 |
I am working with the Adaptive Systems Group at the Naval Center for Applied
Research in Artificial Intelligence (NCARAI) and Bill Spears at the University of Wyoming to extend and generalize his physicomimetics framework for multiagent reactive control. Here an artificial physics system is constructed in order to develop a self-organizing team of agents capable of a wide variety of behaviors. It is particularly well-suited to behaviors that involves geometric formations. We have developed a generalized, graph-based design method for constructing modular and scalable heterogeneous behaviors for teams of robots and applied it to a variety of multiagent problems, such as resource protection. Early work suggests that team formations resilliant to attrition and re-deployment of platforms for quite natural to develop using such representations.
|
Transfer Learning & Role Reassignment
I am working with the Adaptive Systems Group at the Naval Center for Applied
Research in Artificial Intelligence (NCARAI) developing methods
that allow teams of collaborating agents (e.g., robots) to
adaptively restructure, reassigning roles and tasks to continue to
be effective when capabilities or objectives change.
Though in its early stages, this research leverages
existing work by NRL in transfer learning (sometimes refered to as "Anytime learning" or "Continuous and Embedded Learning"). The idea is to allow
agents to test new strategies in simulation while vetted strategies
are in operation. When the system detects changes in capabilities
or objectives, any similar situations remembered by the agent are
recalled and tested (again in simulation), updating operational
behaviors when reasonable solutions are found.
Analysis of Cooperative Coevolutionary Algorithms
Robustness and Coadaptive Learning
Recent analysis of compositional coevolutionary algorithms (CCEAs) has indicated that the underlying purpose of the algorithm is determined largely by how one chooses to aggregate team performance information during the evaluation process. Early analysis suggests that, when evaluation is determined by averaging performances of different team configurations, CCEAs may be quite suitable to finding behaviors for team members that result in good (though not necessarily optimal) performance but which are also robust to changes in other team members. Our group has developed a general framework for clearly defining the term robustness and instantiated particular definitions for our purposes. We have used existing theoretical models of CCEAs, as well as experimentation for real algorithms to help develop a constructive view of CCEAs as optimizers of robustness.
Dynamical Systems Modeling of Multi-Population Symmetric CEAs
 |
Coevolutionary algorithms behave in very complicated, often
quite counterintuitive ways. As a result, engineers using such
algorithms need directed investigations to help practitioners
understand what particular coevolutionary algorithms are good
at, what they are not, and why. In my research, my colleagues
and have chosen to examine a particular class of coevolutionary
algorithms useful to solving compositional,
or cooperative tasks, the multi-population symmetric
coevolutionary algorithm (MPS-CEA). |
Bill Liles, Ken De Jong, and I have sought to improve our
understanding of coevolution by answering the question: "Are MPS-CEAs
appropriate for static optimization tasks?". From a dynamical systems
point of view, one way this question can be reposed more specifically
is by asking "How likely are such algorithms to obtain the optimum?"
This question can be answered by looking at the dynamical properties
of these algorithms, analyzing their limiting behaviors again from
theoretical and empirical points of view. The result is a better
understanding of, and appreciation for, the fact that CCEAs
are not generally appropriate for the task of static,
single-objective optimization. Currently, I am examining how
traditional MPS-CEAs may be more appropriately applied when the
desired solution has certain kinds of robustness properties.
Run Time Analysis of CCEAs
| One way to investigate the optimization potential of
multi-population symmetric coevolutionary algorithms (MPS-CEAs) is
simply to analyze its performance on such problems. Thomas Jansen
and I have applied tools from randomized algorithm analysis to do
exactly this, attempting to answer the question: "What is the
expected number of evaluations the algorithm must make in order to
find the global optimum?" We have mainly concentrated our attention
on the CC (1+1) EA, a particular subclass of coevolutionary
algorithms. We have also investigated some population-based
approaches. |
 |
Though the property of separability of problems as it relates to
the a priori representational decomposition provided by the
design engineer when using such coevolutionary approaches is
considered very important to their success or failure, our research
shows that separability alone is not sufficient to yield any
advantage of the CC (1+1) EA over its traditional,
non-coevolutionary counterpart. Such an advantage is demonstrated to
have its basis in the increased explorative possibilities of the
cooperative coevolutionary algorithm. Moreover, though particular
problems can pose certain unique challenges for CEAs, inseparability
alone is also insufficient for an objective function to cause
difficulties; the CC (1+1) EA may perform equal to its traditional
counterpart, and may even outperform it on certain inseparable
functions.
Augmenting CEAs for Static Optimization Tasks
 |
Multi-population symmetric coevolutionary algorithms (MPS-CEAs)
offer great potential for concurrent multiagent learning domains and
are of special utility to games involving teams of multiple agents.
Unfortunately, these algorithms exhibit pathologies resulting from
their game-theoretic nature, and these pathologies interfere with
finding solutions that correspond to optimal collaborations of
interacting agents. |
With my colleagues Liviu Panait, Sean Luke, and Jayshree Sarma, I
have helped address this problem in two ways. First, MPS-CEAs can
be biased in such a way that the fitness of an individual is based
partly on the result of interaction 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. As it
turns out, it is possible to improve coevolutionary search for
optimal multiagent behaviors using such a biasing method. Second, I
have examined the the use of spatial embedding of populations as a
means to combat certain pathologies frequent in coevolutionary
algorithms. It turns out that applying spatial constraints
to both the selection and the collaboration process is
necessary to see benefits from such a method.
|