Artificial Intelligence
The classical algorithms of AI, implemented and measured: rational agents and task environments, uninformed and heuristic search with A*, IDA* and weighted A*, local search and optimization, adversarial search with alpha-beta pruning and Monte Carlo tree search, constraint satisfaction with propagation and AC-3, propositional logic with resolution, DPLL and WalkSAT, first-order logic, unification and knowledge representation, Bayesian networks with exact and sampling inference, expected utility, value of information and Markov decision processes, and STRIPS/PDDL planning, ending in a capstone agent with ethics, governance and the field today.
CMPUT-366 Year 3 3 credits 12 lessons · 7 h 43 min
Offered by HSM University · Computing Science
This is the Canadian version of this course. See the American version.
What you'll learn
- Describe AI as the design of rational agents, write PEAS descriptions, classify task environments and summarize the history of the field, including its Canadian contributions.
- Formulate problems as state-space search and compare breadth-first, uniform-cost, depth-first, iterative deepening and bidirectional search by completeness, optimality and measured node expansions.
- Implement greedy best-first search, A*, IDA* and weighted A*, prove optimality from admissible and consistent heuristics, and derive and compare heuristics by dominance and effective branching factor.
- Apply hill climbing with restarts and sideways moves, simulated annealing, local beam search, genetic algorithms and gradient descent, and explain their failure modes.
- Solve two-player games with minimax, alpha–beta pruning and transposition tables, handle chance with expectimax, implement Monte Carlo tree search with UCT, and relate these to Chinook and AlphaZero.
- Formulate constraint satisfaction problems and solve them with backtracking, MRV, degree and LCV heuristics, forward checking, AC-3, min-conflicts and tree-structured methods.
- Decide propositional entailment by model checking, resolution and forward and backward chaining, and implement DPLL and WalkSAT, explaining the random 3-SAT phase transition.
- Represent knowledge in first-order logic, implement unification and chaining, and organize categories with ontologies, semantic networks and description logics.
- Build Bayesian networks, read conditional independence by d-separation, and compute posteriors by enumeration, variable elimination, rejection sampling and likelihood weighting.
- Make decisions by maximum expected utility, compute the value of information, and solve Markov decision processes by value iteration and policy iteration.
- Represent planning problems in STRIPS and PDDL and solve them with forward search guided by relaxation heuristics, planning graphs and alternative planning approaches.
- Design and evaluate an agent that combines several AI techniques, and analyze the ethical issues and current Canadian and US approaches to AI governance.
Course content
12 lessons · 7 h 43 min total · final exam
- 1 What AI is and intelligent agents 38 min · quiz
- 2 Uninformed search 38 min · quiz
- 3 Informed search and heuristics (A*) 38 min · quiz
- 4 Local search and optimization 37 min · quiz
- 5 Adversarial search and games 40 min · quiz
- 6 Constraint satisfaction problems 39 min · quiz
- 7 Logical agents: propositional logic and SAT 38 min · quiz
- 8 First-order logic and knowledge representation 39 min · quiz
- 9 Probabilistic reasoning and Bayesian networks 41 min · quiz
- 10 Making decisions: utility, value of information and MDPs 38 min · quiz
- 11 Classical planning 37 min · quiz
- 12 Capstone: an agent for an invented domain, ethics and the field today 40 min · quiz
- E Final exam 20 questions
Requirements
Recommended background. You can start any course at any time.
Description
The classical algorithms of AI, implemented and measured: rational agents and task environments, uninformed and heuristic search with A*, IDA* and weighted A*, local search and optimization, adversarial search with alpha-beta pruning and Monte Carlo tree search, constraint satisfaction with propagation and AC-3, propositional logic with resolution, DPLL and WalkSAT, first-order logic, unification and knowledge representation, Bayesian networks with exact and sampling inference, expected utility, value of information and Markov decision processes, and STRIPS/PDDL planning, ending in a capstone agent with ethics, governance and the field today.
Part of the Science stream, typically taken in year 3.