ASSIGNMENT 1 Solution

(submit via moodle, you may scan or take a picture of your paper answers) Submit only pdf or txt files (in a zip if you have multiple files)







Problem 1. (15 points)




For each of the scenarios below, classify the environment based on the seven classifications discussed in class (i.e. fully/partially observable, single/multi-agents, etc.). Additionally for each of the seven classifications, provide a single sentence supporting your reasoning.




Sorry! (the board game, read up on it here: https://en.wikipedia.org/wiki/Sorry!_(game) )



Tennis.



You are exploring an undiscovered underwater cave system with a robot equipped with just a camera for sensing.






Problem 2. (20 points)




Consider the graph shown below. Assume you start at “Arad” and want to go to either “Dobreta” or “Urziceni”. Show step-by-step how you would solve this with a breadth first graph search. When adding to the breadth first search queue, do it in lexicographical order (i.e. If you were starting at “Iasi” you would first add “Neamt” then “Vaslui” as N is before V in the alphabet). At each step show:




the “fringe” nodes (the queue)
the “explored” nodes (stuff that has left the queue)
which node you are taking next from the fringe set to move to the explored set









Problem 3. (25 points)




For each of the situations specify: (a) The initial state, (b) possible actions from the initial state, (c) a general description of other states, and (d) whether the approach is incremental or complete-state.




You work at Amazon and someone placed a large order of stuff that you will have to pack into three separate boxes. Each box has a weight limit and a dimension limit that cannot be exceeded. (You do know that these three boxes are capable of storing all the items.)



You are imitating Google maps and want to find the shortest distance between two locations using roads.



You are trying to figure out how to win the game checkers.



Problem 4. (25 points)




Between depth first search, breadth first search and uniform-cost search, for each part say which search is most appropriate? Support your answer with one to two sentences explaining why this search is the best, along with a description of how you will represent the problem as a tree or graph.




You want to open one of your locks (the spin-type shown below, where you need to enter 3 sets of numbers by spinning first clockwise, second counter-clockwise and third clockwise again) but you have forgotten the numbers and need to brute force it.






























You go to the renaissance festival and walk through the hedge maze ( https://en.wikipedia.org/wiki/Hedge_maze ). You do not know the structure of the maze. How should you walk through the rooms to reach the end?



You are performing a dance routine and know how to execute 20 different moves. Each moves uses a certain set of muscles and receives a fixed amount of points. You have time to execute 5 moves during your performance, and you want to get the most points possible (without overusing the same muscles too much).









Problem 5. (15 points)




For each of the following, state whether the task is being done rationally. (Note: this is the strict artificial intelligence definition of “rational”.)




A human playing the card game “War” (someone else deals the cards) (Game rules: https://www.pagat.com/war/war.html )
A robot looks at historical trends on the stock market to try an invest to get you the most money.



You want to find a treasure buried square area as fast as possible. All you have to detect the treasure is a metal detector, so you “zig-zag” (go perpendicular to an edge until you reach the other side, the move the furthest away to ensure you do not miss anything with the metal detector and go back (again perpendicular)) as shown below until the metal detector finds the treasure. Once you have located the treasure you dig it out.