Thursday, November 24, 2011

Departmental Seminar @ Memorial University: A Complexity Perspective on Adapting Reactive Architectures

Another seminar upcoming for the Department of Computer Science at Memorial University of Newfoundland. This one is being present by a good friend of mine Dr Todd Wareham (he's one of the core people behind the local CS Games held several times each semester at Memorial).



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

Abstract

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))

No comments: