Knowledge Representation and Reasoning Intro

Knowledge Representation and Reasoning - Introduction

• Knowledge representation and reasoning allows for formalizing knowledge about the world, enabling reasoning, sound inference, proving, planning actions, and understanding/explaining things.
• The objectives are to form representations of the world, use inference to derive new representations, and use these representations to decide on actions.
• A knowledge base consists of sentences expressed in a knowledge representation language, where each sentence represents an assertion about the world.
• Inference involves deriving new sentences from existing ones to draw new conclusions.

Declarative vs Procedural Approach

• The declarative approach involves expressing knowledge of the environment in the form of sentences using a representation language.
• The procedural approach encodes desired behaviors directly as program code.

Exploring the Wumpus World

• The Wumpus world is used as an example of knowledge representation and reasoning

Wumpus World - Environment and Rules

• Squares adjacent to the wumpus are smelly, and those adjacent to pits are breezy.
• Glitter indicates gold in the same square, and shooting kills the wumpus if facing it, using up the only arrow.
• Grabbing picks up gold in the same square, while releasing drops it.
• The goal is to get the gold back to the start without entering a pit or Wumpus square.
• The agent perceives breeze, glitter, and smell, and can perform actions like turning left/right, moving forward, grabbing, releasing, and shooting.
• The Wumpus world is deterministic, but not fully accessible, static, and discrete.

Wumpus World - Exploring and Reasoning

• Exploration involves moving through the world, perceiving the environment, and making inferences about the location of Wumpuses and pits.
• If no stench or breeze is perceived, neighboring squares are considered safe.
• A stench indicates a Wumpus nearby, and a breeze indicates a pit.
• A strategy of coercion can be used, involving shooting straight ahead. If a Wumpus was there, it becomes safe. If not, the area is then deemed safe

Logical Reasoning

• If the available information is correct, the conclusion drawn is also guaranteed to be correct.

Fundamental Concepts of Logical Representation

• Logics are formal languages for representing information to draw conclusions.
• Each sentence is defined by a syntax and a semantic. Syntax defines the sentences in a language, specifying well-formed sentences.
• Semantics define the "meaning" of sentences based on a mapping to the real world, defining the truth of a sentence in a possible world.
• A model is used instead of "possible world" for precision. If the model satisfies alpha then alpha is true in model m .

Sentences and Models

• x + 2≥y is a sentence, while x + y > is not.
• x + 2≥y is true if x+2 is no less than y, as in a world where x=7, y=1, but false where x=0, and y=6.
• Models is a mathematical abstraction that fixes of true / false for every relevant sentence.
• A model is possible assignments of numbers to the variables x and y. Each assignment fixes the truth of a sentence.
• KB = wumpus-world rules + observations

Entailment

• Logical reasoning requires the relation of logical entailment between sentences ("a sentence follows logically from another sentence").
• Mathematical notation: α╞ β means α entails β.
• Formal definition: α ╞ β if and only if in every model in which α is true, β is also true. The truth of beta is contained in alpha.
• Sentences are physical configurations of the agent, and reasoning involves constructing new configurations from old ones.

Model Checking

• Model checking enumerates all possible models to check if α is true in all models in which the knowledge base is true.
• Notation indicates a is derived from KB by inference algorithm i.
• "[1,2] is safe" can be proved from KB using model checking.

Inference Procedures

• An inference procedure can generate new sentences entailed by KB or report whether a sentence is entailed by KB.
• A sound or truth-preserving inference algorithm derives only entailed sentences.
• Completeness defines that an inference algorithm can derive any sentence that is entailed.
• Soundness confirms if something is true by the system, then it is true.
• Completeness confirms if something is true, it can be proven true using the system.

Propositional Logic

• Propositional logic is the simplest logic, involving syntax, semantics, and entailment.
• Syntax defines allowable sentences. An atomic sentence has:
• Single proposition symbol (uppercase names with mnemonic value, e.g., W1,3).
• True and False symbols with fixed meanings.
• Complex sentences are constructed from simpler sentences using logical connectives.

Logical Connectives

• ¬ (NOT) negation.
• ∧ (AND) conjunction, with operands being conjuncts.
• ∨ (OR), with operands being disjuncts.
• ⇒ implication (or conditional) A ⇒ B (A is premise/antecedent, B is conclusion/consequent), also an if-then statement.
• ⇔ if and only if (biconditional).

Sentence Structures

• Logical constants TRUE and FALSE are sentences.
• Proposition symbols (P1, P2, etc.) are sentences.
• Symbols P1 and negated symbols ¬P1 are called literals.
• Sentence construction includes ¬S (NOT), S1 ∧ S2 (AND), S1 ∨ S2 (OR), S1 ⇒ S2 (Implies), and S1 ⇔ S2 (Equivalent) given S, S1, S2 as sentences.

BNF Grammar

• Sentence -> AtomicSentence | ComplexSentence
• AtomicSentence -> True | False | Symbol
• Symbol -> P | Q | R ...
• ComplexSentence -> ¬ Sentence | (Sentence ∧ Sentence) | (Sentence ∨ Sentence) | (Sentence → Sentence) | (Sentence ⇔ Sentence)

Order of Precedence (Highest to lowest)

• Parenthesis (Sentence)
• NOT
• AND
• OR
• Implies
• Equivalent
• Special cases: A ∨ B ∨ C, requires no parenthesis needed

Semantics

• Semantics defines the rules for determining the truth of a sentence with respect to a particular model
• Truth tables show the truth values for sentences with different connectives.

Sentences

• Most sentences are sometimes true, like P ∧ Q.
• Some sentences are always true, like (valid) ¬P ∨ P.
• Some sentences are never true (unsatisfiable), like ¬P ∧ P.

Propositional Inference- Model Checking

• Assume alpha = A v B
• Assume KB = (A v C) ^ (B v ¬C)
• Is it the case that KB |= a, check all possible models of alpha
• Alpha must be true whenever KB is true

Propositional Inference - Proof Methods

• Model checking involves truth table enumeration, which is sound and complete but has a time complexity of O(2^n) for n symbols. A smarter way to do inference is needed.
• Application of inference rules enables legitimate/sound generation of new sentences from old ones.
• Proof is a sequence of inference rule applications, which can be used as operators in a standard search algorithm.

Validity and Satisfiability

• A valid sentence (tautology) is true in all models and a sentence is satisfiable if it is true in some model such as A v B