Problem Solving
Code: 106570 ECTS Credits: 6| Degree | Type | Year | Semester |
|---|---|---|---|
| 2504392 Artificial Intelligence | OB | 2 | 1 |
Contact
- Name:
- Pedro Meseguer Gonzalez
- Email:
- pedro.meseguer@uab.cat
Use of Languages
- Principal working language:
- english (eng)
- Some groups entirely in English:
- Yes
- Some groups entirely in Catalan:
- No
- Some groups entirely in Spanish:
- No
External teachers
- Jordi Levy Diaz
Prerequisites
?
Objectives and Contextualisation
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.
Competences
- Analyse and solve problems effectively, generating innovative and creative proposals to achieve objectives.
- Design, implement, analyse and validate efficient and robust algorithmic solutions to computational problems derived from the design of intelligent systems.
- Identify, understand and apply the fundamental concepts and techniques of knowledge representation, reasoning and computational learning for the solution of artificial intelligence problems.
- Introduce changes to methods and processes in the field of knowledge in order to provide innovative responses to society's needs and demands.
- Students can apply the knowledge to their own work or vocation in a professional manner and have the powers generally demonstrated by preparing and defending arguments and solving problems within their area of study.
Learning Outcomes
- Analyse a situation and identify areas for improvement.
- Analyse and solve problems effectively, generating innovative and creative proposals to achieve objectives.
- Apply metaheuristics and evolutionary and bio-inspired computing techniques to solve optimisation problems.
- Conceptualise and model game problems as search problems.
- Students can apply the knowledge to their own work or vocation in a professional manner and have the powers generally demonstrated by preparing and defending arguments and solving problems within their area of study.
- Understand constraint satisfaction techniques for representing and solving problems in the field of AI.
- Understand model-based reasoning and inference in AI.
- Understand the concepts of combinatorial explosion and heuristics.
- Understand the state space representation of a given problem and its search-based resolution.
Content
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
Methodology
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.
Students will be divided into groups, with the following function in terms of problems:
• at the beginning of the course, each group will receive a set of problems to solve,
• at the request of the teacher, a group solves one of their problems in a class of problems,
• the groups know when the kinds of problems are, and the type of problems to be solved; he does not know if he will have to leave or not in a specific class,
• the teacher chooses the group that has to solve a problem,
• a chosen group has to deliver the solved problem to the teacher for scoring,
• as you solve your problem, the group gets a grade (common for all group members),
• If the group fails, a new submission must be made to the teacher a week later.
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 must be borne 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 to have 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.
Annotation: Within the schedule set by the centre or degree programme, 15 minutes of one class will be reserved for students to evaluate their lecturers and their courses or modules through questionnaires.
Activities
| Title | Hours | ECTS | Learning Outcomes |
|---|---|---|---|
| Type: Directed | |||
| Preparation of problems and practices | 35.5 | 1.42 | 2, 1, 7, 9, 6, 8, 5, 4, 3 |
| Sessions of theory and problems | 50 | 2 | 2, 1, 7, 9, 6, 8, 5, 4, 3 |
| Type: Autonomous | |||
| Assimilation of sessions of theory and problems | 60 | 2.4 | 2, 1, 7, 9, 6, 8, 5, 4, 3 |
Assessment
The assessment of the subject will take into account three types of assessment activities: Two midterm exams as an individual assessment and the realization of problems/practices by groups of students.
The final grade of the course is obtained by combining the assessment of these 3 activities as follows:
Final Grade = (0.6 the two partial tests of individual evaluation) + (0.4 problems/practices)
Individual evaluation: a minimum grade of 5 must be achieved to pass the subject.
Problems/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.
• Problems/practices: in case of not reaching 5 in the problems/practices, the group has to resubmit the corrected work (obviously, there is no time to make a second oral presentation) 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 or attempting 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.
Assessment Activities
| Title | Weighting | Hours | ECTS | Learning Outcomes |
|---|---|---|---|---|
| Individual evaluation | 0.6 | 4 | 0.16 | 2, 1, 7, 9, 6, 8, 5, 4, 3 |
| Problem delivery/practices | 0.4 | 0.5 | 0.02 | 2, 1, 7, 9, 6, 8, 5, 4, 3 |
Bibliography
Artificial Intelligence. A modern approach. Stuart Russell, Peter Norvig. 4th edition. Pearson, 2020.
Software
To be decided.