Authors: Dimitar Kazakov and Mark Bartlett
Speaker: Dimitar Kazakov
Duration: 1/2 day.
Level: Introductory course
Prerequisites: The tutorial will assume familiarity with basic concepts from formal languages and artificial intelligence, such as regular and context-free grammars and evolutionary algorithms. Certain knowledge of logic programming (Prolog) would help appreciate some of the details.
Outline: When a society of agents explores a new and/or dynamically changing enviroment, the issues of navigation, cooperation and communication are intertwined, and of rather complex nature. The individual agent may benefit from an internal representation of the surrounding environment, as this could help re-visit previously discovered locations of interest. The society as a whole may be able to maintain higher population levels, if agents cooperate, i.e., help each other. It is a well known fact that altruism, i.e., helping the others at a cost to ourselves, is compatible with Darwinian selection whithin the frame of kin selection, where help is directed to relatives (Hamilton 1964, Dawkins 1982). Help in kind is the easiest to model, as the degree of relatedness and the amount of help can be precisely related. On the other hand, sharing information about the spatial location of resources is more difficult to explain, as usually one looses control over the shared information, as well as over the actual resource it points to. Results of multi-agent simulations will be used to demonstrate the properties of the enviroment, such as distance between resources, and their amount and volatility, for which communication (sharing directions) is particularly beneficial and outperforms selfish behaviour or sharing in kind (Kazakov & Bartlett 2004, 2005).
The issues of navigation, cooperation and communication are also related through the nature and origin of the communication language being used. There are several models of the origins of human language that use computer simulation in an attempt to illustrate the potential to evolve one or other property of human language, such as compositionality (S. Kirby), or the speakers' ability to agree on a shared lexicon (L. Steels). While some researchers adopt the Chomskian paradigm of an innate Language Acquisition Device (LAD) that constrains the range and type of human languages and so speeds up their acquisition, others have assumed that the language faculty is based on more general information-theoretical principles (Kazakov 1997, Goldsmith 2001), make use of general faculties, such as the ability to learn "agebra-like rules" (Marcus et al., 1999), and that at least some of the mechanisms for language processing could be the result of exaptation, i.e., have evolved for other purposes, such as navigation (Bartlett & Kazakov 2004).
Navigation using landmarks (beacons, waypoints) is computationally equivalent to parsing a string of terminal symbols, i.e., a sentence. Also, combining the ability to evolve a shared lexicon, which is possible from simple first principles (Steels) with the ability to spell out a route as a list of landmarks to follow, can provide a simple explanation for the emergence of compositional language (that is, one with syntax). The isomorphism between navigation and parsing could also be used to test the faculty of other species to perform language-related tasks, a quest recently outlined by Hauser, Chomsky and Fitch (2002). Unlike the experiments with spoken language (Fitch & Hauser 2004), whose setup has been criticised (Liberman 2004), one can use navigation to test the ability to learn regular and context-free languages (Kazakov & Bartlett 2005). Evidence from Neuroscience and Biology (Ullman 2004, Foster & Wilson 2006) will be used to illustrate the link between linguistic and repetitive motor action tasks, and the cross-influence that exercising one faculty has on the other (Hoen et al. 2003).
In the final part of the tutorial, a simple multi-agent (predator-prey) environment written in Prolog will be used to demonstrate how evolution and learning can be used to improve the agents' default hunting strategies based on limited and imprefect perception through cooperation, role specialisation, and the use of simple communication (howling). The examples will be drawn from some 30 fourth-year MEng students' solutions to their open book examination in Adaptive and Learning Agents taught by Dimitar Kazakov at York since Spring 2005.
Aims: The tutorial will provide an integrated view of the issues of spatial cognition, navigation and language, covering some of the most relevant literature, and demonstrate how computer simulations can be used to study those issues in a constructive fashion. A simple Prolog simulator of the discrete predator-prey problem will be made available and its principles briefly explained to make possible future experiments with it.
Both authors have an active research record in the area:
M. Bartlett and D. Kazakov. The evolution of syntactic capacity from navigational ability. The Sixth Intl. Conference on the Evolution of Language (EvoLang 2006). 2p. Rome, 12-15 April 2006. M. Bartlett and D. Kazakov. The Origins of Syntax: from Navigation to Language. Connection Science 17(3-4), pp. 271-288, 2005. (Special issue on the emergence of language: neural and adaptive agent models). D. Kazakov and M. Bartlett. Could Navigation Be the Key to Language? In the Proc. of the Second Symposium on the Emergence and Evolution of Linguistic Communication (EELC'05), pp. 50-55. 12-15 April 2005, Hatfield UK. Published by AISB, ISBN: 1 902956 40 9. D. Kazakov and M. Bartlett. Co-operative navigation and the faculty of language. Applied Artificial Intelligence, 18:885-901, 2004. D. Kazakov and M. Bartlett. Social Learning through Evolution of Language. Artificial Evolution. 6th International Conference, Evolution Artificielle, EA 2003, Marseilles, France, October 27-30, 2003. Series: Lecture Notes in Computer Science, Vol. 2936. Liardet, P.; Collet, P.; Fonlupt, C.; Lutton, E.; Schoenauer, M. (Eds.) 2004, XIV, 410 p. ISBN: 3-540-21523-9. M. Bartlett and D. Kazakov. The role of environment structure in multi-agent simulations of language evolution. Proceedings of the Fourth Symposium on Adaptive Agents and Multi-Agent Systems (AAMAS-4), AISB convention, Leeds, 2004. D. Kazakov. Evolutionary Algorithms with Extended Fitness. Department of Computer Science, University of York, UK. Technical report YCS 370, 2004. H. Turner and D. Kazakov. Stochastic Simulation of Inherited Kinship-Driven Altruism. Journal of Artificial Intelligence and Simulation of Behaviour, p. 183-196, 1(2), 2002. Dimitar Kazakov has been a lecturer in Machine Learning at the Computer Science Department of the University of York, UK since 1999. His research focusses on the intersection between multi-agent systems, machine learning and language. He has taught an MEng (4th, final year) course on Adaptive and Learning Agents at the CS Dept. of the University of York for the past two years, and has given a number of AI-related international summer school tutorials and courses in the past: * ACAI-01: Machine Learning and Inductive Logic Programming for Multi-Agent Systems (with Daniel Kudenko) http://www-users.cs.york.ac.uk/~kazakov/papers/acai01.htm * ECAI-02: Machine Learning for Agents and Multi-Agent Systems (with Daniel Kudenko) * ESSLLI-04: Symbolic Learning of Language (with James Cussens), http://esslli2004.loria.fr/giveabs.php?6 He is also the organiser of the Navigation Debate at the UK AISB 2006 convention: http://www-users.cs.york.ac.uk/~kazakov/AISB-debate/. Mark Bartlett is a research associate at the CS Department of the University of York. He is in the writing up period of his PhD on the Evolution of Syntax in Language. Mark has over 15 peer-reviewed publications, including articles in Applied Artificial Intelligence and Cognitive Science.