
Problem Solving
Code: 106570Credits: 6
| Degree programme | Type | Course |
|---|---|---|
| Bachelor in Artificial Intelligence | OB | 2 |
Contact lecturer
- Name :
- Pedro Meseguer Gonzalez
- Email :
- pedro.meseguer@uab.cat
Teaching staff (external to UAB)
- Instructor/a prácticas 1
- Pedro Meseguer González
- Instructor/a prácticas 2
- Jordi Levy Diaz
Group languages
You can consult this information at the end of the document.
Prerequisites
?
Objectives
This subject will offer a complete vision (including algorithmic methods) of what is meant by problem solving in AI, focused on search problems (heuristics or with metaheuristics), search with an adversary and games, reasoning with restrictions and Boolean satisfiability.
Learning outcomes
- CM06 (Integrate reasoning strategies based on logic modelling and search algorithms into AI applications) Integrate reasoning strategies based on logic modelling and search algorithms into AI applications
- KM20 (Describe the fundamentals of statespace-based problem representation and its solution by search, using the concepts of heuristics and combinatorial explosion.) Describe the fundamentals of statespace-based problem representation and its solution by search, using the concepts of heuristics and combinatorial explosion.
- KM21 (Identify constraint satisfaction techniques to represent and solve problems in the field of artificial intelligence.) Identify constraint satisfaction techniques to represent and solve problems in the field of artificial intelligence.
- SM21 (Apply search algorithms, metaheuristics, and evolutionary and bio-inspired computing techniques to solve optimisation problems in the field of artificial intelligence.) Apply search algorithms, metaheuristics, and evolutionary and bio-inspired computing techniques to solve optimisation problems in the field of artificial intelligence.
- SM22 (Apply modelling with logical formalisms and methods of satisfying constraints in the resolution of reasoning problems in artificial intelligence.) Apply modelling with logical formalisms and methods of satisfying constraints in the resolution of reasoning problems in artificial intelligence.
Contents
HEURISTIC SEARCH
Blind search
Heuristic search
Heuristics
LOCAL SEARCH. METAHEURISTICS.
Optimization
Metaheuristics
Online search
ADVERSARIAL SEARCH. GAMES.
Zero-sum games.
Mini-max. Alpha-beta.
Modern strategies: MCTS
CONSTRAINT REASONING
Definitions and examples
Constraint networks and arc consistency
Look-ahead
BOOLEAN SAT
Introduction and applications
Resolution and DPLL
Learning and backjumping
Restarts and clause deletion
Learning activities and methodology
| Title | Hours | ECTS | Learning outcomes |
|---|---|---|---|
| Sessions of theory and problems | 50 | 2 | CM06, KM20, KM21, SM21, SM22 |
| Assimilation of sessions of theory and problems | 60 | 2.4 | CM06, SM21, SM22 |
| Preparation of problems and practices | 35.5 | 1.42 | CM06, SM21, SM22 |
The sessions will be face-to-face in class and will be organized to introduce the contents of the subject through master classes.
In addition, there will be classes of problems and/or practices to strengthen the contents of the theory classes.
Other activities may be the reading and presentation of articles related to the subject.
The dynamic and proactive attitude of the student body, in order to achieve the skills of the subject, will be especially appreciated.
Classes will be organized in two sessions of two hours per week with all students.
Most of the classes will be theory, with problem/practice classes interspersed.
Students will know in advance when those kinds of problems/practices will happen.
Students are encouraged to bring their own laptop to class if they have one.
Special attention will be devoted to the practice classes. These will be unfolded in parallel
(that is, the group willl be divided in two, and each half will be taught by a different instructor).
A small number of practices will be developed by each group of students and sent to the instructors.
If instructors consider that a group does not pass a particular practice, the group,
after receiving the feedback, will have a second opportunity to correct and present the practice.
In the theory classes, the concepts that are detailed in the syllabus of the subject will be worked on.
In some cases, the possibility of making explanatory videos available to the student that
the student must watch before the class session will be considered.
Each student will have to complete the face-to-face classes with autonomous personal work in carrying out the readings,
problems and practices that are proposed and that should serve to finish understanding the contents of the subject.
It should be keep in mind that the syllabus of the subject has a logical continuity throughout the course,
so that in order to follow a class correctly it is necessary tohave assimilated what has been explained in previous sessions.
The management of the teaching of the subject will be done through the UAB Virtual Campus platform,
which will be used to view the materials, manage the practice groups, make the corresponding deliveries,
see the notes, communicate with the teachers, etc.
Assessment
Continuous assessment activities
| Title | Weight | Hours | ECTS | Learning outcomes |
|---|---|---|---|---|
| Individual evaluation | 0.6 | 4 | 0.16 | KM20, KM21, SM21, SM22 |
| Problem delivery/practices | 0.4 | 0.5 | 0.02 | CM06, SM21, SM22 |
The assessment of the subject will take into account two types of assessment activities: Two midterm exams as an individual assessment and the realization of practices by groups of students.
The final grade of the course is obtained by combining the assessment of these activities as follows:
Final Grade = (0.6 the two partial tests of individual evaluation) + (0.4 practices)
Individual evaluation: a minimum grade of 5 must be achieved to pass the subject.
Practices:a minimum grade of 5 in this activity must be obtained in order to pass the subject.
Individual assessment: this section includes the results of the individual tests that will be done throughout the course.
There will be partial tests that will be done during the academic period of the course and a final test during the official exam period.
This final test will be a recovery test and will only have to be taken by students who have not passed one of the two partial ones.
If one of the two parts has been passed, but the other has not,
only the part of the subject corresponding to the part that has not been passed must be retaken in this test.
• A minimum grade of 4.5 must be obtained in each of the two parts in order to pass the course.
• The final grade will be the average of the two partials:
Individual Assessment = (0.5 * Partial1) + (0.5 * Partial 2)
Recovery:
• First partial: a student who fails the first partial can recover it in the final exam.
• Second partial: a student who fails the first partial can recover it in the final exam.
• Practices: in case of not reaching 5 in the practices, the group has to resubmit the corrected work one week later, so that it includes the instructions of the teachers.
Not assessable: A student will be considered non-assessable (NA) if he / she does not participate in the presentation and
does not take any of the following assessment tests: Part 1, Part 2, Final Recovery Test.
Suspended: If the calculation of the final grade is equal to or higher than 5 but does not reach the minimum required in any of the evaluation activities,
the final grade will be suspended and a 4.5 will be placed on the grade of the transcript of the student.
Honors: Granting an honors degree is the decision of the faculty responsible for the subject. UAB regulations state that MHs can only be awarded to students
who have obtained a final grade equal to or higher than 9.00. Up to 5% MH of the total number of students enrolled can be awarded.
Important Note: Copies and plagiarism Without prejudice to other disciplinary measures deemed appropriate, and in accordance with current academic regulations, irregularities committed by a student that may lead to a variation in the grade will be graded with a zero (0). Assessment activities qualified in this way and by this procedure will not be recoverable. If it is necessary to pass any of these assessment activities to pass the subject, this subject will be suspended directly, without the opportunity to retake it in the same course. These irregularities include, but are not limited to: • The total or partial copy of an internship, report, or any other assessment activity • Let copy • Present a group work not done entirely by the group members • Present as own materials prepared by a third party, even if they are translations or adaptations, and in general works with non-original and exclusive elements of the student • Have communication devices (such as mobile phones, smart watches, etc.) accessible during individual theoretical-practical assessment tests (exams). • Talk to classmates during individual theoretical-practical assessment tests (exams); • Copying orattempting to copy other students during the theoretical-practical assessment tests (exams); • Use or attempt to use writings related to the subject during the performance of the theoretical-practical assessment tests (exams), when these have not been explicitly allowed. In these cases, the numerical grade of the transcript will be the lower value between 3.0 and the weighted average of the grades (and therefore it will not be possible to pass it by compensation). Copy of the program code will be used in the evaluation of problem and practice deliveries. Note on planning assessment activities: The dates of continuous evaluation and delivery of works will be published at the beginning of the course and may be subject to schedule changes for reasons of adaptation to possible incidents. These changes will always be reported to the Virtual Campus as it is understood that this is the usual platform for the exchange of information between teachers and students.
Bibliography
Artificial Intelligence. A modern approach. Stuart Russell, Peter Norvig. 4th edition. Pearson, 2020.
Software
To be decided.
Course groups and languages
The information provided is provisional until November 30. After this date, you will be able to consult the language of each group through this link. To access the information, you will need to enter the course CODE
| Type of teaching | Group | Language | Semester | Shift |
|---|---|---|---|---|
| (TE) Theory | 71 | English | first semester | afternoon |
| (PAUL) Classroom practices | 711 | English | first semester | afternoon |
| (PLAB) Practical laboratories | 711 | English | first semester | afternoon |
| (PLAB) Practical laboratories | 712 | English | first semester | morning-mixed |