Assignment 1 (A1) Search Solution

General Info

10 Point Individual Assignment




Due by 2 pm Monday 9/30 (see Syllabus for collaboration policy & policy regarding late submissions)




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.




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.



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).



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).



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.




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




Category 4 (Score 9-10)




























Category 3

(Score 7-9)













Category 2




(Score 6-7)




Description




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).



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.



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
● The student shows minimal understanding.
(Score 1-6)
● The student addresses only a small portion of the required task(s).


Category 0
● Response is totally incorrect or irrelevant.
(Score 0)


Blank
● No response.
(Score 0)