Artificial Intelligence: A Conceptual Learner's Series

Part 3: Logic and planning

Author: Christopher DanosAI by Claude

Search treats states as black boxes. This part opens the box: describe what a state is made of, state the rules explicitly, and let the computer reason with them.

Concept 1: Constraint satisfaction

In one line: Many puzzles and scheduling problems boil down to filling in blanks so that a set of rules is never broken, and you can solve them by ruling out bad options early.

Example: You're making a wedding seating chart. Ten tables, eighty guests. Rules: the couple's divorced parents can't share a table, the kids sit together, nobody sits alone with strangers, and each table holds eight. You place guests one at a time. The moment you seat Uncle Joe at Table 3, you cross Aunt Sue off Table 3's list. If some guest suddenly has no allowed table left, you know an earlier choice was wrong, so you back up and change it instead of finishing a doomed chart.

Formally:

A constraint satisfaction problem (CSP) has variables (guests), each with a domain of possible values (tables), and constraints that restrict which combinations are allowed.
A solution assigns every variable a value with no constraint violated.
Backtracking search assigns variables one at a time and backs up as soon as a constraint fails.
Forward checking and constraint propagation remove values from other variables' domains as soon as they become impossible, catching dead ends earlier.
Good ordering helps: assign the most constrained variable first (the guest with the fewest allowed tables).

Connections: A CSP is search (Part 2) with structure. Knowing what the rules are lets the solver prune huge parts of the space without exploring them.

Watch out:

Over-constrained problems have no solution. A good solver tells you so quickly; then you must relax a rule.
Ordering heuristics matter enormously. The same problem can take seconds or hours depending on which variable you choose first.

Concept 2: Propositional logic

In one line: Logic is a precise language for facts, true or false, and rules for working out which other facts must follow from them.

Example: A detective knows three things. If the butler did it, there'd be mud on the carpet. There is no mud on the carpet. Either the butler or the gardener did it. From these alone, she concludes the gardener did it, with certainty, no hunch required. Her reasoning would be just as valid if the statements were about anything else, because it depends only on their form.

Formally:

A proposition is a statement that is true or false ("the butler did it"), written as a symbol like B.
Connectives build bigger sentences: NOT (¬), AND (∧), OR (∨), IMPLIES (⇒), IF AND ONLY IF (⇔).
A model is one assignment of true or false to every symbol: one possible world.
A knowledge base (KB) is the set of sentences the agent believes.
The KB entails a sentence α (written KB ⊨ α) if α is true in every model where the KB is true. The detective's KB entails "the gardener did it."

Connections: This is the thinking-rationally approach from Part 1, Concept 2, made concrete.

Watch out:

"Implies" is not causation. In logic, "if A then B" is automatically true whenever A is false, which surprises most people.
Logic says what follows, not what's true. False premises lead to valid but false conclusions.

Concept 3: Inference and satisfiability

In one line: Instead of checking every possible world, a computer can derive new facts step by step with proof rules, or ask whether any world at all fits the rules.

Example: You know: if it rains, the game is canceled; if the game is canceled, practice moves indoors; it's raining. You don't need to list every combination of rain, game and practice. You chain the rules: it rains, so the game is canceled, so practice moves indoors. Each step applies the same simple pattern.

Now flip the question. A logistics manager asks: is there any way to schedule these 200 deliveries with these 12 trucks, given all the rules? That's asking whether the rules can all be true at once.

Formally:

Model checking tests entailment by enumerating models. It's exact but grows as 2^n for n symbols.
Inference rules derive new sentences. Modus ponens: from A and A ⇒ B, conclude B.
Soundness: a procedure derives only entailed sentences. Completeness: it can derive every entailed sentence.
Resolution is a single rule that is complete for propositional logic when sentences are converted to a standard form.
Satisfiability (SAT) asks whether some model makes all sentences true. Modern SAT solvers handle problems with millions of variables and power chip verification and scheduling.

Connections: SAT solving is constraint satisfaction (Concept 1) in logical clothing; the two fields share many techniques.

Watch out:

SAT is hard in the worst case (NP-complete), yet practical instances are often easy. Don't assume either extreme.
Sound but incomplete is common. Fast reasoners may miss some valid conclusions in exchange for speed.

Concept 4: First-order logic

In one line: First-order logic lets you talk about objects and their relationships, and make statements about all of them or some of them, instead of naming each fact separately.

Example: In propositional logic, saying "every parent is older than their child" for a town of 50,000 people needs a separate symbol for every pair. In first-order logic, you write one sentence: for every x and y, if x is a parent of y, then x is older than y. Tell the system that Maria is Leo's parent, and it concludes Maria is older than Leo without having been told directly.

Formally:

Objects (Maria, Leo), relations (Parent(Maria, Leo)) and functions (Mother(Leo)) describe the world.
Quantifiers: ∀ ("for all") and ∃ ("there exists").

\forall x \forall y Parent (x, y) \Rightarrow Older (x, y)

Read it as: for every x and every y, if x is a parent of y, then x is older than y.

Unification matches general rules to specific facts by finding substitutions (x = Maria, y = Leo).
Forward chaining starts from facts and applies rules to derive new ones; backward chaining starts from a question and works back to supporting facts. Logic programming languages such as Prolog use backward chaining.

Connections: First-order logic extends propositional logic (Concept 2) the way variables extend arithmetic: one rule covers countless cases.

Watch out:

Knowledge engineering is the bottleneck. Writing correct, complete rules for a messy domain is slow and error-prone, which is why expert systems became brittle (Part 1, Concept 7).
Quantifier order matters. "Everyone loves someone" and "someone is loved by everyone" are very different claims.

Concept 5: Planning

In one line: Planning means finding a sequence of actions to reach a goal, where each action is described by what must be true before it and what it changes.

Example: You want breakfast on the table: coffee and toast. Making coffee requires water in the kettle and beans ground. Grinding requires the grinder plugged in. Toast requires bread in the toaster. A planner works backward from "coffee and toast served," asking what each step needs, until everything traces back to what's already true. It also notices which steps don't depend on each other, so the toast can run while the kettle heats.

Formally:

Classical planning assumes a fully observable, deterministic world.
Each action has preconditions (what must be true to do it) and effects (facts it makes true or false). A common representation is the STRIPS-style action schema, also standardized as PDDL.
Forward (progression) planning searches from the current state; backward (regression) planning searches from the goal.
Domain-independent heuristics, such as ignoring the negative effects of actions, make planning tractable.
Partial-order planning commits only to the orderings that matter, leaving independent steps flexible.

Connections: Planning combines search (Part 2) with logical descriptions of actions (Concepts 2–4). Planning under uncertainty leads to decision-making (Part 5).

Watch out:

The real world breaks classical assumptions. Actions fail and facts change, so real systems replan as they go.
The frame problem. Saying what an action changes is easy; saying everything it doesn't change is surprisingly hard.

Retention kit

Answer from memory, then check. Review at about 1 day, 3 days, 1 week, 2 weeks and 1 month.

What are the three parts of a constraint satisfaction problem, and how does forward checking speed up the search?
What does it mean for a knowledge base to entail a sentence?
Explain soundness versus completeness. What does a SAT solver decide?
What can first-order logic express that propositional logic can't? Give an example with a quantifier.
What are an action's preconditions and effects? Why do real planners replan?

Build exercise (1–2 hours): Write a Sudoku solver. Start with plain backtracking and count the number of assignments it tries on a hard puzzle. Add forward checking and the most-constrained-variable rule, and compare the count.

Python algorithms

Four small engines for this part: map coloring with backtracking, forward checking and the most-constrained-variable rule (Concept 1); entailment by checking every model, using the detective's clues (Concepts 2–3); forward chaining with modus ponens (Concepts 3–4); and a STRIPS-style breakfast planner (Concept 5). Runs with plain Python 3.

from collections import deque
from itertools import product

# 1. Constraint satisfaction: map coloring with backtracking + forward checking
NEIGHBORS = {
    "Central": ["North", "South", "East", "West"],
    "North": ["Central", "East", "West"],
    "South": ["Central", "East", "West"],
    "East": ["Central", "North", "South"],
    "West": ["Central", "North", "South"],
}

def solve_csp(domains, neighbors, assignment=None, counter=None):
    assignment = assignment or {}
    counter = counter if counter is not None else [0]
    if len(assignment) == len(domains):
        return assignment
    # Most constrained variable: fewest remaining values
    var = min((v for v in domains if v not in assignment), key=lambda v: len(domains[v]))
    for value in domains[var]:
        counter[0] += 1
        # Forward checking: remove this value from unassigned neighbors
        pruned = {n: [x for x in domains[n] if x != value]
                  for n in neighbors[var] if n not in assignment}
        if all(pruned.values()):                       # no neighbor left empty
            result = solve_csp({**domains, var: [value], **pruned}, neighbors,
                               {**assignment, var: value}, counter)
            if result:
                return result
    return None                                        # backtrack

# 2. Propositional entailment by model checking (the detective)
def entails(kb, query, symbols):
    """KB |= query if query is true in every model where KB is true."""
    for values in product([True, False], repeat=len(symbols)):
        model = dict(zip(symbols, values))
        if kb(model) and not query(model):
            return False
    return True

# 3. Forward chaining with Horn rules (modus ponens, repeatedly)
def forward_chain(facts, rules):
    known, changed = set(facts), True
    while changed:
        changed = False
        for premises, conclusion in rules:
            if conclusion not in known and all(p in known for p in premises):
                known.add(conclusion)
                changed = True
    return known

# 4. STRIPS-style planning by breadth-first search over states
ACTIONS = {
    # name: (preconditions, add effects, delete effects)
    "plug_grinder": (set(), {"grinder_on"}, set()),
    "fill_kettle":  (set(), {"kettle_full"}, set()),
    "grind_beans":  ({"grinder_on"}, {"beans_ground"}, set()),
    "heat_water":   ({"kettle_full"}, {"hot_water"}, set()),
    "brew_coffee":  ({"beans_ground", "hot_water"}, {"coffee"}, set()),
    "load_toaster": (set(), {"bread_in"}, set()),
    "toast":        ({"bread_in"}, {"toast"}, {"bread_in"}),
}

def plan(start, goal):
    frontier, seen = deque([(frozenset(start), [])]), {frozenset(start)}
    while frontier:
        state, steps = frontier.popleft()
        if goal <= state:
            return steps
        for name, (pre, add, delete) in ACTIONS.items():
            if pre <= state:
                nxt = frozenset((state - delete) | add)
                if nxt not in seen:
                    seen.add(nxt)
                    frontier.append((nxt, steps + [name]))
    return None

if __name__ == "__main__":
    counter = [0]
    colors = {v: ["red", "green", "blue"] for v in NEIGHBORS}
    print("Coloring:", solve_csp(colors, NEIGHBORS, counter=counter), "| tries:", counter[0])

    # B: butler, G: gardener, M: mud.  KB: (B => M) and not M and (B or G)
    kb = lambda m: ((not m["B"]) or m["M"]) and not m["M"] and (m["B"] or m["G"])
    print("KB entails 'gardener did it':", entails(kb, lambda m: m["G"], ["B", "G", "M"]))

    rules = [(["rain"], "game_canceled"), (["game_canceled"], "practice_indoors")]
    print("Derived facts:", sorted(forward_chain({"rain"}, rules)))
    print("Plan:", plan(set(), {"coffee", "toast"}))

Output when run:

Coloring: {'Central': 'red', 'North': 'green', 'East': 'blue', 'South': 'green', 'West': 'blue'} | tries: 5
KB entails 'gardener did it': True
Derived facts: ['game_canceled', 'practice_indoors', 'rain']
Plan: ['plug_grinder', 'fill_kettle', 'grind_beans', 'heat_water', 'brew_coffee', 'load_toaster', 'toast']

Try it:

Give each region only two colors and watch the solver return None: the problem is over-constrained.
Ask entails whether the butler did it, and explain the answer using the clues.