FAI - Foundations of Artificial Intelligence
Problem Solving by Search
Book sections 3.1-3.3
Uninformed Search Algorithms
Book section 3.4 Slides: https://webeep.polimi.it/pluginfile.php/257113/mod_folder/content/0/F...
Introduction
Preliminaries A search algorithm takes a search problem as input and returns a solution, or an in...
Breadth-first search
When all actions have the same cost, an appropriate strategy is breadth-first search, in which th...
Uniform-cost search
When actions have different costs, an obvious choice is to use best-first search where the evalua...
Depth-first search
Depth-first search always expands the deepest node in the frontier first. It could be implemented...
Depth-limited and iterative deepening search
Depth-limited To keep depth-first search from wandering down an infinite path, we can use depth-l...
Bidirectional search
Simultaneously searches forward from the initial state and backwards from the goal state(s), hopi...
Summary
Informed Search Algorithms
Book section 3.5 Slides: https://webeep.polimi.it/pluginfile.php/257113/mod_folder/content/0/F...
Adversarial Search
Book sections Sections 5.1-5.5 Slides: https://webeep.polimi.it/pluginfile.php/257113/mod_fold...
Introduction
In this chapter we cover competitive environments, in which two or more agents have conflicting g...
Minimax search
MAX wants to find a sequence of actions leading to a win, but MIN has something to say about it. ...
alpha-beta pruning
Reduces the complexity of the minimax search by not considering branches of the game tree that ca...
Monte Carlo Tree Search
The basic MCTS strategy does not use a heuristic evaluation function. Instead, the value of a sta...
Stochastic games
Many games include unpredictable stochastic events, like throwing of dice in backgammon We can ap...
Reinforcement learning
Introduction and Markov decision proceses
Reinforcement learning deals with sequential decision making problems where an agent: Observes t...
Value function and Q-function
The total reward is typically defined s the expected discounted cumulative reward. We can define...
Q-learning
We apply a policy to explore the environment in order to collect information and we keep a progre...
Constraint Satisfaction Problems
Book sections 6.1-6.3 Slides: https://webeep.polimi.it/pluginfile.php/257113/mod_folder/conten...
Introduction
Factored representation for each state: a set of variables, each of which has a value. A problem ...
Constraint Propagation: Inference in CSPs
A CSP algorithm has choices. It can generate successors by choosing a new variable assignment, or...
Backtracking Search for CSPs
Sometimes we can finish the constraint propagation process and still have variables with multiple...
Uncertainty
Book sections 12.1-12.5, 13.1-13.4, lecture: https://politecnicomilano.webex.com/recordingservice...
Introduction to uncertainty
Agents in the real world need to handle uncertainty, whether due to partial observability, nondet...
Bayesian Networks
Bayesian Networks are data structure that represents the dependencies among random categorical va...
Uncertainty over time
We consider the Markov assumption: The current state $X_t$ depends on only a finite fixed number ...
Example problems on uncertainty
Some example problems that could be asked in the exam: Given some knowledge about a problem, rep...
Logical Agents
Book sections 7.1, 7.3-7.6, 8.1, 8.2 Slides: https://webeep.polimi.it/pluginfile.php/257113/m...
Introduction
A logical agent is an agent that is capable of using logical sentences to represent knowledge of ...
Propositional Logic
Syntax The syntax of propositional logic defines the allowable sentences. The atomic sentences co...
First order logic
Whereas propositional logic assumes the world contains statements, first-order logic (like natura...
Model checking
Our goal now is to decide whether $KB \models \alpha$ for some sentence $\alpha$. Reasoning with ...
Theorem proving
Other than model checking entailment can be done by theorem proving—applying rules of inference d...
Planning
Book sections 11.1-11.2 Slides: https://webeep.polimi.it/pluginfile.php/257113/mod_folder/con...
Classical Planning and PDDL
Classical planning is defined as the task of finding a sequence of actions to accomplish a goal i...
Algorithms for Classical Planning
The description of a planning problem provides an obvious way to search from the initial state th...
SATPlan
Starting from a PDDL representation of the agent’s knowledge base KB (specifying the initial stat...