Nate Derbinsky <>
College of Computer and Information Science
Northeastern University
Summary This project is a natural extension to the Pacman Project's Search assignment. It involves formulating maze-solving as a search problem, image processing (via OpenCV) as a step in a maze-solving pipeline, as well as guided performance/quality analysis of representational parameters. The system is developed in steps, each motivated and supported via visualization goals. The assignment ends with a set of interesting directions for ambitious students to explore further.
Topics Search, computer vision, image processing, problem representation
Audience Introductory AI class
Difficulty Assuming a prerequisite introduction to search: moderate. Students incrementally extend search to a likely familiar problem, but must learn sufficient OpenCV in order to visualize outputs and process inputs. Students typically take 1-2 weeks to complete the base assignment, with 2-3 additional for exploratory extensions.
Strengths The project is designed to naturally extend the commonly used Pacman Projects (starter code includes snippets, with license text intact) - if students have completed the Search assignment, graph search should literally copy-paste. The instructions provide a 2-3 step procedure to have a common OpenCV environment across platforms (which is commonly quite time-consuming). The solution (available upon request from instructors) makes it quite easy to create novel maze inputs from existing images and/or PowerPoint shapes. The analysis questions explicitly have students gather performance data and synthesize an understanding of speed vs. quality trade-offs in a simple representational situation; included problem instances can push a reasonable laptop (>1GB memory for larger mazes, >1 min CPU). Half a dozen student teams (size: 2-3) have opted to pursue this project, and outputs have been diverse and often quite impressive (e.g. a real-time, augmented-reality maze solver).
Weaknesses Unlike the Pacman Projects, there is no auto-grading; however, students are able, and encouraged in the instructions, to self-check their progress at numerous points. The Pacman Projects are currently limited to Python 2, whereas this more recent assignment was developed for Python 3 (the graph search component is agnostic, but may lead to multiple Python installs on a student system/computing environment); this can be ameliorated by virtual environments and/or using Anaconda prompts (to selectively load environments), but porting to another language would be no small feat. The task is quite similar to Pacman, and so students aren't gaining much new experience in problem formulation; they are, however, getting a stronger sense of what an input-to-output AI-system pipeline involves. The OpenCV section outsources basic familiarity to quality sources - while it is a useful skill for students to seek online resources, the assignment can't be claimed as fully self-contained (e.g. in comparison to Pacman Projects Python/Unix Tutorial). The usage of OpenCV in the base assignment is limited to very basic functionality (image read/show, pixel read/write, colored shape overlays, blur, thresholding); however the extensions offer motivation for more advanced exploration.
Dependencies Knowledge:
  • Search
  • Python
  • Python (installation instructions are provided for Anaconda)
Variants The end of the assignment provides ideas and resource-pointers for significant extensions. The base problem could have been situated in a game with regions, to introduce ideas about occupancy grids and such. The degree of scaffolding could be easily manipulated (i.e. supply more/less code).

Assignment Components

Example solution will be made available to instructors upon request.