Grant: Discovery Grants Program - Individual
Memorial University of Newfoundland
$15,000.00
Parameterized complexity analysis in cognitive science
EF 2012-13
Résumé
Every day, we as human beings are constantly performing computations as part of our everyday lives -- we search cluttered desks for misplaced keys, we make plans for visiting a set of stores to get everything we need for an upcoming party, we decide that comparing a neighbor's child to a runaway bull is (or is not) appropriate. We do these computations quickly and (for the most part) correctly, and they seem so simple -- however, after 50 years of research, the subdiscipline of Computer Science called Artificial Intelligence (AI) has yet to replicate in robots and software systems many human cognitive abilities that we take for granted. This is not just a software or hardware problem -- psychologists working in Cognitive Science have equal difficulties deriving general theories explaining how we do the things we do as quickly and as well as we do.
The typical approach to handling such difficult problems in both AI and Cognitive Science is to invoke fast approximation methods called heuristics which always give solutions quickly (though not necessarily the best ones). However, this may not be necessary -- given all the restrictions on the types of inputs to and required outputs from human cognition in practice, there may yet be best-solution methods that are slow in general but fast for the particular situations humans typically encounter every day.
In my research, I use techniques from the theory of parameterized computational complexity to find such methods for solving difficult problems encountered in Cognitive Science and AI. I will not only be tackling problems arising from deriving theories or software implementations of human cognitive abilities, but also analysis problems for very large datasets of observed human behaviors (which give further insights into how we think and act the way we do). The methods derived in my research should lead not only to better theories of human cognition but also to better implementations of human abilities in robots and other AI systems.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Newfoundland and Labrador, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
228104-2010
Name nom
Wareham, HaroldTodd
Department département
Computer Science
Organization id
89
Institution établissement
Memorial University of Newfoundland
Province en
Newfoundland and Labrador
Province fr
Terre-Neuve-et-Labrador
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2010
Award amount
15000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
3
Nb partie
5
Application title
Parameterized complexity analysis in cognitive science
Keyword
NSERC
Application summary
Every day, we as human beings are constantly performing computations as part of our everyday lives -- we search cluttered desks for misplaced keys, we make plans for visiting a set of stores to get everything we need for an upcoming party, we decide that comparing a neighbor's child to a runaway bull is (or is not) appropriate. We do these computations quickly and (for the most part) correctly, and they seem so simple -- however, after 50 years of research, the subdiscipline of Computer Science called Artificial Intelligence (AI) has yet to replicate in robots and software systems many human cognitive abilities that we take for granted. This is not just a software or hardware problem -- psychologists working in Cognitive Science have equal difficulties deriving general theories explaining how we do the things we do as quickly and as well as we do.
The typical approach to handling such difficult problems in both AI and Cognitive Science is to invoke fast approximation methods called heuristics which always give solutions quickly (though not necessarily the best ones). However, this may not be necessary -- given all the restrictions on the types of inputs to and required outputs from human cognition in practice, there may yet be best-solution methods that are slow in general but fast for the particular situations humans typically encounter every day.
In my research, I use techniques from the theory of parameterized computational complexity to find such methods for solving difficult problems encountered in Cognitive Science and AI. I will not only be tackling problems arising from deriving theories or software implementations of human cognitive abilities, but also analysis problems for very large datasets of observed human behaviors (which give further insights into how we think and act the way we do). The methods derived in my research should lead not only to better theories of human cognition but also to better implementations of human abilities in robots and other AI systems.
