{ "cells": [ { "cell_type": "markdown", "id": "ed05221b-4344-4d3b-bcea-87fa2bf77b55", "metadata": {}, "source": [ "
\n", " ARTIFICIAL INTELLIGENCE (E016350B)
\n", "ALEKSANDRA PIZURICA
\n", "GHENT UNIVERSITY
\n", "AY 2024/2025
\n", "Assistant: Nicolas Vercheval\n", "
" ] }, { "cell_type": "markdown", "id": "5c682f6d-0856-4907-9cca-c6deac4b41b2", "metadata": {}, "source": [ "# Lab Assignment: Search strategies\n", "\n", "\n", "This lab asks you to help Pacman eat all the food on the map (no ghosts for now!). \n", "You will implement uninformed (depth-first, breadth-first, uniform-cost) and informed (greedy, A*) search strategies and write heuristics specific to the application. Your grade will be based on the answers to the following questions. \n" ] }, { "cell_type": "markdown", "id": "6d2f3764-a2ad-44ab-ad47-262812935eaa", "metadata": {}, "source": [ "## Pacman\n", "\n", "You will work with the Pacman framework from UC Berkeley. You find an introduction to the framework and a link to the project files [here.](https://inst.eecs.berkeley.edu/~cs188/fa24/projects/proj1/)\n", "\n", "The framework has no external dependencies but requires tkinter from the standard library, which is not always installed by default.\n", "If the command `import tkinter` fails, [install it](https://stackoverflow.com/questions/69603788/how-to-pip-install-tkinter) and try again. If it does not work, it may be because you have to specify the Python version you use in your virtual environment in the command.\n", "\n", "After downloading the project files, open and complete the project using your favourite IDE (you can use the given auto-grader to see whether your code is correct, but we will not grade you based on that). \n", "\n", "Then come back to the notebook and answer the following questions.\n" ] }, { "cell_type": "markdown", "id": "e76072a1-c2d2-40dd-a87b-c8b6faad99d0", "metadata": {}, "source": [ "## Read carefully\n", "- This assignment is individual. You are not allowed to work in groups or exchange solutions.\n", "- The auto-grader gives 0 points to a correct implementation of A*. Ignore it for now, we will come back to it in the questions.\n", "- Do not waste too much time getting full points in the auto-grader, particularly for question Q7. You will not get extra points for the assignment.\n", "- For each answer, write a short (2 sentences max) comment to motivate it." ] }, { "cell_type": "code", "execution_count": null, "id": "c37693d0-fae2-4840-b388-7636b2fa8c91", "metadata": {}, "outputs": [], "source": [ "answers = {}\n", "comments = {}" ] }, { "cell_type": "markdown", "id": "70ce633c-0ba5-4657-82a6-79b411547a19", "metadata": {}, "source": [ "## Mazes\n", "Layouts where the goal is to find a single food item. The goal is, therefore, explicit. Note that the layout specifies the starting position and the food location." ] }, { "cell_type": "markdown", "id": "2821bfe1-0220-4a7c-8d3e-5b0d1a985a86", "metadata": {}, "source": [ "### Graph Search\n", "Graph search addresses loops by pruning subtrees with repeated states in the search tree." ] }, { "cell_type": "markdown", "id": "d4f5291f-8af7-4533-8aa1-79f5a471c4d7", "metadata": {}, "source": [ "#### Question 1\n", "Run:\n", "- `python pacman.py -l tinyMaze --frameTime .5`\n", " \n", "and have a look at the maze.\n", "\n", "Depending on how you prune the search tree, the resulting tree may have a different depth. \n", "What is the maximum depth that the pruned tree could have?\n", "Write the correct number as the answer and describe the state(s) that could be the deepest leaf as a comment.\n", "\n", "Note: Each time Pacman bites, the algorithm counts one more action." ] }, { "cell_type": "code", "execution_count": null, "id": "d8d43a9d-b198-4c8f-a147-1da19a03949a", "metadata": {}, "outputs": [], "source": [ "answers[1] = 0\n", "comments[1] = ''" ] }, { "cell_type": "markdown", "id": "7eeca055-687d-4ef9-9251-498483dedb5d", "metadata": {}, "source": [ "### The solution to a search problem\n", "We call the path to a node a sequence of actions that brings you from the starting position to the node. \n", "A solution is a path to a goal state." ] }, { "cell_type": "markdown", "id": "e88e8d09-e3fc-4355-97c5-01456d214f2a", "metadata": {}, "source": [ "#### Question 2\n", "Take a look at the map layout called \"contoursMaze\":\n", "- `python pacman.py -l contoursMaze`\n", "\n", "Which algorithm between depth-first search (DFS) and breadth-first search (BFS) will be faster in finding the **solution**?\n", "1) The solution will be found after the same time, regardless of the order of the children.\n", "2) Depending on the order of the child nodes, BFS can be significantly faster or slower than DFS.\n", "3) Depending on the order of the child nodes, DFS can be significantly faster and never significantly slower than BFS.\n", "4) Depending on the order of the child nodes, DFS can be significantly faster or get stuck in the wrong corner.\n", "\n", "Run the DFS and BFS algorithms:\n", "- `python pacman.py -l contoursMaze -p SearchAgent -a fn=dfs`\n", "- `python pacman.py -l contoursMaze -p SearchAgent -a fn=bfs`\n", " \n", "and write a comment explaining why the results agree with your expectations." ] }, { "cell_type": "code", "execution_count": null, "id": "c63f838c-12b4-41e8-b7a0-420b5b8cbbc3", "metadata": {}, "outputs": [], "source": [ "answers[2] = 0\n", "comments[2] = ''" ] }, { "cell_type": "markdown", "id": "1dffbfe0-b096-4d78-bd49-a3fdc948eb60", "metadata": {}, "source": [ "### Optimal solution\n", "A (cost-)optimal solution is a path from the start node to a goal node with the minimum possible cumulative cost as determined by the cost function." ] }, { "cell_type": "markdown", "id": "72fac038-c06f-4bce-a89a-9381bde67156", "metadata": {}, "source": [ "#### Question 3\n", "Take a look at the map layout called \"openMaze\":\n", "- `python pacman.py -l openMaze` \n", "\n", "Suppose that, for some unknown reason, instead of giving each direction the cost of one, we use a strictly positive cost function where the total cost of all directions is still 4 (i.e. the cost of the path corresponding to the actions [UP, LEFT, DOWN, RIGHT] is 4).\n", "What aspect of uniform-cost search would remain unaffected by this function?\n", "\n", "1) The retrieved solution.\n", "2) The set of optimal solutions.\n", "3) The overall cost of an optimal solution.\n", "4) The number of expanded states.\n", "\n", "Motivate your choice by referring to how a uniform-cost search works when all the directions have the same cost:\n", "- `python pacman.py -l openMaze -p SearchAgent -a fn=ucs`\n", "\n", "Note: this differs from what StayEastSearchAgent and StayWestSearchAgent do because their cost function is a function of the next state, not the action." ] }, { "cell_type": "code", "execution_count": null, "id": "3e7b7e8c-e29c-466f-abc1-75524285179f", "metadata": {}, "outputs": [], "source": [ "answers[3] = 0\n", "comments[3] = ''" ] }, { "cell_type": "markdown", "id": "87a256c1-8076-4be1-be67-644ae64b8aa5", "metadata": {}, "source": [ "### Admissability and consistency\n", "An admissible heuristic never overestimates the true cost of reaching the goal. A consistent heuristic means that the estimated cost of reaching the goal from a node never exceeds the estimated cost from a neighbour node plus the step cost to the neighbour." ] }, { "cell_type": "markdown", "id": "35bd2879-a18d-4431-bc61-dca54d339e05", "metadata": {}, "source": [ "#### Question 4\n", "\n", "If you implemented A* according to the lab session, you should get no points when running the auto-grader for question 4. \n", " - `python autograder.py -q q4`\n", "\n", "In particular, `test_cases/q4/astar_expand_1.test` and `test_cases/q4/astar_expand_2.test` fail. Let us focus on the first failed test (in fact, both fail for the same reason).\n", "\n", "In the auto-grader's output, we observe that our implementation of A* does not find the given solution. Why is that?\n", "\n", "1) The metric is admissible but not consistent\n", "2) The metric is not admissible.\n", "3) The given solution is not optimal.\n", "4) The teaching assistant made a mistake in the code.\n", "\n", "Write the number of the correct solution in the answers and express the issue mathematically in the comment.\n", "\n", "Note: the test `astar_expand_1.test` associates 0 with the action of going right in the diagram and 1 with the action of jumping from Q to B. " ] }, { "cell_type": "code", "execution_count": null, "id": "9cd2ee23-d036-424e-ba63-ef0a1c0ab4ac", "metadata": {}, "outputs": [], "source": [ "answers[4] = 0\n", "comments[4] = ''" ] }, { "cell_type": "markdown", "id": "53b84aaa-af20-4174-96ec-6f251ed1a6aa", "metadata": {}, "source": [ "## Searches\n", "Layouts where the goal is to find all the food items. The goal is, therefore, implicit." ] }, { "cell_type": "markdown", "id": "feddb261-2fb8-4465-96ed-3a93b08a38ea", "metadata": {}, "source": [ "### Dominant heuristic\n", "\n", "A heuristic dominates another when the values for all the nodes in the state-space graphs are greater than or equal to the corresponding values of the other heuristic. " ] }, { "cell_type": "markdown", "id": "bd9ea651-d199-478b-b592-dc59bc896be6", "metadata": {}, "source": [ "#### Question 5\n", "\n", "Given the default cost function, associate the following ideas for a heuristic:\n", "\n", "1) The distance to the closest food position.\n", "2) The distance to the farthest food position.\n", "3) The number of remaining food items.\n", "4) The distance to the farthest food position plus the number of remaining food items.\n", "\n", "to the following properties (referring to an arbitrary Pacman layout):\n", "\n", "1) The metric is not admissible.\n", "2) The metric is admissible but not consistent.\n", "3) The metric is consistent but dominated by another in the list.\n", "4) The metric is consistent but dominates the other consistent in the list.\n", "\n", "Write as an answer a tuple containing the number of the correct property for each idea. For example, if they are linked in a reverse order, the answer would be `(4, 3, 2, 1)`.\n", "\n", "\n", "Implement the various ideas for the \"corner\" problem and run:\n", "- `python autograder.py -q q6`\n", "\n", "to check that they fail the tests (ignore the failed tests for A*).\n", "\n", "Implement the ideas that did not fail the previous tests for a general \"food\" problem and run:\n", "- `python autograder.py -q q7`\n", "\n", "to check that they fail the right tests (ignore the failed tests for A*).\n", "\n", "In the comment, describe a layout where the metric associated with one of the ideas would not be admissible." ] }, { "cell_type": "code", "execution_count": null, "id": "42c02963-70e0-4209-bb47-ac09cc6a1167", "metadata": {}, "outputs": [], "source": [ "answers[5] = (0, 0, 0, 0)\n", "comments[5] = ''" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.7" } }, "nbformat": 4, "nbformat_minor": 5 }