Your mission: implement breadth-first tree search for the Maze Pathfinding Problem!

Wow, say that sentence at a party and everyone will think you're super cool!

This assignment makes the conceptual portions of our first lectures concrete, as you complete your first Search algorithm in Python.

In particular, this exercise will:

• Continue your review of Python fundamentals as well as a variety of data structures necessary to complete the task.

• Provide programmatic implementation of the search concept and steps offered in the lectures.

• Expose you to expectations of test driven development for the remainder of the course.

Maze problems in this scenario will be constructed from a list of strings (a 2D maze of characters) indicating the contents of each cell in the maze.

In particular, the following table describes what constitutes a valid maze in this modified version of our Pathfinder:

Here is an example, valid maze configuration:

  Maze elements are indexed as tuple[int, int] starting at the top left:
  (0, 0) = (x, y) = (col, row) 
  Example Maze:
  
      0123456
  0 ["XXXXXXX",
  1  "X....@X",
  2  "X...XXX",
  3  "XGX.X.X",
  4  "XXXXXXX"]
  
  Initial State: (5, 1)
  Goal State:    (1, 3)
  Solution:      ["L", "L", "L", "L", "D", "D"]
  Total Cost:    6

The Pathfinding game proceeds as follows:

• The MazeProblem is formalized, including the maze layout, initial state, goal state, actions, transitions, and a goal test.

• The Pathfinder agent is provided with the problem (as a parameter).

  This means your pathfinder will have access to all of the methods of the MazeProblem, which will simplify the solution! Read on for more...

• The Pathfinder must find a sequence (i.e., list) of actions ("U", "D", "L", or "R") that takes it from the initial state to the goal with minimal cost.

With these details in place, let's look at the specifications.

Start with the solution skeleton in-hand! In the following project, I've given you the outline for a Maze Pathfinder's supporting components, including a MazeProblem specification and a SearchTreeNode. You must implement the Pathfinding functionality!

GitHub Classroom Link

In the provided solution skeleton, I have given you an outline for how to accomplish breadth-first search through the following components:

• maze_problem.py is used to specify the maze and will be used in your Pathfinder's pathfind method.

• pathfinder.py implemented functionally, the pathfind method is the main work-horse for your assignment, which is parameterized by the given MazeProblem. This is the only file you may modify for your submission.

  Note the provided SearchTreeNode class meant to aid you with your implementation -- you should not need to modify it for this assignment.

• pathfinder_tests.py a set of sample unit tests to verify the correct functionality of your Pathfinder solution. THIS TIME ONLY: I've given you all grading tests that you need to pass to receive full credit on this assignment. Future assignments will require you to write your own to supplement those that I give in sample!

• constants.py a set of problem constants that you shall not change (real basic stuff like what the possible movement directions are).

• mypy.ini, pytest.ini configuration files for mypy, pytest respectively. Do not change these!

• .gitignore a set of patterns for git to avoid committing. You may modify this file if your commit attempts to add any project files to the repo (e.g., VSCode .project files or pycache folders, which should not be submitted).

[OPTIONAL - FOR UNDERSTANDING ONLY]

Let's start with a quick little worksheet to make sure you get a feel for how search operates -- if you already have a good grasp, feel free to continue to the next problem. At the very least this is good study material!

Complete the worksheet in the solution skeleton's doc folder!

Skeletons and solutions are provided in both .doc and .pdf formats, but contain the same content -- feel free to complete whichever, or neither, it's all supplemental here.

Still, if you don't know where else to start, I'd start here!

Protip: Try the exercise first before checking the solution--ask me any questions you have instead of jumping straight to the answer!

[REQUIRED - FOR CREDIT]

To successfully navigate *any* maze meeting the criteria above, we will be programmatically implementing breadth-first tree search in your Pathfinder class, complete with a skeleton of the SearchTreeNode class and function signature:.

  @dataclass
  class SearchTreeNode:
      """
      SearchTreeNodes contain the following attributes to be used in generation of
      the Search tree:
  
      Attributes:
          player_loc (tuple[int, int]):
              The player's location in this node.
          action (str):
              The action taken to reach this node from its parent (or empty if the root).
          parent (Optional[SearchTreeNode]):
              The parent node from which this node was generated (or None if the root).
      """
      player_loc: tuple[int, int]
      action: str
      parent: Optional["SearchTreeNode"]
      
      def __str__(self) -> str:
          return "@: " + str(self.player_loc)
  
  def pathfind(problem: MazeProblem) -> Optional[list[str]]:
      """
      The main workhorse method of the package that performs A* graph search to find the optimal
      sequence of actions that takes the agent from its initial state and shoots all targets in
      the given MazeProblem's maze, or determines that the problem is unsolvable.
  
      Parameters:
          problem (MazeProblem):
              The MazeProblem object constructed on the maze that is to be solved or determined
              unsolvable by this method.
  
      Returns:
          Optional[list[str]]:
              A solution to the problem: a sequence of actions leading from the 
              initial state to the goal (a maze with all targets destroyed). If no such solution is
              possible, returns None.
      """

Some notes about the type hints above:

• Notice that anywhere we're talking about maze coordinates, we're using an (x,y) = (c,r) tuple, which is exactly like a list except that it is immutable (i.e., cannot be changed).

• You'll also notice the new Optional keyword in the type hint, which is a signal that the variable can either be the type inside of the brackets, OR None. E.g., the parent attribute of the search tree node has type hint Optional[SearchTreeNode], meaning that this is either a reference to another SearchTreeNode object, or None (in the case of the root, who has no parent).

  def get_initial_loc (self) -> tuple[int, int]:
      """
      Returns the player's starting position in the maze ("@").
  
      Returns:
          tuple[int, int]:
              The player's starting location in the maze: (col, row) = (x, y).
      """
  
  def get_goal_loc (self) -> tuple[int, int]:
      """
      Returns the location of the goal that must be reached.
  
      Returns:
          tuple[int, int]:
              The goal's location tuple: (col, row) = (x, y).
      """
  
  def get_transitions(self, player_loc: tuple[int, int]) -> dict:
      """
      Returns a dictionary describing all possible transitions that a player may take from their
      given position. 
      
      Parameters:
          player_loc (tuple[int, int]):
              The current location of the player in the maze.
      
      Returns:
          dict:
              A dictionary whose keys are the possible actions from the given player_loc, with mapped
              values next_loc (tuple[int, int]) values that show the player's location after taking that action.
      
      Example:
          For example, if only the actions "D", "U", and "L" were possible from the current player_loc of (3,3),
          we might see an output of:
          {
              "D": (3, 4),
              "U": (3, 2),
              "L": (2, 3)
          }
      """
  
  # ...other methods that you won't need in your solution omitted here...

Problem Simplifications

A few simplifications to make life easy for this introductory classwork:

• Tree Search ONLY: Don't worry about repeated states, memoization, or graph search for now -- these will be covered in your homework!

• ONLY Valid Input Mazes with Solutions: For this assignment, assume that all input mazes to your Pathfinder are validly formatted and will have a solution.

• Uniform Cost: This will be a uniform cost maze search -- all actions are assumed to have the same cost.

Pseudocode

  initialize frontier, initial state node
  add initial state node to frontier
  
  while frontier is not empty:
      pop expanding node from frontier
      generate children of expanded node
      for each generated child:
          if child is goal:
              return solution from child
          add child to frontier
  
  return null (should never reach here for this assignment)

Some challenges, tips, and hints to consider:

• You've graduated from CMSI 2120! Feel free to use any data structures from the python libraries in pursuit of your task BUT all other code must be written from first principles.

• Your SearchTree will be constructed from the root (initial state) onwards in a breadth-first order, with each node remembering its parent in the generation order. This means that when you find a goal state, you will have to "walk back" from that node to the root in order to find the solution path (hint: make a helper method to do this).

Additionally, here's a good order of tasks to tackle:

1. Review your course notes and make sure you have a solid grasp on how BFS is meant to operate, at least at a high-level, including the formalization of how it's meant to employ a frontier and search tree.

2. Read through the documentation and the methods available to you in each class in the skeleton.

3. Sketch an outline in comments for the steps you'd like to accomplish the search.

4. Go back and fill in that sketched outline, using helper methods to reduce code complexity where appropriate.

Start early and ask questions! I'm here to help!

As mentioned, THIS TIME ONLY the full set of grading tests have been provided to you in pathfinder_tests.py. Use these to judge the quality of your solution!

Remember to practice Iterative Development while working!

This means to (1) make a change to the code that you think fixes a bug or implements a new method, (2) validate that change by running tests, and then (3) making a Git commit as a checkpoint for your change.

Your grade (out of a possible 10 points for classwork exercises) will be based on the following:

• Correctness: If good faith effort: -1 point for each missed unit test. If incomplete or has errors: 0 / 10

• Style: General style grading will not be assessed on classwork, but -1 point if mypy . yields ANY errors on your submission.

You will be submitting your assignments through GitHub Classroom!

What

Complete the required method in pathfinder.py that accomplishes the specification above, *in the exact project structure and package given* in the skeleton above. This means you must (1) start from the solution skeleton, (2) not change any file names, nor move or remove them, and (3) keep the directory / folder structure of files as given in the skeleton.

You must NOT modify any class' *public interface* (i.e., any public class or method signatures) in your submission! This means you can't change any method names, parameters, or expected types compared to what is given in the skeleton!

You may NOT modify any class apart from pathfinder.py!

That said, feel free to add any private helpers that you find useful.

How

To clone this assignment (if you need a refresher), consult the guide here:

GitHub Classroom Tutorial

To submit this assignment:

• Simply push your final, submission copy to the GitHub Classroom repository associated with you or your group.

• If you worked in a group (3 individuals maximum), ensure that your GitHub Classroom group includes all members, and place all group members' names at the top of *all modified* files (in appropriate docstring commenting fashion) AND in the accompanying readme file.