Kagan Tumer's Publications

Display Publications by [Year] [Type] [Topic]


Efficient Evaluation Functions for Evolving Coordination. A. K. Agogino and K. Tumer. Evolutionary Computation, 16(2):257–288, 2008.

Abstract

This paper presents fitness evaluation functions that efficiently evolve coordination in large multi-component systems. In particular, we focus on evolving distributed control policies that are applicable to dynamic and stochastic environments. While it is appealing to evolve such policies directly for an entire system, the search space is prohibitively large in most cases to allow such an approach to provide satisfactory results. Instead, we present an approach based on evolving system components individually where each component aims to maximize its own fitness function.Though this approach sidesteps the exploding state space concern, it introduces two new issues:1) how to create component evaluation functions that are aligned with the global evaluation function; and 2) how to create component evaluation functions that are sensitive to the fitness changes of that component, while remaining relatively insensitive to the fitness changes of other components in the system. If the first issue is not addressed, the resulting system becomes uncoordinated; if the second issue is not addressed, the evolutionary process becomes either slow to converge or worse, incapable of converging to good solutions. This paper shows how to construct evaluation functions that promote coordination by satisfying these two properties. We apply these evaluation functions to the distributed control problem of coordinating multiple rovers to maximize aggregate information collected. We focus on environments that are highly dynamic (changing points of interest), noisy (sensor and actuator faults), and communication limited (both for observation of other rovers and points of interest) forcing the rovers to evolve generalized solutions. On this difficult coordination problem, the control policy evolved using aligned and component-sensitive evaluation functions outperforms global evaluation functions by up to 400\%.More notably, the performance improvements increase when the problems becomes more difficult (larger, noisier, less communication). In addition we provide an analysis of the results by quantifying the two characteristics (alignment and sensitivity discussed above) leading to a systematic study of the presented fitness functions.

Download

[PDF]825.8kB  

BibTeX Entry

@article{tumer-agogino_ecj08,
	author = {A. K. Agogino and K. Tumer},
	title = {Efficient Evaluation Functions for Evolving Coordination},
	journal = {Evolutionary Computation},
	Volume = {16},
	Number = {2},
	pages = {257-288},
	bib2html_pubtype = {Journal Articles},
	bib2html_rescat = {Evolutionary Algorithms, Robotics},
	abstract = {This paper presents fitness evaluation functions that efficiently evolve coordination in large multi-component systems. In particular, we focus on evolving distributed control policies that are applicable to dynamic and stochastic environments.   While it is appealing to evolve such policies directly for an entire system, the  search space is prohibitively large in most cases to allow such an approach to provide satisfactory results. Instead, we present an approach based on evolving system components individually where each component aims to maximize its own fitness function.
Though this approach sidesteps the exploding state space concern, it introduces two new issues:
1) how to create component evaluation functions that are aligned with the global evaluation function; and 2) how to create component evaluation functions that are sensitive to the fitness changes of that component, while remaining relatively insensitive to the fitness changes of other components in the system. If the first issue is not addressed, the resulting system becomes uncoordinated; if the second issue is not addressed, the evolutionary process becomes either slow to converge or worse, incapable of converging to good solutions. 
This paper shows how to construct evaluation functions that promote coordination by satisfying these two properties. We apply these evaluation functions to the distributed control problem of coordinating multiple rovers to maximize aggregate information collected. We focus on environments that are highly dynamic (changing points of interest), noisy (sensor and actuator faults), and communication limited (both for observation of other rovers and points of interest) forcing the rovers to evolve generalized solutions. On this difficult  coordination problem, the control policy evolved using aligned and component-sensitive evaluation functions outperforms global evaluation functions by up to 400\%.
More notably, the performance improvements increase when the problems becomes more difficult (larger, noisier, less communication). In addition we provide an analysis of the results by quantifying the two characteristics (alignment and sensitivity discussed above) leading to a systematic study of the presented fitness functions. },
	year = {2008}
}

Generated by bib2html.pl (written by Patrick Riley ) on Tue Jun 26, 2018 19:10:42