Assignment 1

Write and document a Python program that uses breadth-first search (no closed list), uniform cost search (no closed list), and depth-first search (non-recursive; no closed list) to find ALL solutions to a modified STRIPS planning problem (see the making tea planning problem in Lecture #3 of the course notes). Your code need only work for problem instances that do not include reversible actions and hence you do not need to implement closed lists. You have been given Python files mySearchClasses.py and search.py and you need to fill in the function definitions in file mySearchFunctions.template according to appropriately modified versions of the specified algorithms given in Lectures #4 and 5 to create a file mySearchFunctions.py such that search.py (when run relative to given problem-description files prob1.txt, prob2.txt, prob3.txt, prob4.txt, prob5.txt, and prob6.txt using python3 on the CS departmental LabNet systems) can exactly reproduce the outputs in script file out.script.

You are not allowed to modify any of the code in provided files search.py and mySearchClasses.py. When modifying file mySearchFunctions.template to create mySearchFunctions.py, you cannot:

• modify the lone import statement;
• add other import statements;
• add or remove function definitions;
• add new class definitions or global variables (use the provided classes in file mySearchClasses.py); or
• access any provided class attributes directly (use provided attribute access functions in file mySearchClasses.py).

Violations of any of these constraints will result in severe mark deductions (see assignment evaluation scheme below).

Hints

Using the provided implementations of queues, priority queues, and stacks in mySearchClasses.py will help your code to reproduce the algorithm outputs in out.script.

You may find it useful to progress through the given problem-description files in the given order when debugging your code.

Assignment Submission

Please submit your program file mySearchFunctions.py through the course D2L / Brightspace shell by 11:59pm on the assignment due date. Note that each program file must have the following comment block at the top, where the X's are replaced with the appropriate information. For example, my Python file for this assignment would begin with the following comment block:

#########################################################
##  CS 3200 (Fall 2024), Assignment #1                 ##
##   Script File Name: mySearchFunctions.py            ##
##       Student Name: Todd Wareham                    ##
##         Login Name: harold                          ##
##              MUN #: 8008765                         ##
#########################################################

You do not have to develop your code on our CS departmental LabNet systems. However, as your code will be tested on our CS departmental LabNet systems as part of the assignment marking process, you should ensure that your code compiles and runs correctly on at least one of these systems.

Additional Notes:

• August 11, 2024
  Assignment #1 posted.

Created: August 11, 2024
Last Modified: September 20, 2024