Materi AI-08

Dian Palupi Rini
TEKNIK INFORMATIKA UNIVERSITAS SRIWIJAYA

Outline
• Knowledge-based agents
• Wumpus world
• Logic
• Propositional logic
• Equivalence, validity, satisfiability
• Inference rules and proof method
• forward chaining
• backward chaining
• resolution
COURSE : ARTIFICIAL INTELLIGENT

Introduction
• Human make strong claims about how the intelligence
of humans is achieved—not by purely reflex
mechanisms but by processes of reasoning that
operate on internal representations of knowledge.
• Knowledge is the basic element for a human brain to
know and understand the things logically. When a
person becomes knowledgeable about something, he
is able to do that thing in a better way. In AI, the
agents which copy such an element of human beings
are known as knowledge-based agents.

Introduction
• In AI, this approach to intelligence is embodied in
knowledge-based agents.
• The previous problem-solving agents only in a very
limited, inflexible sense. For example, the transition
model for the 8-puzzle—knowledge of what the
actions do—is hidden inside the domain-specific
code of the RESULT function
• This theme will develop LOGIC as a general class of
representations to support knowledge-based agents.
Such agents can combine and recombine information
to suit myriad purposes

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.
• Each sentence is expressed in a language called
a knowledge representation language and
represents some assertion about the world.
• 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

Types of Knowledge

Types of Knowledge
• Meta Knowledge: It is the information/knowledge

about knowledge.
• Heuristic Knowledge: It is the knowledge regarding a
specific topic.
• Procedural Knowledge: It gives information about
achieving something.
• Declarative Knowledge: It is the information which
describes a particular object and its attributes.
• Structural Knowledge: It describes the knowledge
between the objects.

Knowledge-based agents
• Intelligent agents acquire knowledge about the

world to make better decisions in the real world.
• Knowledge-based agent uses some task-specific
knowledge to solve a problem efficiently.
• A knowledge-based system comprises of two
distinguishable features which are:
• A Knowledge base
• An Inference Engine

Knowledge base
• A Knowledge base represents the actual facts which
exist in the real world. It is the central component of
a knowledge-based agent. It is a set of sentences
which describes the information related to the world.
• Note: Here, a sentence is not an English language
sentence, but it is represented in a language known
as Knowledge representation language.
• Inference Engine: It is the engine of a knowledge-

based system which allows to infer new knowledge
in the system.

Actions of an agent
• When there is a need to add/update some new

information or sentences in the knowledge-based
system, we require an inference system. Also, to
know what information is already known to the
agent, we require the inference system.
• The technical words used for describing the
mechanism of the inference system
are: TELL and ASK. When the agent solves a
problem, it calls the agent program each time.

Actions of an agent
• The agent program performs three things:
1.It TELLS the knowledge base what it has perceived
from the environment.
2.It ASKS the knowledge base about the actions it
should take?
3.It TELLS the action which is chosen, and finally, the
agent executes that action.


Each time the agent program is called, it does three
things :
• First, it TELLs the knowledge base what it perceives.
• Second, it ASKs the knowledge base what action it
should perform. In the process of answering this
query, extensive reasoning may be done about the
current state of the world, about the outcomes of
possible action sequences, and so on.
• Third, the agent program TELLs the knowledge base
which action was chosen, and the agent executes
the action.

The Knowledge Representation
• The details of the

knowledge
representation
language are
abstracted under these
three functions. These
functions create an
interface between the
two main components
of an intelligent agent,
i.e., sensors and
actuators.

• The details of the representation language are
hidden inside three functions that implement the
interface between the sensors and actuators on one
side and the core representation and reasoning
system on the other.
• MAKE-PERCEPT-SENTENCE
This function returns a sentence which tells the
perceived information by the agent at a given
time.
It constructs a sentence asserting that the
agent perceived the given percept at the given
time.

• MAKE-ACTION-QUERY
This function returns a sentence which tells
what action the agent must take at the current
time.
constructs a sentence that asks what action
should be done at the current time.
• MAKE-ACTION-SENTENCE
constructs a sentence asserting that the chosen
action was executed
This function returns a sentence which tells an
action is selected as well as executed

A knowledge-based agent
• A knowledge-based agent can be built
simply by TELLing it what it needs to know.
• Starting with an empty knowledge base, the
agent designer can TELL sentences one by
one until the agent knows how to operate in
its environment.
• This is called the declarative approach to
system building. In contrast, the procedural
approach encodes desired behaviors directly
as program code.

A Simple Knowledge Based Agent

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. Some rooms contain
bottomless pits that will trap anyone who
wanders into these rooms (except for the
Wumpus, which is too big to fall in).
• The only mitigating feature of this bleak
environment is the possibility of finding a heap
of gold

Wumpus World Description
• Performance measure: for climbing out of the cave with the gold,
for falling into a pit or being eaten by the Wumpus, for each action
taken and for using up the arrow. The game ends either when the agent
dies or when the agent climbs out of the cave.
• Environment: A 4 × 4 grid of rooms. The agent always starts in the square
labeled [1,1], facing to the right. The locations of the gold and the Wumpus are
chosen randomly, with a uniform distribution, from the squares other than the
start square. In addition, each square other than the start can be a pit, with
probability 0.2.
• Squares adjacent to Wumpus are smelly
• Squares adjacent to pit are breezy
• Glitter if gold is in the same square
• Shooting kills Wumpus if you are facing it
• Shooting uses up the only arrow
• Grabbing picks up gold if in same square
• Releasing drops the gold in same square
• Actuators: Left turn, Right turn, Forward, Grab, Release, Shoot
• Sensors: Stench, Breeze, Glitter, Bump, Scream

Sensor
The agent has five sensors, each of which gives a single bit of
information :
• In the square containing the Wumpus and in the directly (not
diagonally) adjacent squares, the agent will perceive a Stench.
• In the squares directly adjacent to a pit, the agent will perceive a
Breeze.
• In the square where the gold is, the agent will perceive a Glitter.
• When an agent walks into a wall, it will perceive a Bump.
• When the Wumpus is killed, it emits a woeful Scream that can be
perceived anywhere in the cave.
The percepts will be given to the agent program in the form of a list
of five symbols; for example, if there is a stench and a breeze, but
no glitter, bump, or scream, the agent program will get [Stench,
Breeze, None, None, None].

Wumpus World Characteristic
• Fully Observable No – only local perception
• Deterministic Yes – outcome exactly
• Episodic No – sequential in an action level
• Static Yes – Wumpus dan Pits do not move
• Discrete Yes
• Single-agent? Yes – Wumpus only have
natural feature

Exploring a Wumpus world
• For an agent in the environment, the main challenge is its
initial ignorance of the configuration of the environment;
overcoming this ignorance seems to require logical reasoning.
In most instances of the Wumpus world, it is possible for the
agent to retrieve the gold safely.
• Occasionally, the agent must choose between going home
empty-handed and risking death to find the gold. About 21%
of the environments are utterly unfair, because the gold is in a
pit or surrounded by pits.
• Let us watch a knowledge-based Wumpus agent exploring the
environment shown in Figure 7.2. We use an informal
knowledge representation language consisting of writing
down symbols in a grid.
• The agent’s initial knowledge base contains the rules of the
environment, as described previously; in particular, it knows
that it is in [1,1] and that [1,1] is a safe square; we denote
that with an “A” and “OK,” respectively, in square [1,1].











What is Logic?
• Logic is the key behind any knowledge. It allows a
person to filter the necessary information from the
bulk and draw a conclusion. In artificial intelligence,
the representation of knowledge is done via logics.
• There are three main components of logic, which are
as follows:
• Syntax: It is the sequence of a specific language
which should be followed in order to form a
sentence. Syntax is the representation of
a language. Every language has its own syntax. For
example, ax2+bx+c is a well-formed syntax of a
quadratic equation.

What is Logic?
• Semantics: The sentence or the syntax which a logic
follows should be meaningful. Semantics defines the
sense of the sentence which relates to the real
world.
For example, Indian people celebrate Diwali every year. This
sentence represents the true fact about the country and its
people who are Indians. Therefore, the sentence is
syntactically as well as semantically correct.
• Logical Inference: Inference means to infer or draw

some conclusions about some fact or a problem.
Logical inference is thinking all the possible reasons
which could lead to a proper result. Inference
algorithms are used to perform logical inference.

Logic in general

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.
• Complex sentences are constructed from simpler sentences, using
parentheses and logical connectives. There are five connectives in common
use

Semantic
• 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.

Types of logic

Entailment
• The formal definition of entailment is this: α ╞ β
if and only if, in every model in which α is true, β
is also true
• Entailment means something follows from
another
KB ╞
• Knowledge base KB entails sentence α if and
only if α is true in all words where KB is true
• E.g., KB “the Giants won” and “the Reds won”
entails “Either the Giants won, or the Reds won”
• E.g., x+y = 4 entails 4 = x+y
• Entailment is a relationship between sentences
(syntax) based on semantics
Model
• KB ╞ α if and only if M(KB) (α)

• eq:
• KB = Giants won, and Reds won
• α = Giants won

Entailment in Wumpus world

models

• KB = Wumpus-world rules + observations

• α1 = "[1,2] is safe", KB ╞ α1, proved by model checking

Wumpus models
KB = Wumpus-world rules + observations

Wumpus models

• α2 = "[2,2] is safe", KB ╞ α2

Inference

Propositional logic: Syntax

Propositional Logic: Semantics
Each model specifies true/false for each proposition symbol
E.q., P1,2 P2,2 P3,1
false true false
A Simple Recursive Proses to evaluate a sentence

The Truth Table for Connectivity

Sentences for Wumpus world

Propositional Inference : Enumeration Method

Propositional Inference : Enumeration
Method
• For n symbol, time complexity is O(2n ), space complexity

is O(n)

Propositional Inference : Solution

Logical equivalence
• Two sentences are logically equivalent iff true in the
same model: α ≡ ß iff α╞ β and β╞ α

Validity and satisfiability

Proof method

Inference Rules for propositional logic

Resolution

Resolution

Conversion to CNF

Resolution Algorithm

Resolution example

Forward and backward chaining

Forward chaining

Forward chaining
• Kadang disebut:data-driven karena inference
engine menggunakan informasi yang ditentukan
oleh user untuk memindahkan ke seluruh
jaringan dari logika ‘AND’ dan ‘OR’ sampai
sebuah terminal ditentukan sebagai objek.
Bila inference engine tidak dapat menentukan
objek maka akan meminta informasi lain.
• Aturan (Rule) di mana menentukan objek,
membentuk path (lintasan) yang mengarah ke
objek. Oleh karena itu, hanya satu cara untuk
mencapai satu objek adalah memenuhi semua
aturan.

E.q., Forward chaining




Forward chaining example

Contoh Forward chaining



Backward chaining
• Merupakan kebalikan dari forward
chaining dimana mulai dengan sebuah
hipotesa (sebuah objek) dan meminta
informasi untuk meyakinkan atau
mengabaikan. Backward chaining inference
engine sering disebut: ‘Object-Driven/Goal-
Driven‘.

Contoh Backward chaining










Summary

TEKNIK INFORMATIKA UNIVERSITAS SRIWIJAYA

Materi AI-08

Uploaded by

Copyright:

Available Formats

Materi AI-08

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Materi AI-08

Uploaded by

Copyright:

Available Formats

Dian Palupi Rini

TEKNIK INFORMATIKA UNIVERSITAS SRIWIJAYA

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

• Meta Knowledge: It is the information/knowledge

COURSE : ARTIFICIAL INTELLIGENT

• Intelligent agents acquire knowledge about the

COURSE : ARTIFICIAL INTELLIGENT

• Inference Engine: It is the engine of a knowledge-

COURSE : ARTIFICIAL INTELLIGENT

• When there is a need to add/update some new

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

• The details of the

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

• Logical Inference: Inference means to infer or draw

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

• KB ╞ α if and only if M(KB) (α)

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

KB = Wumpus-world rules + observations

COURSE : ARTIFICIAL INTELLIGENT

• KB = Wumpus-world rules + observations

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

COURSE : ARTIFICIAL INTELLIGENT

A Simple Recursive Proses to evaluate a sentence

COURSE : ARTIFICIAL INTELLIGENT