Basic Algorithms for Artificial Intelligence

You are here

Home » Studies » Bachelor's degrees » Bachelor Degree in Artificial Intelligence » Curriculum » Syllabus » 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

  • Javier Vazquez Salceda ( )
  • Ramon Sangüesa Sole ( )

Others

  • Sergio Álvarez Napagao ( )

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: CG2, CG4, CT4, CB2, CE03, CE13, CE14,
  2. To know the bioinspired and evolutionary algorithms
    Related competences: CG2, CG4, CB2, CE03, CE13, CE14,
  3. To know the automated planning methods
    Related competences: CG2, CG4, CT4, CB2, CE03, CE13, CE14,
  4. To be able to analyze problems and choose the best algorithmic strategy
    Related competences: CG2, CG4, CG8, CB2, CE03, CE13, CE14,

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)
Type: assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
0h

Midterm exam


Objectives: 1 2 4
Week: 8
Type: theory exam
Theory
2h
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)
Type: assigment
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)
Type: theory exam
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h

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


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.