Table of Contents
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 :
- The desire to be satisfied and the possiblity to attack other agents to do so
- The necessity of escaping when being attacked
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:
- The first one ( called the kernel) is independent from the domain of application. It contains the definition of the abstract class EcoAgent which defines generic methods allowing the instances of its subclasses to satisfy themselves, flee, etc.
- The second module is dependent on the application domain. It is made up of concrete subclasses of the EcoAgent class. The instances of these classes will be the agents that populate the problem. The main methods of these subclasses called by the previous ones, which implement the concrete behaviour of the agents (i.e. how to satisfy itself, how to flee, how to attack, etc.).
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 !
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 Java Kernel (7 Kb - EcoAgent.java)
- The Java implementation of the n-puzzle (17 Kb - Npuzzle.zip)
The following software is not available on the net, but can be obtained by simply sending me a mail :
- The Smalltalk 2.5 and 4.1 Kernels (need Actalk, developed byJean-Pierre Briot)
- The Smalltalk-80 2.5 Image containing Actalk, the Kernel and some examples (Blocks world, Hanoi towers, N-Puzzle, Pengi, etc.)
List of the people who have worked or still work on this project :
- Jacques Ferber - 1989/1991 - inventor of EPS, first examples
- Eric Jacopin - 1989/1992 - formalization and relationships with planning
- Alexis Drogoul - 1991/.. - Smalltalk implementation, N-Puzzle, Pengi, relationships with ALife
- Christophe Dubreuil - 1991/1992 - N-Puzzle, Smalltalk implementation
- Stephane Bura - 1991/1992 - Metamodel
- Jean-Christophe Bouramoué - 1997/.. -Java implementation
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.
You might be interested to take a look at these links, in some ways related to EPS, for further information :