Dr. Todd Wareham
A Complexity Perspective on Adapting Reactive Architectures
Department of Computer Science
Thursday, December 1, 2011, 1:00 pm., Room EN-2022
The problem of adapting an existing reactive architecture to meet new task constraints has applications in a wide variety of fields, including cognitive robotics, evolutionary robotics, and cognitive neuroscience. Such adaptation can range from simple reconfiguration of existing layers and the linkages between them to the the recruitment of new layers (either on-hand or custom-designed). Though there are a number of proof-of-concept systems implementing such adaptation, it is not obvious if any algorithm can perform efficient adaptation in general or, if not, under which conditions (if any) such efficient adaptation might be possible.
In this talk, we present the initial results of a computational complexity analysis of reactive adaptation carried out to answer these two questions. Our main result is that even for a rather simple world and a simple task, adapting a subsumption reactive architecture to perform that task in a given world is NP-hard. Additional parameterized results in turn delimit those conditions under which efficient adaptation is possible, e.g., we show that architectures with limited sensory and perceptual abilities are efficiently adaptable.
(Work done in collaborations with Pim Haselager, Johan Kwisthout, and Iris van Rooij (Radboud University Nijmegen))