Computer Science › Intelligence + Theory
An agent as anything that perceives its environment through sensors and acts on it through actuators — and rationality as choosing, at every step, the action expected to best achieve the agent's goals given what it has perceived so far, not the action that is provably optimal in hindsight.
The PEAS framework (Performance, Environment, Actuators, Sensors) for specifying a task precisely, the properties that make one environment harder than another (partially observable, stochastic, sequential, dynamic, continuous, multi-agent), and the four-level hierarchy of agent designs — reflex, model-based, goal-based, utility-based — each adding machinery the previous one lacked.
Searching a game tree the same way DFS explores a graph, except two players alternate turns with opposite goals — MAX tries to maximize the final utility, MIN tries to minimize it, and minimax computes the value each rational player can guarantee against a worst-case opponent.
Minimax computes the exact same value while exploring only a fraction of the tree, by tracking the best guarantee each player already has and cutting off any branch that cannot possibly change the outcome — a pruning idea, not an approximation, that never changes the final decision.
Minimax assumes a perfectly rational adversary, but dice, cards, and imperfect opponents call for a chance node that averages over outcomes weighted by probability instead of taking a worst case — the same tree-search skeleton, one node type swapped, and pruning largely lost as a consequence.
A CSP factors a search problem into variables, each with a domain of possible values, and constraints that restrict which combinations are allowed — map coloring, Sudoku, and scheduling are all the same problem shape once written this way, exposing structure a generic state-space search would never see.
Backtracking assigns variables one at a time and undoes a choice the instant it violates a constraint; forward checking goes further, eagerly deleting now-impossible values from every unassigned neighbor's domain so a dead end is caught long before backtracking would otherwise reach it.
AC-3 propagates constraints further than forward checking by enforcing that every value remaining for one variable has at least one compatible value for each neighbor, while the minimum-remaining-values and least-constraining-value heuristics decide which variable and value to try next — the difference between a CSP solver that thrashes and one that barely searches at all.
The same propositional connectives already covered as formal logic, now put to work as a knowledge base an agent can query — TELL adds a sentence, ASK checks whether a sentence is entailed by everything told so far, and model checking answers that question by brute-force truth-table enumeration.
Model checking scales terribly, so real reasoners convert every sentence to conjunctive normal form and apply a single inference rule, resolution, repeatedly — proof by contradiction over and over until the empty clause appears, the same refutation idea that proved the Halting Problem, now automated as a search procedure.
Propositional logic can only say individual facts are true or false; first-order logic adds the objects, relations, functions, and quantifiers already covered as pure mathematics, letting a knowledge base state a single sentence — "every student who studies passes" — that stands for infinitely many propositional facts at once.
Unification finds the variable bindings that make two first-order sentences match — the exact same binding-and-backtracking machinery already traced step by step in Prolog — and forward/backward chaining reuse it to drive both propositional resolution and real logic-programming query engines.
STRIPS represents a planning problem as a set of first-order-logic states and actions with explicit preconditions and effects, turning "find a sequence of actions from start to goal" into a search problem over the space of world-states an agent's own actions can reach.
Real agents rarely have the certainty logic assumes, so this returns to the probability axioms and Bayes' theorem already covered and adds the one idea logic alone cannot express — conditional independence — the assumption that makes probabilistic reasoning about many variables tractable instead of exponential.
A Bayesian network is a directed acyclic graph where each node's conditional probability table depends only on its parents — a factored way of writing a full joint distribution that would otherwise need exponentially many numbers, exploiting exactly the conditional-independence structure most real domains actually have.
Answering a query against a Bayesian network — enumerating the joint distribution directly, or the far cheaper variable-elimination algorithm that sums out irrelevant variables one at a time, caching intermediate factors instead of recomputing the whole joint.
A hidden Markov model chains Bayesian networks across time steps under the same Markov assumption already used for PageRank's transition matrix — except now the true state is never observed directly, only a noisy sensor reading, and filtering asks the exact question a robot with an unreliable sensor actually needs answered: what state am I probably in right now?
Given beliefs as probabilities and preferences as a utility function, the principle of maximum expected utility says a rational agent should pick the action whose probability-weighted average payoff is highest — a single decision rule that subsumes both certain and uncertain choices as special cases.
An MDP extends a Markov chain with actions and rewards, and the Bellman equation expresses the value of a state recursively in terms of the values of the states reachable from it — the same optimal-substructure idea already seen in dynamic programming, applied to sequential decisions instead of a fixed input array.
Two algorithms that solve an MDP's Bellman equation by iterating instead of solving it in closed form — value iteration repeatedly updates every state's value until it converges, policy iteration alternates between evaluating a fixed policy exactly and improving it — both provably converging to the same optimal policy.
A capstone comparing every technique this discipline covered — adversarial search, CSPs, logic, Bayesian networks, MDPs — by the shape of problem each one actually fits, and an honest map of where this discipline stops: reinforcement learning and the machine-learning techniques that estimate these models from data belong to the disciplines that follow it, not this one.
Part of the Computer Science curriculum.
An agent as anything that perceives its environment through sensors and acts on it through actuators — and rationality as choosing, at every step, the action expected to best achieve the agent's goals given what it has perceived so far, not the action that is provably optimal in hindsight.
The PEAS framework (Performance, Environment, Actuators, Sensors) for specifying a task precisely, the properties that make one environment harder than another (partially observable, stochastic, sequential, dynamic, continuous, multi-agent), and the four-level hierarchy of agent designs — reflex, model-based, goal-based, utility-based — each adding machinery the previous one lacked.
Searching a game tree the same way DFS explores a graph, except two players alternate turns with opposite goals — MAX tries to maximize the final utility, MIN tries to minimize it, and minimax computes the value each rational player can guarantee against a worst-case opponent.
Minimax computes the exact same value while exploring only a fraction of the tree, by tracking the best guarantee each player already has and cutting off any branch that cannot possibly change the outcome — a pruning idea, not an approximation, that never changes the final decision.
Minimax assumes a perfectly rational adversary, but dice, cards, and imperfect opponents call for a chance node that averages over outcomes weighted by probability instead of taking a worst case — the same tree-search skeleton, one node type swapped, and pruning largely lost as a consequence.
A CSP factors a search problem into variables, each with a domain of possible values, and constraints that restrict which combinations are allowed — map coloring, Sudoku, and scheduling are all the same problem shape once written this way, exposing structure a generic state-space search would never see.
Backtracking assigns variables one at a time and undoes a choice the instant it violates a constraint; forward checking goes further, eagerly deleting now-impossible values from every unassigned neighbor's domain so a dead end is caught long before backtracking would otherwise reach it.
AC-3 propagates constraints further than forward checking by enforcing that every value remaining for one variable has at least one compatible value for each neighbor, while the minimum-remaining-values and least-constraining-value heuristics decide which variable and value to try next — the difference between a CSP solver that thrashes and one that barely searches at all.
The same propositional connectives already covered as formal logic, now put to work as a knowledge base an agent can query — TELL adds a sentence, ASK checks whether a sentence is entailed by everything told so far, and model checking answers that question by brute-force truth-table enumeration.
Model checking scales terribly, so real reasoners convert every sentence to conjunctive normal form and apply a single inference rule, resolution, repeatedly — proof by contradiction over and over until the empty clause appears, the same refutation idea that proved the Halting Problem, now automated as a search procedure.
Propositional logic can only say individual facts are true or false; first-order logic adds the objects, relations, functions, and quantifiers already covered as pure mathematics, letting a knowledge base state a single sentence — "every student who studies passes" — that stands for infinitely many propositional facts at once.
Unification finds the variable bindings that make two first-order sentences match — the exact same binding-and-backtracking machinery already traced step by step in Prolog — and forward/backward chaining reuse it to drive both propositional resolution and real logic-programming query engines.
STRIPS represents a planning problem as a set of first-order-logic states and actions with explicit preconditions and effects, turning "find a sequence of actions from start to goal" into a search problem over the space of world-states an agent's own actions can reach.
Real agents rarely have the certainty logic assumes, so this returns to the probability axioms and Bayes' theorem already covered and adds the one idea logic alone cannot express — conditional independence — the assumption that makes probabilistic reasoning about many variables tractable instead of exponential.
A Bayesian network is a directed acyclic graph where each node's conditional probability table depends only on its parents — a factored way of writing a full joint distribution that would otherwise need exponentially many numbers, exploiting exactly the conditional-independence structure most real domains actually have.
Answering a query against a Bayesian network — enumerating the joint distribution directly, or the far cheaper variable-elimination algorithm that sums out irrelevant variables one at a time, caching intermediate factors instead of recomputing the whole joint.
A hidden Markov model chains Bayesian networks across time steps under the same Markov assumption already used for PageRank's transition matrix — except now the true state is never observed directly, only a noisy sensor reading, and filtering asks the exact question a robot with an unreliable sensor actually needs answered: what state am I probably in right now?
Given beliefs as probabilities and preferences as a utility function, the principle of maximum expected utility says a rational agent should pick the action whose probability-weighted average payoff is highest — a single decision rule that subsumes both certain and uncertain choices as special cases.
An MDP extends a Markov chain with actions and rewards, and the Bellman equation expresses the value of a state recursively in terms of the values of the states reachable from it — the same optimal-substructure idea already seen in dynamic programming, applied to sequential decisions instead of a fixed input array.
Two algorithms that solve an MDP's Bellman equation by iterating instead of solving it in closed form — value iteration repeatedly updates every state's value until it converges, policy iteration alternates between evaluating a fixed policy exactly and improving it — both provably converging to the same optimal policy.
A capstone comparing every technique this discipline covered — adversarial search, CSPs, logic, Bayesian networks, MDPs — by the shape of problem each one actually fits, and an honest map of where this discipline stops: reinforcement learning and the machine-learning techniques that estimate these models from data belong to the disciplines that follow it, not this one.