CSE571 Project 3 Solved

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 Intelli- gence: 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

wumpus environment.py

wumpus agent.py

logic.py

search.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.

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.

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.

AIMA code implementing propositional (PL) and first-order (FOL) logic lan- guage 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.

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.

1

Max Pts: 32

Files you likely don’t need to look at:

minisat.py

agents.py
utils.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 Min- iSat, and reading the MiniSat results.

AIMA code for the generic Agent and Environment framework. NOTE: this file is slightly modified from the original AIMA release.

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 as- signment. 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.

Evaluation: Your code will be graded using several difference environment layouts (note: some of them are not provided). Please do not change the names of any provided functions or classes within the code. However, the correctness of your implementation will be the final judge of your score. If necessary, we will review and grade assignments individually to ensure that you receive due credit for your work.

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.

Getting Help: You are not alone! If you find yourself stuck on something, contact us, come to office hours and/or post issues on Piazza. We want these projects to be rewarding and instructional, not frustrating and demoralizing. But, we don’t know when or how to help unless you ask. One more piece of advice: if you don’t know what a variable does or what kind of values it takes, print it out.

Discussion: Please be careful not to post spoilers.

2

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.

PL sentences expressed in full propositional logic are sentences that may include all of the standard PL connectives: And/Conjunction (‘&’), Or/Disjunction (‘|’), Not/Negation (‘∼’), Implication (‘>>’), and Biconditional (‘<=>’) (see logic.py for full details about the PL python implementation). In the context of providing full PL sentences to the KB as rules for updating the agent’s knowledge state, we will refer to these sentences as axioms.

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 You may also need to install python-tk: $ 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:
  1. For Windows 10 users: cygwin 32 bit may need to be installed (you may need to uninstall cygwin if you have installed the 64 bit version).
     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.

3

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 4×4 book

4

(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

5

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 fully- implemented 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).

NOTE: While you can construct layout sepcifications (either in layout files or in code) in any dimensions, it is recommend that you follow these general constraints (mainly due to working with the knowledge base; for general manual play without a KB, any size is fine):

• 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

  As the knowledge base and agent planner(s) developer, you have several choices as to how to proceed with develop- ment. The manual command-line interfaces to the wumpus game, defined above and implemented in wumpus.py, were designed to be a way by which you can directly observe the impact of code changes on knowledge base inference and agent behavior. However, you may find some or all development easier by incrementally instantiating and testing parts of the code; in this case, start with the WumpusWorldScenario to see how the main pieces are put together.

6

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.

Be sure to look at the docs for Expr and expr() in logic.py to understand how the PL syntax will be parsed from a string, in particular the note in the docs of expr() about operator precedence: expr(‘P & Q ==> R & S’) will be parsed as ((P & (Q >> R)) & S), which may not be what you intended! To get the expected operator precedence enforced (i.e., & with higher precedence than ==>), you must use expr(‘(P & Q) ==> (R & S)’). In general, it is best to use parentheses to enforce the precedence you intend!

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

7

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 successor- state 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’

8

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()).

9

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.