Full-text

URL: http://arti.vub.ac.be/~bartdv/thesis/evo...ionofconventions.pdf

Related links

Source: http://arti.vub.ac.be/~bartdv/#publications

Web search: Google Web Search   ::   Google Scholar

Within this site: Cited by (2)    References (79)

Abstract

A lot of conventions emerge in gradual stages without being centrally imposed. The most significant and complex example in our human society is undoubtedly human language which evolved according to our need for communication. Also in artificial multi-agent systems, e.g. mobile robots or software agents, it is often desirable that agents can reach a convention in a distributed way. To make this possible, it is important to have a sound grasp of the mechanism by which conventions arise.

In this thesis we define a theoretical framework that enables us to examine this process carefully. We make a strict distinction between the description of the convention problem on the one hand and the solution to this problem in terms of an agent design on the other. A convention problem specifies the preconditions any type of agent must comply with. This includes (i) the space of alternatives from which the convention is to be chosen, (ii) the interaction model between the agents, which determines which agents interact at what time and (iii) the amount, nature and direction of information transmitted between the agents during an interaction. A particular agent design solves a convention problem if a population of such agents will reach an agreement in a reasonable time, under the given restrictions.

We focus on the class of convention problems with a global interaction model: every agent is equally likely to interact with any other agent. We argue that for these convention problems the performance of an agent can be predicted by inspecting the properties of the agent's response function. This response function captures the average behavior of an agent when interacting with agents from a non-changing population.

We apply this analytical technique to different sorts of convention problems. For the more simple convention problems we define general, sufficient properties which guarantee that a convention will arise after a certain amount of time when an agent possesses these. For the more difficult convention problems we confine ourselves to the construction of agents who, we can show, will solve the problem. Finally, our framework is applied to the problem of language evolution in artificial agents. This is a complicated domain for which precise mathematical results are very difficult to obtain. We will focus on the naming game, a relatively simple instance in the paradigm of languages games. In certain instances our analysis will surface problems of convergence that have not been noticed before. This shows on the one hand that it is important to theoretically substantiate computer experiments in language evolution and on the other that the framework introduced in this thesis is very suitable to this extent.

@phdthesis{deVylder07evoltionOfConventionsPHD,
  author={Bart De Vylder},
  title={The Evolution of Conventions in Multi-Agent Systems},
  year={2007},
  school={Artificial Intelligence Laboratory, Vrije Universiteit Brussels},
  url={http://groups.lis.illinois.edu/amag/langev/paper/deVylder07evoltionOfConventionsPHD.html}
}

HOME   ::  PhD Thesis List   ::   Thesis	Comments to: junwang4 you-know-at gmail.com	Last update: 1/11/13