Logical Agents



In [ ]:

    
%classpath add jar ../out/artifacts/aima_core_jar/aima-core.jar

This notebook serves as a supporting material for the chapter Logical Agents. The notebooks illustrate the use of the code repository and demonstrate how the code can be extended to solve various related problems. We begin with overall agent design, introduce a simple new environment, the wumpus world, and illustrate the operation of knowledge-based agent. Then we have a look at the gernal principles of logic and the specifics of propositional logic and with well-developed inference technologies. At last, we combine the concept of knowledge-based agents with technology of propositional logic to build some simple agents for the wumpus world.

Knowledge-Based Agents

The central component of a knowledge-based agent is its knowledge base, or KB. A knowledge base is a set of sentences. (Here “sentence” is used as a technical term. It is related but not identical to the sentences of English and other natural languages.) Each sentence is expressed in a language called a knowledge representation language and represents some assertion about the world. Sometimes we dignify a sentence with the name axiom, when the sentence is taken as given without being derived from other sentences.

There must be a way to add new sentences to the knowledge base and a way to query what is known. The standard names for these operations are TELL and ASK, respectively.Both operations may involve inference—that is, deriving new sentences from old. Inference must obey the requirement that when one ASKs a question of the knowledge base, the answer should follow from what has been told (or TELLed) to the knowledge base previously.

The pseudocode below shows the outline of a knowledge-based agent program. Like all other agents, it takes a percept as input and returns an action. The agent maintaining knowlege base, KB, which may initially contain some *background knowledge



In [2]:

    
from notebookUtils import *
pseudocode('KB-Agent')









    Out[2]:




AIMA3e
function KB-AGENT(percept) returns an action

 persistent: KB, a knowledge base

      t, a counter, initially 0, indicating time
 TELL(KB, MAKE-PERCEPT-SENTENCE(percept, t))

 action ← ASK(KB, MAKE-ACTION-QUERY(t))

 TELL(KB, MAKE-ACTION-SENTENCE(action, t))

 t ← t + 1

 return action

Figure ?? A generic knowledge-based agent. Given a percept, the agent adds the percept to its knowledge base, asks the knowledge base for the best action, and tells the knowledge base that it has in fact taken that action.

The implementation of the above pseudocode can be viewed here. This agent is implemented as an abstract agent which can be extended to construct other agents.

Propositional Logic

We now present a simple but powerful logic called propositional logic. We cover the syntax of propositional logic and its semantics—the way in which the truth of sentences is determined. Then we look at entailment—the relation between a sentence and another sentence that follows from it—and see how this leads to a simple algorithm for logical inference. Everything takes place, of course, in the wumpus world.

1. Syntax

The syntax of propositional logic defines the allowable sentences. The atomic sentences consist of a single proposition symbol. Each such symbol stands for a proposition that can be true or false. We use symbols that start with an uppercase letter and may contain other letters or subscripts.The names are arbitrary but are often chosen to have some mnemonic value—we use W_{1, 3} to stand for the proposition that the wumpus is in [1,3]. (Remember that symbols such as W_1,3 are atomic, i.e., W, 1,and 3 are not meaningful parts of the symbol.) There are two proposition symbols with fixed meanings: True is the always-true proposition and False is the always-false proposition.

Complex sentences are constructed from simpler sentences, using parentheses and logical connectives. There are five connectives in common use:

¬ (not). A sentence such as ¬W_1,3 is called the negation of W_1,3. A literal is either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal).
∧ (and). A sentence whose main connective is ∧, such as W_{1, 3} ∧ P_{3, 1}, is called a conjunction; its parts are the conjuncts.
∨ (or). A sentence using ∨, such as (W_{1, 3} ∧ P_{3, 1})∨W_{2, 2}, is a disjunction of the disjuncts (W_{1, 3} ∧ P_{3, 1}) and W_{2, 2}.
⇒ (implies). A sentence such as (W_{1, 3} ∧ P_{3, 1}) ⇒ ¬W_{2, 2} is called an implication (or conditional). Its premise or antecedent is (W_{1, 3} ∧ P_{3, 1}), and its conclusion or consequent is ¬W_{2, 2}. Implications are also known as rules or if–then statements. The implication symbol is sometimes written in other books as ⊃ or →.
⇔ (if and only if). The sentence W_{1, 3} ⇔ ¬W_{2, 2} is a biconditional. Some other books write this as ≡.

The implementation of forming Complex Sentences is here. The Complex sentence is implemented using Sentence and requires Connective to form it properly.

2. Semantics

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

The semantics for propositional logic must specify how to compute the truth value of any sentence, given a model. This is done recursively. All sentences are constructed from AtomicSentence and the five connectives; therefore, we need to specify how to compute the truth of atomic sentences and how to compute the truth of sentences formed with each of the five connectives. Atomic sentences are easy:

True is true in every model and False is false in every model.
The truth value of every other proposition symbol must be specified directly in the model.

For complex sentences, we have five rules, which hold for any subsentences P and Q in any model m (here “iff” means “if and only if”):

¬P is true iff P is false in m.
P ∧ Q is true iff both P and Q are true in m.
P ∨ Q is true iff either P or Q is true in m.
P ⇒ Q is true unless P is true and Q is false in m.
P ⇔ Q is true iff P and Q are both true or both false in m.

Truth Table Entailment

Truth-Table Entails performs a recursive enumeration of a finite space of assignments to symbols. The algorithm is sound because it implements directly the definition of entailment, and complete because it works for any KB and α and always terminates—there are only finitely many models to examine.

Of course, “finitely many” is not always the same as “few.” If KB and α contain n symbols in all, then there are 2ⁿ models. Thus, the time complexity of the algorithm is O(2n). (The space complexity is only O(n) because the enumeration is depth-first.) Unfortunately, propositional entailment is co-NP-complete (i.e., probably no easier than NP-complete), so every known inference algorithm for propositional logic has a worst-case complexity that is exponential in the size of the input.



In [1]:

    
from notebookUtils import *
pseudocode('TT-Entails')









    Out[1]:




AIMA3e
function TT-ENTAILS?(KB, α) returns true or false

 inputs: KB, the knowledge base, a sentence in propositional logic

      α, the query, a sentence in propositional logic
 symbols ← a list of the propositional symbols in KB and α

 return TT-CHECK-ALL(KB, α, symbols, { })

function TT-CHECK-ALL(KB, α, symbols, model) returns true or false

 if EMPTY?(symbols) then

   if PL-TRUE?(KB, model) then return PL-TRUE?(α, model)

   else return true // when KB is false, always return true

 else do

   P ← FIRST(symbols)

   rest ← REST(symbols)

   return(TT-CHECK-ALL(KB, α, rest, model ∪ { P = true })

      and

      TT-CHECK-ALL(KB, α, rest, model ∪ { P = false }))

Figure ?? A truth-table enumeration algorithm for deciding propositional entailment. (TT stands for truth table.) PL-TRUE? returns true if a sentence holds within a model. The variable model represents a partial model - an assignment to some of the symbols. The keyword "and" is used here as a logical operation on its two arguments, returning true or false.



In [ ]: