Description

CptS 440/540 Artificial Intelligence
Homework 5

For this homework you will implement a search-based agent to play the Wumpus World game. The file “wumpus-search.zip” that accompanies this homework provides an A* search, but you will need to implement the heuristic function. The search algorithm is implemented in the files Search.h, Search.cc and Search.py. The zip file also includes modified Agent.h, Agent.cc and Agent.py files that demonstrate the use of the search capability. Copy all these files, including the updated Makefile, to a copy of the simulator code and recompile to use the search capability. You will mainly need to use the following three methods of the SearchEngine class:
• AddSafeLocation(x,y) – Adds a location to the search engine’s list of safe locations. The search engine considers only safe locations in its solution.
• RemoveSafeLocation(x,y) – Removes a safe location from the search engine’s list of safe locations (e.g., in case a previously-thought safe location turns out to be unsafe).
• FindPath(startLocation,startOrientation,goalLocation,goalOrientation) – Returns a list of actions to get from the start state to the goal state. If no safe path is possible, then returns an empty list.

Your agent should do the following (and only the following).

1. Implement the class MySearchEngine derived from the provided SearchEngine class. Your MySearchEngine class only needs to implement the HeuristicFunction method. This method should compute the city-block distance between the locations in the given state and goalState arguments. See the SearchState class for how to access the location of a state.
2. In addition to the agent’s state information, you should also keep track of the gold location, visited locations, and safe locations, as this information becomes known. You will be playing each world for multiple tries, so keeping track of what you learned from previous tries is useful (and required).
3. You should update location information as you visit new locations:
a. If you perceive a glitter, then set gold location to current location.
b. Add current location to safe locations. If no breeze or stench, then add adjacent locations to safe locations.
1
c. Add current location to visited locations.
d. If your agent dies from doing a GoForward into a pit or the Wumpus, then update safe locations accordingly.
4. If you perceive a glitter, then Grab.
5. If you have the gold and are in the (1,1) location, then Climb.
6. If you know the gold’s location, and you don’t have the gold, then use the search engine to find a sequence of actions to get there.
7. If you have the gold, but aren’t in the (1,1) location, then use the search engine to find a sequence of actions to get to (1,1).
8. Otherwise, determine a safe unvisited location and use the search engine to find a sequence of actions to get there.

The test worlds will adhere to the following constraints:
• The world size can vary from 3×3 to 9×9.
• The gold will never be co-located with the Wumpus or a pit.
• There will always be a safe path to the gold that does not require shooting the Wumpus.

2