WACHEMO UNIVERSITY

INSTITUTE OF ENGINEERING AND TECHNOLOGY

SCHOOL OF COMPUTING AND INFORMATICS
DEPARTMENT OF IT, CS and SW

INTRODUCTION TO ARTIFICIAL INTELLIGENCE COURSE MODULE

Prepared By:
1. Redwan Aman (MSc in Information Technology)
2. Tsedeke Temesgen (MSc in Computer Science)
3. Alemayehu Shemebo (MSc in Computer Science and Engineering)

Reviewed By

1. Ayana Olika (MSc in Computer Science and Engineering)

4.
2. Kibru Abera (MSc in Computer Science)

Wachamo, Hossena, Ethiopia

5.
July,2022
 The objectives of the module are:
- To provide an introduction to the basic principles and applications of Artificial Intelligence.
- To understand, define, design and analyze expert and knowledge based systems
- To study mathematical analysis of networks, on methods of training them and on their
application to practical engineering problems
Module Competences: At the end of this module students will:

- Understand reasoning, knowledge representation and learning techniques of artificial

intelligence

- Evaluate the strengths and weaknesses of these techniques and their applicability to different
tasks

- Assess the role of AI in gaining insight into intelligence and perception

- know classical examples of artificial intelligence

- know characteristics of programs that can be considered "intelligent" understand the use of
heuristics in search problems and games
Target Department: Computer Science, Information Technology and Software Engineering

Module Title: Intelligent system Module Code :

Module ECTS:
Course Goals or Learning Outcomes:
At the end of this course the students will be able to:
- Understand reasoning, knowledge representation and learning techniques of artificial
intelligence
- Evaluate the strengths and weaknesses of these techniques and their applicability to
different tasks
- Assess the role of AI in gaining insight into intelligence and perception
- know classical examples of artificial intelligence
- know characteristics of programs that can be considered "intelligent"
- understand the use of heuristics in search problems and games
- know a variety of ways to represent and retrieve knowledge and information
- know the fundamentals of artificial intelligence programming techniques in a modern
programming language
- consider ideas and issues associated with social technical, and ethical uses of machines
that involve artificial intelligence
I
Table of Contents
1 Chapter One: Introduction to AI ............................................................................................................1
1.1. Goals of AI ......................................................................................... Error! Bookmark not defined.
1.2. AI Objectives:..................................................................................... Error! Bookmark not defined.
1.3. What is AI? ........................................................................................................................................2
1.4. Approaches to AI...............................................................................................................................3
1.5. The Foundation of AI ........................................................................................................................6
1.6. Bit History of AI............................................................................................................................. 10
1.7. State of the Art ............................................................................................................................... 12
1.8. Summary ........................................................................................................................................ 14
2 CHAPTER TWO: Intelligent Agents .................................................................................................. 16
2.1 Introduction ............................................................................................................................................... 16
2.1. Agents and Environments............................................................................................................... 16
2.2. Acting of Intelligent Agents (Rationally) ....................................................................................... 18
2.3. Structure of Intelligent Agents ....................................................................................................... 22
2.4. Agent Program Types ..................................................................................................................... 22
2.5. Important Concepts and Terms ...................................................................................................... 30
3 Chapter Three: Solving Problems ....................................................................................................... 33
3.1 Introduction ................................................................................................................................................ 33
3.2 Problem Solving by Searching ................................................................................................................... 33
3.2.1 Problem Solving-Agents........................................................................................................................ 33
3.2.2 Problem Formulation ............................................................................................................................. 37
3.2.1. Example – Search Problems ....................................................................................................... 38
3.2.2. Search Strategies ........................................................................................................................ 44
3.1. Avoiding Repeated States............................................................................................................... 51
3.2. Constraint Satisfaction Problem (CSP) .......................................................................................... 51
3.3. Games as Search Problem .............................................................................................................. 54
4 Chapter Four: Knowledge and Reasoning .......................................................................................... 57
4.1 Logical Agents ........................................................................................................................................... 57
4.2 Knowledge Representation ........................................................................................................................ 58
4.2.1 Techniques of knowledge representation............................................................................................... 59
4.2.2 Logical Representation .......................................................................................................................... 60
4.2.3 Syntax: ................................................................................................................................................... 60
4.2.4 Semantics:.............................................................................................................................................. 60
4.2.5 Semantic Network Representation......................................................................................................... 61
4.2.6 Frame Representation ............................................................................................................................ 62
4.2.7 Production Rules.................................................................................................................................... 63
4.3 Propositional Logic .................................................................................................................................... 65
4.4 First-Order logic: ....................................................................................................................................... 69

II
 4.5 Predicate (First-Order)Logic ...................................................................................................................... 71
4.5.1 Components ........................................................................................................................................... 71
4.6 Inference in First-Order Logic ................................................................................................................... 72
4.6.1 Forward Chaining .................................................................................................................................. 72
4.6.2 Backward Chaining ............................................................................................................................... 73
4.6.3 Substitution: ........................................................................................................................................... 73
4.6.4 FOL inference rules for quantifier: ........................................................................................................ 74
4.6.5 Resolution .............................................................................................................................................. 76
4.7 Knowledge-based Agent ............................................................................................................................ 77
1. Knowledge level ........................................................................................................................................ 79
2. Logical level: ............................................................................................................................................. 79
3. Implementation level: ................................................................................................................................ 79
Approaches to designing a knowledge-based agent: ............................................................................................... 79
A generic knowledge-based agent: .......................................................................................................................... 80
4.7.1 Summary................................................................................................................................................ 81
5 Chapter 5: Uncertain Knowledge and Reasoning ............................................................................... 84
5.1 Quantifying Uncertainty ............................................................................................................................ 84
5.2 Causes of uncertainty: ................................................................................................................................ 84
5.2.1 Acting under Uncertainty ...................................................................................................................... 84
5.2.2 Handling uncertain knowledge .............................................................................................................. 85
5.2.3 Uncertainty and rational decisions ......................................................................................................... 88
5.2.4 Design for a decision-theoretic agent .................................................................................................... 88
5.3 Probabilistic Reasoning.............................................................................................................................. 89
5.3.1 Conditional probability: ......................................................................................................................... 90
5.3.2 Semantics of Conditional Probability .................................................................................................... 92
5.3.3 Axioms for Probability .......................................................................................................................... 93
5.3.4 Bayes’ Rule ........................................................................................................................................... 94
5.3.5 Probabilistic Inference ........................................................................................................................... 95
5.4 Probabilistic Reasoning over Time ............................................................................................................ 96
5.4.1 Time and Uncertainty ............................................................................................................................ 96
5.4.2 Bayesian Network.................................................................................................................................. 97
5.5 Making Simple Decisions ............................................................................................................................ 2
5.5.1 The Basis of Utility Theory ..................................................................................................................... 2
5.5.2 Utility Functions ...................................................................................................................................... 5
5.5.3 Multi-attribute Utility Functions .............................................................................................................. 7
5.5.4 Decision Networks .................................................................................................................................. 8
5.5.5 Value of information ............................................................................................................................. 10
5.6 Making Complex Decisions ....................................................................................................................... 11
5.6.1 Sequential Decision Problems ............................................................................................................... 11
5.6.2 Value Iteration ....................................................................................................................................... 13

III
 5.6.3 Policy iteration ....................................................................................................................................... 14
5.7 Summery .................................................................................................................................................... 15
6 Chapter Six: Learning ......................................................................................................................... 21
6.1 Learning from Examples/Observation ....................................................................................................... 21
6.2 Machine Learning - Categories .................................................................................................................. 23
6.2.1 Supervised learning ............................................................................................................................... 23
6.2.2 Classification ......................................................................................................................................... 26
6.2.3 Unsupervised Learning .......................................................................................................................... 27
6.2.4 Reinforcement Learning ........................................................................................................................ 29
6.2.5 Deep Learning ....................................................................................................................................... 30
6.2.6 Deep Reinforcement Learning ............................................................................................................... 30
6.3 Learning probabilistic model ..................................................................................................................... 31
6.3.1 Statistical learning ................................................................................................................................. 31
6.3.2 Importance of probabilistic learning models ......................................................................................... 32
6.3.3 Bayesian Inference ................................................................................................................................ 32
6.3.4 Naive Bayes algorithm .......................................................................................................................... 33
6.3.5 Neural Networks .................................................................................................................................... 35
6.3.6 Summary................................................................................................................................................ 41
7 Chapter Seven: Communicating, Perceiving, and Acting ................................................................... 45
7.1 Introduction ................................................................................................................................................ 45
7.2 Natural Language Processing ..................................................................................................................... 47
7.3 Natural Language for Communication ....................................................................................................... 49
7.4 Perception .................................................................................................................................................. 49
7.5 Robotics ..................................................................................................................................................... 50

IV
Reference
- Luger, G. (2002) Artificial Intelligence, 4th ed. Addison-Wesley.
- Bratko, Ivan (1990) PROLOG Programming for Artificial Intelligence, 2nd ed.
Addison-Wesley, 1990
- Winston, P.H. (1992) Artificial Intelligence Addison-Wesley
- Ginsberg, M.L. (1993) Essentials of Artificial Intelligence. Morgan Kaufman

V
 Chapter One: Introduction to AI

Activity:
 What is artificial intelligence AI?
 What is the importance of artificial intelligence?
 What is the purpose of artificial intelligence?
 What is the role of artificial intelligence in education?
 What is the future of artificial intelligence?
 How is artificial intelligence created?

We call ourselves Homo sapiens - man the wise. For thousands of years, we have tried to
understand how we think; that is, how a mere handful of matter can perceive, understand, predict,
and manipulate a world. The field of artificial intelligence (AI) attempts not just to understand
but also to build intelligent entities.

AI is one of the newest fields in science and engineering. Work started in earnest soon after
World War II, and the name itself was coined in 1956 by John McCarthy. AI currently
encompasses a huge variety of subfields, ranging from the general (learning and perception) to
the specific, such as playing chess, proving mathematical theorems, writing poetry, driving a car
on a crowded street, and diagnosing diseases. AI is relevant to any intellectual task; it is truly a
universal field.

1.1 Goals of AI
✓ To create expert systems – the systems which exhibit intelligent behavior, learn,
demonstrate, explain, and advice its users which is called smart program.
✓ To implement human intelligence in machines − creating systems that understand, think,
learn, and behave like humans. Shortly, to understand human intelligence better and
writing programs which emulate it.
✓ Make machines smarter
✓ Understand what intelligence is.
✓ Make machines more useful.

1
1.2 What is AI?
AI is an area of computer science that emphasizes the creation of intelligent machines that work
and reacts like humans. It is the simulation of human intelligence processes by machines,
especially computer systems. These processes include learning (the acquisition of information
and rules for using the information), reasoning (using rules to reach approximate or definite
conclusions) and self-correction.
Generally, there are eight definitions of AI, laid out along two dimensions.
✓ The definitions on top are concerned with thought processes and reasoning, whereas the ones
on the bottom address behavior. The definitions on the left measure success in terms of
fidelity to human performance, whereas the ones on the right measure against an ideal
performance measure, called rationality. A system is rational if it does the “right thing,”
given what it knows.

Table 1: AI
The above table means that:
a. Systems that think like humans.
b. Systems that think rationally.
c. Systems that act like humans.
d. Systems that act rationally.

2
1.3 Approaches to AI

The above table can be summarized into the following approaches:

Human-like Rationally
Think (1). Cognitive Science Approach (2). Laws of Thought Approach
Act (3). Turing Test Approach (4). Rational Agent Approach

Most of AI work falls into category (2) and (4).

Historically, all four approaches to AI have been followed, each by different people with
different methods. A human-centered approach must be in part an empirical science, involving
observations and hypotheses about human behavior. A rationalist approach involves a
combination of mathematics and engineering. The various group have both disparaged and
helped each other. Let us look at the four approaches in more detail.

A. Act Humanly: The Turing Test Approach

The Turing Test (performed by Turing Machine1), proposed by Alan Turing (1950). A computer
passes the test if a human interrogator, after posing some written questions, cannot tell whether
the written responses come from a person or from a computer. The computer would need to
possess the following capabilities:
✓ Natural Language Processing (NLP) to enable it to communicate successfully in English;
✓ Knowledge Representation to store what it knows or hears;
✓ Automated Reasoning to use the stored information to answer questions and to draw new
conclusions;
✓ Machine Learning to adapt to new circumstances and to detect and extrapolate patterns.

Turing’s test deliberately avoided direct physical interaction between the interrogator and the
computer, because physical simulation of a person is unnecessary for intelligence. However, the
so-called total Turing Test includes a video signal so that the interrogator can test the subject’s
perceptual abilities, as well as the opportunity for the interrogator to pass physical objects
“through the hatch.” To pass the total Turing Test, the computer will need
✓ Computer Vision to perceive objects, and
✓ Robotics to manipulate objects and move about.
B. Think Humanly: The Cognitive Modeling Approach

1
Turing Machine - A hypothetical computer with an infinitely long memory tape.

3
If we are going to say that a given program thinks like a human, we must have some way of
determining how humans think. We need to get inside the actual workings of human minds.
There are three ways to do this through:
i. Introspection - trying to catch our own thoughts as they go by;
ii. Psychological Experiments - observing a person in action; and
iii. Brain Imaging - observing the brain in action.

Once we have a sufficiently precise theory of the mind, it becomes possible to express the theory
as a computer program. If the program’s input–output behavior matches corresponding human
behavior, that is evidence that some of the programs mechanisms could also be operating in
humans.

The interdisciplinary field of cognitive science2 brings together computer models from AI and
experimental techniques from psychology to construct precise and testable theories of the human
mind. Real cognitive science is necessarily based on experimental investigation of actual
humans or animals.
C. Thinking Rationally: The “Laws of Thought” Approach
“Right Thinking” – is first codified by Aristotle. His syllogisms provided patterns for argument
structures that always yielded correct conclusions when given correct premises.
Example 1.1:
✓ “Socrates is a man; all men are mortal; therefore, Socrates is mortal.”

These laws of thought were supposed to govern the operation of the mind; their study initiated
the field called logic.
There are two main obstacles to this approach.
i. It is not easy to take informal knowledge and state it in the formal terms required by
logical notation, particularly when the knowledge is less than 100% certain.
ii. There is a big difference between solving a problem “in principle” and solving it in
practice. The “in principle” - solve any solvable problem described in logical notation, if
no solution exists, the program might loop forever. This so-called logicist tradition
within an AI that hopes to create Intelligent systems.
D. Acting Rationally: The Rational Agent Approach

2 Cognitive Science - The field of science concerned with cognition; includes parts of cognitive psychology, linguistics,
computer science, cognitive neuroscience and philosophy of mind.

4
An agent is just something that acts (agent comes from the Latin agere, to do). All computer
programs do something, but computer agents are expected to do more:
✓ Operate autonomously,
✓ Perceive their environment,
✓ Persist over a prolonged time period,
✓ Adapt to change, and
✓ Create and pursue goals.
A rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty,
the best expected outcome. In the “laws of thought” approach to AI, the emphasis was on correct
inferences. Making correct inferences is sometimes part of being a rational agent, because one
way to act rationally is to reason logically to the conclusion that a given action will achieve one’s
goals and then to act on that conclusion. On the other hand, correct inference is not all of
rationality.
All the skills needed for the Turing Test also allow an agent to act rationally. Knowledge
representation and reasoning enable agents to reach good decisions. We need to be able to
generate comprehensible sentences in natural language to get by in a complex society. We need
learning not only for erudition, but also because it improves our ability to generate effective
behavior.
The rational-agent approach has two advantages over the other approaches.
a. It is more general than the “laws of thought” approach because correct inference is just
one of several possible mechanisms for achieving rationality.
b. It is more amenable to scientific development than are approaches based on human
behavior or human thought. Human behavior, on the other hand, is well adapted for one
specific environment and is defined by, well, the sum total of all the things that humans
do.

A perfect rationality – is always doing the right thing - isn’t feasible in complicated
environments.

There are two categories of AI. They are

✓ Weak AI – it is also known as Narrow AI. It is an AI system that is designed and trained for
a particular task.
Example: - Virtual Personal Assistants such as Apple’s Siri.

5
 ✓ Strong AI – it is also known as Artificial General Intelligence. It is an AI system with
generalized human cognitive abilities. When presented with an unfamiliar task, it is able to
find a solution without human intervention.
1.4 The Foundation of AI
There are basically
1. Philosophy3

 Can formal rules be used to draw valid conclusions?

 How does the mind arise from a physical brain?
 Where does knowledge come from?
 How does knowledge lead to action?

Aristotle (384–322 B.C.) was the first to formulate a precise set of laws governing the rational
part of the mind. He developed an informal system of syllogisms for proper reasoning, which in
principle allowed one to generate conclusions mechanically, given initial premises. Thomas
Hobbes (1588–1679) proposed that reasoning was like numerical computation, that “we add and
subtract in our silent thoughts.”

Ren´e Descartes (1596–1650) gave a strong advocate of the power of reasoning in understanding
the world, a philosophy now called rationalism. But Descartes was also a proponent of dualism.
He held that there is a part of the human mind (or soul or spirit) that is outside of nature, exempt
from physical laws. Animals, on the other hand, did not possess this dual quality; they could be
treated as machines. An alternative to dualism is materialism, which holds that the brain’s
operation according to the laws of physics constitutes the mind. Free will is simply the way that
the perception of available choices appears to the choosing entity.

The empiricism movement, starting with Francis Bacon’s (1561–1626) Novum Organum, is
characterized by a dictum of John Locke (1632–1704): “Nothing is in the understanding, which
was not first in the senses.” David Hume’s (1711–1776) A Treatise of Human Nature (Hume,
1739) proposed what is now known as the principle of induction: that general rules are acquired
by exposure to repeated associations between their elements. Building on the work of Ludwig
Wittgenstein (1889–1951) and Bertrand Russell (1872–1970), the famous Vienna Circle, led by
Rudolf Carnap (1891–1970), developed the doctrine of logical positivism. This doctrine holds

3
Philosophy – is the rational investigation of questions about existence and knowledge and ethics.

6
 that all knowledge can be characterized by logical theories connected, ultimately, to observation
sentences that correspond to sensory inputs; thus, logical positivism combines rationalism and
empiricism. The confirmation theory of Carnap and Carl Hempel (1905–1997) attempted to
analyze the acquisition of knowledge from experience.

The final element in the philosophical picture of the mind is the connection between knowledge
and action, because intelligence requires action as well as reasoning.
2. Mathematics

 What are the formal rules to draw valid conclusions?

 What can be computed?
 How do we reason with uncertain information?

Philosophers required a level of mathematical formalization in three fundamental areas:

i. Logic - George Boole (1815–1864), who worked out the details of propositional, or Boolean,
logic (Boole, 1847). In 1879, Gottlob Frege (1848–1925) extended Boole’s logic to include
objects and relations, creating the first order logic. Alfred Tarski (1902–1983) introduced a
theory of reference that shows how to relate the objects in a logic to objects in the real world.
ii. Computation - The first nontrivial algorithm is thought to be Euclid’s algorithm for
computing greatest common divisors. Tractability is the understanding of computation via
decidability and computability to solve a problem by dividing into sub-problems within a
given time. It the time required to solve a given problem growths exponentially (not
polynomial), it is called intractable and cannot be solved in a given time. Such intractable
problem can be solved by reducing the time via the theory of NP-Completeness.
iii. Probability – is first framed by the Italian Gerolamo Cardano (1501–1576) in terms of the
possible outcomes of gambling events. In 1654, Blaise Pascal (1623–1662), in a letter to
Pierre Fermat (1601–1665), showed how to predict the future of an unfinished gambling
game and assign average payoffs to the gamblers. Probability quickly became an invaluable
part of all the quantitative sciences, helping to deal with uncertain measurements and
incomplete theories.
3. Economics

7
  How should we make decisions so as to maximize payoff?
 How should we do this when others may not go along?
 How should we do this when the payoff may be far in the future?

The science of economics got its start in 1776, when Scottish philosopher Adam Smith
(1723–1790) published An Inquiry into the Nature and Causes of the Wealth of Nations. It
doesn’t merely mean of money, but also it makes people choices that lead to preferred outcomes.
It is used to provide preferred outcome or utility. It is just like a game, which means that the
actions of one player can significantly affect the utility of another (either positively or
negatively).
4. Neuroscience

 How do brains process information?

Neuroscience is the study of the nervous system, particularly the brain. Aristotle wrote, “Of all
the animals, man has the largest brain in proportion to his size.” Generally, a collection of
simple cells can lead to thought, action, and consciousness or, in the pithy words of John Searle
(1992), brains cause minds.
The comparison of supercomputer, personal computer and human brain since 2008.

Mysticism4 means that minds operate in some mystical realm that is beyond physical science.
Brains and digital computers have somewhat different properties. From the above table,
computers have a cycle time that is a million times faster than a brain.
5. Psychology5

 How do humans and animals think and act?

4
Mysticism – irrational thought or a religion based on mystical communion with an ultimate reality
5
Psychology – is the science of mental life.

8
The origins of scientific psychology are usually traced to the work of the German physicist
Hermann von Helmholtz (1821–1894) and his student Wilhelm Wundt (1832–1920). The
behaviorism movement is used between human and animal considering the measures of percepts
(stimulus) and actions (response).
6. Computer Engineering

 How can we build an efficient computer?

For artificial intelligence to succeed, we need two things: intelligence and an artifact. The
computer has been the artifact of choice. The first operational computer was the
electromechanical Heath Robinson, built in 1940 by Alan Turing’s team for a single purpose:
deciphering German messages.
7. Control Theory and Cybernetics

 How can artifacts operate under their own control?

Ktesibios of Alexandria (c. 250 B.C.) built the first self-controlling machine: a water clock with
a regulator that maintained a constant flow rate. This invention changed the definition of what an
artifact could do. Previously, only living things could modify their behavior in response to
changes in the environment.

Modern control theory, especially the branch known as stochastic optimal control, has as its goal
the design of systems that maximize an objective function over time. This roughly matches our
view of AI: designing systems that behave optimally.
8. Linguistics

 How does language relate to thought?

Modern linguistics and AI, then, were “born” at about the same time, and grew up together,
intersecting in a hybrid field called computational linguistics or natural language processing.
Much of the early work in knowledge representation (the study of how to put knowledge into a
form that a computer can reason with) was tied to language and informed by research in
linguistics, which was connected in turn to decades of work on the philosophical analysis of
language.

9
1.5 Bit History of AI
✓ 1940s – the invention of a programmable digital computer, the Atanasoff Berry Computer
(ABC). This specific invention inspired scientists to move forward with the idea of creating
an “electronic brain,” or an artificially intelligent being. In the same year, Alan Turing, a
mathematician among other things, proposed a test that measured a machine’s ability to
replicate human actions to a degree that was indistinguishable from human behavior.
✓ 1949 - Computer scientist Edmund Berkeley’s book “Giant Brains: Or Machines That
Think” noted that machines have increasingly been capable of handling large amounts of
information with speed and skill. He went on to compare machines to a human brain if it
were made of “hardware and wire instead of flesh and nerves,” describing machine ability
to that of the human mind, stating that “a machine, therefore, can think.”
✓ 1950 - Alan Turing published “Computing Machinery and Intelligence,” which proposed the
idea of The Imitation Game – a question that considered if machines can think. This proposal
later became The Turing Test, which measured machine (artificial) intelligence. Turing’s
development tested a machine’s ability to think as a human would. The Turing Test became
an important component in the philosophy of artificial intelligence, which discusses
intelligence, consciousness, and ability in machines.

✓ 1956 – is the birth of Artificial Intelligent. American computer scientist John McCarthy
organized the Dartmouth Conference, at which the term ‘Artificial Intelligence’ was first

10
 adopted. Therefore, McCarthy is the father of AI. He also developed LISP programming
language.
✓ 1959 - Samuel coined the term “machine learning” when speaking about programming a
computer to play a game of chess better than the human who wrote its program.
✓ 1966 - Shakey the Robot, developed by Charles Rosen with the help of 11 others, was the
first general-purpose mobile robot, also known as the “first electronic person.”
✓ 1970 - WABOT-1, the first anthropomorphic robot, was built in Japan at Waseda University.
Its features included moveable limbs, ability to see, and ability to converse.
✓ 1977 - Director George Lucas’ film Star Wars is released. The film features C-3PO, a
humanoid robot who is designed as a protocol droid and is “fluent in more than seven million
forms of communication.”
✓ 1980 - WABOT-2 was built at Waseda University. This inception of the WABOT allowed
the humanoid to communicate with people as well as read musical scores and play music on
an electronic organ.
✓ 1990s - a fifth generation computer to advance of machine learning developed by Japanese
government. AI enthusiasts believed that soon computers would be able to carry on
conversations, translate languages, interpret pictures, and reason like people.
✓ 1997 - Computer scientists Sepp Hochreiter and Jürgen Schmidhuber developed Long
Short-Term Memory (LSTM), a type of a recurrent neural network (RNN) architecture used
for handwriting and speech recognition.
✓ 1998 - Dave Hampton and Caleb Chung invented Furby, the first “pet” toy robot for children.
✓ 1999 - In line with Furby, Sony introduced AIBO (Artificial Intelligence RoBOt), a robotic
pet dog crafted to “learn” by interacting with its environment, owners, and other AIBOs. Its
features included the ability to understand and respond to 100+ voice commands and
communicate with its human owner.
✓ 2000 - Professor Cynthia Breazeal developed Kismet, a robot that could recognize and
simulate emotions with its face. It was structured like a human face with eyes, lips, eyelids,
and eyebrows.
✓ 2000 - Honda releases ASIMO, an artificially intelligent humanoid robot.
✓ 2004 - NASA's robotic exploration rovers Spirit and Opportunity navigate Mars’ surface
without human intervention.
✓ 2006 - Oren Etzioni (computer science professor), Michele Banko, and Michael Cafarella
(computer scientists), coined the term “machine reading,” defining it as unsupervised
autonomous understanding of text.

11
✓ 2010 - Microsoft launched Kinect for Xbox 360, the first gaming device that tracked human
body movement using a 3D camera and infrared detection.
✓ 2011 - Apple released Siri, a virtual assistant on Apple iOS operating systems. Siri uses a
natural-language user interface to infer, observe, answer, and recommend things to its human
user. It adapts to voice commands and projects an “individualized experience” per user.
✓ 2016 - A humanoid robot named Sophia is created by Hanson Robotics. She is known as the
first “robot citizen.” What distinguishes Sophia from previous humanoids is her likeness to
an actual human being, with her ability to see (image recognition), make facial expressions,
and communicate through AI.
✓ 2016 - Google released Google Home, a smart speaker that uses AI to act as a “personal
assistant” to help users remember tasks, create appointments, and search for information by
voice.
✓ 2017 - The Facebook Artificial Intelligence Research lab trained two “dialog agents”
(chatbots) to communicate with each other in order to learn how to negotiate. However, as
the chatbots conversed, they diverged from human language (programmed in English) and
invented their own language to communicate with one another – exhibiting artificial
intelligence to a great degree.
✓ 2018 - Google developed BERT, the first “bidirectional, unsupervised language
representation that can be used on a variety of natural language tasks using transfer
learning.”
✓ 2018 - Samsung introduced Bixby, a virtual assistant. Bixby’s functions include Voice,
where the user can speak to and ask questions, recommendations, and suggestions; Vision,
where Bixby’s “seeing” ability is built into the camera app and can see what the user sees (i.e.
object identification, search, purchase, translation, landmark recognition); and Home, where
Bixby uses app-based information to help utilize and interact with the user (e.g. weather and
fitness applications.)
1.6 State of the Art
The state-of-the-art deals with the applications of AI. Some of the AI applications are
 Robotic Vehicles – A driverless robotic car named STANLEY sped through the rough
terrain of the Mojave Desert at 22 mph, finishing the 132-mile course first to win the 2005
DARPA Grand Challenge. STANLEY is a Volkswagen Touareg outfitted with cameras,
radar, and laser rangefinders to sense the environment and onboard software to command the
steering, braking, and acceleration (Thrun, 2006).

12
 Speech Recognition – Some intelligent systems are capable of hearing and comprehending
the language in terms of sentences and their meanings while a human talk to it. It can handle
different accents, slang words, noise in the background, change in human’s noise due to cold,
etc.
 Autonomous Planning and Scheduling – A hundred million miles from Earth, NASA’s
Remote Agent program became the first on-board autonomous planning program to control
the scheduling of operations for a spacecraft (Jonsson et al., 2000). REMOTE AGENT
generated plans from high-level goals specified from the ground and monitored the
execution of those plans—detecting, diagnosing, and recovering from problems as they
occurred.
 Game Playing – AI plays crucial role in strategic games such as chess, poker, tic-tac-toe,
etc., where machine can think of large number of possible positions based on heuristic
knowledge.
 Spam Fighting – Each day, learning algorithms classify over a billion messages as spam,
saving the recipient from having to waste time deleting what, for many users, could comprise
80% or 90% of all messages, if not classified away by algorithms.
 Logistics Planning – During the Persian Gulf crisis of 1991, U.S. forces deployed a
Dynamic Analysis and Re-planning Tool, DART (Cross and Walker, 1994), to do automated
logistics planning and scheduling for transportation. This involved up to 50,000 vehicles,
cargo, and people at a time, and had to account for starting points, destinations, routes, and
conflict resolution among all parameters.
 Robotics – Robots are able to perform the tasks given by a human. They have sensors to
detect physical data from the real world such as light, heat, temperature, movement, sound,
bump, and pressure. They have efficient processors, multiple sensors and huge memory, to
exhibit intelligence. In addition, they are capable of learning from their mistakes and they
can adapt to the new environment.
 Machine Translation – A computer program automatically translates from Arabic to
English, allowing an English speaker to see the headline “Ardogan Confirms That Turkey
Would Not Accept Any Pressure, Urging Them to Recognize Cyprus.”
 Natural Language Processing − It is possible to interact with the computer that understands
natural language spoken by humans.
 Expert Systems − There are some applications which integrate machine, software, and
special information to impart reasoning and advising. They provide explanation and advice
to the users.

13
 Machine (Systems) Vision − These systems understand, interpret, and comprehend visual
input on the computer. For example,
o A spying aero-plane takes photographs, which are used to figure out spatial information
or map of the areas.
o Doctors use clinical expert system to diagnose the patient.
o Police use computer software that can recognize the face of criminal with the stored
portrait made by forensic artist.
 Handwriting Recognition − The handwriting recognition software reads the text written on
paper by a pen or on screen by a stylus. It can recognize the shapes of the letters and convert
it into editable text.
1.7 Summary
Programming Without AI Programming With AI
A computer program without AI can answer A computer program with AI can answer the
the specific questions it is meant to solve. generic questions it is meant to solve.
Modifications in the program leads to AI programs can absorb ne modifications by
change in its structure. putting highly independent pieces of information
together. Hence you can modify even a minute
piece if information of program without affecting
its structure.
Modification is not quick and easy. It may Quick and easy program modification.
lead to affecting the program adversely.

14
 Review Questions

1. What is the key component of AI?

2. What are the main goals of AI?
3. What is explainable AI principle?
4. What skills do you need for AI?
5. What are the major elements of AI?
6. Briefly explain intelligence? What it is composed of?
7. Define artificial intelligence?
8. Why we need artificial intelligence?
9. List down disciplines which artificial intelligence requires?
10. Write the pros and cons of AI?
11. Who coined the term AI for the first time?
12. Based on the level of strength we can classify AI into three, briefly explain each of them?
13. Based on the functionality we can classify AI into four, briefly explain each of them?
14. Briefly explain the mapping of human thinking to artificial intelligence components?
15. Write down some applications of AI in agriculture, health, education, and business?
16. List down some well-known AI tools and platforms?
17. List down some concrete examples of AI in social media, online shopping, and mobile
phone usage?

15
 CHAPTER TWO: Intelligent Agents

Activity:
 What are the main components of intelligent agent?
 Which things are used to improve the agents performance?
 How many types of intelligent agents are there?
 What is intelligent agent and explain its types with examples?
 What is environment in artificial intelligence?

2.1 Introduction
The concept of rationality can be applied to a wide variety of agents operating in any imaginable
environment. We begin by examining agents, environments, and the coupling between them.
The observation that some agents behave better than others leads naturally to the idea of a
rational agent one that behaves as well as possible. How well an agent can behave depends on the
nature of the environment; some environments are more difficult than others. We give a crude
categorization of environments and show how properties of an environment influence the design
of suitable agents for that environment.

2.2 Agents and Environments

An agent is anything that can be viewed as perceiving its environment through sensors6 and
acting upon that environment through actuators7.
Example 2.1:

Fig. 2.1. Agents interact with environments through sensors and actuators.

A human agent has eyes, ears, and other organs for sensors and hands, legs, vocal tract, and so
on for actuators. A robotic agent might have cameras and infrared range finders for sensors and
various motors for actuators. A software agent receives keystrokes, file contents, and network

6
Sensors – is any device that receives a signal or stimulus (as heat or pressure or light or motion etc.) and responds to it in a distinctive manner.
7
Actuators – is a mechanism that puts something into automatic action.

16
packets as sensory inputs and acts on the environment by displaying on the screen, writing file,
and sending network packets.

The term percept to refer to the agent’s perceptual inputs at any given instant. An agent’s
percept sequence is the complete history of everything the agent has ever perceived. In general,
an agent’s choice of action at any given instant can depend on the entire percept sequence
observed to date, but not on anything it hasn’t perceived. An agent’s behavior is described by the
agent function that maps any given percept sequence to an action.

Given an agent to experiment with, we can, in principle, construct a table by trying out all
possible percept sequences and recording which actions the agent does in response. The table is
an external characterization of the agent. Internally, the agent function for an artificial agent
will be implemented by an agent program. The agent function is an abstract mathematical
description; the agent program is a concrete implementation, running within some physical
system.
Example:
 The vacuum-cleaner world. It has two locations: squares A and B. It is shown here below
figure.

Fig. 2.2. A vacuum-cleaner world with just two locations.

The vacuum agent perceives which square it is in and whether there is dirt in the square. It can
choose to move left, move right, suck up the dirt, or do nothing. One very simple agent function
is the following: if the current square is dirty, then suck; otherwise, move to the other square. A
partial tabulation of this agent function is shown in figure below.

17
Fig. 2.3. Partial tabulation of a simple agent function for the vacuum-cleaner world shown in fig. 2.2.

The vacuum-world agents can be defined simply by filling in the right-hand column in various
ways. What is the right way to fill out the table? or what makes an agent good or bad, intelligent
or stupid?

2.3 Acting of Intelligent Agents (Rationally)

A rational agent is one that does the right thing. When an agent is plunked down in an
environment, it generates a sequence of actions according to the percepts it receives. This
sequence of actions causes the environment to go through a sequence of states. If the sequence is
desirable, then the agent has performed well. This notion of desirability is captured by a
performance measure that evaluates any given sequence of environment states.

Obviously, there is not one fixed performance measure for all tasks and agents; typically, a
designer will devise one appropriate to the circumstances.

As a general rule, it is better to design performance measures according to what one actually
wants in the environment, rather than according to how one thinks the agent should behave.

Rationality:
What is rational at any given time depends on four things:
✓ The performance measure that defines the criterion of success.
✓ The agent’s prior knowledge of the environment.
✓ The actions that the agent can perform.
✓ The agent’s percept sequence to date.
This leads to a definition of a rational agent:

18
 ✓ For each possible percept sequence, a rational agent should select an action that is
expected to maximize its performance measure, given the evidence provided by the
percept sequence and whatever built-in knowledge the agent has.
Omniscience, Learning, and Autonomy:
An omniscient agent knows the actual outcome of its actions and can act accordingly; but
omniscience is impossible in reality. Rationality maximizes expected performance, while
perfection maximizes actual performance. A rationality does not require omniscience, then,
because the rational choice depends only on the percept sequence to date.

Doing actions in order to modify future percepts - sometimes called information gathering - is an
important part of rationality. A rational agent not only require to gather information but also to
learn as much as possible from what it perceives.

To the extent that an agent relies on the prior knowledge of its designer rather than on its own
percepts, we say that the agent lacks autonomy. A rational agent should be autonomous - it
should learn what it can to compensate for partial or incorrect prior knowledge.

After sufficient experience of its environment, the behavior of a rational agent can become
effectively independent of its prior knowledge. Hence, the incorporation of learning allows one
to design a single rational agent that will succeed in a vast variety of environments.
The Nature of Environments
The flavor of the task environment directly affects the appropriate design for the agent program
that provides solutions for problems. These flavors are:
a. Specifying the Task Environment:
A group of the performance measure, the environment, and the agent’s actuators and sensors
specified are called task environment. Acronymically minded as PEAS (Performance,
Environment, Actuators, Sensors). In designing an agent, the first step must always be to specify
the task environment as fully as possible.
Example 2.2:
 Consider an automated taxi driver.

19
 Fig. 2.4. PEAS description of the task environment for an automated taxi.
What are the desirable qualities of PEAS?
b. Properties of Task Environment
 Fully Observable vs. Partially Observable – if an agent’s sensors give it access to the
complete state of the environment at each point in time, then is called fully observable. A
task environment is effectively fully observable if the sensors detect all aspects that are
relevant to the choice of action; relevance, in turn, depends on the performance measure.
Fully observable environments are convenient because the agent need not maintain any
internal state to keep track of the world. An environment might be partially observable
because of noisy and inaccurate sensors or because parts of the state are simply missing
from the sensor data - for example, a vacuum agent with only a local dirt sensor cannot tell
whether there is dirt in other squares, and an automated taxi cannot see what other drivers
are thinking. If the agent has no sensors at all then the environment is unobservable.
 Single Agent vs. Multiagent – an agent solving a crossword puzzle by itself is clearly in a
single-agent environment, whereas an agent playing chess is in a two-agent environment.
In chess, the opponent entity B is trying to maximize its performance measure, which, by
the rules of chess, minimizes agent A’s performance measure. Thus, chess is a competitive
multiagent environment.
In the taxi-driving environment, on the other hand, avoiding collisions maximizes the
performance measure of all agents, so it is a partially cooperative multiagent environment.
 Deterministic vs. Stochastic – If the next state of the environment is completely
determined by the current state and the action executed by the agent, then we say the
environment is deterministic; otherwise, it is stochastic. In principle, a fully observable,
deterministic environment, while if the environment is partially observable, however, then
it could appear to be stochastic. Taxi driving is stochastic, because one can never predict
the behavior of traffic exactly. The vacuum world is deterministic, but variations can
include stochastic elements such as randomly appearing dirt and an unreliable suction

20
 mechanism. We say an environment is uncertain if it is not fully observable or not
deterministic.
The word “stochastic” generally implies that uncertainty about outcomes is quantified in
terms of probabilities; a nondeterministic environment is one in which actions are
characterized by their possible outcomes, but no probabilities are attached to them.
Nondeterministic environment descriptions are usually associated with performance
measures that require the agent to succeed for all possible outcomes of its actions.
 Episodic vs. Sequential – In an episodic task environment, the agent’s experience is
divided into atomic episodes. In each episode the agent receives a percept and then
performs a single action. Crucially, the next episode does not depend on the actions taken in
previous episodes. In sequential environments, on the other hand, the current decision
could affect all future decisions. Chess and taxi driving are sequential: in both cases,
short-term actions can have long-term consequences. Episodic environments are much
simpler than sequential environments because the agent does not need to think ahead.
 Static vs. Dynamic - If the environment can change while an agent is deliberating, then we
say the environment is dynamic for that agent; otherwise, it is static. Static environments
are easy to deal with because the agent need not keep looking at the world while it is
deciding on an action, nor need it worry about the passage of time. Dynamic environments,
on the other hand, are continuously asking the agent what it wants to do; if it hasn’t decided
yet, that counts as deciding to do nothing. If the environment itself does not change with the
passage of time but the agent’s performance score does, then we say the environment is
semi-dynamic. Taxi driving is clearly dynamic: the other cars and the taxi itself keep
moving while the driving algorithm dithers about what to do next. Chess, when played with
a clock, is semi-dynamic. Crossword puzzles are static.
 Discrete vs. Continuous – they are applied to the state of the environment, to the way time
is handled, and to the percepts and actions of the agent. For example, the chess
environment has a finite number of distinct states (excluding the clock). Taxi driving is a
continuous-state and continuous-time problem: the speed and location of the taxi and of the
other vehicles sweep through a range of continuous values and do so smoothly over time.
Input from digital cameras is discrete.
 Known vs. Unknown – it refers both the environment and agent’s (or designer’s) state of
knowledge about the “laws of physics” of the environment. In a known environment, the
outcomes (or outcome probabilities if the environment is stochastic) for all actions are
given. Obviously, if the environment is unknown, the agent will have to learn how it works

21
 in order to make good decisions. For a known environment to be partially observable like,
in solitaire card games, I know the rules but am still unable to see the cards that have not yet
been turned over. Conversely, an unknown environment can be fully observable - in a new
video game, the screen may show the entire game state but you still don’t know what the
buttons do until you try them.

2.4 Structure of Intelligent Agents

Behavior is the action that is performed after any given sequence of percepts. The job of AI is to
design an agent program that implements the agent function - the mapping from percepts to
actions. We assume this program will run on some sort of computing device with physical
sensors and actuators - we call this the architecture:
agent = architecture + program
The program we choose has to be one that is appropriate for the architecture. If the program is
going to recommend actions like Walk, the architecture had better have legs. The architecture
might be an ordinary PC, or it might be a robotic car with several onboard computers, cameras,
and other sensors. Generally, the architecture makes the percepts from the sensors available to
the program, runs the program, and feeds the program’s action choices to the actuators as they
are generated.
 Agent Programs
It takes the current percept as input from the sensors, the agent function, which takes the entire
percept history and return an action to the actuators. What is the difference between agent
program and agent functions? The agent program takes the current percept as input, while the
agent function takes the entire percept history.
2.5 Agent Program Types
There are basically five basic kinds of agent programs that embody the principles underlying
almost all intelligent systems:
A. Simple Reflex Agent
It is the simplest kind of agent. These agents select actions on the basis of the current percept,
ignoring the rest of the percept history.

22
Example-1-:
 The vacuum agent whose agent function is based only on the current location and on
whether that location contains dirt, because its decision is based only on the current location
and on whether that location contains dirt of figure 2.2. above. An agent program for this
agent is shown here below.

Fig. 2.5. The agent program for a simple reflex agent in the two-state vacuum environment.
Example-2.3:

Consider an automated taxi driver. If the car in front brakes and its brake lights come on, then
you should notice this and initiate braking. In other words, some processing is done on the visual
input to establish the condition we call “The car in front is braking.” Then, this triggers some
established connection in the agent program to the action “initiate braking.” We call such a
connection a condition–action rule written as
if car-in-front-is-braking then initiate-braking.

The figure below gives the structure of general program in schematic form, showing how the
condition–action rules allow the agent to make the connection from percept to action.

Fig. 2.6. Schematic diagram of a simple reflex agent.

23
 Fig. 2.7. A simple reflex agent that acts according to a rule whose condition matches the current state.

The rectangles are used to denote the current internal state of the agent’s decision process, and
ovals to represent the background information used in the process. The INTERPRET-INPUT
function generates an abstracted description of the current state from the percept, and the
RULE-MATCH function returns the first rule in the set of rules that matches the given state
description. The description in terms of “rules” and “matching” is purely conceptual.

The agent in Figure 2.7. above will work only if the correct decision can be made on the basis of
only the current percept - that is, only if the environment is fully observable.
B. Model Based Reflex Agent
The most effective way to handle partial observability is for the agent to keep track of the part of
the world it can’t see now. That is, the agent should maintain some sort of internal state that
depends on the percept history and thereby reflects at least some of the unobserved aspects of the
current state. Shortly is knowledge-base.
Example:
 The automated taxi driver (In case of car braking problem).

The Figure below gives the structure of the model-based reflex agent with internal state, showing
how the current percept is combined with the old internal state to generate the updated
description of the current state, based on the agent’s model of how the world works.

24
 Fig. 2.8. A model-based reflex agent.
The agent program of model-based agent is shown in figure below.

Fig. 2.9. A model-based reflex agent. It keeps track of the current state of the world, using an internal model. It then
chooses an action in the same way as the reflex agent.

The interesting part is the function UPDATE-STATE, which is responsible for creating the new
internal state description. The details of how models and states are represented vary widely
depending on the type of environment and the particular technology used in the agent design.
C. Goal Based Agent
Knowing something about the current state of the environment is not always enough to decide
what to do. It is an expansion of model-based reflex agent.
Example:
 At a road junction, the taxi can turn left, turn right, or go straight on. The correct decision
depends on where the taxi is trying to get to. In other words, as well as a current state
description, the agent needs some sort of goal information that describes situations that are
desirable for example, being at the passenger’s destination. The agent program can
combine this with the model (the same information as was used in the model-based reflex

25
 agent) to choose actions that achieve the goal. Figure below shows the goal-based agent’s
structure.

Fig. 2.10. A model-based, goal-based agent. It keeps track of the world state as well as a set of goals it is trying to
achieve, and chooses an action that will (eventually) lead to the achievement of its goals.
Sometimes goal-based action selection is straightforward.
Example 2.4:
 When goal satisfaction results immediately from a single action. Sometimes it will be
more-tricky. For example, when the agent has to consider long sequences of twists and
turns in order to find a way to achieve the goal. Search and planning are the subfields of AI
devoted to finding action sequences that achieve the agent’s goals.

In this, decision making involves consideration of the future - both “What will happen if I do
such-and-such?” and “Will that make me happy?” It is less efficient; it is more flexible because
the knowledge that supports its decisions is represented explicitly and can be modified.
D. Utility Based Agent
An agent’s utility function is essentially an internalization of the performance measure. If the
internal utility function and the external performance measure are in agreement, then an agent
that chooses actions to maximize its utility will be rational according to the external performance
measure.
It has two kinds of cases in terms of flexibility and learning to make rational decisions.
1. When there are conflicting goals, only some of which can be achieved (for example,
speed and safety), the utility function specifies the appropriate tradeoff.

26
 2. When there are several goals that the agent can aim for, none of which can be achieved
with certainty, utility provides a way in which the likelihood of success can be weighed
against the importance of the goals.

Partial observability and stochasticity are ubiquitous in the real world, and so, therefore, is
decision making under uncertainty. Technically speaking, a rational utility-based agent chooses
the action that maximizes the expected utility of the action outcomes - that is, the utility the agent
expects to derive, on average, given the probabilities and utilities of each outcome. An agent that
possesses an explicit utility function can make rational decisions with a general-purpose
algorithm that does not depend on the specific utility function being maximized. The
utility-based agent structure appears in figure below.

Fig. 2.11. A model-based, utility-based agent.

A utility-based agent has to model and keep track of its environment, tasks that have involved a
great deal of research on perception, representation, reasoning, and learning.
E. Learning Agent
Each kind of agent program combines particular components in particular ways to generate
actions. We convert all these agents to improve the performance of their components so as to
generate better actions which is called learning agents. A learning agent can be divided into
four conceptual components as shown in the figure below.

27
 Fig. 2.12. A general learning agent.

The learning element is responsible for making improvements, while the performance element is
responsible for selecting external actions. The performance element is what we have previously
considered to be the entire agent: it takes in percepts and decides on actions. The learning
element uses feedback from the critic on how the agent is doing and determines how the
performance element should be modified to do better in the future.

The design of the learning element depends very much on the design of the performance element.
When trying to design an agent that learns a certain capability, the first question is not “How am
I going to get it to learn this?” but “What kind of performance element will my agent need to do
this once it has learned how?” Given an agent design, learning mechanisms can be constructed to
improve every part of the agent.

The critic tells the learning element how well the agent is doing with respect to a fixed
performance standard. The critic is necessary because the percepts themselves provide no
indication of the agent’s success.
Example:
 A chess program could receive a percept indicating that it has checkmated its opponent, but
it needs a performance standard to know that this is a good thing; the percept itself does not
say so. It is important that the performance standard be fixed. Conceptually, one should
think of it as being outside the agent altogether because the agent must not modify it to fit
its own behavior.

28
Th problem generator is responsible for suggesting actions that will lead to new and informative
experiences. The point is that if the performance element had its way, it would keep doing the
actions that are best, given what it knows. But if the agent is willing to explore a little and do
some perhaps suboptimal actions in the short run, it might discover much better actions for the
long run. The problem generator’s job is to suggest these exploratory actions. This is what
scientists do when they carry out experiments. Galileo did not think that dropping rocks from the
top of a tower in Pisa was valuable in itself. He was not trying to break the rocks or to modify the
brains of unfortunate passers-by. His aim was to modify his own brain by identifying a better
theory of the motion of objects.
Let us consider an automated taxi to summarize the learning agent.
The performance element consists of whatever collection of knowledge and procedures the taxi
has for selecting its driving actions. The taxi goes out on the road and drives, using this
performance element. The critic observes the world and passes information along to the learning
element. For example, after the taxi makes a quick left turn across three lanes of traffic, the critic
observes the shocking language used by other drivers. From this experience, the learning
element is able to formulate a rule saying this was a bad action, and the performance element is
modified by installation of the new rule. The problem generator might identify certain areas of
behavior in need of improvement and suggest experiments, such as trying out the brakes on
different road surfaces under different conditions.

The forms of learning in the preceding paragraph do not need to access the external performance
standard - in a sense, the standard is the universal one of making predictions that agree with
experiment. The situation is slightly more complex for a utility-based agent that wishes to learn
utility information. For example, suppose the taxi-driving agent receives no tips from passengers
who have been thoroughly shaken up during the trip. The external performance standard must
inform the agent that the loss of tips is a negative contribution to its overall performance; then the
agent might be able to learn that violent maneuvers do not contribute to its own utility. In a sense,
the performance standard distinguishes part of the incoming percept as a reward (or penalty) that
provides direct feedback on the quality of the agent’s behavior. Hard-wired performance
standards such as pain and hunger in animals can be understood in this way.

Generally, learning in intelligent agents can be summarized as a process of modification of each

component of the agent to bring the components into closer agreement with the available
feedback information, thereby improving the overall performance of the agent.

29
2.6 Important Concepts and Terms
How the Components of Agent Programs Work?
To understand how the components of agent program work, it is important to categorize into the
following parts and shown in the figure below.

Fig. 2.13 Three ways to represent states and the transitions between them. (a) Atomic representation: a state (such as
B or C) is a black box with no internal structure; (b) Factored representation: a state consists of a
vector of attribute values; values can be Boolean, real-valued, or one of a fixed set of symbols. (c)
Structured representation: a state includes objects, each of which may have attributes of its own
as well as relationships to other objects.

In an atomic representation each state of the world is indivisible - it has no internal structure.
Consider the problem of finding a driving route from one end of a country to the other via some
sequence of cities. For the purposes of solving this problem, it may suffice to reduce the state of
world to just the name of the city we are in - a single atom of knowledge; a “black box” whose
only discernible property is that of being identical to or different from another black box.
Example 2.6:
 Search, and Game-Playing.
A factored representation splits up each state into a fixed set of variables or attributes, each of
which can have a value. While two different atomic states have nothing in common - they are
just different black boxes - two different factored states can share some attributes (such as being
at some particular GPS location) and not others (such as having lots of gas or having no gas); this
makes it much easier to work out how to turn one state into another. With factored
representations, we can also represent uncertainty - for example, ignorance about the amount of
gas in the tank can be represented by leaving that attribute blank.

30
Example 2.7:
 Constraint Satisfaction Problem, Propositional Logic, and Machine Learning.
For many purposes, we need to understand the world as having things in it that are related to each
other, not just variables with values. For example, we might notice that a large truck ahead of us
is reversing into the driveway of a dairy farm but a cow has got loose and is blocking the truck’s
path. A structured representation is pre-equipped with the attribute
TruckAheadBackingIntoDairyFarmDrivewayBlockedByLooseCow with value true or false, in
which objects such as cows and trucks and their various and varying relationships can be
described explicitly.
Example 2.8:
 Relational Databases, First-Order Logic, First-Order Probability Models, Knowledge-Based
Learning and Natural Language Understanding.
In fact, almost everything that humans express in natural language concerns objects and their
relationships. The axis expressiveness representation increases and become more complex from
atomic to structured representation.

31
Review Questions

1. How an agent will interact with the environment?

2. What is an agent perceiving its environment?
3. What is agent and its types?
4. What is agent function in AI?
5. What is agent and environment in AI?
6. What is the structure of agents?
7. What are intelligent agents and its types?
8. What do you mean by intelligent agent?
9. What are the characteristics of intelligent agent?
10. What are the functions of agent?
11. What are the types of agents?
12. What is an example of an agent?
13. How many types of agents are there in intelligent systems?
14. How many types of agent program are there?
15. What is an agent program in artificial intelligence?
16. Which is basic kind of agent program?
17. What are the types of intelligent agents?
18. What are the components of agents?
19. What's the difference between agent function and agent program?
20. What are learning agents?
21. What is the relation between agent function and agent program?

32
 Chapter Three: Solving Problems
3.1 Introduction
The simplest agents were the reflex agents, which base their actions on a direct mapping from
states to actions. Such agents cannot operate well in environments for which this mapping would
be too large to store and would take too long to learn. Goal-based agents consider future actions
and the desirability of their outcomes.

This chapter describes one kind of goal-based agent called a problem-solving agent.
Problem-solving agents use atomic representations, i.e., states of the world are considered as
wholes, with no internal structure visible to the problem-solving algorithms. The search
algorithms used in this chapter to solve problems are uninformed search algorithms - algorithms
that are given no information about the problem other than its definition and an informed search
algorithm can do quite well given some guidance on where to look for solutions.

3.2 Problem Solving by Searching

3.2.1 Problem Solving-Agents

Intelligent agents are supposed to maximize their performance measure. Imagine an agent in the
city of Arad, Romania, enjoying a touring holiday. The agent’s performance measure contains
many factors: it wants to improve its suntan, improve its Romanian, take in the sights, enjoy the
nightlife, avoid hangovers, and so on. The decision problem is a complex one involving many
tradeoffs and careful reading of guidebooks. Now, suppose the agent has a nonrefundable ticket
to fly out of Bucharest the following day. In that case, it makes sense for the agent to adopt the
goal of getting to Bucharest. Courses of action that don’t reach Bucharest on time can be rejected
without further consideration and the agent’s decision problem is greatly simplified. Goals help
organize behavior by limiting the objectives that the agent is trying to achieve and hence the
actions it needs to consider. Goal formulation, based on the current situation and the agent’s
performance measure, is the first step in problem solving.

Consider a goal to be a set of world states - exactly those states in which the goal is satisfied. The
agent’s task is to find out how to act, now and in the future, so that it reaches a goal state. Before
it can do this, it needs to decide what sorts of actions and states it should consider. If it were to
consider actions at the level of “move the left foot forward an inch” or “turn the steering wheel
one degree left,” the agent would probably never find its way out of the parking lot, let alone to
Bucharest, because at that level of detail there is too much uncertainty in the world and there

33
would be too many steps in a solution. Problem formulation is the process of deciding what
actions and states to consider, given a goal.

Our agent has now adopted the goal of driving to Bucharest and is considering where to go from
Arad. Three roads lead out of Arad, one toward Sibiu, one to Timisoara, and one to Zerind. None
of these achieves the goal, so unless the agent is familiar with the geography of Romania, it will
not know which road to follow (which of its possible actions is best), because it does not yet
know enough about the state that results from taking each action. If the agent has no additional
information - i.e., if the environment is unknown - then it is having no choice but to try one of the
actions at random.

But, suppose the agent has a map of Romania. The point of a map is to provide the agent with
information about the states it might get itself into and the actions it can take. The agent can use
this information to consider subsequent stages of a hypothetical journey via each of the three
towns, trying to find a journey that eventually gets to Bucharest. Once it has found a path on the
map from Arad to Bucharest, it can achieve its goal by carrying out the driving actions that
correspond to the legs of the journey. In general, an agent with several immediate options of
unknown value can decide what to do by first examining future actions that eventually lead to
states of known value.

To be more specific about “examining future actions,” we have to be more specific about
properties of the environment. Assume that the environment is observable (the agent always
knows the current state. For the agent driving in Romania, it’s reasonable to suppose that each
city on the map has a sign indicating its presence to arriving drivers), discrete (at any given state
there are only finitely many actions to choose from. This is true for navigating in Romania
because each city is connected to a small number of other cities), known (the agent knows which
states are reached by each action) and deterministic (each action has exactly one outcome).

Under these assumptions, the solution to any problem is a fixed sequence of actions. The process
of looking for a sequence of actions that reaches the goal is called search. A search algorithm
takes a problem as input and returns a solution in the form of an action sequence. Once a solution
is found, the actions it recommends can be carried out. This is called the execution phase. Thus,
we have a simple “formulate, search, execute” design for the agent, as shown in Fig. 3.1. below.

34
Fig. 3.1. A simple problem-solving agent. It first formulates a goal and a problem, searches for a sequence of
actions that would solve the problem, and then executes the actions one at a time. When this is complete, it
formulates another goal and starts over.

After formulating a goal and a problem to solve, the agent calls a search procedure to solve it. It
then uses the solution to guide its actions, doing whatever the solution recommends as the next
thing to do - typically, the first action of the sequence and then removing that step from the
sequence. Once the solution has been executed, the agent will formulate a new goal.
Notice

✓ While the agent is executing the solution sequence it ignores its percepts when choosing an
action because it knows in advance what they will be. An agent that carries out its plans with
its eyes closed, so to speak, must be quite certain of what is going on. Control theorists call
this an open-loop system, because ignoring the percepts breaks the loop between agent and
environment.

Well-Defined Problems and Solutions

A problem can be defined formally by five components:
a. The initial state that the agent starts in. For example, the initial state for our agent in
Romania might be described as In(Arad).
b. A description of the possible actions available to the agent. Given a particular state s,
ACTIONS(s) returns the set of actions that can be executed in s. We say that each of

35
 these actions is applicable in s. For example, from the state In(Arad), the applicable
actions are {Go(Sibiu), Go(Timisoara), Go(Zerind)}.
c. A description of what each action does; the formal name for this is the transition model,
specified by a function RESULT (s, a) that returns the state that results from doing action
a in state s. We also use the term successor to refer to any state reachable from a given
state by a single action. For example, we have
RESULT (In (Arad), Go (Zerind)) = In (Zerind). Together, the initial state, actions, and
transition model implicitly define the state space of the problem - the set of all states
reachable from the initial state by any sequence of actions. The state space forms a
directed network or graph in which the nodes are states and the links between nodes are
actions. (The map of Romania shown in Fig. 3.2 below can be interpreted as a state-space
graph if we view each road as standing for two driving actions, one in each direction.) A
path in the state space is a sequence of states connected by a sequence of actions.
d. The goal test, which determines whether a given state is a goal state. Sometimes there is
an explicit set of possible goal states, and the test simply checks whether the given state is
one of them. The agent’s goal in Romania is the singleton set {In(Bucharest)}.
e. A path cost function that assigns a numeric cost to each path. The problem-solving agent
chooses a cost function that reflects its own performance measure. For the agent trying to
get to Bucharest, time is of the essence, so the cost of a path might be its length in
kilometers. The cost of a path is the sum of the costs of the individual actions along the
path. The step cost of taking action a in state s to reach state sꞌ is denoted by c(s, a, sꞌ). The
step costs for Romania are shown in Fig. 3.2. below as route distances. We assume that
step costs are non-negative.

36
Therefore, the shortest path cost to reach the goal is 140 + 80 + 97 + 101 = 418. A solution to a
problem is an action sequence that leads from the initial state to a goal state. Solution quality is
measured by the path cost function, and an optimal solution has the lowest path cost among all
solutions.

3.2.2 Problem Formulation

The model is an abstract mathematical description. The process of removing detail from the
representation is called abstraction.
Example:

✓ Compare the simple state description we have chosen, In(Arad), to an actual cross-country
trip, where the state of the world includes so many things: the traveling companions, the
current radio program, the scenery out of the window, the proximity of law enforcement
officers, the distance to the next rest stop, the condition of the road, the weather, and so on.
All these considerations are left out of our state descriptions because they are irrelevant to the
problem of finding a route to Bucharest.
✓ Also, we must abstract the actions themselves. Besides changing the location of the vehicle
and its occupants, it takes up time, consumes fuel, generates pollution, and changes the agent
considering change in location. Also, turning on the radio, looking out of the window,
slowing down for law enforcement officers, and so on.

37
A model of formulating a given problem into initial state, actions, transition model, goal test, and
path cost are called problem formulation.
3.2.3 Example – Search Problems
Toy Problems vs Real-World Problems
A toy problem is intended to illustrate or exercise various problem-solving methods. It can be
given a concise, exact description and hence is usable by different researchers to compare the
performance of algorithms. A real-world problem is one whose solutions people actually care
about. Such problems tend not to have a single agreed-upon description, but we can give the
general flavor of their formulations.
Toy Problem-1-:
 The Vacuum-World problem. Formulate all the applicable solutions for the problem.

Fig. 3.3. The state space for the vacuum world. Links denote actions: L = Left, R = Right, S = Suck.
The problem is formulated as follows:
a. States - is determined by both the agent location and the dirt locations. The agent is in
one of two locations, each of which might or might not contain dirt. Thus, there are 2 × 22
= 8 possible world states. A larger environment with n locations has n * 2n states.
b. Initial State – is any state can be designated as the initial state.
c. Actions - in this simple environment, each state has just three actions: Left, Right, and
Suck. Larger environments might also include Up and Down.
d. Transition Model - the actions have their expected effects, except that moving Left in
the leftmost square, moving Right in the rightmost square, and Sucking in a clean square
have no effect. The complete state space is shown in Fig. 3.3. above.

38
 e. Goal Test - this check whether all the squares are clean.
f. Path Cost - each step costs 1, so the path cost is the number of steps in the path.
Compared with the real world, this toy problem has discrete locations, discrete dirt, reliable
cleaning, and it never gets any dirtier.
Toy Problem-2-:
 The 8-Puzzle Problem. It consists of a 3×3 board with eight numbered tiles and a blank
space. A tile adjacent to the blank space can slide into the space. The object is to reach a
specified goal state, such as the one shown on the right of the figure below.

Fig. 3.4. A typical instance of the 8-puzzle.

The standard formulation is as follows:
a. States - a state description specifies the location of each of the eight tiles and the blank in
one of the nine squares.
b. Initial State - any state can be designated as the initial state. Note that any given goal can
be reached from exactly half of the possible initial states.
c. Actions - the simplest formulation defines the actions as movements of the blank space
Left, Right, Up, or Down. Different subsets of these are possible depending on where the
blank is.
d. Transition Model - given a state and action, this returns the resulting state; for example,
if we apply Left to the start state in Fig. 3.4., the resulting state has the 5 and the blank
switched.
e. Goal Test - this check whether the state matches the goal configuration shown in Fig. 3.4.
(Other goal configurations are possible.)
f. Path Cost - each step costs 1, so the path cost is the number of steps in the path.
What abstractions have we included here? The actions are abstracted to their beginning and final
states, ignoring the intermediate locations where the block is sliding. We have abstracted away
actions such as shaking the board when pieces get stuck and ruled out extracting the pieces with
a knife and putting them back again.

39
The 8-puzzle belongs to the family of sliding-block puzzles, which are often used as test
problems for new search algorithms in AI. This family is known to be NP-complete, so one does
not expect to find methods significantly better in the worst case than the search algorithms. The
9!
8-puzzle has =181,440 reachable states. The 15-puzzle (on a 4×4 board) has around 1.3
2
trillion states, and random instances can be solved optimally in a few milliseconds by the best
search algorithms. The 24-puzzle (on a 5 × 5 board) has around 1025 states, and random instances
take several hours to solve optimally.
Toy Problem-3-:
 The 8-Queens problem. The goal of this is to place eight queens on a chessboard such
that no queen attacks any other. (A queen attacks any piece in the same row, column or
diagonal.) It is shown in the following Fig. 3.5.

Fig. 3.5. Almost a solution to the 8-queens problem.

Although efficient special-purpose algorithms exist for this problem and for the whole n-queens
family, it remains a useful test problem for search algorithms. There are two main kinds of
formulation.
a. An incremental formulation involves operators that augment the state description,
starting with an empty state; for the 8-queens problem, this means that each action adds a
queen to the state.
b. A complete-state formulation starts with all 8 queens on the board and moves them
around. In either case, the path cost is of no interest because only the final state counts.
The first incremental formulation one might try is the following:
A. States: Any arrangement of 0 to 8 queens on the board is a state.
B. Initial State: No queens on the board.
C. Actions: Add a queen to any empty square.
D. Transition Model: Returns the board with a queen added to the specified square.
E. Goal Test: 8 queens are on the board, none attacked.

40
Real-World Problems:
A. Route-Finding Problems
It is defined in terms of specified locations and transitions along links between them.
Route-finding algorithms are used in a variety of applications. Some, such as Web sites and
in-car systems that provide driving directions. Others, such as routing video streams in computer
networks, military operations planning, and airline travel-planning systems. Consider the airline
travel problems that must be solved by a travel-planning Web site:
i. States - each state obviously includes a location (e.g., an airport) and the current time.
Furthermore, because the cost of an action (a flight segment) may depend on previous
segments, their fare bases, and their status as domestic or international, the state must
record extra information about these “historical” aspects.
ii. Initial State - this is specified by the user’s query.
iii. Actions - take any flight from the current location, in any seat class, leaving after the
current time, leaving enough time for within-airport transfer if needed.
iv. Transition Model - the state resulting from taking a flight will have the flight’s
destination as the current location and the flight’s arrival time as the current time.
v. Goal Test - are we at the final destination specified by the user?
vi. Path Cost - this depends on monetary cost, waiting time, flight time, customs and
immigration procedures, seat quality, time of day, type of airplane, frequent-flyer
mileage awards, and so on.
B. Touring Problems
It is closely related to route-finding problems. Consider, for example, the problem “Visit every
city in Fig. 3.2. above at least once, starting and ending in Bucharest.” As with route finding, the
actions correspond to trips between adjacent cities. The state space, however, is quite different.
Each state must include not just the current location but also the set of cities the agent has visited.
So the initial state would be In(Bucharest), Visited({Bucharest}), a typical intermediate state
would be In(Vaslui), Visited({Bucharest, Urziceni , Vaslui}), and the goal test would check
whether the agent is in Bucharest and all 20 cities have been visited.
C. The Traveling Salesperson Problem (TSP)
It is a touring problem in which each city must be visited exactly once. The aim is to find the
shortest tour. In addition to planning trips for traveling salespersons, these algorithms have been
used for tasks such as planning movements of automatic circuit-board drills and of stocking
machines on shop floors.
Example: Find the shortest path if the initial and goal state is A.

41
Fig. 3.6. Route-finding problems in the world.
Answer:
A, B, C, D, E – five states.
No. Route Path Cost
1. A→B→D→C→E→A 610
2. A→C→B→D→E→A 598 (Shortest path)
3. A→D→B→C→E→A 728
Measuring Problem-Solving Performance
There are basically four measurement of problem-solving performance. They are
a. Completeness - is the algorithm guaranteed to find a solution when there is one?
b. Optimality - does the strategy find the optimal solution, as defined well?
c. Time Complexity - how long does it take to find a solution?
d. Space Complexity - how much memory is needed to perform the search?
Search for Solutions
A solution is an action sequence, so search algorithms work by considering various possible
action sequences. The possible action sequences starting at the initial state form a search tree
with the initial state at the root; the branches are actions and the nodes correspond to states in
the state space of the problem. The following Fig. shows the first few steps in growing the
search tree for finding a route from Arad to Bucharest.

42
Fig. 3.7. Partial search trees for finding a route from Arad to Bucharest. Nodes that have been expanded are shaded;
nodes that have been generated but not yet expanded are outlined in bold; nodes that have not yet been generated are
shown in faint dashed lines.
The root node of the tree corresponds to the initial state, In(Arad). The first step is to test whether
this is a goal state. Then we need to consider taking various actions. We do this by expanding
the current state; that is, applying each legal action to the current state, thereby generating a new
set of states. In this case, we add three branches from the parent node In(Arad) leading to three
new child nodes: In(Sibiu), In(Timisoara), and In(Zerind). Now we must choose which of these
three
possibilities to consider further.
This is the essence of search - following up one option now and putting the others aside for later,
in case the first choice does not lead to a solution. Suppose we choose Sibiu first. We check to see
whether it is a goal state (it is not) and then expand it to get In(Arad), In(Fagaras), In(Oradea),
and In(RimnicuVilcea). We can then choose any of these four or go back and choose Timisoara
or Zerind. Each of these six nodes is a leaf node, that is, a node with no children in the tree. The
set of all leaf nodes available for expansion at any given point is called the frontier (open list).
The frontier of each tree consists of those nodes with bold outlines.

43
The process of expanding nodes on the frontier continues until either a solution is found or there
are no more states to expand. The basic structures that all search algorithms share primarily
according to how they choose which state to expand next is called search-strategy.
The eagle-eyed reader will notice one peculiar thing about the search tree shown in Fig. 3.6. - it
includes the path from Arad to Sibiu and back to Arad again! We say that In(Arad) is a repeated
state in the search tree, generated in this case by a loopy path. Considering such loopy paths
means that the complete search tree for Romania is infinite because there is no limit to how often
one can traverse a loop. Loops can cause certain algorithms to fail, making otherwise solvable
problems unsolvable. Fortunately, there is no need to consider loopy paths. Loopy paths are a
special case of the more general concept of redundant paths, which exist whenever there is more
than one way to get from one state to another.
To do this, we augment the TREE-SEARCH algorithm with a data structure called the explored
set (also known as the closed list), which remembers every expanded node. Newly generated
nodes that match previously generated nodes - ones in the explored set or the frontier - can be
discarded instead of being added to the frontier.

3.2.4 Search Strategies

There are two basic search strategies. They are
a. Uninformed Search Strategies
It is also called blind search. It is the strategies that have no additional information about states
beyond that provided in the problem definition. All they can do is generate successors and
distinguish a goal state from a non-goal state. All search strategies are distinguished by the order
in which nodes are expanded. Simply, there is no domain specific. GPS is an application of the
strategy. Search doesn’t use any specific information regarding the domain to perform search.
Example: Breadth-first search, uniform cost-search, depth-first search, depth-limited search,
iterative depending depth-first search, and bidirectional search.
Breadth-First Search:
 It an algorithm used to expand the shallowest unexpanded state level-wise.
 Its implementation follows queue procedure, i.e., FIFO.
 It is complete.
 It is optimal if all path costs are the same because it always finds the shallowest state first.
Example: Find the goal state 11 using BFS from the following Fig.

44
Fig. 3.8. A tree of level-3.
Answer:1→2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11
Depth-First Search:
 It is an algorithm used to expands the deepest unexpanded state and backtracks it to find
its goal state.
 Its implementation follows a stack procedure, i.e., LIFO.
 It isn’t complete because of infinite depth and loops.
 It isn’t optimal and it uses a pre-order searching strategy, i.e., Root → Left → Right.
Example: Find the goal state 11 using DFS from the above Fig. 3.6.
Answer: 1→2→4→8→9→5→10→11.
Depth-Limited Search:
 It is e depth-first search with a cutoff depth (predetermined limit).
 It isn’t a complete because the goal may be below the cutoff state.
 It isn’t optimal.
 The states at the depth-limit are treated as they had no successors.
Example: Find the goal state 11 using DLS at level-2 from above Fig. 3.8.
Answer: 1→2→4→5→3→6→7
Iterative Deepening DFS (IDDFS):
 It is a DFS with the benefit of BFS.
 On each iteration, it visits the nodes in the search tree in the same order as DFS, but the
cumulative order in which nodes are first visited is BFS.
 It is complete for finite BFS.
 It is optimal in terms of its solutions.
Example: Find the goal state 11 using IDS from the above Fig. 3.8.
Answer:
1st Iteration: 1
2nd Iteration: 1 → 2 → 3

45
 3rd Iteration: 1→2→4→5→3→6→7
4th Iteration: 1→2→4→8→9→5→10→11
Uniform Cost Search:
 It expands the lowest path cost state and much related to BFS.
 Its implementation follows a priority queue, i.e., the lowest path cost state has the highest
priority.
Backward Chaining:
 It is used to run the search backwards from a goal state to start state.
 It works best when the actions are reversible, and the set of goal states is small.
Bi-directional Search:
 It is used to search searches in two directions at the same time (simultaneously), forward
from the start state and backward from the goal state.
 The search stops when search from both directions meet in the middle.
 It works best when the backward search is feasible.
b. Informed Search Strategies
It is also called Heuristic search. One that uses problem-specific knowledge beyond the
definition of the problem itself - can find solutions more efficiently than can an uninformed
strategy. It uses a shortest-path since its cost known. It uses domain specific knowledge.
Example: - Best-First Search, Greedy Best-First Search, A* Search, Memory-Bounded
Heuristic Search (Recursive Best-First Search, Simplified Memory-Bounded A*), etc.
A. Best-First Search:
It is an instance of the general TREE-SEARCH or GRAPH-SEARCH algorithm in which a node
is selected for expansion based on an evaluation function, f(n). The evaluation function is
construed as a cost estimate, so the node with the lowest evaluation is expanded first. The
implementation of best-first graph search is identical to that for uniform-cost search except for
the use of f instead of g to order the priority queue.
Most best-first search algorithms include as a component of f a heuristic function, denoted h(n):
ℎ(𝑛) = 𝑒𝑠𝑡𝑖𝑚𝑎𝑡𝑒𝑑 𝑐𝑜𝑠𝑡 𝑜𝑓 𝑡ℎ𝑒 𝑐ℎ𝑒𝑎𝑝𝑒𝑠𝑡 𝑝𝑎𝑡ℎ 𝑓𝑟𝑜𝑚 𝑡ℎ𝑒 𝑠𝑡𝑎𝑡𝑒 𝑎𝑡 𝑛𝑜𝑑𝑒 𝑛 𝑡𝑜 𝑎 𝑔𝑜𝑎𝑙 𝑠𝑡𝑎𝑡𝑒.
Notice:
 h(n) takes a node as input, but, unlike g(n), it depends only on the state at that node.
It uses the combination of BFS and DFS to find its goal state with a single path. Heuristic
functions are the most common form in which additional knowledge of the problem is imparted
to the search algorithm. For now, we consider the states to be arbitrary, nonnegative,
problem-specific functions, with one constraint: if n is a goal node, then h(n) = 0.

46
Example:
 In the following Fig., one might estimate the cost of the cheapest path from S to E via the
straight-line distance (SLD).

Fig. 3.9. A graph of 8-cities.

Answer:
Steps Expanded State (E) Children of E (C) Explored Set (S) Sorted value
1. [S], is goal? No [A5, B6] [] [A5, B6]
2. [A], is goal? No [Y8, X5] [S] [X5, B6, Y8]
3. [X], is goal? No [E0] [S, A] [E0, B6, Y8]
4. [E], is goal? Yes [] [S, A, X] [B6, Y8]
Therefore, the best path to arrive the goal is [S, A, X, E] and its actual cost is 7. The
performance measurement of the algorithm is incomplete, not optimal and both space and time
complexity are O(bm).
Note:
 A5 means in the table above “state A and its estimated cost is 5”.
B. Greedy Best-First Search (GBFS):
It tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a
solution quickly. Thus, it evaluates nodes by using just the heuristic function:
𝑓(𝑛) = ℎ(𝑛).
Example:
 Consider the Fig. 3.9. above. The straight-line distance heuristic, which we will call hSLD
was used. Find the shortest path if the initial state is S and the goal is E using a GBFS.

47
 Answer:
Steps Expanded States Cost of States Shortest Path Cost Children of Selected State
1. [S], is goal? No 0 0 [A, B]
[A], is goal? No 5
2. 5 [Y, X]
[B], is goal? No 6

3. [Y], is goal? No 8
5 [E]
[X], is goal? No 5
4. [E], is goal? Yes 0 0 []
Therefore, the shortest path, hSLD is S→A→X→E and the actual cost to the goal are 7. Therefore,
the heuristic function should always less than or equal to the actual cost.
The values of hSLD cannot be computed from the problem description itself. Moreover, it takes a
certain amount of experience to know that hSLD is correlated with actual road distances and is,
therefore, a useful heuristic.
For this particular problem, greedy best-first search using hSLD finds a solution without ever
expanding a node that is not on the solution path; hence, its search cost is minimal. This shows
why the algorithm is called “greedy” - at each step it tries to get as close to the goal as it can. Its
performance measurement is incomplete, un-optimal, and time and space complexity are O(bm).
C. A* Search:
It is used for minimizing the total estimated solution cost. The most widely known form of
best-first search is called A∗ search (“A-star search”). It evaluates nodes by combining g(n), the
cost to reach the node, and h(n), the cost to get from the node to the goal:
𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛) .
Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the
cheapest path from n to the goal (heuristic value), we have
𝑓(𝑛) = 𝑒𝑠𝑡𝑖𝑚𝑎𝑡𝑒𝑑 𝑐𝑜𝑠𝑡 𝑜𝑓 𝑡ℎ𝑒 𝑐ℎ𝑒𝑎𝑝𝑒𝑠𝑡 𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛 𝑡ℎ𝑟𝑜𝑢𝑔ℎ 𝑛 .
Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with
the lowest value of g(n) + h(n). It turns out that this strategy is more than just reasonable:
provided that the heuristic function h(n) satisfies certain conditions, A∗ search is both complete
and optimal.
Example:
 By considering Fig. 3.9. above search the shortest path if the initial state is “S” and goal
state is “E” using A* algorithm.

48
Answer: f(n) = g(n) + h(n)
Cycle States Path (g(n)) f(n)
1. Initial State S 0+1 = 1
(S, A) 1+5 = 6
2. Expand “S”
(S, B) 2+6 = 8
(S, A, Y) 1+7+8 = 16
Expand “A”
3. (S, A, X) 1+4+5 = 10
(S, B, C) 2+7+4 = 13
Expand “B”
(S, B, D) 2+1+15 = 18
Expand “Y” (S, A, Y, E) 1+7+3+0 = 11
4. Expand “X” (S, A, X, E) 1+4+2+0 = 7
Expand “C” (S, B, C, E) 2+7+5+0 = 14
Expand “D” (S, B, D, E) 2+1+12+0 = 15
Therefore, the best path to arrive to the goal with an actual cost = “7”. Its performance
measurements are complete, optimal, time and space complexity are O(bm), where b is branching
factor and m is maximum depth.
D. Memory Bounded Heuristic Search:
It is the simplest way to reduce memory requirements for A∗ algorithm. There are basically two
types of memory-bounded heuristic search.
a. Recursive Best-First Search (RBFS)
It is a simple recursive algorithm that attempts to mimic the operation of standard best-first
search, but using only linear space. Its structure is similar to that of a recursive depth-first search,
but rather than continuing indefinitely down the current path, it uses the f limit variable to keep
track of the f-value of the best alternative path available from any ancestor of the current node.
If the current node exceeds this limit, the recursion unwinds back to the alternative path. As the
recursion unwinds, RBFS replaces the f-value of each node along the path with a backed-up
value - the best f-value of its children. In this way, RBFS remembers the f-value of the best leaf
in the forgotten subtree and can therefore decide whether it’s worth re-expanding the subtree at
some later time. RBFS is somewhat more efficient than IDA∗, but still suffers from excessive
node regeneration.
It is an optimal algorithm if the heuristic function h(n) is admissible. Its space complexity is
linear in the depth of the deepest optimal solution, but its time complexity is rather difficult to
characterize: it depends both on the accuracy of the heuristic function and on how often the best
path changes as nodes are expanded. It suffers from using too little memory. It retains more
information in memory, but it uses only linear space: even if more memory were available,
RBFS has no way to make use of it. Because they forget most of what they have done, both
algorithms may end up re-expanding the same states many times over.
Example:

49
  By considering Fig. 3.9. above search the shortest path if the initial state is “S” and goal
state is “E” using RBFS algorithm.
Answer:
Path: S→A→X→E
Path Cost: 7
b. Simplified MA* (SMA*)
It expands the best leaf until memory is full. It cannot add a new node to the search tree without
dropping an old one. SMA∗ always drops the worst leaf node - the one with the highest f-value.
It then backs up the value of the forgotten node to its parent. In this way, the ancestor of a
forgotten subtree knows the quality of the best path in that subtree. With this information, SMA∗
regenerates the subtree only when all other paths have been shown to look worse than the path it
has forgotten. In other way, if all the descendants of a node n are forgotten, then we will not
know which way to go from n, but we will still have an idea of how worthwhile it is to go
anywhere from n.
SMA∗ expands the best leaf and deletes the worst leaf. What if all the leaf nodes have the same
f-value? To avoid selecting the same node for deletion and expansion, SMA∗ expands the newest
best leaf and deletes the oldest worst leaf. These coincide when there is only one leaf, but in that
case, the current search tree must be a single path from root to leaf that fills all of memory. If the
leaf is not a goal node, then even if it is on an optimal solution path, that solution is not reachable
with the available memory. Therefore, the node can be discarded exactly as if it had no
successors.
SMA∗ is complete if there is any reachable solution that is, if d, the depth of the shallowest goal
node, is less than the memory size (expressed in nodes). It is optimal if any optimal solution is
reachable; otherwise, it returns the best reachable solution. In practical terms, SMA∗ is a fairly
robust choice for finding optimal solutions, particularly when the state space is a graph, step
costs are not uniform, and node generation is expensive compared to the overhead of
maintaining the frontier and the explored set.
Example:
 By considering Fig. 3.7. above search the shortest path if the initial state is “S” and goal
state is “E” using SMA* algorithm.
Answer:
Path: S→A→X→E
Path Cost: 7

50
3.2.5 Avoiding Repeated States
In BFS, if the repeated state is in structure of closed (parent) or open state (frontier or child),
the actual path (goal state) has equal or greater depth than the repeated state and can be forgotten.

Fig. 3.10. The repeated state using BFS.

In DFS, if the repeated state is in the structure of closed state, the actual path is kept if its depth
is less than the repeated state. If the repeated state is in the structure of open state, the actual path
has always greater depth than the repeated state and can be forgotten.

Fig. 3.11. The repeated state using DFS.

3.2.6 Constraint Satisfaction Problem (CSP)

A problem can be solved by searching in a space of states. These states can be evaluated by
domain-specific heuristics and tested to see whether they are goal states. From the point of view
of the search algorithm, however, each state is atomic, or indivisible - a black box with no
internal structure. In CSP, the factored representation is used for each state: a set of variables,
each of which has a value. Therefore, CSP is a problem solved when each variable has a value
that satisfies all the constraints on the variable.
CSP search algorithms take advantage of the structure of states and use general-purpose
heuristics to enable the solution of complex problems. The main idea is to eliminate large
portions of the search space all at once by identifying variable/value combinations that violate
the constraints.
A constraint satisfaction problem consists of three components, X, D, and C:

51
Each domain Di consists of a set of allowable values, {v1, . . ., vk} for variable Xi. Each constraint
Ci consists of a pair {scope, rel}, where scope is a tuple of variables that participate in the
constraint and rel is a relation that defines the values that those variables can take on. A relation
can be represented as an explicit list of all tuples of values that satisfy the constraint, or as an
abstract relation that supports two operations: testing if a tuple is a member of the relation and
enumerating the members of the relation.
Example-1-:
a. If X1 and X2 both have the domain {A, B}, then the constraint saying the two variables
must have different values can be written as {(X1, X2), [(A, B), (B, A)]} or as {(X1, X2),
X1 ≠ X2}.
To solve a CSP, we need to define a state space and the notion of a solution. Each state in a CSP
is defined by an assignment of values to some or all of the variables, {Xi = vi, Xj = vj, . . .}. An
assignment that does not violate any constraints is called a consistent or legal assignment. A
complete assignment is one in which every variable is assigned, and a solution to a CSP is a
consistent, complete assignment. A partial assignment is one that assigns values to only some
of the variables.
Example of Constraint Satisfaction Problem:
a. Cryptarithmetic
b. N-Queen
c. Crossword Puzzle
d. Map Coloring
e. Latin Square
f. Sudoku
Map Coloring Problem:
Suppose that at a map of Australia showing each of its states and territories shown in the Fig.
below (a).

52
 Fig. 3.12. (a). The principal states and territories of Australia. (b) The map-coloring problem represented as a
constraint graph.
It is given the task of coloring each region either red, green, or blue in such a way that no
neighboring regions have the same color. To formulate this as a CSP, we define the variables to
be the regions

The domain of each variable is the set Di = {red, green, blue}. The constraints require
neighboring regions to have distinct colors. Since there are nine places where regions border,
there are nine constraints:

Here, using abbreviations; SA ≠ WA is a shortcut for {(SA, WA), SA ≠ WA}, where SA ≠ WA

can be fully enumerated in turn as

There are many possible solutions to this problem, such as

It can be helpful to visualize a CSP as a constraint graph, as shown in Fig. 3.10. (b). The nodes
of the graph correspond to variables of the problem, and a link connects any two variables that
participate in a constraint.
Why formulate a problem as a CSP?
a. The CSPs yield a natural representation for a wide variety of problems; if you already have a
CSP-solving system, it is often easier to solve a problem using it than to design a custom
solution using another search technique.

53
b. A CSP solvers can be faster than state-space searchers because the CSP solver can quickly
eliminate large swatches of the search space. For example, once we have chosen {SA=blue}
in the Australia problem, we can conclude that none of the five neighboring variables can
take on the value blue. Without taking advantage of constraint propagation, a search
procedure would have to consider 35 = 243 assignments for the five neighboring variables;
with constraint propagation we never have to consider blue as a value, so we have only 25 =
32 assignments to look at, a reduction of 87%.
In regular state-space search we can only ask: is this specific state a goal? No? What about this
one? With CSPs, once we find out that a partial assignment is not a solution, we can immediately
discard further refinements of the partial assignment. Furthermore, we can see why the
assignment is not a solution - we see which variables violate a constraint - so we can focus
attention on the variables that matter. As a result, many problems that are intractable for regular
state-space search can be solved quickly when formulated as a CSP.
Variations on the CSP Formalism
The simplest kind of CSP involves variables that have discrete, finite domains. Consider the
CSP examples given above. A discrete domain can be infinite, such as the set of integers or
strings. Therefore, variables can be discrete vs continuous and domains can be finite vs infinite.
There are three types of constraints.
a. Unary Constraint – is the simplest type which restricts the value of a single variable.

‹
Example: Map-Coloring like (SA), SA ≠ green›.

b. Binary Constraint – it relates two variables. Example: SA ≠ NSW. A binary CSP is one
with only binary constraints; it can be represented as a constraint graph, as in Fig. 3.10.
(b).
c. Higher-Order Constraint – it involves three or more variables, such as asserting that
the value of Y is between X and Z, with the ternary constraint Between (X, Y, Z).
A constraint involving an arbitrary number of variables is called a global constraint. One of the
most common global constraints is Alldiff, which says that all of the variables involved in the
constraint must have different values.

3.2.7 Games as Search Problem

 Sudoku Puzzle
In Sudoku problems, all variables in a row or column must satisfy an Alldiff constraint. A
Sudoku board consists of 81 squares, some of which are initially filled with digits from 1 to 9.

54
The puzzle is to fill in all the remaining squares such that no digit appears twice in any row,
column, or 3×3 box. A row, column, or box is called a unit.
A Sudoku puzzle can be considered a CSP with 81 variables, one for each square. We use the
variable names A1 through A9 for the top row (left to right), down to I1 through I9 for the
bottom row. The empty squares have the domain {1, 2, 3, 4, 5, 6, 7, 8, 9} and the prefilled squares
have a domain consisting of a single value. It is shown in Fig. below.

Fig. 3.13. (a) A Sudoku puzzle and (b) its solution.

In addition, there are 27 different Alldiff constraints: one for each row, column, and box of 9
squares.

There are 81 variables, that their domains are the digits 1 to 9, and that there are 27 Alldiff
constraints.

55
Review Questions
1. What do you mean by problem-solving?
2. What are types of problem-solving?
3. What is problem-solving method with example?
4. Why is solving problems important?
5. What are problem-solving steps?
6. What is problem-solving by searching?
7. Why is searching important in problem-solving?
8. What is problem searching in Artificial Intelligence?
9. What are the searching techniques in AI?
10. What do you mean by searching?
11. What are the different types of search algorithms?
12. How do you create a search problem?
13. What is problem formulation?
14. What are components of problem formulation?
15. How do you write a problem formulation?
16. What are the steps of problem-solving in AI?
17. What is the first step in formulating a problem?

56
 Chapter Four: Knowledge and Reasoning
4.1 Logical Agents

This chapter introduces knowledge-based agents. The concepts that we discuss the
representation of knowledge and the reasoning processes that bring knowledge to life are central
to the entire field of artificial intelligence. Humans, it seems, know things and do reasoning.
Knowledge and reasoning are also important for artificial agents because they enable successful
behaviors that would be very hard to achieve otherwise. We have seen that knowledge of action
outcomes enables problemsolving agents to perform well in complex environments. A reflex
agents could only find its way from Arad to Bucharest by dumb luck. The knowledge of
problem-solving agents is, however, very specific and inflexible. A chess program can calculate
the legal moves of its king, but does not know in any useful sense that no piece can be on two
different squares at the same time. Knowledge-based agents can benefit from knowledge
expressed in very general forms, combining and recombining information to suit myriad
purposes. Often, this process can be quite far removed from the needs of the moment as when a
mathematician proves a theorem or an astronomer calculates the earth’s life expectancy.

Knowledge and reasoning also play a crucial role in dealing with partially observable
environments. A knowledge-based agent can combine general knowledge with current percepts
to infer hidden aspects of the current state prior to selecting actions. For example, a physician
diagnoses a patient that is, infers a disease state that is not directly observable prior to choosing a
treatment. Some of the knowledge that the physician uses in the form of rules learned from
textbooks and teachers, and some is in the form of patterns of association that the physician may
not be able to consciously describe. If its inside the physician’s head, it counts as knowledge.

Understanding natural language also requires inferring hidden state, namely, the intention of the
speaker. When we hear, “John saw the diamond through the window and coveted it,” we know
“it” refers to the diamond and not the window we reason, perhaps unconsciously, with our
knowledge of relative value. Similarly, when we hear, “John threw the brick through the window
and broke it,” we know “it” refers to the window. Reasoning allows us to cope with the virtually
infinite variety of utterances using a finite store of commonsense knowledge. Problem-solving
agents have difficulty with this kind of ambiguity because their representation of contingency
problems is inherently exponential.

57
4.2 Knowledge Representation
Humans are best at understanding, reasoning, and interpreting knowledge. Human knows things,
which is knowledge and as per their knowledge they perform various actions in the real
world. But how machines do all these things comes under knowledge representation and
reasoning. Hence we can describe Knowledge representation as following:

✓ Knowledge representation and reasoning (KR, KRR) is the part of Artificial intelligence
which concerned with AI agents thinking and how thinking contributes to intelligent
behavior of agents.
✓ It is responsible for representing information about the real world so that a computer can
understand and can utilize this knowledge to solve the complex real world problems such
as diagnosis a medical condition or communicating with humans in natural language.
✓ It is also a way which describes how we can represent knowledge in artificial intelligence.
Knowledge representation is not just storing data into some database, but it also enables an
intelligent machine to learn from that knowledge and experiences so that it can behave
intelligently like a human.

Following are the kind of knowledge which needs to be represented in AI systems:

✓ Object: All the facts about objects in our world domain. E.g., Guitars contains strings,
trumpets are brass instruments.
✓ Events: Events are the actions which occur in our world.
✓ Performance: It describe behavior which involves knowledge about how to do things.
✓ Meta-knowledge: It is knowledge about what we know.
✓ Facts: Facts are the truths about the real world and what we represent.
✓ Knowledge-Base: The central component of the knowledge-based agents is the knowledge
base. It is represented as KB. The Knowledge base is a group of the Sentences (Here,
sentences are used as a technical term and not identical with the English language).

Knowledge: Knowledge is awareness or familiarity gained by experiences of facts, data, and

situations. Following are the types of knowledge in artificial intelligence:

58
Types of Knowledge
Following are the various types of knowledge:

1. Declarative Knowledge:

✓ Declarative knowledge is to know about something.

✓ It includes concepts, facts, and objects.
✓ It is also called descriptive knowledge and expressed in declarative sentences.
✓ It is simpler than procedural language.

2. Procedural Knowledge

✓ It is also known as imperative knowledge.

✓ Procedural knowledge is a type of knowledge which is responsible for knowing how
to do something.
✓ It can be directly applied to any task.
✓ It includes rules, strategies, procedures, agendas, etc.
✓ Procedural knowledge depends on the task on which it can be applied.

3. Meta-knowledge:

✓ Knowledge about the other types of knowledge is called Meta-knowledge.

4. Heuristic knowledge:

✓ Heuristic knowledge is representing knowledge of some experts in a filed or subject.

✓ Heuristic knowledge is rules of thumb based on previous experiences, awareness of
approaches, and which are good to work but not guaranteed.

5. Structural knowledge:

✓ Structural knowledge is basic knowledge to problem-solving.

✓ It describes relationships between various concepts such as kind of, part of, and
grouping of something.
✓ It describes the relationship that exists between concepts or objects.

4.2.7 Techniques of knowledge representation

There are mainly four ways of knowledge representation which are given as follows:

59
 1. Logical Representation
2. Semantic Network Representation
3. Frame Representation
4. Production Rules

4.2.8 Logical Representation

Logical representation is a language with some concrete rules which deals with propositions and
has no ambiguity in representation. Logical representation means drawing a conclusion based on
various conditions. This representation lays down some important communication rules. It
consists of precisely defined syntax and semantics which supports the sound inference. Each
sentence can be translated into logics using syntax and semantics.

4.2.9 Syntax:
✓ Syntaxes are the rules which decide how we can construct legal sentences in the logic.
✓ It determines which symbol we can use in knowledge representation.
✓ How to write those symbols.

4.2.10 Semantics:
✓ Semantics are the rules by which we can interpret the sentence in the logic.
✓ Semantic also involves assigning a meaning to each sentence.

Logical representation can be categorised into mainly two logics:

1. Propositional Logics
2. Predicate logics

Advantages of logical representation:

✓ Logical representation enables us to do logical reasoning.

✓ Logical representation is the basis for the programming languages.

Disadvantages of logical Representation:

✓ Logical representations have some restrictions and are challenging to work with.
✓ Logical representation technique may not be very natural, and inference may not be so
efficient.

60
4.2.11 Semantic Network Representation

Semantic networks are alternative of predicate logic for knowledge representation. In Semantic
networks, we can represent our knowledge in the form of graphical networks. This network
consists of nodes representing objects and arcs which describe the relationship between those
objects. Semantic networks can categorize the object in different forms and can also link those
objects. Semantic networks are easy to understand and can be easily extended.

This representation consist of mainly two types of relations:

✓ IS-A relation (Inheritance)

✓ Kind-of-relation

Example: Following are some statements which we need to represent in the form of nodes and
arcs.

Statements:

✓ Jerry is a cat.
✓ Jerry is a mammal
✓ Jerry is owned by Priya.
✓ Jerry is brown colored.
✓ All Mammals are animal.

In the above diagram, we have represented the different type of knowledge in the form of nodes
and arcs. Each object is connected with another object by some relation.

61
Drawbacks in Semantic representation:

✓ Semantic networks take more computational time at runtime as we need to traverse the
complete network tree to answer some questions. It might be possible in the worst case
scenario that after traversing the entire tree, we find that the solution does not exist in
this network.
✓ Semantic networks try to model human-like memory (Which has 1015 neurons and
links) to store the information, but in practice, it is not possible to build such a vast
semantic network.
✓ These types of representations are inadequate as they do not have any equivalent
quantifier, e.g., for all, for some, none, etc.
✓ Semantic networks do not have any standard definition for the link names.
✓ These networks are not intelligent and depend on the creator of the system.

Advantages of Semantic network:

✓ Semantic networks are a natural representation of knowledge.

✓ Semantic networks convey meaning in a transparent manner.
✓ These networks are simple and easily understandable.

4.2.12 Frame Representation

A frame is a record like structure which consists of a collection of attributes and its values to
describe an entity in the world. Frames are the AI data structure which divides knowledge into
substructures by representing stereotypes situations. It consists of a collection of slots and slot
values. These slots may be of any type and sizes. Slots have names and values which are called
facets.

Facets: The various aspects of a slot is known as Facets. Facets are features of frames which
enable us to put constraints on the frames. Example: IF-NEEDED facts are called when data of
any particular slot is needed. A frame may consist of any number of slots, and a slot may include
any number of facets and facets may have any number of values. A frame is also known
as slot-filter knowledge representation in artificial intelligence.

Frames are derived from semantic networks and later evolved into our modern-day classes and
objects. A single frame is not much useful. Frames system consist of a collection of frames which
are connected. In the frame, knowledge about an object or event can be stored together in the

62
knowledge base. The frame is a type of technology which is widely used in various applications
including Natural language processing and machine visions.

Example 1: Let's take an example of a frame for a book

Slots Filters
Title Artificial Intelligence
Genre Computer Science
Author Peter Norvig
Edition Third Edition
Year 1996
Page 1152

Example 2: Let's suppose we are taking an entity, Peter. Peter is an engineer as a profession, and
his age is 25, he lives in city London, and the country is England. So following is the frame
representation for this:
Slots Filter
Name Peter
Profession Doctor
Age 25
Marital status Single
Weight 78

Advantages of frame representation:

✓ The frame knowledge representation makes the programming easier by grouping the
related data.
✓ The frame representation is comparably flexible and used by many applications in AI.
✓ It is very easy to add slots for new attribute and relations.
✓ It is easy to include default data and to search for missing values.
✓ Frame representation is easy to understand and visualize.

Disadvantages of frame representation:

✓ In frame system inference mechanism is not be easily processed.

✓ Inference mechanism cannot be smoothly proceeded by frame representation.
✓ Frame representation has a much generalized approach.

4.2.13 Production Rules

Production rules system consist of (condition, action) pairs which mean, "If condition then
action". It has mainly three parts:

63
 ✓ The set of production rules
✓ Working Memory
✓ The recognize-act-cycle

In production rules agent checks for the condition and if the condition exists then production rule
fires and corresponding action is carried out. The condition part of the rule determines which rule
may be applied to a problem. And the action part carries out the associated problem-solving steps.
This complete process is called a recognize-act cycle.

The working memory contains the description of the current state of problems-solving and rule
can write knowledge to the working memory. This knowledge match and may fire other rules.

If there is a new situation (state) generates, then multiple production rules will be fired together,
this is called conflict set. In this situation, the agent needs to select a rule from these sets, and it is
called a conflict resolution.

Example:

✓ IF (at bus stop AND bus arrives) THEN action (get into the bus)
✓ IF (on the bus AND paid AND empty seat) THEN action (sit down).
✓ IF (on bus AND unpaid) THEN action (pay charges).
✓ IF (bus arrives at destination) THEN action (get down from the bus).

Advantages of Production rule:

✓ The production rules are expressed in natural language.

✓ The production rules are highly modular, so we can easily remove, add or modify an
individual rule.

Disadvantages of Production rule:

✓ Production rule system does not exhibit any learning capabilities, as it does not store
the result of the problem for the future uses.
✓ During the execution of the program, many rules may be active hence rule-based
production systems are inefficient.

64
4.3 Propositional Logic
It is a simple knowledge representation language. It works at the sentential level. The sentences
here are called propositions. We do not go within the individual sentences and discuss their
meaning. Propositional logic is unambiguous and is also called Boolean logic as the sentences or
propositions return a true or false value. Further, all other logic like First Order Logic are built on
top of Propositional Logic. For instance: Grass is green,It is Sunday and 2 + 2=4.

These are all valid propositions, whereas: Close the door, Is it Monday today?, x=x are invalid
propositions. Propositional logic (PL) is the simplest form of logic where all the statements are
made by propositions. A proposition is a declarative statement which is either true or false. It is a
technique of knowledge representation in logical and mathematical form

Atomic propositions are simple propositions and Compound propositions are constructed by
combining atomic propositions using logical connectives and parenthesis. For instance, It is
Sunday and it is a holiday. Logical connectives are used in propositional logic to connect two
sentences logically:

Name Symbol Stands for

Conjunction ^ And

Disjunction v Or

Implication ---> If-then

Negation ~ Not

Bi-conditional <---> If and only

Let’s look at this with the help of an example. If it is hot and humid, then it is raining. Here P= It
is hot, Q= It is humid, R=It is raining. This can be represented as: (P ^ Q) → R

Following are some basic facts about propositional logic:

✓ Propositional logic is also called Boolean logic as it works on 0 and 1.

✓ In propositional logic, we use symbolic variables to represent the logic, and we can use any
symbol for a representing a proposition, such A, B, C, P, Q, R, etc.
✓ Propositions can be either true or false, but it cannot be both.
✓ Propositional logic consists of an object, relations or function, and logical connectives.
✓ These connectives are also called logical operators.

65
✓ The propositions and connectives are the basic elements of the propositional logic.
✓ Connectives can be said as a logical operator which connects two sentences.
✓ A proposition formula which is always true is called tautology, and it is also called a valid
sentence.
✓ A proposition formula which is always false is called Contradiction.
✓ A proposition formula which has both true and false values is called
✓ Statements which are questions, commands, or opinions are not propositions such as "Where
is Rohini", "How are you", "What is your name", are not propositions.

Syntax of propositional logic:

The syntax of propositional logic defines the allowable sentences for the knowledge
representation. There are two types of Propositions:
1. Atomic Propositions
2. Compound propositions

o Atomic Proposition: Atomic propositions are the simple propositions. It consists of a

single proposition symbol. These are the sentences which must be either true or false.
Example:
✓ 2+2 is 4, it is an atomic proposition as it is a true fact.
✓ "The Sun is cold" is also a proposition as it is a false fact.

o Compound proposition: Compound propositions are constructed by combining

simpler or atomic propositions, using parenthesis and logical connectives.
Example

✓ a) "It is raining today, and street is wet."

✓ b) "Ankit is a doctor, and his clinic is in Mumbai."

66
Truth Table:

In propositional logic, we need to know the truth values of propositions in all possible scenarios.
We can combine all the possible combination with logical connectives, and the representation of
these combinations in a tabular format is called Truth table. The above list of table is the truth
table for all logical connectives:

Truth table with three propositions:

We can build a proposition composing three propositions P, Q, and R. This truth table is made-up
of 8n Tuples as we have taken three proposition symbols.

67
Precedence of connectives:

Just like arithmetic operators, there is a precedence order for propositional connectors or logical
operators. This order should be followed while evaluating a propositional problem. Following is
the list of the precedence order for operators:
Precedence Operators
First Precedence Parenthesis
Second Precedence Negation
Third Precedence Conjunction(AND)
Fourth Precedence Disjunction(OR)
Fifth Precedence Implication
Six Precedence Biconditional

Logical equivalence:

Logical equivalence is one of the features of propositional logic. Two propositions are said to be
logically equivalent if and only if the columns in the truth table are identical to each other.

Let's take two propositions A and B, so for logical equivalence, we can write it as A⇔B. In below
truth table we can see that column for ¬A∨ B and A→B, are identical hence A is Equivalent to B

Properties of Propositional Logic:

✓ Commutativity :

o P∧ Q= Q ∧ P, or
o P ∨ Q = Q ∨ P.

68
✓ Associativity

o (P ∧ Q) ∧ R= P ∧ (Q ∧ R),
o (P ∨ Q) ∨ R= P ∨ (Q ∨ R)
✓ Distributive property

o P∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R).
o P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R).
✓ DeMorgan’s law

o ¬ (P ∧ Q) = (¬P) ∨ (¬Q)
o ¬ (P ∨ Q) = (¬ P) ∧ (¬Q).
✓ Double negation elimination

o ¬ (¬P) = P.
✓ Identity element

o P ∧ True = P,
o P ∨ True= True.

However, Propositional Logic has limited expressive power. It cannot be used to represent
specializations, generalizations, or patterns. Elements like all, some and none cannot be expressed
using propositional logic. For example, All mushrooms are brown, some grapes are sweet, and
more. There are two components:

Limitations of Propositional logic:

✓ We cannot represent relations like ALL, some, or none with propositional logic. Example:

a) All the girls are intelligent.

b) Some apples are sweet.
✓ Propositional logic has limited expressive power.
✓ In propositional logic, we cannot describe statements in terms of their properties or logical
relationships.

4.3 First-Order logic:

✓ First-order logic is another way of knowledge representation in artificial intelligence. It is an
extension to propositional logic.
✓ FOL is sufficiently expressive to represent the natural language statements in a concise way.

69
✓ First-order logic is also known as Predicate logic or First-order predicate logic.
First-order logic is a powerful language that develops information about the objects in a more
easy way and can also express the relationship between those objects.
✓ First-order logic (like natural language) does not only assume that the world contains facts
like propositional logic but also assumes the following things in the world:

o Objects: A, B, people, numbers, colors, wars, theories, squares, pits, wumpus, ......
o Relations: It can be unary relation such as: red, round, is adjacent, or n-any
relation such as: the sister of, brother of, has color, comes between
o Function: Father of, best friend, third inning of, end of, ......
✓ As a natural language, first-order logic also has two main parts:

c) Syntax
d) Semantics

Syntax of First-Order logic:

The syntax of FOL determines which collection of symbols is a logical expression in first-order
logic. The basic syntactic elements of first-order logic are symbols. We write statements in
short-hand notation in FOL.

Basic Elements of First-order logic:

Following are the basic elements of FOL syntax:

Variables Values
Constant 1, 2, A, John, Mumbai, cat,....
Variables x, y, z, a, b,....
Predicates Brother, Father, >,....
Function sqrt, LeftLegOf, ....
Connectives ∧, ∨, ¬, ⇒, ⇔
Equality ==
Quantifier ∀, ∃

Atomic sentences:
✓ Atomic sentences are the most basic sentences of first-order logic. These sentences are
formed from a predicate symbol followed by a parenthesis with a sequence of terms.
✓ We can represent atomic sentences as Predicate (term1, term2, ......, term n).

Example: Ravi and Ajay are brothers: => Brothers(Ravi, Ajay).

Chinky is a cat: => cat (Chinky).

70
Complex Sentences:
✓ Complex sentences are made by combining atomic sentences using connectives.

First-order logic statements can be divided into two parts:

✓ Subject: Subject is the main part of the statement.

✓ Predicate: A predicate can be defined as a relation, which binds two atoms together in a
statement.

Consider the statement: "x is an integer.", it consists of two parts, the first part x is the subject
of the statement and second part "is an integer," is known as a predicate.

4.4 Predicate (First-Order)Logic

It is another knowledge representation language built on top of propositional logic. It is more
expressive as compared to propositional logic and supports temporal information. It is also called
higher order logic and can support complex statements.

4.4.4 Components

User defines primitives:

✓ Constant symbols- terms with fixed value which belong to the domain. Example: Tara, 2
✓ Function symbols- mapping individuals to individuals. Example: Mary is the mother of Tara.
mother_of(Tara)=Mar
✓ Predicate symbols- mapping individuals to truth values. Example: 4 is greater than 2.
greater(4,2)

FOL supports these primitives:

✓ Variable symbols- x,y

✓ Connectives- conjunction, disjunction, implication, negation, biconditional
✓ Quantifiers

71
A. Universal: It stands for “for all” and is represented by the symbol ∀. It corresponds to
conjunction ‘and.’ Example: All dolphins are mammals. ∀x: dolphin(x) — -> mammal(x)

B. Existential- It stands for “there exists”. It is represented by the symbol ∃ and corresponds to
disjunction ‘or.’ Example: Some mammals lay eggs. ∃x: mammal(x) — -> lay_eggs(x)

C. Equal: X=Y

In predicate logic, a rule has two parts: predecessor and successor. If the predecessor is true, the
successor is true. It uses the implication symbol. It represents if-then type of sentences. Example:
If the bag is of pink color, I will buy it. colour(bag, pink) — — -> buy(bag).

4.5 Inference in First-Order Logic

Inference in First-Order Logic is used to deduce new facts or sentences from existing sentences.
Before understanding the FOL inference rule, let's understand some basic terminologies used in
FOL. It is used for simple problems or arrangement of facts. It is used when the knowledge base
consists of sentences with horn clauses (I.e. disjunction of literals of which at the most one is
positive). Inference means deriving new sentences from old. Inference system allows us to add a
new sentence to the knowledge base. A sentence is a proposition about the world. Inference
system applies logical rules to the KB to deduce new information. Inference system generates
new facts so that an agent can update the KB. An inference system works mainly in two rules
which are given as:

4.5.4 Forward Chaining

It is an inference technique that starts with sentences in the knowledge base and generates new
conclusions that can in turn allow more inferences to be made. It is a data driven approach. We
start with known facts and arrange or chain them in order to reach the query. It uses modus ponens.
It starts with available information and uses inference rules to extract more data until the goal is
reached.

Example 4.1: To conclude color of the pet named Fritz, given that it croaks and eats flies. The
Knowledge Base contains these rules:

✓ If X croaks and eats flies — → Then X is a frog.

✓ If X sings — → Then X is a bird.
✓ If X is a frog — → Then X is green.

72
 ✓ If x is a bird — -> Then X is blue.

Given: Croaks and eats flies is searched in the KB. This leads us to rule 1 as its antecedent
matches our data. The consequent of rule 1 i.e. X is a frog is added to the KB. Now the KB is
searched again and rule 3 is chosen since its antecedent (X is a frog) matches our data that was
just confirmed. Then the new consequent is added to the KB (i.e. X is green). Thus we have
reached the goal of determining color of the pet given than it croaks and eats flies.

4.5.5 Backward Chaining

It is an inference technique that starts from the goal. We find implication sentences that allow us
to conclude the it and attempt to establish its premises. It uses modus ponens backwards. It is a
goal driven approach and is used in theorem proving.

Example 4.2: To conclude color of the pet named Fritz, given that it croaks and eats flies. The
KB contains these rules:

✓ If X croaks and eats flies — → Then X is a frog.

✓ If X sings — → Then X is a bird.
✓ If X is a frog — → Then X is green.
✓ If x is a bird — -> Then X is blue.

The third and forth rules are selected as they match our goal of determining color of the pet. i.e. X
is green or X is blue. Both the antecedents of the rules i.e. X is a frog and X is a bird are added to
the goal list. Then KB is searched again and the first two rules are selected as their consequents
match the new goals added to the list i.e. X is a frog or X is a bird. The antecedent (If X croaks and
eats flies) is true/ given and thus we can conclude than Fritz is a frog. The goal of determining
color of the pet is achieved ( Fritz is green if it is a frog and blue if it is a bird. But it is a frog as it
croaks and eats flies). Thus Fritz is Green.

4.5.6 Substitution:

Substitution is a fundamental operation performed on terms and formulas. It occurs in all

inference systems in first-order logic. The substitution is complex in the presence of quantifiers in
FOL. If we write F[a/x], so it refers to substitute a constant "a" in place of variable "x".

73
Equality: First-Order logic does not only use predicate and terms for making atomic sentences
but also uses another way, which is equality in FOL. For this, we can use equality symbols which
specify that the two terms refer to the same object.

Example: Brother (John) = Smith.

As in the above example, the object referred by the Brother (John) is similar to the object
referred by Smith. The equality symbol can also be used with negation to represent that two terms
are not the same objects.

Example: ￢(x=y) which is equivalent to x ≠y.

4.5.7 FOL inference rules for quantifier:

As propositional logic we also have inference rules in first-order logic, so following are some
basic inference rules in FOL:

✓ Universal Generalization
✓ Universal Instantiation
✓ Existential Instantiation
✓ Existential introduction

1. Universal Generalization:

✓ Universal generalization is a valid inference rule which states that if premise P(c) is true for
any arbitrary element c in the universe of discourse, then we can have a conclusion as ∀ x
P(x).

✓ It can be represented as: .

✓ This rule can be used if we want to show that every element has a similar property.
✓ In this rule, x must not appear as a free variable.
Example: Let's represent, P(c): "A byte contains 8 bits", so for ∀ x P(x) "All bytes contain 8
bits.", it will also be true.

2. Universal Instantiation:

✓ Universal instantiation is also called as universal elimination or UI is a valid inference rule.

It can be applied multiple times to add new sentences.
✓ The new KB is logically equivalent to the previous KB.

74
 ✓ As per UI, we can infer any sentence obtained by substituting a ground term for the variable.
✓ The UI rule state that we can infer any sentence P(c) by substituting a ground term c (a
constant within domain x) from ∀ x P(x) for any object in the universe of discourse.

✓ It can be represented as: .

Example:1. IF "Every person like ice-cream"=> ∀x P(x) so we can infer that

"John likes ice-cream" => P(c)

Example: 2. Let's take a famous example,

"All kings who are greedy are Evil." So let our knowledge base contains this detail as in the form
of FOL:

∀x king(x) ∧ greedy (x) → Evil (x),

So from this information, we can infer any of the following statements using Universal
Instantiation:

✓ King(John) ∧ Greedy (John) → Evil (John),

✓ King(Richard) ∧ Greedy (Richard) → Evil (Richard),
✓ King(Father(John)) ∧ Greedy (Father(John)) → Evil (Father(John)),
3. Existential Instantiation:

✓ Existential instantiation is also called as Existential Elimination, which is a valid inference

rule in first-order logic.
✓ It can be applied only once to replace the existential sentence.
✓ The new KB is not logically equivalent to old KB, but it will be satisfiable if old KB was
satisfiable.
✓ This rule states that one can infer P(c) from the formula given in the form of ∃x P(x) for a
new constant symbol c.
✓ The restriction with this rule is that c used in the rule must be a new term for which P(c ) is
true.

✓ It can be represented as:

Example: From the given sentence: ∃x Crown(x) ∧ OnHead(x, John),

75
So we can infer: Crown(K) ∧ OnHead( K, John), as long as K does not appear in the knowledge
base. The above used K is a constant symbol, which is called Skolem constant. The Existential
instantiation is a special case of Skolemization process.

4. Existential introduction

An existential introduction is also known as an existential generalization, which is a valid

inference rule in first-order logic.

✓ This rule states that if there is some element c in the universe of discourse which has a
property P, then we can infer that there exists something in the universe which has the
property P.

✓ It can be represented as:

✓ Example: Let's say that,
"Priyanka got good marks in English."
"Therefore, someone got good marks in English."

4.5.8 Resolution

It is a type of inference technique. The following steps are executed.

✓ Convert data into logical statements (propositional or predicate logic).

✓ Convert these into Conjunctive Normal form (CNF).
✓ Negate the conclusion.
✓ Resolve using resolution tree.

Example 4.3: If the maid stole the jewellery, then the butler was not guilty. Either the maid stole
the maid stole the jewellery, or she milked the cow. If the maid milked the cow, then the butler got
the cream. Therefore, if the butler was guilty, then he got his cream.

Step1 : Expressing as propositional logic.

✓ P= maid stole the jewellery.

✓ Q= butler is guilty.
✓ R= maid milked the cow.
✓ S= butler got the cream.

76
Step 2: Convert to propositional logic.

✓ P — -> ~Q
✓P v R
✓ R — -> S
✓ Q — -> S (Conclusion)

Step 3: Converting to CNF.

✓ P v ~Q
✓P v R
✓ ~R v S
✓ ~Q v S (Conclusion)

Step 4:

Negate the conclusion: ~(~Q v S) = Q ^ ~S. It is not in CNF due to the presence of ‘^’. Thus we
break it into two parts: Q and ~S. We start with Q and resolve using resolution tree.

Negation of the conclusion gives a null value. Hence our conclusion is proved.

4.6 Knowledge-based Agent

✓ An intelligent agent needs knowledge about the real world for taking decisions
and reasoning to act efficiently.

77
 ✓ Knowledge-based agents are those agents who have the capability of maintaining an
internal state of knowledge, reason over that knowledge, update their knowledge after
observations and take actions. These agents can represent the world with some formal
representation and act intelligently.
✓ Knowledge-based agents are composed of two main parts:

o Knowledge-base and
o Inference system.

A knowledge-based agent must able to do the following:

✓ An agent should be able to represent states, actions, etc.

✓ An agent Should be able to incorporate new percepts
✓ An agent can update the internal representation of the world
✓ An agent can deduce the internal representation of the world
✓ An agent can deduce appropriate actions.

The below diagram is representing a generalized architecture for a knowledge-based agent. The
knowledge-based agent (KBA) take input from the environment by perceiving the environment.
The input is taken by the inference engine of the agent and which also communicate with KB to
decide as per the knowledge store in KB. The learning element of KBA regularly updates the KB
by learning new knowledge.

The architecture of knowledge-based agent:

Knowledge base: Knowledge-base is a central component of a knowledge-based agent, it is also

known as KB. It is a collection of sentences (here 'sentence' is a technical term and it is not

78
identical to sentence in English). These sentences are expressed in a language which is called a
knowledge representation language. The Knowledge-base of KBA stores fact about the world.

Why use a knowledge base?

Knowledge-base is required for updating knowledge for an agent to learn with experiences and
take action as per the knowledge. A knowledge-based agent can be viewed at different levels
which are given below:

1. Knowledge level

Knowledge level is the first level of knowledge-based agent, and in this level, we need to specify
what the agent knows, and what the agent goals are. With these specifications, we can fix its
behavior. For example, suppose an automated taxi agent needs to go from a station A to station B,
and he knows the way from A to B, so this comes at the knowledge level.

2. Logical level:

At this level, we understand that how the knowledge representation of knowledge is stored. At
this level, sentences are encoded into different logics. At the logical level, an encoding of
knowledge into logical sentences occurs. At the logical level we can expect to the automated taxi
agent to reach to the destination B.

3. Implementation level:

This is the physical representation of logic and knowledge. At the implementation level agent
perform actions as per logical and knowledge level. At this level, an automated taxi agent is
actually implemented his knowledge and logic so that he can reach to the destination.

Approaches to designing a knowledge-based agent:

There are mainly two approaches to build a knowledge-based agent:

1. Declarative approach: We can create a knowledge-based agent by initializing with an

empty knowledge base and telling the agent all the sentences with which we want to start
with. This approach is called Declarative approach.
2. Procedural approach: In the procedural approach, we directly encode desired behavior
as a program code. Which means we just need to write a program that already encodes
the desired behavior or agent?

79
However, in the real world, a successful agent can be built by combining both declarative and
procedural approaches, and declarative knowledge can often be compiled into more efficient
procedural code.

Operations Performed by KBA: Following are three operations which are performed by KBA
in order to show the intelligent behavior:

✓ TELL: This operation tells the knowledge base what it perceives from the environment.
✓ ASK: This operation asks the knowledge base what action it should perform.
✓ Perform: It performs the selected action.

An agent makes use of TELL and ASK mechanism. TELL the agent, about surrounding
environment what it needs to know in order to perform some action. TELL mechanism is similar
to taking input for a system.

Then the agent ASKs itself what action should be carried out to get desired output. ASK
mechanism is similar to producing output for a system. However, ASK mechanism makes use of
the knowledge base to decide what it should do.

✓ TELL(K): Is a function that adds knowledge K to the knowledge base.

✓ ASK(K): Is a function that queries the agent about the truth of K.

A generic knowledge-based agent:

Following is the structure outline of a generic knowledge-based agents program:

function KB-AGENT(percept):
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

The knowledge-based agent takes percept as input and returns an action as output. The agent
maintains the knowledge base, KB, and it initially has some background knowledge of the real

80
world. It also has a counter to indicate the time for the whole process, and this counter is
initialized with zero.

Each time when the function is called, it performs its three operations:

✓ Firstly it TELLs the KB what it perceives.

✓ Secondly, it asks KB what action it should take
✓ Third agent program TELLS the KB that which action was chosen.

The MAKE-PERCEPT-SENTENCE generates a sentence as setting that the agent perceived

the given percept at the given time.

The MAKE-ACTION-QUERY generates a sentence to ask which action should be done at the
current time.

4.6.4 Summary
✓ Intelligent agents need knowledge about the world in order to reach good decisions.
✓ Knowledge is contained in agents in the form of sentences in a knowledge
representation language that are stored in a knowledge base.
✓ A knowledge-based agent is composed of a knowledge base and an inference
mechanism. It operates by storing sentences about the world in its knowledge base,
using the inference mechanism to infer new sentences, and using these sentences to
decide what action to take.
✓ A representation language is defined by its syntax, which specifies the structure of
sentences, and its semantics, which defines the truth of each sentence in each possible
world or model.
✓ The relationship of entailment between sentences is crucial to our understanding of
reasoning. A sentence entails another sentence if is true in all worlds where is true.
Equivalent definitions include the validity of the sentence and the unsatisfiability of
the sentence.
✓ Inference is the process of deriving new sentences from old ones. Sound inference
algorithms derive only sentences that are entailed; complete algorithms derive all
sentences that are entailed.
✓ Propositional logic is a simple language consisting of proposition symbols and logical
connectives. It can handle propositions that are known to be true, known to be false, or
completely unknown.

81
✓ The set of possible models, given a fixed propositional vocabulary, is finite, so
entailment can be checked by enumerating models. Efficient model-checking
inference algorithms for propositional logic include backtracking and local search
methods and can often solve large problems quickly.
✓ Inference rules are patterns of sound inference that can be used to find proofs. The
resolution rule yields a complete inference algorithm for knowledge bases that are
expressed in conjunctive normal form. Forward chaining and backward chaining are
very natural reasoning algorithms for knowledge bases in Horn form.
✓ Local search methods such as WALKSAT can be used to find solutions. Such
algorithms are sound but not complete.
✓ Logical state estimation involves maintaining a logical sentence that describes the set
of possible states consistent with the observation history. Each update step requires
inference using the transition model of the environment, which is built from
successorstate axioms that specify how each fluent changes.
✓ Decisions within a logical agent can be made by SAT solving: finding possible models
specifying future action sequences that reach the goal. This approach works only for
fully observable or sensorless environments.
✓ Propositional logic does not scale to environments of unbounded size because it lacks
the expressive power to deal concisely with time, space, and universal patterns of
relationships among objects.

82
 Review Questions
1. What do you mean by knowledge in AI?
2. What is the reasoning in AI?
3. What is knowledge and types of knowledge in AI?
4. What is reasoning in AI explain its types?
5. What is reasoning in machine learning?
6. What are the types of knowledge?
7. Which AI technique uses knowledge and how?
8. What is knowledge represented in AI?
9. What are the types of knowledge representation?
10. What is knowledge representation method?
11. Why is knowledge representation important?
12. How many types of knowledge are there in AI?
13. What are the characteristics of knowledge representation?
14. Which are techniques of AI?
15. What is the known representation?
16. What are the basic components of knowledge-based agents?
17. What do you mean by knowledge base?
18. Why do we use knowledge base in artificial intelligence?
19. What is logical agent and knowledge representation?
20. What are the types of knowledge-based system?
21. What is the importance of knowledge-based system?
22. What is an example of a knowledge base?
23. What are the types of knowledge base in AI?

83
 Chapter Five: Uncertain Knowledge and Reasoning

5.1 Quantifying Uncertainty

Something is that not exactly known or situations involving imperfect or unknown information.
It applies to predictions of future events, to physical measurements that are already made, or to
the unknown.

Till now, we have learned knowledge representation using first-order logic and propositional
logic with certainty, which means we were sure about the predicates. With this knowledge
representation, we might write A→B, which means if A is true then B is true, but consider a
situation where we are not sure about whether A is true or not then we cannot express this
statement, this situation is called uncertainty.

So to represent uncertain knowledge, where we are not sure about the predicates, we need
uncertain reasoning or probabilistic reasoning.

5.2 Causes of uncertainty:

Following are some leading causes of uncertainty to occur in the real world.

✓ Information occurred from unreliable sources.

✓ Experimental Errors.

✓ Equipment fault.

✓ Temperature variation.

✓ Climate change.

5.2.4 Acting under Uncertainty

Agents in the real world need to handle uncertainty, whether due to partial observability,
non-determinism, or adversaries. An agent may never know for sure what state it is in now or
where it will end up after a sequence of actions.

We have seen problem-solving and logical agents handle uncertainty by keeping track of a belief
state a representation of the set of all possible world states that it might be in and generating a
contingency plan that handles every possible eventuality that its sensors may report during
execution. This approach works on simple problems, but it has drawbacks:

✓ The agent must consider every possible explanation for its sensor observations, no matter
how unlikely. This leads to a large belief-state full of unlikely possibilities.

84
✓ A correct contingent plan that handles every eventuality can grow arbitrarily large and must
consider arbitrarily unlikely contingencies.

✓ Sometimes there is no plan that is guaranteed to achieve the goal—yet the agent must act. It
must have some way to compare the merits of plans that are not guaranteed.

Suppose, for example, that an automated taxi has the goal of delivering a passenger to the airport
on time. The taxi forms a plan, A90 , that involves leaving home 90 minutes before the flight
departs and driving at a reasonable speed. Even though the airport is only 5 miles away, a logical
agent will not be able to conclude with absolute certainty that “Plan A90 will get us to the airport
in time.” Instead, it reaches the weaker conclusion “Plan A90 will get us to the airport in time, as
long as the car doesn’t break down, and I don’t get into an accident, and the road isn’t closed, and
no meteorite hits the car, and, none of these conditions can be deduced for sure, so we can’t infer
that the plan succeeds. This is the logical qualification problem (page 241), for which we so far
have seen no real solution.

Nonetheless, in some sense A90 is in fact the right thing to do. What do we mean by this? As we
discussed in Chapter 2 , we mean that out of all the plans that could be executed, A90 is expected
to maximize the agent’s performance measure (where the expectation is relative to the agent’s
knowledge about the environment).

The performance measure includes getting to the airport in time for the flight, avoiding a long,
unproductive wait at the airport, and avoiding speeding tickets along the way. The agent’s
knowledge cannot guarantee any of these outcomes for A , but it can provide some degree of
belief that they will be achieved. 90 Other plans, such as A 180, might increase the agent’s belief
that it will get to the airport on time, but also increase the likelihood of a long, boring wait. The
right thing to do the rational decision therefore depends on both the relative importance of
various goals and the likelihood that, and degree to which, they will be achieved.

5.2.5 Handling uncertain knowledge

In this section, we look more closely at the nature of uncertain knowledge. We will use a simple
diagnosis example to illustrate the concepts involved. Diagnosis whether for medicine,
automobile repair, or whatever is a task that almost always involves uncertainty. If we tried to
build a dental diagnosis system using first-order logic, we might propose rules such as

Vp Symptom (p, Toothache} => Disease (p, Cavity)

The problem is that this rule is wrong. Not all patients with toothaches have cavities; some of
them have gum disease, an abscess, or one of several other problems:

85
Vp Symptom (p, Toothache) => Disease (p, Cavity) V Disease (p, GumDisease) V Disease (p,
Impacted Wisdom)

Unfortunately, in order to make the rule true, we have to add an almost unlimited list of possible
problems. We could try turning the rule into a causal rule:

V/? Disease (p, Cavity) => Symptom (p, Toothache)

But this rule is not right either; not all cavities cause pain. The only way to fix the rule is to make
it logically exhaustive: to augment the left-hand side with all the qualifications required for a
cavity to cause a toothache. Trying to use logic to cope with a domain like medical diagnosis
thus fails for three main reasons:

LAZINESS: It is too much work to list the complete set of antecedents or consequents needed to
ensure an exceptionalness rule and too hard to use such rules, and too hard to use the enormous
rules that result.

THEORETICAL IGNORANCE: Medical science has no complete theory for the domain.

PRACTICAL IGNORANCE: Even if we know all the rules, we might be uncertain about a
particular patient because not all the necessary tests have been or can be run.

The connection between toothaches and cavities is not a strict logical consequence in either
direction. This is typical of the medical domain, as well as most other judgmental domains: law,
business, design, automobile repair, gardening, dating, and so on. The agent’s knowledge
can at best provide only a degree of belief in the relevant sentences. Our main tool for dealing
with degrees of belief is probability theory. The ontological commitments of logic and
probability theory are the same that the world is composed of facts that do or do not hold in any
particular case but the epistemological commitments are different: a logical agent believes each
sentence to be true or false or has no opinion, whereas a probabilistic agent may have a
numerical degree of belief between 0 (for sentences that are certainly false) and 1 (certainly
true).

Probability provides a way of summarizing the uncertainty that comes from our laziness and
ignorance. We may not know for sure what afflicts a particular patient, but we believe that there
is, say, an 80% chance that is, a probability of 0.8 that the patient has a cavity if he or she has a
toothache. This probability could be derived from statistical data 80% of the toothache patients
seen so far have had cavities or from some general rules, or from a combination of evidence
sources. The 80% summarizes those cases in which all the factors needed for a cavity to cause a

86
toothache are present, as well as other cases in which the patient has both toothache and cavity
but the two are unconnected. The missing 20% summarizes all the other possible causes of
toothache that we are too lazy or ignorant to confirm or deny

A probability of 0 for a given sentence corresponds to an unequivocal belief that the sentence is
false, while a probability of 1 corresponds to an unequivocal belief that the sentence is true.
Probabilities between 0 and 1 correspond to intermediate degrees of belief in the truth of the
sentence. The sentence itself is in fact either true or false. It is important to note that a degree of
belief is different from a degree of truth. A probability of 0.8 does not mean "80% true" but
rather an 80% degree of belief—that is, a fairly strong expectation. If an agent assigns a
probability of 0.8 to a sentence, then the agent expects that in 80% of cases that are
indistinguishable from the current situation as far as the agent's knowledge goes, the sentence
will turn out to be actually true. Thus, probability theory makes the same ontological
commitment as logic, namely, that facts either do or do not hold in the world. Degree of truth, as
opposed to degree of belief, is the subject of fuzzy logic.

Before we plunge into the details of probability, let us pause to consider the status of probability
statements such as "The probability that the patient has a cavity is 0.8." In propositional and
first-order logic, a sentence is true or false depending on the interpretation and the world; it is
true just when the fact it refers to is the case. Probability statements do not have quite the same
kind of semantics. This is because the probability that an agent assigns to a proposition depends
on the percepts that it has received to date. In discussing uncertain reasoning, we call this the
evidence. For example, suppose that the agent has drawn a card from a shuffled pack. Before
looking at the card, the agent might assign a probability of 1/52 to its being the ace of spades.
After looking at the card, an appropriate probability for the same proposition would be 0 or 1.
Thus, an assignment of probability to a proposition is analogous to saying whether or not a given
logical sentence (or its negation) is entailed by the knowledge base, rather than whether or not it
is true. Just as entailment status can change when more sentences are added to the knowledge
base, probabilities can change when more evidence is acquired.

All probability statements must therefore indicate the evidence with respect to which the
probability is being assessed. As the agent receives new percepts, its probability assessments are
updated to reflect the new evidence. Before the evidence is obtained, we talk about prior or
unconditional probability; after the evidence is obtained, we talk about posterior or
conditional probability. In most cases, an agent will have some evidence from its percepts, and

87
will be interested in computing the conditional probabilities of the outcomes it cares about given
the evidence it has. In some cases, it will also need to compute conditional probabilities with
respect to the evidence it has plus the evidence it expects to obtain during the course of executing
some sequence of actions.

5.2.6 Uncertainty and rational decisions

To make such choices, an agent must first have preferences between the different possible
outcomes of the various plans. A particular outcome is a completely specified state, including
such factors as whether or not the agent arrives in time, and the length of the wait at the airport.
We will be using utility theory to represent and reason with preferences. The term utility is used
here in the sense of "the quality of being useful," not in the sense of the electric company or
water works. Utility theory says that every state has a degree of usefulness, or utility, to an agent,
and that the agent will prefer states with higher utility.

DECISION THEORY: Preferences, as expressed by utilities, are combined with probabilities

in the general theory of rational decisions called decision theory:

Decision theory = probability theory + utility theory

The fundamental idea of decision theory is that an agent is rational if and only if it chooses \ t:
the action that yields the highest expected utility, averaged over all the possible outcomes of the
action. This is called the principle of Maximum Expected Utility (MEU). Probabilities and
utilities are therefore combined in the evaluation of an action by weighting the utility of a
particular outcome by the probability that it occurs.

5.2.7 Design for a decision-theoretic agent

Figure 5.1: A decision-theoretic agent that selects rational actions. The steps will be fleshed out in the next four
chapters

88
5.3 Probabilistic Reasoning

In which we explain how to build reasoning systems that use network models to reason with
uncertainty according to the laws of probability theory. The main advantage of probabilistic
reasoning over logical reasoning is in allowing the agent to reach rational decisions even when
there is not enough information to prove that any given action will work.

Probabilistic reasoning is a way of knowledge representation where we apply the concept of

probability to indicate the uncertainty in knowledge. In probabilistic reasoning, we combine
probability theory with logic to handle the uncertainty. We use probability in probabilistic
reasoning because it provides a way to handle the uncertainty that is the result of someone's
laziness and ignorance.

In the real world, there are lots of scenarios, where the certainty of something is not confirmed,
such as "It will rain today," "behavior of someone for some situations," "A match between two
teams or two players." These are probable sentences for which we can assume that it will happen
but not sure about it, so here we use probabilistic reasoning.

Need of probabilistic reasoning in AI:

✓ When there are unpredictable outcomes.

✓ When specifications or possibilities of predicates becomes too large to handle.

✓ When an unknown error occurs during an experiment.

In probabilistic reasoning, there are two ways to solve problems with uncertain knowledge:

1 Bayes' rule 2 Bayesian Statistics

As probabilistic reasoning uses probability and related terms, so before understanding
probabilistic reasoning, let's understand some common terms:

Probability: Probability can be defined as a chance that an uncertain event will occur. It is the
numerical measure of the likelihood that an event will occur. The value of probability always
remains between 0 and 1 that represent ideal uncertainties.

✓ 0 ≤ P(A) ≤ 1, where P(A) is the probability of an event A.

✓ P(A) = 0, indicates total uncertainty in an event A.

✓ P(A) =1, indicates total certainty in an event A.

89
We can find the probability of an uncertain event by using the below formula.

✓ P(¬A) = probability of a not happening event.

✓ P(¬A) + P(A) = 1.
Event: Each possible outcome of a variable is called an event.
Sample space: The collection of all possible events is called sample space.
Random variables: Random variables are used to represent the events and objects in the real
world.
Prior probability: The prior probability of an event is probability computed before observing
new information.
Posterior Probability: The probability that is calculated after all evidence or information has
taken into account. It is a combination of prior probability and new information.

5.3.4 Conditional probability:

Conditional probability is a probability of occurring an event when another event has already
happened. Let's suppose, we want to calculate the event A when event B has already occurred,
"the probability of A under the conditions of B", it can be written as:

Where P (A ⋀B) = Joint probability of A and B,

P (B) = Marginal probability of B.
If the probability of A is given and we need to find the probability of B, then it will be given as:

It can be explained by using the below Venn diagram, where B is occurred event, so sample
space will be reduced to set B, and now we can only calculate event A when event B is already
occurred by dividing the probability of P(A ⋀B) by P( B ).

90
Example 5.1: In a class, there are 70% of the students who like English and 40% of the students
who likes English and mathematics, and then what is the percent of students those who like
English also like mathematics?

Solution: Let, A is an event that a student likes Mathematics and B is an event that a student
likes English.

Hence, 57% are the students who like English also like Mathematics.

Probability is a measure of belief. Beliefs need to be updated when new evidence is observed.

The measure of belief in proposition h given proposition B is called the conditional

probability of A given B, written P (A|B) P.

A proposition e representing the conjunction of all of the agent’s observations of the world is
called evidence. Given evidence B, the conditional probability P (A|B) P is the
agent’s posterior probability of B. The probability P (B) is the prior probability of B and is
the same as P (B|true) because it is the probability before the agent has observed anything.

The evidence used for the posterior probability is everything the agent observes about a
particular situation. Everything observed, and not just a few select observations, must be
conditioned on to obtain the correct posterior probability.

Example 5.2: For the diagnostic assistant, the prior probability distribution over possible
diseases is used before the diagnostic agent finds out about the particular patient. Evidence is
obtained through discussions with the patient, observing symptoms, and the results of lab tests.
Essentially any information that the diagnostic assistant finds out about the patient is evidence.
The assistant updates its probability to reflect the new evidence in order to make informed
decisions.

Example 5.3: The information that the delivery robot receives from its sensors is its evidence.
When sensors are noisy, the evidence is what is known, such as the particular pattern received by
the sensor, not that there is a person in front of the robot. The robot could be mistaken about what
is in the world but it knows what information it received.

91
5.3.5 Semantics of Conditional Probability

Evidence e, where e is a proposition, will rule out all possible worlds that are incompatible
with e. Like the definition of logical consequence, the given proposition e selects the possible
worlds in which e is true. As in the definition of probability, we first define the conditional
probability over worlds, and then use this to define a probability over propositions.

Evidence e induces a new probability P(w|e) of world w given e. Any world where e is false has
conditional probability 0, and the remaining worlds are normalized so that the probabilities of
the worlds sum to 1:

Where c is a constant (that depends on e) that ensures the posterior probability of all worlds
sums to 1. For P(w|e) to be a probability measure over worlds for each e:

Therefore, c=1/P(e)c=1/P. Thus, the conditional probability is only defined if P(e)>0P. This is
reasonable, as if P (e) =0P, e is impossible. The conditional probability of proposition h given
evidence e is the sum of the conditional probabilities of the possible worlds in which h is true.
That is,

92
The last form above is typically given as the definition of conditional probability. Here we have
derived it as a consequence of a more basic definition.

5.3.6 Axioms for Probability

The preceding section gave a semantic definition of probability. We can also give an axiomatic
definition of probability that specifies axioms of what properties we may want in a calculus of
belief. Suppose P is a function from propositions into real numbers that satisfies the following
three axioms of probability:
Axiom 1
0 ≤ P (α) for any proposition α. That is, the belief in any proposition cannot be negative.
All probabilities are between 0 and 1, for any proposition α:
✓ 0 < P (α) < 1
Axiom 2
P (τ) = 1 if τ is a tautology. That is, if τ is true in all possible worlds, its probability is 1.
That means P (true) = 1 P (false) = 0
Axiom 3
P(α∨β)=P(α)+P(β) if α and β are contradictory propositions; that is, if ¬(α∧β) is a
tautology. In other words, if two propositions cannot both be true (they are mutually
exclusive), the probability of their disjunction is the sum of their probabilities

These axioms are meant to be intuitive properties that we would like to have of any reasonable
measure of belief. If a measure of belief follows these intuitive axioms, it is covered by
probability theory, whether or not the measure is derived from actual frequency counts. These
axioms form a sound and complete axiomatization of the meaning of probability. Soundness
means that probability, as defined by the possible-worlds semantics, follows these axioms.
Completeness means that any system of beliefs that obeys these axioms has a probabilistic
semantics.

If there are a finite number of finite discrete random variables, Axioms 1, 2, and 3 are sound and
complete with respect to the semantics. It is easy to check that these axioms are true of the
semantics. In the other way around, you can use the axioms to compute any probability from the
probability of worlds, because the descriptions of two worlds are mutually exclusive. The full
proof is left as an exercise.

The following hold for all propositions α and β:

1. Negation of a proposition: P (¬α) =1-P(α).

2. If α↔β, then P (α) =P (β). That is, logically equivalent propositions have the same
probability.
3. Reasoning by cases: P(α)=P(α∧β)+P(α∧¬β).

93
 4. If V is a random variable with domain D, then, for all propositions α,
P(α)=∑d ∈ DP(α∧V=d).

5. Disjunction for non-exclusive propositions: P (α∨ β)=P(α)+P(β)-P(α∧β).

Proof
a. The propositions α∨ ¬α and ¬(α∧¬α) are tautologies. Therefore, 1=P(α∨ ¬α)
=P(α)+P( ¬α). Rearranging gives the desired result.
b. If α↔β, then α∨ ¬β is a tautology, so P(α∨ ¬β)=1. α and ¬β are contradictory
statements, so we can use Axiom 3 to give P(α∨ ¬β)=P(α)+P(¬β).
c. Using part (a), P(¬β)=1-P(β). Thus, P(α)+1-P(β)=1, and so P(α)=P(β).
d. The proposition α↔((α∧β)∨ (α∧¬β)) and ¬((α∧β)∧(α∧¬β)) are tautologies.
Thus, P(α)=P((α∧β)∨ (α∧¬β))=P(α∧β)+P(α∧¬β).
e. The proof is analogous to the proof of part (c). (α∨ β) ↔((α∧¬β)∨ β) is a tautology.
Thus,

P(α∨ β) = P((α∧¬β)∨ β)

= P(α∧¬β)+P(β).
Part (c) shows P(α∧¬β)= P(α) -P(α∧β). Thus,
P(α∨ β) = P(α)-P(α∧β)+P(β).

5.3.7 Bayes’ Rule

An agent using probability updates its belief when it observes new evidence. A new piece of
evidence is conjoined to the old evidence to form the complete set of evidence. Bayes’ rule
specifies how an agent should update its belief in a proposition based on a new piece of evidence.

Suppose an agent has a current belief in proposition h based on evidence k already observed,
given by P(h|k)P and subsequently observes e. Its new belief in hh is P(h|e∧k)P. Bayes’ rule
tells us how to update the agent’s belief in hypothesis h as new evidence arrives.
Proposition 5.3.4: (Bayes’ rule) as long as P (e|k) ≠0,

This is often written with the background knowledge k implicit. In this case, if P(e)≠0, then

94
The theorem follows from dividing the right-hand sides by P(e|k), which is not 0 by assumption.
Often, Bayes’ rule is used to compare various hypotheses (different his). The
denominator P(e|k) is a constant that does not depend on the particular hypothesis, and so when
comparing the relative posterior probabilities of hypotheses, the denominator can be ignored.

To derive the posterior probability, the denominator may be computed by reasoning by cases.
If H is an exclusive and covering set of propositions representing all possible hypotheses, then

Thus, the denominator of Bayes’ rule is obtained by summing the numerators for all the
hypotheses. When the hypothesis space is large, computing the denominator is computationally
difficult. Generally, one of P(e|h∧k) or P(h|e∧k) is much easier to estimate than the other.
Bayes’ rule is used to compute one from the other.
Example 5.4
In medical diagnosis, the doctor observes a patient’s symptoms, and would like to know the
likely diseases. Thus the doctor would like P(Disease/Symptoms). This is difficult to assess as it
depends on the context (e.g., some diseases are more prevalent in hospitals). It is typically more
easy to assess P(Disease/Symptoms). as how the disease gives rise to the symptoms is typically
less context dependent. These two are related by Bayes’ rule, where the prior probability of the
disease, P(Disease), reflects the context.

5.3.8 Probabilistic Inference

The most common probabilistic inference task is to compute the posterior distribution of a query
variable or variables given some evidence. The main approaches for probabilistic inference in
belief networks are:

[Link] Exact inference

Where the probabilities are computed exactly, a simple way is to enumerate the worlds that are
consistent with the evidence. It is possible to do much better than this by exploiting the structure
of the network. The variable elimination algorithm is an exact algorithm that uses dynamic
programming and exploits conditional independence.

95
[Link] Approximate inference

Where probabilities are only approximated, these methods are characterized by the different
guarantees they provide:
✓ They produce guaranteed bounds on the probabilities.
✓ They produce probabilistic bounds on the error produced.
✓ They could make a best effort to produce an approximation that may be good enough,
even though there may be cases where they do not work very well. One such class of
techniques is called variational inference, where the idea is to find an approximation to
the problem that is easy to compute.

5.4 Probabilistic Reasoning over Time

Agents in partially observable environments must be able to keep track of the current state, to the
extent that their sensors allow. In Text book Section 4.4 we showed a methodology for doing that:
an agent maintains a belief state that represents which states of the world are currently possible.
From the belief state and a transition model, the agent can predict how the world might evolve in
the next time step. . From the percepts observed and a sensor model, the agent can update the
belief state. This is a pervasive idea: in Text book Chapter 4 belief states were represented by
explicitly enumerated sets of states, whereas in Text book Chapters 7 and 11 they were
represented by logical formulas. Those approaches defined belief states in terms of which world
states were possible, but could say nothing about which states were likely or unlikely. In this
chapter, we use probability theory to quantify the degree of belief in elements of the belief state.
As we show in Section 5.4.1, time itself is handled in the same way as in Text book Chapter 7 : a
changing world is modeled using a variable for each aspect of the world state at each point in
time. The transition and sensor models may be uncertain: the transition model describes the
probability distribution of the variables at time, given the state of the world at past times, while
the sensor model describes the probability of each percept at time, given the current state of the
world. Section 5.4.2 defines the basic inference tasks and describes the general structure of
inference algorithms for temporal models. Then we describe three specific kinds of models:
hidden Markov models, Kalman filters, and dynamic Bayesian networks (which include hidden
Markov models and Kalman filters as special cases).

5.4.4 Time and Uncertainty

We have developed our techniques for probabilistic reasoning in the context of static worlds, in
which each random variable has a single fixed value. For example, when repairing a car, we

96
assume that whatever are broken remains broken during the process of diagnosis; our job is to
infer the state of the car from observed evidence, which also remains fixed.

Now consider a slightly different problem: treating a diabetic patient. As in the case of car repair,
we have evidence such as recent insulin doses, food intake, blood sugar measurements, and other
physical signs. The task is to assess the current state of the patient, including the actual blood
sugar level and insulin level. Given this information, we can make a decision about the patient’s
food intake and insulin dose. Unlike the case of car repair, here the dynamic aspects of the
problem are essential. Blood sugar levels and measurements thereof can change rapidly over
time, depending on recent food intake and insulin doses, metabolic activity, the time of day, and
so on. To assess the current state from the history of evidence and to predict the outcomes of
treatment actions, we must model these changes.

The same considerations arise in many other contexts, such as tracking the location of a robot,
tracking the economic activity of a nation, and making sense of a spoken or written sequence of
words. How can dynamic situations like these be modeled?

5.4.5 Bayesian Network

Bayesian belief network is key computer technology for dealing with probabilistic events and to
solve a problem which has uncertainty. We can define a Bayesian network as:

"A Bayesian network is a probabilistic graphical model which represents a set of variables and
their conditional dependencies using a directed acyclic graph."
It is also called a Bayes network, belief network, decision network, or Bayesian model.
Bayesian networks are probabilistic, because these networks are built from a probability
distribution, and also use probability theory for prediction and anomaly detection.
Real world applications are probabilistic in nature, and to represent the relationship between
multiple events, we need a Bayesian network. It can also be used in various tasks
including prediction, anomaly detection, diagnostics, automated insight, reasoning, time
series prediction, and decision making under uncertainty.
Bayesian Network can be used for building models from data and experts opinions, and it
consists of two parts:
✓ Directed Acyclic Graph
✓ Table of conditional probabilities.

97
The generalized form of Bayesian network that represents and solve decision problems under
uncertain knowledge is known as an Influence diagram. A Bayesian network graph is made up of
nodes and Arcs (directed links), where:

✓ Each node corresponds to the random variables, and a variable can

be continuous or discrete.
✓ Arc or directed arrows represent the causal relationship or conditional probabilities
between random variables. These directed links or arrows connect the pair of nodes in the
graph.
These links represent that one node directly influence the other node, and if there is no
directed link that means that nodes are independent with each other

o In the above diagram, A, B, C, and D are random variables represented by the

nodes of the network graph.
o If we are considering node B, which is connected with node A by a directed
arrow, then node A is called the parent of Node B.
o Node C is independent of node A.

The Bayesian network has mainly two components:

✓ Causal Component
✓ Actual numbers
Each node in the Bayesian network has condition probability distribution P(Xi |Parent(Xi) ),
which determines the effect of the parent on that node.
Bayesian network is based on Joint probability distribution and conditional probability. So let's
first understand the joint probability distribution:
Let's understand the Bayesian network through an example by creating a directed acyclic graph:
Example 5.5:
Harry installed a new burglar alarm at his home to detect burglary. The alarm reliably responds
at detecting a burglary but also responds for minor earthquakes. Harry has two neighbors David
and Sophia, who have taken a responsibility to inform Harry at work when they hear the alarm.

98
David always calls Harry when he hears the alarm, but sometimes he got confused with the
phone ringing and calls at that time too. On the other hand, Sophia likes to listen to high music,
so sometimes she misses to hear the alarm. Here we would like to compute the probability of
Burglary Alarm.
Problem:
Calculate the probability that alarm has sounded, but there is neither a burglary, nor an
earthquake occurred, and David and Sophia both called the Harry.
Solution:
✓ The Bayesian network for the above problem is given below. The network structure is
showing that burglary and earthquake is the parent node of the alarm and directly
affecting the probability of alarm's going off, but David and Sophia's calls depend on
alarm probability.
✓ The network is representing that our assumptions do not directly perceive the burglary
and also do not notice the minor earthquake, and they also not confer before calling.
✓ The conditional distributions for each node are given as conditional probabilities table or
CPT.
✓ Each row in the CPT must be sum to 1 because all the entries in the table represent an
exhaustive set of cases for the variable.
✓ In CPT, a boolean variable with k boolean parents contains 2K probabilities. Hence, if
there are two parents, then CPT will contain 4 probability values
List of all events occurring in this network:
✓ Burglary (B)
✓ Earthquake(E)
✓ Alarm(A)
✓ David Calls(D)
✓ Sophia calls(S)
We can write the events of problem statement in the form of probability: P[D, S, A, B, E], can
rewrite the above probability statement using joint probability distribution:
P[D, S, A, B, E]= P[D | S, A, B, E]. P[S, A, B, E]
=P[D | S, A, B, E]. P[S | A, B, E]. P[A, B, E]
= P [D| A]. P [ S| A, B, E]. P[ A, B, E]
= P[D | A]. P[ S | A]. P[A| B, E]. P[B, E]
= P[D | A ]. P[S | A]. P[A| B, E]. P[B |E]. P[E]

99
100
Let's take the observed probability for the Burglary and earthquake component:
P(B= True) = 0.002, which is the probability of burglary.
P(B= False)= 0.998, which is the probability of no burglary.
P(E= True)= 0.001, which is the probability of a minor earthquake
P(E= False)= 0.999, Which is the probability that an earthquake not occurred.
We can provide the conditional probabilities as per the below tables:
Conditional probability table for Alarm A:
The Conditional probability of Alarm A depends on Burglar and earthquake:
B E P(A= True) P(A= False)
True True 0.94 0.06
True False 0.95 0.04
False True 0.31 0.69
False False 0.001 0.999
Conditional probability table for David Calls:
The Conditional probability of David that he will call depends on the probability of Alarm.
A P(D= True) P(D= False)
True 0.91 0.09
False 0.05 0.95
Conditional probability table for Sophia Calls:
The Conditional probability of Sophia that she calls is depending on its Parent Node "Alarm."
A P(S= True) P(S= False)
True 0.75 0.25
False 0.02 0.98
From the formula of joint distribution, we can write the problem statement in the form of
probability distribution:
P(S, D, A, ¬B, ¬E) = P (S|A) *P (D|A)*P (A|¬B ^ ¬E) *P (¬B) *P (¬E).
= 0.75* 0.91* 0.001* 0.998*0.999
= 0.00068045.
Hence, a Bayesian network can answer any query about the domain by using Joint distribution.
The semantics of Bayesian Network:
There are two ways to understand the semantics of the Bayesian network, which is given below:
1. To understand the network as the representation of the Joint probability distribution.

1
It is helpful to understand how to construct the network.
2. To understand the network as an encoding of a collection of conditional independence
statements.

5.5 Making Simple Decisions

5.5.4 The Basis of Utility Theory

Intuitively, the principle of Maximum Expected Utility (MEU) seems like a reasonable way to
make decisions, but it is by no means obvious that it is the only rational way. After all, why should
maximizing the average utility be so special? What’s wrong with an agent that maximizes the
weighted sum of the cubes of the possible utilities, or tries to minimize the worst possible loss?
Could an agent act rationally just by expressing preferences between states, without giving them
numeric values? Finally, why should a utility function with the required properties exist at all? We
shall see.

[Link] Constraints on Rational Preferences

These questions can be answered by writing down some constraints on the preferences that a
rational agent should have and then showing that the MEU principle can be derived from the
constraints. We use the following notation to describe an agent’s preferences:
✓ A ≻ B the agent prefers A over B.
✓ A ~ B the agent is indifferent between A and B.
✓ A ≻ B the agent prefers A over B or is indifferent between them.

We can think of the set of outcomes for each action as a lottery—think of each action as a ticket. A
lottery with possible outcomes that occur with probabilities is written
✓ L = [p1, S1; p2, S2; … pn, Sn].

In general, each outcome of a lottery can be either an atomic state or another lottery. The primary
issue for utility theory is to understand how preferences between complex lotteries are related to
preferences between the underlying states in those lotteries. To address this issue we list six
constraints that we require any reasonable preference relation to obey:

ORDERABILITY: Given any two lotteries, a rational agent must either prefer one or else rate
them as equally preferable. That is, the agent cannot avoid deciding.

2
 Exactly one of (A ≻ B), (B ≻ A), or (A ∼ B) holds

TRANSITIVITY: Given any three lotteries, if an agent prefers to and prefers A to B and prefer B
to C, then the agent must prefer A to C. (A ≻ B)∧ (B≻C) ⇒ (A≻C) .

CONTINUITY: If some lottery B is between A and C in preference, then there is some

probability p for which the rational agent will be indifferent between getting B for sure and the
lottery that yields A with probability p and C with probability 1-p.

A ≻ B ≻ C ⇒ ∃ p  [p, A; 1 − p, C] ~B

SUBSTITUTABILITY: If an agent is indifferent between two lotteries, A and B , then the agent
is indifferent between two more complex lotteries that are the same except that B is substituted for
A in one of them. This holds regardless of the probabilities and the other outcome(s) in the
lotteries.

A ~ B ⇒ [p, A; 1 − p, C] ~ [p, B; 1 − p, C] . This also holds if we substitute for in this axiom.

MONOTONICITY: Suppose two lotteries have the same two possible outcomes, A and B. If an
agent prefers A to B , then the agent must prefer the lottery that has a higher probability for A (and
vice versa). A ≻B ⇒ (p > q   ⇔   [p, A; 1 − p, B] ≻ [q, A; 1 − q, B]).

DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of
probability. [p, A; 1 − p, [q, B; 1 − q, C]] ~ [p, A; (1 − p)q, B; (1 − p)(1 − q), C]. These
constraints are known as the axioms of utility theory. Each axiom can be motivated by showing
that an agent that violates it will exhibit patently irrational behavior in some situations. Suppose
that the agent has the nontransitive preferences A ≻ B ≻ C ≻ A, where A, B, and C are goods that
can be freely exchanged. If the agent currently has A, then we could offer to trade A for C plus one
cent. The agent prefers C , and so would be willing to make this trade. We could then offer to trade
A for B, extracting another cent, and finally trade A for B. This brings us back where we started
from; except that the agent has given us three cents (Figure 16.1 (a)). We can keep going around
the cycle until the agent has no money at all. Clearly, the agent has acted irrationally in this case.

3
[Link] Rational preferences lead to utility

Notice that the axioms of utility theory are really axioms about preferences—they say nothing
about a utility function . But in fact from the axioms of utility we can derive the following
consequences.

EXISTENCE OF UTILITY FUNCTION: If an agent’s preferences obey the axioms of utility,

then there exists a function U such that U(A) > U(B) if and only if A is preferred to B , and U(A)
= U(B) if and only if the agent is indifferent between A and B. That is,

U(A) > U(B)     A≻B and U(A) = U(B)      A ~ B

EXPECTED UTILITY OF A LOTTERY: The utility of a lottery is the sum of the probability of
each outcome times the utility of that outcome.

4
As in game-playing, in a deterministic environment an agent needs only a preference ranking on
states the numbers don’t matter. This is called a value function or ordinal utility function.

The preceding theorems establish that (assuming the constraints on rational preferences) a utility
function exists for any rational agent. The theorems do not establish that the utility function is
unique. It is easy to see, in fact, that an agent’s behavior would not change if its utility function U(S)
were transformed according to

U’ (S) = aU(S) + b

5.5.5 Utility Functions

Utility functions map from lotteries to real numbers. We know they must obey the axioms of
orderability, transitivity, continuity, substitutability, monotonicity, and decomposability. Is that all
we can say about utility functions? Strictly speaking, that is it: an agent can have any preferences it
likes. For example, an agent might prefer to have a prime number of dollars in its bank account; in
which case, if it had $16 it would give away $3. This might be unusual, but we can’t call it
irrational. An agent might prefer a dented 1973 Ford Pinto to a shiny new Mercedes. The agent
might prefer prime numbers of dollars only when it owns the Pinto, but when it owns the Mercedes,
it might prefer more dollars to fewer. Fortunately, the preferences of real agents are usually more
systematic and thus easier to deal with.

[Link] Utility assessment and utility scales

If we want to build a decision-theoretic system that helps a human make decisions or acts on his or
her behalf, we must first work out what the human’s utility function is. This process, often called
preference elicitation, involves presenting choices to the human and using the observed
preferences to pin down the underlying utility function.

[Link] The utilities and money

Utility theory has its roots in economics, and economics provides one obvious candidate for a
utility measure: money (or more specifically, an agent’s total net assets). The almost universal

5
exchangeability of money for all kinds of goods and services suggests that money plays a
significant role in human utility functions. It will usually be the case that an agent prefers more
money to less, all other things being equal. We say that the agent exhibits a monotonic preference
for more money. This does not mean that money behaves as a utility function, because it says
nothing about preferences between lotteries involving money.

Suppose you have triumphed over the other competitors in a television game show. The host now
offers you a choice: either you can take the $1,000,000 prize or you can gamble it on the flip of a
coin. If the coin comes up heads, you end up with nothing, but if it comes up tails, you get
2,500,000. If you’re like most people, you would decline the gamble and pocket the million. Are
you being irrational?

Assuming the coin is fair, the expected monetary value (EMV) of the gamble is

, which is more than the original $1,000,000. But that does not necessarily mean that accepting the
gamble is a better decision. Suppose we use Sn to denote the state of possessing total wealth $n,
and that your current wealth is $k. Then the expected utilities of the two actions of accepting and
declining the gamble are

6
5.5.6 Multi-attribute Utility Functions

Decision making in the field of public policy involves high stakes, in both money and lives. For
example, in deciding what levels of harmful emissions to allow from a power plant, policy makers
must weigh the prevention of death and disability against the benefit of the power and the
economic burden of mitigating the emissions. Picking a site for a new airport requires
consideration of the disruption caused by construction; the cost of land; the distance from centers
of population; the noise of flight operations; safety issues arising from local topography and
weather conditions; and so on. Problems like these, in which outcomes are characterized by two or
more attributes, are handled by multi-attribute utility theory. In essence, it’s the theory of
comparing apples to oranges.

Example: The attributes in the airport problem could be:

✓ THROUGHPUT, measured by the number of flights per day

✓ SAFETY, measured by minus the expected number of deaths per year;
✓ QUIETNESS, measured by minus the number of people living under the flight paths;

7
 ✓ FRUGALITY, measured by the negative cost of construction.

5.5.7 Decision Networks

In this section, we look at a general mechanism for making rational decisions. The notation is often
called an influence diagram, but we will use the more descriptive term decision network. Decision
networks combine Bayesian networks with additional node types for actions and utilities. We use
the problem of picking an airport site as an example.

➢ Representing a decision problem with a decision network: In its most general form, a decision
network represents information about the agent’s current state, its possible actions, the state
that will result from the agent’s action, and the utility of that state.
✓ Chance nodes (ovals) represent random variables, just as they do in Bayesian networks. The
agent could be uncertain about the construction cost, the level of air traffic and the potential
for litigation, and the Safety, Quietness, and total Frugality variables, each of which also
depends on the site chosen. Each chance node has associated with it a conditional
distribution that is indexed by the state of the parent nodes. In decision networks, the parent
nodes can include decision nodes as well as chance nodes. Note that each of the current-state
chance nodes could be part of a large Bayesian network for assessing construction costs, air
traffic levels, or litigation potentials.
✓ Decision nodes (rectangles) represent points where the decision maker has a choice of actions.
In this case, the AirportSite action can take on a different value for each site under
consideration. The choice influences the safety, quietness, and frugality of the solution. In
this chapter, we assume that we are dealing with a single decision node.
✓ Utility nodes (diamonds) represent the agent’s utility function. The utility node has as parents
all variables describing the outcomes that directly affect utility. Associated with the utility
node is a description of the agent’s utility as a function of the parent attributes. The
description could be just a tabulation of the function, or it might be a parameterized additive
or linear function of the attribute values. For now, we will assume that the function is
deterministic; that is, given the values of its parent variables, the value of the utility node is
fully determined.

8
A simplified form is also used in many cases. The notation remains identical, but the chance nodes
describing the outcome states are omitted. Instead, the utility node is connected directly to the
current-state nodes and the decision node. In this case, rather than representing a utility function on
outcome states, the utility node represents the expected utility associated with each action, as
defined in Equation (16.1) on page 529 (text book); that is, the node is associated with an
action-utility function (also known as a Q-function in reinforcement learning, as described in Text
Book Chapter 22 ). Figure 16.7 shows the action-utility representation of the airport sitting
problem.

9
➢ Evaluating decision networks: Actions are selected by evaluating the decision network for
each possible setting of the decision node. Once the decision node is set, it behaves exactly like
a chance node that has been set as an evidence variable. The algorithm for evaluating decision
networks is the following:
✓ Set the evidence variables for the current state.
✓ For each possible value of the decision node:
a. Set the decision node to that value.
b. Calculate the posterior probabilities for the parent nodes of the utility node,
using a standard probabilistic inference algorithm.
c. Calculate the resulting utility for the action.
✓ Return the action with the highest utility

5.5.8 Value of information

This section describes information value theory, which enables an agent to choose what
information to acquire. We assume that prior to selecting a “real” action represented by the
decision node; the agent can acquire the value of any of the potentially observable chance variables
in the model. Thus, information value theory involves a simplified form of sequential decision
making simplified because the observation actions affect only the agent’s belief state, not the
external physical state. The value of any particular observation must derive from the potential to
affect the agent’s eventual physical action; and this potential can be estimated directly from the
decision model itself.

10
5.6 Making Complex Decisions

In this topic, we address the computational issues involved in making decisions in a stochastic
environment. Making simple Decision was concerned with one-shot or episodic decision
problems, in which the utility of each action’s outcome was well known, we are concerned here
with sequential decision problems, in which the agent’s utility depends on a sequence of decisions.
Sequential decision problems incorporate utilities, uncertainty, and sensing, and include search
and planning problems as special cases.

5.6.4 Sequential Decision Problems

Suppose that an agent is situated in the 4x3 environment shown in Figure 17.1(a). Beginning in the
start state, it must choose an action at each time step. The interaction with the environment
terminates when the agent reaches one of the goal states, marked +1 or -1. Just as for search
problems, the actions available to the agent in each state are given by ACTIONS(s), sometimes
abbreviated to A(s) ; in the 4x3 environment, the actions in every state are Up, Down, Left, and
Right. We assume for now that the environment is fully observable, so that the agent always knows
where it is.

11
If the environment were deterministic, a solution would be easy: [Up, Up, Right, Right, Right].
Unfortunately, the environment won’t always go along with this solution, because the actions are
unreliable. The transition model (or just “model,” when the meaning is clear) describes the
outcome of each action in each state.

Markovian: the probability of reaching from depends only on and not on the history of earlier
states. To complete the definition of the task environment, we must specify the utility function for
the agent. Because the decision problem is sequential, the utility function will depend on a
sequence of states and actions an environment history rather than on a single state.

An optimal policy: is a policy that yields the highest expected utility. We use π ∗ to denote an
optimal policy. There are two policies because the agent is exactly indifferent between going left
and going up from (3,1): going left is safer but longer, while going up is quicker but risks falling
into (4,2) by accident. In general there will often be multiple optimal policies.

12
With a finite horizon, an optimal action in a given state may depend on how much time is left. A
policy that depends on the time is called nonstationary.

5.6.5 Value Iteration

The Bellman equation is the basis of the value iteration algorithm for solving MDPs. If there are n
possible states, then there are n Bellman equations, one for each state. The n equations contain
unknowns the utilities of the states. So we would like to solve these simultaneous equations to find
the utilities. There is one problem: the equations are nonlinear, because the “max” operator is not
a linear operator. Whereas systems of linear equations can be solved quickly using linear algebra
techniques, systems of nonlinear equations are more problematic. One thing to try is an iterative
approach. We start with arbitrary initial values for the utilities, calculate the right-hand side of the
equation, and plug it into the left-hand side thereby updating the utility of each state from the
utilities of its neighbors. We repeat this until we reach equilibrium.

Bellman equation refer text book

13
The detailed algorithm, including a termination condition when the utilities are “close enough,” is
shown in Figure 17.6. Notice that we make use of the Q-VALUE function defined on page 569.

5.6.6 Policy iteration

In the previous section, we observed that it is possible to get an optimal policy even when the
utility function estimate is inaccurate. If one action is clearly better than all others, then the exact
magnitude of the utilities on the states involved need not be precise. This insight suggests an
alternative way to find optimal policies. The policy iteration algorithm alternates the following
two steps, beginning from some initial policy π0:

POLICY EVALUATION: given a policy πi, calculate Ui = U πi , the utility of each state if πi were
to be executed.

POLICY IMPROVEMENT: Calculate a new MEU policy πi+1, using one-step look-ahead based
on Ui (as below eq.).

14
This very general algorithm is called asynchronous policy iteration. Given certain conditions on
the initial policy and initial utility function, asynchronous policy iteration is guaranteed to
converge to an optimal policy.

5.7 Summery

✓ Uncertainty arises because of both laziness and ignorance. It is inescapable in complex,

nondeterministic, or partially observable environments.
✓ Probabilities express the agent’s inability to reach a definite decision regarding the truth of a
sentence. Probabilities summarize the agent’s beliefs relative to the evidence.
✓ Decision theory combines the agent’s beliefs and desires, defining the best action as the one
that maximizes expected utility.
✓ Basic probability statements include prior or unconditional probabilities and posterior or
conditional probabilities over simple and complex propositions.
✓ The axioms of probability constrain the probabilities of logically related propositions. An
agent that violates the axioms must behave irrationally in some cases.

15
✓ The full joint probability distribution specifies the probability of each complete assignment
of values to random variables. It is usually too large to create or use in its explicit form, but
when it is available it can be used to answer queries simply by adding up entries for the
possible worlds corresponding to the query propositions.
✓ Absolute independence between subsets of random variables allows the full joint distribution
to be factored into smaller joint distributions, greatly reducing its complexity.
✓ Bayes’ rule allows unknown probabilities to be computed from known conditional
probabilities, usually in the causal direction. Applying Bayes’ rule with many pieces of
evidence runs into the same scaling problems as does the full joint distribution.
✓ Conditional independence brought about by direct causal relationships in the domain allows
the full joint distribution to be factored into smaller, conditional distributions. The naive
Bayes model assumes the conditional independence of all effect variables, given a single
cause variable; its size grows linearly with the number of effects.
✓ A wumpus-world agent can calculate probabilities for unobserved aspects of the world,
thereby improving on the decisions of a purely logical agent. Conditional independence
makes these calculations tractable.
✓ A Bayesian network is a directed acyclic graph whose nodes correspond to random variables;
each node has a conditional distribution for the node, given its parents.
✓ Bayesian networks provide a concise way to represent conditional independence
relationships in the domain.
✓ A Bayesian network specifies a joint probability distribution over its variables. The
probability of any given assignment to all the variables is defined as the product of the
corresponding entries in the local conditional distributions. A Bayesian network is often
exponentially smaller than an explicitly enumerated joint distribution.
✓ Many conditional distributions can be represented compactly by canonical families of
distributions. Hybrid Bayesian networks, which include both discrete and continuous
variables, use a variety of canonical distributions.
✓ Inference in Bayesian networks means computing the probability distribution of a set of query
variables, given a set of evidence variables. Exact inference algorithms, such as variable
elimination, evaluate sums of products of conditional probabilities as efficiently as possible.

16
✓ In polytrees (singly connected networks), exact inference takes time linear in the size of the
network. In the general case, the problem is intractable.
✓ Random sampling techniques such as likelihood weighting and Markov chain Monte Carlo
can give reasonable estimates of the true posterior probabilities in a network and can cope
with much larger networks than can exact algorithms.
✓ Whereas Bayes nets capture probabilistic influences, causal networks capture causal
relationships and allow prediction of the effects of interventions as well as observations
✓ Relational probability models (RPMs) define probability models on worlds derived from
the database semantics for first-order languages; they are appropriate when all the objects
and their identities are known with certainty.
✓ Given an RPM, the objects in each possible world correspond to the constant symbols in the
RPM, and the basic random variables are all possible instantiations of the predicate symbols
with objects replacing each argument. Thus, the set of possible worlds is finite.
✓ RPMs provide very concise models for worlds with large numbers of objects and can handle
relational uncertainty.
✓ Open-universe probability models (OUPMs) build on the full semantics of first-order logic,
allowing for new kinds of uncertainty such as identity and existence uncertainty.
✓ Generative programs are representations of probability models—including OUPMs—as
executable programs in a probabilistic programming language or PPL. A generative
program represents a distribution over execution traces of the program. PPLs typically
provide universal expressive power for probability models
✓ The changing state of the world is handled by using a set of random variables to represent the
state at each point in time.
✓ Representations can be designed to (roughly) satisfy the Markov property, so that the future is
independent of the past given the present. Combined with the assumption that the process is
time-homogeneous, this greatly simplifies the representation.
✓ A temporal probability model can be thought of as containing a transition model describing
the state evolution and a sensor model describing the observation process.
✓ The principal inference tasks in temporal models are filtering (state estimation), prediction,
smoothing, and computing the most likely explanation. Each of these tasks can be achieved
using simple, recursive algorithms whose run time is linear in the length of the sequence.

17
✓ Three families of temporal models were studied in more depth: hidden Markov models,
Kalman filters, and dynamic Bayesian networks (which include the other two as special
cases).
✓ Unless special assumptions are made, as in Kalman filters, exact inference with many state
variables is intractable. In practice, the particle filtering algorithm and its descendants are an
effective family of approximation algorithms.
✓ Probability theory describes what an agent should believe on the basis of evidence, utility
theory describes what an agent wants, and decision theory puts the two together to describe
what an agent should do.
✓ We can use decision theory to build a system that makes decisions by considering all possible
actions and choosing the one that leads to the best expected outcome. Such a system is
known as a rational agent.
✓ Utility theory shows that an agent whose preferences between lotteries are consistent with a
set of simple axioms can be described as possessing a utility function; furthermore, the agent
selects actions as if maximizing its expected utility.
✓ Multi-attribute utility theory deals with utilities that depend on several distinct attributes of
states. Stochastic dominance is a particularly useful technique for making unambiguous
decisions, even without precise utility values for attributes.
✓ Decision networks provide a simple formalism for expressing and solving decision problems.
They are a natural extension of Bayesian networks, containing decision and utility nodes in
addition to chance nodes.
✓ Sometimes, solving a problem involves finding more information before making a decision.
The value of information is defined as the expected improvement in utility compared with
making a decision without the information; it is particularly useful for guiding the process of
information-gathering prior to making a final decision.
✓ When, as is often the case, it is impossible to specify the human’s utility function completely
and correctly, machines must operate under uncertainty about the true objective. This makes
a significant difference when the possibility exists for the machine to acquire more
information about human preferences. We showed by a simple argument that uncertainty
about preferences ensures that the machine defers to the human, to the point of allowing
itself to be switched off.

18
✓ Sequential decision problems in stochastic environments, also called Markov decision
processes, or MDPs, are defined by a transition model specifying the probabilistic
outcomes of actions and a reward function specifying the reward in each state.
✓ The utility of a state sequence is the sum of all the rewards over the sequence, possibly
discounted over time. The solution of an MDP is a policy that associates a decision with
every state that the agent might reach. An optimal policy maximizes the utility of the state
sequences encountered when it is executed.
✓ The utility of a state is the expected sum of rewards when an optimal policy is executed from
that state. The value iteration algorithm iteratively solves a set of equations relating the
utility of each state to those of its neighbors.
✓ Policy iteration alternates between calculating the utilities of states under the current policy
and improving the current policy with respect to the current utilities.
✓ Partially observable MDPs, or POMDPs, are much more difficult to solve than are MDPs.
They can be solved by conversion to an MDP in the continuous space of belief states; both
value iteration and policy iteration algorithms have been devised. Optimal behavior in
POMDPs includes information gathering to reduce uncertainty and therefore make better
decisions in the future.
✓ A decision-theoretic agent can be constructed for POMDP environments. The agent uses a
dynamic decision network to represent the transition and sensor models, to update its belief
state, and to project forward possible action sequences.

19
Review Questions

1. What do you mean by uncertain knowledge?

2. What is the reasoning in AI?
3. What is reasoning under uncertainty?
4. What is uncertainty in AI example?
5. What is symbolic reasoning under uncertainty in AI?
6. What is reasoning and its types?
7. What is knowledge in artificial intelligence?
8. What are the types of knowledge in AI?
9. What are the types of knowledge?
10. What is knowledge-based reasoning?
11. What are the sources of uncertainty in artificial intelligence?
12. How you represent knowledge in an uncertain domain?

20
 Chapter Six: Learning
6.1 Learning from Examples/Observation

Why would we want a machine to learn? Why not just program it the right way to begin with?
There are two main reasons. First, the designers cannot anticipate all possible future situations.
For example, a robot designed to navigate mazes must learn the layout of each new maze it
encounters; a program for predicting stock market prices must learn to adapt when conditions
change from boom to bust. Second, sometimes the designers have no idea how to program a
solution themselves. Most people are good at recognizing the faces of family members, but they do
it subconsciously, so even the best programmers don’t know how to program a computer to
accomplish that task, except by using machine learning algorithms.

Any component of an agent program can be improved by machine learning. The improvements,
and the techniques used to make them, depend on these factors:

✓ Which component is to be improved?

✓ What prior knowledge the agent has, which influences the model it builds.
✓ What data and feedback on that data is available.

In chapter 2 described several agent designs. The components of these agents include:

1. A direct mapping from conditions on the current state to actions.

2. A means to infer relevant properties of the world from the percept sequence.
3. Information about the way the world evolves and about the results of possible actions the
agent can take.
4. Utility information indicating the desirability of world states.
5. Action-value information indicating the desirability of actions.
6. Goals that describe the most desirable states.
7. A problem generator, critic, and learning element that enable the system to improve.

Each of these components can be learned. Consider a self-driving car agent that learns by
observing a human driver. Each of these components can be learned. Consider a self-driving car
agent that learns by observing a human driver. Every time the driver brakes, the agent might learn
a condition– action rule for when to brake (component 1). By seeing many camera images that it is

21
told contain buses, it can learn to recognize them (component 2). By trying actions and observing
the results—for example, braking hard on a wet road—it can learn the effects of its actions
(component 3). Then, when it receives complaints from passengers who have been thoroughly
shaken up during the trip, it can learn a useful component of its overall utility function (component
4).

Little prior knowledge on the part of the agent: it starts from scratch and learns from the data. We
consider transfer learning, in which knowledge from one domain is transferred to a new domain,
so that learning can proceed faster with less data. We do assume, however, that the designer of the
system chooses a model framework that can lead to effective learning.

Going from a specific set of observations to a general rule is called induction; from the
observations that the sun rose every day in the past, we induce that the sun will come up tomorrow.
This differs from the deduction because the inductive conclusions may be incorrect, whereas
deductive conclusions are guaranteed to be correct if the premises are correct.

When the output is one of a finite set of values (such as sunny/cloudy/rainy or true/false), the
learning problem is called classification. When it is a number (such as tomorrow’s temperature,
measured either as an integer or a real number), the learning problem has the (admittedly obscure )
name regression.

There are three types of feedback that can accompany the inputs, and that determine the three main
types of learning:

✓ In supervised learning the agent observes input-output pairs and learns a function that
maps from input to output. For example, the inputs could be camera images, each one
accompanied by an output saying “bus” or “pedestrian,” etc. An output like this is called a
label. The agent learns a function that, when given a new image, predicts the appropriate
label. In the case of braking actions (component 1 above), an input is the current state
(speed and direction of the car, road condition), and an output is the distance it took to stop.
In this case a set of output values can be obtained by the agent from its own percepts (after
the fact); the environment is the teacher, and the agent learns a function that maps states to
stopping distance.

22
 ✓ In unsupervised learning the agent learns patterns in the input without any explicit
feedback. The most common unsupervised learning task is clustering: detecting potentially
useful clusters of input examples. For example, when shown millions of images taken from
the Internet, a computer vision system can identify a large cluster of similar images which
an English speaker would call “cats.”
✓ In reinforcement learning the agent learns from a series of reinforcements: rewards and
punishments. For example, at the end of a chess game the agent is told that it has won (a
reward) or lost (a punishment). It is up to the agent to decide which of the actions prior to
the reinforcement were most responsible for it, and to alter its actions to aim towards more
rewards in the future.

6.2 Machine Learning - Categories

6.2.4 Supervised learning

Supervised learning is analogous to training a child to walk. You will hold the child’s hand, show
him how to take his foot forward, walk yourself for a demonstration and so on, until the child
learns to walk on his own. There are several algorithms available for supervised learning. Some of
the widely used algorithms of supervised learning are as shown below

✓ k-Nearest Neighbours
✓ Decision Trees
✓ Naive Bayes
✓ Logistic Regression

As we move ahead in this chapter, let us discuss in detail about each of the algorithms.

[Link] K-Nearest Neighbours

The k-Nearest Neighbours, which is simply called kNN is a statistical technique that can be used
for solving for classification and regression problems. Let us discuss the case of classifying an
unknown object using kNN. Consider the distribution of objects as shown in the image given
below:

23
The diagram shows three types of objects, marked in red, blue and green colors. When you run the
kNN classifier on the above dataset, the boundaries for each type of object will be marked as
shown below:

As you see it visually, the unknown data point belongs to a class of blue objects. Mathematically,
this can be concluded by measuring the distance of this unknown point with every other point in
the data set. When you do so, you will know that most of its neighbours are of blue color. The
average distance to red and green objects would be definitely more than the average distance to
blue objects. Thus, this unknown object can be classified as belonging to blue class.

The kNN algorithm can also be used for regression problems. The kNN algorithm is available as
ready-to-use in most of the ML libraries.

24
[Link] Decision Trees

A decision tree is a representation of a function that maps a vector of attribute values to a single
output value a “decision.” A decision tree reaches its decision by performing a sequence of tests,
starting at the root and following the appropriate branch until a leaf is reached. Each internal node
in the tree corresponds to a test of the value of one of the input attributes, the branches from the
node are labeled with the possible values of the attribute, and the leaf nodes specify what value is
to be returned by the function.

In general, the input and output values can be discrete or continuous, but for now we will
consider only inputs consisting of discrete values and outputs that are either true (a positive
example) or false (a negative example). We call this Boolean classification. We will use to index
the examples ( is the input vector for the th example and is the output), and for the th attribute of
the th example. A simple decision tree in a flowchart format is shown below:

You would write a code to classify your input data based on this flowchart. The flowchart is
self-explanatory and trivial. In this scenario, you are trying to classify an incoming email to decide
when to read it.

25
In reality, the decision trees can be large and complex. There are several algorithms available to
create and traverse these trees. As a Machine Learning enthusiast, you need to understand and
master these techniques of creating and traversing decision trees.

[Link] Naive Bayes

Naive Bayes is used for creating classifiers. Suppose you want to sort out (classify) fruits of
different kinds from a fruit basket. You may use features such as color, size and shape of a fruit,
For example, any fruit that is red in color, is round in shape and is about 10 cm in diameter may be
considered as Apple. So to train the model, you would use these features and test the probability
that a given feature matches the desired constraints. The probabilities of different features are then
combined to arrive at a probability that a given fruit is an Apple. Naive Bayes generally requires a
small number of training data for classification

[Link] Regression

Similarly, in the case of supervised learning, you give concrete known examples to the computer.
You say that for given feature value x1 the output is y1, for x2 it is y2, for x3 it is y3, and so on.
Based on this data, you let the computer figure out an empirical relationship between x and y.

Once the machine is trained in this way with a sufficient number of data points, now you would ask
the machine to predict Y for a given X. Assuming that you know the real value of Y for this given
X, you will be able to deduce whether the machine’s prediction is correct.

Thus, you will test whether the machine has learned by using the known test data. Once you are
satisfied that the machine is able to do the predictions with a desired level of accuracy (say 80 to
90%) you can stop further training the machine.

Now, you can safely use the machine to do the predictions on unknown data points, or ask the
machine to predict Y for a given X for which you do not know the real value of Y. This training
comes under the regression that we talked about earlier.

6.2.5 Classification

You may also use machine learning techniques for classification problems. In classification
problems, you classify objects of similar nature into a single group. For example, in a set of 100

26
students say, you may like to group them into three groups based on their heights - short, medium
and long. Measuring the height of each student, you will place them in a proper group.

Now, when a new student comes in, you will put him in an appropriate group by measuring his
height. By following the principles in regression training, you will train the machine to classify a
student based on his feature – the height. When the machine learns how the groups are formed, it
will be able to classify any unknown new student correctly. Once again, you would use the test
data to verify that the machine has learned your technique of classification before putting the
developed model in production.

Supervised Learning is where the AI really began its journey. This technique was applied
successfully in several cases. You have used this model while doing the hand-written recognition
on your machine. Several algorithms have been developed for supervised learning. You will learn
about them in the following chapters.

6.2.6 Unsupervised Learning

In unsupervised learning, we do not specify a target variable to the machine, rather we ask machine
“What can you tell me about X?”. More specifically, we may ask questions such as given a huge
data set X, “What are the five best groups we can make out of X?” or “What features occur
together most frequently in X?”. To arrive at the answers to such questions, you can understand
that the number of data points that the machine would require to deduce a strategy would be very
large. In case of supervised learning, the machine can be trained with even about few thousands of
data points. However, in case of unsupervised learning, the number of data points that is
reasonably accepted for learning starts in a few millions. These days, the data is generally
abundantly available. The data ideally requires curating. However, the amount of data that is
continuously flowing in a social area network, in most cases data curation is an impossible task.

The following figure shows the boundary between the yellow and red dots as determined by
unsupervised machine learning. You can see it clearly that the machine would be able to determine
the class of each of the black dots with a fairly good accuracy.

27
[Link] k-means clustering

The 2000 and 2004 Presidential elections in the United States were close — very close. The largest
percentage of the popular vote that any candidate received was 50.7% and the lowest was 47.9%. If
a percentage of the voters were to have switched sides, the outcome of the election would have
been different. There are small groups of voters who, when properly appealed to, will switch sides.
These groups may not be huge, but with such close races, they may be big enough to change the
outcome of the election. How do you find these groups of people? How do you appeal to them with
a limited budget? The answer is clustering.

Let us understand how it is done.

✓ First, you collect information on people either with or without their consent: any sort of
information that might give some clue about what is important to them and what will
influence how they vote.
✓ Then you put this information into some sort of clustering algorithm.
✓ Next, for each cluster (it would be smart to choose the largest one first) you craft a message
that will appeal to these voters.
✓ Finally, you deliver the campaign and measure to see if it’s working.

Clustering is a type of unsupervised learning that automatically forms clusters of similar things. It
is like automatic classification. You can cluster almost anything, and the more similar the items are
in the cluster, the better the clusters are. In this chapter, we are going to study one type of clustering

28
algorithm called k-means. It is called k-means because it finds ‘k’ unique clusters, and the center
of each cluster is the mean of the values in that cluster.

[Link] Cluster Identification

Cluster identification tells an algorithm, “Here’s some data. Now group similar things together and
tell me about those groups.” The key difference from classification is that in classification you
know what you are looking for. While that is not the case in clustering.

Clustering is sometimes called unsupervised classification because it produces the same result as
classification does but without having predefined classes.

Now, we are comfortable with both supervised and unsupervised learning. To understand the rest
of the machine learning categories, we must first understand Artificial Neural Networks (ANN),
which we will learn in the next chapter.

6.2.7 Reinforcement Learning

Consider training a pet dog, we train our pet to bring a ball to us. We throw the ball at a certain
distance and ask the dog to fetch it back to us. Every time the dog does this right, we reward the
dog. Slowly, the dog learns that doing the job rightly gives him a reward and then the dog starts
doing the job right way every time in future. Exactly, this concept is applied in “Reinforcement”
type of learning. The technique was initially developed for machines to play games. The machine
is given an algorithm to analyze all possible moves at each stage of the game. The machine may
select one of the moves at random. If the move is right, the machine is rewarded, otherwise it may
be penalized. Slowly, the machine will start differentiating between right and wrong moves and
after several iterations would learn to solve the game puzzle with a better accuracy. The accuracy
of winning the game would improve as the machine plays more and more games. The entire
process may be depicted in the following diagram:

29
This technique of machine learning differs from the supervised learning in that you need not
supply the labelled input/output pairs. The focus is on finding the balance between exploring the
new solutions versus exploiting the learned solutions.

6.2.8 Deep Learning

The deep learning is a model based on Artificial Neural Networks (ANN), more specifically
Convolutional Neural Networks (CNN)s. There are several architectures used in deep learning
such as deep neural networks, deep belief networks, recurrent neural networks, and convolutional
neural networks.

These networks have been successfully applied in solving the problems of computer vision, speech
recognition, natural language processing, bioinformatics, drug design, medical image analysis,
and games. There are several other fields in which deep learning is proactively applied. The deep
learning requires huge processing power and humongous data, which is generally easily available
these days.

We will talk about deep learning more in detail in the coming chapters.

6.2.9 Deep Reinforcement Learning

The Deep Reinforcement Learning (DRL) combines the techniques of both deep and
reinforcement learning. The reinforcement learning algorithms like Q-learning are now combined
with deep learning to create a powerful DRL model. The technique has been with a great success in

30
the fields of robotics, video games, finance and healthcare. Many previously unsolvable problems
are now solved by creating DRL models. There is lots of research going on in this area and this is
very actively pursued by the industries.

So far, you have got a brief introduction to various machine learning models, now let us explore
slightly deeper into various algorithms that are available under these models.

6.3 Learning probabilistic model

Probabilistic Models in Machine Learning is the use of the codes of statistics to data examination.
It was one of the initial methods of machine learning. It’s quite extensively used to this day.
Individual of the best-known algorithms in this group is the Naive Bayes algorithm. Probabilistic
modeling delivers a framework for accepting what learning is. The probabilistic framework
defines how to signify and deploy reservation about models. Predictions have a dominant role in
scientific data analysis. Their role is also so important in machine learning, automation, cognitive
computing and artificial intelligence.

Probabilistic models are presented as a prevailing idiom to define the world. Those were described
by using random variables for example building blocks believed together by probabilistic
relationships.

There are probabilistic models along with non-probabilistic models in machine learning. The
information about basic concepts of probability for example random variables and probability
distributions would be helpful in order to have a well understanding of probabilistic models.

Portrayal inference from noisy or ambiguous data is an imperative part of intelligent systems. In
probability theory particularly Bayes’ theorem helps as a principled framework of combining prior
knowledge and empirical evidence.

6.3.4 Statistical learning

Statistical Learning is understands from training data and predicting on unseen data. Statistical
learning is used to build predictive models based on the data. Statistical learning is the ability for
humans and other animals to extract statistical regularities from the world around them to learn

31
about the environment. Although statistical learning is now thought to be a generalized learning
mechanism, the phenomenon was first identified in human infant language acquisition.

Statistical Learning is a set of tools for understanding data. These tools broadly come under two
classes: supervised learning & unsupervised learning. Generally, supervised learning refers to
predicting or estimating an output based on one or more inputs. Unsupervised learning, on the
other hand, provides a relationship or finds a pattern within the given data without a supervised
output.

Bayesian learning simply statistical method which is calculates the probability of each hypothesis,
given the data, and makes predictions on that basis. That is, the predictions are made by using all
the hypotheses, weighted by their probabilities, rather than by using just a single “best” hypothesis.
In this way, learning is reduced to probabilistic inference.

Linear regression is a statistical method belonging to supervised learning used for predicting
quantitative responses. Simple Linear Regression approach predicts a quantitative response based
on a single variable X assuming a linear relationship.

6.3.5 Importance of probabilistic learning models

One of the key benefits of probabilistic models is that they give an idea about the uncertainty
linked with predictions. We may get an idea of how confident a machine learning model is on its
prediction. For example, if the probabilistic classifier allocates a probability of 0.9 for the ‘Dog’
class in its place of 0.6, it means the classifier is extra confident that the animal in the image is a
dog. These concepts connected to uncertainty and confidence are very valuable when it originates
to critical machine learning uses for example disease diagnosis and autonomous driving.
Moreover, probabilistic consequences would be worthwhile for many methods linked to Machine
Learning for instance Active Learning.

6.3.6 Bayesian Inference

At the centre of Bayesian inference is the Bayes’ rule sometimes called Bayes’ theorem. It is used
to define the probability of a hypothesis with former knowledge. It is contingent on conditional
probability.

32
Bayes Rule: The formula for Bayes’ theorem is known as;

P (hypothesis│data) = P (data│hypothesis) P (hypothesis) / P (data)

✓ Bayes rule states that how to do inference about hypotheses from data.
✓ Learning and prediction may be understood as forms of inference.

The typical Bayesian inference with Bayes’ rule needs for a mechanism to straight regulate the
target posterior distribution. For example, the inference process is a one-way procedure that plans
the earlier distribution to the posterior by detecting empirical data. In supervised learning and
reinforcement learning, our final goal is to put on the posterior to learning tasks. That is applied
with some measurement on the performance for instance prediction error or expected reward.

An upright posterior distribution should have a small prediction error or a great expected reward.
Furthermore, by way, the large scale knowledge bases are built and crowdsourcing platforms are
broadly accepted to gather human data, it is needed to include the outside information into
statistical modelling and inference when building an intelligent system.

The typical Bayesian inference with Bayes’ rule is needing for a mechanism to straight regulate the
target posterior distribution. For example, the inference process is a one-way procedure that plans
the earlier distribution to the posterior by detecting empirical data. In supervised learning and
reinforcement learning, our final goal is to put on the posterior to learning tasks. That is applied
with some measurement on the performance for instance prediction error or expected reward.

An upright posterior distribution should have a small prediction error or a great expected reward.
Furthermore, by way, the large scale knowledge bases are built and crowdsourcing platforms are
broadly accepted to gather human data, it is needed to include the outside information into
statistical modelling and inference when building an intelligent system.

6.3.7 Naive Bayes algorithm

Naïve Bayes algorithm is a supervised learning algorithm. It is created on the Bayes theorem and
used for resolving sorting problems. It is chiefly used in text classification that comprises a
high-dimensional training dataset. The naïve Bayes algorithm is one of the simple and best

33
operational Classification algorithms that support construction the of fast machine learning models
which may create rapid predictions.

The naive Bayes algorithm is a probabilistic classifier. It means that it predicts on the basis of the
probability of an object. More or less prevalent instances of Naïve Bayes Algorithm are;

✓ Spam filtration
✓ Sentimental analysis
✓ Classifying articles

A narrowly correlated model is the logistic regression. That is sometimes well thought-out to be
the “hello world” of modern machine learning. Don’t be deceived by its name as log reg is a
classification algorithm somewhat a regression algorithm. Considerably like Naive Bayes, up till
now, it’s quite useful to this day as log reg predates computing for a long time, Thanks to its
modest and multipurpose nature. It’s frequently the first thing a data scientist would attempt on a
dataset to become a feel for the classification task at hand.

[Link] Types of Naïve Bayes Model

There are the following three types of Naive Bayes Model:

Gaussian: The Gaussian model takes responsibility that features monitor a normal distribution.
This means that if analysts take nonstop values rather than separate, then the model takes up that
these values are tested from the Gaussian distribution.

Multinomial: It is used when the data is multinomial circulated. It is mainly used for document
classification problems. It means a specific document goes to that category for example Sports,
education, and Politics etc. The classifier uses the rate of words for the predictors.

Bernoulli: The Bernoulli classifier does work alike to the Multinomial classifier. Then the
predictor variables are the self-governing Booleans variables. For example, if a specific word is
present or not in a document. This model is as well well-known for document classification tasks.

Uses of Naïve Bayes Model

The Naïve Bayes Classifier used;

34
 ✓ For Credit Scoring.
✓ In medical data classification.
✓ It may be used in real-time predictions as Naïve Bayes Classifier is a keen learner.
✓ In-Text classification for example Spam filtering and Sentiment analysis.

Pros and Cons of Bayes Classifier

Pros:

✓ Naïve Bayes is one of the easy and fast machine learning algorithms to foresee a class of
datasets.
✓ It may be used for Binary also as Multi-class Classifications.
✓ It does well in Multi-class predictions for example likened to the other Algorithms.
✓ It is the greatest widespread selection for text classification problems.

Cons:

✓ Naive Bayes accepts that all sorts are autonomous or disparate. Therefore it cannot learn
the association between features.

6.3.8 Neural Networks

The inventor of the first neurocomputer, Dr. Robert Hecht-Nielsen, defines a neural network as
"...a computing system made up of a number of simple, highly interconnected processing elements,
which process information by their dynamic state response to external inputs.”

[Link] Basic Structure of ANNs

The idea of ANNs is based on the belief that working of human brain by making the right
connections can be imitated using silicon and wires as living neurons and dendrites.

The human brain is composed of 86 billion nerve cells called neurons. They are connected to other
thousand cells by Axons. Stimuli from external environment or inputs from sensory organs are
accepted by dendrites. These inputs create electric impulses, which quickly travel through the
neural network. A neuron can then send the message to other neuron to handle the issue or does not
send it forward

35
 Figure: illustrates the typical diagram of Biological Neural Network.

Figure: The typical Artificial Neural Network looks something like the given figure.

Dendrites from Biological Neural Network represent inputs in Artificial Neural Networks, cell
nucleus represents Nodes, synapse represents Weights, and Axon represents Output. Relationship
between Biological neural network and artificial neural network:
Biological Neural Network Artificial Neural Network
Dendrites Inputs
Cell nucleus Nodes
Synapse Weights
Axon Output

Artificial Neural Network primarily consists of three layers:

36
 ✓ Input Layer: As the name suggests, it accepts inputs in several different formats provided
by the programmer.
✓ Hidden Layer: The hidden layer presents in-between input and output layers. It performs
all the calculations to find hidden features and patterns.
✓ Output Layer: The input goes through a series of transformations using the hidden layer,
which finally results in output that is conveyed using this layer.

The artificial neural network takes input and computes the weighted sum of the inputs and includes
a bias. This computation is represented in the form of a transfer function

It determines weighted total is passed as an input to an activation function to produce the output.
Activation functions choose whether a node should fire or not. Only those who are fired make it to
the output layer. There are distinctive activation functions available that can be applied upon the
sort of task we are performing.

ANNs are composed of multiple nodes, which imitate biological neurons of human brain. The
neurons are connected by links and they interact with each other. The nodes can take input data and

37
perform simple operations on the data. The result of these operations is passed to other neurons.
The output at each node is called its activation or node value. Each link is associated
with weight. ANNs are capable of learning, which takes place by altering weight values. The
following illustration shows a simple ANN −

[Link] Types of Artificial Neural Networks

There are two Artificial Neural Network topologies: FeedForward and Feedback.

FeedForward ANN: In this ANN, the information flow is unidirectional. A unit sends
information to other unit from which it does not receive any information. There are no feedback
loops. They are used in pattern generation/recognition/classification. They have fixed inputs and
outputs. In this type of ANN, the output returns into the network to accomplish the best-evolved
results internally. As per the University of Massachusetts, Lowell Centre for Atmospheric
Research. The feedback networks feed information back into itself and are well suited to solve
optimization issues. The Internal system error corrections utilize feedback ANNs.

FeedBack ANN: Here, feedback loops are allowed. They are used in content addressable memorie

38
 s.

A feed-forward network is a basic neural network comprising of an input layer, an output layer,
and at least one layer of a neuron. Through assessment of its output by reviewing its input, the
intensity of the network can be noticed based on group behavior of the associated neurons, and the
output is decided. The primary advantage of this network is that it figures out how to evaluate and
recognize input patterns.

[Link] Working of ANNs

In the topology diagrams shown, each arrow represents a connection between two neurons and
indicates the pathway for the flow of information. Each connection has a weight, an integer
number that controls the signal between the two neurons.

If the network generates a “good or desired” output, there is no need to adjust the weights.
However, if the network generates a “poor or undesired” output or an error, then the system alters
the weights in order to improve subsequent results.

39
Afterward, each of the input is multiplied by its corresponding weights ( these weights are the
details utilized by the artificial neural networks to solve a specific problem ). In general terms,
these weights normally represent the strength of the interconnection between neurons inside the
artificial neural network. All the weighted inputs are summarized inside the computing unit.

If the weighted sum is equal to zero, then bias is added to make the output non-zero or something
else to scale up to the system's response. Bias has the same input, and weight equals to 1. Here the
total of weighted inputs can be in the range of 0 to positive infinity. Here, to keep the response in
the limits of the desired value, a certain maximum value is benchmarked, and the total of weighted
inputs is passed through the activation function.

The activation function refers to the set of transfer functions used to achieve the desired output.
There is a different kind of the activation function, but primarily either linear or non-linear sets of
functions. Some of the commonly used sets of activation functions are the Binary, linear, and Tan
hyperbolic sigmoidal activation functions. Let us take a look at each of them in details:

Binary: In binary activation function, the output is either a one or a 0. Here, to accomplish this,
there is a threshold value set up. If the net weighted input of neurons is more than 1, then the final
output of the activation function is returned as one or else the output is returned as 0.

Sigmoidal Hyperbolic: The Sigmoidal Hyperbola function is generally seen as an "S" shaped
curve. Here the tan hyperbolic function is used to approximate output from the actual net input.
The function is defined as: F(x) = (1/1 + exp(-????x)) Where???? is considered the Steepness
parameter.

Advantages of Artificial Neural Network (ANN)

✓ Parallel processing capability: Artificial neural networks have a numerical value that can
perform more than one task simultaneously.
✓ Storing data on the entire network: Data that is used in traditional programming is
stored on the whole network, not on a database. The disappearance of a couple of pieces of
data in one place doesn't prevent the network from working.

40
 ✓ Capability to work with incomplete knowledge: After ANN training, the information
may produce output even with inadequate data. The loss of performance here relies upon
the significance of missing data.
✓ Having a memory distribution: For ANN is to be able to adapt, it is important to
determine the examples and to encourage the network according to the desired output by
demonstrating these examples to the network. The succession of the network is directly
proportional to the chosen instances, and if the event can't appear to the network in all its
aspects, it can produce false output.
✓ Having fault tolerance: Extortion of one or more cells of ANN does not prohibit it from
generating output, and this feature makes the network fault-tolerance.

Disadvantages of Artificial Neural Network:

✓ Assurance of proper network structure: There is no particular guideline for determining

the structure of artificial neural networks. The appropriate network structure is
accomplished through experience, trial, and error.
✓ Unrecognized behavior of the network: It is the most significant issue of ANN. When
ANN produces a testing solution, it does not provide insight concerning why and how. It
decreases trust in the network.
✓ Hardware dependence: Artificial neural networks need processors with parallel
processing power, as per their structure. Therefore, the realization of the equipment is
dependent.
✓ Difficulty of showing the issue to the network: ANNs can work with numerical data.
Problems must be converted into numerical values before being introduced to ANN. The
presentation mechanism to be resolved here will directly impact the performance of the
network. It relies on the user's abilities.
✓ The duration of the network is unknown: The network is reduced to a specific value of
the error, and this value does not give us optimum results.

6.3.9 Summary
Statistical learning methods range from simple calculation of averages to the construction of
complex models such as Bayesian networks. They have applications throughout computer science,

41
engineering, computational biology, neuroscience, psychology, and physics. This chapter has
presented some of the basic ideas and given a flavor of the mathematical underpinnings. The main
points are as follows:

✓ Learning takes many forms, depending on the nature of the agent, the component to be
improved, and the available feedback.
✓ Decision trees can represent all Boolean functions. The information-gain heuristic
provides an efficient method for finding a simple, consistent decision tree.
✓ Computational learning theory analyzes the sample complexity and computational
complexity of inductive learning. There is a tradeoff between the expressiveness of the
hypothesis space and the ease of learning.
✓ Bayesian learning methods formulate learning as a form of probabilistic inference, using
the observations to update a prior distribution over hypotheses. This approach provides a
good way to implement Ockham’s razor, but quickly becomes intractable for complex
hypothesis spaces.
✓ Linear regression is a widely used model. The optimal parameters of a linear regression
model can be calculated exactly, or can be found by gradient descent search, which is a
technique that can be applied to models that do not have a closed-form solution.
✓ Maximum a posteriori (MAP) learning selects a single most likely hypothesis given the
data. The hypothesis prior is still used and the method is often more tractable than full
Bayesian learning.
✓ Logistic regression replaces the perceptron’s hard threshold with a soft threshold defined
by a logistic function. Gradient descent works well even for noisy data that are not linearly
separable.
✓ Maximum-likelihood learning simply selects the hypothesis that maximizes the
likelihood of the data; it is equivalent to MAP learning with a uniform prior. In simple
cases such as linear regression and fully observable Bayesian networks,
maximumlikelihood solutions can be found easily in closed form. Naive Bayes learning is
a particularly effective technique that scales well.
✓ When some variables are hidden, local maximum likelihood solutions can be found using
the expectation maximization (EM) algorithm. Applications include unsupervised

42
 clustering using mixtures of Gaussians, learning Bayesian networks, and learning hidden
Markov models.
✓ Learning the structure of Bayesian networks is an example of model selection. This usually
involves a discrete search in the space of structures. Some method is required for trading
off model complexity against degree of fit.
✓ Nonparametric models represent a distribution using the collection of data points. Thus,
the number of parameters grows with the training set. Nearest-neighbors methods look at
the examples nearest to the point in question, whereas kernel methods form a
distance-weighted combination of all the examples.
✓ Three main components of ANN: an input later, a processing layer, and an output layer.
The inputs may be weighted based on various criteria. Within the processing layer, which
is hidden from view, there are nodes and connections between these nodes, meant to be
analogous to the neurons and synapses in an animal brain.

43
Review Questions
1. What is learning in AI and its types?
2. What defines machine learning?
3. What is learning in artificial neural network?
4. What is this learning?
5. What is learning and adaptation?
6. What is machine learning and examples?
7. What is machine learning vs AI?
8. Why is machine learning used?
9. What are the three main types of learning in AI?
10. What is a probabilistic model in AI?
11. What is probabilistic model in deep learning?
12. What are types of probabilistic models?
13. Where are probabilistic models used?
14. What is a probability model?
15. Is AI probabilistic?
16. What is non probabilistic model?
17. Are neural networks probabilistic models?
18. Are all machine learning models probabilistic?
19. What are probabilistic and deterministic models?
20. Is decision tree a probabilistic model?
21. What is deterministic model example?
22. Is SVM probabilistic model?

44
 Chapter Seven: Communicating, Perceiving, and Acting

7.1 Introduction
There are two main reasons why we want our computer agents to be able to process natural
languages: first, to communicate with humans, and second, to acquire information from written
language. There are over a trillion pages of information on the Web, almost all of it in natural
language. An agent that wants to do knowledge acquisition needs to understand (at least partially)
the ambiguous, messy languages that humans use.
Communication and artificial intelligence (AI) are closely related. It is communication –
particularly interpersonal conversational interaction – that provides AI with its defining test case
and experimental evidence. Likewise, recent developments in AI introduce new challenges and
opportunities for communication studies. Technologies such as machine translation of human
languages, spoken dialogue systems like Siri, algorithms capable of producing publishable
journalistic content, and social robots are all designed to communicate with users in a human-like
way.
Perception in Artificial Intelligence is the process of interpreting vision, sounds, smell, and touch.
Perception helps to build machines or robots that react like humans. Perception is a process to
interpret, acquire, select, and then organize the sensory information from the physical world to
make actions like humans. The main difference between AI and robot is that the robot makes
actions in the real world.
Reasoning

Reasoning plays a great role in the process of artificial Intelligence. Thus, Reasoning can be
defined as the logical process of drawing conclusions, making predictions or constructing
approaches towards a particular thought with the help of existing knowledge. In artificial
intelligence, reasoning is very important because to understand the human brain, how the brain
thinks, how it draws conclusions towards particular things for all these sorts of works we need the
help of reasoning.
Types of Reasoning in Artificial Intelligence

In today’s modern world with the advancement of technology we can process the thoughts of
humans, the machines are been designed which can think like humans and mimic their actions,

45
thus the overall procedure of design of the machine which can act like humans is called Artificial
Intelligence. Some of the applications of artificial Intelligence is expert systems, Natural language
processing, Speech Recognition, Computer Vision.
Methods of Reasoning: The reasoning is classified into the following types:

Deductive Reasoning: Deductive Reasoning is the strategic approach that uses available facts,
information or knowledge to draw valid conclusions. It basically beliefs in the facts and ideas
before drawing any result. Deductive reasoning uses a top-down approach. In deductive reasoning,
the arguments can be valid or invalid based on the value of the premises. If the value of the
premises is true, then the conclusion is also true. Deductive reasoning helps in scanning the
generalized statement into a valid conclusion. Some of the examples are
✓ People who are aged 20 or above are active users of the internet.
✓ Out of the total number of students present in the class, the ratio of boys is more than
the girls.

Inductive Reasoning: Inductive reasoning is completely different from the deductive reasoning
approach because Inductive reasoning is associated with the hypothesis-generating approach
rather than drawing any particular conclusion to the facts at the beginning of the process. Inductive
reasoning help in making generalization from specific facts and knowledge. Inductive reasoning is
the bottom-up process. In inductive Reasoning even if the premises are true there is no chance that
the conclusion will also be true because it depends upon the inductive argument which can be
either strong or weak. Some of the examples are:
✓ All the students present in the classroom are from London.
✓ Always the hottest temperature is recorded in Death Valley.

Common Sense Reasoning: Common sense reasoning is the most occurred type of reasoning in
daily life events. It is the type of reasoning which comes from experiences. When a human face a
different situation in life it gains some knowledge. So whenever in the next point of time it faces a
similar type of situation then it uses its previous experiences to draw a conclusion to do situation.
Some of the examples are:
✓ when a bike crosses the traffic signal when it is red then it learns from its mistakes and next
time the bike is aware of the signal and actions.

46
 ✓ While overtaking someone on the road what all ideas should be kept in mind.
✓ Monotonic Reasoning: It is the type of reasoning which follows a different approach
towards the thinking process it uses facts, information and knowledge to draw a conclusion
about the problem but the major point is its conclusion remain fixed permanently once it is
decided because even if we add new information or facts to the existing one the conclusion
remains the same it doesn’t change. Monotonic reasoning is used mainly in conventional
reasoning systems and logic-based systems. Some Examples of monotonic are:
o The Sahara Desert of the world is one of the most spectacular deserts.
o One of the longest rivers in the world is the Nile River.

Abductive Reasoning: Abductive Reasoning is a type of reasoning which acts differently from all
the above reasoning strategies. It begins with an incomplete set of facts, information and
knowledge and then proceeds to find the most deserving explanation and conclusion. It draws
conclusions based on what facts you know at present rather than collecting some outdated facts
and information. It mostly plays a great role in the daily life decision-making process. Some of the
examples are:
✓ Doctor drawing conclusions regarding your health based on test reports.
✓ A bowl of soup is kept and vapour evaporating from it which draws the conclusion that the
bowl is hot in nature.

7.2 Natural Language Processing

Language Models: Formal languages, such as the programming languages Java or Python, have
precisely defined language models. A language can be defined as a set of strings; “print (2 + 2)” is
a legal program in the language Python, whereas “2) +(2 print” is not. Since there are an infinite
number of legal programs, they cannot be enumerated; instead, they are specified by a set of rules
called a grammar. Formal languages also have rules that define the meaning or semantics of a
program; for example, the rules say that the “meaning” of “2 + 2” is 4, and the meaning of “1/0” is
that an error is signaled.

Natural languages, such as English or Spanish, cannot be characterized as a definitive set of

sentences. Everyone agrees that “Not to be invited is sad” is a sentence of English, but people
disagree on the grammaticality of “To be not invited is sad.” Therefore, it is more fruitful to define

47
a natural language model as a probability distribution over sentences rather than a definitive set.
That is, rather than asking if a string of words is or is not a member of the set defining the language,
we instead ask for P (S = words) - what is the probability that a random sentence would be words.

Natural languages are also ambiguous. “He saw her duck” can mean either that he saw a waterfowl
belonging to her, or that he saw her move to evade something. Thus, again, we cannot speak of a
single meaning for a sentence, but rather of a probability distribution over possible meaning.

Finally, natural languages are difficult to deal with because they are very large, and constantly
changing. Thus, our language models are, at best, an approximation. We start with the simplest
possible approximations and move up from there.
Text Classification:

It is also known as categorization - given a text of some kind, decide which of a predefined set of
classes it belongs to.
Example 7.1:
✓ Language identification and genre classification, as is sentiment analysis (classifying a
movie or product review as positive or negative) and spam detection (classifying an email
message as spam or not-spam). Since “not-spam” is awkward, researchers have coined the
term ham for not-spam. A training set is readily available: the positive (spam) examples are
in my spam folder, the negative (ham) examples are in my inbox. Here is an excerpt:
✓ Spam: Wholesale FashionWatches -57% today. Designer watches for cheap ...
✓ Spam: You can buy ViagraFr$1.85 All Medications at unbeatable prices! ...
✓ Spam: WE CAN TREAT ANYTHING YOU SUFFER FROM JUST TRUST US ...
✓ Spam: [Link] earn*ing the salary you d-eserve by o’btaining the proper crede’ntials!
✓ Ham: The practical significance of hypertree width in identifying more ...
✓ Ham: Abstract: We will motivate the problem of social identity clustering: ...
✓ Ham: Good to see you my friend. Hey Peter, It was good to hear from you. ...
✓ Ham: PDS implies convexity of the resulting optimization problem (Kernel
Ridge ...

48
7.3 Natural Language for Communication
Communication is the intentional exchange of information brought about by the production and
perception of signs drawn from a shared system of conventional signs. Most animals use signs to
represent important messages: food here, predator nearby, approach, withdraw, let’s mate. In a
partially observable world, communication can help agents be successful because they can learn
information that is observed or inferred by others. Humans are the most-chatty of all species, and if
computer agents are to be helpful, they’ll need to learn to speak the language.

7.4 Perception
Perception provides agents with information about the world they inhabit by interpreting the
response of sensors. A sensor measures some aspect of the environment in a form that can be used
as input by an agent program. The sensor could be as simple as a switch, which gives one bit telling
whether it is on or off, or as complex as the eye. A variety of sensory modalities are available to
artificial agents. Those they share with humans include vision, hearing, and touch. Modalities that
are not available to the unaided human include radio, infrared, GPS, and wireless signals. Some
robots do active sensing, meaning they send out a signal, such as radar or ultrasound, and sense the
reflection of this signal off of the environment. Rather than trying to cover all of these, this chapter
will cover one modality in depth: vision.

A model-based decision-theoretic agent in a partially observable environment has a sensor model -

a probability distribution P(E|S) over the evidence that its sensors provide, given a state of the
world. Bayes’ rule can then be used to update the estimation of the state.

For vision, the sensor model can be broken into two components:
a. An object model describes the objects that inhabit the visual world - people, buildings,
trees, cars, etc. The object model could include a precise 3D geometric model taken from a
computer-aided design (CAD) system, or it could be vague constraints, such as the fact that
human eyes are usually 5 to 7 cm apart.
b. A rendering model describes the physical, geometric, and statistical processes that
produce the stimulus from the world. Rendering models are quite accurate, but they are
ambiguous.
Example:

49
A white object under low light may appear as the same color as a black object under intense light.
A small nearby object may look the same as a large distant object. Without additional evidence, we
cannot tell if the image that fills the frame is a toy Godzilla or a real monster. We can characterize
three broad approaches to the problem.
a. The feature extraction approach, as exhibited by Drosophila, emphasizes simple
computations applied directly to the sensor observations.
b. The recognition approaches an agent draws distinctions among the objects it encounters
based on visual and other information. Recognition could mean labeling each image with a
yes or no as to whether it contains food that we should forage, or contains Grandma’s face.
c. The reconstruction approaches an agent builds a geometric model of the world from an
image or a set of images.
Image Formation
Imaging distorts the appearance of objects.
Example:
✓ A picture taken looking down a long straight set of railway tracks will suggest that the rails
converge and meet.
✓ If you hold your hand in front of your eye, you can block out the moon, which is not
smaller than your hand. As you move your hand back and forth or tilt it, your hand will
seem to shrink and grow in the image, but it is not doing so in reality.

7.5 Robotics
Robots are physical agents that perform tasks by manipulating the physical world. To do so, they
are equipped with effectors such as legs, wheels, joints, and grippers. Effectors have a single
purpose: to assert physical forces on the environment. Robots are also equipped with sensors,
which allow them to perceive their environment. Present day robotics employs a diverse set of
sensors, including cameras and lasers to measure the environment, and gyroscopes and
accelerometers to measure the robot’s own motion. Most of today’s robots fall into one of three
primary categories.
a. Manipulators, or Robot Arms (Figure 6.1(a)), are physically anchored to their workplace.
Example 7.2: - In a factory assembly line or on the International Space Station.

50
 Manipulator motion usually involves a chain of controllable joints, enabling such robots to
place their effectors in any position within the workplace. The most common type of industrial
robots. Some mobile manipulators are used in hospitals to assist surgeons. Few car
manufacturers could survive without robotic manipulators, and some manipulators have even
been used to generate original artwork.
b. Mobile Robots move about their environment using wheels, legs, or similar mechanisms.
They have been put to use delivering food in hospitals, moving containers at loading docks,
and similar tasks. Unmanned ground vehicles (UGVs), drive autonomously on streets,
highways, and off-road. The planetary rover shown in Figure 6.2(b) explored Mars for a
period of 3 months in 1997. Subsequent robots include the twin Mars Exploration Rovers,
which landed in 2003 and were still operating six years later. Other types of mobile robots
include unmanned air vehicles (UAVs), commonly used for surveillance, crop-spraying, and
military operations. Figure 6.2(a) shows a commonly used by the U.S. military. Autonomous
underwater vehicles (AUVs) are used in deep sea exploration. Mobile robots deliver
packages in the workplace and vacuum the floors at home.
c. Mobile Manipulator which is a combination of mobile robots and manipulator. It is often
called a Humanoid robot mimic the human torso. Figure 6.1(b) shows two early humanoid
robots, both manufactured by Honda Corp. in Japan. Mobile manipulators can apply their
effectors further afield than anchored manipulators can, but their task is made harder because
they don’t have the rigidity that the anchor provides.

Fig. 7.1 (a) An industrial robotic manipulator for stacking bags on a pallet. Image courtesy of Nachi Robotic Systems.
(b) Honda’s P3 and Asimo humanoid robots.

51
 Fig. 7.2 (a) Predator, an unmanned aerial vehicle (UAV) used by the U.S. Military. Image courtesy of General
Atomics Aeronautical Systems. (b) NASA’s Sojourner, a mobile robot that explored the surface of Mars in July 1997.

The field of robotics also includes prosthetic devices (artificial limbs, ears, and eyes for humans),
intelligent environments (such as an entire house that is equipped with sensors and effectors), and
multibody systems, wherein robotic action is achieved through swarms of small cooperating
robots.

Real robots must cope with environments that are partially observable, stochastic, dynamic, and
continuous. Many robot environments are sequential and multi-agent as well. Partial observability
and stochasticity are the result of dealing with a large, complex world. Robot cameras cannot see
around corners, and motion commands are subject to uncertainty due to gears slipping, friction, etc.
Also, the real world stubbornly refuses to operate faster than real time. In a simulated
environment, it is possible to use simple algorithms to learn in a few CPU hours from millions of
trials. In a real environment, it might take years to run these trials. Furthermore, real crashes really
hurt, unlike simulated ones. Practical robotic systems need to embody prior knowledge about the
robot, its physical environment, and the tasks that the robot will perform so that the robot can learn
quickly and perform safely.
Robot Hardware:

The agent architecture - sensors, effectors, and processors. The success of real robots depends at
least as much on the design of sensors and effectors that are appropriate for the task.
a. Sensors

52
Sensors are the perceptual interface between robot and environment. Passive sensors, such as
cameras, are true observers of the environment: they capture signals that are generated by other
sources in the environment. Active sensors, such as sonar, send energy into the environment. They
rely on the fact that this energy is reflected back to the sensor. Active sensors tend to provide more
information than passive sensors, but at the expense of increased power consumption and with a
danger of interference when multiple active sensors are used at the same time. Whether active or
passive, sensors can be divided into three types, depending on whether they sense the environment,
the robot’s location, or the robot’s internal configuration.
a. Range finders are sensors that measure the distance to nearby objects. In the early days of
robotics, robots were commonly equipped with sonar sensors. Sonar sensors emit
directional sound waves, which are reflected by objects, with some of the sound making it
back into the sensor. The time and intensity of the returning signal indicates the distance to
nearby objects. Sonar is the technology of choice for autonomous underwater vehicles.
Stereo vision relies on multiple cameras to image the environment from slightly different
viewpoints, analyzing the resulting parallax in these images to compute the range of
surrounding objects. For mobile ground robots, sonar and stereo vision are now rarely used,
because they are not reliably accurate.
Most ground robots are now equipped with optical range finders. Just like sonar sensors,
optical range sensors emit active signals (light) and measure the time until a reflection of
this signal arrives back at the sensor. This camera acquires range images like the one at up
to 60 frames per second.
Other range sensors use laser beams and special 1-pixel cameras that can be directed using
complex arrangements of mirrors or rotating elements. These sensors are called scanning
lidars (short for light detection and ranging). Scanning lidars tend to provide longer ranges
than time of flight cameras, and tend to perform better in bright day-light.
Other common range sensors include radar, which is often the sensor of choice for UAVs.
Radar sensors can measure distances of multiple kilometers. On the other extreme end of
range sensing are tactile sensors such as whiskers, bump panels, and touch-sensitive skin.
These sensors measure range based on physical contact, and can be deployed only for
sensing objects very close to the robot.

53
b. Location Sensors - it mostly uses range sensing as a primary component to determine
location. Outdoors, the Global Positioning System (GPS) is the most common solution to
the localization problem. GPS measures the distance to satellites that emit pulsed signals.
At present, there are 31 satellites in orbit, transmitting signals on multiple frequencies.
GPS receivers can recover the distance to these satellites by analyzing phase shifts. By
triangulating signals from multiple satellites, GPS receivers can determine their absolute
location on Earth to within a few meters. Differential GPS involves a second ground
receiver with known location, providing millimeter accuracy under ideal conditions.
Unfortunately, GPS does not work indoors or underwater. Indoors, localization is often
achieved by attaching beacons in the environment at known locations. Many indoor
environments are full of wireless base stations, which can help robots localize through the
analysis of the wireless signal. Underwater, active sonar beacons can provide a sense of
location, using sound to inform AUVs of their relative distances to those beacons.
c. Proprioceptive Sensors – it informs the robot of its own motion. To measure the exact
configuration of a robotic joint, motors are often equipped with shaft decoders that count
the revolution of motors in small increments. On robot arms, shaft decoders can provide
accurate information over any period of time. On mobile robots, shaft decoders that report
wheel revolutions can be used for odometry - the measurement of distance traveled.
Unfortunately, wheels tend to drift and slip, so odometry is accurate only over short
distances. External forces, such as the current for AUVs and the wind for UAVs, increase
positional uncertainty. Inertial sensors, such as gyroscopes, rely on the resistance of mass
to the change of velocity. They can help reduce uncertainty.
Other important aspects of robot state are measured by force sensors and torque sensors.
These are indispensable when robots handle fragile objects or objects whose exact shape
and location is unknown. Imagine a one-ton robotic manipulator screwing in a light bulb. It
would be all too easy to apply too much force and break the bulb. Force sensors allow the
robot to sense how hard it is gripping the bulb, and torque sensors allow it to sense how
hard it is turning. Good sensors can measure forces in all three translational and three
rotational directions. They do this at a frequency of several hundred times a second, so that
a robot can quickly detect unexpected forces and correct its actions before it breaks a light
bulb.

54
 b. Effectors
Effectors are the means by which robots move and change the shape of their bodies. To understand
the design of effectors, it will help to talk about motion and shape in the abstract, using the concept
of a degree of freedom (DOF) We count one degree of freedom for each independent direction in
which a robot, or one of its effectors, can move.
Example 7.3:
Rigid mobile robot such as an AUV has six degrees of freedom, three for its (x, y, z) location in
space and three for its angular orientation, known as yaw, roll, and pitch. These six degrees
define the kinematic state or pose of the robot. The dynamic state of a robot includes these six
plus an additional six dimensions for the rate of change of each kinematic dimension, that is,
their velocities.
For nonrigid bodies, there are additional degrees of freedom within the robot itself.
Example 7.4:
The elbow of a human arm possesses two degree of freedom. It can flex the upper arm towards
or away, and can rotate right or left. The wrist has three degrees of freedom. It can move up and
down, side to side, and can also rotate. Robot joints also have one, two, or three degrees of
freedom each. Six degrees of freedom are required to place an object, such as a hand, at a
particular point in a particular orientation. The arm has exactly six degrees of freedom, created
by five revolute joints that generate rotational motion and one prismatic joint that generates
sliding motion. You can verify that the human arm as a whole has more than six degrees of
freedom by a simple experiment: put your hand on the table and notice that you still have the
freedom to rotate your elbow without changing the configuration of your hand. Manipulators
that have extra degrees of freedom are easier to control than robots with only the minimum
number of DOFs. Many industrial manipulators therefore have seven DOFs, not six.

Robotic Perception:

Perception is the process by which robots map sensor measurements into internal representations
of the environment. Perception is difficult because sensors are noisy, and the environment is
partially observable, unpredictable, and often dynamic. In other words, robots have all the
problems of state estimation (or filtering). As a rule of thumb, good internal representations for
robots have three properties:

55
 ✓ They contain enough information for the robot to make good decisions,
✓ They are structured so that they can be updated efficiently, and
✓ They are natural in the sense that internal variables correspond to natural state variables in
the physical world.
Localization and Mapping
Localization is the problem of finding out where things are - including the robot itself. Knowledge
about where things are is at the core of any successful physical interaction with the environment.
Example 7.5: Robot manipulators must know the location of objects they seek to manipulate;
navigating robots must know where they are to find their way around.
In some situations, no map of the environment is available. Then the robot will have to acquire a
map. This is a bit of a chicken-and-egg problem: the navigating robot will have to determine its
location relative to a map it doesn’t quite know, at the same time building this map while it doesn’t
quite know its actual location. This problem is important for many robot applications, and it has
been studied extensively under the name simultaneous localization and mapping, abbreviated as
SLAM.
Not all of robot perception is about localization or mapping. Robots also perceive the temperature,
odors, acoustic signals, and so on. Many of these quantities can be estimated using variants of
dynamic Bayes networks. All that is required for such estimators are conditional probability
distributions that characterize the evolution of state variables over time, and sensor models that
describe the relation of measurements to state variables.
Planning to Move: All of a robot’s deliberations ultimately come down to deciding how to move
effectors.
The point-to-point motion problem is to deliver the robot or its end effector to a designated target
location. A greater challenge is the compliant motion problem, in which a robot moves while being
in physical contact with an obstacle. An example of compliant motion is a robot manipulator that
screws in a light bulb, or a robot that pushes a box across a table top.
We begin by finding a suitable representation in which motion-planning problems can be
described and solved. It turns out that the configuration space - the space of robot states defined by
location, orientation, and joint angles is a better place to work than the original 3D space. The path
planning problem is to find a path from one configuration to another in configuration space. The

56
complication added by robotics is that path planning involves continuous spaces. There are two
main approaches: cell decomposition and skeletonization.
a. Cell Decomposition - it decomposes the free space into a finite number of contiguous
regions, called cells. These regions have the important property that the path-planning
problem within a single region can be solved by simple means (e.g., moving along a
straight line). The path-planning problem then becomes a discrete graph-search problem.
b. Skeletonization – this algorithm reduces the robot’s free space to a one-dimensional
representation, for which the planning problem is easier. This lower-dimensional
representation is called a skeleton of the configuration space.
Each reduces the continuous path-planning problem to a discrete graph-search problem. In this
section, we assume that motion is deterministic and that localization of the robot is exact.
Subsequent sections will relax these assumptions.
Planning Uncertain Movements:
In robotics, uncertainty arises from partial observability of the environment and from the
stochastic (or unmodeled) effects of the robot’s actions. Errors can also arise from the use of
approximation algorithms such as particle filtering, which does not provide the robot with an exact
belief state even if the stochastic nature of the environment is modeled perfectly. Most of today’s
robots use deterministic algorithms for decision making.
Robotics Software Architecture:
A methodology for structuring algorithms is called software architecture. Architecture includes
languages and tools for writing programs.
Modern-day software architectures for robotics must decide how to combine reactive control and
model-based deliberative planning. In many ways, reactive and deliberate techniques have
orthogonal strengths and weaknesses. Reactive control is sensor-driven and appropriate for
making low-level decisions in real time. However, it rarely yields a plausible solution at the global
level, because global control decisions depend on information that cannot be sensed at the time of
decision making. For such problems, deliberate planning is a more appropriate choice.
Consequently, most robot architectures use reactive techniques at the lower levels of control and
deliberative techniques at the higher levels. Architectures that combine reactive and deliberate
techniques are called hybrid architectures.
Subsumption Architecture

57
It is a framework for assembling reactive controllers out of finite state machines. Nodes in these
machines may contain tests for certain sensor variables, in which case the execution trace of a
finite state machine is conditioned on the outcome of such a test. Arcs can be tagged with messages
that will be generated when traversing them, and that are sent to the robot’s motors or to other
finite state machines. Additionally, finite state machines possess internal timers (clocks) that
control the time it takes to traverse an arc. The resulting machines are referred to as augmented
finite state machines (AFSMs), where the augmentation refers to the use of clocks.
This AFSM implements a cyclic controller, whose execution mostly does not rely on
environmental feedback. The forward swing phase, however, does rely on sensor feedback. If the
leg is stuck, meaning that it has failed to execute the forward swing, the robot retracts the leg, lifts
it up a little higher, and attempts to execute the forward swing once again. Thus, the controller is
able to react to contingencies arising from the interplay of the robot and its environment.
Three-layer architecture
Hybrid architectures combine reaction with deliberation. The most popular hybrid architecture
is the three-layer architecture, which consists of a reactive layer, an executive layer, and a
deliberative layer.
a. The reactive layer provides low-level control to the robot. It is characterized by a tight
sensor–action loop. Its decision cycle is often on the order of milliseconds.
b. The executive layer (or sequencing layer) serves as the glue between the reactive layer
and the deliberative layer. It accepts directives by the deliberative layer, and sequences
them for the reactive layer. For example, the executive layer might handle a set of
via-points generated by a deliberative path planner, and make decisions as to which
reactive behavior to invoke. Decision cycles at the executive layer are usually in the order
of a second. The executive layer is also responsible for integrating sensor information into
an internal state representation. For example, it may host the robot’s localization and online
mapping routines.
c. The deliberative layer generates global solutions to complex tasks using planning.
Because of the computational complexity involved in generating such solutions, its
decision cycle is often in the order of minutes. The deliberative layer (or planning layer)
uses models for decision making. Those models might be either learned from data or
supplied and may utilize state information gathered at the executive layer.

58
Variants of the three-layer architecture can be found in most modern-day robot software systems.
The decomposition into three layers is not very strict. Some robot software systems possess
additional layers, such as user interface layers that control the interaction with people, or a
multiagent level for coordinating a robot’s actions with that of other robots operating in
the same environment.
Application Domain:
✓ Industry and Agriculture.
✓ Transportation.
✓ Robotic Cars.
✓ Health Care.
✓ Hazardous Environments.
✓ Exploration.
✓ Personal Services.
✓ Entertainment.
✓ Human Augmentation.

59
Review Questions
1. What is communication according to AI?
2. What are the types of communication in AI?
3. What is acting rationally in AI?
4. How AI is used in communication?
5. What defines communication?
6. What is communication and types?
7. What is important of communication?
8. What are the elements of communication?
9. What is the difference between thinking rationally and acting rationally approach to AI?
10. Who is the father of artificial intelligence?
11. What is perception and action in AI?
12. What is acting in AI?
13. What do you mean by acting rationally?
14. What is perception in machine learning?
15. What is the connection between perception and action?
16. How does AI perceive?
17. What are perception algorithms?
18. What is perception in neural network?