Logical Agents

Knowledge-based Agents

Definition

The central component of a knowledge-based agent is its knowledge base. Knowledge base is a set of sentences. Each sentence is expressed in a language called a knowledge representation language and represents some assertion about the world.

TELL and ASK Operations

• TELL: Adds new sentences the knowledge base
• ASK: Queries the knowledge base to see if a sentence is entailed by the base

Example

An automated taxi agent knows the Golden Gate Bridge is the only link between San Francisco and Marin County. It can deduce that crossing the bridge will achieve its goal of taking a passenger to Marin County.

The Wumpus World

The world is represented as a $4\times 4$ grid of rooms connected by passageways. The agent's goal is to find gold and climb out of the cave. However, the cave contains dangers such as a deadly wumpus and bottomless pits.

The agent can perform actions like moving, turning, grabbing, shooting (with a single arrow), and climbing.

It has sensors that provide limited information about its surroundings: stench indicates the presence of the wumpus nearby, breeze indicates a pit nearby, glitter indicates the presence of gold, bump indicates hitting a wall, and a scream indicates the wumpus has been killed.

The agent receives a reward for escaping with the gold and penalties for falling into a pit, being eaten by the wumpus, and for each action taken or the arrow used. The locations of the gold and the wumpus are randomly determined, and each non-starting square has a probability of containing a pit. The agent starts at position (1, 1).

Logic

Syntax

Rules for constructing valid sentences. e.g., "x + y = 4" is valid; "x4y+=" is not

Semantics

Defines the truth of sentences in possible worlds (models).

Entailment

$\alpha |=\beta$ if $\beta$ is true in all models where $\alpha$ is true.

Propositional Logic

See Propositional Logic and Rules of Inference

Effective Propositional Model Checking

This section discusses efficient algorithms for checking satisfiability (SAT) in propositional logic.

Complete Backtracking Algorithm (DPLL)

The Davis–Putnam–Logemann–Loveland (DPLL) algorithm is a refined depth-first backtracking search for SAT solving. It improves upon exhaustive enumeration by employing:

Early Termination

The algorithm detects whether the sentence must be true or false,

• If any clause is false, backtrack immediately.
• If all clauses are true, return the current assignment. For example, the sentence $(A\vee B)\wedge (A\vee C)$ is true is $A$ is true, regardless of the values of $B$ and $C$.

Pure Symbol Heuristic

A pure symbol is a symbol that always appears with the same "sign" in all clauses. For example, in the three clauses $(A\vee \neg B)$, $(\neg B\vee \neg C)$ and $(C\vee A)$, the symbol $A$ is pure because only the positive liter appears, $B$ is pure and $C$ is impure.

It's easy to see that if a sentence has a model, then it has a model with the pure symbols assigned so as to make their literals true, because doing so can never make a clause false.

Note that, in determining the purity of a symbol, the algorithm can ignore clauses that are already known to be true in the model constructed so far. For example, if the model contains $B=\text{false}$, then the clause $(\neg B\vee \neg C)$ is already true, and in the remaining clauses $C$ appears only as a positive literal; therefore $C$ becomes pure.

Unit Clause Heuristic (Unit Propagation)

A unit clause is a clause with just one literal. In the context of DPLL, it also means clauses in which all literals but one are already assigned false by the model. For example, if the model contains $B=\text{true}$, then $(\neg B\vee \neg C)$ simplifies to $\neg C$, which is a unit clause.

The unit clause heuristic assigns all such symbols before branching on the remainder. One important consequence of the heuristic is that any attempt to prove (by refutation) a literal that is already in the knowledge base will succeed immediately.

Notice also that assigning one unit clause can create another unit clause (e.g. $C\vee A$ to $A$ if setting $C=\text{false}$). This “cascade” of forced assignments is called unit propagation

Local Search Algorithms (WALKSAT)

For large SAT problems, combinatorial explosion makes backtracking impractical. Instead, stochastic local search can be effective.

WALKSAT Algorithm

1. Start with a random assignment.
2. Repeatedly flip a variable to minimize unsatisfied clauses:
   • With probability $p$ : randomly flip any variable in an unsatisfied clause.
   • With probability $1-p$ : flip the variable that minimizes the number of unsatisfied clauses ("min-conflicts").

Agents Based on Propositional Logic

The current state of the world

Hybrid Agent

Logical state estimation