Advanced Artificial Intelligence

Objectives:

The course presents both the theory of Artificial Intelligence, as well as its applications and more specifically modeling and solving interesting combinatorial problems using constraint satisfaction techniques and taking decisions under uncertainty. It also presents the modern view of intelligent systems, with probabilistic knowledge representations and reasoning with exact and approximate (through sampling) methods.

Skills:

Upon the successful completion of the course, students will be able to:

• model simple combinatorial problems as constraint satisfaction problems (CSP), and select the appropriate global constraints for solving such problems efficiently,
• solve scheduling problems using the most suitable representation and apply algorithms to find the optimal solution,
• implement CSP solutions in a constraint programming platform,
• model probabilistic decision problems using bayesian networks,
• compute probabilistic distributions analytically and by sampling,
• apply probabilistic reasoning in real world problems, such as target tracking and localisation.

Prerequisites:

It is recommended, that the student has the undergraduate course in Artificial Intelligence. The classes of this undergraduate course have been recorded (Spring semester of academic year 2013-14) and are available online through the Open Courses program of University of Macedonia.

The student is also expected to have a basic understanding of probabilities and statistics. Finally, the student is also expected to have good programming skills (e.g., know at least one programming language (such as Python).

Content:

• Uninformed & heuristic search algorithms: Depth first search, breadth first search, best first search, Α*.
• Constraint satisfaction problems and constraint modeling. Solving constraint satisfaction problems. Consistency algorithms and arc consistency. Consistency algorithms' degree and efficiency. Combining search and constraint propagation.
• Introduction to constraint programming platforms. Solving simple problems.   Enforcing consistency and solution search.
• Heuristics in constraint satisfaction problems. Global constraints. The alldifferent constraint. Resource allocation and the element constraint.
• Optimization and the branch and bound algorithm in satisfaction problems.
• Modeling scheduling problems. Global constraint that target scheduling. Scheduling under resource constraints.
• Acting under uncertainty. Rational decisions. A decision theory agent. Basic notations of probabilities. Probability axioms. Reasoning with complete joint probability distributions. Independence. Conditional independence.
• Probabilistic reasoning. Bayesian networks. Markov blanket. Continuous variables. Exact reasoning in Bayesian networks. Reasoning through enumeration. Approximate reasoning. Direct sampling. Rejection sampling. Likelihood weigthing. Monte Carlo Markov chain.
• Temporal probabilistic reasoning. Stationary processes. Markov hypothesis. Reasoning in temporal models: Filtering, Prediction, Smoothing. Finding the most likely explanation. Viterbi algorithm. Dynamic Bayesian networks. Particle filtering.
• Making simple decisions. Maximum expected utility. Axioms of utility theory. Utility functions. Risk aversion, risk neutral. Multicriteria utility functions. Decision networks. Value of information. Expert systems of decision theory.
• Sequential decision making problems. Markov decision processes (MDPs). Value iteration. Policy iteration. Partially observable Markov decision processes.

Textbooks:

• Stuart Russell & Peter Norvig, Artificial Intelligence, A Modern Approach (3^rd edition), Prentice Hall, 2009. ISBN: 0136042597.
• Mausam and Andrey Kolobov, Planning with Markov Decision Processes, an AI perspective. Morgan and Claypool, 2012.
• Judy Pearl, Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988.
• Stefan Edelkamp and Stefan Schroedl, Heuristic Search, theory and applications. Morgan Kaufmann, 2012.
• K.R. Apt, Principles of Constraint Programming, Cambridge University Press, 2003.
• Francesca Rossi, Peter van Beek, and Toby Walsh, (editors), Handbook of Constraint Programming, Elsevier Science, 2006
• Kim Marriott and Peter J. Stuckey, A MiniZinc Tutorial, http://www.minizinc.org/resources.html

Assessment:

Students will be expected to complete two smaller programming assignments (25% of the final mark) and one assignment that contributes 25% to the final mark. The final written examination, will contribute 50% of the final mark.

Webpage:

http://compus.uom.gr/MINF117/