Lecture: Intelligent Autonomous Agents, Winter 13/14


Lecturer: Ralf Möller


Content

  1. Introduction
    Terminology, 4-phase model(s), agents, rational behavior, goals, utilities, PEAS, environment types
  2. Adversarial Agent Cooperation
    Agents with complete access to the state(s) of the environment, games, Minimax algorithm, alpha-beta pruning, elements of chance
  3. Uncertainty
    Motivation: agents with no direct access to the state(s) of the environment, probabilities, conditional probabilities, product rule, Bayes rule, full joint probability distribution, marginalization, summing out, answering queries, complexity, independence assumptions, naive Bayes, conditional independence assumptions
  4. Bayesian networks
    Syntax and semantics of Bayesian networks, answering queries revised (inference by enumeration), typical-case complexity, pragmatics: reasoning from effect (that can be perceived by an agent) to cause (that cannot be directly perceived).
  5. Probabilistic reasoning over time (1)
    Motivation: environmental state may change even without the agent performing actions, dynamic Bayesian networks, Markov assumption, transition model, sensor model, inference problems: filtering, prediction, smoothing, most-likely explanation
  6. Probabilistic reasoning over time (2)
    Special cases: hidden Markov models, Kalman filters, Exact inferences and approximations
  7. Decision making under uncertainty (1): Simple decisions
    Utility theory, multivariate utility functions, dominance, decision networks, value of information
  8. Decision making under uncertainty (2): Complex decisions
    Sequential decision problems, value iteration, policy iteration, MDPs
  9. Decision making under uncertainty (3): Decision-theoretic agents
    POMDPs, Reduction to multidimensional continuous MDPs, Dynamic Decision Networks
  10. Game theory (Golden Balls: Split or Share)
    Decisions with multiple agents, Nash equilibrium, Bayes-Nash equilibrium
  11. Social Choice
    Voting protocols, preferences, paradoxes, Arrow's Theorem,
  12. Mechanism Design
    Fundamentals, dominant strategy implementation, Revelation Principle, Gibbard-Satterthwaite Impossibility Theorem, Direct mechanisms, incentive compatibility, strategy-proofness, Vickrey-Groves-Clarke mechanisms, expected externality mechanisms, participation constraints, individual rationality, budget balancedness, bilateral trade, Myerson-Satterthwaite Theorem

Acknowledgments:

Numerous lecturers have made available material for teaching chapters of the AIMA book [1]. Some of this material has been integrated into this lecture. Since it is hard to trace back the original contributors of particular slides, I would like to thank all authors who provided their slides and made them available on the web. See also the site of the AIMA book for further references. Special acknowledgments for Kate Larson who made their slides on electronic market design available on the web.


Literature:

  1. Artificial Intelligence: A Modern Approach (Second Edition), Stuart Russell, Peter Norvig, Prentice Hall, 2003
    Chapters 2, 6, 13-17, 10.6
  2. Multiagent Systems -- Algorithmic, Game-Theoretic, and Logical Foundations, Yoav Shoham, Kevin Leyton-Brown, Cambridge University Press, 2009.


Old Exams:

Can be found here.
Ralf Möller