Representational complexity of reactive agents

Reactive agents are an important part of video games and numerous tools have emerged to facilitate the rapid construction of such agents. While the ability of the commonly used reactive techniques to express agent specifications is roughly equivalent, the authorial burden of constructing these specifications varies. In practice, this means that identical agent behavior may be more difficult to create in some architectures than others. In this paper we introduce the notion of representational complexity that relates to the authorial burden of constructing such agents and theoretically compare the representational complexity of finite state machines, behavior trees, and subsumption architectures. Our key finding is that hierarchical subsumption architectures have significantly lower representational complexity as compared to hierarchical finite state machines and behavior trees, which makes subsumption the best choice when developing authoring tools for non-expert users.