Assignment 1 (A1) Search

Assignment 1 (A1)
Search
General Info

Learning Objective
This assignment satisfies learning objective 2 (LO2) as specified in the syllabus. You will apply
conceptual knowledge of core AI concepts by implementing AI algorithms, analyzing existing
intelligent systems (including humans), and using existing AI tools to solve problems.
Getting Help
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. If you find yourself stuck on something,
contact us via Piazza or come by the office hours. If you can't make our office hours, let us know
and we will be happy to schedule alternate times.
Submission
You should submit the deliverables on Gradescope under Assignment 1. If you encounter any
difficulties during the submission process please contact us via email and also include a copy of
your submission files before the deadline.
Scoring Rubric
The scoring rubric is provided at the bottom of this document.
Overview
You have a choice of problems for this assignment. Problem A asks you to implement some of
the basic AI search algorithms within a Pac-Man framework while Problem B asks you to
analyze human search behavior and compare it to AI search algorithms. You are free to choose
either A or B.
Problem A
The purpose of this assignment is to get you some hands-on experience with implementing some
of the core AI search algorithms and analyzing their behavior. The assignment requires you to
program in python. Python was selected because it is extremely versatile, is portable, and is very
easy to learn. If you are not familiar with python, you might want to see the tutorial and quiz
available on Canvas, which takes about one hour to complete.
Instructions. Download “search.zip” on Canvas and open “Assignment1_ProblemA.pdf” for
details on the assignment. This assignment is to be completed in Python 3.
Deliverables: You need to submit three files named exactly as follows: search.py,
searchAgents.py and [Identikey]report.pdf
Problem B
The purpose of Problem B is to investigate how humans solve AI problems and compare their
strategies to AI strategies (uninformed and heuristic search algorithms). More specifically, you
will select an existing search problem or design one yourself, ask three or more humans to solve
it, identify the strategies they use to solve the problem, and compare their strategies to the AI
search strategies covered in the class.
Instructions and Deliverables: Submit a report called [Identikey]SearchReport.pdf that
addresses the specific items listed below.
1. Designing the problem (2 points). This is likely the most crucial part of the assignment.
You can select any AI problem, such as eight-puzzle, route finding, missionaries and
cannibals, and others. The problem you select should follow the Goldilocks principle by
having just the appropriate amount of difficulty so that it will provide usable data. More
specifically, the problem should not be too simple so that humans can find an optimal
solution by simply gazing at the problem for a few seconds. Alternatively, it should not
be too complex so that they cannot solve it after trying for a few minutes. Suggestion:
Follow a rapid prototyping procedure by selecting a problem category (e.g., route
finding), designing 3-5 instances of the problem with varied difficulty (i.e., different
maps), informally testing them out on a 2-4 people, and selecting the problem instance
that seems to work best in terms of the Goldilocks principle. Deliverables: Briefly
discuss the problem you selected including your motivation for selecting the problem.
Discuss (with screenshots) the various instances you created including any piloting work
that was conducted to select the best problem instance (if applicable). Then describe the
final problem instance that was selected along with the optimal solution.
2. Data Collection (3 points). Recruit 3 or more volunteers to serve as participants. You
may not select students from this AI class or anyone who is familiar with AI-based
search. Show each participant the problem on a sheet of paper along with a problem
statement (e.g., Find the shortest route from Arad to Bucharest). Your goal is to identify
the specific strategies used by the participants. Use a combination of the following
methods to achieve this goal: (1) Sit nearby to observe the participants solve the problem
and take notes (online observations), (2) Ask them to report their thoughts while they
solve the problem and jot these down (concurrent think-alouds), (3) Interview them after
they solve the problem (called after-action reviews), (4) Collect and analyze any notes
they generate (log-file analysis). Deliverables. Briefly describe who the participants were
(without revealing their names) and the procedure(s) you used (e.g., concurrent think
alouds, after-action reviews).
3. Identifying Strategies (2 points). Identify the strategies used by each of the participants
based on some combination of online observations, concurrent think alouds, after-action
reviews, and log-file analysis. Deliverables. Clearly discuss each strategy you derived
using supporting evidence (e.g., images of their notes, quotes from the interviews).
4. Analyzing Strategies (2 points). Compare the strategies used by each participant. Were
they all similar, were they all different, were some similar, etc? Then compare each
human strategy to the AI algorithms (breadth-first, depth-first, uniform-cost, pure
heuristic, and A* search)? Are the human strategies similar to AI algorithms or are they
very different? If different, who seems to have the advantage – the human or the
computer? Deliverables: Briefly describe your findings with respect to these questions.
Also discuss what you learned about human problem solving and its similarities or
differences to AI search algorithms.
5. Improving AI algorithms (1 point). Can you suggest any improvements to the AI
search algorithms compared to what you learned from humans? Any ideas on how AI and
humans might work together on search? Deliverables. At least one concrete suggestion
along with supporting justification/documentation.
Scoring Rubric
The scoring rubric is based on the Kentucky General Scoring Rubric from the Kentucky
Department of Education (KDE).
Score Description
Category 4
(Score 9-10)
● The student completes all important components of the task and
communicates ideas clearly.
● The student demonstrates in-depth understanding of the relevant concepts
and/or process.
● Where appropriate, the student chooses more efficient and/or sophisticated
processes.
● Where appropriate, the student offers insightful interpretations or extensions
(generalizations, applications, analogies).
Category 3
(Score 7-9)
● The student completes most important components of the task and
communicates clearly.
● The student demonstrates an understanding of major concepts even though
he/she overlooks or misunderstands some less important ideas or details.
Category 2
(Score 6-7)
● The student completes some important components of the task and
communicates those clearly.
● The student demonstrates that there are gaps in his/her conceptual
understanding.
Category 1
(Score 1-6)
● The student shows minimal understanding.
● The student addresses only a small portion of the required task(s).
Category 0
(Score 0)
● Response is totally incorrect or irrelevant.
Blank
(Score 0)
● No response.