The Array/HashSearchBackWumpus Family

A Hero for the Wumpus Environment

The ArrayBackSearchWumpus family and the HashSearchBackWumpus family offer some improvements over their ancestors. The most interesting improvement is that it searches for a - hopefully short - way home if it decides it's time to leave the cave.

The strategy for generating a represantation of the environment

The agent invokes its superclasses' capabilities and enlarges them by the following check to discern a wumpus:

• If a stench was perceived at location x/y the following is checked: A wumpus has to be at field x/( y - 1 ) ( i.e. up ) if the following holds:
  • At fields ( x - 1 )/( y - 1 ) and ( x + 1 )/( y - 1 ) a stench was perceived.
  • At field ( x - 1 )/( y - 1 ) a stench was perceived but not at field ( x - 1 )/( y + 1 ).
  • At field( x + 1 )/( y - 1 ) a stench was perceived but not at field ( x + 1 )/( y + 1 ).

  The same deliberation can be taken for the fields that lie at the right, left and down of the current field.

  This line of reasoning is only valid in regard for the wumpus as there can only be one per environment. Therefore the same check for pits could lead to wrong conclusions.

The strategy for generating a new action

The agent decides for its next action by combining the percepts for the current round with his knowledge about the environment. If the new methods are not able to find a satisfying action, the reason capabilities of the ancestor is invoked.

• If a piece of gold was found, the agent starts its search method. If the search method turns up with a valid way home it is checked against the wayback vector ( the part of the agent's 'brain' that holds a way back home ). If the calculated way home is shorter than the way stored in the wayback vector it is taken, otherwise the way stored in the wayback vector is used to return to the exit-field.

The following search strategies have been implemented in agents:

• Depth-First search.
• Depth-Iterated search.
• DepthLimited search.
• Breadth-First search.

Each of those algorithms was enhanced using the 'Manhatten-distance'-metric heuristic which always expands the node that is nearest to the goal-field according to that metric. Therefore the algorithms belong to the family of the so-called 'greedy' search algorithms.

The only difference in the above listed agents is the time it takes for them for finding a solution and the amount of memory used to find a solution.

A demonstration shows how one menber of the ArraySearchBackWumpus family and one member of the HashSearchBackWumpus family fare in the Wumpus environment.

Navigation:

• Back to the agent intro.
• Go to the Wumpus main page

Last modified: Sa. June 06 14:34:54 1997 by Christian Schwaiger

email to: webmaster@kr.tuwien.ac.at