A knowledge-based agent needs to know: the current state of the world, how to infer unseen properties from percepts, how the world evolves over time, what it wants to achieve, and what its own actions do in various circumstances.
The basic elements of a reasoning agent's design are: a formal language in which knowledge can be expressed and a means of carrying out reasoning in such a language. These two elements constitute a logic.
There must be a way to add new sentences to the knowledge base and a way to query what is known. We will call these standard functions TELL and ASK, respectively.
Determining what follows from a KB is the job of the inference mechanism.
The agent maintains a KB which may initially contains some background knowledge.
In the process of answering this query, logical reasoning is used to prove which action is better than all others, given what the agent knows and what its goals are.
Make-percept-sentence takes a percept and a time and returns a sentence representing the fact that the agent perceived the percept at time t.
Make-action-query takes a time and returns a sentence that is suitable for asking what action should be performed at that time.
At any point, we can describe a knowledge-based agent at three levels:
The agents task is to find the gold and return to square [1,1].
In most environments in this class, it is possible for the agent to return successfully with the gold. However, in some the agent must choose between going home empty handed or taking a chance that could lead to death or the gold. And in about 21% of the environments, there is no way the agent can get a positive score.
Acting and reasoning in the wumpus world
Why does an agent that is successful in this world need to be able to reason? The following figure shows the state of the agent's knowledge after it has received its initial percept in the world above.
The agent detects a breeze in [2,1], so there must be a pit in a neighbouring
square, either [2,2] or [3,1]. (The notation P? indicates a possible pit.)
The pit cannot be in [1,1] because the agent has already been there and
did not fall in. At this point, there is only one known square that is
OK and has not yet been visited. So the prudent agent turns back and goes
to [1,1] and then [1,2], giving us (a) below:
We want to generate sentences that are necessarily true given that the
old sentences are true. This relationship between sentences is called entailment.
Example Consider the sentence E=mc2. The syntax of the "equation language" allows two expressions to be connected by =. An expression can be a symbol or a number, a concatenation of two expressions, two expressions joined by +, and so on.
The semantics of the language says that the two expressions on each side of the = refer to the same quantity; that the concatenation of two expressions refers to the quantity that is the product of the two quantities referred to by each of the expressions; and so on.
From the semantics, we can show that a new sentence can be generated by, for example, concatenating the same expression to both sides of the equation. ET=mc2T.
Representation
Representations need to be good at the job for which they are intended, but what does this mean? We start by looking at some more familiar examples than representation languages.
Programming languages are good for describing algorithms and concrete data structures. It is easy to imagine using a 4x4 array to represent the wumpus world and world[2,2]<-pit is a natural way to place a pit in square [2,2] of a world. However, when we want to say less specific things, we run into trouble. For example, "there is a pit in [2,2] or [3,1]" or "there is a wumpus somewhere."
The reason we run into this problem is that programming languages are designed to completely describe the state of the computer and how it changes as a program executes. But we would like to be able to describe situations where complete information is not available. A language that does not allow us to do this is not sufficiently expressive.
A good knowledge representation language should be expressive and concise so that what we say today will still be understandable tomorrow. It should be unambiguous and independent of context. Also, it should be possible to design an inference procedure for it.
Semantics
In logic, the meaning of a sentence is what it states about the world. So, how do we establish the correspondence between facts and sentences? In order to say what a sentence means, an interpretation must be provided to say what fact is corresponds to. Without an interpretation, a sentence is meaningless. This idea is easiest to see in fabricated languages.
The languages that we will deal with are all compositional - the meaning of a sentence is a function of the meaning of its parts. Just as the meaning of x2 + y2 is determined from the meanings of x2 and y2, we want the meaning of "s1 and s2" to be determined from the meanings of "s1" and "s2".
A sentence is true under a particular interpretation if the state of affairs it represents is the case. Hence, truth depends both on the interpretation and the actual state of affairs in the world.
Example
"S1,2" would be true under the interpretation in which it means that there is a stench in [1,2], in the world we explored earlier, but it would be false in worlds that do not have a stench in [1,2]. Also it would be false in our example world if its interpretation were "there is a breeze in [1,2]."
Inference
We are concerned with sound inference which is called logical inference or deduction. Logical inference is a process that implements the entailment relation between sentences. We begin with the idea of necessary truth.
Validity and satisfiability
A sentence is valid or necessarily true if and only if it is true under all possible interpretations in all possible worlds.
Example "There is a stench at [1,1] implies there is a stench at [1,1]." By contrast, "There is an open area in the square in front of me or there is a wall in the square in front of me" is not valid.
A sentence is satisfiable if and only if there is some interpretation in some world that makes it true, e.g., "there is a wumpus at [1,2]". If there is no interpretation and no world in which a sentence is true, it is called unsatisfiable.
Example There is a wall in front of me if and only if there is no wall in front of me.
Inference in computers
It turns out that validity and unsatisfiability are crucial to the ability of a computer to reason logically.
Computers do not know the interpretation you are using for the sentences in the knowledge base, nor does it know anything more than what appears on the knowledge base (it has no direct experience with the world).
Example Suppose we ask if it is OK to move to square [2,2]. The
computer does not know what OK means, nor does it know what a wumpus a
a pit is. So it cannot reason informally as we do. All it can do is see
if KB
"[2,2] is OK". The inference
procedure must show that the sentence, "If KB is true then [2,2] is OK"
is a valid sentence. If it can show this then [2,2] is OK under any interpretation
and model.
Hence, the powerful thing about formal inference is that it can be used to derive valid conclusions even if the reasoner does not know the intended interpretation.
Logics
As we have said, logics consist of the following:
In propositional logic symbols represent whole propositions (what we have been calling facts), e.g., D might have the interpretation, "the wumpus is dead". These symbols can be combined into more complicated sentences using boolean connectives.
First-order logic commits to the representation of the world in terms of objects and predicates on those objects as well as connectives (as in propositional logic) and quantifiers.
It is illuminating to consider logics in the light of their ontological and epistemological commitments. Ontological commitments have to do with the nature of reality. For example, propositional logic assumes that there are facts that either hold or do not hold in the world. First-order logic further assumes that the world consists of objects with certain relationships between them that either hold or do not hold. Special purpose logics make further commitments.
Epistemological commitments have to do with the possible states
of knowledge an agent can have using various types of logics. In propositional
and first-order logic, a sentence represents a fact and the agent either
believes the sentence to be true, believes it to be false or cannot make
a determination. Hence, these logics have three possible states of belief
about any sentence. Systems using probability theory can have any degree
of belief in a sentence, ranging from 0 (false) to 1 (true).
The symbols are True and False, propositional symbols such as P or Q,
the logical connectives, 
,
,<=>,=>,
and parentheses. All sentences are made by putting these symbols together
using the following rules:
<sentence>
|
| <=> | =>,,,=>,<=>.
Semantics
A propositional symbol can be interpreted as any fact. The propositional constants have the obvious interpretations.
For a complex sentence the meaning (as a function of the truth values of the constituent parts, is given by truth tables.
Validity and inference
Truth tables can also be used to test the validity of sentences.
Example
Models
Any world in which a sentence is true under a particular interpretation is called a model of that sentence under that interpretation.
The more we claim, the fewer models there will be of those claims, e.g., there are fewer models of "There is a pit in [1,2] and there is a Wumpus in [4,2]" than of "There is a pit in [1,2]."
Models are very important in logic because of the relationship between
models and entailment. If KB
,
then every model of KB is also a model of .
Hence, whenever KB is true so also is .
We could define the meaning of a sentence by means of set operations
on sets of models. For example, the set of models of PQ
is the intersection of the models of P and the models of Q.
The process by which the soundness of an inference rule is established through truth tables can be extended to entire classes of inferences. There are certain patterns of inferences that occur over and over, and their soundness can be shown once and for all. Then the pattern can be captured in what is called an inference rule. Once this has been done, the rule can be used to make inferences without going through the tedious process of building truth tables.
We have already seen the notation 
to say that can be derived
from by inference. An alternate
notation emphasizes that this is not a sentence, but rather an inference
rule:
Here
and
match sentences.
Whenever something in the knowledge base matches the pattern above the line, the inference rule concludes the sentence below the line.
An inference rule is sound if the conclusion is true in all cases in which the premises are true.
Some example inference rules:
Modus Ponens
And-Elimination
Or-Introduction
Double-Negation Elimination
Unit Resolution
Resolution
Complexity of Propositional Inference--------------
Since there are 2n rows in a truth table, one might suspect that the complexity of propositional inference is exponential. One might wonder if there is a polynomial-time procedure for propositional inference. This very problem was the motivation for the class of NP-complete problems.
There is a useful class of sentences for which polynomial-time inference
procedure exists. This is a class called Horn sentences. These sentences
have the form:
P2...Pn=>QLet B1,1 mean there is a breeze in [1,1].
Let W1,1 mean there is a Wumpus in [1,1].
Let P1,1 mean there is a pit in [1,1].
what we know about the wumpus world is:
S1,1
S2,1
S1,2
B1,1
B2,1
B1,2
How can we express the rules about Wumpuses and Pits?
r1: S1,1=>W1,1W1,2W2,1
r2: S2,1=>W1,1W2,1W2,2W3,1
r3: S1,2=>W1,3W1,2W2,2W1,1
Now to find the wumpus using the inference rules:
modus ponens with S1,1 and
r1 gives
W1,1W1,2W2,1
and elimination gives:
W1,1
W1,2
W2,1
modus ponens followed by and elimination with S2,1
and r2 gives:
W1,1
W2,1
W2,2
W3,1
modus ponens with S1,2 and r3 gives:
W1,3W1,2W2,2W1,1
apply unit resolution where
is W1,3W1,2W2,2
and is W1,1 gives:
W1,3W1,2W2,2
apply unit resolution where
is W1,3W1,2 and
is W2,2 gives:
W1,3W1,2
apply unit resolution where
is W1,3W1,2 and is
W1,2 gives:
W1,3
We have found the wumpus!!
