I am going to need assistance only with the programming part which is PART II
CS 4365 Artificial Intelligence Assignment 1: Basic Search Due: Thursday, Sep 22th Instructions: 1. Your solution to this assignment must be submitted via eLearning. 2. For the written problems, submit your solution as a single PDF file. • Only use blue or black pen (black is preferred). Scan your PDF using a scanner and upload it. Make sure your final PDF is legible. Regrades due to non-compliance will receive a 30% score penalty. • Verify that both your answers and procedure are correct, ordered, clean, and self- explanatory before writing. Please ask yourself the following questions before submitting: – Are my answers and procedure legible? – Are my answers and procedure in the same order as they were presented in the assign- ment? Do they follow the specified notation? – Are there any corrections or scratched out parts that reflect negatively on my work? – Can my work be easily understood by someone else? Did I properly define variables or functions that I am using? Can the different steps of my development of a problem be easily identified, followed, and understood by someone else? Are there any gaps in my development of the problem that need any sort of justification (be it calculations or a written explanation)? Is it clear how I arrived to each and every result in my procedure and final answers? Could someone describe my submission as messy? 3. You may work individually or in a group of two. Only one submission should be made per group. If you work in a group, make sure to indicate both group members when submitting through eLearning. 4. IMPORTANT: As long as you follow these guidelines, your submission should be in good shape; if not, we reserve the right to penalize answers and/or submissions as we see fit. 1 Part I: Written Problems (50 points) 0.1 Uninformed Search (23 points) We define a state space as follows. The start state is 1. The successor function for state n returns two states, which are numbered 3n and 3n + 2. The goal state is 35. (a) (4 pts) Draw the state space involving only states 1 to 35. (b) (5 pts) List the order in which nodes will be visited for breadth first search. (c) (5 pts) List the order in which the nodes will be visited for depth-limited search with limit 3. (d) (5 pts) List the order in which the nodes will be visited for iterative deepening search. (e) (4 pts) Is bidirectional search appropriate for this problem? Explain your answer. 0.2 Informed Search (27 points) Consider the problem of getting to Bucharest from Oradea in the map below: When answering the following questions, assume that (1) each node should be expanded at most once; and (2) if needed, break ties alphabetically. (a) (10 pts) Trace the operation of the UCS search algorithm applied to this problem by showing the state that is expanded and its successor states (together with their g values) in each iteration of the algorithm. (b) (7 pts) Trace the operation of the best-first greedy search algorithm applied to this problem by showing the state that is expanded and its successor states (together with their h values) in each iteration of the algorithm. Use the straight-line distance heuristic values shown to the right of the map. (c) (10 pts) Trace the operation of the A* search algorithm applied to this problem by showing the state that is expanded and its successor states (together with their g, h, and f values) in each iteration of the algorithm. Use the straight-line distance heuristic values shown to the right of the map. 2 Part II: Programming (100 points) Task Description Figure 1: All those colored walls, Mazes give Pacman the blues, So teach him to search. 0.3 Introduction In this project, your Pacman agent will find paths through his maze world, both to reach a particular location and to collect food efficiently. You will build general search algorithms and apply them to Pacman scenarios. This project includes an autograder for you to grade your answers on your machine. This can be run with the command: python autograder.py You can also select individual questions for the autograder to run. For example, if you wanted to run question 2 on a project, you would run the command: python autograder.py -q q2 The code for this project consists of several Python 2 files, some of which you will need to read and understand in order to complete the assignment, and some of which you can ignore. You can download all the code and supporting files as a zip from eLearning. 0.4 Files you’ll edit: • search.py 3 – Where all of your search algorithms will reside. • searchAgents.py – Where all of your search-based agents will reside. 0.5 Files you might want to look at: • pacman.py – The main file that runs Pacman games. This file describes a Pacman GameState type, which you use in this project. • game.py – The logic behind how the Pacman world works. This file describes several supporting types like AgentState, Agent, Direction, and Grid. • util.py – Useful data structures for implementing search algorithms. 0.6 File Download: Please see the eLearning. 0.7 Files to Submit: You will fill in portions of search.py and searchAgents.py during the assignment. You should submit these files with your code and comments. Please do not change the other files in this distribution or submit any of our original files other than these files. 0.8 Evaluation: Your code will be autograded for technical correctness. Please do not change the names of any provided functions or classes within the code, or you will wreak havoc on the autograder. However, the correctness of your implementation – not the autograder’s judgements – will be the final judge of your score. If necessary, we will review and grade assignments individually to ensure that you receive due credit for your work. 0.9 Academic Dishonesty We will be checking your code against other submissions in the class for logical redundancy. If you copy someone else’s code and submit it with minor changes, we will know. These cheat detectors are quite hard to fool, so please don’t try. We trust you all to submit your own work only; please don’t let us down. If you do, we will pursue the strongest consequences available to us. 0.10 Getting Help You are not alone! If you find yourself stuck on something, contact the course staff for help. Office hours and eLearning are there for your support; please use them. If you can’t make our office hours, talk to our TA. 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. 4 Welcome to Pacman After downloading the code (search.zip), unzipping it, and changing to the directory, you should be able to play a game of Pacman by typing the following at the command line: python pacman.py Note: The exact command you should be using depends on your distribution and python installation. Pacman lives in a shiny blue world of twisting corridors and tasty round treats. Navigating this world efficiently will be Pacman’s first step in mastering his domain. The simplest agent in searchAgents.py is called the GoWestAgent, which always goes West (a trivial reflex agent). This agent can occasionally win: python pacman.py --layout testMaze --pacman GoWestAgent But, things get ugly for this agent when turning is required: python pacman.py --layout tinyMaze --pacman GoWestAgent If Pacman gets stuck, you can exit the game by typing CTRL-c into your terminal. Soon, your agent will solve not only tinyMaze, but any maze you want. Note that pacman.py supports a number of options that can each be expressed in a long way (e.g., --layout) or a short way (e.g., -l). You can see the list of all options and their default values via: python pacman.py -h Question 1 (12 points): Finding a Fixed Food Dot using Depth First Search In searchAgents.py, you’ll find a fully implemented SearchAgent, which plans out a path through Pacman’s world and then executes that path step-by-step. The search algorithms for formulating a plan are not implemented – that’s your job. First, test that the SearchAgent is working correctly by running: python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch The command above tells the SearchAgent to use tinyMazeSearch as its search algorithm, which is implemented in search.py. Pacman should navigate the maze successfully. Now it’s time to write full-fledged generic search functions to help Pacman plan routes! Pseudocode for the search algorithms you’ll write can be found in the lecture slides. Remember that a search node must contain not only a state but also the information necessary to reconstruct the path (plan) which gets to that state. Important note: All of your search functions need to return a list of actions that will lead the agent from the start to the goal. These actions all have to be legal moves (valid directions, no moving through walls). 5 Important note: Make sure to use the Stack, Queue and PriorityQueue data structures provided to you in util.py! These data structure implementations have particular properties which are required for compatibility with the autograder. Hint: Each algorithm is very similar. Algorithms for DFS, BFS, UCS, and A* differ only in the details of how the fringe is managed. So, concentrate on getting DFS right and the rest should be relatively straightforward. Indeed, one possible implementation requires only a single generic search method which is configured with an algorithm-specific queuing strategy. (Your implementation need not be of this form to receive full credit). Implement the depth-first search (DFS) algorithm in the depthFirstSearch function in search.py. To make your algorithm complete, write the graph search version of DFS, which avoids expanding any already visited states. Your code should quickly find a solution for: python pacman.py -l tinyMaze -p SearchAgent python pacman.py -l mediumMaze -p SearchAgent python pacman.py -l bigMaze -z .5 -p SearchAgent The Pacman board will show an overlay of the states explored, and the order in which they were explored (brighter red means earlier exploration). Is the exploration order what you would have expected? Does Pacman actually go to all the explored squares on his way to the goal? Hint: If you use a Stack as your data structure, the solution found by your DFS algorithm for mediumMaze should have a length of 130 (provided you push successors onto the fringe in the order provided by getSuccessors; you might get 246 if you push them in the reverse order). Is this a least cost solution? If not, think about what depth-first search is doing wrong. Question 2 (12 points): Breadth First Search Implement the breadth-first search (BFS) algorithm in the breadthFirstSearch function in search.py. Again, write a graph search algorithm that avoids expanding any