Navigation, Cooperation and Language Tutorial

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.

Authors' background:

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,

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

* ACAI-01: Machine Learning and Inductive Logic Programming for
  Multi-Agent Systems (with Daniel Kudenko)

* ECAI-02: Machine  Learning for Agents and  Multi-Agent Systems (with
  Daniel Kudenko)

* ESSLLI-04: Symbolic Learning of Language (with James Cussens),

He is also the organiser of  the Navigation Debate at the UK AISB 2006

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.