Artificial Intelligence

Search, logic, planning and decisions for explicitly represented problems

About this course

Classical artificial intelligence built around rational agents — state-space and adversarial search, constraint satisfaction, propositional and first-order logic, automated planning, and decision-making under uncertainty.

What you will be able to do

  • Formulate a problem as a state space and solve it with uninformed and heuristic search, including A*
  • Apply local search, minimax game-tree search and constraint propagation to concrete problems
  • Represent knowledge in propositional and first-order logic, and derive conclusions by inference and unification
  • Build a plan for a planning problem and use planning graphs to derive heuristics
  • Model a decision under uncertainty as a decision network or Markov decision process, and choose an action

What this course covers

  • Agent–Environment Interaction Loop
  • Task Specification and PEAS
  • Rational Action and Expected Performance
  • Environment Classification
  • Agent Program Types
  • Rational Evaluation of Action Sequences
  • Local Optimization vs. Path Search
  • Candidate, Objective, and Neighborhood
  • Hill Climbing, Local Peaks, Plateaus, and Ridges
  • Random Restart Hill Climbing
  • Simulated Annealing and Acceptance Probability
  • Levels of Optimization Evidence and Method Selection
  • Probability as a language for belief
  • Bayes' rule and the base-rate discipline
  • Odds form and likelihood ratios
  • Combining multiple observations under conditional independence
  • Bayesian networks: factorization and conditional independence
  • Scope boundaries of a finite probability model
  • Classical Planning Model and Assumptions
  • Action Model: Preconditions, Add and Delete Effects
  • Action Schemas vs. Grounded Actions
  • Forward State-Space Search and Backward Regression
  • Delete Relaxation as a Planning Heuristic
  • Separating Existence, Optimality, and Guidance Certificates
  • Four Logical Layers: Syntax, Semantics, Entailment, Proof
  • Propositional Syntax and Parse Structure
  • Truth-Functional Semantics and Connective Truth Conditions
  • Models, Entailment, and Countermodels
  • Natural Deduction Proof as a Syntactic Certificate
  • Resolution Refutation in Propositional Logic
  • Comparing Three Certificates and Matching Evidence to Claims
  • First-Order Logic Syntax and Semantics
  • Free and Bound Variables, Quantifier Scope
  • Unification and Most General Unifier
  • Variable Hygiene and Standardization Apart
  • Forward Chaining by Matching
  • First-Order Resolution Refutation
  • Three Certificates and Limits of Finite Computation
  • Strategy vs. Principal Variation
  • Adversarial Game Model and Assumptions
  • Minimax Backup Procedure
  • Alpha-Beta Pruning Mechanics
  • Move Ordering and Pruning Efficiency
  • Depth Limits and Evaluation Functions
  • Planning Graph Structure and Monotone Layers
  • Persistence (No-op) Actions
  • Action Mutex: Three Sources
  • Proposition Mutex by Inconsistent Support
  • Graph Growth, Fixed Point, and Goal Reachability
  • Backward Extraction and Forward Validation
  • Planning Graph Heuristics: Max Level, Level Sum, Set Level
  • Delete-Relaxed Heuristics and Relaxed Plan Extraction
  • Expected Utility as the Bridge from Belief to Action
  • Influence Diagrams and Information Structure
  • Observation-Contingent Policy and Value of Information
  • Markov Decision Process Specification
  • Bellman Backup and Optimality Equation
  • Backward Induction and Horizon-Dependent Policy
  • Search Problem Formulation: Five Ingredients
  • State Representation and Sufficiency
  • Applicable Actions, Transition Model, and Step Costs
  • Initial State, Goal Test, and Route Comparison
  • State Graphs, Search Trees, and Duplicate Handling
  • Abstraction: Granularity and Formulation Pitfalls
  • Stored, Derived, and Assumed Provenance
  • Syntax, Interpretation, and Inference Policy
  • Category Inheritance and the Hierarchy
  • Multiple Inheritance Conflict and Ambiguity
  • Default Reasoning and Non-Monotonicity
  • Relational Structure, Argument Roles, and Open-World Reasoning
  • Frames, Slots, and Provenance Preservation
  • Event Representation and State Transition
  • Coordinated Abstractions as the Central Result
  • Search nodes, frontiers, and reached structures
  • Generic graph search algorithm
  • Breadth-first search: shallowest-depth guarantee
  • Depth-first search and depth-limited variants
  • Uniform-cost search: least-cost certificate
  • Comparative guarantees and algorithm selection
  • AI Capability Integration and Typed Handoffs
  • Formulation as Architectural Foundation
  • Uniform-Cost Route Search with Label Repair
  • Horn-Clause Forward Chaining for Permission Derivation
  • Classical Planning with Precondition–Effect Action Schemas
  • Bayesian Belief Update from a Noisy Sensor
  • Expected Utility Decision-Making and Contingent Policy
  • End-to-End Audit: Certificates, Boundaries, and Composed Guarantees
  • CSP Formulation: Variables, Domains, Constraints
  • Constraint Graph Representation
  • Arc Consistency and AC-3 Propagation
  • Forward Checking vs. Maintaining Arc Consistency (MAC)
  • Variable and Value Ordering Heuristics (MRV, Degree, LCV)
  • Backtracking Search with Sound Pruning and State Restoration
  • Solution Validation, Uniqueness, and Limits of Evidence
  • G, H, and F: Three Search Node Values
  • A* Search: Priority, Frontier Updates, and Goal Acceptance
  • Admissibility: H as a Global Lower Bound
  • Consistency (Monotonicity): The Local Edge Inequality
  • Reopening: Repairing Premature Closure Under Inconsistency
  • Inadmissibility and the Limits of Heuristic Safety

Syllabus

  1. Agents and Search

    1. L1 · Agents, Environments, and Rational Action
    2. L2 · Problem Formulation and State Spaces
    3. L3 · Uninformed Search
    4. L4 · Heuristic Search and A*

  2. Optimization, Games and Constraints

    1. L5 · Local Search and Optimization
    2. L6 · Adversarial Search and Game Trees
    3. L7 · Constraint Satisfaction Problems

  3. Logic and Knowledge Representation

    1. L8 · Propositional Logic and Inference
    2. L9 · First-Order Logic and Unification
    3. L10 · Knowledge Representation

  4. Planning

    1. L11 · Automated Planning
    2. L12 · Planning Graphs and Planning Heuristics

  5. Uncertainty, Decisions and Synthesis

    1. L13 · Reasoning Under Uncertainty
    2. L14 · Decision Networks and Markov Decision Processes
    3. L15 · One Agent, the Whole Classical AI Stack