Description
Also the code from problem 1 should be written in vscode or devc++ or any other programming program you want to
Unformatted Attachment Preview
Machine Translated by Google
YS02 Artificial Intelligence – Winter Semester 2023-2024
Work Tuesday
2 units of the total grade in the course
Excellent=240 points, there are also 200 bonus points
Announcement Date: 09/12/2023
Delivery Date: 07/01/2024 at 23:59
Copying: In case of copying phenomena, those involved will be graded with a grade of zero.
Problem 1: (The radio link frequency assignment problem – RLFA)
In this question you have to solve the RLFA constraint satisfaction problem (radio link frequency
assignment) using the FC, MAC and FC-CBJ algorithms. The RLFA problem is defined as follows. We
have to assign frequencies to radio links. The variables of the problem are the radio links and the fields
of the variables are the available frequencies. Fields are sets of positive numbers. Binary constraints
between variables are also given. Constraints are of the form | ÿ | > where and are variables and a
positive number. We want to find an assignment of frequencies (values) to radio assignments
(variables) that satisfies all constraints. More details on the problem can be found at https://miat.inrae.fr/
schiex/rlfap.shtml .
You have to do the following:
1. See the rlfap.zip zip file we have posted with the exercise. This folder contains 12 instances of
the problem to test your algorithms. Read the odigies.txt file to understand the contents of the
folder.
2. Implement the FC, MAC, and FC-CBJ algorithms and apply them to the problem. It is
recommended to use dynamic variable ordering using the dom/wdeg heuristic
from the article
F. Boussemart, F. Hemery, C. Lecoutre and L. Sais. Boosting Systematic Search by
Weighting Constraints. Proc. of ECAI 2004, pages 146–150, 2004. Available at http://
www.frontiersinai.com/ecai/ecai2004/ecai04/pdf/p0146.pdf .
You’ll also need to write code to read the above files, and load them into whatever structures
you use in memory for the variables, fields, and constraints. Your implementation must be
based on the
Python code available at https://github.com/aimacode/aima-python/blob/master/csp.py .
3. Experimentally compare the algorithms you implemented using the examples we gave you and
setting appropriate metrics. You should explain which one
Machine Translated by Google
comparison criteria you used and why. Present your results clearly using tables and comment
on them.
4. Try to solve the given instances with the local search algorithm
MINCONFLICTS. Comment on the results obtained and compare them with those of the
previous question. (200 units)
Problem 2: (Modeling with constraint satisfaction problems)
The “Ano ki Kato Milia” philological association has its annual conference at the hotel “I Orea Thea”
located in the village of Ano Milia. For the last day of the conference starting at 9 am, 4 readings of
recent books by members of the club are scheduled: Mr. John, Mrs. Maria, Mrs. Olga and Mr. Mitsos
(in that order). Each reading is done by the author himself and lasts 30 minutes. At the end of the
readings, club members choose the best book of the year. The winner receives a prize of a golden
apple which is kept in the hotel safe during the conference.
Unfortunately when the club president and the hotel manager go to fetch the golden apple for the
award, they discover that the safe has been broken into and the apple has been stolen. The policeman
Siespis who undertook to solve the theft quickly came to three suspects: Giannis, Maria and Olga.
According to the testimony of the hotel employees, these 3 left the conference room for a while, during
the readings, but returned before 11:00, when the readings end and the selection of the winner begins.
Employees cannot recall any further relevant details. All three suspects gave the same alibi:
“I left the hall after reading from my book, and went to my room to rest for a while. I fell asleep
there but as soon as I woke up, I ran back to the hall. I didn’t steal the golden apple.”
It takes 5-10 minutes to get from the conference room to your room. It takes 20-30 minutes to go from
the conference room to the room where the safe is located. It takes 45-90 minutes to breach the safe.
Officer Siespis carefully examined the alibis of the three suspects and arrested one of them.
1. Precisely define a constraint satisfaction problem that encodes all the temporal information
given by the above text. 2. To use terms of the theory of
constraint satisfaction problems to
explain which suspect Officer Siespis arrested and why.
3. Suggest a constraint propagation method that Siespis could have used to reach his decision.
Machine Translated by Google
(10+5+5=20 credits)
Problem 3: (Modeling with constraint satisfaction problems)
Consider the problem of scheduling 5 actions A1, …, A5. Each action takes 60 minutes to complete.
Each action can start at 9:00, 10:00 or 11:00. Actions can be done in parallel as long as the following
time constraints are met:
• A1 must start after A3.
• A3 must start before A4 and after A5.
• A2 cannot be performed at the same time as A1 or A4.
• A4 cannot start at 10:00.
You have to do the following:
1. Model the above scheduling problem as a constraint satisfaction problem.
2. Draw the constraint graph
3. Apply the AC-3 edge consistency algorithm to the problem until it becomes consistent
in terms of edges (arc-consistent).
(5+5+10=20 credits)
Problem 4: (Time Calculus)
Consider the problem of checking the consistency of disjoint time constraints described in the article
https://cdn.aaai.org/AAAI/1998/AAAI98-034.pdf . Carefully study the first 4 pages of the article and
implement the algorithms presented by following the article closely. Compare the algorithms you
implemented with each other by creating a figure like the one in Figure 1 (this figure will be the final
result of your study). You will definitely need to refer to other literature mentioned in the article above.
You can use code from the AIMA book website mentioned in Problem 1.
(200 bonus points)
Purchase answer to see full
attachment
