Intelligent Agents & Problem Formulation

The field of AI has been defined in at least four distinct ways, organized along two axes: human vs. rational and thinking vs. acting.

Thinking humanly — the cognitive modeling approach — tries to reproduce human mental processes. This is more psychology than engineering; you need to know how humans solve the problem before you can mimic it.

Acting humanly — the Turing Test view — says a machine is intelligent if its behavior is indistinguishable from a human's in conversation. This was Turing's 1950 proposal. It is historically important but scientifically inadequate: a parrot that says "I love you" is not acting rationally toward any goal.

Thinking rationally — the "laws of thought" tradition — uses formal logic to encode correct inference. If all Greeks are mortal and Socrates is Greek, a logical agent can deduce Socrates is mortal. The problem: not all knowledge can be encoded cleanly in first-order logic, and exact inference is computationally intractable.

Acting rationally — the rational agent view adopted by modern AI — says a system is intelligent if it does the right thing given what it knows. "Right" means whatever maximizes the agent's performance measure. This view does not require the agent to think like a human; it only requires it to act effectively. This is the approach we will use throughout this curriculum, because it is the cleanest, most general, and most useful for building real systems.

The key insight: rationality is about outcomes relative to information, not about mimicking human cognition. An agent that always takes the escalator when the stairs are broken is rational even if it uses a simple lookup table rather than human-like reasoning.

An agent is anything that perceives its environment through sensors and acts upon it through actuators. This is deliberately abstract: a thermostat is an agent (sensor: thermometer; actuator: furnace switch). So is a chess program, a self-driving car, and a human.

A rational agent selects actions that are expected to maximize its performance measure, given:

1. The performance measure that defines what success looks like
2. The agent's prior knowledge of the environment
3. The actions the agent can perform
4. The agent's percept sequence to date

Note carefully: rationality is about expected performance, not omniscience. An agent that takes the best action it can given what it knows is rational even if bad luck produces a poor outcome. We distinguish:

• Rational: maximizes expected performance given available information
• Omniscient: knows the actual outcome of every action (impossible in reality)
• Successful: actually achieves high performance (depends on luck)

Designing the performance measure is harder than it looks and is one of the most important engineering decisions you will make. The measure must evaluate the environment state, not the agent's internal behavior. A vacuum-cleaning agent that maximizes "dirt sucked up per hour" might dump dirt on the floor and re-vacuum it. The correct measure is something like "total clean area at the end of the day."

This design challenge is called reward hacking or specification gaming in modern RL, and it has crashed real systems. In 1994 a simulated robot trained to maximize forward speed learned to grow very tall and fall over. In 2016 a boat-racing RL agent discovered it could score points by spinning in circles collecting power-ups rather than finishing the race. The performance measure IS your specification of what you want — get it wrong and you get something you do not want, perfectly optimized.

# A minimal agent function: maps percept history to an action
def rational_agent(percept_sequence: list, knowledge_base: dict) -> str:
    """
    The most general agent: a lookup table from percept sequences to actions.
    In practice, we never build this table — it's exponentially large.
    We approximate it with a program.
    """
    # For a vacuum world with two rooms (A, B) and dirt state:
    location, is_dirty = percept_sequence[-1]  # use only latest percept
    if is_dirty:
        return "Suck"
    elif location == "A":
        return "MoveRight"
    else:
        return "MoveLeft"

# Usage:
percepts = [("A", True)]  # In room A, dirt present
action = rational_agent(percepts, {})
print(action)  # "Suck"

To design any AI agent rigorously, you must specify its PEAS:

• Performance measure — what does success look like?
• Environment — what does the agent interact with?
• Actuators — how does the agent affect the environment?
• Sensors — how does the agent perceive the environment?

The agent-environment loop is the fundamental interaction pattern: at each time step t, the agent receives a percept P_t from the environment, runs its agent function to select action A_t, and the environment transitions to a new state based on A_t (and possibly other exogenous events).

This loop is not just a software pattern — it is the correct mathematical model of any situated AI system, and it directly corresponds to the Markov Decision Process (MDP) formalism used in reinforcement learning.

Example: Autonomous Taxi

• P: Safe, fast, legal, comfortable trip; maximize tips
• E: Roads, traffic, pedestrians, customers, weather
• A: Steer, accelerate, brake, horn, display
• S: Cameras, GPS, speedometer, microphone, keyboard

Example: Medical Diagnosis System

• P: Correct diagnoses, minimize unnecessary tests, patient outcomes
• E: Patients, test results, medical history
• A: Test requests, diagnoses, referrals
• S: Patient symptoms, lab results, imaging

The loop runs indefinitely in real agents. Each percept is added to the percept history, which (in principle) determines the optimal action. In practice, agents compress history into an internal state — an estimate of the world sufficient to choose good actions.

# The agent-environment loop skeleton
class Environment:
    def get_percept(self) -> object: ...
    def apply_action(self, action) -> None: ...
    def is_done(self) -> bool: ...
    def performance(self) -> float: ...

class Agent:
    def __init__(self):
        self.percept_history = []
    
    def act(self, percept) -> object:
        self.percept_history.append(percept)
        return self.agent_function(self.percept_history)
    
    def agent_function(self, history) -> object:
        raise NotImplementedError  # subclasses implement this

def run_environment(agent: Agent, env: Environment) -> float:
    while not env.is_done():
        percept = env.get_percept()
        action  = agent.act(percept)
        env.apply_action(action)
    return env.performance()

The properties of the environment dictate which algorithms are feasible. This is not academic taxonomy — it directly determines what tools you reach for.

1. Fully observable vs. partially observable An agent has a complete view of the environment state at each step (chess: fully observable) or only a partial view (poker: partially observable — opponent cards are hidden). Partial observability requires the agent to maintain a belief state — a probability distribution over possible world states. This is vastly harder.

2. Single-agent vs. multi-agent In a single-agent environment (crossword puzzle), there is only one entity acting. In multi-agent environments (chess, traffic), other agents are present. Are they cooperative (they share your goal) or competitive (they actively oppose you)? Multi-agent settings require game theory and adversarial search.

3. Deterministic vs. stochastic In a deterministic environment, the next state is completely determined by the current state and action (Rubik's cube). In a stochastic environment, there is randomness (backgammon dice). A nondeterministic environment is one where outcomes are not determined but we do not assign probabilities — we just know the set of possible outcomes.

4. Episodic vs. sequential In an episodic task, each episode is independent — the action in this episode does not affect the next (image classification: classify this photo, then the next, independent). In a sequential task, current decisions affect future ones (chess: every move changes what future moves are possible). Sequential tasks require planning ahead.

5. Static vs. dynamic In a static environment, the world does not change while the agent is deliberating. In a dynamic environment, it does (real-time strategy games, stock trading). A semidynamic environment does not change, but the agent's performance score does (timed chess).

6. Discrete vs. continuous Are state, time, percepts, and actions discrete (finite number of distinct values) or continuous? A chess board is discrete; a robotic arm's joint angles are continuous. Continuous spaces require different mathematical machinery.

7. Known vs. unknown Does the agent know the rules of the environment — the laws governing how states transition? A card game with known rules is "known"; an unexplored planet is "unknown." Unknown environments require the agent to learn the model as it acts.

The real world is: partially observable, multi-agent, stochastic, sequential, dynamic, continuous, and partially unknown. Every simplification you make (e.g., assume fully observable and deterministic) makes your algorithm tractable but less general.

# Demonstrating deterministic vs stochastic transition
import random

def deterministic_transition(state, action):
    """Next state is fully determined."""
    transitions = {
        ("A", "right"): "B",
        ("B", "left"):  "A",
        ("B", "right"): "C",
    }
    return transitions.get((state, action), state)

def stochastic_transition(state, action, slip_prob=0.1):
    """With probability slip_prob, action has no effect."""
    if random.random() < slip_prob:
        return state   # slipped, stayed in place
    return deterministic_transition(state, action)

print(deterministic_transition("A", "right"))  # Always "B"
print(stochastic_transition("A", "right"))     # "B" 90% of the time

Not all agents are alike. Russell and Norvig identify four canonical architectures, in order of increasing sophistication:

1. Simple Reflex Agent Maps the current percept directly to an action using condition-action rules: if dirty then suck. Has no memory, no model of the world. Works only in fully observable, simple environments. The thermostat is a simple reflex agent.

2. Model-Based Reflex Agent Maintains an internal state — a representation of the parts of the world it cannot currently see. The model has two components: (a) how the world evolves independently of the agent, (b) how the agent's actions affect the world. Uses the internal state + current percept to choose actions.

3. Goal-Based Agent In addition to a world model, has explicit goals — descriptions of desirable states. The agent uses search and planning to find action sequences that reach goal states. This is the foundation of classical AI planning systems.

4. Utility-Based Agent Goals alone cannot distinguish between two paths that both reach the goal — one fast, one slow. A utility function maps states (or sequences) to real numbers, encoding a total preference ordering over outcomes. The agent maximizes expected utility. This is the most general architecture.

5. Learning Agents (a meta-architecture) Any of the above can be augmented with a learning element that improves the agent's components from experience, a performance element that selects actions, a critic that evaluates performance against the performance standard, and a problem generator that suggests exploratory actions. This is the RL framework in its general form.

The progression from 1 to 4 is not historical — it is logical. Each step removes an assumption about the environment: reflex agents assume full observability; goal-based agents assume the goals fully specify what is wanted; utility-based agents make no such assumptions.

# Simple reflex vs model-based agent

# 1. Simple Reflex Agent — no internal state
class SimpleReflexVacuum:
    def act(self, percept):
        location, is_dirty = percept
        if is_dirty:
            return "Suck"
        elif location == "A":
            return "MoveRight"
        else:
            return "MoveLeft"

# 2. Model-Based Reflex Agent — tracks internal state
class ModelBasedVacuum:
    def __init__(self):
        self.state = {"A": "unknown", "B": "unknown"}
        self.location = None

    def act(self, percept):
        location, is_dirty = percept
        self.location = location
        self.state[location] = "dirty" if is_dirty else "clean"

        if is_dirty:
            return "Suck"
        elif self.state.get("A") != "clean":
            return "MoveLeft" if location == "B" else "Suck"
        elif self.state.get("B") != "clean":
            return "MoveRight" if location == "A" else "Suck"
        else:
            return "NoOp"  # everything known to be clean

A search problem is a mathematical formulation of a decision problem. It has five components:

1. State space S: the set of all possible world configurations the agent might be in. For a 15-puzzle: all permutations of 16 tiles = 16! ≈ 20 trillion states.
2. Initial state s₀ ∈ S: the state where the agent starts.
3. Goal test: a function is_goal(s) → bool that identifies whether a state is a solution. (Can also be a set of goal states.)
4. Actions A(s): the set of legal actions in state s.
5. Transition model T(s, a) → s': the state that results from applying action a in state s.
6. Action cost c(s, a, s') → ℝ₊: the cost of taking action a in state s to reach s'. (Often added as a 6th component.)

A solution is a sequence of actions that leads from s₀ to a goal state. An optimal solution minimizes total cost.

The state space can be visualized as a directed graph: nodes are states, edges are actions (labeled with costs). Finding a solution = finding a path from s₀ to any goal node.

The art of abstraction: good problem formulation removes irrelevant detail. In a route-finding problem from Arad to Bucharest, the state is which city you're in, not the position of your car's wheels. We abstract away everything that is irrelevant to the goal. A good abstraction (a) removes irrelevant detail, (b) makes actions easier to specify, (c) preserves validity (every abstract solution maps to a valid real solution). Bad abstraction either loses important information or keeps so much detail that the state space is intractable.

Example: 8-puzzle

• States: all arrangements of 8 tiles + 1 blank in a 3×3 grid → 9!/2 = 181,440 reachable states
• Initial state: a given scrambled configuration
• Actions: slide blank Up/Down/Left/Right (where legal)
• Goal: specific target arrangement
• Cost: 1 per move (minimize number of moves)

from dataclasses import dataclass
from typing import List, Tuple, Optional

@dataclass(frozen=True)
class State:
    """Immutable state for the 8-puzzle. Board is a 9-tuple, 0 = blank."""
    board: Tuple[int, ...]

    def blank_pos(self) -> int:
        return self.board.index(0)

GOAL_STATE = State(board=(1, 2, 3, 4, 5, 6, 7, 8, 0))

def actions(s: State) -> List[str]:
    pos = s.blank_pos()
    row, col = divmod(pos, 3)
    valid = []
    if row > 0: valid.append("Up")
    if row < 2: valid.append("Down")
    if col > 0: valid.append("Left")
    if col < 2: valid.append("Right")
    return valid

def transition(s: State, action: str) -> State:
    pos = s.blank_pos()
    row, col = divmod(pos, 3)
    delta = {"Up": (-1, 0), "Down": (1, 0),
             "Left": (0, -1), "Right": (0, 1)}
    dr, dc = delta[action]
    new_pos = (row + dr) * 3 + (col + dc)
    b = list(s.board)
    b[pos], b[new_pos] = b[new_pos], b[pos]
    return State(board=tuple(b))

def is_goal(s: State) -> bool:
    return s == GOAL_STATE

# Now you have a complete, clean problem formulation.
# Any search algorithm (BFS, A*, IDA*) takes these three functions.

Understanding the size of the state space is essential before choosing an algorithm. The state space determines the worst-case time and memory complexity of any exhaustive search.

Counting state spaces:

• 8-puzzle: 9!/2 ≈ 181 thousand reachable states (trivial for BFS)
• 15-puzzle: 16!/2 ≈ 10 trillion (BFS is infeasible; need A* with good heuristic)
• Chess: ~10^44 legal positions; game tree ~10^123 nodes (Brute-force impossible)
• Go: ~10^170 legal positions (even deeper; classical algorithms completely fail; need MCTS + neural nets)

This is why AlphaGo was a breakthrough — not because Go is a new kind of problem, but because its state space is so enormous that search requires function approximation (neural networks) to guide it efficiently.

Branching factor b and depth d determine tree size: a search tree of depth d with branching factor b has O(b^d) nodes. For chess b ≈ 35, d ≈ 80, giving 35^80 ≈ 10^123. Even at 10^9 operations per second, this would take longer than the age of the universe.

The state space vs. the search tree: the state space is a graph (nodes can be revisited via different paths); the search tree is what we build as we explore, and it can be exponentially larger than the state space (due to repeated states). This distinction matters: BFS on the state space graph is O(|S|) if we track visited states; BFS on the search tree without such tracking can loop forever.

Effective branching factor: the average branching factor over all nodes actually explored, as a function of the heuristic quality. A perfect heuristic gives b* = 1 (straight-line to goal). The power of good heuristics is making b* much smaller than b.

# Rough state-space size estimates
def factorial(n): 
    return 1 if n <= 1 else n * factorial(n-1)

puzzle_8  = factorial(9) // 2
puzzle_15 = factorial(16) // 2

print(f"8-puzzle reachable states:  {puzzle_8:,}")
print(f"15-puzzle reachable states: {puzzle_15:,.0f}")

# Branching factor analysis
def search_tree_size(branching: float, depth: int) -> float:
    """Upper bound on nodes in a uniform-branching search tree."""
    return (branching**(depth + 1) - 1) / (branching - 1)

print(f"\nBFS tree, b=35 (chess), d=5:  {search_tree_size(35, 5):,.0f} nodes")
print(f"BFS tree, b=35 (chess), d=10: {search_tree_size(35, 10):,.0f} nodes")
print(f"BFS tree, b=3  (easy), d=10:  {search_tree_size(3,  10):,.0f} nodes")

Learning AI means building a library of canonical problem formulations. Each illustrates a different structure:

Toy problems (clean, well-understood, used to test algorithms):

1. Vacuum World — two rooms, each clean or dirty. 8 states, 3 actions. The simplest nontrivial state space.

2. 8-Puzzle / 15-Puzzle — slide puzzle. Used to benchmark heuristic search. The misplaced tiles and Manhattan distance heuristics are classic examples of admissible heuristics.

3. 8-Queens — place 8 non-attacking queens on a chessboard. Formulated as incremental search (add one queen per step, prune illegal placements) or complete-state search (start with all 8, use local moves). 8! initial placements but clever formulation reduces search dramatically.

4. Cryptarithmetic — SEND + MORE = MONEY. Assign digits to letters. Illustrates constraint satisfaction as search.

Real-world problems:

1. Route finding — graph nodes = cities, edges = roads with distances. This is exactly what Google Maps solves, using A* variants on graphs with ~10^9 nodes.

2. Touring problems — visit a set of cities (Traveling Salesman Problem, TSP). With n cities, there are (n-1)!/2 tours. For n = 50, this is about 3×10^62 — intractable by brute force, requiring heuristics, approximation algorithms, or integer programming.

3. VLSI layout — place components on a chip minimizing wire length and heat. State space is continuous; requires constraint-based and numerical methods.

4. Robot motion planning — navigate a robot arm from configuration A to B without collision. State space = configuration space (joint angles), continuous and high-dimensional.

The key lesson: the same algorithmic toolkit (search, constraint propagation, local search, etc.) applies across all these domains — the problem formulation is what ties them together.

# 8-Queens as an incremental search problem
# State: partial assignment of queens to columns, one per row
# We place queens row by row; state = tuple of column assignments

def is_consistent(assignment: tuple, row: int, col: int) -> bool:
    """Check if placing a queen at (row, col) conflicts with existing queens."""
    for r, c in enumerate(assignment):
        if c == col:             # same column
            return False
        if abs(r - row) == abs(c - col):  # same diagonal
            return False
    return True

def successors(assignment: tuple) -> list:
    """Generate next states by placing a queen in the next row."""
    row = len(assignment)
    result = []
    for col in range(8):
        if is_consistent(assignment, row, col):
            result.append(assignment + (col,))
    return result

def is_goal(assignment: tuple) -> bool:
    return len(assignment) == 8

# DFS to find first solution
def solve_n_queens(n=8):
    stack = [()]
    while stack:
        state = stack.pop()
        if is_goal(state):
            return state
        stack.extend(successors(state))
    return None

print(solve_n_queens())  # e.g., (0, 4, 7, 5, 2, 6, 1, 3)

An agent's ability to act rationally depends critically on what it knows about the environment. We can arrange agents on a knowledge spectrum:

Complete ignorance: the agent knows its actions but not their effects. This is the exploration problem — the agent must act to learn the environment model. Relevant to reinforcement learning and robotics operating in unknown terrain.

Partial knowledge: the agent knows some structural properties (e.g., "actions are deterministic but the map is unknown"). It can reason about what it does and does not know.

Full knowledge: the agent has a complete, correct model of the environment — the full state space, transition function, and cost function. Classical search algorithms assume this. The agent's only computational challenge is finding the optimal policy in a known MDP.

This spectrum directly maps to AI subfields:

• Classical search and planning = full knowledge, deterministic, fully observable
• MDPs and dynamic programming = full knowledge, stochastic, fully observable
• POMDPs = full knowledge, stochastic, partially observable (extremely hard)
• Reinforcement learning = unknown model, learn from interaction
• Bayesian inference = uncertain knowledge, update beliefs with observations

The closed-world assumption — the default in classical AI planning — says everything not known to be true is false. This makes inference tractable but fails in open-world settings like the web, where the absence of knowledge about a fact does not imply the fact is false.

Understanding where your problem sits on this knowledge-observability-stochasticity cube is the first step in algorithm selection. Most of deep learning's success comes from learning the transition and reward models from massive data — replacing the "full knowledge" assumption with "enough data to learn the model."

The performance measure is the objective function of the agent. Designing it correctly is an ethical and engineering problem, not just a mathematical one.

Temporal scope: does the measure evaluate final state, cumulative reward over time, or both? In chess, only the final outcome (win/loss/draw) matters. In a factory controller, every minute of downtime costs money — cumulative reward.

Discounting: future rewards are often discounted by a factor γ ∈ (0,1]. The discounted cumulative reward is:

G_t = r_t + γ·r_{t+1} + γ²·r_{t+2} + ...

Discounting models time-preference (a dollar today is worth more than a dollar tomorrow) and ensures the sum converges for infinite-horizon problems.

Multi-objective performance: real systems have multiple, competing objectives — speed vs. safety for a car, accuracy vs. fairness for a classifier. Multi-objective optimization and Pareto frontiers become relevant.

Goodhart's Law: "When a measure becomes a target, it ceases to be a good measure." This is perhaps the most important lesson in AI alignment. Any proxy measure can be exploited. Examples:

• Maximize user engagement → reward outrage, misinformation (social media)
• Maximize reported bugs found → find and re-report trivial bugs
• Maximize test coverage → write tests that trivially pass

The solution is to make the performance measure as close as possible to what you actually care about, not a proxy. In practice this is hard — the real objective (human welfare, long-term company value) is often impossible to formalize. This gap between the formal objective and the true objective is the alignment problem in AI safety.

Expected utility theory provides the formal foundation: a rational agent should act to maximize E[U(outcome)] where U is a utility function encoding preferences. Von Neumann and Morgenstern proved (1944) that any agent with consistent preferences can be represented as maximizing expected utility — this is the basis of rational choice theory and underlies modern decision theory, economics, and AI.

# Discounted cumulative reward (returns)
def compute_return(rewards: list, gamma: float = 0.99) -> list:
    """
    Compute G_t = r_t + gamma*r_{t+1} + gamma^2*r_{t+2} + ...
    Working backward for efficiency.
    """
    G = 0.0
    returns = []
    for r in reversed(rewards):
        G = r + gamma * G
        returns.append(G)
    returns.reverse()
    return returns

# Example: a robot reaches a goal after 5 steps, reward +10 at end
rewards = [0, 0, 0, 0, 10]
print("Undiscounted:", compute_return(rewards, gamma=1.0))   
# [10.0, 10.0, 10.0, 10.0, 10.0]
print("Discounted (0.9):", compute_return(rewards, gamma=0.9))
# [6.56, 7.29, 8.1, 9.0, 10.0]  — earlier steps "see" the future reward as less valuable