CS8691

Artificial Intelligence

7 Files
•
Updated Jan 2026
Download Progress 0/7 files
Unit 1
Notes Not downloaded 285 KB
Unit 2
Notes Not downloaded 412 KB
Unit 3
Notes Not downloaded 578 KB
Unit 4
Notes Not downloaded 634 KB
Unit 5
Notes Not downloaded 1.2 MB
Important Questions
Study Not downloaded 52 KB
Question Paper
Exam Not downloaded 78 KB
Academic Study Guide

Artificial Intelligence & Intelligent Systems Academic Guide

Artificial Intelligence examines the computational mechanisms governing rational agency, heuristic problem-solving, automated reasoning, knowledge representation, and machine intelligence. This guide covers PEAS agent frameworks, state-space search algorithms (A*, IDA*), adversarial game tree search (Minimax, Alpha-Beta pruning), First-Order Logic inference, and probabilistic Bayesian reasoning aligned with university curricula.

Unit-by-Unit Theoretical Revision

Unit 1: Intelligent Agents & Problem Formulation

An intelligent agent perceives its environment via sensors and acts rationally upon it using actuators to maximize its expected performance measure.

  • PEAS Descriptor Framework: Performance Measure, Environment, Actuators, Sensors. (Example: Automated Taxi - Safety/Speed, Roads/Traffic, Steering/Brakes, Cameras/Sonar).
  • Environment Properties: Fully Observable vs Partially Observable, Deterministic vs Stochastic, Episodic vs Sequential, Static vs Dynamic, Discrete vs Continuous, and Single-Agent vs Multi-Agent.
  • Agent Architectures: Simple Reflex Agents (condition-action rules), Model-Based Reflex Agents (maintains internal state), Goal-Based Agents, Utility-Based Agents (quantifies preference tradeoffs), and Learning Agents.

Unit 2: Uninformed & Informed State-Space Search Strategies

  • Problem Formulation: Initial State, Actions / Transition Model, Goal Test, and Path Cost.
  • Uninformed (Blind) Search Algorithms:
    • Breadth-First Search (BFS): Explores shallowest nodes first using FIFO Queue. Complete, optimal for uniform edge costs. Time & Space complexity: O(b^d).
    • Depth-First Search (DFS): Explores deepest branches first using LIFO Stack. Incomplete in infinite spaces. Space complexity: O(b · m), Time: O(b^m).
    • Iterative Deepening Search (IDS): Combines BFS optimality and completeness with DFS linear space efficiency O(b · d).
    • Uniform Cost Search (UCS): Expands lowest cumulative path cost g(n) node using a Priority Queue. Equivalent to Dijkstra's algorithm.
  • Informed (Heuristic) Search:
    • A* Search: Evaluation function f(n) = g(n) + h(n), where g(n) is actual cost from start to n, and h(n) is estimated heuristic cost from n to goal.
    • Admissibility & Consistency: An admissible heuristic never overestimates actual cost: h(n) ≤ h*(n). Consistency (monotonicity) requires h(n) ≤ c(n, a, n') + h(n'). A* tree-search is optimal if h is admissible; graph-search is optimal if h is consistent.

Unit 3: Adversarial Search & Constraint Satisfaction Problems (CSP)

  • Adversarial Search (Games): Deterministic, turn-taking, two-player zero-sum games (MAX and MIN players).
  • Minimax Algorithm: Recursively maximizes value for MAX player and minimizes value for MIN player up to terminal states. Time complexity: O(b^m).
  • Alpha-Beta Pruning: Optimizes Minimax by maintaining two parameters: α (best MAX value found so far) and β (best MIN value found so far). Prunes subtree when α ≥ β. Reduces worst-case time to O(b^(m/2)) with optimal move ordering, doubling searchable depth.
  • Constraint Satisfaction Problems (CSP): Variables X, Domains D, Constraints C. Solved using Backtracking search enhanced with MRV (Minimum Remaining Values / Most Constrained Variable heuristic), Degree heuristic, Least Constraining Value, and AC-3 Arc Consistency algorithm.

Unit 4: Knowledge Representation & Logical Inference

  • Propositional Logic (PL): Truth functional logic using connectives (∧, ∨, ¬, →, ↔). Syntax vs Semantics, Truth Tables, Entailment (α ⊨ β), Validity, and Satisfiability.
  • First-Order Logic (FOL / Predicate Calculus): Represents objects, relations, and functions using Universal (∀) and Existential (∃) quantifiers.
  • Inference in FOL: Forward Chaining (data-driven, bottom-up inference), Backward Chaining (goal-driven, top-down derivation), and Resolution Refutation. Conversion to Conjunctive Normal Form (CNF) using Skolemization.

Unit 5: Probabilistic Reasoning & Machine Learning Basics

  • Uncertainty & Probability: Prior probability, Conditional probability P(A|B) = P(A ∧ B) / P(B), and Bayes’ Rule: P(Cause|Effect) = (P(Effect|Cause) · P(Cause)) / P(Effect).
  • Bayesian Belief Networks (BBN): Directed Acyclic Graph (DAG) representing conditional independence assertions among variables. Joint probability factored as: P(X₁, ..., X_n) = ∏ P(X_i | Parents(X_i)).
  • Machine Learning Fundamentals: Supervised Learning (Classification, Regression), Unsupervised Learning (Clustering, PCA), and Reinforcement Learning (Markov Decision Processes, Q-learning).

Search Strategies Performance Matrix

Algorithm Complete? Optimal? Time Complexity Space Complexity
Breadth-First (BFS)YesYes (uniform costs)O(b^d)O(b^d) [Exponential]
Depth-First (DFS)No (infinite spaces)NoO(b^m)O(b · m) [Linear]
Iterative Deepening (IDS)YesYes (uniform costs)O(b^d)O(b · d) [Linear]
Uniform Cost (UCS)YesYesO(b^(1 + C*/ε))O(b^(1 + C*/ε))
A* SearchYesYes (Admissible h)O(b^d) [Heuristic dependent]O(b^d) [Exponential]

High-Frequency University Exam Questions

Q1: Define Admissible and Consistent heuristics in A* search. Why is consistency necessary for graph search?

A heuristic function h(n) is admissible if it never overestimates the actual minimal cost to reach the goal from node n, i.e., 0 ≤ h(n) ≤ h*(n). A heuristic is consistent (or monotonic) if for every node n and every successor n' generated by action a, h(n) ≤ c(n, a, n') + h(n') (satisfying the triangle inequality). In graph search, reopening closed nodes when finding shorter paths requires expensive re-expansions. A consistent heuristic guarantees that the first time A* expands a node, the shortest path to that node has already been found, eliminating the need to reopen closed states.

Q2: Explain Alpha-Beta pruning in adversarial search and state the pruning conditions.

Alpha-Beta pruning eliminates game tree branches that cannot influence the final decision of the Minimax algorithm. Alpha (α) is the highest value found so far by MAX, initialized to -∞. Beta (β) is the lowest value found so far by MIN, initialized to +∞. The pruning condition occurs whenever α ≥ β: if a node at MIN's turn discovers a value less than or equal to current α, MAX will never choose this path because MAX already has a superior alternative elsewhere, so the remaining children of that node are pruned.

Q3: Explain Bayes' Theorem and its role in probabilistic reasoning in AI.

Bayes' Theorem provides the mathematical foundation for updating belief states given observed evidence: P(Hypothesis | Evidence) = [P(Evidence | Hypothesis) · P(Hypothesis)] / P(Evidence). In AI diagnostic systems (such as medical diagnosis or fault isolation), calculating the likelihood of evidence given a hypothesis is straightforward from empirical data. Bayes' rule allows systems to invert this conditional probability to infer the posterior probability of the underlying cause given sensor observations.