Faculty of Science

Objectives

To introduce the elementary notions in artificial intelligence, review the underlying logic theory needed, and teach a logic programming language (Prolog) and its use in the design of intelligent systems.

Contents

Fundamental Issues Philosophical issues. What is intelligent behaviour? Artificial intelligence: different views (definitions) of AI; AI application areas; introduction to agents and agent programs; review of some classical AI problems (e.g., 8-puzzle, missionaries and cannibals, towers of Hanoi); limitations, Knowledge representation (including the use of logic and production rules) - the notions of entailment, satisfiability, and validity; Rational versus non-rational reasoning. Nature of environments: Fully versus partially observable; Single versus multi-agent; Deterministic versus stochastic; Static versus dynamic; Discrete versus continuous. Nature of agents: Autonomous versus semi-autonomous; Reflexive, goal-based, and utility-based; The importance of perception and environmental interactions

Basic Search Strategies Problem spaces (states, goals and operators), problem solving by search. Factored representation (factoring state into variables). Uninformed search (breadth-first, depth-first, depth-first with iterative deepening). Heuristics and informed search (hill-climbing, generic best-first, A*). Space and time efficiency of search. Two-player games (Introduction to minimax search). Constraint satisfaction (backtracking and local search methods)

Basic Knowledge Representation and Reasoning Review of propositional and First Order Logic (syntax, semantics, translations to/from natural language sentences); Logical inferences: truth table approach, inference rules, Modus Ponens and Resolution, Unification, Normal Forms, Forward and Backward Chaining. Introduction to ontologies; Simple search strategies (e.g. breadth-first, depth-first, simple heuristic search); Overview of fields related to artificial intelligence; Need to use logic in programming; declarative vs. procedural semantics; intensions and extensions; Functional vs relational interpretation of statements; Horn clauses; abstract interpreter for Horn clauses; the prolog language: prolog programs as first order predicate logic, equality, the “cut”, completion and negation in prolog; recursion; arithmetic; Unification and resolution mechanisms; recursive rules in prolog, prolog data structures (e.g. lists); Review of probabilistic reasoning, Bayes theorem.

Basic Machine Learning Definition and examples of broad variety of machine learning tasks, including classification. Inductive learning. Simple statistical-based learning such as Naive Bayesian Classifier, Decision trees. Define over-fitting problem. Measuring classifier accuracy

Advanced Search Constructing search trees, dynamic search space, combinatorial explosion of search space. Stochastic search. Simulated annealing. Genetic algorithms. Monte-Carlo tree search. Implementation of A* search, Beam search. Minimax Search, Alpha-beta pruning. Expectimax search (MDP-solving) and chance nodes

Advanced Representation and Reasoning Knowledge representation issues: Description logics; Ontology engineering. Reasoning about action and change (e.g., situation and event calculus). Temporal and spatial reasoning. Rule-based Expert Systems. Model-based and Case-based reasoning. Planning: Partial and totally ordered planning

Reasoning Under Uncertainty Review of basic probability. Random variables and probability distributions: Axioms of probability; Probabilistic inference; Bayes’ Rule. Conditional Independence. Knowledge representations: Bayesian Networks [Exact inference and its complexity, Randomized sampling (Monte Carlo) methods (e.g. Gibbs sampling)]; Markov Networks; Relational probability models; Hidden Markov Models. Decision Theory: Preferences and utility functions; Maximizing expected utility

Agents Definitions of agents. Agent architectures (e.g., reactive, layered, cognitive, etc.).

Prerequisite: