Basic Algorithms for Artificial Intelligence

Credits
6
Types
Compulsory
Requirements
This subject has not requirements , but it has got previous capacities
Department
CS
Web
https://sites.google.com/upc.edu/abia
La asignatura da a conocer y permite dominar a las diversas familias de algoritmos de resolución de problemas utilizados en Inteligencia Artificial. Se hace especial énfasis en la búsqueda en un espacio de posibles configuraciones (espacio de estados, espacio de soluciones, espacio de variables, espacio de planes). También se estudian los algoritmos de resolución de problemas basados en métodos evolutivos y bioinspirados.
El objetivo es que los estudiantes sean capaces de analizar un problema y aprovechar y/o adaptar el esquema algorítmico más adecuado para su resolución.

Teachers

Person in charge

Others

Weekly hours

Theory
2
Problems
0
Laboratory
2
Guided learning
0
Autonomous learning
6

Competences

Transversal Competences

Transversals

  • CT4 [Avaluable] - Teamwork. Be able to work as a member of an interdisciplinary team, either as a member or conducting management tasks, with the aim of contributing to develop projects with pragmatism and a sense of responsibility, taking commitments taking into account available resources.

    • Basic

  • CB2 - That the students know how to apply their knowledge to their work or vocation in a professional way and possess the skills that are usually demonstrated through the elaboration and defense of arguments and problem solving within their area of ??study.

    • Technical Competences

    Especifics

  • CE03 - To identify and apply the basic algorithmic procedures of computer technologies to design solutions to problems by analyzing the suitability and complexity of the proposed algorithms.
  • CE13 - To evaluate the computational complexity of a problem, identify algorithmic strategies that can lead to its resolution and recommend, develop and implement the one that guarantees the best performance in accordance with the established requirements.
  • CE14 - To master the foundations, paradigms and techniques of intelligent systems and to analyze, designing and build computer systems, services and applications that use these techniques in any field of application, including robotics.

    • Generic Technical Competences

    Generic

  • CG2 - To use the fundamental knowledge and solid work methodologies acquired during the studies to adapt to the new technological scenarios of the future.
  • CG4 - Reasoning, analyzing reality and designing algorithms and formulations that model it. To identify problems and construct valid algorithmic or mathematical solutions, eventually new, integrating the necessary multidisciplinary knowledge, evaluating different alternatives with a critical spirit, justifying the decisions taken, interpreting and synthesizing the results in the context of the application domain and establishing methodological generalizations based on specific applications.
  • CG8 - Perform an ethical exercise of the profession in all its facets, applying ethical criteria in the design of systems, algorithms, experiments, use of data, in accordance with the ethical systems recommended by national and international organizations, with special emphasis on security, robustness , privacy, transparency, traceability, prevention of bias (race, gender, religion, territory, etc.) and respect for human rights.

    • Objectives

    1. To know the main algorithms for searching and exploring configuration spaces
      Related competences: CB2, CT4, CE03, CE13, CE14, CG2, CG4,
    2. To know the bioinspired and evolutionary algorithms
      Related competences: CB2, CE03, CE13, CE14, CG4, CG2,
    3. To know the automated planning methods
      Related competences: CT4, CE03, CE13, CE14, CG2, CG4, CB2,
    4. To be able to analyze problems and choose the best algorithmic strategy
      Related competences: CB2, CE03, CE13, CE14, CG2, CG4, CG8,

    Contents

    1. Introduction to problem solving through search
      Introduction to automatic problem solving methodologies. Representation as a state space. Basic uninformed search algorithms in the state space. Limitations.
    2. Heuristic Search
      Knowing and understanding search methods guided by heuristic functions. Properties that must fulfill heuristic functions.
    3. Local Search
      Local search algorithms and their motivation are presented and studied. They are protrayed as heuristic methods for solving computationally difficult optimization problems, using strategies for maximizing or minimizing some criteria that characterize possible solutions.
    4. Adversarial Search.Games
      Games are presented as an extension of minimization and maximization strategies. They are also explored from the more general perspective of game theory, focusing on a broad taxonomy that includes competitive, cooperative, zero-sum, infinite, repeated games, and so on, with an exploration of concepts and conditions of equilibrium.
    5. Introduction to constraint satisfaction
      Problem-solving methods for constraint satisfaction are presented as a way of exploring space using the constraints imposed on the set of variables that characterize the problem and its possible solutions.
      Methods of backpropagation and propagation of constraints are presented, studied and compare and they are also connected with logical forms of expressing the satisfaction of constraints.
    6. Automated Planning
      Strategies for exploring the sequencing of actions over time in order to efficiently achieve the goals of smart agents are presented. They are connected with optimization in a multidimensional space. The main planning algorithms are presented by relating them to exploration, search and optimization strategies: classical, temporal, probabilistic, and hierarchical planning for example, and they are portrayed as an exploration in a space of plans. Reuse of plans is also studied. A planning language is presented to be able to start planning exercises and projects.

    Activities

    Activity Evaluation act


    Problem Solving through Heuristic Search

    Students not only should attend the teacher lectures, but also do exercises on the use of search algorithms, and participate in discussions with the teacher and other students on when is best to use each of the algorithms. In the laboratory students will apply what they learned in a moderate problem.
    • Theory: Theoretical presentation of search and main algorithms.
    • Problems: Search and programming exercises and problem solving with heuristic search.
    • Laboratory: Development of small programs to explore the various search strategies.
    • Autonomous learning: Study and practice of search strategies.
    Objectives: 1 4
    Contents:
    Theory
    6h
    Problems
    0h
    Laboratory
    6h
    Guided learning
    0h
    Autonomous learning
    12h

    Problem Solving through Local Search

    Students not only should attend the teacher lectures, but also do exercises on the use of search algorithms, and participate in discussions with the teacher and other students on when is best to use each of the algorithms. In the laboratory students will apply what they learned in a moderate problem.
    Objectives: 1 2 4
    Contents:
    Theory
    7h
    Problems
    0h
    Laboratory
    5h
    Guided learning
    0h
    Autonomous learning
    12h

    Practical Assignment 1: Problem solving as a Search on a configuration space

    Carrying out the practical assignment on Search algorithms. Students will do most of the practical work independently in non-presencial hours. There willl be some face-to-face hours with the teacher to guide the resolution and to resolve doubts. A report must be submitted at the end of the practical assigment.
    Objectives: 1 4
    Contents:
    Theory
    0h
    Problems
    0h
    Laboratory
    2h
    Guided learning
    0h
    Autonomous learning
    16.5h

    Problem Solving through Adversarial Search. Games

    Students not only should attend the teacher lectures, but also do exercises on the use of search algorithms, and participate in discussions with the teacher and other students on when is best to use each of the algorithms. In the laboratory students will apply what they learned in a moderate problem.
    Objectives: 1 4
    Contents:
    Theory
    3h
    Problems
    0h
    Laboratory
    3h
    Guided learning
    0h
    Autonomous learning
    6h

    Delivery of practical exercise 1: Problem solving as a Search on a configuration space

    Delivery of the report on the search algorithms practical assignment that students have done.
    Objectives: 1 4
    Week: 7 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Midterm exam


    Objectives: 1 2 4
    Week: 8
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Constraint Satisfaction and Optimization

    Students not only should attend the teacher lectures, but also do exercises on the use of search algorithms, and participate in discussions with the teacher and other students on when is best to use each of the algorithms. In the laboratory students will apply what they learned in a moderate problem.
    Objectives: 1 4
    Contents:
    Theory
    4h
    Problems
    0h
    Laboratory
    4h
    Guided learning
    0h
    Autonomous learning
    10h

    Automated Planning

    Students not only should attend the teacher lectures, but also do exercises on the use of search algorithms, and participate in discussions with the teacher and other students on when is best to use each of the algorithms. In the laboratory students will apply what they learned in a moderate problem.
    Objectives: 3 4
    Contents:
    Theory
    8h
    Problems
    0h
    Laboratory
    7h
    Guided learning
    0h
    Autonomous learning
    15h

    Practical Assignment 2: Problem solving through Automated Planning

    Carrying out the practical assignment on Automated Planninf. Students will do most of the practical work independently in non-presencial hours. There willl be some face-to-face hours with the teacher to guide the resolution and to resolve doubts. A report must be submitted at the end of the practical assigment.
    Objectives: 3 4
    Contents:
    Theory
    0h
    Problems
    0h
    Laboratory
    3h
    Guided learning
    0h
    Autonomous learning
    14.5h

    Delivery Practical Exercise 2: Problem solving through Automated Planning

    Delivery of the report on the Automated Planning practical assignment that students have done.
    Objectives: 3 4
    Week: 14 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Final Exam

    Final exam for the course contents.
    Objectives: 1 2 3 4
    Week: 15 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Teaching methodology

    The classroom sessions are divided into theory, problems and laboratory sessions.

    Theory sessions introduce the knowledge of the course concepts, switching between the exhibition of new material with examples and discussion with students on concepts and examples.

    Problem sessions deepen the knowledge on techniques and algorithms explained in the Theory sessions. They stimulate the participation of students to discuss possible alternatives.

    Laboratory sessions develop small practical assignments by using AI tools and languages ¿in order to practice and enhance the students' knowledge on concepts, techniques and algorithms.

    Evaluation methodology

    The student assessment will consist of a partial exam mark, a final exam mark and a laboratory mark.

    The partial exam will be done during standard class hours. Passing the partial exam does not mean that those course contents won't appear again int he final exam. People who do not pass the partial will be evaluated their theoretical knowledge only on the final exam mark.

    The laboratory mark will come from the practical assignments' reports.

    The calculation of the final mark will be as follows:

    PM = partial exam mark
    FM = final exam mark
    LM = laboratory mark

    MARK = max ((PM*0.2 + FM*0.3), FM*0.5) + LM*0.5

    Reassessment: Only those who have failed the final exam may take the reassessment. The maximum grade that can be obtained in the reassessment is 7.

    Competences' Assessment

    The assessment of the competence on teamwork (CT4) is based on work done during the laboratory assignments. The ABCD grade is calculated from a detailed rubric given to students at the beginning of the course.

    The assessment of the competence on application of knowledge (CB2) is calculated directly from the course mark, as, in fact, this competence is being evaluated effectively in all evaluation acts.

    Bibliography

    Basic

    Complementary

    Previous capacities

    Prior skills on Logics acquired in the course Mathematica Foundations (FM) and Knowledge and Automatic Reasoning (CRA):
    - Knowledge of the basic concepts: logical propositions and predicates
    - Ability to formulate a problem in logical terms.
    - Knowledge of logical inference and decision. Understanding resolution strategies.

    Prior skills on Algorithmics acquired in the courses on Algorithms and Programming (PA1 and PA2)
    - Knowledge on tree and graph structures,
    - Knowledge pn tree and graph search algorithms.
    - Basic notions in algorithmic complexity.