Introduction to Artificial Intelligence
Principles and tools used in Artificial Intelligence. Fundamentals of Knowledge Representation and Reinforcement Learning and Nature-Based computing. Methods for non-adversarial problem solving including non-exhaustive and heuristic-based strategies for searching the state space. Methods for adversarial problem solving, modeled as two-person and multi-person games.
Study notes
Independent, AI-drafted study guide · Public sources linked below · Added November 5, 2026
Original guide aligned to the public Fall 2026 outline. The outline identifies course topics; explanations and exercises are independently written.
Agents and problem formulation
An agent maps available information to actions in an environment. Rationality is relative to a performance measure, uncertainty, available actions, and computational resources; it does not imply knowing the future. Define a search problem with a state representation, initial state, actions, transition model, goal test, and costs. The representation must retain information needed to predict future possibilities. If fuel affects which routes are possible, representing only the vehicle's current city merges states that are behaviorally different.
References: Carnegie Mellon 15-281 — Search and Games instructor notes
Uninformed search and duplicate states
Breadth-first search expands shallowest states first and finds a fewest-edge solution when edges have equal cost. Uniform-cost search expands lowest path cost and handles varying nonnegative costs under appropriate termination conditions. Depth-first search uses little frontier space on trees but can follow an infinite branch or miss a cheaper solution. A graph search needs a policy for repeated states. Marking a state visited too early can discard a cheaper path; the correct policy depends on the algorithm's guarantees.
References: Carnegie Mellon 15-281 — Search and Games instructor notes
Heuristics and A-star
A heuristic estimates remaining cost. An admissible heuristic never overestimates the optimal remaining cost; consistency requires h(n) <= c(n,n') + h(n') for each edge. A-star prioritizes f(n) = g(n) + h(n). The heuristic guides exploration, while g preserves the cost already paid. With a consistent heuristic, the usual graph-search form can finalize a state's best cost when expanded. With merely admissible but inconsistent estimates, reopening improved states may be necessary for optimality.
References: Carnegie Mellon 15-281 — Search and Games instructor notes
Worked route-search comparison
Suppose S-A costs 2, S-B costs 1, A-G costs 2, and B-G costs 8. Breadth-first search sees both solutions at depth two and may choose cost 9 depending on tie order. Uniform-cost search eventually selects the cost-4 route through A. Choose h(A)=2, h(B)=3, h(G)=0, and h(S)=3: these are admissible, and the displayed edges also satisfy consistency. A-star compares accumulated plus estimated cost, so the route through A is explored before accepting the expensive goal.
References: Carnegie Mellon 15-281 — Search and Games instructor notes
Adversarial search and uncertainty
Minimax alternates maximizing and minimizing values in a deterministic zero-sum game with perfect information. A depth-limited version needs an evaluation function for nonterminal leaves. Alpha-beta pruning removes branches that cannot alter the result under the current bounds; move order affects work, not the exact minimax value when implemented correctly. Expectimax replaces an adversary's worst-case choice with a probability-weighted outcome. State the game's information and payoff assumptions before applying any of these models.
References: Carnegie Mellon 15-281 — Search and Games instructor notes
Knowledge, learning, and nature-based methods
Knowledge representation makes facts, relationships, and inference rules explicit. A representation can support reasoning while still being incomplete or inconsistent, so distinguish a proposition's truth from the system's ability to prove it. Reinforcement learning improves a policy through rewards and interaction; the reward function must capture the intended objective. Evolutionary methods search a population using variation and selection. Their success is empirical evidence about a search process, not a guarantee that the returned candidate is globally optimal.
References: Carnegie Mellon 15-281 — Search and Games instructor notes
Practice & worked answers
Original exercises for this guide.
1. Is straight-line distance always an admissible driving-time heuristic?
Show worked answer
Distance and time use different units. Distance divided by an actual upper bound on possible travel speed can lower-bound time, but an arbitrary speed may overestimate the achievable minimum. Check the model and units before claiming admissibility.
2. What goes wrong if a maze state stores position but ignores which keys have been collected?
Show worked answer
Two visits to the same cell can enable different future actions. Merging them may remove a route through a locked door. Include the relevant key inventory in the state so that transitions depend only on the represented state.
Public notes & references
Course sources establish the scope above. Reference materials support the explanations; linked lecture notes and books remain with their authors.
2026
Topics
- Principles of Machine Learning Textbook 19.1,19.2,19.4
- Bayes Theorem and Inference Textbook 12.5,12.6, 13.1-13.3
- Rule-based Systems
- Artificial Life Textbook 23.1, 4.1
- Natural Language Processing Textbook 23.1
- Artificial Neural Networks Textbook 21.1-21.6
Readings
- Artificial Intelligence: A (hardcover) Modern Approach, 4th Edition.
- Pearson (2020). ISBN-13: 9780134610993.
Prerequisites & course information
Precludes additional credit for COMP 4106 (no longer offered), SYSC 4416 . Prerequisite(s): COMP 2402 and ( COMP 2404 or SYSC 3010 or SYSC 3110 ) and COMP 2804 . Lectures three hours a week.