| Summary |
This assignment presents students with a variant of an interactive tiling problem involving multiple constraints. Specifically, we randomly initialize a grid-environment with some cells colored in and ask students to color the remainder of the grid such that no two cells sharing an edge share the same color. We provide a set of colors and list of brushes to choose from – each of which takes on one of nine shapes and spans up to four cells on the grid. The objective is to also minimize the number of brush strokes and colors used.
Students are tasked with programmatically exploring the implicit search space graph and to find solutions using an AI search algorithm of their choice. By randomly iniitializing the grid environment with pre-filled cells, we incentivize students to build custom heuristics that are more generalizable. We model the environment as a black box, providing an interface that mirrors real-world applications, such as the popular Gymnasium environ-ments for reinforcement learning. Thus, the assignment naturally lends itself to a range of algorithms from basic searches to reinforcement learning, allowing instructors to control difficulty. |
|---|---|
| Topics | Search Problems, Constraint Satisfaction, Heuristics, Hill Climbing |
| Audience | Suitable for undergraduate or graduate students enrolled in introductory Artificial Intelligence or Machine Learning courses. |
| Difficulty | Moderate difficulty for undergraduates with a background in Python programming. A pilot run showed that most students were able to successfully complete the assignment within the allotted time (1 week). |
| Strengths |
The open-ended nature of the assignment helps students build multiple vital skills: a) correctly and efficiently modeling a search space, b) working with a black box model through a limited set of interactions, c) optimizing code for runtime and memory, and d) testing for edge-cases and generalizability.
This assignment encourages students to design, implement and experiment with different search techniques. The assignment supports the application of various algorithms, including BFS, DFS, A*, Genetic Algorithms, and even Reinforcement Learning, providing flexibility in problem-solving approaches. We also supply an autograder that evaluates the student’s solution based on the number of brush strokes and colors used, as well as their runtime, designed to be deployed on Gradescope. This allows students to receive immediate feedback on their submissions, which is essential for iterative improvement. |
| Weaknesses | Requires proficiency in Python, which could be challenging for less experienced students. |
| Dependencies | A background in Python programming is recommended. The assignment is compatible with Python 3+ and can be executed on most single-board computers, ensuring accessibility across various platforms. |
| Variants | This assignment is highly adaptable. Instructors can limit the requirements to specific algorithms or modify the complexity by altering the number and nature of constraints. These modifications allow the assignment to be customized for different levels of difficulty and learning objectives. |
|
Assignment handout template |
Autograder for the assignment, compatible with Gradescope |
|
Skeleton code file to be edited by students |
Source code for the environment |