Chapter 7. Logical Agents
Chapter 7. Logical Agents
The Wumpus World
The wumpus world is a cave consisting of rooms connected by passageways.
Lurking somewhere in the cave is the terrible wumpus, a beast that eats anyone who enters its room.
The wumpus can be shot by an agent, but the agent has only one arrow.
+1,000 for collecting the gold
-1,000 for falling into a hole or being eaten by the wumpus
-1 for each action taken and -10 for throwing the arrow.
A matrix of 4 x 4 rooms
The agent always starts in the box labeled by [1, 1], and oriented to the right.
The agent can move forward, turn left 90 °, or right 90 °.
The agent may die a miserable death if he enters a box where there is a hole or where the wumpus is alive
The agent has five sensors, and each one gives a small information about the environment
The agent will perceive a bad stench if it is in the same box as the wumpus
or in those directly adjacent to it (not diagonally).
2.The agent will receive a small breeze in the boxes directly adjacent where there is a hole.
The agent will see a glow in the boxes where the gold is.
If the agent tries to cross a wall he will feel a blow.
When the wumpus is annihilated, it emits a disconsolate cry that can be heard in the whole cave.
These sentences are expressed according to the syntax of the representation language, which specifies all the sentences that are well formed.
A logic must also define the semantics or meaning of sentences.
The semantics defines the truth of each sentence with respect to each possible world. When we need to be precise, we use the term model in place of “possible world.”
The final issue to consider is grounding the connection between logical reasoning processes and the real environment in which the agent exists.
Knowledge – Based Agents
The main component of a knowledge-based agent is its knowledge base or BC.
Is a set of sentences
Each sentence is expressed in a language called a knowledge representation language and represents some assertion about the world.
There must be a mechanism to add new sentences to the knowledge base, and one to ask what is known in the knowledge base.
The standard names for these two tasks are
Both tasks require inference, that is, to derive new sentences from the old ones.
The inference must comply with the essential requirement that when
is asked to the knowledge base, the answer must be followed from what has been said to the knowledge base previously.
Receive a perception as input and return an action.
The agent maintains a knowledge base, BC, which initially contains some background knowledge.
Each time the agent's program is invoked, it accomplishes two things.
First, it tells the knowledge base what it has perceived.
Second, ask the knowledge base what action to execute.
An extensive reasoning must be made about the current state of the world, the effects of possible actions,etc.
Once the action has been chosen, the agent records his choice by means of a
and execute the action
is necessary to allow the knowledge base to know that the hypothetical action has actually been executed.
Propositional Logic: A very simple logic
The syntax of propositional logic defines the allowable sentences. The atomic sentences consist of a single proposition symbol.
The semantics defines the rules for determining the truth of a sentence with respect to a particular model. In propositional logic, a model simply fixes the truth value true or false for every proposition symbol
A simple knowledge base
We need the following symbols for each [i, j] location
H(i,j) is true if there is a pit in [i, j].
B (i,j) is true if the agent perceives a breeze in [i, j].
Agents based on propositional logic
A logical agent operates by deducing what to do from a knowledge base of sentences about the world.
The knowledge base is composed of axioms:
General knowledge about how the world works
Percept sentences obtained from the agent’s experience in a particular world
It is a particular type of reflective agent with internal state.
The perceptions are the inputs of a sequential circuit (a network of doors, each one of them implements a logical connective, and of registers, each one of them stores the logical value of an atomic proposition).
The outputs of the circuit are the registers corresponding to the actions,
for example, the Grab output is assigned to true if the agent wants to grab something. If the Radiance entry connects directly to the Grab output, the agent will take the objective (the gold object) whenever it sees the glow.
Represent propositions by bits in registers, and update them using the signal propagation of the logic circuits.
Forward and backward chaining
Knowledge bases in the real world often contain only clauses, of a restricted type, called
Knowledge bases containing only definite clauses are interesting for three reasons:
Every definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is a single positive literal.
Inference with Horn clauses can be done through the forward-chaining and backwardchaining algorithms. Both of these algorithms are natural, in that the inference steps are obvious and easy for humans to follow. This type of inference is the basis for logic programming.
Deciding entailment with Horn clauses can be done in time that is linear in the size of the knowledge base a pleasant surprise.
Effective propositional inference
A complete backtracking algorithm
The algorithm incorporates three improvements to the simple scheme of ¿IMPLICACIÓN-TV?
1. Early termination:
The algorithm detects whether the sentence must be true or false,even with a partially completed model. A clause is true if any literal is true, even if the other literals do not yet have truth values
2. Pure symbol heuristic:
A pure symbol is a symbol that always appears with the same “sign” in all clauses.
3. Unit clause heuristic:
A unit clause was defined earlier as 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.
Local search algorithms
These algorithms can be applied directly to satisfiability problems, provided that we choose the right evaluation function. Because the goal is to find an assignment that satisfies every clause, an evaluation function that counts the number of unsatisfied clauses will do the job
Patterns of reasoning in propositional logic
The best-known rule is called
We just need to define a proof problem as follows:
: the initial knowledge base.
: the set of actions consists of all the inference rules applied to all the sentences that match the top half of the inference rule.
: the result of an action is to add the sentence in the bottom half of the inference rule.
: the goal is a state that contains the sentence we are trying to prove.
Comparison between Inference-based and circuit-based agents
They can be compared in several aspects
The agent based on circuits, unlike the agent based on inference, does not need to have different copies of its "knowledge" for each moment
In the worst case, the inference can take an exponential time regarding the number of symbols, while evaluating a circuit takes a linear time with respect to the size of the circuit
The circuit-based agent could be incomplete, due to the restriction that it is acyclic.
Ease of construction
In Artificial Intelligence, this approach to intelligence is embodied in knowledge-based agents.