Ignorance is bliss: A complexity perspective on adapting reactive architectures
S.l. : IEEE
In2011 IEEE International Conference on Development and Learning (ICDL), pp. 1-5
Article in monograph or in proceedings
Display more detailsDisplay less details
SW OZ DCC CO
SW OZ DCC AI
2011 IEEE International Conference on Development and Learning (ICDL)
SubjectCognitive artificial intelligence; DI-BCB_DCC_Theme 2: Perception, Action and Control
We study the computational complexity of adapting a reactive architecture to meet task constraints. This computational problem has application in a wide variety of fields, including cognitive and evolutionary robotics and cognitive neuroscience. We show that-even for a rather simple world and a simple task-adapting a reactive architecture to perform a given task in the given world is NP-hard. This result implies that adapting reactive architectures is computationally intractable regardless the nature of the adaptation process (e.g., engineering, development, evolution, learning, etc.) unless very special conditions apply. In order to find such special conditions for tractability, we have performed parameterized complexity analyses. One of our main findings is that architectures with limited sensory and perceptual abilities are efficiently adaptable.
Upload full text
Use your RU credentials (u/z-number and password) to log in with SURFconext to upload a file for processing by the repository team.