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.
- Breadth-First Search (BFS): Explores shallowest nodes first using FIFO Queue. Complete, optimal for uniform edge costs. Time & Space complexity:
- Informed (Heuristic) Search:
- A* Search: Evaluation function
f(n) = g(n) + h(n), whereg(n)is actual cost from start to n, andh(n)is estimated heuristic cost from n to goal. - Admissibility & Consistency: An admissible heuristic never overestimates actual cost:
h(n) ≤ h*(n). Consistency (monotonicity) requiresh(n) ≤ c(n, a, n') + h(n'). A* tree-search is optimal if h is admissible; graph-search is optimal if h is consistent.
- A* Search: Evaluation function
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 toO(b^(m/2))with optimal move ordering, doubling searchable depth. - Constraint Satisfaction Problems (CSP): Variables
X, DomainsD, ConstraintsC. 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) | Yes | Yes (uniform costs) | O(b^d) | O(b^d) [Exponential] |
| Depth-First (DFS) | No (infinite spaces) | No | O(b^m) | O(b · m) [Linear] |
| Iterative Deepening (IDS) | Yes | Yes (uniform costs) | O(b^d) | O(b · d) [Linear] |
| Uniform Cost (UCS) | Yes | Yes | O(b^(1 + C*/ε)) | O(b^(1 + C*/ε)) |
| A* Search | Yes | Yes (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.