Assignment 1 Solution

This assignment consists of four questions which involve written answers and code. In order to complete the assignment you must submit a written report in pdf form detailing your answers to the questions as well as your code. As discussed in class all work must be your own. You may not use third party libraries or example code to complete the assignment. All reports must be clear and well written. All code must be clear, readable, and well-commented.

    • Question 1 Agents and Environments (20pts)

Consider the ve problem scenarios listed below. For each scenario answer the following questions and provide a justi cation for your answer.

    1. What is the appropriate PEAS speci cation for an agent that solves the problem and what are the features of the environment?

    2. What is the least powerful agent that can solve the problem, and why?

Scenario 1: Intelligent Monitor can be deployed in some storehouses. This monitor will stay in standby mode under normal conditions. But it will take videos when it detect moving target by sensors. The monitor and sensors can cover all place in the storehouse.

Scenario 2: Deep Sea Drone A deep sea research drone designed to measure subsurface ocean currents by diving to a pre-speci ed depth, recording salinity and temperature information at a set location, and then returning to the surface to transmit data.

Scenario 3: Tax Assistance Given a tax assistance system where individuals can seek advice on what forms are required to complete their taxes. To address this problem the system will take them through a series of questions about their current nancial situation as well as what forms they have completed. The system can also direct them to complete a given form and then return with new information.

Scenario 4: Intelligent Infrastructure Management In large organizations many online resources exist that go unused most of the time. These include virtual machines or other system resources, and soft-switch hardware resources such as networking kits. Assume that you have an intelligent agent that is tasked with managing these resources to maintain minimal power usage and fast user responses.

Scenario 5: Assume we have a Robot Soccer Player which can run and shot. This robot play a traditional soccer game with other ve Robot Soccer Players. The robots do not know the locations of each other but their sensors can feel other robots if they are close enough. Meanwhile, there is no connection between robots, but if they are close enough, they can also detect if they are in the same team(cooperation) or not(con ict). Every robots also have sensors to tell where is the ball and the goal. The agent is assigned a task of making goals as many as it can for winning the game.

Question 2 Belief Maintenance (5 points)

Robot R is in position a in the given maze and its’ goal is to reach G in position l. The possible set of actions for this agent is Up, Down, Left, and Right. The thick lines indicate walls and every time that an action is against a wall, nothing happens and the robot stays in the same state. For each action, there is a slip chance for the agent to move in the opposite direction. Assuming the following set of consecutive actions A = f!; !; "; ; g, indicate the belief state after executing each action a 2 A.



1










Question 3 (15 pts)

Below are game trees. Assume the root node represents the current game state, and that the system must now select the child of the root with the maximum value. Squares and circles represent maximize and minimize. Suppose the static position evaluation values are given in the leaf nodes. Perform both minimax search and - pruning as called for below.

    a. (5 pts) Inside each node of below game tree, indicate the minmax values for all nodes, including the root, assuming no pruning. What is the best rst move for max?

















Figure 1: Game Tree for Q3.a

b. (5 pts) Using below game tree, to the left of each node, indicate the intervals for all interior nodes and show how the intervals change dynamically during search, assuming the move generator proceeds left to right. Draw a short line through the edges that would be pruned by -pruning, and draw an

next to these lines. Draw a short line through the edges that would be pruned by -pruning, and draw a next to these lines.

















Figure 2: Game Tree for Q3.b



2

    c. (5 pts) Imagine a stochastic two-player game that the result of the actions are unknown. There is 1=2 chance that the actions result in di erent outcomes. Figure below shows a game tree with player A as starter and three possible actions to perform. Next layer is chance node, followed by player B’s actions and chance nodes. Compute the values for each node. Then indicate what is the best rst move for player A and state why.

Question 4 Search (60 points)

A number-maze is a matrix representation for a maze problem. Each cell in the maze contains a number or a "G" indicating the goal state. A sample number maze is shown in Figure 4. Solvers start the maze at the entry point at cell 0,0. At each cell they can move up, down, left, or right, the number of cells listed in the current cell, unless they hit an edge. Thus in the example shown below they can move down or to the right by 2 cells to cells 0,2 or 2,0 respectively. A number maze is complete when you have traversed through it to nd the goal state marked "G".

For the purposes of this assignment you have been given two sample mazes, the 4x4 maze shown below, and the 6x6 maze along with their ideal answers. You have also been given an 8x8, 12x12 and 25x25 maze without answers. For this question you should:

    1. De ne an admissible or consistent heuristic for the maze using one of the techniques in class and justify that here. Identify any limitations of your algorithm.

    2. Implement a maze solver using state-space search that implements DFS, BFS, Best First, and A* search with your chosen heuristic. Your code must take a single argument specifying the maze le and must output an answer le in the same format supplied. The dimensions of the puzzle and other information must be read from the le itself. Note that your code will be tested on other unseen mazes.

    3. Use the implemented solvers to solve each maze, including the example mazes. For each maze provide the following information:

        (a) The shortest path.

        (b) The number of states expanded by each algorithm when  nding the path.

        (c) The total number of unique paths through the graph for the 6x6, and 8x8.

        (d) The number of states expanded in  nding the paths.

All code must be clearly documented and be your own work. You are not permitted to use third party libraries, shared code, or demonstration code.
























3
























Figure 3: Game Tree for Q3.c


















t


0
1
2
3





0
2
1
1
3





1
2
1
2
3





2
1
1
2
3





3
3
G
3
1





Solution: 0,0; 2,0; 2,1; 3,1

Figure 4: Number Maze Example.











4