Artificial Intelligence-[SESIZC444]

CS 2-Agents &Environment
BITS Pilani Dr. Vijayalakshmi Anand
Pilani Campus
Course Plan

M1 Introduction to AI
M2 Problem Solving Agent using Search
M3 Game Playing, Constraint Satisfaction Problem
M4 Knowledge Representation using Logics
M5 Probabilistic Representation and Reasoning
M6 Reasoning over time, Reinforcement Learning

BITS Pilani, Pilani Campus

Module 1 : Introduction to AI

A. Overview of AI & Applications

B. Intelligent Agents

C. Task Environment

BITS Pilani, Pilani Campus

Design Principles & Techniques

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

AI Agents and Environment

An AI system is composed of
 an agent
 an environment

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

What is agent?

Agent is anything that can perceive its environment

through sensors and acts upon the environment
through effectors .

Example of agents
 Robotic
 Human
 Software

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Important terminologies

1.Percept-It is a perceptual inputs at a given instance

2.Agent program is an implementation of an agent
function.
3.Agent function is a map from the percept
sequence(history of all that an agent has perceived to
date) to an action. 
4.Performance measure-It is criteria how successful
an agent is
5.Action-Agent performs after any given sequence of
percepts
6.Effectors- can be legs, wheels, arms, fingers, wings,
fins, and display screen

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

AI system architecture

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

 Real time example

Performance measure: An objective criterion for success of

an agent's behaviour

E.g., performance measure of a vacuum-cleaner agent

» amount of dirt cleaned up
» amount of time taken
» amount of electricity consumed
» amount of noise generated, etc.
BITS Pilani, Pilani Campus
Contd..

BITS Pilani, Pilani Campus

PEAS Environment
Design on what an application wants the
agent to do in the environment

Agent Performance Environme Sensors Actuators

nt
Medical Healthy Patient, Keyboard entry Display of
diagnosis patient, hospital, of symptoms, questions, tests,
system reduced costs staff findings, diagnosis,
patient’s treatments,
answers referrals

Satellite Correct image Downlink Color pixel Display of scene

Image categorization from analysis categorization
analysis orbiting
system satellite
Interactive Student’s Set of Keyboard entry Display of
English tutor score on test students, exercises,
testing suggestions,
agency corrections
BITS Pilani, Pilani Campus
PEAS Environment Design on what an application wants the agent
to do in the environment

Agent Performan Environ Sensors Actuators

ce ment
Automate Safe, fast, Roads, Cameras, Steering
d taxi legal, other sonar, wheel,
driver comfortabl traffic, speedometer accelerator,
e trip, pedestria , GPS, brake,
maximize ns, odometer, signal, horn
profits customer engine
s sensors,
keyboard

BITS Pilani, Pilani Campus

Types of agents

 Simple Reflex Agents

 Model-Based Reflex Agents
 Goal-Based Agents
 Utility-Based Agents
 Learning Agent

BITS Pilani, Pilani Campus

Simple reflex agent

 Simple
 No calculation or solve complicated problems
 Fully observable environment
 Works on condition-action rule

BITS Pilani, Pilani Campus

Model Based reflex agents
 Partially observable environment
 Store perceive history

BITS Pilani, Pilani Campus

Goal based agent
 Expansion of model based reflex agent
 Mainly focused on its Goal
 Searching and planning
 Agent is more flexible

BITS Pilani, Pilani Campus

Utility based agent

 Main focus is on utility

 Utility function
 Deals with happy and unhappy state

BITS Pilani, Pilani Campus

Learning agent
 Learning element: It is responsible for making
improvements by learning from the environment
 Critic: The learning element takes feedback from critics
which describes how well the agent is doing with respect to a
fixed performance standard.

BITS Pilani, Pilani Campus

 Performance element: It is responsible for selecting
external action
 Problem Generator: This component is responsible for
suggesting actions that will lead to new and informative
experiences.

BITS Pilani, Pilani Campus

Environment

BITS Pilani, Pilani Campus

Task Environment

 A rational agent is built to solve a specific task. Each

such task would then have a different environment which
we refer to as Task Environment

 Based on the applicability of each technique for agent

implementation its task environment design is
determined by multiple dimension

BITS Pilani, Pilani Campus

Sensor based Task
environment
Observability : Fully observable Vs Partial observable

Poker Chess

BITS Pilani, Pilani Campus

Action Based Task Environment

 Dependency : Episodic Vs Sequential

chech chess game

Mail sorting system

Pick and place

robot system

BITS Pilani, Pilani Campus

State Based Task Environment

 No.of.State : Discrete Vs Continuous

BITS Pilani, Pilani Campus

Action & State Based:

 State Determinism : Deterministic Vs Stochastic |

Strategic
(If the environment is deterministic except for the actions of
other agents, then the environment is strategic)

BITS Pilani, Pilani Campus

Agent Based:

> Cardinality : Single Vs MultiAgent

BITS Pilani, Pilani Campus

Action & State Based:

 Change in Time : Static Vs Dynamic

 (The environment is semi dynamic if the environment
itself does not change with the passage of time but the
agent's performance score does)

BITS Pilani, Pilani Campus

Task Environment

Sensor Based:
 Observability : Full Vs Partial

Action Based:
 Dependency : Episodic Vs Sequential

State Based:
 No.of.State : Discrete Vs Continuous

Agent Based:
> Cardinality : Single Vs MultiAgent

Action & State Based:

 State Determinism : Deterministic Vs Stochastic | Strategic
 Change in Time : Static Vs Dynamic

BITS Pilani, Pilani Campus

Task Environment

Task Fully vs Single Deterministi Episodic Static vs Discrete vs

Environment Partially vs c vs vs Dynamic Continuou
Observabl Multi- Stochastic Sequential s
e Agent
Medical Partially Single Stochastic Sequential Dynamic Continuou
diagnosis s
system
Satellite Fully Single Deterministi Episodic Static Continuou
Image c s
Analysis
System
Interactive Partially Multi Stochastic Sequential Dynamic Discrete
English tutor

BITS Pilani, Pilani Campus

Task Environment

Task Fully vs Single Deterministic Episodic vs Static vs Discrete vs

Environm Partially vs vs Stochastic Sequential Dynamic Continuou
ent Observable Multi- s
Agent
Taxi P M S S D C
Driving

BITS Pilani, Pilani Campus

Introduction to learning

 Supervised learning
 Unsupervised learning
 Reinforcement learning

BITS Pilani, Pilani Campus

Supervised
learning:classification
Given a collection of records (training set )
– Each record contains a set of attributes, one of the attributes is
the class.
Find a model for class attribute as a function of
the values of other attributes.
Goal: previously unseen records should be
assigned a class as accurately as possible.
– A test set is used to determine the accuracy of the model.
Usually, the given data set is divided into training and test sets,
with training set used to build the model and test set used to
validate it.

BITS Pilani, Pilani Campus

 Classification Example
c al c al us
i i o
gor gor i nu
te te nt ss
a a o a
c c c cl

Test
Set

Training
Learn
Set Classifier Model
 Classification: Application 1

Direct Marketing
– Goal: Reduce cost of mailing by targeting a set of consumers likely to buy a new cell-
phone product.
– Application:
Retail industry-by providing useful and accurate trends.
Credit company –to identify customers to be interested

– Approach:
• Use the data for a similar product introduced before.
• We know which customers decided to buy and which decided
otherwise. This {buy, don’t buy} decision forms the class attribute.
• Collect various demographic, lifestyle, and company-interaction
related information about all such customers.
– Type of business, where they stay, how much they earn, etc.
• Use this information as input attributes
Fromto learn
[Berry a classifier
& Linoff] Data model.
Mining Techniques, 1997

BITS Pilani, Pilani Campus

 Classification: Application 2

Fraud Detection
– Goal: Predict fraudulent cases in credit card transactions.
– Approach:
• Use credit card transactions and the information on
its account-holder as attributes.
– When does a customer buy, what does he buy, how often
he pays on time, etc
• Label past transactions as fraud or fair
transactions. This forms the class attribute.
• Learn a model for the class of the transactions.
• Use this model to detect fraud by observing credit
card transactions on an account.

BITS Pilani, Pilani Campus

 Classification: Application 3

Customer Attrition/Churn:
– Goal: To predict whether a customer is likely to be lost to a competitor.
– Approach:
• Use detailed record of transactions with each of
the past and present customers, to find attributes.
– How often the customer calls, where he calls, what time-
of-the day he calls most, his financial status, marital
status, etc.
• Label the customers as loyal or disloyal.
• Find a model for loyalty.
From [Berry & Linoff] Data Mining Techniques, 1997

BITS Pilani, Pilani Campus

 Classification: Application 4

Sky Survey Cataloging

– Goal: To predict class (star or galaxy) of sky objects, especially visually faint ones,
based on the telescopic survey images (from Palomar Observatory).
– 3000 images with 23,040 x 23,040 pixels per image.
– Approach:
• Segment the image.
• Measure image attributes (features) - 40 of them
per object.
• Model the class based on these features.
• Success Story: Could find 16 new high red-shift
quasars, some of the farthest objects that are
From [Fayyad, et.al.] Advances in Knowledge Discovery and Data Mining, 1996
difficult to find!

BITS Pilani, Pilani Campus

 Unsupervised learning -Clustering

Given a set of data points, each having a set of attributes,

and a similarity measure among them, find clusters such
that
– Data points in one cluster are more similar to one another.
– Data points in separate clusters are less similar to one another.

Similarity Measures:
– Euclidean Distance if attributes are continuous.
– Other Problem-specific Measures.

BITS Pilani, Pilani Campus

 Illustrating Clustering

Euclidean Distance Based

Clustering in 3-D space

BITS Pilani, Pilani Campus

 Clustering: Application 1

Market Segmentation:
– Goal: subdivide a market into distinct subsets of customers where any subset may
conceivably be selected as a market target to be reached with a distinct marketing
mix.
– Approach:
• Collect different attributes of customers based on their
geographical and lifestyle related information.
• Find clusters of similar customers.
• Measure the clustering quality by observing buying
patterns of customers in same cluster vs. those from
different clusters.

BITS Pilani, Pilani Campus

 Clustering: Application 2

Document Clustering:
– Goal: To find groups of documents that are similar to
each other based on the important terms appearing in
them.
– Approach: To identify frequently occurring terms in
each document. Form a similarity measure based on
the frequencies of different terms. Use it to cluster.
– Gain: Information Retrieval can utilize the clusters to
relate a new document or search term to clustered
documents.

BITS Pilani, Pilani Campus

Reinforcement learning

Reinforcement learning is a type of machine learning that

enables the use of artificial intelligence in complex
applications from video games to robotics, self-driving
cars, and more.

example
Basic diagram for reinforcement learning
algorithm

BITS Pilani, Pilani Campus

Real time examples

 Self driving cars

 Industry automation
 Trading and finance
 NLP
 Gaming

BITS Pilani, Pilani Campus

Expert system

BITS Pilani, Pilani Campus

 Human Experts
US: 1 radiologist for every 10,000

India: 1 radiologist for every 1,00,0001

Many diseases can be positively

impacted if diagnosed early2

Lack of radiologists delay diagnosis

1 - https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2747434/
2 – Early diagnosis saves lives, cuts treatment costs

BITS Pilani, Pilani Campus

 Expert Systems
Solution:
– Encode the expert’s knowledge into machine readable
representation
– Using that knowledge, build systems that can solve
problems which would otherwise require a human
expert

Buzz Words
– Expert’s Knowledge
– Representation
– Solving problems

BITS Pilani, Pilani Campus

Expert Systems: Knowledge
Expert’s Knowledge
 Set of facts, rules, procedures and heuristics used by
experts in solving problems

 Heuristics are the practical ways of solving problems

gained with experience. E.g., a car mechanic might know
the problem with a car just based on engine sound.

 Not to be confused with data, E.g., doctor treating a

patient uses Knowledge & Data

BITS Pilani, Pilani Campus

Expert System: Knowledge Representation

Knowledge Representation
– Expert Knowledge is represented in Symbols
that can be understood by programs
– Representation schemes: Predicate Logic,
Frames and associative networks, Fuzzy
Logic, Object oriented methods

BITS Pilani, Pilani Campus

Expert System: Knowledge Representation

Knowledge Representation
– E.g.,
• “Spot is a dog” is an English sentence
• If represented in logic, “dog(Spot)”
• Suppose, we have a logic representation of
fact that “all dogs have tails”

• Using deductive logic, we can generate

BITS Pilani, Pilani Campus

 Expert System: Knowledge Base

Knowledge Base: All such knowledge when converted into symbolic

representation along with relations form a knowledge base

Sample Knowledge Base of Family Relationships (in LISP):

Facts are represented as a1, a2, a3
– E.g., a1 (male bob) , i.e., bob is a male
Rules are represented as r1, r2, r3
– E.g., r1 ((husband ?x ?y))  (male ?x) , i.e., if ?x is husband
of ?y, then ?x is male
– r2 ((mother ?x ?y) (husband ?z ?x))  (father ?z ?y) , i.e., the
two facts on LHS (mother and husband) when satisfied in
conjunction then RHS is true

BITS Pilani, Pilani Campus

Expert System: Sample Knowledge
Base
( (a1 (male bob)) .. (r4 ((mother ?x ?y) (husband ?z ?x))
(a2 (female sue))  (father ?z ?y))
(a3 (male sam)) (r5 ((father ?x ?z) (mother ?y ?z)
 (husband ?x ?y))
(a4 (male bill))
(r6 ((father ?x ?z) (mother ?y ?z)
(a5 (female pam))  (wife ?y ?x))
(r1 ((husband ?x ?y)) (r7 ((father ?x ?y) (father ?y ?z)
 (male ?x))  (grandfather ?x ?z)) )
(r2 ((wife ?x ?y))
 (female ?x))
(r3 ((wife ?x ?y))
 (husband ?y ?x)) …

BITS Pilani, Pilani Campus

 Expert System: Inference

Inference: The act of using the symbolic representation of

knowledge in deriving conclusions given user’s input

Inferring process done in three stages:

1. Match – User’s input is compared with facts and rules
in Knowledge base
2. Select – All appropriate facts and rules matched are
put together and one of the rules is selected. Criteria
can be #conjuncts on left or smallest rule number.
3. Execute – The selected rule is executed and resulting
action is displayed to user

BITS Pilani, Pilani Campus

Expert System: Inference

Example 1:
User’s Input - (father bob sam) (mother sue sam)
Match step: r5 and r6 rules are matched and their conclusions
(husband bob sue) and (wife sue bob) are put in a conflict set
Select step: Simply select the first match, i.e., (husband bob
sue)
Execute step: Trigger a message to user and probe further
questions and repeat

Forward Chaining: The input is matched from LHS and the RHS
is executed

BITS Pilani, Pilani Campus

 Expert System: Inference

Example 2:
Suppose, we added (a6 (father sam bill)) and (a7 (father
bill pam)) to knowledge base
User Input: Who is the grandfather of Pam?  (grandather
?x pam)
Match step: (r7 ((father ?x ?y) (father ?y ?z) 
(grandfather ?x pam))
– (father ?x ?y) (father ?y pam)
– Substituting with a7  (father ?x bill) (father bill pam)
– Substituting with a6  (father sam bill) (father bill pam)
– (grandfather sam pam)

Backward Chaining: RHS is instantiated first, then the

LHS becomes sub goals and they are matched with
BITS Pilani, Pilani Campus
 Expert System: Knowledge
Acquisition
 Acquisition and encoding of requisite domain
knowledge
 Expert sources can be experts in a field, journal
articles, texts, reports, etc.
 Tedious job, can take several years sometimes
and also costly
 Experts sometimes cannot articulate their
problem solving process

BITS Pilani, Pilani Campus

Expert System – Knowledge Acquisition

–Knowledge Engineers – intermediaries between experts and systems

• Conduct extensive interviews with domain experts
• During the interview, experts are asked to solve problems and explain their solution
• Codes the knowledge into rules or some other representation
• These encoded rules are tested, reviewed and errors are corrected till sufficient
accuracy

Domain Knowledge System Knowledge

Expert Engineer Builder Base

BITS Pilani, Pilani Campus

Expert System – Explainability

Builds trust in the system when it can explain its

reasoning process
Two possible explanations
– How did the system reach a particular
conclusion
– Why would a system need a particular
information in order to complete a step
–Behavior of an expert system can be explained
by tracing the chain of rules that were fired

BITS Pilani, Pilani Campus

Expert System - Explainability

How Query?
– How did you reach this conclusion?
– The sequence of rules that led to the
conclusion are displayed to the user
– E.g., Why is Sam the grandfather of Pam?
• Pam’s father is Bill and Bill’s father is Sam.
As per Rule no. 7, it infers that Sam is the
grandfather of Pam.

BITS Pilani, Pilani Campus

Expert Systems – Maintenance
• Most difficult task: maintaining a consistent but complete
set of rules in a knowledge base

• Very easy ways of allowing knowledge to be modified to

keep the knowledge base consistent

• Intuitive User Interface with User testing the current

version of knowledge base and suggesting changes

BITS Pilani, Pilani Campus

Module 2 : Problem Solving Agent using
Search

A. Uninformed Search

B. Informed Search

C. Heuristic Functions

D. Local Search Algorithms & Optimization Problems

BITS Pilani, Pilani Campus

Problem Solving Agents
An agent that tries to come up with a sequence of actions
that will bring the environment into a desired state.
Phases of Solution Search by PSA

“a problem- Goal
Formulatio
solving refers to n
a state where we
Problem
wish to reach to Formulatio
n
a definite goal
from a present Search
state or condition Phase

Execution
Phase BITS Pilani, Pilani Campus
Problem Solving Agents-Goal
formulation
 first and simplest step in problem-solving.
 organizes the steps/sequence required to formulate
one goal out of multiple goals as well as actions to
achieve that goal.
 current situation and the agent’s performance measure
is the first step in problem solving.

BITS Pilani, Pilani Campus

Problem solving Agents-Problem
formulation
 Initial State: Start point of problem
 Final State: The finish point of problem.
Aka Goal or solution state
 States: Total states in problem
 Transition Model: How one can shift
from one state to another
 Actions: Actions set, used to move from
one state to another
 Path Cost: What is total effort (cost) from
initial state to final state

BITS Pilani, Pilani Campus

Problem Solving Agents –Search
Phase

 It identifies all the best possible sequence of

actions to reach the goal state from the current
state.
 It takes a problem as an input and returns
solution as its output.

BITS Pilani, Pilani Campus

Problem solving agents –
execution phase
It executes the best optimal solution from the searching
algorithms to reach the goal state from the current state.

BITS Pilani, Pilani Campus

Problem Solving Agents –
example

Initial State –E.g., In(Arad)

Possible Actions – ACTIONS(s)  {Go(Sibiu), Go(Timisoara), Go(Zerind)}
Transition Model – RESULT( In(Arad), Go(Sibiu) ) = In(Sibiu)
Goal Test – IsGoal( In(Bucharest) ) = Yes
Path Cost – cost( In(Arad), go(Sibiu)) = 140 kms

BITS Pilani, Pilani Campus

N - Queen

BITS Pilani, Pilani Campus

Vacuum World Problem

BITS Pilani, Pilani Campus

 Example Problem Formulation

Vacuum World 8 – Queen Problem Travelling Problem

Initial State Any No Queen on board Based on the problem

Possible [Move Left, Move Add a Queen to Take a flight | Train |

Actions Right, Suck] any empty square
Transition [A, ML] = [B , Dirty] [A1, B2] = [FAIL] [A, Go(A->S)] = [S]
Model [A, ML] = [B, Clean] [A1, B3] = [SAFE]

Goal Test Is all room clean? All Queen Safe Is current = B

[A, Clean] [B, Clean] (destination)
Path Cost No of steps in path No of Moves done, Cost + Time + Quality
backtracking

BITS Pilani, Pilani Campus

Searching for solutions

BITS Pilani, Pilani Campus

 In(Arad)

Go(Sibiu) Go(Timisoara) Go(Zerind)

In(Sibiu) In(Timisoara) In(Zerind)

Go(Arad) Go(Fagaras) Go(Oradea) Go(Rimnicu Vilcea)

In(Arad) In(Fagaras) In(Oradea) In(Rimnicu Vilcea)

Leaf Nodes
(no children yet)

BITS Pilani, Pilani Campus

Terminologies

 Nodes
 States
 Frontier | Fringes
 Search Strategy : LIFO | FIFO | Priority Queue
 Performance Metrics

 Completeness
 Optimality
 Time Complexity
 Space Complexity
 Algorithm Terminology
- d Depth of a node - m – maximum
- b Branching factor - C* - Optimal Cost
- n – nodes - E – least Cost
- l – level of a node - N –total node generated

BITS Pilani, Pilani Campus

Uninformed Search
BFS & its Variants
Breadth First Search (BFS)

Generate all nodes at a given depth

before proceeding to deeper nodes

BITS Pilani, Pilani Campus

Breadth First Search (BFS)

BITS Pilani, Pilani Campus

BFS – Uninformed Problem

(1)

BITS Pilani, Pilani Campus

 Breadth First Search – Evaluation

Why is Space Complexity a big problem? Imagine a problem with

– branching factor b = 10
– generates 1 million nodes/sec
– Each node requires 1KB

BITS Pilani, Pilani Campus

Breadth First Search – Evaluation

Complete – If the shallowest goal node is at a depth d, BFS will eventually find it by
generating all shallower nodes
Optimal – Not necessarily. Optimal if path cost is equal
Time Complexity – b - branching factor, d – depth
Space Complexity –

BITS Pilani, Pilani Campus

Thank you

BITS Pilani, Pilani Campus

Any Questions?

BITS Pilani, Pilani Campus