3.5.3 Smart Wumpass

Smart Wumpus using Influence Maps and ISSAMP

Work in a new directory (2/c) and start by copying your 2/b code into 2/c.

Influence Maps

Look at a map of the earth. Before we explore it, we might know where are the hills and valleys. But we don’t know which oceans have dragons and which ports have labor relation problems. We can only learn that from experience.

So take a second piece of paper- thin paper- and lay it over the first map. Now send 100 ships around the world with orders to mail back locations of dragons, hurricanes, riots, etc. Color the overlay with red for every place something bad happened to one of these explorers.

Now, when the 101-th ship sails off, it takes two maps. One of the earth, and the overlay (which we will call an influence map). Now, when charting a new course, our captain adds together the distance of the trip along with the number of trouble spots meet on the way. The captain, if she is wise, picks the route which minimizes miles and trouble spots.

ISSAMP

ISSAMP (iterative sampler) is a stochastic explorer. At any time, it selects any option at random. If anything goes wrong, ISSAMP aborts and jumps back to the root and starts all over again. Since ISSAMP does not waste time trying to be clever to fix any problem, it can explore more, faster.

ISSAMP and WUMPUS

ISSAMP can be used to iteratively build influence maps. Consider Grand Theft Wumpus, with one addition. Suppose that when our explorer is caught, or dies, they hit a special button on their vest that detonates a stink bomb that spreads N edges from the location of their misfortune. The stink obviously weakens as it spreads so all edges immediately adjacent to capture/death get 0.5 units of stink, all edges adjacent to that get 0.25 units, all edges adjacent to that gets 0.125 (after that, the stink is too faint to smell).

We will assume that this stink is really hard to wash off. It lingers, forever. So the stink for each explorer adds to the stink of all previous ones.

How to do it

So the scenario is this:

• Your family is shamed by you being tricked by the wumpus. Hence, the clan has come to support you.
• One by one they go off into Congestion City. If they are caught, or get captured, you can just hear the sound of their stink vests going off (actually, its the sound of the locals holding their noise and going "phew, yuck, can anyone stop that stink???").
• Each new explorer may stumble across the stink of failure of the prior explorers (the influence map).
• Which means, when they are considering what edge to take next, they can sort possible edges according to their sirens, blood trails, glow and by how much they stink.

To implement this, you need some data structure that stores the amount of stink in each edge.

Then you need to augment the edge sorting heuristics implemented last week such that edge stink changes where our agent walks next. Internally, this will be some multi-utility functions that does feature extraction of each edge (sirens? glow? stink?, whatever, use your creativity) and weights these is some way; e.g.

(defun edgeScore (sirens? glow? stink? etc?)
    "a b c d are weights on different heuristic search measures"
     (+ (* a (if sirens? 1 0) (zip))
        (* b (if glow?   1 0) (zip))
        (* c stink)           (zip))
        (* d etc)             (zip)))

(defun zip ()
    "Returns a random number between 0.99 and 0.999.
     Enables random selection."
    (+ 0.99 (randf 0.009))
)

Then, you need a main driver that sends of explorers, waits for their stink to go off, they adjusts the edge stink weights before the next explorer goes off.

Finally, you need to experiment with your rig:

• Record the number of explorers required before we find the wumpus.
• See how that number is altered by setting different values of a,b,c,d

What to Hand In

All your changed, new, LISP code.

Charts that show which (if any) combinations of a,b,c,d mean we find the wumpus faster.

All stapled up, as usual.

This document was generated on March 1, 2011 using texi2html 5.0.