Knowledge-based Agents and Propositional Logic Notes

Purpose and Overview of Knowledge Representation

Knowledge representation is a specialized field in Artificial Intelligence dedicated to representing world knowledge in a way that allows computational units to understand environments and solve problems. It serves as the foundation for systematic information processing in machines.

• Information Hierarchy: The field distinguishes between various layers of information processing:

  • Data

  • Facts

  • Information

  • Knowledge

Knowledge-Based Agents (KBA)

A knowledge-based agent is an autonomous entity that makes decisions based on its internal Knowledge Base (KB).

• The Knowledge Base (KB): A set of "sentences" (not natural language sentences, but formal representations) that encapsulate the agent's understanding of the world.

• Agent Interaction Cycle:

  1. Perceive and Tell: The agent perceives the environment and "tells" the KB what it has sensed.

  2. Ask: The agent "asks" the KB which action it should perform next.

  3. Reason: The KB performs reasoning about the world state and provides a set of possible actions.

  4. Execute and Tell: The agent selects an action, "tells" the KB which action was chosen, and then executes that action in the environment.

• Initialization: When an agent begins, the KB may be empty or initialized with background knowledge. Over time, the agent performs inference to derive new sentences from existing ones.

The Wumpus World Environment

The Wumpus World is a classic task environment used to demonstrate the capabilities of knowledge-based agents. It consists of a cave of rooms connected by passageways.

• Cave Layout: Typically represented as a $4 \times 4$ grid of rooms.

• Key Elements:

  • Wumpus: A beast that eats any agent entering its square. If the Wumpus is alive, the square is lethal.

  • Pits: Traps that end the game if an agent enters the square.

  • Gold: The primary objective (motivation) for the explorer.

  • Arrow: The agent starts with exactly one arrow to shoot the Wumpus.

PEAS Description of Wumpus World

• Performance Measure:

  • $+1000$ for exiting the cave with the gold.

  • $-1000$ for death (falling into a pit or being eaten).

  • $-1$ for every action taken (encourages efficiency).

  • $-10$ for using the single arrow.

  • The game terminates upon death or successfully climbing out of the cave.

• Environment:

  • $4 \times 4$ grid.

  • Agent starts at square $(1,1)$ facing right.

  • Gold and Wumpus locations are assigned randomly (excluding the start square).

  • Pits have a probability of $0.2$ for each square (excluding the start square).

• Actuators:

  • Movements: Forward, Turn Left (90°), Turn Right (90°).

  • Safety: Entering a square with a pit or a live Wumpus results in death; a dead Wumpus square is safe.

  • Walls: Bumping into a wall results in no movement.

  • Interactions: Grab (pick up gold), Shoot (fires arrow in a straight line), Climb (only available at square $(1,1)$).

• Sensors:

  • Stench: Perceived in squares directly adjacent to the Wumpus (non-diagonal).

  • Breeze: Perceived in squares directly adjacent to a pit.

  • Glitter: Perceived specifically in the square containing the gold.

  • Bump: Perceived when the agent walks into a boundary wall.

  • Scream: Perceived globally (anywhere in the cave) when the Wumpus is killed.

Logic Fundamentals

Logic is defined as the systematic representation of information and knowledge used for communication with machines. Similar to natural languages, logic consists of syntax and semantics.

• Syntax: Defines the rules for well-formed expressions. It identifies if a sentence is correctly structured.

  • Well-formed: $x + y = 4$

  • Malformed: $x4y+ =$

• Semantics: Defines the truth of a sentence relative to a "possible world" (also known as a Model). In standard logic, a sentence must be either true or false.

  • Example: $x + y = 4$ is true in a model where $x=2, y=2$; it is false in a model where $x=1, y=1$.

Logical Languages and Commitments

Different logic languages have varying levels of expressivity and commitments:

• Propositional Logic:

  • Ontological: Facts.

  • Epistemological: Truth or Falsity ($True/False$).\n* First-Order Logic:

  • Ontological: Facts, objects, and relations.

  • Epistemological: Truth or Falsity ($True/False$).

• Temporal Logic:

  • Ontological: Facts, objects, relations, and time.

  • Epistemological: Truth or Falsity ($True/False$).

• Probability Theory:

  • Ontological: Facts.

  • Epistemological: Degree of belief belonging to the interval $[0, 1]$.

• Fuzzy Logic:

  • Ontological: Facts with a degree of truth belonging to the interval $[0, 1]$.

  • Epistemological: Known interval value.

Propositional Logic Syntax and Sentences

• Atomic Sentences: Simple sentences consisting of a single proposition symbol representing a fact that can be true or false (e.g., $A$, $True$, $W_{1,3}$).

• Complex Sentences: Constructed from simpler sentences using parentheses and logical connectives:

  • Negation: $\neg A$

  • Conjunction: $A \wedge B$

  • Disjunction: $A \vee B$

  • Implication: $p \Rightarrow q$ ("p implies q" or "if p is true, then q is true").

  • Biconditional: $p \Leftrightarrow q$ ("p if and only if q").

Evaluation of Truth Tables

• Implication ($p \Rightarrow q$): The statement is only false if the premise ($p$) is true but the conclusion ($q$) is false.

• Biconditional ($p \Leftrightarrow q$): The statement is true only if both $p$ and $q$ share the same truth value.

Entailment

Entailment occurs when one sentence follows logically from another. It is represented by the symbol $\models$.

• Representation: $\alpha \models \beta$ (Sentence $\alpha$ entails sentence $\beta$).

• Mathematical Example: $x = 0 \models xy = 0$.

• Natural Language Example:

  • $A =$ {All horses are animals; All stallions are horses}.

  • $B =$ {All stallions are animals}.

  • Result: $A \models B$.

• Wumpus World Example:

  • $A =$ {Breeze exists in squares next to a pit; There is no breeze in the current square}.

  • $B =$ {All squares adjacent to the current square are not pits}.

  • Result: $A \models B$.

Inference

Inference is the mechanical process of deriving new entailments from the Knowledge Base (KB).

• Sound Inference: A sound algorithm derives only sentences that are actually entailed by the KB (logical correctness).

• Unsound Inference: An unsound procedure "makes things up"—it derives sentences that are not logically followed from the KB.