What AI is and intelligent agents

Artificial intelligence is the study of how to build systems that choose good actions. That sounds modest, but behind it sit some of the oldest questions in computing. What counts as good? How can a program decide what to do in a world it can only partly see? How much should it compute before acting? This course answers those questions with algorithms: search, constraint satisfaction, logical inference, probabilistic reasoning, decision making and planning. Each lesson builds working Python code, measures how it behaves, and explains the theory that predicts that behaviour.

CMPUT-366 is the classical, algorithmic core of AI. It assumes the data structures and graph algorithms of CMPUT-204 and the probability of STAT-151. Several other courses go deeper into parts of the field. AI-320 develops probabilistic models and inference, AI-330 covers reinforcement learning and Markov decision processes in depth, and AI-470 builds agent systems around today's large models. Machine learning, where a system improves from data rather than from explicitly programmed knowledge, is the subject of CMPUT-367 and CMPUT-466. Here we build the reasoning machinery those courses rely on.

Four ways to define AI

Textbook definitions of AI fall along two axes. One axis asks whether we care about thinking or about acting. The other asks whether we measure success against human performance or against an ideal standard of rationality. The four combinations give four research programs, each with a long history.

In 1950 Alan Turing proposed what he called the imitation game: an interrogator exchanges typed messages with a hidden person and a hidden machine, and the machine passes if the interrogator cannot reliably tell which is which. The test was a clever way to replace the vague question 'can machines think?' with an operational one. It remains culturally important, but researchers rarely aim at it directly, for the same reason aeronautical engineers do not aim to build machines so exactly like pigeons that they can fool other pigeons. What matters for most applications is acting well, not acting human.

This course adopts the fourth view, acting rationally. A rational agent is one that acts to achieve the best expected outcome given what it has perceived. The view has two advantages. It is more general than 'thinking rationally', because correct logical inference is only one way to act well; sometimes a reflex, such as pulling a hand off a hot stove, is better than deliberation. And it is more amenable to science than the human-based views, because rationality is mathematically defined while human behaviour is the product of a particular evolutionary history.

Agents and environments

An agent is anything that perceives its environment through sensors and acts on it through actuators. A robot has cameras and motors; a software agent receives network packets or keystrokes and sends files or messages. The agent's percept sequence is the complete history of everything it has perceived. Mathematically, an agent's behaviour is described by an agent function that maps every possible percept sequence to an action. An agent program is a concrete implementation of that function running on some physical architecture.

The distinction between agent function and agent program matters because the obvious implementation is useless. A table-driven agent would store the correct action for every percept sequence and look it up. The program below counts how many entries such a table needs, even for a tiny world. The lesson is that the challenge of AI is to produce rational behaviour from a small program rather than a vast table, just as a few lines implementing Newton's method replace the enormous tables of square roots that engineers once carried.

# Why a lookup-table agent is hopeless: it needs one entry per possible percept sequence.
def table_entries(n_percepts, lifetime):
    return sum(n_percepts ** t for t in range(1, lifetime + 1))

print("corridor agent (8 positions x clean/dirty = 16 percepts):")
for T in (1, 5, 10, 50):
    print(f"  lifetime {T:3} steps: {table_entries(16, T):.3e} entries")
# a camera percept: 640 x 480 pixels, 24 bits each, 30 frames a second
bits_per_frame = 640 * 480 * 24
digits = bits_per_frame * 30 * 3600 * 0.30103      # log10 of 2 ** (bits in an hour of video)
print(f"one hour of video: about 10 to the power {digits:,.0f} possible percept sequences")

corridor agent (8 positions x clean/dirty = 16 percepts):
  lifetime   1 steps: 1.600e+01 entries
  lifetime   5 steps: 1.118e+06 entries
  lifetime  10 steps: 1.173e+12 entries
  lifetime  50 steps: 1.714e+60 entries
one hour of video: about 10 to the power 239,698,870,272 possible percept sequences

Rationality and the performance measure

Whether an agent is rational depends on four things: the performance measure that defines success, the agent's prior knowledge of the environment, the actions it can perform, and its percept sequence to date. A rational agent selects, for each percept sequence, an action that is expected to maximize its performance measure, given the evidence of the percepts and its built-in knowledge.

The performance measure should be designed around what we actually want in the environment, not around how we think the agent should behave. Rewarding a cleaning robot for each unit of dirt it picks up sounds sensible, but a rational agent could then maximize its score by dumping dirt and picking it up again. This is a small example of a big problem that returns in lesson 12: an agent optimizes the objective it is given, which may differ from the objective its designers had in mind. Researchers call this misspecification or reward hacking.

Rationality is not omniscience. An agent that crosses a street after looking both ways and is hit by a falling satellite part acted rationally; it could not have known. Rationality maximizes expected performance, not actual performance. It does, however, require information gathering and learning. A rational agent should look before crossing, should explore an unfamiliar environment, and should improve its behaviour when its prior knowledge turns out to be incomplete. An agent that relies only on its designer's prior knowledge, never on its own percepts, lacks autonomy.

Specifying the task environment

Before designing an agent we specify its task environment with four headings, remembered by the acronym PEAS: Performance measure, Environment, Actuators and Sensors. For an automated snowplow on a city route, the performance measure might combine kilometres of lane cleared, time, fuel, salt used, damage and safety incidents; the environment includes roads, parked cars, pedestrians, other vehicles and the weather; the actuators are steering, throttle, brake, blade and spreader; the sensors include cameras, lidar, GPS, wheel encoders and a road-temperature sensor. Writing the PEAS description first forces the designer to say what success means.

Task environments vary along several dimensions, and the right techniques depend heavily on where a task falls. The program below classifies a few tasks; the table after it defines each dimension and names the lesson where we meet algorithms designed for each hard setting.

# Describing task environments along the standard dimensions.
TASKS = {
    "8-puzzle":         dict(observable="fully",     agents="single", deterministic=True,  episodic=False, static=True,  discrete=True),
    "route planning":   dict(observable="fully",     agents="single", deterministic=True,  episodic=False, static=True,  discrete=True),
    "checkers":         dict(observable="fully",     agents="multi",  deterministic=True,  episodic=False, static=True,  discrete=True),
    "poker":            dict(observable="partially", agents="multi",  deterministic=False, episodic=False, static=True,  discrete=True),
    "snowplow driving": dict(observable="partially", agents="multi",  deterministic=False, episodic=False, static=False, discrete=False),
    "spam filtering":   dict(observable="partially", agents="single", deterministic=False, episodic=True,  static=True,  discrete=True),
}
def difficulty(p):
    """Count the 'hard' settings: each one rules out a family of simple techniques."""
    return sum([p["observable"] != "fully", p["agents"] == "multi", not p["deterministic"],
                not p["episodic"], not p["static"], not p["discrete"]])
for name, p in sorted(TASKS.items(), key=lambda kv: difficulty(kv[1])):
    flags = [k for k, ok in [("partial", p["observable"] != "fully"), ("multi-agent", p["agents"] == "multi"),
             ("stochastic", not p["deterministic"]), ("sequential", not p["episodic"]),
             ("dynamic", not p["static"]), ("continuous", not p["discrete"])] if ok]
    print(f"{name:17} hard dimensions: {difficulty(p)}  {', '.join(flags) or '-'}")

8-puzzle          hard dimensions: 1  sequential
route planning    hard dimensions: 1  sequential
checkers          hard dimensions: 2  multi-agent, sequential
spam filtering    hard dimensions: 2  partial, stochastic
poker             hard dimensions: 4  partial, multi-agent, stochastic, sequential
snowplow driving  hard dimensions: 6  partial, multi-agent, stochastic, sequential, dynamic, continuous

The hardest case, partially observable, multi-agent, stochastic, sequential, dynamic and continuous, describes driving a snowplow, or nearly any task a person does outside a game. The art of applied AI is often to find a simplification that moves a problem toward the easy end of enough dimensions to make it tractable, while keeping enough of the real problem that the solution still works.

Kinds of agent program

Agent programs come in a few basic designs, each adding capability to the last.

The experiment below compares three agents in a corridor of eight cells where dirt keeps appearing. The random agent picks actions blindly. The simple reflex agent cleans when its cell is dirty and otherwise wanders randomly. The model-based agent keeps one bit of internal state, its sweep direction, and so covers the corridor systematically. Each runs for 400 steps in 20 seeded environments, scored by the performance measure in the comment. That single bit of memory nearly doubles the reflex agent's score.

# Three agents clean a corridor of 8 cells in which dirt keeps appearing.
# Performance measure: +10 per unit of dirt removed, -1 per move, over 400 steps.
import random

class Corridor:
    def __init__(self, n=8, p_dirt=0.05, seed=1):
        self.rng = random.Random(seed); self.n, self.p = n, p_dirt
        self.dirty = [self.rng.random() < 0.5 for _ in range(n)]
        self.pos, self.score = 0, 0
    def percept(self):                       # the agent senses only its own cell
        return self.pos, self.dirty[self.pos]
    def act(self, action):
        if action == "suck" and self.dirty[self.pos]:
            self.dirty[self.pos] = False; self.score += 10
        elif action in ("left", "right"):
            self.pos = max(0, min(self.n - 1, self.pos + (1 if action == "right" else -1)))
            self.score -= 1
        for i in range(self.n):              # new dirt appears at random
            if not self.dirty[i] and self.rng.random() < self.p: self.dirty[i] = True

def random_agent(rng):
    return lambda percept: rng.choice(["left", "right", "suck"])

def reflex_agent(rng):
    def act(percept):
        pos, dirty = percept
        return "suck" if dirty else rng.choice(["left", "right"])
    return act

def model_based_agent(n=8):
    state = {"heading": "right"}             # internal state: which way the sweep is going
    def act(percept):
        pos, dirty = percept
        if dirty: return "suck"
        if pos == n - 1: state["heading"] = "left"
        if pos == 0: state["heading"] = "right"
        return state["heading"]
    return act

for name, make in [("random", lambda: random_agent(random.Random(7))),
                   ("simple reflex", lambda: reflex_agent(random.Random(7))),
                   ("model-based sweep", lambda: model_based_agent())]:
    scores = []
    for seed in range(20):
        env, agent = Corridor(seed=seed), make()
        for _ in range(400): env.act(agent(env.percept()))
        scores.append(env.score)
    print(f"{name:18} mean score {sum(scores) / len(scores):7.1f}   worst {min(scores):5}   best {max(scores):5}")

random             mean score   252.5   worst   172   best   352
simple reflex      mean score   543.2   worst   392   best   766
model-based sweep  mean score   906.2   worst   722   best  1151

Goal-based and utility-based agents are where most of this course lives. A goal-based agent with a map can find a route by search (lessons 2 and 3); one with a logical model can deduce safe moves (lesson 7); one with action schemas can build a plan (lesson 11). A utility-based agent weighs uncertain outcomes by probability and desirability (lessons 9 and 10). Learning agents are developed in CMPUT-367, CMPUT-466 and AI-330.

A short history of AI

The field has a rhythm of bold predictions, real progress, disappointment and renewal. Knowing the history helps explain why the methods in this course look the way they do, and why some ideas fell out of fashion and then returned.

Canada has played an outsized role in this story, and the University of Alberta in particular. Jonathan Schaeffer's team built Chinook, which won the world checkers championship against human players in the 1990s and in 2007 proved that perfect play from the standard opening leads to a draw, the largest game solved at the time. The same department produced the Cepheus and DeepStack poker programs, and Richard Sutton, who with Andrew Barto shaped the modern field of reinforcement learning, has worked in Edmonton for two decades. In 2025 the ACM announced that Barto and Sutton had received the 2024 Turing Award, computing's highest honour, for that work. Toronto and Montréal were centres of the deep-learning revival through Geoffrey Hinton and Yoshua Bengio, who shared the 2018 Turing Award with Yann LeCun.

A theme runs through the history: early programs reasoned well over small, clean, fully specified problems and failed when problems grew or became uncertain. The classical algorithms in this course are the answers the field found to those failures. Heuristic search tames combinatorial explosion, constraint propagation prunes impossible choices before trying them, and probabilistic reasoning and decision theory handle uncertainty. These methods remain inside modern systems: AlphaZero is Monte Carlo tree search guided by a neural network, route planners run A* variants, chip and airline schedulers run constraint solvers, and hardware verification runs SAT solvers on formulas with millions of variables.

The plan of the course

Lessons 2 to 4 treat problem solving as search: uninformed search, heuristic search and A*, and local search for optimization. Lesson 5 adds an opponent. Lesson 6 exploits the structure of constraint satisfaction problems. Lessons 7 and 8 represent knowledge in logic and reason with it. Lesson 9 replaces certainty with probability, and lesson 10 combines probability with utility to make decisions, including sequential decisions in Markov decision processes. Lesson 11 plans with action schemas, and lesson 12 assembles the pieces into one agent and discusses ethics, governance and the state of the field.

Worked examples