Table of contents
Description
(Most of this text has been written by Jean-Christophe Bouramoué; for more details, especially theoretical foundations and proofs of this approach, see this page).
The N-puzzle is a classical example illustrating how artificial intelligence can be used for problem solving applications. The traditional method consists in covering a number of different states. The state of the N-puzzle is represented by the position of all of its tiles at one given point. The total number of states is the number of states which can be accessed from the initial state. Two, three or four states can be directly accessed from one given state based on the position of the blank ( the "empty patch"). The problem therefore boils down to that of a tree ( AO* type algorithm) with two to four sons per node.
To eliminate some sons, a heuristic will be used. For example, one may choose the son for which the sum of the Manhattan distances ( rectangular distance) for each tile from its position to its final state is the lowest.
There are three majors drawbacks to this approach :
- The number of sons grows exponentially with the number of transitions ( tile moves).
- When a node is reached with no interesting state for the chosen heuristic, it is necessary to backtrack, which is costly in execution time and memory.
- When there are disturbances, that is to say a change of state due to an outside agent ( an evil user!), it is necessary to start all over again from a new state.
Eco-Problem-Solving is an interesting alternative to solve the problem of the N-puzzle. It enables to avoid the drawbacks mentionned above and introduces elements of self-organisation which are particularly effective.
Implementation
a / Linking the Subgoals
Tiles cannot get satisfied at the same time ( there is one blank, so tiles cannot move concurrently !). Therefore it is necessary to order the subgoals.
 |
 |
The main idea is simple ( see figure above) and has been implemented (in the Smalltalk implementation) as another EPS application:
- patch[0][3] ( top right corner : row 0, column 3 ) : its goal is the N-puzzle
- Tile number 4 : its goal is patch[0][3]
- patch[0][2] : its goal is tile number 4
- tile number 3 : its goal is patch[0][2] ....etc.....
- blank : its goal is patch[0][3]
- N-puzzle :its goal is the blank
This linking enables to progressively reduce the size of the N-puzzle ( down to a size 2 N-puzzle).
b / Blocking the patches
It is essential, for the attacking agent ( ever when trying to get satisfied or trying to escape) to block the patch on which it is positionned : it prevents the attacked agent from attacking its own attacker ( except if it hasn't any other choice).
c / Looking for place
the EcoTile class has intelligent methods which enables its instances to find a place ( which means a patch) to escape or to get satisfied without making useless moves :
- To escape : among the adjacent patches, take the closest to the blank, taking into account the blocked patches ( there is still the possibility to escape onto the goal if it is adjacent and it is not blocked).
- To get satisfied : among the adjacent patches, take the closest to the goal. If there are several, take the closest to the blank ( taking into account the blocked patches).
Remark : These heuristic choices are not strictly a part of eco-problem-solving.
d / Forbidding patches
It's interesting to, little by little, reduce the size of the problem. Our goal linking took into account the fact that once all patches of one row and its symetrical column are satisfied, the N-puzzle moves from size n to size n - 1 .
e / Transmitting constraints among the tiles
There are two types of attacks for the tiles :
- Attacking to get satisfied : there are two possibilities.
- The attackers goal is not adjacent. In that case, the attacker asks the attacked not to escape to its goal. So, the attacker's goal is the constraint that the escaper must respect, that is to say avoid ( the constraint is, in fact, transmitted as an argument of the satisfactionAgression() method ).
- The attacker's goal is adjacent. Then, the constraint is less obvious. It is provided by the attacker's findConstraintForSatisfaction method : it can be the patch preceding the attacker's goal ( in the linking order chosen - i.e paragraph a/, it's the conservation principle) or else the patch on which the attacker is positionned.
- Attacking to escape : In that case, the constraint is simply the patch which the agent has chosen to escape to. With the N-puzzle, contrary to the Blocks' World, the attacked is always on the patch the tile has chosen to escape to.
It is important to notice the difference between the two types of attack. In the first case, the agent is pickier on the choice of the place. In the second case, it is more of an emergency solution ( dictated by the necessity to escape). The weaker constraints in the second case enable to avoid the loops : When an attacker, trying to get satisfied, has launched a series of calls to fleeAgression() method ( which has created a loop), it won't have the same constraints when it is its turn to escape. In other words, the attacker, when attacked, takes the shorter escape before doing another satisfactionAgression() . This behaviour is illustrated in the examples below.
f / Examples of agent's behaviour - The case of corners
Example 1 :
fig1 |
fig2 |
fig3 |
fig4 |
Tile number 1 attacks 5 ( which is its goal). findConstraintForSatisfaction() return the patch on which tile 2 is positionned. 5 attacks 1 which escapes ( fig. 1 & 2 ) . 1 attacks 5 again. The constraint given by 1 to 5 is not to escape to its goal ( which is occupied by the blank : see fig. 3).
fig5 |
fig6 |
fig7 |
fig8 |
1 moves on to patch[1][0] ( fig. 4 & 5 ) and attacks 2 to get satisfied. 2 attacks 3. 3 doesn't escape onto the blank ( although it is adjacent) but onto its goal because it is adjacent, satisfied and it is not blocked ( see paragraph 4.2.c/ Looking for place ). Therefore it is tile 8 and 4 which are attacked (fig. 6).
4 gets satisfied (fig. 7).
fig9 |
fig10 |
fig11 |
fig12 |
7's satisfaction follows the same process as that of 1( charts 8, 9, 10, 11 and 12). 7 gets satisfied. Row and column 0 are then forbidden .
fig13 |
fig14 |
Example 2 :
fig1bis |
fig2bis |
fig3bis |
fig4bis |
1 attacks 5 whose only choice is to attack 5 again ( same reason as before). 1 escapes to patch[2][0] and attacks 5 again ( fig. 1bis & 2bis). 1's is not being adjacent this time, so the constraint given to 5 is to avoid patch[0][0] ( which is 1's goal). The patches which are attacked one after the other are therefore patches under tiles 5, 6 and 2 ( fig. 3bis).
fig5bis |
fig6bis |
1 moves to patch[1][0], blocks its patch and attacks 2, which attacks 6, which attacks 5, which attacks 7 ( fig. 4bis). It can be noticed that the patches which are choosen for an escape are always the closest to the blank ( taking into account the fact that patch[1][0] is blocked ). 1 gets satisfied by filling in row number 0.
Remark : It can be noted, from these examples, that corners are not particular cases . The satisfactionAgression() and fleeAgression() arguments are the same as for tiles which are in the middle of the N-puzzle. The constraints are good enough for the tiles to get out of a seemingly more difficult situation.
Note on the Graphical User Interface:
The execution time can be adjusted ( "Speed" item) and EPS can be started by pressing the Run button ..
The Stop button can be used to disturb ( with the mouse) the N-puzzle by interrupting the game. The N-puzzle can then restart from the new initial state by recreating the list of dependents. The color of the tiles is an indication of their state :
- Red : the tile is in the process of attacking to get satisfied.
- Dark gray :the tile is satisfied.
- Pink :the tile is trying to escape.
- Light gray :the tile doesn't have an assigned goal yet or its goal hasn't been satisfied yet.
- Black :the tile is on a forbidden patch (it belongs to a row or a column entirely satisfied).