Validating complex agent behavior.

Abstract

Developing software agents that replicate human behavior, even within a narrow domain, is a time consuming and error prone process. The most widely used methodology for designing these agents is based on the complementary processes of knowledge acquisition and validation, both of which have been cited as significant bottlenecks. In this thesis, we identify two methods for comparing actors' behavior that have the potential to decrease the cost of validation. The first is a simple sequence-based approach that can be used to compare many different aspects of two actors' behavior. Although initially promising, our empirical and analytical analysis exposes significant limitations with this general class of approaches, especially as the complexity of the domain increases. As a result, we turn to a novel comparison approach that we call behavior bounding. Unlike the sequential approaches, behavior bounding uses a concise representation of an actor's aggregate behavior as a basis for performing its comparison. We show that behavior bounding requires minimal human effort to use and that its representation of behavior is efficient to construct and maintain even as the complexity of the environment increases. Furthermore, we show that behavior bounding outperforms the sequential comparison approach in two domains of distinct complexity. Finally, we provide empirical evidence that behavior bounding's summary of the differences in two actors' behavior can be used to significantly speed up the knowledge validation process.