Project #1
Wumpus World
Due 9/18/98
Background
Lisp is used for a large part in Artificial Intelligence problems. To give you a sense of solving a real problem using Lisp, we will be doing several homeworks relating to the a classic AI problem, the Wumpus World.
The Wumpus World problem is a straightforward logical reasoning agent problem. Okay, that's a mouthful. All that means is that you write an agent, which is formally defined as "something which perceives and acts," to reason out the solution to a problem based on some simple information about the world. (Russel, 7)
In the Wumpus World, your agent is an intrepid explorer seeking to obtain the treasure in the lair of the large, hairy and smelly Wumpus, who will swallow your agent with one gulp. To make matters slightly worse, there are several bottomless pits strewn about. Fortunately for the Wumpus, he is too large to fall down these, but unfortunately for you they are quite large enough to engulf your agent's puny body.
But never fear, your agent is very observant, and can detect a breeze blowing out of the pits, and can smell the Wumpus from quite far away. And should you meet the Wumpus, you are equipped with your trusty bow and... an arrow. Well, who needs more than one shot?
Formally, the Wumpus world is given as a grid of squares. Each square may contain one of several percepts. Percepts are simple facts about the square you are in; for example you may sense a breeze. Each square has some subset of the following percepts:
(Stench, Breeze, Glitter, Bump, Scream, Death)
A Stench means the Wumpus is in an adjoining square (not diagonally). A Breeze indicates the presence of a pit, simliarly. A Glitter indicates that the current square contains gold. A Bump means you walked into a wall. A Scream is heard if you successfully kill the Wumpus with your arrow. It takes a long time to die, and you can hear it throughout the cave. Death means, well, death.
There are several actions your agent can take:
(Forward, left, right, shoot, grab, climb)
Forward means to move one space forward in the direction you are facing. Left means to turn left 90°. Right means turn right 90°. Shoot means to fire your arrow (which proceeds straight in your current direction). Grab means try to pick up treasure (if present). Climb means to climb out of the cave (if you're at the entrance).
Your agent's goal is to reason out where the pits are, where the Wumpus is, so as to get to the treasure without getting killed.
A sample Wumpus World is shown in Figure 1.
Your Task
You have several tasks for this phase of the project. We will (hopefully) reuse some of our code as we develop our agent throughout the course.
Step 1: Develop a reasonable file format to hold a Wumpus World. Your format should support a World of any square size, any number of pits, and at least one Wumpus. The adventurer always starts in square 1,1 the lower left hand corner, so there is no need to store this.
Step 2: Write a Lisp function to read in a Wumpus world from a file and return an well-choosen data structure containing the Wumpus world.
Step 3: Write a Lisp function to display the Wumpus world to the user (yes, this is a side effect, but needed). Your display need not be graphic -- simple nice text will work. REALLY nice displays may receive extra points. It should, as a parameter, be able to display either the entire world or just the explored world. The percepts for each explored square should be visible. (Print a key, if needed).
Step 4: Write a Lisp function to take an action by the agent and alter the world state accordingly. Note the distinction between the world state and the agent's knowledge of the world. For example, the world state includes knowledge of the agent's position. This should change if a move is enacted. Note that this function should tell us of the agent's death...
Step 5: Write a Lisp program to call the above functions and others to enable the user to play a game of Wumpus World. This should have two modes, debug and normal. In debug mode, the player should be able to see the entire world. In normal mode, only the explored world should be visible.
Grading
Functionality: 50%
Design Choices: 30%
Documentation: 10%
Coding: 10%
Functionality refers to the question: does the program do what it is supposed to, somehow, someway? Design choices asks the question, does it do what it is supposed to intelligently? Documentation asks: is the code sufficiently commented? Coding asks: is the program in good Lisp style, i.e. does it use functional programming and recursion rather than traditional methods?
References
Russell, Stuart and Norvig, Peter. Artificial Intelligence: A Modern Approach, Prentice Hall, 1995. ISBN 0-13-103805-2.