This particular status of artificial intelligence as an experimental platform for theories about intelligence has several positive and negative aspects. On the positive side, one can mention that there are very few, if any, other fields of research where natural science meets human science so vitally and where researchers have as much interest in understanding fellows from other disciplines. This gives a taste for variety and arouses curiosity for other domains in a sometimes shy scientific environment. Further, problems linked with mind, intelligence, or cognition also encourage a feeling of excitement about the importance of discoveries that could be made in the field. And with the slow maturation of complexity theories, system theories and cognitive theories, the (mistaken?) feeling that science is near a revolution of the type described by Thomas S. Kuhn [32] feeds the excitement. On the negative side, the very richness of the field makes it impossible to acquire a perfect overall understanding of the disciplines involved. Due to this, research has to be led with the constant attention not to be pulled into areas of personal incompetence or general ignorance, for example, as was elegantly put by Brooks [6], ``the temptation to introduce artificial intelligence research with a definition of intelligence incurs the danger of deep philosophical regress without recovery''. I have attempted to avoid this trap, even though much of the theoretical work that I will introduce in the early chapters of this thesis has been heavily influenced by my philosophical readings.
To continue with an aspect that I have found difficult to manage over the course of this work, I have to mention the lack of structure in the overall domain. I think this is due to the youth of the field, since no effort to classify and formalize the main problems that must be solved has yet succeeded. Comparing this to mathematics, I have the impression that an endeavor comparable to that of Hilbert or the Bourbaki group in the early twentieth century still needs to be made (of course, mathematics have a history of two thousand years behind them and if computer science was able to structure itself in a comparable way after only sixty years of existence it would be an impressive result). I am hoping that through some of the ideas presented here this problem will be more easily addressed.
This thesis is part of the AXE project, funded by the Swiss national fund for scientific research, in which aspects of massively parallel processing are studied. The overall aim of the AXE project is to provide a foundation and design methodology for evolutive parallel and distributed systems composed of artificial agents. In this global problematic, various aspects have been studied and are still under study, such as on the level of network operating systems (the WOS project [52,45]), programming languages for distributed systems (the STL coordination language [31]), agent communication in distributed systems ([10] or the Saga project [51]) or agent population interactions with sexual and asexual reproduction mechanisms (Bio-machines [35]). The direction in which this thesis is inscribed is in the autonomy and coordination part of the project, where the problem of interactions between agents in a complex environment is addressed.
The ultimate goal of this research is to understand how agents situated in an environment made of an open network of computers can compete, collaborate or simply maintain themselves in order to accomplish their tasks. In order to tackle this question, I have taken the path of understanding how artificial agents relate to their environment. It is in this perspective that I have developed a model of text-based virtual worlds, that have been implemented as EMuds. The EMud model is based on the idea that in order to understand the processes that occur in a computer network, an agent has to be able to adapt to unpredictable symbolic information generated by an environment in which it is embedded. EMuds provide such a framework by describing an environment as a virtual physical dimension in which agents exist and where virtual physical laws can affect the agents. The size of the environments that can be built in an EMud, along with the possibility of integrating multiple interacting agents in these environments make them an ideal platform for experimentation. In view of further extensions of research towards human-machine interfaces, EMuds also allow human agents to coexist and interact with the artificial agents in an EMud.
The problem encountered in artificial intelligence that is descriptive for this overall situation is called the symbol grounding problem. The symbol grounding problem is a problem that initially appears when one studies the relation between the real world and a system that uses some form of model or representation of reality to make decisions about a real world problem. Typically, when an expert system uses an internal representation of symptoms, illnesses and diagnoses to help a practician pronounce a patient's diagnosis or when a mobile robot uses an internal representation of the room it is in to decide how to move about, the representation and the world are two distinct entities. Since this situation appears to be a limiting factor for further development of artificial intelligence techniques, the question is how do these entities relate to each other? Can the symbols manipulated by the computer systems acquire an intrinsic meaning (related to the problem) in the system as opposed to an external meaning bestowed by a human observer of the system.
Now, if the symbol grounding problem is analyzed, there are several new problems in different areas that appear. First of all, why does one require symbols to have an intrinsic meaning? The answer is that if such symbols have no meaning for the system, new situations that were unplanned in the internal representation will be dealt with randomly by the system. A problem for computer science is then to find the best ``random'' choice and this seems to require some form of meaning to be included in the symbols. Secondly, what is meaning actually? Is there an internal and an external meaning, is there meaning without intent and then, what is intentionality? All questions leading to deep philosophical problems. Thirdly, can complete or more accurate representations of the world be used to avoid the problem of meaning? An approach that is often used, but leads to the problem of the observer that is very acute in physics or the problem of closed/open systems that has been studied extensively, with pessimistic results for this approach: there is no closed physical system. What then is the minimal size (minimal level of detail) of an accurate description for an open system? Fourthly, assuming there was a way of bestowing meaning to symbols in a representation, what meaning should the symbols acquire? Should some form of computer psychology be elaborated?
As is evident from these few remarks, any endeavor in which a computer system must make decisions about the real world is faced with far reaching questions that can either be addressed or ignored. In some situations, ignorance works well and in some others, not at all. The frontier is not clear and what is easy to solve for a human being is often intractable to the current state of computer science. We should be reassured that the reverse is also true, I for one have problems with solving 106 multiplications without mistake, but it seems natural for some reason. In this work, I have taken the option to acknowledge these difficulties and attempt to provide a (demystifying) scientific interpretation of meaning for symbol systems. For this purpose, I have sought to maintain a scientific approach to the problem studied by introducing ideas and using them as working hypothesis, although a philosophical perspective to these ideas could also be investigated. I have intentionally used generous reduction in the presentation of the philosophy underlying my personal position in the domain while hopefully giving a satisfying synthesis of the relevant ideas in the field that will situate the work and encourage further reading. On the other hand, since I intend to support the idea that reduction is an important part of understanding, the approach is coherent with the goal.
The goal pursued in chapter three is to hypothesize a model of understanding based on the process of information compression, and to use it as a classification scheme for problem solving algorithms. The chapter begins by a statement of the symbol grounding problem and an overview of previous attempts to solve this problem. It is here suggested that the current formulation of the symbol grounding problem based on an overgeneral sense of meaning makes it unsolvable in its present form. With a definition of meaning based on information compression, the problem becomes tractable. Grounding an agent is then a matter of degrees, where grounding is directly related to the efficiency of an agent's ability to represent environment structures in its own internal representation language. It is argued that the ability of an agent to accurately represent a complex environment with limited ressources through information compression is characteristic of the use of an appropriately expressive internal representation language for the problem faced by the agent. The mesure of algorithmic information is then suggested as an appropriate candidate for mesuring this degree of grounding of an agent. The key idea is to use algorithmic information not as a universal mesure of information content, but as a value calculated for each type of problem and each type of control algorithm so as to be able to compare algorithms by the complexity with which they represent problem environments.
With chapter four, the terminology of artificial intelligence used in the following chapters is clarified or introduced. The notions covered by agents, behaviors and autonomy are first introduced to give a foundation of agent theory. Concepts used when dealing with multiple agents sharing a same environment are then presented with multi-agent systems, interactions and emergence. The second part of the chapter gives an overview of the current practice in artificial intelligence. The subjet matter presented here is used as the basic theory upon which the next chapters are built.
Chapter six describes the EMud environment implemented following the ideas introduced in the preceding chapter and presents its possible uses. In the chapter, the structural components forming an EMud environment are described, followed by an explanation of how the dynamics of these environments are handled. Since the strength of this experimentation model is that it allows the definition of new environments for each experiment, a description of the environment specification procedure is made.
Chapter eight develops a new experimental approach used to highlight fundamental information compression characteristics of an algorithm, in order to support the thesis that the information compression/generalization properties of an algorithm determine its efficiency in dealing with an environment. The first set of experiments uses permutations on the representation of the multiplexer problem to show that the system obtains optimal results in solving the problem as long as the generalization mechanism is able to sucessfully store all the necessary information about the problem within the available ressources of the algorithm. So that even with a large search space, with generalization can produce a mapping of the problem in the limited representation space of the algorithm. As soon as this generalization cannot occur due to incompatible problem representation, the algorithm performance breaks down. It is then shown with a problem where temporal information is required for its resolution that the generalization mechanism is unable to extract the needed information for an optimal solution to the problem and that in this case, random permutations on the static representation of the problem have no noteworthy effect on the efficiency of the algorithm. The conclusion of this chapter is that as was suggested in chapter three, a classification of algorithms based on their compression of information characteristics be made. This can be done by using a similar line of thought as in the calculation of algorithmic information, by determining the total amount of ressources needed by various algorithms to express an optimal solution to various chosen benchmark experiments.
The conclusion in chapter nine reviews the question that were adressed in the thesis, starting by practical aspects of the design of an EMud experiment environment and its implementation. A critical review of the missing components of the implementation follows. An overview of the theoretical problems that were adressed in the work and their tentative answer is then presented, while proposing a future course of study for the actual implementation of the ideas introduced over the course of the first eight chapters.