CSE571 Project 3 Solution

Make sure to download the project from Canvas/Files/Project folder.
Introduction
A total of 32 points can be earned over the course of this project. In this project, you will build a propositional logic (PL) agent capable of solving a variant of the Hunt The Wumpus game. This will include constructing the agent’s knowledge base and implementing simple search routines the agent uses for planning.
The code for this project consists of several Python files, some of which you will need to read and understand in order to complete the assignment, and some of which you can mostly ignore.
NOTE: The abbreviation AIMA used below refers to the Stuart Russell and Peter Norvig’s book Artificial Intelligence: A Modern Approach, 3rd Edition, as well as the associated python code available from their AIMA Github repository (However, all files needed for Project 3 are included in the zip archive; do not replace the files here with the AIMA files as a few of them are slightly modified).
Files you will edit and submit:
wumpus kb.py Contains code to generate the wumpus knowledge base. You need to fill in most of these functions!
wumpus planners.py Contains code to perform plan route and plan shot. You need to fill in code to implement the PlanRouteProblem and PlanShotProblem. See search.py for Problem parent class and examples.
Files you will likely want to look at:
wumpus.py The main file to execute the Hunt The Wumpus game. Contains code for generating WumpusWorldScenarios that combine a WumpusEnvironment and agent (either Explorer or HybridWumpusAgent) to play the game. Includes agent programs to drive game play manually (with and without a knowledge base). Also includes main command-line interface.
wumpus environment.py Implements main classes of the wumpus domain. The Explorer agent is a simple wumpus hunter agent that does not have a knowledge base. The WumpusEnvironment implements the physics and game play of the Hunt The Wumpus game.
wumpus agent.py Defines the HybridWumpusAgent (extends Explorer). This agent includes a knowledge base. The agent program implements a hierarchy of reflexes that are executed depending on the percepts and knowledge state. This includes calls to plan route and plan shot that you will implement in wumpus planners.py.
logic.py AIMA code implementing propositional (PL) and first-order (FOL) logic language components and various inference algorithms. You will want to look at the relevant PL implementation. NOTE: This file is slightly modified from the current AIMA release.
search.py AIMA code setting up basic search facilities; includes Problem class that
you will implement in wumpus planners.py for plan route and plan shot. NOTE: this file is slightly modified from the current AIMA release.
Files you likely don’t need to look at:
minisat.py Implements the interface to MiniSat, including translating AIMA PL clauses into DIMACS CNF, generating the DIMACS file read by MiniSat, using python’s sys interface to call MiniSat, and reading the MiniSat results.
agents.py AIMA code for the generic Agent and Environment framework. NOTE: this file is slightly modified from the original AIMA release.
utils.py AIMA code providing utilities used by other AIMA modules. NOTE: this file is slightly modified from the original AIMA release.
Files to Edit and Submit: You will fill in portions of wumpus kb.py and wumpus planners.py during the assignment. You should submit these files with your code and comments. Please do not change the other files in this distribution or submit any of our original files other than these files.
Academic Dishonesty: We will be checking your code against other submissions in the class for logical redundancy. If you copy someone else’s code and submit it with minor changes, we will know. These cheat detectors are quite hard to fool, so please don’t try. If we find any cheating, we will deal with it, as mentioned in the syllabus, with zero tolerance.We trust you all to submit your own work only; please don’t let us down. If you do, we will pursue the strongest consequences available to us.
Discussion: Please be careful not to post spoilers.
Notes on terminology
In the discussion and comments/docs in the code we freely switch between referring to the agent knowledge base, KB, kb and agent.kb. These are all the same thing: the collective facilities for storing propositional logic sentences. Also, we sometimes abbreviate propositional logic as PL.
When PL sentences are added to the KB, they are immediately converted to conjunctive normal form, CNF. This CNF representation is stored in the KB as a list of the individual disjunctive clauses (the list is treated as an implicit conjunction of its member clauses), and we will refer to the clauses in the list collectively as the KB clauses.
Setup: Install MiniSat, download project code, and run test
This project relies on the light weight, open source, cross platform SAT solver MiniSat (http://minisat.se). There are a variety of ways to obtain MiniSat; here are methods for the popular three platforms:
• Mac OS X: install using port (https://www.macports.org/install.php)
(NOTE: Unfortunately minisat is currently unavailable through Homebrew), then $ port install minisat
• Linux: install using source code; or
$ sudo apt-get update
$ sudo apt-get install minisat
$ sudo apt-get update
$ sudo apt-get install python-tk
• Windows: see these instructions.
If you are encountering problems getting minisat to pass all 3 tests on Windows, please try the following variations:
NOTE: Some report that after installing cygwin and the minisat package, the tests fail until the following is changed in minisat.py, line 157: Replace
COMMAND = ‘minisat %s %s > /dev/null’ with
COMMAND = ‘minisat %s %s > ’ + os.devnull or alternatively:
COMMAND = ‘minisat %s %s > NUL’
2. A next option is to try using a linux virtual machine. (Highly recommended!)
After installing MiniSat, download the Project 3 zip archive (wumpus.zip) and unzip it (if you haven’t already), and change to the wumpus directory. You can then test the connection to MiniSat by executing the following from the command-line:
python wumpus.py -t
The three simple tests should pass. If they do not, or you get unexpected behavior, please contact us for help.
Welcome to the Wumpus Caves!
Having verified that the connection to MiniSat works, the next step is to familiarize yourself with the Hunt The Wumpus game. Execute the following at the command-line to play the game:
python wumpus.py
This launches the interactive command-line interface to the game, running in “Manual” mode: you control the wumpus hunting agent. Entering ‘env’ at any point will display an ascii-art representation of the current Wumpus enviroment state. For example, when executed in the first time tick, you will see:

At the top, the current score of the Wumpus hunting agent (in the default manual mode, represented as an <Explorer>) is displayed. The x coordinates of the Wumpus environment are displayed across the row above the grid, and the y coordinates are displayed down the right-side of the grid. Each grid cell represents a wumpus cave room. ‘#’ represents a wall, and ‘W’, ‘P’, and ‘G’ represent the Wumpus, a Pit, and the Gold, respectively. The position of the wumpus hunter agent are represented by ‘∧’, ‘>’, ‘∨’, and ‘<’, each of which show the direction (heading) the hunter agent is currently facing. At the start, the agent is in location (1,1).
Enter ‘?’ at any time to see a complete list of commands.
The goal of the game is to achieve the highest score. Each move costs one point, shooting the arrow (irrespective of whether it kills the Wumpus) costs 10 points, and leaving the caves (accomplished by executing ‘Climb’ in the same location that the hunter agent started in (the cave ‘entrance’) with the Gold (i.e., having previously successfully ‘Grab’bed the Gold), earns 1000 points. Dying, by entering a square with the Wumpus or a Pit, costs 1000 points.
At each time step, the current percepts are represented by a list of the percept propositions (‘∼’ represents that the proposition is currently False). For example, at time 0 (indicated in the brackets on the left) the percepts for the environment depicted above are:
[0] You perceive: [‘∼Stench’, ‘∼Breeze’, ‘∼Glitter’, ‘∼Bump’, ‘∼Scream’]
Play several games and see how the Wumpus environment state determines the percepts. Try dying by moving into the Wumpus square or a Pit. Shoot the Wumpus: you must execute ‘Shoot’ while facing the Wumpus; when successful, the Wumpus will die and the following time step you will perceive the ‘Scream’; also note that the Wumpus is no longer represented by ‘W’, instead replaced by an ‘X’. It is now safe to move into the Wumpus square. Also solve the game by moving to the Gold, executing ‘Grab’, and move back to the exit/entrance and execute ‘Climb’.
You can load different Wumpus environment layouts by specifying either the name of an existing layout in the wumpus/layouts/ directory (currently there are only two provided), or by specifying the path to a layout, using this command-line option:
python wumpus.py -l wumpus 4x4 book
(You can optionally specify the layout extension ‘.lay’.) The format of a layout specification file is very simple; here’s an example:
. , . , . , .
W , G , P , .
. , . , . , .
A , . , P , .
The file format specifies the Wumpus environment grid as a series of comma-separated wumpus-room specifications, with each row representing a row of rooms in the Wumpus environment. ‘.’ represents an empty wumpus room, ‘W’ places a Wumpus (the knowledge base you will create below can only accommodate presence of exactly 1 Wumpus, no more or less, but in the manual game you can have multiple Wumpi), ‘P’ places a Pit, ‘G’ places the Gold (again, the KB will only support Grabbing 1 Gold), and ‘A’ is the location of the Wumpus hunting Agent (The Agent’s heading is specified separately in code; North, or ‘∧’, is the default). You can also add Walls, represented by ‘#’. By default, the specified layout will be automatically surrounded by Walls when the Wumpus environment is constructed.
Take a look at the code comments and examples in wumpus.py to see how to construct a WumpusWorldScenario from a layout file or by specifying directly in code by constructing objects and assigning them to Wumpus environment locations.
General comments about the code structure and command-line options
There are two main classes that together make a working version of the Hunt the Wumpus game: the WumpusEnvironment and an instance of an agent are combined in a WumpusWorldScenario, defined in wumpus.py.
• The WumpusEnvironment, defined in wumpus environment.py, represents the Wumpus cave environment, the position and state of all objects, and enforces the rules of the game (the game ‘physics’), such as the effects of agent actions. The step() method advances the game one time step and includes calling the Wumpus hunter agent’s agent program.
• There are two classes that define Wumpus hunter agents. The Explorer, also defined in wumpus environment.py, provides a minimal hunter agent skeleton, while the HybridWumpusAgent, defined in wumpus agent.py, is a full agent implementation and includes a knowledge base and set of reflexes sufficient to solve any Hunt the Wumpus game (once you provide some code).
The main action of a wumpus hunter agent happens in its agent program. There are three different agent programs provided:
1. The function with manual program (in wumpus.py) takes an agent as input and replaces its agent program with a “manual” agent program in which the agent waits for commands from the command-line at each step. This is the agent that is run when launching the game from the command-line with (with or without the ‘-l’ layout file option): python wumpus.py
This version is most useful for playing the game and verifying you understand the “physics” of the Wumpus environment (i.e., the effects of actions of states of the world and subsequent percepts).
2. The function with manual kb program (also in wumpus.py) works similar to with manual program except the agent also creates a knowledge base and the agent program updates a knowledge base with new percepts and the action selected (by the human user) at each step. The user can also issue any relevant query about propositions in the knowledge base. This option is most useful for developing and debugging the axioms you provide for initializing and updating the knowledge-based. You will implement these axioms in the axiom generators in wumpus kb.py. Until these axiom generators are implemented, your KB will not be fully functional. The with manual kb program agent program can be run by executing the following from the command-line (inside the wumpus/ directory): python wumpus.py -k
(You can also combine this with the ‘-l’ option to load a specific layout.) Once launched, enter ‘?’ to get the list of commands and complete list of available knowledge base queries.
3. The HybridWumpusAgent (HWA) class is defined in wumpus agent.py (it is a subclass of the Explorer). The HWA defines an agent program that implements the Wumpus agent as specified in Figure 7.20, page 270 of AIMA. Once you have correctly implemented the knowledge base axiom generators (in wumpus kb.py), and the PlanRouteProblem and PlanShotProblem methods (all in wumpus planners.py), the HWA agent program will be able to solve any (solvable) instance of the Hunt The Wumpus game. The HWA and its agent program can be run from the command-line (inside the wumpus/ directory) with:
python wumpus.py -y
(Again, you can also combine this with the ‘-l’ option; however, ‘-y’ option will override the ‘-k’ option, if included). When run, the HWA agent program will select all actions, so there is nothing for the human user to do but watch. As with the above options, the output to screen is intentionally very verbose so that you can follow along with each step in the execution.
To see what “correct” behavior should look like, we have provided the output of two runs of the fullyimplemented HWA, running on the two provided layouts: HWA lay book run.txt and HWA lay 2 run.txt.
Also note that the number of clauses in the KB grows as the agent takes actions in the environment. This is expected: at each time step, new axioms are added to the knowledge base in order to represent change (based on percepts and actions).
• Do not create environments smaller than two rooms, as the knowledge base assumes there is 1 and only 1 Wumpus, so a 1-room cave would necessarily put the Wumpus in the same location as the entrance, leading to a contradiction!
• Do not create environments greater than 16 rooms, as the KB will grow in size too quickly and inference will bog down.)
Development
Propositional logic in python
The two agent programs you will be working with (found either in with manual kb program in wumpus.py or the HybridWumpusAgent (HWA) class defined in wumpus agent.py) make use of the PropKB SAT knowledge base. This is defined in wumpus agent.py and is a subclass the PropKB class defined in logic.py. As you’ll see, these are actually quite simple, implementing the tell() method to add new sentences to the knowledge base, and the ask() method to query the knowledge base (ask() is an interface MiniSat). Assertions made to the knowledge base (often starting as PL syntax expressed in a string) are stored in the clauses field of the KB, and that is just a python list! (Robust implementations of propositional KBs have much more sophisticated storage). Representation of the assertions (sentences) themselves are built on top of the AIMA implementation of propositional logic. As you will be implementing axiom generators, it is important you understand how propositional sentences, initially expressed in strings, are turned into the underlying propositional logic representations. Take a look in logic.py. In particular, the following excerpt from the python prompt demonstrates some of the basic functionality.
In [1]: import logic
In [2]: a = ‘(A & B) >> ( ∼(C | D) <=> E )’
In [3]: e = logic.expr(a)
In [4]: e
Out[4]: ((A & B) >> (∼(C | D) <=> E))
In [5]: c = logic.to cnf(e)
In [6]: c
Out[6]: ((∼C | ∼E | ∼A | ∼B) & (∼D | ∼E | ∼A | ∼B) & (E | C | D | ∼A | ∼B))
In [7]: logic.conjuncts(c)
Out[7]: [(∼C | ∼E | ∼A | ∼B), (∼D | ∼E | ∼A | ∼B), (E | C | D | ∼A | ∼B)]
On line 2, a propositional sentence is expressed in a string, in the syntax of the AIMA propositional language. (Note: you can use either ‘>>’ or ‘==>’ for implication in the string.) See the Expr class in logic.py. The function expr() parses that string and builds an Expr. The Expr object is designed to have a “pretty” python representation, an example of which is on line 4 above (this is accomplished by the definition of the repr () method in Expr; see this explanation). But keep in mind that this is an object in Python! It has two main fields: the operator, op, and a list of arguments to the operator, args. Since the variable e currently references the Expr, we can inspect the op and args as follows:
In [10]: e.op
Out[10]: ‘>>’
In [11]: e.args
Out[11]: [(A & B), (∼(C | D) <=> E)]
This shows that the Expr e refers to has as its operator the implication symbol, and its args have two entries, the first being the antecedent to the implication, in this case A & B, and the second is the consequent, ∼(C | D) <=> E. Each of these are also Exprs, with the first having the conjunction operator, ‘&’, with two args A and B. In this way, our original Expr referred to by e is actually the root of an Expr tree, allowing for representation of arbitrarily complex sentences.
Moving on with the original example, on line 5 we convert the full PL sentence into conjunctive normal form using the to cnf() function; line 6 shows the result. This is still an Expr object; also it is completely logically equivalent to the previous form expressed on lines 2 and 4. Whenever an Expr is tell()ed to the KB, the Expr will be converted to CNF. Then the conjuncts of the CNF will be extracted so that what is stored in the clauses store of the KB is a list of the individual clauses of the CNF. This is demonstrated on line 7.
Finally, a note about the use of MiniSat. MiniSat is a SAT solver, meaning that it searches for the a satisfying assignment to a set of CNF clauses, return True if such an assignment is found (and in MiniSat’s case, it also returns the satisfying assignment), or False if no assignment is found. This is a good building block but not by itself sufficient for propositional inference. In our case, we will not be doing full proposition inference, but instead asking whether individual propositions are entailed (True) or not (False) by the KB, or whether their truth cannot be determined. In order to determine which of these three possible outcomes is the case, the ask() method of PropKB SAT make two calls to minisat, one which which the query variable (the proposition who’s truth we’re trying to determine) is assumed to be True, and one where it is assume to be False, and in both cases minisat determines whether that assertion conjuncted with all of the clauses in the KB is satisfiable. If the clauses + query are satisfiable in both cases, then that means the KB cannot determine whether the proposition is True or False. On the other hand, if one call to minisat is satisfiable, but the other not, then the proposition’s truth is which of the calls was satisfiable. In general you won’t have to worry about these details, but it is important to understand how this is working!
Construct the knowledge base
OK, time to get to work! The first set of tasks is to fill in the axiom generators for the knowledge base. For this part of the project you will work in wumpus kb.py, adding your code to all locations indicated by "*** YOUR CODE HERE ***". You will notice a pattern here, all of the methods you are implementing start with “axiom generator ···” in their name. The doc strings to these functions describe the knowledge that you need to assert in propositional logic, with explanations of what the function arguments represent. The return values are assumed to be strings representing the PL assertions.
Section 7.7 of AIMA, starting on page 265, is a good guide for a number of the axioms you are required to implement. But beware, it is incomplete!
After the current percept sentence generator (which converts percept vectors into a sentence asserting percept propositions), there are two general classes of axiom generators you will construct: a set that generate axioms describing the initial state of knowledge, and axioms that represent changes over time (in particular, the successorstate axioms).
The assertions your generators will make will be built out of propositions. The first section of wumpus kb.py defines every proposition that will appear in the KB. Because it would be very easy to add a malformed proposition symbol to the KB without knowing it, we have provided a set of proposition string builder functions, one for each type of proposition. Even though it is more verbose to use function calls like percept breeze str(3) rather than just ‘Breeze3’, you’ll be better off, as the KB itself won’t tell you if you happened to have mistakenly asserted ‘Breez3’ (that’s a misspelling!) – the KB will happily accept it and you’ll be left to find your mistake through painful debugging! However, the choice is entirely up to you – nothing about the grading will check whether you use these string-builders.
You will be working a lot with strings in this part of the project. Here are general python string functions that we found useful while building my solution:
• The plus sign is overloaded: ‘a’ + ‘b’ results in ‘ab’
• The join method is very handy; the first string the join being called on will be inserted between the listed strings being joined (use an empty string to just concatenate the list of strings):
◦ ‘’.join([‘a’,‘b’,‘c’]) results in ‘abc’
◦ ‘-’.join([‘a’,‘b’,‘c’]) results in ‘a-b-c’
• The format method is your friend: ‘string with {0}{1}’.format(‘stu’, ‘ff’) results in ‘string with stuff’
Points will be awarded, pending correct implementation, as follows (for a total of 24 points):
• axiom generator percept sentence = 1 pt
• axiom generator initial location assertions = 0.5 pt
• axiom generator pits and breezes = 1 pt
• axiom generator wumpus and stench = 1 pt
• axiom generator at least one wumpus = 1 pt
• axiom generator at most one wumpus = 1 pt
• axiom generator only in one location = 1 pt
• axiom generator only one heading = 1 pt
• axiom generator have arrow and wumpus alive = 0.5 pt
• axiom generator location OK = 1 pt
• axiom generator breeze percept and location property = 1 pt
• axiom generator stench percept and location property = 1 pt
• axiom generator at location ssa = 4 pts
• axiom generator have arrow ssa = 1 pt
• axiom generator wumpus alive ssa = 1 pt
• axiom generator heading north,east,south,west ssa = 3 pts (for the set)
• axiom generator heading only north,east,south,west = 2 pts (for the set)
• axiom generator only one action axioms = 2 pts
NOTE: While you are constructing the knowledge base generators, the KB should always be satisfiable. If it ever becomes unsat, then something you have added is leading to a contradiction! That is always a problem. To check for satisfiability of the KB, call the minisat() function in wumpus agent.py with just the KB clauses, e.g., minisat(kb.clauses); when running the wumpus.py with a KB (option -k) from the command-line, you can enter the ‘kbsat’ command to do the same thing. Note, however, that just because the KB is satsifiable does not mean there are not other problems.
Implement route and shot planning
The second major task of Project 3 is to complete the implementation of the route and shot planning for the Hybrid Wumpus Agent. Your coding will take place in wumpus planners.py. The docs for plan route and plan shot outline the problem, but the code to be added will be in the PlanRouteProblem and PlanShotProblem classes, both of which extend the search Problem class (defined in search.py) that serves as the interface to the AIMA search code.
The goal test in both problems is initially set to always return True, and both plan route and plan shot will return empty action lists if finding a solution fails. This allows you to run the full Hybrid Wumpus Agent even before these planning facilities are implemented, but obviously you’ll be changing things.
Once implemented, both plan route and plan shot will use the AIMA implementation of A*, which is also defined in search.py (as astar search()).
It is recommended that you implement PlanRouteProblem first, as much of the solution there can be used in PlanShotProblem. Remember, for the PlanShotProblem, you only need to plan a path to the closest location in which you will be facing the Wumpus.
As noted in plan route and plan shot, the representation of a state is a triple representing the x, y location and heading, of the agent. The heading is an integer of 0, 1, 2, or 3, representing North, West, South, and East, respectively. Goals and allowed states, however, ignore heading, and thus are just lists of x,y tuples.
manhattan distance with heading() has been provided; as the name suggests, it computes the Manhattan distance, but also adds in the cost of having to change the heading (i.e., turn to the correct orientation) before following the Manhattan path.
Correct implementation of each search problems is worth 4 points each, for a total of 8 points.
Submission
Please submit ONLY wumpus kb.py and wumpus planners.py in ONE zip file to Canvas. Please verify if you have directly zipped wumpus kb.py and wumpus planners.py and NOT put them in a folder before zipping it.
The file name should be your ASUID.zip, for instance, if your ASUID is 1234567890, the file name should be 1234567890.zip. Failure to make the correct file format will cause penalty.