Please Enter a Search Term
Departmental Seminar Dec 1st: Todd Wareham
Antonina Kolokolova

                                  Dr.  Todd Wareham
                                           (CS, MUN)

                                     Educating Genghis:
        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))


Nov 2nd, 2011

Bookmark and Share