Artificial

Intelligenc
e
•Course faculty: Dr. Jansi Rani J
•Course code:BCS515B
•Branch:5 Sem CSE
•VTU 22 Scheme
Module 3
• Informed Search Strategies:
• Greedy best first search
• A*search.
• Heuristic Functions
• Logical Agents: Knowledge–based agent
• The Wumpus world
• Logic Propositional logic
• Reasoning patterns in Propositional Logic
Informed Search

• Informed search algorithms use domain knowledge.

• In an informed search, problem information is available which can guide the
search.
• Informed search strategies can find a solution more efficiently than an
uninformed search strategy.
• Informed search is also called a Heuristic search.
• A heuristic is a way which might not always be guaranteed for best solutions
but guaranteed to find a good solution in reasonable time.
• Informed search can solve much complex problem which could not be solved in
another way.
• An example of informed search algorithms is a traveling salesman problem.
Greedy best First Search:

• Greedy Best-First Search works by Evaluate the cost of each possible path and
then expanding the path with the closest to the Goal. This process is repeated
until the goal is reached.
• The algorithm uses a heuristic function to determine which path is the most
promising.
• The heuristic function means the cost of the current path and the estimated
cost of the remaining paths.
• F(n)=h(n)
• If the cost of the current path is lower than the estimated cost of the remaining
paths, then the current path is chosen. This process is repeated until the goal is
reached.
We are starting from A , so from A there are direct
path to node B( with heuristics value of 32 ) , from
A to C ( with heuristics value of 25 ) and from A to
D( with heuristics value of 35 ) .

2) currently C has close to the goal node . So we

will go from A to C.
3) Now from C we have direct paths as C to F( with
heuristics value of 17 ) and C to E( with heuristics
value of 19) , so we will go from C to F which has
closest value.
3)Now from F we have direct path to go to the goal
node G ( with heuristics value of 0 ) , so we will go
from F to G.

The goal node G has been reached and the path

we will follow is A->C->F->G .
Advantage of Greedy Best-First Search:

• Simple and Easy to Implement: Greedy Best-First Search is a relatively

straightforward algorithm, making it easy to implement.
• Fast and Efficient: Greedy Best-First Search is a very fast algorithm, making it
ideal for applications where speed is essential.
• Low Memory Requirements: Greedy Best-First Search requires only a small
amount of memory, making it suitable for applications with limited memory.
• Flexible: Greedy Best-First Search can be adapted to different types of
problems and can be easily extended to more complex problems.
• Efficiency: If the heuristic function used in Greedy Best-First Search is good to
estimate, how close a node is to the solution, this algorithm can be a very
efficient and find a solution quickly, even in large search spaces.
Disadvantages of Greedy Best-First
Search

• Inaccurate Results: Greedy Best-First Search is not always guaranteed to find

the optimal solution, as it is only concerned with finding the most promising
path.
• Local Optima: Greedy Best-First Search can get stuck in local optima,
meaning that the path chosen may not be the best possible path.
• Heuristic Function: Greedy Best-First Search requires a heuristic function in
order to work, which adds complexity to the algorithm.
• Lack of Completeness: Greedy Best-First Search is not a complete algorithm,
meaning it may not always find a solution if one is exists. This can happen if the
algorithm gets stuck in a cycle or if the search space is a too much complex.
 Applications of Greedy Best-First Search

• Pathfinding: Greedy Best-First Search is used to find the shortest path between two points in a graph. It
is used in many applications such as video games, robotics, and navigation systems.
• Machine Learning: Greedy Best-First Search can be used in machine learning algorithms to find the most
promising path through a search space.
• Optimization: Greedy Best-First Search can be used to optimize the parameters of a system in order to
achieve the desired result.
• Game AI: Greedy Best-First Search can be used in game AI to evaluate potential moves and chose the
best one.
• Navigation: Greedy Best-First Search can be use to navigate to find the shortest path between two
locations.
• Natural Language Processing: Greedy Best-First Search can be use in natural language processing
tasks such as language translation or speech recognisation to generate the most likely sequence of words.
• Image Processing: Greedy Best-First Search can be use in image processing to segment image into
regions of interest.
A*Search

• A* (pronounced "A-star") is a powerful graph traversal and pathfinding

algorithm widely used in artificial intelligence and computer science.
• It is mainly used to find the shortest path between two nodes in a graph, given
the estimated cost of getting from the current node to the destination node.
• The main advantage of the algorithm is its ability to provide an optimal path by
exploring the graph in a more informed way compared to traditional search
algorithms such as Dijkstra's algorithm.
The evaluation function of node n is defined as f(n) = g(n) +h(n).

Start from A node

• Possible moves from A:
• A → B (cost = 1)
• A → C (cost = 4)
• calculate f(n) for both:
• f(B) = g(B) + h(B) = 1 + 6 = 7
• f(C) = g(C) + h(C) = 4 + 4 = 8
• Select node B (because 7 < 8)
• Compute new g(n) and f(n):
• For D: g(D) = 1 + 3 = 4 → f(D) = 4 + 3 = 7
• For C: g(C) = 1 + 2 = 3 → f(C) = 3 + 4 = 7
• Choose either D or C (same cost). Usually, A* expands D first.
• Compute From D
• g(F) = 4 + 2 = 6 → f(F) = 6 + 1 = 7
• g(G) = 4 + 4 = 8 → f(G) = 8 + 0 = 8

Choose F (f = 7)
• Compute from F
• g(G) = 6 + 1 = 7 → f(G) = 7 + 0 = 7
• Goal reached
• optimized path cost
• path: A->B->D->F->G=7 cost
Advantages of A* Search Algorithm

Optimal solution: A* ensures finding the optimal (shortest) path from the start node
to the destination node in the weighted graph given an acceptable heuristic function.
Completeness: If a solution exists, A* will find it, provided the graph does not have
an infinite cost This completeness property ensures that A* can have completeness.
Efficiency: A* is efficient if an efficient and acceptable heuristic function is used.
Versatility: A* is widely applicable to various problem areas, including wayfinding,
route planning, robotics, game development, and more. A* can be used to find
optimal solutions efficiently as long as a meaningful heuristic can be defined.
Optimized search: A* maintains a priority order to select the nodes with the minor
f(n) value (g(n) and h(n)) for expansion. This allows it to explore promising paths first,
which reduces the search space and leads to faster convergence.
Memory efficiency: A* stores only a limited number of nodes in the priority
queue, which makes it memory efficient, especially for large graphs.
Tunable Heuristics: A*'s performance can be fine-tuned by selecting different
heuristic functions. More educated heuristics can lead to faster convergence and
less expanded nodes.
Memory-bounded heuristic search

• Memory-bounded search is a heuristic search technique in artificial intelligence

that solves problems using a strict, fixed amount of memory.
• By dynamically managing and pruning its search data, it efficiently finds
solutions even on devices with limited resources, making it ideal for real-time
and embedded systems.
•IDA*
Common Memory-Bounded Heuristic Search Combines the space
(Iterative Deepening Performs depth-first searchAlgorithms
efficiency of DFS with the
A*) using increasing cost limits.
optimality of A*.
When memory is full, it
A practical version of A* that
SMA* (Simplified Memory- deletes the node with the
uses available memory
Bounded A*) worst f-cost (estimated
efficiently.
Uses a recursive structure to total cost).
Keeps track of the best
RBFS (Recursive Best-First explore best paths first while
alternative path when
Search) storing only limited
backtracking.
information.
Applications of Memory-Bound Search

• Robotics: Helps robots navigate efficiently and avoid obstacles with limited
memory.
• Autonomous Vehicles: Enables real-time route planning and obstacle
avoidance given onboard memory constraints.
• Game AI: Allows AI agents in games like Chess or Go to make strong decisions
within a fixed memory budget.
• NLP Tasks: Supports tasks like translation or summarization on memory-
constrained devices.
• IoT & Embedded Devices: Facilitates complex tasks, such as image
recognition, on devices with minimal memory.
Advantage
• Memory Efficiency: Works well even when available memory is tight.
• Real-World Ready: Ideal for practical systems with hardware constraints.
• Quality Results: Delivers good solutions using limited resources.
• Adaptive Memory Use: Dynamically manages what to keep and what to prune, using memory wisely.

• Disadvantage:
• Potential for Suboptimal Solutions: May overlook the best solutions due
to aggressive memory pruning.
• Added Computational Overhead: Frequent memory checks and pruning
can slow down the search process.
• Complex Implementation Requirements: Necessitates sophisticated
strategies for selective memory retention and pruning.
• Balancing Challenges: Maintaining both high solution quality and low
memory usage often involves trade-offs.
Heuristic Function for 8 Puzzle problem
Characteristics of Heuristic Functions

• Admissibility: A heuristic is admissible if it never overestimates the true cost

to reach the goal. This property is essential for guaranteeing optimality in
certain algorithms, like A*.
• Consistency: Also known as monotonicity, a heuristic is consistent if the
estimated cost is always less than or equal to the estimated cost from any
neighboring node plus the cost of reaching that neighbor. Consistent heuristics
are always admissible.
Logical Agent
• An Agent can represent Knowledge of its world/environment, its goal and
the current situation.
• Logical Agent has a collection of sentences in logic form.
• By using these logical sentences, the agent decides what to do by inferring
knowledge (conclusion).
• The conclusions are achieved by certain action or set of actions, is appropriate
to achieve its goals.
• Knowledge and reasoning are important to logical agents because they
enable successful behaviors to achieve a desired goal.
Knowledge Based Agents
The central components of knowledge-Based Agent is a Knowledge-Base(KB)
Knowledge-Base contains a set of sentences in a formal language.
Sentences are expressed using a knowledge representation language.
Two generic Functions:
TELL –add new sentences(Facts) to the Knowledge-Base.
“Tell it what it needs to know”.
ASK-query what is known the Knowledge-Base.
“Ask what to do next”.
•A Knowledge-Based Agent is an AI
system that reasons and acts by using a
knowledge base — a collection of facts and
rules about the world.
• A knowledge-based agent must able to do the following:
• An agent should be able to represent states, actions, etc.
• An agent Should be able to incorporate new percepts
• An agent can update the internal representation of the world
• An agent can deduce the hidden properties of the world
• An agent can deduce appropriate actions.
Inference system
• Inference means deriving new sentences from old.
• Inference system allows us to add a new sentence to the knowledge base.
• A sentence is a proposition about the world. Inference system applies logical
rules to the Knowledge-Base to deduce new information.
• Inference system generates new facts so that an agent can update the
Knowledge-Base. An inference system works mainly in two rules
• Forward chaining
• Backward chaining
Various levels of knowledge-based
agent:
• A knowledge-based agent can be viewed at different levels which are given below:
• 1. Knowledge level
• 2. Logical level
• 3. Implementation level
• 1. Knowledge level:
• Represents what the agent knows about the world.
• This includes facts, rules, and relationships about its environment.
• The knowledge is expressed in a knowledge representation language (e.g.,
propositional logic, first-order logic).
• Example:
• The agent knows: “If it is raining, the ground will be wet.”
• 2. Logical Level (Representation and Reasoning Level)
• Defines how knowledge is represented and manipulated.
• Uses formal logic and inference rules to derive conclusions.
• Example:
• Knowledge: “If raining → wet ground”
• Percept: “It is raining”
• Inference: “Therefore, the ground is wet.”
• 3. Implementation level:
• This is the physical representation of logic and knowledge.
• At the implementation level agent perform actions as per logical and
knowledge level.
Approaches to designing a knowledge-based agent:

• Declarative approach: We can create a knowledge-based agent by

initializing with an empty knowledge base and telling the agent all the
sentences with which we want to start with.
• This approach is called Declarative approach.
• Procedural approach: In the procedural approach, we directly encode
desired behavior as a program code.
• Which means we just need to write a program that already encodes the desired
behavior or agent.
Wumpus World
• The Wumpus world is a simple world example to illustrate the worth of a
knowledge-based agent and to represent knowledge representation.
• The Wumpus world is a cave which has 4X4 rooms connected with
passageways.
• So there are total 16 rooms which are connected with each other.
• We have a knowledge-based agent who will go forward in this world.
• The cave has a room with a beast which is called Wumpus, who eats anyone
who enters the room.
Wumpus World

• The Wumpus can be shot by the agent, but the agent has a single arrow.
• In the Wumpus world, there are some Pits rooms which are bottomless, and if
agent falls in Pits, then he will be stuck there forever.
• The exciting thing with this cave is that in one room there is a possibility of
finding a heap of gold.
• So the agent goal is to find the gold and climb out the cave without fallen into
Pits or eaten by Wumpus.
• The agent will get a reward if he comes out with gold, and he will get a penalty
if eaten by Wumpus or falls in the pit.
PEAS description of Wumpus world
Performance measure

+1000 reward points if the agent comes out of the

cave with the gold.
-1000 points penalty for being eaten by the
Wumpus or falling into the pit.
-1 for each action, and -10 for using an arrow.
The game ends if either agent dies or came out of
the cave.

Environment:
•A 4x4 grid of rooms.
•The agent initially in room square [1, 1], facing toward the
right.
•Location of Wumpus and gold are chosen randomly except
the first square [1,1].
•Each square of the cave can be a pit with probability 0.2
except the first square.
• Actuators:
• Left turn, Right turn, Move forward, Grab, Release, Shoot.
• Sensors
• The agent will perceive the stench if he is in the room adjacent to the Wumpus.
(Not diagonally).
• The agent will perceive breeze if he is in the room directly adjacent to the Pit.
• The agent will perceive the glitter in the room where the gold is present.
• The agent will perceive the bump if he walks into a wall.
The Wumpus world Properties(characteristics)

• Partially observable: The Wumpus world is partially observable because the

agent can only perceive the close environment such as an adjacent room.
• Deterministic: It is deterministic, as the result and outcome of the world are
already known.
• Sequential: The order is important, so it is sequential.
• Static: It is static as Wumpus and Pits are not moving.
• Discrete: The environment is discrete.
• Single agent: The environment is a single agent as we have one agent only
and Wumpus is not considered as an agent.
Exploring the Wumpus world

• Step 1:
• The Wumpus world and will determine how the agent will find its goal by
applying logical reasoning.
• Initially, the agent is in the first room or on the square [1,1], and we already
know that this room is safe for the agent, so to represent on the diagram (a)
that room is safe we will add symbol OK. Symbol A is used to represent agent,
symbol B for the breeze, G for Glitter or gold, V for the visited room, P for pits, W
for Wumpus.
• At Room [1,1] agent does not feel any breeze or any Stench which means the
adjacent squares are also OK
• Step 2:
• Now agent needs to move forward, so it will either move to [1, 2], or [2,1]. Let's
suppose agent moves to the room [2, 1], at this room agent perceives some
breeze which means Pit is around this room. The pit can be in [3, 1], or [2,2], so
we will add symbol P? to say that, is this Pit room?
• Now agent will stop and think and will not make any harmful move. The agent
will go back to the [1, 1] room. The room [1,1], and [2,1] are visited by the
agent, so we will use symbol V to represent the visited squares.
• Step 3:
• At the third step, now agent will move to the room [1,2] which is OK. In the
room [1,2] agent perceives a stench which means there must be a Wumpus
nearby.
• But Wumpus cannot be in the room [1,1] as by rules of the game, and also not
in [2,2] (Agent had not detected any stench when he was at [2,1]).
• Therefore agent infers that Wumpus is in the room [1,3], and in current state,
there is no breeze which means in [2,2] there is no Pit and no Wumpus.
• So it is safe, and we will mark it OK, and the agent moves further in [2,2].
• Step4:
• At room [2,2], here no stench and no breezes present so let's suppose agent
decides to move to [2,3].
• At room [2,3] agent perceives glitter, so it should grab the gold and climb out of
the cave.
Logic

• Knowledge base consists of sentences.

• Sentences are expressed according to the syntax of the representation
language.
• Syntax specifies all the sentences that are well formed.
• x+y=4 is a well-formed sentence.
• x4y+= is not well formed sentence.
• Logic must defines the semantics of sentences.
• The semantic defines the truth of each of sentence with respect to the possible
world.
• X=2,y=2 then x+y =4.
• Where as x is, y is 1 then it is not true.
Propositional logic

• Propositional logic
• 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.
• 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.
• A proposition formula which has both true and false values is called
• Statements which are questions, commands, or opinions are not propositions
such as "Where is Rohini", "How are you", "What is your name", are not
propositions.
Syntax of propositional logic:

• The syntax of propositional logic defines the allowable sentences for the
knowledge representation. There are two types of Propositions:
[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.
a) 2+2 is 4, it is an atomic proposition as it is a true fact.
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. There are mainly five connectives, which are
given as follows:
[Link]: A sentence such as ¬ P is called negation of P. A literal can be
either Positive literal or negative literal.
[Link]: 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 Engineer, so we can write it as P ∨ Q.
• 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.
Propositional Logic Connectives:
Truth Table:
Truth table with three propositions:

We can build a proposition composing three propositions P, Q, and R.

This truth table is made-up of 8n Tuples as we have taken three
proposition symbols.
• Precedence of connectives:
• Just like arithmetic operators, there is a precedence order for propositional
connectors or logical operators. This order should be followed while evaluating
a propositional problem. Following is the list of the precedence order for
operators:
Logical equivalence:
• Logical equivalence is one of the features of propositional logic. Two
propositions are said to be logically equivalent if and only if the columns in the
truth table are identical to each other.
• Let's take two propositions A and B, so for logical equivalence, we can write it
as A⇔B. In below truth table we can see that column for ¬A∨ B and A→B, are
identical hence A is Equivalent to B
Reasoning

• The reasoning is the mental process of deriving logical conclusion and making
predictions from available knowledge, facts, and beliefs.
• "Reasoning is a way to infer facts from existing data." It is a general
process of thinking rationally, to find valid conclusions.
• In artificial intelligence, the reasoning is essential so that the machine can also
think rationally as a human brain, and can perform like a human.
Types of Reasoning

• Deductive reasoning
• Inductive reasoning
• Abductive reasoning
• Common Sense Reasoning
• Monotonic Reasoning
• Non-monotonic Reasoning
 Deductive reasoning:

• Deductive reasoning is deducing new information from logically related

known information. It is the form of valid reasoning, which means the
argument's conclusion must be true when the premises are true.
• Deductive reasoning is a type of propositional logic in AI, and it requires various
rules and facts. In deductive reasoning, the truth of the premises guarantees
the truth of the conclusion.
• Deductive reasoning mostly starts from the general premises to the specific
conclusion, which can be explained as below example.
The general process of deductive reasoning is given below:

• Example:
• Premise-1: All the human eats veggies
• Premise-2: Suresh is human.
• Conclusion: Suresh eats veggies.
• The general process of deductive reasoning is
2. Inductive Reasoning:
• Inductive reasoning is a form of reasoning to arrive at a conclusion using
limited sets of facts by the process of generalization.
• It starts with the series of specific facts or data and reaches to a general
statement or conclusion.
• Inductive reasoning is a type of propositional logic, which is also known as
cause-effect reasoning or bottom-up reasoning.

• In inductive reasoning, we use historical data or various premises to generate

a generic rule, for which premises support the conclusion.

• In inductive reasoning, premises provide probable supports to the conclusion,

so the truth of premises does not guarantee the truth of the conclusion.
• Example:
• Premise: All of the pigeons we have seen in the zoo are white.
• Conclusion: Therefore, we can expect all the pigeons to be white.
3. Abductive reasoning:

• Abductive reasoning is a form of logical reasoning which starts with single or

multiple observations then seeks to find the most likely explanation or
conclusion for the observation.
• Abductive reasoning is an extension of deductive reasoning, but in abductive
reasoning, the premises do not guarantee the conclusion.
• Example:
• Implication: Cricket ground is wet if it is raining
• Axiom: Cricket ground is wet.
• Conclusion It is raining.
4. Common Sense Reasoning

• Common sense reasoning is an informal form of reasoning, which can be gained

through experiences.
• Common Sense reasoning simulates the human ability to make presumptions
about events which occurs on every day.
• It relies on good judgment rather than exact logic and operates on heuristic
knowledge and heuristic rules.
• Example:

[Link] person can be at one place at a time.

[Link] I put my hand in a fire, then it will burn.
• The above two statements are the examples of common sense reasoning which a
human mind can easily understand and assume.
5. Monotonic Reasoning:

• In monotonic reasoning, once the conclusion is taken, then it will remain the
same even if we add some other information to existing information in our
knowledge base. In monotonic reasoning, adding knowledge does not decrease
the set of prepositions that can be derived.
• To solve monotonic problems, we can derive the valid conclusion from the
available facts only, and it will not be affected by new facts.
• Monotonic reasoning is not useful for the real-time systems, as in real time,
facts get changed, so we cannot use monotonic reasoning.
• Monotonic reasoning is used in conventional reasoning systems, and a logic-
based system is monotonic.
• Example:
• Earth revolves around the Sun.
• It is a true fact, and it cannot be changed even if we
• Advantages of Monotonic Reasoning:
• In monotonic reasoning, each old proof will always remain valid.
• If we deduce some facts from available facts, then it will remain valid for
always.
• Disadvantages of Monotonic Reasoning:
• We cannot represent the real world scenarios using Monotonic reasoning.
• Hypothesis knowledge cannot be expressed with monotonic reasoning, which
means facts should be true.
• Since we can only derive conclusions from the old proofs, so new knowledge
from the real world cannot be added.
6. Non-monotonic Reasoning

• In Non-monotonic reasoning, some conclusions may be invalidated if we add

some more information to our knowledge base.
• Logic will be said as non-monotonic if some conclusions can be invalidated by
adding more knowledge into our knowledge base.
• Non-monotonic reasoning deals with incomplete and uncertain models.
• "Human perceptions for various things in daily life, "is a general example of
non-monotonic reasoning.
• Example: Let suppose the knowledge base contains the following knowledge:
• Birds can fly
• Penguins cannot fly
• Pitty is a bird
• So from the above sentences, we can conclude that Pitty can fly.
• However, if we add one another sentence into knowledge base "Pitty is a
penguin", which concludes "Pitty cannot fly", so it invalidates the above
conclusion.
• Advantages of Non-monotonic reasoning:
• For real-world systems such as Robot navigation, we can use non-monotonic
reasoning.
• In Non-monotonic reasoning, we can choose probabilistic facts or can make
assumptions.
• Disadvantages of Non-monotonic Reasoning:
• In non-monotonic reasoning, the old facts may be invalidated by adding new
sentences.
• It cannot be used for theorem proving.