Created: 04/15/99 :: Updated:2/2/03 :: Visitors: :: © A. Drogoul 1993-2003 ::

Table of Contents

Description

Eco-Problem-Solving is a different approach to problem solving than the more traditional AI or DAI problem-solving methods used so far. It is strongly related to ALife techniques such as those being studied in Swarm Intelligence or self-organizing systems. Problem solving is seen as the production of stable states in a dynamic system, where evolution is due to the behaviours of simple agents. By "simple" we mean agents that do not make plans but just behave according to their specific program, called eco-behaviour, which is just a combination of "tropisms", i.e. behaviours made of reactions to their environment (including the other agents).

Instead of considering a problem as a whole, we then decompose it into a set of small entities, each being considered as an independant reactive agent with its own goal and its own behaviour (see figure below). This behaviour simply consists in interacting with the other agents to achieve its goal, in a strictly codified way which follows these two simple rules :

As all the problem is described using agents, the goal of an agent will always be another agent (e.g. another block in the blocks' world, a stick in Hanoï towers, etc.). This enables us to describe specific relationships between the agents, called dependencies : an agent will always be dependent on its goal (which means that it will have to wait until its goal is itself satisfied to satisfy itself). It allows us to dynamically (and at any time) have the subgoals being ordered in a correct way. The overall objective (i.e. the solution of the problem) will therefore be achieved when all the agents are satisfied, that is when they all have reached their own goals, and do not have any other agent to attack.

Any EPS application is divided into two main modules:

Defining a set of subclasses respectively provided with this set of methods is all what is needed for describing a problem in EPS. However, as in many Alife applications, the tough work is the experimental study of the resulting collective achievement. Though a good analysis of the problem usually provides the designer with the correct classes of agents, their behaviours have to be determined empirically.

However, incredible results have been obtained in solving some classical problems, such as the famous N-Puzzle, for which we have been able to reach very large sizes (99-Puzzle !) while keeping a very good quality of the solutions (10% above the estimated optimal number of moves).

You might want to try it by yourself : just go to this page and play with the java applet that implements the solving of the N-Puzzle !

Software

The EPS kernel was originally written by Jacques Ferber (and Eric Jacopin) in LISP is 1989, followed by an implementation in Smalltalk-80, realized by Christophe Dubreuil and myself in 1991. The current kernel has been written in Java in 1997 by Jean-Christophe Bouramoué and Jean-François Yoro. The following software is available for downloading :

The following software is not available on the net, but can be obtained by simply sending me a mail :

People

List of the people who have worked or still work on this project :

Related papers

You might be interested to take a look at these papers for further information :

Many other papers concerning EPS are available, but not online. Just send me an e-mail to get those cited in my bibliography.

Related links

You might be interested to take a look at these links, in some ways related to EPS, for further information :