Deductive reasoning agents
The classic symbolic agent. Its beliefs are logical facts, its program is a set of rules, and it chooses an action by proving that it should take it.
Kind: deliberative agent (symbolic).
Week: 2 (slides 3 to 12).
Book: Wooldridge ch. 3 intro (pp. 49 to 50) and 3.1 Agents as theorem provers (pp. 50 to 55).
Techniques on this page: the two open problems, action selection by proof, negation as failure and the closed world, tracing the vacuum world, calculative rationality.
The problem it solves
We want an agent whose decisions are explainable and checkable. If the agent keeps its knowledge as logical facts and decides by logical inference, every action comes with a proof you can inspect. It can’t invent an ungrounded answer the way a generative model can: it can only be wrong if its facts or rules are wrong.
This is the first architecture of the module and the purest deliberative agent: an explicit symbolic model of the world, plus decisions made by symbolic reasoning. Everything later in weeks 2 and 3 is a response to its weaknesses (slow, no goals, hard to keep up with a changing world).
Words you’ll hear
| Word or symbol | Plain meaning |
|---|---|
| deliberative agent | keeps an explicit symbolic world model and decides by reasoning over it |
| \(\Delta\) (delta) | the agent’s database of facts: its beliefs about the current state |
| \(\rho\) (rho) | the rules: the agent’s “program” |
| \(\Delta \vdash_\rho \varphi\) | \(\varphi\) can be proved from the facts using the rules |
| \(Do(\alpha)\) | “the agent should do action \(\alpha\)” |
| Horn clause | a rule of the form “if these all hold, then that” (Prolog’s rules) |
negation as failure, \+ |
“not \(G\)” succeeds when \(G\) can’t be proved |
| closed world assumption | anything you can’t prove is taken to be false |
| transduction | turning the real world into symbols (vision, speech, sensors) |
Technique 1: the two open problems
Problem it solves: tells you why this approach is hard before you build anything.
| Problem | Question | Hard when |
|---|---|---|
| transduction | can we turn the world into an accurate symbolic description in time to use it? | vision, speech, physical robots (easier with structured web APIs) |
| representation / reasoning | can we represent complex real things symbolically and reason with them in time? | common sense, time and change, the cost of proofs |
Both say “in time”: a correct answer that arrives too late is useless.
Does “no hallucination” survive? (slide 6) Not fully. Inference is sound relative to \(\Delta\). If an LLM or a noisy sensor fills \(\Delta\) and gets a fact wrong, the agent will soundly derive a wrong action from it. The hallucination moves into transduction. What you keep is traceability: the proof shows which belief was wrong.
Technique 2: action selection by proof
Problem it solves: turns “what should I do?” into a logic query.
function action(Δ) returns an action
for each α in Ac:
if Δ ⊢ρ Do(α): return α # 1. an action I can prove I should do
for each α in Ac:
if Δ ⊬ρ ¬Do(α): return α # 2. an action I can't prove I mustn't do
return null # 3. nothing found“Act if you can prove you should, or if you can’t prove you shouldn’t. Otherwise do nothing.”
- The order of \(Ac\) matters: if several \(Do(\alpha)\) are provable, the first wins. Rule writers usually make conditions mutually exclusive so it never comes up.
- Step 2 can pick an action that is merely not forbidden, so an agent with too few rules still does something.
In the book’s notation the internal state is a database \(D\), and week 1’s functions become \(see: E \to Per\), \(next: D \times Per \to D\) and \(action: D \to Ac\), with \(action\) defined by proof (see the formal agent model).
Technique 3: negation as failure and the closed world
Problem it solves: lets rules say “if there is no dirt here” without listing every clean square.
In Prolog, step 1 is the query ?- do(A). and step 2 is ?- \+ not_do(A).. \+ G succeeds whenever G can’t be proved. That’s the closed world assumption: what isn’t in \(\Delta\) and can’t be derived is false. So if dirty(1,1) isn’t in the database, \+ dirty(1,1) succeeds.
Slide 9 typo. The Prolog rule do(forward) :- location(1,1), dirty(1,1), facing("E"). has lost its negation. The logic rule above it says \(\neg dirty(1,1)\), so it should be \+ dirty(1,1). As written, the robot would drive away from dirt.
Technique 4: tracing the vacuum world
Problem it solves: the standard exam exercise: given \(\Delta\), which action is proved, by which rule?
The slides’ rules:
- \(location(X,Y) \wedge dirty(X,Y) \to do(clean)\)
- \(location(X,Y) \wedge odd(X) \wedge facing(\text{S}) \to do(turn(left))\)
- \(location(X,Y) \wedge odd(X) \wedge facing(D) \wedge D \in \{\text{W},\text{N}\} \to do(turn(right))\)
- \(location(X,Y) \wedge odd(X) \wedge facing(\text{E}) \wedge \neg dirty(X,Y) \wedge \neg wall(front) \to do(forward)\)
with \(odd(X) \leftarrow X \bmod 2 = 1\).
Worked example: the slide 11 proof. \(\Delta = \{location(1,1),\ facing(\text{S})\}\).
- Rule 1 needs \(dirty(1,1)\). Not in \(\Delta\), not provable, so false (closed world).
- Rule 2: \(location(1,1)\) ✓, \(odd(1)\) ✓, \(facing(\text{S})\) ✓. So \(\Delta \vdash_\rho do(turn(left))\).
- Rules 3 and 4 need facing W, N or E: fail.
The first loop returns turn(left).
Worked example: two more.
\(\Delta = \{location(3,2),\ facing(\text{E}),\ dirty(3,2)\}\): rule 1 fires; rule 4 fails on \(\neg dirty\). Only \(Do(clean)\) is provable: clean.
\(\Delta = \{location(2,2),\ facing(\text{E})\}\): \(odd(2)\) fails, so rules 2 to 4 can’t fire, and there’s no dirt. Nothing is provable, so step 2 returns the first action that isn’t forbidden: simply the first action in \(Ac\). The slide’s rules are only a fragment (“…plus a lot more rules”).
The book’s vacuum world (pp. 52 to 54) is a different hand-written route: a 3 × 3 grid starting at \((0,0)\) facing north, actions forward, suck, turn (right only), and an update \(next(DB, p) = (DB \setminus old(DB)) \cup new(DB, p)\). Don’t mix its rules with the slides’.
Technique 5: calculative rationality
Problem it solves: names the main weakness, and tells you when this design is acceptable.
Proving \(Do(\alpha)\) starts at time \(t_1\) and finishes at \(t_2\). The action was right for the world at \(t_1\). If the world changed in between, it may be wrong by the time it’s done.
An agent has calculative rationality if it picks an action that was optimal when it started deciding. That’s only acceptable in an (effectively) static environment. With full first-order logic the prover may not even finish.
Verdict: elegant, clean semantics, inspectable proofs; but slow, and transduction and representing time and change are hard.
Where is the goal? (slide 12) Nowhere. \(\rho\) is a flat list of condition-action rules; “clean the room” lives only in the programmer’s head. That’s the motivation for teleo-reactive programs.
What to read in the book
| Section | Read? | Why |
|---|---|---|
| Ch. 3 intro, pp. 49 to 50 | Read | Deliberative agents and the two open problems (slide 5, nearly word for word) |
| 3.1 Agents as theorem provers, pp. 50 to 55 | Read | Figure 3.2 is slide 8; the vacuum world; calculative rationality (not named on the slides but the key criticism) |
| 3.3 Concurrent MetateM | Skip | Only named on the slides |
Page numbers are the book’s; in the scanned PDF add 21.
Practice prompt
I'm studying CS5940 Intelligent Agents (Wooldridge, An Introduction to MultiAgent Systems, 2nd ed., ch. 3 intro and 3.1). I want practice on DEDUCTIVE REASONING AGENTS:
- what makes an agent deliberative; the transduction and representation/reasoning problems
- the action-selection function (prove Do(a); else pick an action not provably forbidden; else null) and why the order of actions matters
- tracing vacuum-world rules: give me a database Delta (location, facing, dirty, wall facts) and rules like location(X,Y) & odd(X) & facing(S) -> do(turn(left)); I say which rule fires and which action is returned
- Prolog negation as failure and the closed world assumption
- calculative rationality and why deductive agents struggle in dynamic environments
- whether "no hallucination" survives when an LLM fills the database
- why a flat rule set has no explicit goal
Please:
1. Use plain, everyday language and explain any symbol in one short sentence.
2. Give me ONE question at a time, easy first, then harder.
3. Wait for my answer, then mark it and show the full reasoning (which conditions hold, which fail).
4. If I get it wrong, explain the mistake and give me a similar question.
5. Every 5 questions, summarise my strengths and what to practise.