TM366 2023 2024 2 TMA (Egy)

TM366: Artificial intelligence
Tutor-Marked Assignment (TMA) Spring 23/24
Cut-Off Date: Based on the Published Deadline.

Total Marks: …. marks turned to 15 marks
Contents
Warnings and Declaration…………………………………….………………………………......1
Question 1 ……………….…………………………………. ………………………………...…..2
Question 2 ………………………………………………………………………………….…..…..3
Question 3 ………………………………………………………………………………….…..…..4
Marking Criteria ...…………..………………………………………………………….………..…5
Plagiarism Warning:
As per AOU rules and regulations, all students are required to submit their own TMA
work and avoid plagiarism. The AOU has implemented sophisticated techniques for
plagiarism detection. You must provide all references in case you use and quote
another person's work in your TMA. You will be penalized for any act of plagiarism as
per the AOU's rules and regulations.
Declaration of No Plagiarism by Student (to be signed and submitted by student

with TMA work):
I hereby declare that this submitted TMA work is a result of my own efforts and I have
not plagiarized any other person's work. I have provided all references of information
that I have used and quoted in my TMA work.
Name of Student:……………………………..
Signature:…………………………………………...
Date:…………………………………………………
TM366 / TMA Page 1 of 6 2023/2024 Fall

Question 1, [20 marks]
a) Given the following search graph and adopting depth-first search:
1. Trace the states inside the search agenda until reaching the goal state.
2. How many states will be visited until reaching the goal state?
3. Mention the solution path if exist to the goal state.
Assume that the goal state is 15.
b) Apply the same three items in a) adopting breadth-first search
c) Compare the two methods adopted in a),b)

Having the following goal state for the XO game:
X XX
E E E
E E E
E E E
X XX
E E E
E E E
E E E
X XX
X EE
X EE
X EE

E XE
E XE
E XE
E EX
E EX
E EX
X E E
E XE
E E X
E E X
E XE
X E E
and having the following current state s=

O E X
E E X
X OO
a. Write the direct children states for s following the XO actions.

b. Mention one possible heuristic function for this game
c. Based on b, calculate the heuristic value for each child state obtained in a.

In a TSP problem with 5 cities, cities are connected as shown in the figure:
the following table shows the distances between different cities

C0 C1 C2 C3 C4
C0 0.00 45.00 55.00 19.00 67.00
C1 45.00 0.00 85.00 26.00 25.00
C2 55.00 85.00 0.00 69.00 97.00
C3 19.00 26.00 69.00 0.00 51.00
C4 67.00 25.00 97.00 51.00 0.00
[Distance of 0 means distance is not applicable.

]The following table shows the pheromone in units between different cities
C0 C1 C2 C3 C4
C0 0.00 43.94 0.00 17.75 9.42
C1 43.94 0.00 0.00 32.35 7.64
C2 0.00 0.00 0.00 21.26 49.56
C3 17.75 32.35 21.26 0.00 0.00
C4 9.42 7.64 49.56 0.00 0.00
 Assume that an ant has followed the following route:[2,3,1,0,4,] and back to source
a. Calculate the total cost of the above route.

b. Calculate the ant's switching probabilities for the first 2 steps in the above route assuming
pheromone exponent parameter α=0.38 and heuristic exponent parameter β=0.74.
c. Calculate the updated pheromone amounts after applying the ACO evaporation step
assuming ρ=0.90.
d. Calculate the updated pheromone amounts after applying the ACO depositing step
assuming Q=34.42.
Given the following particle positions in a PSO minimization optimization process:
X1 X2 X3 X4 X5 X6
-2 0 0 0 -1 -1
1 1 2 2 1 1
1 -1 0 1 -1 1
and given that each particle's attached velocity is:
V1 V2 V3 V4 V5 V6
0.5 -1.4 1.8 -0.4 -1.5 0.3
-0.4 0.8 -0.4 2.0 -1.3 0.7
0.2 -0.6 -0.4 0.5 1.1 -1.2
and given each particle's local best as:
P1 P2 P3 P4 P5 P6
-1 1 -1 -1 2 1
1 -1 1 1 -1 -1
-2 -1 2 0 -2 0
assuming the global best is:[-1,1,-2,]
Calculate the updated positions and velocities for the next 4 iterations
Assume Φ1=0.8 and Φ2=0.4
The function to be minimized is:6x12+8x23+1x35
Given the following search graph, write the sequence of node numbers in the search agenda across
the search life-time and using A* search.

Assume the following heuristic value per node:
Node ID Node Heuristic value
1 191
2 486
3 348
4 440
5 0
6 81
Assume distance between cities are as mentioned on the links

Apply A* algorithm showing intermediate values for the Agenda, g(n), h(n)
Source city is :C2
Destination city:C5

TM366 2023 2024 2 TMA (Egy)

Uploaded by

Copyright:

Available Formats

TM366 2023 2024 2 TMA (Egy)

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

TM366 2023 2024 2 TMA (Egy)

Uploaded by

Copyright:

Available Formats

TM366: Artificial intelligence

Tutor-Marked Assignment (TMA) Spring 23/24

Cut-Off Date: Based on the Published Deadline.

Declaration of No Plagiarism by Student (to be signed and submitted by student

TM366 / TMA Page 1 of 6 2023/2024 Fall

Question 2, [20 marks]

TM366 / TMA Page 2 of 6 2023/2024 Fall

and having the following current state s=

a. Write the direct children states for s following the XO actions.

TM366 / TMA Page 3 of 6 2023/2024 Fall

the following table shows the distances between different cities

[Distance of 0 means distance is not applicable.

TM366 / TMA Page 4 of 6 2023/2024 Fall

TM366 / TMA Page 5 of 6 2023/2024 Fall

Assume distance between cities are as mentioned on the links

TM366 / TMA Page 6 of 6 2023/2024 Fall

You might also like