FIT5047 Intelligent Systems
Solutions to Practice Questions for Final Exam
1. [Agents] Consider the vacuum agent presented in class, but assume that the room
has 8 squares and a square can get dirty after it has been cleaned.
(a) Use PEAS to specify the task environment.
SOLUTION:
Performance measure: cleanliness of the room, number of moves.
Environment: room, furniture, people.
Actuators: vaccum cleaner.
Sensors: vision, touch.
(b) Specify the attributes of the environment.
SOLUTION:
Known (the conditions of the environment are known)
Stochastic (squares can become dirty at any time)
m
Observable (everything can be seen)
er as
Multiple agents (there are people who may dirty the room)
co
Sequential (next action depends on previous action)
eH w
Static (the environment may change, but not while the robot is deciding)
o.
Continuous (the wheels of the robot may go in any direction, and stop at any
point). rs e
ou urc
2. [Search] The diagram below depicts the street map of a city, where the nodes rep-
resent intersections between streets. The table below gives the streets covered by an
o
intersection, and the cost of installing a fire hydrant in an intersection. You want to
aC s
put fire hydrants in some intersections so that each street has at least one fire hydrant.
vi y re
Your objective is to minimize the cost of installing the fire hydrants.
1 5 2
P l
PP Streets
ed d
PP
4 P l7 Intersection Cost
3 PP Covered
ar stu
l
P
PP l
1 3 3, 4, 5
2 P
Pl
3a
4
2 2 5, 6, 7
a aa1 6 3 4 1, 2, 3
aa
is
a
5a 1 8 4 5 2, 4, 7, 8
aa
aa 5 1 1, 6
Th
6
6 1 1, 8
(a) Draw the search path generated by the Greedy Best-first Search algorithm to de-
sh
termine the locations of the fire hydrants.
Use the function f = cheapest intersection. If two or more intersections have the
same cost, use first the intersection with the lowest number. If all the streets
covered by a newly considered intersection are already covered by previously in-
stalled fire hydrants, then discard this intersection.
List the intersections containing fire hydrants. What is the cost of your solution?
SOLUTION:
Intersection 5, total coverage (1,6), total cost = 1.
This study source was downloaded by 100000796901680 from CourseHero.com on 04-10-2021 17:01:26 GMT -05:00
1
https://www.coursehero.com/file/30522324/Exam-Prep-exercises12solnpdf/
, Intersection 6, total coverage (1,6,8), total cost = 2.
Intersection 2, total coverage (1,5,6,7,8), total cost = 4.
Intersection 1, total coverage (1,3,4,5,6,7,8), total cost = 7.
Intersection 3, total coverage (1,2,3,4,5,6,7,8), total cost = 11.
(b) Draw the search paths generated by the Backtrack procedure to determine the
locations of the fire hydrants, where a rule corresponds to assigning a fire hydrant
to an intersection. Assume that the search is discontinued when cost≥10.
Use the heuristic intersection that covers the most streets to order the rules. In
case of a tie, order the rules in ascending order of their intersection number.
When backtracking, state clearly the reason for backtracking. Which intersections
contain fire hydrants? What is the cost of your solution?
SOLUTION:
m
er as
co
eH w
o.
rs e
ou urc
o
(c) Draw the search tree generated by the Graphsearch procedure to determine the
aC s
locations of the fire hydrants, using the following heuristic function to estimate
vi y re
the cost of allocating the remaining fire hydrants:
Number of streets still to be covered. In case of a tie, order the nodes in OPEN in
descending order of their depth, and in ascending order of the number of the
ed d
last intersection to which a fire hydrant was allocated.
ar stu
When performing Graphsearch, in the first level, the operators are the intersec-
tions that cover Street #1, namely 3, 5 and 6; in the second level, the operators
are the intersections that cover Street #2, namely 3 and 4; etc. If a street is
already covered by a previous expansion, consider the next street.
is
Indicate clearly the values of g, h and f at each node, and the values of OPEN and
Th
CLOSED after each expansion. Also, indicate in roman numerals the order of
expansion of the nodes. Which intersections contain fire hydrants? What is the
cost of your solution?
sh
This study source was downloaded by 100000796901680 from CourseHero.com on 04-10-2021 17:01:26 GMT -05:00
2
https://www.coursehero.com/file/30522324/Exam-Prep-exercises12solnpdf/
Solutions to Practice Questions for Final Exam
1. [Agents] Consider the vacuum agent presented in class, but assume that the room
has 8 squares and a square can get dirty after it has been cleaned.
(a) Use PEAS to specify the task environment.
SOLUTION:
Performance measure: cleanliness of the room, number of moves.
Environment: room, furniture, people.
Actuators: vaccum cleaner.
Sensors: vision, touch.
(b) Specify the attributes of the environment.
SOLUTION:
Known (the conditions of the environment are known)
Stochastic (squares can become dirty at any time)
m
Observable (everything can be seen)
er as
Multiple agents (there are people who may dirty the room)
co
Sequential (next action depends on previous action)
eH w
Static (the environment may change, but not while the robot is deciding)
o.
Continuous (the wheels of the robot may go in any direction, and stop at any
point). rs e
ou urc
2. [Search] The diagram below depicts the street map of a city, where the nodes rep-
resent intersections between streets. The table below gives the streets covered by an
o
intersection, and the cost of installing a fire hydrant in an intersection. You want to
aC s
put fire hydrants in some intersections so that each street has at least one fire hydrant.
vi y re
Your objective is to minimize the cost of installing the fire hydrants.
1 5 2
P l
PP Streets
ed d
PP
4 P l7 Intersection Cost
3 PP Covered
ar stu
l
P
PP l
1 3 3, 4, 5
2 P
Pl
3a
4
2 2 5, 6, 7
a aa1 6 3 4 1, 2, 3
aa
is
a
5a 1 8 4 5 2, 4, 7, 8
aa
aa 5 1 1, 6
Th
6
6 1 1, 8
(a) Draw the search path generated by the Greedy Best-first Search algorithm to de-
sh
termine the locations of the fire hydrants.
Use the function f = cheapest intersection. If two or more intersections have the
same cost, use first the intersection with the lowest number. If all the streets
covered by a newly considered intersection are already covered by previously in-
stalled fire hydrants, then discard this intersection.
List the intersections containing fire hydrants. What is the cost of your solution?
SOLUTION:
Intersection 5, total coverage (1,6), total cost = 1.
This study source was downloaded by 100000796901680 from CourseHero.com on 04-10-2021 17:01:26 GMT -05:00
1
https://www.coursehero.com/file/30522324/Exam-Prep-exercises12solnpdf/
, Intersection 6, total coverage (1,6,8), total cost = 2.
Intersection 2, total coverage (1,5,6,7,8), total cost = 4.
Intersection 1, total coverage (1,3,4,5,6,7,8), total cost = 7.
Intersection 3, total coverage (1,2,3,4,5,6,7,8), total cost = 11.
(b) Draw the search paths generated by the Backtrack procedure to determine the
locations of the fire hydrants, where a rule corresponds to assigning a fire hydrant
to an intersection. Assume that the search is discontinued when cost≥10.
Use the heuristic intersection that covers the most streets to order the rules. In
case of a tie, order the rules in ascending order of their intersection number.
When backtracking, state clearly the reason for backtracking. Which intersections
contain fire hydrants? What is the cost of your solution?
SOLUTION:
m
er as
co
eH w
o.
rs e
ou urc
o
(c) Draw the search tree generated by the Graphsearch procedure to determine the
aC s
locations of the fire hydrants, using the following heuristic function to estimate
vi y re
the cost of allocating the remaining fire hydrants:
Number of streets still to be covered. In case of a tie, order the nodes in OPEN in
descending order of their depth, and in ascending order of the number of the
ed d
last intersection to which a fire hydrant was allocated.
ar stu
When performing Graphsearch, in the first level, the operators are the intersec-
tions that cover Street #1, namely 3, 5 and 6; in the second level, the operators
are the intersections that cover Street #2, namely 3 and 4; etc. If a street is
already covered by a previous expansion, consider the next street.
is
Indicate clearly the values of g, h and f at each node, and the values of OPEN and
Th
CLOSED after each expansion. Also, indicate in roman numerals the order of
expansion of the nodes. Which intersections contain fire hydrants? What is the
cost of your solution?
sh
This study source was downloaded by 100000796901680 from CourseHero.com on 04-10-2021 17:01:26 GMT -05:00
2
https://www.coursehero.com/file/30522324/Exam-Prep-exercises12solnpdf/
