2
CAP 6635 Artificial Intelligence
Homework 1 [12 pts]
If you have multiple pictures, please include all pictures in one Word/pdf file.
1. [1 pt] What is PEAS task environment description for intelligent agent? For the following agents, develop a PEAS description of their task environment
· Assembling line part-picking robot
· Robot soccer playe
2. [1 pt] Figure 1 shows the relationship between an AI agent and its environment. Please explain the names and functionalities of the parts marked as A, B, C, and D, respectively.
Figure 1
Figure 2
3. [1 pt] Please design pseudo-code of an energy efficient model-based vacuum-cleaner agent as follows:
(1) The environment has three locations (A, B, C as shown in Figure 2) and three states (“Clean”, “Dirty”, “Unknown”).
(2) The vacuum-cleaner has four actions “Left”, “Right”, “Suck”, and “Idle”,
(3) The vacuum-cleaner will clean the dirt as soon as it senses that the cu
ent environment is Dirty,
(4) If the vacuum-cleaner senses the cu
ent environment is “Clean” or “Unknown”, it will remain Idle for one time point, and
(5) The vacuum-cleaner will change location if it senses the cu
ent environment is “Clean” for two consecutive time points in a row, and
(6) The vacuum-cleaner will change location if it senses the cu
ent environment is “Unknown” for two consecutive time points in a row.
(7) When change locations, agent can only move “right” if it is at location “A”, move “left” if it is at location “C”, and randomly decide to move “left” or “right” if it is location “B”
Summarize percept sequences and co
esponding actions as a table [0.5 pt],
Write the pseudo code of the agent [0.5 pt].
4. [1 pt] Please summarize task environment types for the following three agents, in terms of “observable”, “deterministic”, “episodic”, “static”, “discrete”, “number of agents”
Agent
observable
deterministic
episodic
static
discrete
# of agents
Tic-tac-toe
Tetris
Robot soccer competition
Texas hold 'em
Tic-tac-toe
Tetris
XXXXXXXXXXTexas hold’em
Robot soccer competition
5. [1 pt] The goal of the 4-queens problem is to place 4 queens on a 4 rows 4 columns chessboard, such that no two queens attach each other. One solution to the 4-queens problem is shown in Figure 3. Please design a search based solution to solve the 4-queens problem. Your solution must include following four components
a. Define state [0.25]
. Define successor function, and calculate total number of states, based on the defined successor function [0.25 pt]
c. Show state graph [0.25 pt]
d. Show how to find solutions from the state graph [0.25 pt]
Figure 3
Figure 4: Eight-puzzle game: an initial state (left), and a portion of a search tree (right).
6. [1 pt] Figure 4 shows an initial state of the eight-puzzle game. Please create a search tree using this initial state. The search tree must have depth 2 (Figure 4 cu
ently shows a search tree with depth 1), and shows all search nodes (including states co
esponding to each search node.
Figure 5
7. [1 pt] Figure 5 shows a search tree with 21 nodes. Please uses Breath First Search (BFS) algorithm showing in Figure 6 to report the order of the nodes being visited, and the Fringe structure (report fringe structure of each step as show in the table below) [0.5 pt]. Please compare the fringe structure and explain the memory consumption of each method, with respect to
anching factor (b) and the search depth (d) [0.5 pt].
Fringe
Node visited
Fringe Size
Search depth
Figure 6: Breath First Search (BFS)
Figure 7 Depth First Search DFS
8. [1 pt] Figure 5 shows a search tree with 21 nodes. Please uses Depth First Search algorithms showing in Figures 7 to report the order of the nodes being visited, and the Fringe structure of each method (report fringe structure of each step as show in the table below) [0.5 pt]. Please compare the fringe structure and explain the memory consumption of each method, with respect to
anching factor (b) and the search depth (d) [0.5 pt].
DFS Method
Fringe
Node visited
Fringe Size
Search depth
Figure 8 Robot navigation field.
9. [1 pt] Figure 8 shows a robot navigation field, where the red square (d2) is the robot, and green square (c7) is the goal. The shad squares (such as b2, c2, etc.) are obstacles. The robot is not allowed to move in diagonal line. Node are coded using an alphabet letter followed by a digit (such as a0, b1, b2 etc.). When two sibling nodes are inserted into fringe (queue), use deque order to favor node with a lower alphabet and a lower digit. For example, if d1 and e2 are sibling nodes, d1 will be dequeued first (because “d” has a lower alphabetic order than “e”). If a1 and a2 are sibling nodes, a1 will be dequeued first (because “1” has a lower digit than “2”). Node expanded/visited does not need to be revisited.
· Use Depth First Search to find path from d2 to c7.
· Report nodes in the fringe in the orders they are included in the fringe. [0.25 pt]
· Report the order of the nodes being expanded. [0.5 pt]
· Report the final path from d2 to c7. [0.25 pt]
· Use Breadth First Search to find path from d2 to c7.
· Report nodes in the fringe in the orders they are included in the fringe. [0.25 pt]
· Report the order of the nodes being expanded. [0.5 pt]
· Report the final path from d2 to c7. [0.25 pt]
Fringe:
Node visited/expanded
For all programming tasks, please submit the Notebook as html or pdf files for grading (your submission must include scrips/code and the results of the script).
For each subtask, please use task description (requirement) as comments, and report your coding and results in following format:
10. [1 pt] The “Source Code” module in Canvas lists three python programs. “randomagentrobot.py” is a random moving agent, “simpleagentrobot.py” is a reflex agent with a model to ensure agent walking through all locations. “complexagentrobot.py” is a goal-based agent aiming to clean all dirty spots with minimum steps of moves.
a. Use proper python IDE environment (FAU HPC environment will allow students to use Jupyter Notebook for python coding) to run each of the three python programs. Change environment as a 6x6 navigation board (0.25pt). Capture one screenshot (or plot) showing that the program is properly running (0.25 pt).
. Explain which agent performs the best, and why (0.25 pt).
c. Propose a solution to design a fourth agent program which may outperform “complexagenetrobot.py”. Explain why your proposed solution can perform better (0.25 pt). (no need to implement the agent. Just description your idea using textual descriptions or pseudo-code).
11. [2 pts] The “Blind Search to Play Maze [Notebook, html]” posted on Canvas “Source Code” shows a Maze game using DFS and BFS search (using “DFS” or “BFS” parameters). Use Notebook as the skeleton code, validate and compare following settings and results.
a. Using Figure 9 as the game field, and use any two states as initial and goal states, report a screenshot of the program. Explaining the meaning of the output [0.25 pt]
. Set initial state as [0, 0] and goal state as [0, 1]. Report number of nodes expanded by BFS and DFS, respectively. Report final path discovered by each algorithm, respectively [0.25 pt]. Explain why or why not the method is optimal [0.25 pt], and why one approach expands far more nodes than the other method [0.25 pt]
c. Set initial state as [0, 0] and goal state as [0, 1], [0, 2], [0, 3], [0, 5], [0, 6], [0, 7], [0, 8], [0, 9], respectively. Create one plot to show the number of maximum Fringe size of BFS (x-axis denotes the goal state, and y-axis denotes the maximum Fringe size) [0.25 pt]. Create one plot to show the number of maximum Fringe size of DFS (x-axis denotes the goal state, and y-axis denotes the maximum Fringe size) [0.25 pt]. Explain how the Fringe size grows with respect to the search depth for DFS and BFS, respectively. [0.25 pt]
d. For goal state [0, 9], compare path returned by BFS and DFS, respectively. Which method is optimal, and which method is not optimal? Why? [0.25 pt]
Figure 9: Maze game field