A Wumpus-Pacman game in progress: Pacman stands beside a live ghost with the PKE meter reading on, one trapped ghost sits greyed out under a hazard-striped trap, two more live ghosts lurk, and the status pane reads PKE: ON, TRAPS: 3, GHOSTS LEFT: 3.

Logic and the Hybrid Wumpus Agent

Logic and searching.
Unseen ghosts will soon be trapped.
Spock would be so proud.

Introduction

In this project, your Pacman agent will use propositional logic to hunt ghosts it cannot see. You will first warm up building logic sentences and running them through a SAT solver (Questions 1 and 2). You will then build up, piece by piece, the knowledge base of a hybrid agent: an agent that combines logical inference (to prove which squares are safe) with search-based planning (to decide where to go next). By the end, your agent will explore a Wumpus World-inspired Pacman board, prove where the hidden ghosts are, and trap every one of them, eating food for points along the way, without ever stepping on a square it cannot prove safe.

Download: all the code and supporting files are in logic_plan.zip. Download it, unzip it, and change into the logic_plan directory.

Play the game: the best introduction to the assignment is to play a game of Wumpus-Pacman yourself, right now (move with 'w', 'a', 's', 'd' or the arrow keys; press 't' to toggle trapping mode, and 'v' to reveal the hidden ghosts and food):

python3.12 wumpus.py

The rules of the game are described in The Wumpus-Pacman World section below.

As in previous programming assignments, this assignment includes an autograder for you to grade your answers on your machine. This can be run with the command:

python3.12 autograder.py

See the autograder tutorial in Project 0 for more information about using the autograder.

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

Files you will edit

logicPlan.py Where your logic sentences, knowledge base, and safety inference will reside (Questions 1-5).
hybridAgents.py Where your exploration and hybrid agents will reside (Questions 6-7).

Files you might want to look at

logic.py Propositional logic code originally from https://code.google.com/p/aima-python/ with modifications for our project. There are several useful utility functions for working with logic in here.
wumpus.py The Wumpus-Pacman game itself: rules, percepts, traps, and the command-line interface. The docstring at the top and the GameState.getPercept method are worth reading.
searchUtil.py A* search over safe squares, used by the provided planning helpers in hybridAgents.py.
pycosat_test.py Quick test main function that checks that the pycosat module is installed correctly.
game.py The logic behind how the Pacman world works. The only thing you might want to look at in here is the Grid class.
test_cases/ Directory containing the test cases for each question

Files you will not edit

logic_utils.py Utility functions for logic.py
util.py Utility functions primarily for other projects.
logic_planTestClasses.py Project specific autograding test classes
wumpusDisplay.py Graphics for the Wumpus-Pacman game
wumpusKeyboardAgents.py Keyboard interface to control Pacman in the Wumpus-Pacman game
graphicsUtils.py Support for Pacman graphics
textDisplay.py ASCII graphics for Pacman
ghostAgents.py Agents to control ghosts
layout.py Code for reading layout files and storing their contents
autograder.py Project autograder
testParser.py Parses autograder test and solution files
testClasses.py General autograding test classes

Files to Edit and Submit: You will fill in portions of logicPlan.py and hybridAgents.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.

Evaluation: Your code will be autograded for technical correctness. Please do not change the names of any provided functions or classes within the code, or you will wreak havoc on the autograder. However, the correctness of your implementation, not the autograder's judgements, 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. 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 the course staff for help. Office hours, section, and the discussion forum are there for your support; please use them. If you can't make our office hours, let us know and we will schedule more. 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.

Discussion: Please be careful not to post spoilers.

Assignment FAQ

We have compiled a list of frequently asked questions and common mistakes on various problems in this assignment. Please read this list carefully, and refer back to this before asking any questions on the discussion board.

  • Question 1: Read the PropSymbolExpr class carefully and make sure you know how to construct symbols with indices like G[3,4]
  • Questions 3-5: Positions are 1-indexed, and walls is a Grid (see game.py): walls[x][y] is True if there is a wall at (x, y)
  • Question 3: Only non-wall neighbors may appear in the percept rule: a ghost can never be inside a wall
  • Question 4: Assert only what Pacman actually knows. Adding facts (or percept rules) for squares Pacman has no reading from will fail the tests
  • Question 5: Both entailment checks are satisfiability checks on the negation of what you want to prove; make sure you have the direction right, or SAFE and NOT_SAFE will come out swapped
  • Questions 6-7: The agents receive a percept dict, not a game state. Everything your agent knows must come from the percepts it has stored
  • Question 7: Call self.recordTrap before returning a trap action, or your knowledge base will contradict itself later

The Expr Class

In the first part of this project, you will be working with the Expr class defined in logic.py to build propositional logic sentences. An Expr object is implemented as a tree with logical operators (\(\land, \lor, \neg, \Rightarrow, \Leftrightarrow\)) at each node and with literals (\(A, B, C\)) at the leaves. The sentence

\[ (A \land B) \Leftrightarrow (\neg C \lor D) \]

would be represented as the tree

Example logic tree.

To instantiate a symbol named 'A', call the constructor like this:

A = Expr('A')

The Expr class allows you to use Python operators to build up these expressions. The following are the available Python operators and their meanings:

  • ~A: \(\neg A\)
  • A & B: \(A \land B\)
  • A | B: \(A \lor B\)
  • A >> B: \(A \Rightarrow B\)
  • A % B: \(A \Leftrightarrow B\)

So to build the expression \(A \land B\), you would type this:

A = Expr('A')

B = Expr('B')

a_and_b = A & B

Note: A to the left of the assignment operator in that example is just a Python variable name, i.e. symbol1 = Expr('A') would have worked just as well.)

Important: A & B & C will give the expression ((A & B) & C). If instead you want (A & B & C), as you will for these problems, use logic.conjoin, which takes a list of expressions as input and returns one expression that is the conjunction of all the inputs. The & operator in Python is a binary operator and builds an unbalanced binary tree if you chain it several times, whereas conjoin builds a tree that is one level deep with all the inputs extending directly from the & operator at the root. logic.disjoin is similarly defined for |. The autograder for Question 1 will require that you use logic.conjoin and logic.disjoin wherever you could otherwise chain several & operators or several | operators. If you keep with this convention for later problems, it will help with debugging because you will get more readable expressions.

There is additional, more detailed documentation for the Expr class in logic.py.

Tips

  • When creating a symbol with Expr, it must start with an upper case character. You will get non-obvious errors later if you don't follow this convention.
  • Be careful creating and combining Expr instances. For example, if you intend to create the expression x = Expr('A') & Expr('B'), you don't want to accidentally type x = Expr('A & B'). The former will be a logical expression of the symbol 'A' and the symbol 'B', while the latter will be a single symbol (Expr) named 'A & B'.

SAT Solver Setup

A SAT (satisfiability) solver takes a logic expression which encodes the rules of the world and returns a model (true and false assignments to logic symbols) that satisfies that expression if such a model exists. To efficiently find a possible model from an expression, we take advantage of the pycosat module, which is a Python wrapper around the picoSAT library.

Unfortunately, this requires installing this module/library on each machine.

To install this software in the Andrew Linux servers:

  1. ssh -Y <andrewid>@unix.andrew.cmu.edu
  2. Install pycosat: python3.12 -m pip install --user pycosat --upgrade setuptools There should be no errors.

To install this software on your own machine (Mac and Unix), please follow these steps:

  1. Install pycosat: python3.12 -m pip install pycosat
  2. If the line above does not work try upgrading the set up tools by python3.12 -m pip install --user pycosat --upgrade setuptools

To install this software on your own machine (Windows), please follow these steps:

  1. Install pycosat: python3.12 -m pip install pycosat
  2. If it gives you a Microsoft Visual C++ 14.0 or greater is required. error, visit this link and download MSVC v143 - VS 2022 C++ x64/x86 build tools (Latest) and Windows 10/11 SDK(depending on your system)

Testing pycosat installation:

After unzipping the project code and changing to the project code directory, run:

python3.12 pycosat_test.py

This should output:

[1, -2, -3, -4, 5].

Please let us know if you have issues with this setup. This is critical to completing the project, and we don't want you to spend your time fighting with this installation process.

Question 1 (4 points): Logic Warm-up

This question will give you practice working with logic. The logic.Expr data type used in the project to represent propositional logic sentences.

Fill in the functions sentence1(), sentence2(), and sentence3() in the file logicPlan.py, which ask you to create specific logic.Expr instances.

For sentence1(), create one logic.Expr instance that represents that the following three sentences are true. Do not do any logical simplification, just put them in in this form in this order.

\[ A \lor B \]

\[ \neg A \Leftrightarrow \neg B \lor C \]

\[ \neg A \lor \neg B \lor C \]

For sentence2(), create one logic.Expr instance that represents that the following four sentences are true. Again, do not do any logical simplification, just put them in in this form in this order.

\[ C \Leftrightarrow B \lor D \]

\[ A \Rightarrow \neg B \land \neg D \]

\[ \neg (B \land \neg C) \Rightarrow A \]

\[ \neg D \Rightarrow C \]

Later in the project, we will have symbols with names like \(G[3, 4]\), which represents that a ghost is at position \((3, 4)\), and we will use them in logic expressions like the above in place of \(A, B, C, D\). The logic.PropSymbolExpr constructor is a useful tool for creating symbols like \(G[3, 4]\) that have numerical information encoded in their name (for this, you would type PropSymbolExpr('G', 3, 4)).

Using the logic.PropSymbolExpr constructor, create symbols WumpusAlive[0], WumpusAlive[1], WumpusBorn[0], and WumpusKilled[0], and create one logic.Expr instance which encodes the following three English sentences as propositional logic in this order without any simplification:

The Wumpus is alive at time 1 if and only if he was alive at time 0 and he was not killed at time 0 or he was not alive at time 0 and he was born at time 0.

At time 0, the Wumpus cannot both be alive and be born.

The Wumpus is born at time 0.

Are sentence1(), sentence2(), and sentence3() satisfiable? If so, try to find a satisfying assignment. (This is not graded, but is a good self-check to make sure you understand what's happening here.)

Before you continue, try instantiating a small sentence, e.g. \(A \land B \implies C\) and call logic.to_cnf on it. Inspect the output and make sure you understand it (refer to AIMA section 7.5.2 for details on the algorithm logic.to_cnf implements).

Now, implement a small function findModel(sentence), which uses logic.to_cnf to convert the input sentence into Conjunctive Normal Form (the form required by the SAT solver), then passes it to the SAT solver using logic.pycoSAT to find a satisfying assignment to the symbols in sentence, i.e., a model. A model is a dictionary of the symbols in your expression and a corresponding assignment of True or False. You can test your code on sentence1(), sentence2(), and sentence3() by opening an interactive session in Python and running findModel(sentence1()) and similar queries for the other two. Do they match what you thought?

To test and debug your code run:

python3.12 autograder.py -q q1

You can also run one test at a time with the -t flag. Each question's tests live in the test_cases directory, one .test file per test (with a matching .solution file holding the expected result):

$ ls test_cases/q1
CONFIG                     correctSentence3.solution   findModelSentence2.test
correctSentence1.solution  correctSentence3.test       findModelSentence3.solution
correctSentence1.test      findModelSentence1.solution findModelSentence3.test
correctSentence2.solution  findModelSentence1.test
correctSentence2.test      findModelSentence2.solution

So, for example, to run only the first sentence test:

python3.12 autograder.py -t test_cases/q1/correctSentence1

(The trailing .test is optional: -t test_cases/q1/correctSentence1.test, as tab-completion gives you, works too.)

Question 2 (4 points): Logic Workout

Implement the following three logic expressions in logicPlan.py:

  • atLeastOne(literals): Return a single expression (Expr) in CNF that is true only if at least one expression in the input list is true. Each input expression will be a literal.
  • atMostOne(literals): Return a single expression (Expr) in CNF that is true only if at most one expression in the input list is true. Each input expression will be a literal. There are multiple ways to implement this function. If you find your algorithm timing out on later problems maybe it is helpful to revisit the implementation of this function.
  • exactlyOne(literals): Return a single expression (Expr) in CNF that is true only if exactly one expression in the input list is true. Each input expression will be a literal.

Each of these methods takes a list of logic.Expr literals and returns a single logic.Expr expression that represents the appropriate logical relationship between the expressions in the input list. An additional requirement is that the returned Expr must be in CNF (conjunctive normal form). You may NOT use the logic.to_cnf function in your method implementations (or any of the helper functions logic.eliminate_implications, logic.move_not_inwards, and logic.distribute_and_over_or).

Important: When implementing your agents in the later questions, you will not have to worry about CNF until right before sending your expression to the SAT solver (at which point you can use findModel from question 1). logic.to_cnf implements the algorithm from section 7.5 in AIMA. However, on certain worst-case inputs, the direct implementation of this algorithm can result in exponentially sized sentences. In fact, a certain non-CNF implementation of one of these three functions is one such worst case. So if you find yourself needing the functionality of atLeastOne, atMostOne, or exactlyOne for a later question, make sure to use the functions you've already implemented here to avoid accidentally coming up with that non-CNF alternative and passing it to logic.to_cnf.

You may utilize the logic.pl_true function to test the output of your expressions. pl_true takes an expression and a model and returns True if and only if the expression is true given the model.

To test and debug your code run:

python3.12 autograder.py -q q2

The Wumpus-Pacman World

The rest of the project takes place in a Wumpus World-inspired variant of Pacman, implemented in wumpus.py. Pacman hunts ghosts, but cannot see them, and stepping onto a square occupied by a live ghost is fatal. Fortunately, Pacman carries two tools:

  • A PKE meter (psychokinetic energy meter, standard ghostbusting equipment), which reads True whenever a live ghost is in one of the four squares immediately adjacent (North, South, East, West) to Pacman's current square. The meter does not say which neighbor.
  • A limited supply of ghost traps. The actions 'TrapNorth', 'TrapSouth', 'TrapEast', and 'TrapWest' place a trap in the corresponding adjacent square (Pacman does not move that turn). If a ghost is there, it is captured: it stays on the board, greyed out, and is harmless from then on. If the square was empty, the trap is wasted. By default Pacman has one trap per ghost.

Ghosts never move. The game is won the moment every ghost has been trapped; the food is worth points along the way (on a board with no ghosts, eating all the food wins instead). The game is lost if Pacman steps onto a live ghost. Ghosts and food are hidden by default: visible food would give away which squares are ghost-free.

Play a game yourself to get a feel for the world, if you have not already (move with 'w', 'a', 's', 'd' or the arrow keys; press 't' to toggle trapping mode, and 'v' to reveal the ghosts and food):

python3.12 wumpus.py

By default, every game is played on a freshly generated random board hiding four ghosts, so no two games are alike (-f replays the same board). Random boards come with no promises: most fall to careful play, but on some only a lucky gamble wins. For a board that is always winnable without guessing, play the fixed classic board with -l wumpusClassic: there, a careful player can prove where every ghost is from PKE readings alone before ever risking a step, so if you die, it was avoidable! For a gentler warm-up try -l wumpusTiny or -l wumpusHunt7 (also winnable without guessing), or use -l to try any layout in the layouts directory.

Your agents will not get to see the game state. Instead, each turn they receive a percept, a Python dict with exactly four entries:

percept['pacman'] Pacman's current (x, y) position
percept['pkeReading'] True if a live ghost is adjacent to Pacman right now
percept['walls'] the walls Grid: walls[x][y] is True if (x, y) is a wall
percept['traps'] how many traps Pacman has left

Note that with the way the grid is laid out, the leftmost, bottommost space occupiable by Pacman (assuming there isn't a wall there) is (1, 1), as shown below (not (0, 0)).

This is exactly the hybrid-agent setting of AIMA chapter 7.7, "Agents Based on Propositional Logic": the agent turns its percept history into a propositional knowledge base, asks a SAT solver what the knowledge base entails about the world, and then uses ordinary search to plan a route through squares it has proven safe. Questions 3-5 build the knowledge base and the inference; Questions 6-7 build the agents.

Since the ghosts never move, none of the symbols in this knowledge base need a time index. We will use just two families of symbols: \(G[x, y]\), meaning there is a ghost at \((x, y)\), and \(PKE[x, y]\), meaning the PKE meter reads True at \((x, y)\). In your code, always build these with the constants defined at the top of logicPlan.py: PropSymbolExpr(ghost_str, x, y) and PropSymbolExpr(pke_str, x, y).

Question 3 (6 points): The Percept Rule

A PKE reading on its own is just a bit. To make it mean something, the knowledge base needs the rule that connects the reading to ghosts: the meter reads True at a square exactly when a ghost is in one of the adjacent non-wall squares.

Implement pkeRule(position, walls) in logicPlan.py. Given a position (x, y) and the walls Grid, it should return a single logic.Expr encoding

\[ PKE[x, y] \Leftrightarrow \bigvee_{\text{non-wall neighbors } (n_x, n_y)} G[n_x, n_y] \]

For example, on a board where \((2, 1)\) has open squares to its East and West and walls to its North and South, pkeRule((2, 1), walls) should return an expression equivalent to \(PKE[2,1] \Leftrightarrow (G[1,1] \lor G[3,1])\).

Important: squares inside walls must not appear in the rule: a ghost can never be inside a wall, and the autograder checks that your rule does not mention them. Use logic.disjoin for the disjunction. You may assume the query square itself is not a wall and has at least one non-wall neighbor.

To test and debug your code run:

python3.12 autograder.py -q q3

The test cases start with a dead-end square that has only a single open neighbor; if your rule is wrong, debug it there before worrying about the four-neighbor cases.

Question 4 (8 points): Build the Knowledge Base

As Pacman walks around, he accumulates two kinds of knowledge: squares that are known to be ghost-free (every square he has safely stood on, for a start), and the PKE readings he has taken. Your job is to assemble all of it into one list of logic sentences.

Implement buildKnowledgeBase(pkeReadings, knownSafePositions, walls) in logicPlan.py, where pkeReadings is a dict mapping positions to the boolean reading observed there, and knownSafePositions is a set of positions known to hold no ghost. Return a list of logic.Expr instances containing:

  • for every known safe position \((x, y)\): the fact \(\neg G[x, y]\);
  • for every reading at \((x, y)\): the reading itself as a literal (\(PKE[x, y]\) if it was True, \(\neg PKE[x, y]\) if it was False), and the percept rule from Question 3 for \((x, y)\), so that the reading actually constrains where ghosts can be.

The order of the list does not matter. What does matter is that you assert nothing about squares Pacman knows nothing about: the autograder evaluates your knowledge base only over the symbols it is allowed to mention, and a knowledge base that asserts extra facts will fail.

To test and debug your code run:

python3.12 autograder.py -q q4

The first test has no readings at all (just two safe squares), so you can check the safe-position facts in isolation before adding the reading logic.

Question 5 (10 points): Is This Square Safe?

Now for the inference. Given everything Pacman knows, a square falls into exactly one of three categories, and your agent will need to distinguish all three:

  • SAFE: the knowledge base entails that there is no ghost there. Pacman may step here.
  • NOT_SAFE: the knowledge base entails that there is a ghost there. Pacman must not step here, but a trap thrown here is guaranteed to catch a ghost.
  • UNSURE: the knowledge base allows both possibilities. Entering is a gamble.

Implement isSafe(position, pkeReadings, knownSafePositions, walls) in logicPlan.py, returning one of the three constants SAFE, NOT_SAFE, or UNSURE defined at the top of the file (do not return bare strings you typed yourself; use the constants).

Remember from lecture how entailment reduces to satisfiability:

\[ KB \models \alpha \quad\text{if and only if}\quad KB \land \neg\alpha \text{ is unsatisfiable} \]

You already have all the pieces: buildKnowledgeBase gives you \(KB\) as a list, logic.conjoin turns a list into one sentence, and findModel from Question 1 tells you whether a sentence is satisfiable. Two findModel calls are enough to distinguish the three answers; work out on paper which two sentences to check before you code.

To test and debug your code run:

python3.12 autograder.py -q q5

The test cases build up from trivial to subtle, in order: a known-safe square, a square nothing is known about, a square cleared by a False reading, a ghost pinned down by a True reading in a corridor, a True reading with two possible culprits (provably neither can be called safe!), and finally a scenario where several readings combine to pin a ghost to one square. If a test fails, debug it before moving to the next one; each builds on the reasoning of the previous.

Hint: if you have SAFE and NOT_SAFE swapped, revisit the entailment formula above: to prove the square safe you must show that "there is a ghost here" is impossible, i.e. that \(KB \land G[x,y]\) has no model.

Question 6 (8 points): The Safe Exploration Agent

Time to put the inference to work. Implement getAction of the SafeExplorationAgent class in hybridAgents.py: an agent that explores the board while only ever standing on squares it has proven safe.

The class already sets up three pieces of state in __init__ for you to maintain: self.pkeReadings (dict of readings taken), self.safePositions (set of squares proven safe), and self.visited (set of squares Pacman has stood on). Each turn, your getAction(percept) should:

  1. Record the percept: the current square is visited and known safe, and its PKE reading goes into self.pkeReadings.
  2. Classify every square with the provided helper findAllSafeStatus(pkeReadings, knownSafePositions, walls), and add every square it proves SAFE to self.safePositions.
  3. Plan a route to the nearest safe square not yet visited, travelling only through safe squares, using the provided helper planToNearest(currentPosition, goalPositions, allowedPositions, walls).
  4. Return the first action of that route, or None to give up if there is nothing safe left to explore (the game ends in a loss, but a dignified one).

Note that the agent replans from scratch every turn. That is fine: each new percept can change what is provably safe, so yesterday's route may be obsolete anyway.

Because this agent never uses traps, it can only win on boards with no ghosts: eating all the food wins the game when there are no ghosts to trap. That is exactly what the autograder tests it on. Start with the easiest test, a three-square ghost-free corridor. When run with -q or -t, the autograder shows each game graphically so you can watch your agent work (add --no-graphics to turn that off):

python3.12 autograder.py -t test_cases/q6/exploration1_corridor

Each of these tests is a small text file that contains its own custom layout, so you can always see exactly what board a test plays on:

$ cat test_cases/q6/exploration1_corridor.test
class: "WumpusGameTest"

# A ghost-free corridor: walk East, eating the food.

agent: "SafeExplorationAgent"
layoutName: "safeCorridor"
layout: """
%%%%%
%P..%
%%%%%
"""

You can also watch your agent roam the larger boards from the layouts directory (start simple!):

python3.12 wumpus.py -p SafeExplorationAgent -l wumpusSafe1
python3.12 wumpus.py -p SafeExplorationAgent -l wumpusSafe2
python3.12 wumpus.py -p SafeExplorationAgent -l wumpusSafe3

For fun, watch it on a board that does have a ghost: it explores everything it can prove safe, then gives up rather than gamble:

python3.12 wumpus.py -p SafeExplorationAgent -l wumpusMaybeSafe

To test and debug your code run:

python3.12 autograder.py -q q6

Debugging hints:

  • If your agent stands still or dithers between two squares, check that you are adding newly proven squares to self.safePositions before planning.
  • If your agent never expands its frontier, check that you recorded the current square's reading with the right key; readings are keyed by position.
  • Run the first autograder test (a three-square corridor) before anything else; every bug is easier to see there.

Question 7 (10 points): The Hybrid Wumpus Agent

The exploration agent stops the moment nothing more can be proven safe. The full hybrid agent keeps going: it uses its traps to make squares safe, and when all else fails, takes a calculated gamble.

Implement getAction of the HybridAgent class in hybridAgents.py. Start each turn exactly like the exploration agent (record the percept, update the knowledge base, and classify every square), then choose an action by working down this strategy list, using the first tier that produces a plan:

  1. Explore. Head for the nearest unvisited SAFE square, travelling only through safe squares. (This is Question 6's behavior.)
  2. Hunt. If a trap is available and some square is proven NOT_SAFE, plan a route to the nearest such square (travelling through safe squares, with the ghost square itself as the final step) and replace the final action of the plan with its Trap variant (e.g. 'East' becomes 'TrapEast'). A trap thrown at a proven ghost is never wasted.
  3. Gamble. Plan a route to the nearest UNSURE square the same way; if a trap is available, replace the final action with its Trap variant, so the square is trapped just before Pacman would step in. Sometimes the board leaves no certainty to work with, and a hybrid agent has to accept that.

Return the first action of the chosen plan, or None to give up if no tier produces one. Since the agent replans every turn, only the first action is ever executed; the trap-substitution on the final step matters on the turn the agent is standing right next to its target.

One subtlety is handled for you. When a trap fires, the target square becomes safe no matter what was there, but any earlier True PKE reading next to that square may have been caused by the ghost that was just captured, so those readings are now stale, and keeping them would make the knowledge base contradict itself. The provided recordTrap method handles both updates. Your only obligation: whenever the action you are about to return is a trap action, call self.recordTrap(currentPosition, action) first. (Read recordTrap; it is short, and understanding why stale readings must be forgotten is the best logic exercise in this project.)

Start with the easiest autograder test: one ghost in a corridor, where the PKE readings pin it down exactly (as in Question 6, -q and -t show the games graphically, and the test file contains the board):

python3.12 autograder.py -t test_cases/q7/hybrid1_corridorGhost

Then watch your agent hunt on the larger boards, again starting simple:

python3.12 wumpus.py -p HybridAgent -l wumpusTiny
python3.12 wumpus.py -p HybridAgent -l wumpusMaybeSafe
python3.12 wumpus.py -p HybridAgent -l wumpus1
python3.12 wumpus.py -p HybridAgent -l wumpus3
python3.12 wumpus.py -p HybridAgent -l wumpusHunt7

(Press 'v' during a game to reveal the ghosts and food and see how the agent's deductions line up with reality.)

To test and debug your code run:

python3.12 autograder.py -q q7

Debugging hints:

  • The first autograder test is a corridor where the ghost's position is provable; if your agent dies there, your tiers are firing in the wrong order or your Question 5 answers are wrong.
  • If your agent throws traps at squares that turn out to be empty over and over, check that tier 2 (a certain catch) really takes priority over tier 3 (a gamble).
  • If the game crashes with an illegal action, you are probably returning a Trap action with no traps left; tier 3 only adds the Trap variant when percept['traps'] > 0.
  • If your agent wins small boards but stalls on big ones, print the sizes of your SAFE / NOT_SAFE / UNSURE sets each turn and watch whether inference is actually making progress.

Submission

Complete Questions 1 through 7 as specified in the project instructions. Then upload logicPlan.py and hybridAgents.py to Gradescope.

Prior to submitting, be sure you run the autograder on your own machine. Running the autograder locally will help you to debug and expediate your development process. The autograder can be invoked on your own machine using the command:

python3.12 autograder.py

To run the autograder on a single question, such as question 3, invoke it by

python3.12 autograder.py -q q3

Note that running the autograder locally will not register your grades with us. Remember to submit your code when you want to register your grades for this assignment.

The autograder on Gradescope might take a while but don't worry: so long as you submit before the due date, it's not late.