FUNDAMENTALS IN AI and ML

Course Code : CSA2001

Course Type :LTP
Credits : 4
Course Objectives:

❖ To understand the various characteristics of Intelligent agents

❖ To learn about the different search strategies in AI
❖ To learn to represent knowledge in solving AI problems
❖ To understand the different ways of designing software agents and Prolog
❖ To learn the Machine Learning Techniques
Text Book(s)& References

1. S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, Third Edition, 2009.
• References:
1. Bratko, Prolog: Programming for Artificial Intelligence, Fourth edition, Addison-Wesley Educational
Publishers Inc., 2011.
2. Stephen Marsland, Machine Learning – An algorithmic perspective, Second Edition,
3. Chapman and Hall/CRC Machine learning and Pattern Recognition Series, 2014.
UNIT I INTRODUCTION

• Introduction–Definition - Future of Artificial Intelligence Characteristics of Intelligent Agents - Typical

Intelligent Agents – Problem Solving Approach to Typical AI problems (6 hours)
Artificial Intelligence
Artificial Intelligence
• Artificial Intelligence is composed of two
words Artificial and Intelligence, where Artificial defines "man-
made," and intelligence defines "thinking power", hence AI means "a
man-made thinking power.“
• It is a branch of computer science by which we can create intelligent
machines which can behave like a human, think like humans, and able
to make decisions.
Artificial Intelligence
• Artificial Intelligence exists when a machine can have human based
skills such as learning, reasoning, and solving problems
• With Artificial Intelligence you do not need to preprogram a machine
to do some work, despite that you can create a machine with
programmed algorithms which can work with own intelligence, and
that is the awesomeness of AI.
• It is believed that AI is not a new technology, and some people says
that as per Greek myth, there were Mechanical men in early days
which can work and behave like humans.
Why Artificial Intelligence?

• With the help of AI, you can create such software or devices which
can solve real-world problems very easily and with accuracy such as
health issues, marketing, traffic issues, etc.
• With the help of AI, you can create your personal virtual Assistant,
such as Cortana, Google Assistant, Siri, etc.
• With the help of AI, you can build such Robots which can work in an
environment where survival of humans can be at risk.
• AI opens a path for other new technologies, new devices, and new
Opportunities.
Goals of Artificial Intelligence

[Link] human intelligence

[Link] Knowledge-intensive tasks
[Link] intelligent connection of perception and action
[Link] a machine which can perform tasks that requires human
intelligence such as:
1. Proving a theorem
2. Playing chess
3. Plan some surgical operation
4. Driving a car in traffic
[Link] some system which can exhibit intelligent behavior, learn new
things by itself, demonstrate, explain, and can advise to its user.
What Comprises to Artificial Intelligence?
History of Artificial Intelligence
Year Milestone / Innovation

Karel Čapek plays named “Rossum’s Universal Robots,

1923
the first use of the word “robot” in English.

1943 Foundations for neural networks laid.

Isaac Asimov, a Columbia University alumni, use the
1945
term Robotics.

John McCarthy first used the term Artificial

1956 Intelligence. Demonstration of the first running AI
program at Carnegie Mellon University.

Danny Bobrow’s dissertation at MIT showed how

1964
computers could understand natural language.

Scientists at Stanford Research Institute Developed

1969 Shakey. A robot equipped with locomotion and
problem-solving.
 The world’s first computer-controlled autonomous
1979
vehicle, Stanford Cart, was built.
1990 Significant demonstrations in machine learning
The Deep Blue Chess Program beat the then world
1997
chess champion, Garry Kasparov.
Interactive robot pets have become commercially
2000 available. MIT displays Kismet, a robot with a face
that expresses emotions.
AI came into the Business world in the year 2006.
2006 Companies like Facebook, Netflix, Twitter started
using AI.
Google has launched an Android app feature called
2012 “Google now”, which provides the user with a
prediction.
The “Project Debater” from IBM debated complex
2018 topics with two master debaters and performed
exceptionally well.
Subfields of Artificial Intelligence
Subfields of Artificial Intelligence

• Machine Learning:
• Machine learning is the art of studying algorithms that learn from examples and
experiences.
• Machine learning is based on the idea that some patterns in the data were
identified and used for future predictions.
• The difference from hardcoding rules is that the machine learns to find such rules.
• Deep Learning:
• Deep learning is a sub-field of machine learning.
• Deep learning does not mean the machine learns more in-depth knowledge; it uses
different layers to learn from the data.
• The depth of the model is represented by the number of layers in the model. For
instance, the Google LeNet model for image recognition counts 22 layers.
Subfields of Artificial Intelligence
• Natural Language Processing:
• A neural network is a group of connected I/O units where each connection has a weight associated with
its computer programs. It helps you to build predictive models from large databases.
• This model builds upon the human nervous system.
• You can use this model to conduct image understanding, human learning, computer speech, etc.
• Expert Systems:
• An expert system is an interactive and reliable computer-based decision-making system that uses facts
and heuristics to solve complex decision-making problems.
• It is also considered at the highest level of human intelligence.
• The main goal of an expert system is to solve the most complex issues in a specific domain.
• Fuzzy Logic:
• Fuzzy Logic is defined as a many-valued logic form that may have truth values of variables in any real
number between 0 and 1.
• It is the handle concept of partial truth. In real life, we may encounter a situation where we can’t decide
whether the statement is true or false.
AI has three different levels

1) Narrow AI: A artificial intelligence is said to be narrow when the

machine can perform a specific task better than a human. The current
research of AI is here now
2) General AI: An artificial intelligence reaches the general state when
it can perform any intellectual task with the same accuracy level as a
human would
3) Active AI: An AI is active when it can beat humans in many tasks
Artificial Intelligence Machine Learning Data Science
Includes Machine Learning. Subset of Artificial Intelligence. Includes various Data Operations.

Artificial Intelligence combines large Data Science works by sourcing,

Machine Learning uses efficient
amounts of data through iterative cleaning, and processing data to extract
programs that can use data without
processing and intelligent algorithms to meaning out of it for analytical
being explicitly told to do so.
help computers learn automatically. purposes.

Some of the popular tools used by Data

Some of the popular tools that AI uses The popular tools that Machine
Science are-
are- Learning makes use of are-
1. SAS
1. TensorFlow 1. Amazon Lex
2. Tableau
2. Scikit Learn 2. IBM Watson Studio
3. Apache Spark
3. Keras 3. Microsoft Azure ML Studio
4. MATLAB

Artificial Intelligence uses logic and Machine Learning uses statistical Data Science deals with structured and
decision trees. models. unstructured data.

Recommendation Systems such as

Chatbots, and Voice assistants are Fraud Detection and Healthcare analysis
Spotify, and Facial Recognition are
popular applications of AI. are popular examples of Data Science.
popular examples.
 Difference between Machine Learning and Deep Learning
Parameter Machine Learning Deep Learning
Excellent performances on a Excellent performance on a big
Data Dependencies
small/medium dataset dataset
Requires powerful machine,
preferably with GPU: DL performs
Hardware dependencies Work on a low-end machine.
a significant amount of matrix
multiplication
Need to understand the features No need to understand the best
Feature engineering
that represent the data feature that represents the data
Up to weeks. Neural Network
Execution time From few minutes to hours needs to compute a significant
number of weights
Some algorithms are easy to
interpret (logistic, decision tree),
Interpretability Difficult to impossible
some are almost impossible (SVM,
XGBoost)
When to use ML or DL?

Parameter Machine Learning Deep Learning

Training dataset Small Large

Choose features Yes No

Number of algorithms Many Few

Training time Short Long

Criteria Supervised ML Unsupervised ML Reinforcement ML

Trained using unlabelled data Works on interacting with the

Definition Learns by using labelled data
without any guidance. environment

Type of data Labelled data Unlabelled data No – predefined data

Type of problems Regression and classification Association and Clustering Exploitation or Exploration

Supervision Extra supervision No supervision No supervision

Linear Regression, Logistic K – Means, Q – Learning,

Algorithms
Regression, SVM, KNN etc. C – Means, Apriori SARSA

Aim Calculate outcomes Discover underlying patterns Learn a series of action

Recommendation System, Self Driving Cars, Gaming,

Application Risk Evaluation, Forecast Sales
Anomaly Detection Healthcare
Agents in Artificial Intelligence

• An agent can be anything that perceive its environment through sensors and
act upon that environment through actuators. An Agent runs in the cycle
of perceiving, thinking, and acting. An agent can be:
• Human-Agent: A human agent has eyes, ears, and other organs which work
for sensors and hand, legs, vocal tract work for actuators.
• Robotic Agent: A robotic agent can have cameras, infrared range finder,
NLP for sensors and various motors for actuators.
• Software Agent: Software agent can have keystrokes, file contents as
sensory input and act on those inputs and display output on the screen.
• Hence the world around us is full of agents such as thermostat, cellphone,
camera, and even we are also agents.
Agents in Artificial Intelligence
• Sensor: Sensor is a device which detects the
change in the environment and sends the
information to other electronic devices. An
agent observes its environment through
sensors.
• Actuators: Actuators are the component of
machines that converts energy into motion.
The actuators are only responsible for moving
and controlling a system. An actuator can be
an electric motor, gears, rails, etc.
• Effectors: Effectors are the devices which
affect the environment. Effectors can be legs,
wheels, arms, fingers, wings, fins, and display
screen.
•
Intelligent Agents:

• An intelligent agent is an autonomous entity which act upon an

environment using sensors and actuators for achieving goals. An
intelligent agent may learn from the environment to achieve their
goals. A thermostat is an example of an intelligent agent.
• Following are the main four rules for an AI agent:
• Rule 1: An AI agent must have the ability to perceive the
environment.
• Rule 2: The observation must be used to make decisions.
• Rule 3: Decision should result in an action.
• Rule 4: The action taken by an AI agent must be a rational action.
PEAS Representation

• PEAS is a type of model on which an AI agent works upon. When we

define an AI agent or rational agent, then we can group its properties
under PEAS representation model. It is made up of four words:
• P: Performance measure
• E: Environment
• A: Actuators
• S: Sensors
PEAS Representation

• Performance: Safety, time, legal

drive, comfort
• Environment: Roads, other
vehicles, road signs, pedestrian
• Actuators: Steering, accelerator,
brake, signal, horn
• Sensors: Camera, GPS,
speedometer, odometer,
accelerometer, sonar.
 Example of Agents with their PEAS
representation
Agent Performance measure Environment Actuators Sensors

1. Medical Diagnose •Healthy patient •Patient •Tests Keyboard

•Minimized cost •Hospital •Treatments (Entry of symptoms)
•Staff

2. Vacuum Cleaner •Cleanness •Room •Wheels •Camera

•Efficiency •Table •Brushes •Dirt detection sensor
•Battery life •Wood floor •Vacuum Extractor •Cliff sensor
•Security •Carpet •Bump Sensor
•Various obstacles •Infrared Wall Sensor

3. Part -picking Robot •Percentage of parts in •Conveyor belt with parts, •Jointed Arms •Camera
correct bins. •Bins •Hand •Joint angle sensors.
Agent Environment in AI

• An environment is everything in the world which surrounds the agent,

but it is not a part of an agent itself. An environment can be described
as a situation in which an agent is present.
• The environment is where agent lives, operate and provide the agent
with something to sense and act upon it. An environment is mostly
said to be non-feministic.
Features of Environment

• As per Russell and Norvig, an environment can have various features from
the point of view of an agent:
[Link] observable vs Partially Observable
[Link] vs Dynamic
[Link] vs Continuous
[Link] vs Stochastic
[Link]-agent vs Multi-agent
[Link] vs sequential
[Link] vs Unknown
[Link] vs Inaccessible
1. Fully observable vs Partially Observable:

• If an agent sensor can sense or access the complete state of an

environment at each point of time then it is a fully
observable environment, else it is partially observable.
• A fully observable environment is easy as there is no need to maintain
the internal state to keep track history of the world.
• An agent with no sensors in all environments then such an
environment is called as unobservable.
Deterministic vs Stochastic:

• If an agent's current state and selected action can completely determine

the next state of the environment, then such environment is called a
deterministic environment.
• A stochastic environment is random in nature and cannot be
determined completely by an agent.
• In a deterministic, fully observable environment, agent does not need
to worry about uncertainty.
Episodic vs Sequential:

• In an episodic environment, there is a series of one-shot actions, and

only the current percept is required for the action.
• However, in Sequential environment, an agent requires memory of
past actions to determine the next best actions.
Single-agent vs Multi-agent

• If only one agent is involved in an environment, and operating by

itself then such an environment is called single agent environment.
• However, if multiple agents are operating in an environment, then
such an environment is called a multi-agent environment.
• The agent design problems in the multi-agent environment are
different from single agent environment.
Static vs Dynamic:

• If the environment can change itself while an agent is deliberating then

such environment is called a dynamic environment else it is called a
static environment.
• Static environments are easy to deal because an agent does not need to
continue looking at the world while deciding for an action.
• However for dynamic environment, agents need to keep looking at the
world at each action.
• Taxi driving is an example of a dynamic environment whereas
Crossword puzzles are an example of a static environment.
Discrete vs Continuous:

• If in an environment there are a finite number of percepts and actions

that can be performed within it, then such an environment is called a
discrete environment else it is called continuous environment.
• A chess gamecomes under discrete environment as there is a finite
number of moves that can be performed.
• A self-driving car is an example of a continuous environment.
Known vs Unknown

• Known and unknown are not actually a feature of an environment, but

it is an agent's state of knowledge to perform an action.
• In a known environment, the results for all actions are known to the
agent. While in unknown environment, agent needs to learn how it
works in order to perform an action.
• It is quite possible that a known environment to be partially observable
and an Unknown environment to be fully observable.
Accessible vs Inaccessible

• If an agent can obtain complete and accurate information about the

state's environment, then such an environment is called an Accessible
environment else it is called inaccessible.
• An empty room whose state can be defined by its temperature is an
example of an accessible environment.
• Information about an event on earth is an example of Inaccessible
environment.
Examples of Problems in Artificial Intelligence

• Travelling Salesman Problem

• Tower of Hanoi Problem
• Water-Jug Problem
• N-Queen Problem
• Chess
• Sudoku
• Crypt-arithmetic Problems
• Magic Squares
• Logical Puzzles and so on.
Search Algorithm Terminologies

• Search: Searching is a step by step procedure to solve a search-problem in a given search

space. A search problem can have three main factors:
• Search Space: Search space represents a set of possible solutions, which a system may have.
• Start State: It is a state from where agent begins the search.
• Goal test: It is a function which observe the current state and returns whether the goal state is
achieved or not.
• Search tree: A tree representation of search problem is called Search tree. The root of the
search tree is the root node which is corresponding to the initial state.
• Actions: It gives the description of all the available actions to the agent.
• Transition model: A description of what each action do, can be represented as a
transition model.
• Path Cost: It is a function which assigns a numeric cost to each path.
• Solution: It is an action sequence which leads from the start node to the goal node.
• Optimal Solution: If a solution has the lowest cost among all solutions.
Properties of search algorithms

• Completeness
• A search algorithm is said to be complete when it gives a solution or returns any
solution for a given random input.
• Optimality
• If a solution found is best (lowest path cost) among all the solutions identified, then
that solution is said to be an optimal one.
• Time complexity
• The time taken by an algorithm to complete its task is called time complexity. If the
algorithm completes a task in a lesser amount of time, then it is an efficient one.
• Space complexity
• It is the maximum storage or memory taken by the algorithm at any time while
searching.
Types of search algorithms:
Uninformed Search Algorithms

• Uninformed search is a class of general-purpose search algorithms which

operates in brute force-way.
• Uninformed search algorithms do not have additional information about
state or search space other than how to traverse the tree, so it is also called
blind search.
• Following are the various types of uninformed search algorithms:
[Link]-first Search
[Link]-first Search
[Link]-limited Search
[Link] deepening depth-first search
[Link] cost search
[Link] Search
Breadth-first Search

• Breadth-first search is the most common search strategy for traversing

a tree or graph. This algorithm searches breadthwise in a tree or graph,
so it is called breadth-first search.
• BFS algorithm starts searching from the root node of the tree and
expands all successor node at the current level before moving to nodes
of next level.
• The breadth-first search algorithm is an example of a general-graph
search algorithm.
• Breadth-first search implemented using FIFO queue data structure.
Algorithm for BFS:

Step 1: Choose any one node randomly, to start traversing.

Step 2: Visit its adjacent unvisited node.
Step 3: Mark it as visited in the boolean array and display it.
Step 4: Insert the visited node into the queue.
Step 5: If there is no adjacent node, remove the first node from the queue.
Step 6: Repeat the above steps until the queue is empty.
Working of Breadth First Search:
Working of Breadth First Search:
Working of Breadth First Search:
Working of Breadth First Search:
Working of Breadth First Search:
Working of Breadth First Search:
Working of Breadth First Search:

In this way, we will get the output of BFS to be A→B→C→D→E→F→G→H.

Example:

S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K
Breadth-first Search

• Advantages:
• BFS will provide a solution if any solution exists.
• If there are more than one solutions for a given problem, then BFS
will provide the minimal solution which requires the least number of
steps.
• Disadvantages:
• It requires lots of memory since each level of the tree must be saved
into memory to expand the next level.
• BFS needs lots of time if the solution is far away from the root node.
Pseudo-code for BFS:
• procedure BFS(Graph, root) is
• Let root = explored
• [Link](root)
• while(Queue is not empty):
• v := [Link]()
• if v == goal:
• return v
• for all edges from v to w in [Link](v):
• if w is not labeled as explored:
• label w as explored
• [Link](w)
• END for
• END while
• END BFS
Applications of Breadth First Search
• To find the shortest path between two edges when the path length is equivalent
to the number of edges.
• To check whether a graph is bipartite or not
• To copy garbage collection by Cheney’s algorithm
• Used in unweighted graphs to find the minimum cost spanning tree
• To form peer-to-peer network connections
• To find neighboring locations in the GPS navigation system
• To detect cycle in an undirected graph
• To broadcast packets in a network
• To find all the nodes within one connected component in an otherwise
disconnected graph
Breadth-first Search:

• Time Complexity: Time Complexity of BFS algorithm can be obtained by

the number of nodes traversed in BFS until the shallowest Node. Where the
d= depth of shallowest solution and b is a node at every state.
• T (b) = 1+b2+b3+.......+ bd= O (bd)
• Space Complexity: Space complexity of BFS algorithm is given by the
Memory size of frontier which is O(bd).
• Completeness: BFS is complete, which means if the shallowest goal node
is at some finite depth, then BFS will find a solution.
• Optimality: BFS is optimal if path cost is a non-decreasing function of the
depth of the node.
Depth-first Search

• Depth-first search is a recursive algorithm for traversing a tree or

graph data structure.
• It is called the depth-first search because it starts from the root node
and follows each path to its greatest depth node before moving to the
next path.
• DFS uses a stack data structure for its implementation.
• The process of the DFS algorithm is similar to the BFS algorithm.
Depth-first Search

• Advantage:
• DFS requires very less memory as it only needs to store a stack of the
nodes on the path from root node to the current node.
• It takes less time to reach to the goal node than BFS algorithm (if it
traverses in the right path).
• Disadvantage:
• There is the possibility that many states keep re-occurring, and there is
no guarantee of finding the solution.
• DFS algorithm goes for deep down searching and sometime it may go
to the infinite loop.
Depth-first Search

• Example:
• In the below search tree, we have shown the flow of depth-first search, and
it will follow the order as:
• Root node--->Left node ----> right node.
• It will start searching from root node S, and traverse A, then B, then D and
E, after traversing E, it will backtrack the tree as E has no other successor
and still goal node is not found. After backtracking it will traverse node C
and then G, and here it will terminate as it found goal node.
•
Depth-first Search
Depth-first Search

• Completeness: DFS search algorithm is complete within finite state space

as it will expand every node within a limited search tree.
• Time Complexity: Time complexity of DFS will be equivalent to the node
traversed by the algorithm. It is given by:
• T(n)= 1+ n2+ n3 +.........+ nm=O(nm)
• Where, m= maximum depth of any node and this can be much larger
than d (Shallowest solution depth)
• Space Complexity: DFS algorithm needs to store only single path from the
root node, hence space complexity of DFS is equivalent to the size of the
fringe set, which is O(bm).
• Optimal: DFS search algorithm is non-optimal, as it may generate a large
number of steps or high cost to reach to the goal node.
Depth-Limited Search Algorithm:
• A depth-limited search algorithm is similar to depth-first search with a
predetermined limit.
• Depth-limited search can solve the drawback of the infinite path in the Depth-first
search.
• In this algorithm, the node at the depth limit will treat as it has no successor nodes
further.
• Depth-limited search can be terminated with two Conditions of failure:
• Standard failure value: It indicates that problem does not have any solution.
• Cutoff failure value: It defines no solution for the problem within a given depth limit.
• Advantages:
• Depth-limited search is Memory efficient.
• Disadvantages:
• Depth-limited search also has a disadvantage of incompleteness.
• It may not be optimal if the problem has more than one solution.
Depth-Limited Search Algorithm:
Depth-Limited Search Algorithm:

• Completeness: DLS search algorithm is complete if the solution is

above the depth-limit.
• Time Complexity: Time complexity of DLS algorithm is O(bℓ).
• Space Complexity: Space complexity of DLS algorithm is O(b×ℓ).
• Optimal: Depth-limited search can be viewed as a special case of
DFS, and it is also not optimal even if ℓ>d.
Uniform-cost Search Algorithm:

• Uniform-cost search is a searching algorithm used for traversing a weighted tree

or graph.
• This algorithm comes into play when a different cost is available for each edge.
• The primary goal of the uniform-cost search is to find a path to the goal node
which has the lowest cumulative cost.
• Uniform-cost search expands nodes according to their path costs form the root
node.
• It can be used to solve any graph/tree where the optimal cost is in demand.
• A uniform-cost search algorithm is implemented by the priority queue.
• It gives maximum priority to the lowest cumulative cost.
• Uniform cost search is equivalent to BFS algorithm if the path cost of all edges is
the same.
Uniform-cost Search Algorithm:

• Advantages:
• Uniform cost search is optimal because at every state the path with the
least cost is chosen.
• Disadvantages:
• It does not care about the number of steps involve in searching and
only concerned about path cost. Due to which this algorithm may be
stuck in an infinite loop.
Uniform-cost Search Algorithm:
Uniform-cost Search Algorithm:

• Completeness:
• Uniform-cost search is complete, such as if there is a solution, UCS will find it.
• Time Complexity:
• Let C* is Cost of the optimal solution, and ε is each step to get closer to the goal node.
Then the number of steps is = C*/ε+1. Here we have taken +1, as we start from state 0
and end to C*/ε.
• Hence, the worst-case time complexity of Uniform-cost search isO(b1 + [C*/ε])/.
• Space Complexity:
• The same logic is for space complexity so, the worst-case space complexity of Uniform-
cost search is O(b1 + [C*/ε]).
• Optimal:
• Uniform-cost search is always optimal as it only selects a path with the lowest path cost.
Iterative deepening depth-first Search:

• The iterative deepening algorithm is a combination of DFS and BFS

algorithms. This search algorithm finds out the best depth limit and
does it by gradually increasing the limit until a goal is found.
• This algorithm performs depth-first search up to a certain "depth
limit", and it keeps increasing the depth limit after each iteration until
the goal node is found.
• This Search algorithm combines the benefits of Breadth-first search's
fast search and depth-first search's memory efficiency.
• The iterative search algorithm is useful uninformed search when
search space is large, and depth of goal node is unknown.
Iterative deepening depth-first Search:

• Advantages:
• It combines the benefits of BFS and DFS search algorithm in terms of
fast search and memory efficiency.
• Disadvantages:
• The main drawback of IDDFS is that it repeats all the work of the
previous phase.
1'st Iteration-----> A
2'nd Iteration----> A, B, C
3'rd Iteration------>A, B, D, E, C, F, G
4'th Iteration------>A, B, D, H, I, E, C, F, K, G
In the fourth iteration, the algorithm will find the goal node.
Iterative deepening depth-first Search:

• Completeness:
• This algorithm is complete is ifthe branching factor is finite.
• Time Complexity:
• Let's suppose b is the branching factor and depth is d then the worst-case
time complexity is O(bd).
• Space Complexity:
• The space complexity of IDDFS will be O(bd).
• Optimal:
• IDDFS algorithm is optimal if path cost is a non- decreasing function of the
depth of the node.
Bidirectional Search Algorithm:

• Bidirectional search algorithm runs two simultaneous searches, one form initial
state called as forward-search and other from goal node called as backward-
search, to find the goal node.
• Bidirectional search replaces one single search graph with two small subgraphs in
which one starts the search from an initial vertex and other starts from goal vertex.
• The search stops when these two graphs intersect each other.
• Bidirectional search can use search techniques such as BFS, DFS, DLS, etc.
• Advantages:
• Bidirectional search is fast.
• Bidirectional search requires less memory
• Disadvantages:
• Implementation of the bidirectional search tree is difficult.
• In bidirectional search, one should know the goal state in advance.
Bidirectional Search Algorithm:

• Completeness: Bidirectional Search is complete if we use BFS in

both searches.
• Time Complexity: Time complexity of bidirectional search using BFS
is O(bd).
• Space Complexity: Space complexity of bidirectional search is O(bd).
• Optimal: Bidirectional search is Optimal
 Comparison of various uninformed search algorithms

Algorithm Time Space Complete Optimality

Breadth First O(b^d) O(b^d) Yes Yes

Depth First O(b^m) O(bm) No No

Depth Limited O(b^l) O(bl) No No

Iterative Deepening O(b^d) O(bd) Yes Yes

Bidirectional O(b^(d/2)) O(b^(d/2)) Yes Yes

O(bl+floor(C*/epsilon O(bl+floor9C*/epsilo
Uniform Cost Yes Yes
)) n))
 Key BFS DFS

Definition BFS, stands for Breadth First Search. DFS, stands for Depth First Search.

Data structure BFS uses Queue to find the shortest path. DFS uses Stack to find the shortest path.

Source BFS is better when target is closer to Source. DFS is better when target is far from source.

Suitability for As BFS considers all neighbor so it is not suitable for DFS is more suitable for decision tree. As with one
decision tree decision tree used in puzzle games. decision, we need to traverse further to augment the
decision. If we reach the conclusion, we won.

Speed BFS is slower than DFS. DFS is faster than BFS.

Time Complexity Time Complexity of BFS = O(V+E) where V is vertices and Time Complexity of DFS is also O(V+E) where V is
E is edges. vertices and E is edges.
Parameters Informed Search Uninformed Search

Known as It is also known as Heuristic Search. It is also known as Blind Search.

Using Knowledge It uses knowledge for the searching process. It doesn’t use knowledge for the searching process.

It finds solution slow as compared to an informed

Performance It finds a solution more quickly.
search.

Completion It may or may not be complete. It is always complete.

Cost Factor Cost is low. Cost is high.

It consumes moderate time because of slow

Time It consumes less time because of quick searching.
searching.

Direction There is a direction given about the solution. No suggestion is given regarding the solution in it.

Implementation It is less lengthy while implemented. It is more lengthy while implemented.

It is more efficient as efficiency takes into account It is comparatively less efficient as incurred cost is
Efficiency cost and performance. The incurred cost is less and more and the speed of finding the Breadth-
speed of finding solutions is quick. Firstsolution is slow.

Computational requirements Computational requirements are lessened. Comparatively higher computational requirements.

Having a wide scope in terms of handling large

Size of search problems Solving a massive search task is challenging.
search problems.
•Greedy Search
•Depth First Search (DFS)
•A* Search
Examples of Algorithms •Breadth First Search (BFS)
•AO* Search
•Branch and Bound
•Hill Climbing Algorithm
What is Heuristics?

• A heuristic is a technique that is used to solve a problem faster than the

classic methods.
• These techniques are used to find the approximate solution of a problem
when classical methods do not.
• Heuristics are said to be the problem-solving techniques that result in
practical and quick solutions.
• Heuristics are strategies that are derived from past experience with similar
problems.
• Heuristics use practical methods and shortcuts used to produce the solutions
that may or may not be optimal, but those solutions are sufficient in a given
limited timeframe.
Different techniques
Heuristic Search Techniques in AI
Direct Heuristic Search Techniques in AI

• It includes Blind Search, Uninformed Search, and Blind control

strategy.
• These search techniques are not always possible as they require much
memory and time.
• These techniques search the complete space for a solution and use the
arbitrary ordering of operations.
• The examples of Direct Heuristic search techniques include Breadth-
First Search (BFS) and Depth First Search (DFS).
Weak Heuristic Search techniques in AI

• It includes Informed Search, Heuristic Search, and Heuristic control strategy.

• These techniques are helpful when they are applied properly to the right types of
tasks. They usually require domain-specific information.
• The examples of Weak Heuristic search techniques include Best First Search
(BFS) and A*.
• Before describing certain heuristic techniques, let's see some of the techniques
listed below:
• Bidirectional Search
• A* search
• Simulated Annealing
• Hill Climbing
• Best First search
• Beam search
Hill Climbing in Artificial Intelligence
Features of Hill Climbing in AI

• One such example of Hill Climbing will be the widely discussed

Travelling Salesman Problem- one where we must minimize the
distance he travels.
• It is a variant of the generate-and-test algorithm
• It makes use of the greedy approach
Types of Hill Climbing in AI
Types of Hill Climbing in AI

• Simple Hill Climbing- This examines one neighboring node at a time

and selects the first one that optimizes the current cost to be the next
node.
• Steepest Ascent Hill Climbing- This examines all neighboring nodes
and selects the one closest to the solution state.
• Stochastic Hill Climbing- This selects a neighboring node at random
and decides whether to move to it or examine another.
Hill Climbing Algorithm

[Link] initial state- if goal state, stop and return success. Else, make
initial state current.
[Link] until the solution reached or until no new operators left to apply
to current state:
• a. Select new operator to apply to the current producing new state.
• b. Evaluate new state:
• If a goal state, stop and return success.
• If better than the current state, make it current state, proceed.
• Even if not better than the current state, continue until the solution reached.
[Link].
Problems with Hill Climbing in AI

• 1. Local Maximum
• 2. Plateau
• 3. Ridges
Local Maximum

• All neighboring states have values worse than the current. The greedy
approach means won’t be moving to a worse state.
• This terminates the process even though there may have been a better
solution. As a workaround, use backtracking.
Plateau

• All neighbors to it have the same value. This makes it impossible to

choose a direction. To avoid this, randomly make a big jump.
Ridge

• At a ridge, movement in all possible directions is downward.

• This makes it look like a peak and terminates the process.
• To avoid this, may use two or more rules before testing.
Informed search algorithms

• The informed search algorithm is also called heuristic search or

directed search.
• In contrast to uninformed search algorithms, informed search
algorithms require details such as distance to reach the goal, steps to
reach the goal, cost of the paths which makes this algorithm more
efficient.
• Here, the goal state can be achieved by using the heuristic function.
• The heuristic function is used to achieve the goal state with the lowest
cost possible. This function estimates how close a state is to the goal.
Greedy best-first search algorithm

• Greedy best-first search uses the properties of both depth-first search

and breadth-first search.
• Greedy best-first search traverses the node by selecting the path which
appears best at the moment.
• The closest path is selected by using the heuristic function.
Greedy best-first search algorithm
Greedy best-first search algorithm

• Here, A is the start node and H is the goal node.

• Greedy best-first search first starts with A and then examines the next
neighbour B and C.
• Here, the heuristics of B is 12 and C is 4.
• The best path at the moment is C and hence it goes to C.
• From C, it explores the neighbours F and G. the heuristics of F is 8
and G is 2.
• Hence it goes to G. From G, it goes to H whose heuristic is 0 which is
also our goal state.
 Greedy best-first search algorithm

The path of traversal is

A —-> C —-> G —-> H
The time complexity of Greedy best-first search is O(bm) in
worst cases.
Greedy best-first search algorithm

• Advantages of Greedy best-first search

• Greedy best-first search is more efficient compared with breadth-first search
and depth-first search.
• Disadvantages of Greedy best-first search
• In the worst-case scenario, the greedy best-first search algorithm may behave
like an unguided DFS.
• There are some possibilities for greedy best-first to get trapped in an infinite
loop.
• The algorithm is not an optimal one.
A* search algorithm

• A* search algorithm is a combination of both uniform cost search

and greedy best-first search algorithms.
• It uses the advantages of both with better memory usage.
• It uses a heuristic function to find the shortest path.
• A* search algorithm uses the sum of both the cost and heuristic of the
node to find the best path.
A* search algorithm
A* search algorithm

• Let A be the start node and H be the goal node.

• First, the algorithm will start with A. From A, it can go to B, C, H.
• Note the point that A* search uses the sum of path cost and heuristics
value to determine the path.
• Here, from A to B, the sum of cost and heuristics is 1 + 3 = 4.
• From A to C, it is 2 + 4 = 6.
• From A to H, it is 7 + 0 = 7.
• Here, the lowest cost is 4 and the path A to B is chosen. The other paths will be on
hold.
• Now, from B, it can go to D or E.
• From A to B to D, the cost is 1 + 4 + 2 = 7.
• From A to B to E, it is 1 + 6 + 6 = 13.
• The lowest cost is 7. Path A to B to D is chosen and compared with other paths
which are on hold.
• Here, path A to C is of less cost. That is 6.
• Hence, A to C is chosen and other paths are kept on hold.
• From C, it can now go to F or G.
• From A to C to F, the cost is 2 + 3 + 3 = 8.
• From A to C to G, the cost is 2 + 2 + 1 = 5.
• The lowest cost is 5 which is also lesser than other paths which are on hold. Hence,
path A to G is chosen.
• From G, it can go to H whose cost is 2 + 2 + 2 + 0 = 6.
• Here, 6 is lesser than other paths cost which is on hold.
A* search algorithm

The path of traversal is

A —-> C —-> G —-> H
A* search algorithm

• The time complexity of the A* search is O(b^d) where b is the

branching factor.
• Advantages of A* search algorithm
• This algorithm is best when compared with other algorithms.
• This algorithm can be used to solve very complex problems also it is an
optimal one.
• Disadvantages of A* search algorithm
• The A* search is based on heuristics and cost. It may not produce the shortest
path.
• The usage of memory is more as it keeps all the nodes in the memory.
Agents in Artificial Intelligence
• Artificial intelligence is defined as the study of rational agents.
• A rational agent could be anything that makes decisions, as a person,
firm, machine, or software.
• It carries out an action with the best outcome after considering past
and current percepts.
• An AI system is composed of an agent and its environment. The
agents act in their environment. The environment may contain other
agents.
• An agent is anything that can be viewed as :
• perceiving its environment through sensors and
• acting upon that environment through actuators
Agents in Artificial Intelligence

• To understand the structure of Intelligent Agents, we should be

familiar with Architecture and Agent programs.
• Architecture is the machinery that the agent executes on.
• It is a device with sensors and actuators, for example, a robotic car, a
camera, a PC.
• Agent program is an implementation of an agent function.
• An agent function is a map from the percept sequence to an action.

• Agent = Architecture + Agent Program

Examples of Agent:
• A software agent has Keystrokes, file contents, received network
packages which act as sensors and displays on the screen, files, sent
network packets acting as actuators.
• A Human-agent has eyes, ears, and other organs which act as sensors,
and hands, legs, mouth, and other body parts acting as actuators.
• A Robotic agent has Cameras and infrared range finders which act as
sensors and various motors acting as actuators.
Types of Agents

• Simple Reflex Agents

• Model-Based Reflex Agents
• Goal-Based Agents
• Utility-Based Agents
• Learning –Based Agents
Simple reflex agents
• Simple reflex agents ignore the rest of the percept history and act only on
the basis of the current percept.
• Percept history is the history of all that an agent has perceived to date. The
agent function is based on the condition-action rule.
• A condition-action rule is a rule that maps a state i.e, condition to an action.
• If the condition is true, then the action is taken, else not.
• This agent function only succeeds when the environment is fully
observable.
• For simple reflex agents operating in partially observable environments,
infinite loops are often unavoidable.
• It may be possible to escape from infinite loops if the agent can randomize
its actions.
Simple reflex agents
Simple reflex agents

• function SIMPLE-REFLEX-AGENT(percept ) returns an action

• persistent: rules, a set of condition–action rules
• state←INTERPRET-INPUT(percept )
• rule←RULE-MATCH(state, rules)
• action ←[Link]
• return action
Problems with Simple reflex agents are :
• Very limited intelligence.
• No knowledge of non-perceptual parts of the state.
• Usually too big to generate and store.
• If there occurs any change in the environment, then the collection of
rules need to be updated.
Model-based reflex agents

• It works by finding a rule whose condition matches the current

situation.
• A model-based agent can handle partially observable
environments by the use of a model about the world.
• The agent has to keep track of the internal state which is adjusted by
each percept and that depends on the percept history.
• The current state is stored inside the agent which maintains some kind
of structure describing the part of the world which cannot be seen.
Model-based reflex agents
Model-based reflex agents

• function MODEL-BASED-REFLEX-AGENT(percept ) returns an action

• persistent: state, the agent’s current conception of the world state
• model , a description of how the next state depends on current state and action
• rules, a set of condition–action rules
• action, the most recent action, initially none
• state←UPDATE-STATE(state, action, percept ,model )
• rule←RULE-MATCH(state, rules)
• action ←[Link]
• return action
Model-based reflex agents

• Updating the state requires information about :

• how the world evolves independently from the agent, and
• how the agent’s actions affect the world.
Goal-based agents

• These kinds of agents take decisions based on how far they are
currently from their goal(description of desirable situations).
• Their every action is intended to reduce its distance from the goal.
• This allows the agent a way to choose among multiple possibilities,
selecting the one which reaches a goal state.
• The knowledge that supports its decisions is represented explicitly and
can be modified, which makes these agents more flexible.
• They usually require search and planning.
• The goal-based agent’s behavior can easily be changed.
Goal-based agents
Utility-based agents
• The agents which are developed having their end uses as building blocks are
called utility-based agents.
• When there are multiple possible alternatives, then to decide which one is
best, utility-based agents are used.
• They choose actions based on a preference (utility) for each state.
Sometimes achieving the desired goal is not enough.
• We may look for a quicker, safer, cheaper trip to reach a destination.
• Agent happiness should be taken into consideration.
• Utility describes how “happy” the agent is.
• Because of the uncertainty in the world, a utility agent chooses the action
that maximizes the expected utility.
• A utility function maps a state onto a real number which describes the
associated degree of happiness.
Utility-based agents
Learning Agent :
• A learning agent in AI is the type of agent that can learn from its past experiences
or it has learning capabilities.
• It starts to act with basic knowledge and then is able to act and adapt automatically
through learning.

• A learning agent has mainly four conceptual components, which are:

[Link] element: It is responsible for making improvements by learning from
the environment
[Link]: The learning element takes feedback from critics which describes how
well the agent is doing with respect to a fixed performance standard.
[Link] element: It is responsible for selecting external action
[Link] Generator: This component is responsible for suggesting actions that
will lead to new and informative experiences.
Learning Agent :
Statements:
• No fingers are legs
• Mostly legs are hands
• Only a few hands are hairs
• Conclusions:
I. Some legs are not hairs
• II. All hands being fingers is a possibility.
• a. Only conclusion II follows
• b. Neither conclusion I nor conclusion II follows
• c. Only conclusion I follows
• d. Both conclusion I and conclusion II follow.
• e. None of the above
• Statements:
• Only a few rides are trips.
• No trip is mountain.
• All mountains are trees.
• I: Some trees are not trips.
• II: All rides being trips is not a possibility.
• a. Only conclusion I follows
• b. Only conclusion II follows
• c. Either conclusion I or II follows
• d. Both conclusions I and II follow
• e. Neither conclusion I nor II follows
• Statements:
• Mostly pets are cats
• Only cats are dogs
• No cats are rabbits
• I. Some pets are rabbits.
• II. All pets being rabbits is not a possibility.
• a. Both conclusion I and conclusion II follow.
• b. Only conclusion I follows
• c. Neither conclusion I nor conclusion II follows
• d. Only conclusion II follows
• e. None of the above
• Q1. Statements:
• All Tree is Mango
• All Mango are Orange
• Some oranges is Papaya
• Conclusion:
• I: All Mango are Tree
• II: Some Papaya are Tree

• Q2. Statements:
• Some Arm are legs
• No legs are shoes
• All shoes are socks
• Conclusion:
• I: All Arm can never be shoes
• II: Some Socks can be arm
(a)If only conclusion I follow.
(b) If only conclusion II follows.
(c) If either conclusion I or II follows.
(d) If neither conclusion I nor II follows.
(e) If both conclusions I and II follow.
Q1. Statements:
All Tree is Mango
All Mango are Orange
Some oranges is Papaya
Conclusion:
I: All Mango are Tree
II: Some Papaya are Tree
• Q3. Statements:
• All Music are war
• No war is Queen
• No music is Forest
• Conclusions:
• I. some music are not Queen
• II. Some war are not Forest

• Q4. Statements:
• Some genius are crazy
• All crazy are mad
• Some mad are superhero
• Conclusions:
• I. Some Mad are not Genius
• II. All Mad are genius
• Q5. Statements:
No eyes are beautiful
No beautiful is soft
All soft are dogs
Conclusions:
I: Some Dogs are eyes
II: All Dogs are Soft
• All sand are water.
No fruit is a pen.
Some pen are sand.
Conclusions:
I. All fruit are not sand.
II. All water being fruit is a possibility.
• All Quagmires are Digital
No Digital is Government
All Government are Dumb
Conclusions:
I. Some digital can be Dumb
II. All Dumb can never be Digital
• Some kind are man.
All Man are Cash.
No Cash is a Cheque
Conclusions:
I. No man is cheque
II. Some cash is kind
• Some graph are Fish
Some fish are sparrow
Some sparrow are Eagle
Conclusions:
I. Some Fish are Eagle
II. No Eagle is Fish
• All iron are Eight
No Eight is Two
All Two are Four
Conclusions:
I. No iron is Two
II. Some four can be Eight
• Q11. Statements:
Some Behavior are Security
Some Security are Logical
All Relation are Logical
Conclusion:
I: Some Relation are Security
II: Some logical are Security
• Some Demand are Supply
No Supply are Common
No common are train
Conclusion:
I: All demand can be supply
II: Some train are not demand
• No issue is social
All social are animal
All animal are loyal
Conclusions:
I. some Animal are Social
II. Some loyal are not Issue
• Some Exam are important
• No important is Sand
• Some sand are water
• Conclusions:
• I. All important can be exam
• II. Some water are not Exam

• Q15. Statements:
• All Three are Seven
• Some Seven are Nine
• All Nine are Five
• Conclusions:
• I: Some Five are Seven
• II: Some Nine are Three is possibility
First-Order Logic in Artificial intelligence
• 1. All birds fly.
• In this question the predicate is "fly(bird)."
• And since there are all birds who fly so it will be represented as follows.
• ∀x bird(x) →fly(x).
• 2. Every man respects his parent.
• In this question, the predicate is "respect(x, y)," where x=man, and y= parent.
• Since there is every man so will use ∀, and it will be represented as follows:
• ∀x man(x) → respects (x, parent).
• 3. Some boys play cricket.
• In this question, the predicate is "play(x, y)," where x= boys, and y= game. Since there are
some boys so we will use ∃, and it will be represented as:
• ∃x boys(x) → play(x, cricket).
• 4. Not all students like both Mathematics and Science.
• In this question, the predicate is "like(x, y)," where x= student, and y= subject.
• Since there are not all students, so we will use ∀ with negation, so following
representation for this:
• ¬∀ (x) [ student(x) → like(x, Mathematics) ∧ like(x, Science)].

• 5. Only one student failed in Mathematics.

• In this question, the predicate is "failed(x, y)," where x= student, and y= subject.
• Since there is only one student who failed in Mathematics, so we will use
following representation for this:
• ∃(x) [ student(x) → failed (x, Mathematics) ∧∀ (y) [¬(x==y) ∧ student(y)
→ ¬failed (x, Mathematics)].
[Link] likes all kind of food.
[Link] and vegetable are food
[Link] anyone eats and not killed is food.
[Link] eats peanuts and still alive
[Link] eats everything that Anil eats.
Prove by resolution that:
[Link] likes peanuts.
Propositional logic in Artificial intelligence

• 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.
• Example:
1.a) It is Sunday.
2.b) The Sun rises from West (False proposition)
3.c) 3+3= 7(False proposition)
4.d) 5 is a prime number.
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.
• 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.

• 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:

[Link] Propositions
[Link] propositions
• 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:
1.a) 2+2 is 4, it is an atomic proposition as it is a true fact.
2.b) "The Sun is cold" is also a proposition as it is a false fact.
• Compound proposition: Compound propositions are constructed by combining simpler
or atomic propositions, using parenthesis and logical connectives.
• Example:
1.a) "It is raining today, and street is wet."
2.b) "Ankit is a doctor, and his clinic is in Mumbai."
Logical Connectives:

• Logical connectives are used to connect two simpler propositions or representing a

sentence logically.
• We can create compound propositions with the help of logical connectives.
• Negation: A sentence such as ¬ P is called negation of P. A literal can be either Positive
literal or negative literal.
• Conjunction: A sentence which has ∧ connective such as, P ∧ Q is called a conjunction.
• Example: Rohan is intelligent and hardworking. It can be written as,
• P= Rohan is intelligent,
• Q= Rohan is hardworking. → P∧ Q.
• Disjunction: A sentence which has ∨ connective, such as P ∨ Q. is called disjunction,
where P and Q are the propositions.
• Example: "Ritika is a doctor or Engineer",
• Here P= Ritika is Doctor. Q= Ritika is Doctor, so we can write it as P ∨ Q.
Logical Connectives:

• Implication: A sentence such as P → Q, is called an implication.

Implications are also known as if-then rules. It can be represented as
• If it is raining, then the street is wet.
• Let P= It is raining, and Q= Street is wet, so it is represented as P → Q
• Biconditional: A sentence such as P⇔ Q is a Biconditional sentence,
example If I am breathing, then I am alive
• P= I am breathing, Q= I am alive, it can be represented as P ⇔ Q.
Table for Propositional Logic Connectives:
Truth table with three propositions
Properties of Operators:

• Commutativity:
• P∧ Q= Q ∧ P, or
• P ∨ Q = Q ∨ P.
• Associativity:
• (P ∧ Q) ∧ R= P ∧ (Q ∧ R),
• (P ∨ Q) ∨ R= P ∨ (Q ∨ R)
• Identity element:
• P ∧ True = P,
• P ∨ True= True.
Properties of Operators:

• Distributive:
• P∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R).
• P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R).
• DE Morgan's Law:
• ¬ (P ∧ Q) = (¬P) ∨ (¬Q)
• ¬ (P ∨ Q) = (¬ P) ∧ (¬Q).
• Double-negation elimination:
• ¬ (¬P) = P.
Rules of Inference in Artificial intelligence

• Inference rules:
• Inference rules are the templates for generating valid arguments. Inference
rules are applied to derive proofs in artificial intelligence, and the proof is a
sequence of the conclusion that leads to the desired goal.
• Implication: It is one of the logical connectives which can be represented
as P → Q. It is a Boolean expression.
• Converse: The converse of implication, which means the right-hand side
proposition goes to the left-hand side and vice-versa. It can be written as Q
→ P.
• Contrapositive: The negation of converse is termed as contrapositive, and
it can be represented as ¬ Q → ¬ P.
• Inverse: The negation of implication is called inverse. It can be represented
as ¬ P → ¬ Q.
Inference rules:

• Inference rules are the templates for generating valid arguments.

• Inference rules are applied to derive proofs in artificial intelligence, and the proof
is a sequence of the conclusion that leads to the desired goal.
• Implication:
• It is one of the logical connectives which can be represented as P → Q. It is a Boolean
expression.
• Converse:
• The converse of implication, which means the right-hand side proposition goes to the left-hand
side and vice-versa. It can be written as Q → P.
• Contrapositive:
• The negation of converse is termed as contrapositive, and it can be represented as ¬ Q → ¬ P.
• Inverse:
• The negation of implication is called inverse. It can be represented as ¬ P → ¬ Q.
Inference rules:
 Types of Inference rules:
• 1. Modus Ponens:
• The Modus Ponens rule is one of the most important rules of
inference, and it states that if P and P → Q is true, then we can infer
that Q will be true. It can be represented as:

Statement-1: "If I am sleepy then I go to bed" ==> P→ Q

Statement-2: "I am sleepy" ==> P
Conclusion: "I go to bed." ==> Q.
Hence, we can say that, if P→ Q is true and P is true then Q will be true.
 Modus Tollens:

• The Modus Tollens rule state that if P→ Q is true and ¬ Q is true,

then ¬ P will also true. It can be represented as:

Statement-1: "If I am sleepy then I go to bed" ==> P→ Q

Statement-2: "I do not go to the bed."==> ~Q
Statement-3: Which infers that "I am not sleepy" => ~P
Hypothetical Syllogism
• The Hypothetical Syllogism rule state that if P→R is true whenever P→Q is true, and Q→R is
true. It can be represented as the following notation:
• Example:
• Statement-1: If you have my home key then you can unlock my home. P→Q
Statement-2: If you can unlock my home then you can take my money. Q→R
Conclusion: If you have my home key then you can take my money. P→R
Disjunctive Syllogism:
• The Disjunctive syllogism rule state that if P∨Q is true, and ¬P is true,
then Q will be true. It can be represented as:

Example:
Statement-1: Today is Sunday or Monday. ==>P∨Q
Statement-2: Today is not Sunday. ==> ¬P
Conclusion: Today is Monday. ==> Q
Addition:

• The Addition rule is one the common inference rule, and it states that
If P is true, then P∨Q will be true.

Example:
Statement: I have a vanilla ice-cream. ==> P
Statement-2: I have Chocolate ice-cream.
Conclusion: I have vanilla or chocolate ice-cream. ==> (P∨Q)
 Simplification:

• The simplification rule state that if P∧ Q is true, then Q or P will also

be true. It can be represented as:
Resolution:

• The Resolution rule state that if P∨Q and ¬ P∧R is true, then Q∨R will
also be true. It can be represented as
Q16. Statements: Q19. Statements:
Only a few March are April. Some apple are Papaya
Only a few April is May. No apple is Mango
All May is June. All Mango is litchi
Conclusions: Conclusion:
I. All June being April is a possibility. I: Some papaya are not Mango
II. Some May are March. II: Some litchi are mango

Q17. Statements: Q20. Statements:

Only chips are coffee. All Box are Bottle
Some chips is cookies. All Bottle are cards
Only a few cookies is sugar. Some cards are mobile
Conclusions: Conclusion:
I. Some coffee is cookies I: Some mobile are Bottle
II. All cookies are sugar is a possibility II: All cards are bottle
Q21. Statements:
Q18. Statements: All Day is call
Some Blue are Olive. Some sleep are night
All Olive is Yellow. Some sleep are call
Some Yellow is White. All sleep are hey
Conclusions: Conclusions:
I. Some Olive is White. I. Some night can be hey
II. Some Blue are Yellow. II. Some day are not Hey
Q22. Statements:
Q25. Statements:
Some Who are You
Only a few Orange are Apple Q28. Statements:
No We is He
Some Apple are Mango Only a few Brown are green.
No Me are You
Only Mango are Grapes Some green are yellow
Some Me are We
Conclusions: Atleast yellow are white
Conclusions:
I. All Mango can be Apple Conclusions:
I. Some Me are He
II. Some Orange can be Mango I. Some white is brown
II. Some Me are not He
II. No brown is white
Q23. Statements: Q26. Statements:
Some Thought are Of Only a few cotton are silk. Q29. Statements:
All The are Day All silk are rayon. No Light is Current
Some The are Of No silk are polyester Some Bulb are Bright
Conclusions: Conclusions: All Bright are Light
I. Some thought are The I. All polyester is cotton is a possibility Conclusions:
II. No The are Thought II. No rayon is polyester I. Some bulb are not current
Q24. Statements: Q27. Statements: II. No light are bulb
Some Quant are English Some bunny is easter.
Some IT are CS No easter is a egg.
Some English are CS Only a few egg are hidden
Conclusions: Conclusions:
I. All Quant can be IT I. All hidden is easter is a possibility
II. Some Quant are CS II. Some bunny is hidden is a possibility
 Q33. Statements: Q36. Statements:
Q30. Statements:
All arrogant are table All Writer are Painter
Only Yellow are Orange
Some table are tree All Painter is Bookworm
No Black are yellow
All tree are parrot All Bookworm are Clever
Only black are green
Conclusion: Conclusions:
Conclusions:
I. All tree are arrogant I: All painter are clever is possibility
I. Some Orange are green
II. Some tree are not arrogant II: Some writer is clever
II. No green are orange
Q31. Statements: Q34. Statements: Q37. Statements:
Some Apple are mango No house is luxury All Shirt are Jeans
No mango is blood Some luxury is car Some jeans are home
Only Blood is Heart Only car is Scooter All Home is page
Conclusion: Conclusions: Conclusions:
I. Some Heart is not Mango I. Some scooter is car is a possibility. I: Some Home are shirt
II. All blood can be Apple II. Some car is not house II: Some page are Jeans

Q32. Statements: Q35. Statements: Q38. Statements:

Only a few Queue is long All black are white Some Music Earphone
Some Long are Short Some black are green No earphone is amazing
Some Short is Bottle Only a few Green are Yellow No amazing is fun
Conclusion: Conclusions: Conclusions:
I. All Long can be Short I. All green can be white I. Some earphone are not Fun
II. All queue can be Long II. Some yellow can be black II. Some Fun are not Music
Q39. Statements:
Some apple are Blue
No blue is lens
All lens are Expensive
Conclusions:
I. Some expensive are apple
II. No lens is apple

Q40. Statements:
Some laugh are Destiny
All Destiny are Voice
All Voice are water
Conclusions:
I. All voice can be destiny
II. All water is destiny
Forward Chaining
• Forward chaining is a method of reasoning in artificial intelligence in
which inference rules are applied to existing data to extract additional
data until an endpoint (goal) is achieved.
• In this type of chaining, the inference engine starts by evaluating
existing facts, derivations, and conditions before deducing new
information.
• An endpoint (goal) is achieved through the manipulation of knowledge
that exists in the knowledge base.
Forward Chaining and Backward
Chaining
• Example: • Example:
A B
A -> B A -> B
B A
—————————– —————————–
He is running. He is sweating.
If he is running, he sweats. If he is running, he sweats.
He is sweating. He is running.
Forward Chaining

Forward chaining can be used in planning, monitoring, controling, and interpreting applications.
Properties of forward chaining

• The process uses a down-up approach (bottom to top).

• It starts from an initial state and uses facts to make a conclusion.
• This approach is data-driven.
• It’s employed in expert systems and production rule system.
Examples of forward chaining

• A simple example of forward chaining can be explained in the following

sequence.
•A
• A->B
•B
• A is the starting point. A->B represents a fact. This fact is used to achieve a
decision B.
• A practical example will go as follows;
• Tom is running (A)
• If a person is running, he will sweat (A->B)
• Therefore, Tom is sweating. (B)
Advantages

• It can be used to draw multiple conclusions.

• It provides a good basis for arriving at conclusions.
• It’s more flexible than backward chaining because it does not have a
limitation on the data derived from it.
Disadvantages

• The process of forward chaining may be time-consuming.

• It may take a lot of time to eliminate and synchronize available data.
• Unlike backward chaining, the explanation of facts or observations for
this type of chaining is not very clear.
• The former uses a goal-driven method that arrives at conclusions
efficiently.
Backward chaining

• Backward chaining is a concept in artificial intelligence that involves

backtracking from the endpoint or goal to steps that led to the
endpoint.
• This type of chaining starts from the goal and moves backward to
comprehend the steps that were taken to attain this goal.
• The backtracking process can also enable a person establish logical
steps that can be used to find other important solutions.
•
Backward chaining

Backward chaining can be used in debugging, diagnostics, and prescription applications.

Properties of backward chaining
• The process uses an up-down approach (top to bottom).
• It’s a goal-driven method of reasoning.
• The endpoint (goal) is subdivided into sub-goals to prove the truth of
facts.
• A backward chaining algorithm is employed in inference engines,
game theories, and complex database systems.
• The modus ponens inference rule is used as the basis for the backward
chaining process. This rule states that if both the conditional statement
(p->q) and the antecedent (p) are true, then we can infer the
subsequent (q).
Examples of forward chaining
• The information provided in the previous example (forward chaining) can
be used to provide a simple explanation of backward chaining. Backward
chaining can be explained in the following sequence.
•B
• A->B
•A
• B is the goal or endpoint, that is used as the starting point for backward
tracking. A is the initial state. A->B is a fact that must be asserted to arrive
at the endpoint B.
• A practical example of backward chaining will go as follows:
• Tom is sweating (B).
• If a person is running, he will sweat (A->B).
• Tom is running (A).
Advantages

• The result is already known, which makes it easy to deduce inferences.

• It’s a quicker method of reasoning than forward chaining because the
endpoint is available.
• In this type of chaining, correct solutions can be derived effectively if
pre-determined rules are met by the inference engine.
Disadvantages

• The process of reasoning can only start if the endpoint is known.

• It doesn’t deduce multiple solutions or answers.
• It only derives data that is needed, which makes it less flexible than
forward chaining.
Difference between Forwarding Chaining
and Backward Chaining
 Backward chaining
Forward chaining

1.
Backward chaining starts from the goal and
When based on available data a decision is taken
works backward to determine what facts must be
then the process is called as Forward chaining.
asserted so that the goal can be achieved.

Forward chaining is known as data-driven Backward chaining is known as goal-driven

2. technique because we reaches to the goal using the technique because we start from the goal and
available data. reaches the initial state in order to extract the facts.

3. It is a bottom-up approach. It is a top-down approach.

4. It applies the Breadth-First Strategy. It applies the Depth-First Strategy.

Its goal is to get the possible facts or the required

5. Its goal is to get the conclusion.
data.

6. Slow as it has to use all the rules. Fast as it has to use only a few rules.

It operates in forward direction i.e it works from It operates in backward direction i.e it works from
7.
initial state to final decision. goal to reach initial state.

It is used in automated inference engines, theorem

Forward chaining is used for the planning,
8. proofs, proof assistants and other artificial
monitoring, control, and interpretation application.
intelligence applications.
Alpha-beta pruning
• The word ‘pruning’ means cutting down branches and leaves.
• In data science pruning is a much-used term which refers to post and
pre-pruning in decision trees and random forest.
• Alpha-beta pruning is nothing but the pruning of useless branches in
decision trees.
• This alpha-beta pruning algorithm was discovered independently by
researchers in the 1900s.
Condition for Alpha-beta pruning

• Alpha: At any point along the Maximizer path, Alpha is the best option or the
highest value we’ve discovered. The initial value for alpha is – ∞.
• Beta: At any point along the Minimizer path, Beta is the best option or the lowest
value we’ve discovered.. The initial value for alpha is + ∞.
• The condition for Alpha-beta Pruning is that α >= β.
• The alpha and beta values of each node must be kept track of. Alpha can only be
updated when it’s MAX’s time, and beta can only be updated when it’s MIN’s
turn.
• MAX will update only alpha values and the MIN player will update only beta
values.
• The node values will be passed to upper nodes instead of alpha and beta values
during going into the tree’s reverse.
• Alpha and Beta values only are passed to child nodes.
Working of Alpha Beta Pruning

• Step 1: The Max player will start by traveling from node A to node B,
where α = -∞ and β = +∞, and delivering these alpha and beta values
to node B, where = - and = + once again, and Node B transmitting the
identical value to its offspring D.
• Step 2: As Max's turn at Node D approaches, the value of α will be
decided. When the value of α is compared to 2, then 3, the value at
node D is max (2, 3) = 3. Hence, the node value is also 3.
• Step 3: The algorithm returns to node B, where the value of β will
change since this is a turn of Min. Now β = +∞will be compared to the
value of the available subsequent nodes, i.e., min (∞, 3) = 3, resulting
in node B now α = -∞, and β = 3. In the next phase, the algorithm will
visit the next successor of Node B, Node E, and pass the values of α =
-∞ and β = 3.
• Step 4: Max will take over at node E and change alpha's value. The
current existing value of alpha will be compared to 5, resulting in max
(-∞, 5) = 5, and at node E, where α>=β, the right successor of E will
be pruned, and the algorithm will not traverse it, resulting in the value
at node E being 5.
• Step 5: We now traverse the tree backward, from node B to node A. At
node A, alpha will be converted to the greatest feasible value of 3, as
max (-∞, 3)= 3, and β = +∞. These two values will now be passed on
to Node C, A's right-hand successor.
• At node C, the values and β = +∞ and α =3 will be passed on to node
F, and node F will get the identical values.
• Step 6: At node F, the value of α is compared with the left child 0, and
max(3,0)= 3. It is then compared with the right child, which is 1, and
max(3,1)= 3.
• Step 7: Node F sends the node value 1 to node C. The value of Beta is
adjusted at C, α = 3 and β= +∞, and it is compared to 1, resulting in
min (∞, 1) = 1. Now, if α = 3 and β = 1, the condition α>=β is met, the
algorithm will prune the next child of C, which is G, rather than
calculating the entire sub-tree G.
• Step 8: C now returns the value of 1 to A, with max (3, 1) = 3 being
the optimum result for A. The final game tree is shown here, with
nodes that have been calculated and nodes that have never been
computed. As a result, in this case, the ideal value for the maximizer is
3.