UNIT 2: Problem Formulation: Defining problem as a state space

search, Problem reduction, problem characteristics, Production

Systems. Blind Search Techniques: Depth First Search & Breadth
First Search
Structure

2.0 Introduction
2.1 Learning Outcomes
2.2 Defining problem as a state space search
2.3 Problem reduction
2.4 Problem characteristics
2.5 Production Systems
2.6 Blind Search Techniques
2.6.1 Depth First Search
2.6.2 Bredth First Search
2.7 Summary
2.8 Unit End Questions
2.9 References and Suggested Readings
 2.0: Introduction
State space search is a problem-solving technique used in Artificial Intelligence (AI) to find the
solution path from the initial state to the goal state by exploring the various states. The state
space search approach searches through all possible states of a problem to find a solution. It is an
essential part of Artificial Intelligence and is used in various applications, from game-playing
algorithms to natural language processing.

Artificial intelligence stands as a continuously advancing field at the forefront of technological

progress. At its core, AI entails crafting algorithms and systems capable of emulating human
intelligence, tackling intricate problems, and making informed decisions. In this piece, we will
delve into the essence of problem characteristics within artificial intelligence, exploring their
significant properties and the systematic approach to effectively address them.

Problems in Artificial Intelligence (AI) manifest in diverse forms, each presenting its own set of
challenges and potential for innovation. From image recognition to natural language processing,
AI problems exhibit distinct attributes that influence the methodologies and techniques employed
to tackle them. In this article, we delve into the fundamental characteristics of AI problems,
shedding light on what renders them captivating and substantial. Problem Reduction
Techniques in AI are ways to break down big, complicated problems into smaller, more
manageable parts. They help AI systems tackle tough challenges step by step. Every automatic
system with a specific algorithm must have rules for its proper functioning and functioning
differently. The production systems in artificial intelligence are rules applied to different
behaviors and environments. Artificial Intelligence is the study of building agents that act
rationally. Most of the time, these agents perform some kind of search algorithm in the
background in order to achieve their tasks.
 A search problem consists of:

o A State Space. Set of all possible states where you can be.
o A Start State. The state from where the search begins.
o A Goal State. A function that looks at the current state returns whether or not it is
the goal state.
 The Solution to a search problem is a sequence of actions, called the plan that transforms
the start state to the goal state.
 This plan is achieved through search algorithms.
 2.1: Learning Outcomes

After studying this chapter, the student will be able:

 Understanding problem formulation means recognizing how real-world problems can be

broken down into a state space
 Understanding problem reduction involves recognizing how a complex problem can be
decomposed into smaller sub-problems that are easier to solve.
 Understand the characteristics of a problem, one needs to consider its structure. Is it fully
observable or partially observable?
 Understanding production systems involves knowing how they work through sets of rules
(if-then statements) that transform one state into another
 Understanding DFS involves recognizing its mechanism of exploring a path to its deepest
point before backtracking.
 Understanding BFS means recognizing that it explores all nodes at the current depth level
before moving to the next depth level.

2.2: Defining problem as a state space search A

st
ate space is a way to mathematically represent a problem by defining all the possible states in
which the problem can be. This is used in search algorithms to represent the initial state, goal
state, and current state of the problem. Each state in the state space is represented using a set of
variables.

The efficiency of the search algorithm greatly depends on the size of the state space, and it is
important to choose an appropriate representation and search strategy to search the state space
efficiently.

One of the most well-known state space search algorithms is the A algorithm. Other commonly
used state space search algorithms include breadth-first search (BFS), depth-first search
(DFS), hill climbing, simulated annealing, and genetic algorithms.

Features of State Space Search

State space search has several features that make it an effective problem-solving technique in
Artificial Intelligence. These features include:

 Exhaustiveness:
State space search explores all possible states of a problem to find a solution.
  Completeness:
If a solution exists, state space search will find it.

 Optimality:
Searching through a state space results in an optimal solution.

 Uninformed and Informed Search:

State space search in artificial intelligence can be classified as uninformed if it provides
additional information about the problem.

In contrast, informed search uses additional information, such as heuristics, to guide the
search process.

Steps in State Space Search

The steps involved in state space search are as follows:

 To begin the search process, we set the current state to the initial state.
 We then check if the current state is the goal state. If it is, we terminate the algorithm and
return the result.
 If the current state is not the goal state, we generate the set of possible successor states
that can be reached from the current state.
 For each successor state, we check if it has already been visited. If it has, we skip it, else
we add it to the queue of states to be visited.
  Next, we set the next state in the queue as the current state and check if it's the goal state.
If it is, we return the result. If not, we repeat the previous step until we find the goal state
or explore all the states.
 If all possible states have been explored and the goal state still needs to be found, we
return with no solution.

State Space Representation

State space Representation involves defining an INITIAL STATE and a GOAL STATE and
then determining a sequence of actions, called states, to follow.

 State:
A state can be an Initial State, a Goal State, or any other possible state that can be
generated by applying rules between them.
 Space:
In an AI problem, space refers to the exhaustive collection of all conceivable states.
 Search:
This technique moves from the beginning state to the desired state by applying good rules
while traversing the space of all possible states.
 Search Tree:
To visualize the search issue, a search tree is used, which is a tree-like structure that
represents the problem. The initial state is represented by the root node of the search tree,
which is the starting point of the tree.
 Transition Model:
This describes what each action does, while Path Cost assigns a cost value to each path,
an activity sequence that connects the beginning node to the end node. The optimal
option has the lowest cost among all alternatives.

Example of State Space Search

The 8-puzzle problem is a commonly used example of a state space search. It is a sliding puzzle
game consisting of 8 numbered tiles arranged in a 3x3 grid and one blank space. The game aims
to rearrange the tiles from their initial state to a final goal state by sliding them into the blank
space.

To represent the state space in this problem, we use the nine tiles in the puzzle and their
respective positions in the grid. Each state in the state space is represented by a 3x3 array with
values ranging from 1 to 8, and the blank space is represented as an empty tile.

The initial state of the puzzle represents the starting configuration of the tiles, while the goal
state represents the desired configuration. Search algorithms utilize the state space to find a
sequence of moves that will transform the initial state into the goal state.
This algorithm guarantees a solution but can become very slow for larger state spaces.
Alternatively, other algorithms, such as A search, use heuristics to guide the search more
efficiently.

Our objective is to move from the current state to the target state by sliding the numbered tiles
through the blank space. Let's look closer at reaching the target state from the current state.
To summarize, our approach involved exhaustively exploring all reachable states from the
current state and checking if any of these states matched the target state.

Applications of State Space Search

 State space search algorithms are used in various fields, such as robotics, game playing,
computer networks, operations research, bioinformatics, cryptography, and supply chain
management. In artificial intelligence, state space search algorithms can solve problems
like pathfinding, planning, and scheduling.
 They are also useful in planning robot motion and finding the best sequence of actions to
achieve a goal. In games, state space search algorithms can help determine the best move
for a player given a particular game state.
 State space search algorithms can optimize routing and resource allocation in computer
networks and operations research.
 In Bioinformatics, state space search algorithms can help find patterns in biological data
and predict protein structures.
 In Cryptography, state space search algorithms are used to break codes and find
cryptographic keys.

Conclusion

 State Space Search is a problem-solving technique used in AI to find a solution to a

problem by exploring all possible states of the problem.
 It is an exhaustive, complete, and optimal search process that can be classified as
uninformed or informed.
 State Space Representation is a crucial step in the state space search process as it
determines the efficiency of the search algorithm.
 State space search in artificial intelligence has several applications, including game-
playing algorithms, natural language processing, robotics, planning, scheduling, and
computer vision.

2.3: Problem reduction

Problem Reduction Techniques in AI are ways to break down big, complicated problems into
smaller, more manageable parts. They help AI systems tackle tough challenges step by step.

In this blog, we’ll look at different types of problem reduction techniques in AI, see how they
work in real life, and learn why they’re so important for AI. We’ll keep things simple and easy to
understand, perfect for those just starting out in AI.
 Understanding Problem Reduction Techniques in AI

Problem Reduction Techniques in AI are clever ways to make big problems smaller and easier to
solve.

Think of them like breaking a giant puzzle into smaller pieces. Instead of trying to solve one
huge problem, AI uses these techniques to split it into bite-sized chunks.

These methods help AI systems tackle complex tasks without getting overwhelmed.

They work by simplifying problems, cutting out unnecessary information, or turning tricky
issues into more familiar ones.

By using Problem Reduction Techniques, AI can work faster and smarter. It’s like having a
toolbox full of different problem-solving tricks.

This approach helps AI handle all sorts of challenges, from playing chess to planning routes or
understanding human language.
 Common Problem Reduction Techniques in AI

Let’s look at some common Problem Reduction Techniques used in AI. These are different tools
that help AI break down big problems into smaller ones.

Divide and Conquer

This is like cutting a big cake into slices. AI splits a big problem into smaller parts, solves each
part, and then puts the answers back together.

Abstraction

Imagine looking at a map instead of the real world. Abstraction removes unnecessary details,
focusing only on what’s important to solve the problem.

State Space Reduction

This is like finding shortcuts in a maze. It helps AI ignore paths that won’t lead to a solution,
saving time and effort.
Problem Transformation

Sometimes, it’s easier to change the problem into one we already know how to solve. It’s like
turning a word problem into a math equation.

These techniques help AI tackle complex problems more easily. They’re like different ways to
simplify puzzles, making them easier for AI to solve.

Real-world Applications

et’s look at how Problem Reduction Techniques in AI are used in the real world. These methods
help solve everyday problems in clever ways.

Example 1: Navigation Apps

When you use a map app on your phone, it uses problem reduction. Instead of checking every
possible route, it breaks the journey into smaller parts and finds the best path for each section.
Example 2: Voice Assistants

When you talk to Siri or Alexa, they break down your words into smaller parts. This helps them
understand what you’re saying and find the right answer more quickly.

Example 3: Online Shopping

Ever wonder how websites suggest products you might like? They use problem reduction to
break down your shopping history into patterns, making it easier to predict what you’ll want
next.

Example 4: Chess Programs

AI that plays chess doesn’t look at every possible move. It breaks the game into smaller
situations, focusing on the most promising moves to save time and make smarter choices.

Benefits of Problem Reduction Techniques in AI

Problem Reduction Techniques in AI come with lots of benefits. Let’s look at why they’re so
helpful:
1. Faster Problem Solving

By breaking big problems into smaller ones, AI can work much quicker. It’s like solving many
small puzzles instead of one huge one.

2. Better Use of Resources

These techniques help AI use computer power more wisely. It doesn’t waste time on parts of the
problem that aren’t important.

3. Handling Complex Problems

Some problems are too big to solve all at once. Problem reduction lets AI tackle issues that
would otherwise be too difficult.

4. More Accurate Results

By focusing on smaller parts, AI can be more precise. It’s easier to get things right when you’re
dealing with simpler tasks.

5. Flexibility

These methods can be used for all sorts of problems. This makes AI more versatile and able to
handle different challenges.

6. Easier to Understand

When a problem is broken down, it’s often easier for humans to see how the AI is working. This
helps us trust and improve AI systems.

These benefits show why Problem Reduction Techniques are so important in AI. They make AI
smarter, faster, and more useful in our daily lives.

Challenges in Applying Problem Reduction in AI

Problem Reduction Techniques in AI are powerful, but they come with their own set of
challenges.

Choosing the right method isn’t always straightforward, and sometimes important details can get
lost in the simplification process.

Combining solutions from smaller problems into one big answer can be tricky. There’s also a
risk of making simple problems more complex by breaking them down too much.
Balancing speed and accuracy is another ongoing challenge.

AI systems need to be flexible, adapting their approach to different situations. What works for
one problem might not work for another.

Understanding these challenges helps us use Problem Reduction Techniques more effectively,
improving AI’s ability to solve complex problems in the real world.

Conclusion

In conclusion, Problem Reduction Techniques in AI are powerful tools that help tackle complex
challenges. By breaking big problems into smaller, manageable parts, AI can work more
efficiently and accurately. While these methods come with their own challenges, they’re crucial
for advancing AI capabilities. As we continue to refine these techniques, we’ll see AI solving
even more complex problems, making our lives easier, and opening up new possibilities in
technology.

2.4: Problem Characteristics

Problems in Artificial Intelligence (AI) manifest in diverse forms, each presenting its own set of
challenges and potential for innovation. From image recognition to natural language processing,
AI problems exhibit distinct attributes that influence the methodologies and techniques employed
to tackle them. In this article, we delve into the fundamental characteristics of AI problems,
shedding light on what renders them captivating and substantial.

Key Issues in AI Characteristics

1. The Crux of AI Difficulties

artificial intelligence issues are particular animals. They habitually incorporate a level of
complexity and unusual nature not ordinarily present in traditional programming. It is
fundamental to grasp these characteristics to make AI arrangements that work.

2. Intricacy

Artificial intelligence, taking everything into account, challenges are more troublesome than
traditional PC occupations. The huge information volumes that artificial intelligence frameworks
should deal with and the confounded calculations they use are the wellsprings of this intricacy.

3. Uncertainty
AI instead of dated computations, occasionally handles unclear and deficient data. man-made
brainpower structures ought to use probabilistic reasoning to pursue assumptions and choices
because of this weakness.

4. Flexibility

Artificial intelligence frameworks need to conform to new data and evolving environmental
elements. Developers are tested by this powerful nature to plan versatile calculations that might
develop and change over the long haul.

5. Objective-centered

Artificial intelligence calculations are made to achieve specific targets. These targets may be
pretty much as fundamental as arranging information or as modern as facial acknowledgement or
language interpretation.

Steps for the Problem Characteristics

The intricacy of AI issues necessitates a methodical approach. Here is a methodical approach to
comprehending and resolving these issues:

1. Identifying the Issue

Clearly defining the issue is the first step. Just what problem are you attempting to solve? This
might entail analysing big databases, identifying trends, or formulating forecasts. Solving an
issue with clarity makes it easier.

2. Gathering & Preparing Data

AI is data-driven. Gather pertinent information and get it ready for analysis. This includes
sanitising the data, dealing with null values, and maybe converting it into a format that AI
systems can understand.

3. Selecting the Proper Algorithm

Different AI techniques are needed for different challenges. Neural networks, for instance, may
perform better for image recognition tasks than decision trees for categorization tasks. Choosing
the right algorithm is essential.

4. Getting the Model Ready

To do this, data must be fed into the algorithm so that it may learn from it. Iterative training
necessitates continuous modification and improvement.

5. Assessment and Enhancement

Analyse the model's performance after training. Utilise measures like as recall, accuracy, and
precision to assess the effectiveness of your AI. Optimise the model to perform better based on
these evaluations.

6. Implementation and Tracking

The AI solution is implemented in a real-world setting after it has been optimised. It must be
continuously observed to make sure it adjusts to new information and circumstances.

Artificial intelligence (AI) is primarily concerned with the search process, therefore selecting the
optimal answer requires a technique.

Before choosing a suitable approach for a given problem, we must classify the problem
according to the following attributes.

o Is it possible to break the problem down into manageable, easily solved subproblems?
o Are stages in a solution reversible or ignorable?
o Is the problem's universe predictable?
o Is a sound answer to the issue universal or specific?
o Is there a path or a state where the problem can be solved?
o How does knowledge fit into the artificial intelligence problem-solving process?
o Does a problem-solving task include interaction with people?

1. Can the problem be broken down into manageable, easily solved subproblems?
Separating an issue into more modest, more reasonable sub-issues can frequently make it simpler
to tackle. By taking apart the main pressing concern into more modest parts, you can handle each
part independently, possibly working on the general errand. This approach is especially helpful
for complex issues that could appear to be overpowering when drawn nearer in general.
Notwithstanding, whether an issue is decomposable into simple to-tackle sub-issues relies upon
the idea of the actual issue methods to address them. This gradual methodology frequently
prompts more clear bits of knowledge and more powerful arrangements.

(picture)

2. Can solution steps be ignored or undone?

A verified lemma in the Theorem Proving issue can be disregarded for the remainder of the
procedure.

We refer to these issues as ignorable issues.

Moves in the 8-Puzzle can be reversed and retraced.

We refer to these issues as recoverable issues.

Justification:
The 8-Puzzle is viewed as a recoverable issue because any move made to change the riddle's
setup can be scattered by switching that move. For example, if a tile is slid into an unfilled space,
a similar tile can be moved back to its unique position. This property permits one to backtrack
through the grouping of moves to any past state, empowering recuperation and re-investigation
in various ways in the arrangement cycle. In this way, the riddle upholds reversible activities and
complete recoverability.

Retracted is a move in chess play.

We refer to these issues as irreversible issues.

Justification:

Playing chess is viewed as an irrecoverable issue because, albeit individual moves can be
withdrawn in relaxed play, each move on a very basic level changes the game's state in a manner
that can't be completely scattered. For example, a withdrawn move doesn't delete the gathered
upper hand or information acquired by one or the other player. Not at all like riddles where states
can be definitively returned, chess includes developing procedures and places that make genuine
recuperation to a past state deficient and unfeasible.

A straightforward, never-backtracking control structure can be used to handle insignificant

issues. Backtracking is an effective way to tackle recoverable difficulties. Planning allows
recoverable style solutions to address irrecoverable difficulties.

3. Is the problem's universe predictable?

We are unable to predict the movements of other players throughout their turns or the precise
locations of all the cards when playing bridge. Planning may be used to create a series of
operators for certain outcome issues that will inevitably result in a solution.

Example:

Think about a robot that is assigned the duty of cleaning a room. The following would be part of
the planning process:
 o Determining the Objective: A tidy room.
o Defined Operators: such as "move to a location," "pick up object," and "vacuum floor."
o Formulating a Scheme: a series of steps, like this: Go to the first corner.
o The floor is vacuumed.
o Proceed to the following location.
o Clear the clutter.
o Continue until the space is tidy.
A series of produced operators can only have a fair chance of leading to a solution for uncertain
outcome issues. As the plan is implemented and the required input is received, revisions are
made.

Example:

o Think of an autonomous vehicle navigating a metropolis to get to its destination, for

instance:
o Determining the Objective: Get to a given address.
o Defined Operators: Activities such as "drive straight," "turn left," "turn right," "stop at a
traffic light," "yield to pedestrians."
o Formulating a Scheme: a series of steps, as driving straight for two blocks.
o At the junction, make a left.
o Proceed straight ahead for three blocks.
o Make a right turn.

4. Is a good answer for the issue outright or relative?

Regarding the travelling Sales rep Issue, we need to attempt all ways to see it as the most limited
one.

Any path problem can be solved using heuristics that suggest good paths to explore. For best-
path problems, a much more exhaustive search will be performed.

5. Is the solution to the problem a state or a path?

In artificial intelligence, the answer for an issue can be either a state or a way, contingent upon
the issue type. The fact that satisfies the objective circumstances makes for state-based issues,
the arrangement a last expression. For way-based issues, the arrangement is a succession of
states (way) from the underlying state to the objective state.

6. How does knowledge fit into the artificial intelligence problem-solving process?
Playing Chess:

Chess Playing Considering the chess problem once more, let's say you have infinite processing
power. What knowledge, if any, would a perfect programme need? The answer is very little, just
the rules governing legal moves and a basic control mechanism that carries out a suitable search
procedure. Of course, a little more knowledge about things like sound strategy and tactics could
greatly aid in limiting the search and expediting the program's execution.
Reading Newspaper:

Now think about the issue of sifting through the daily newspapers to determine which ones are
conservative and which are liberal in an impending election. Once more, supposing infinite
computational capacity, what level of expertise would a machine seeking to resolve this issue
require? The response is substantial this time.

7. Does the task of solving a problem require human interaction?

Sometimes it is useful to program computers to solve problems in ways that the majority of
people would not be able to understand. This is fine if the level of the interaction between the
computer and its human users is problem-in solution-out.

But increasingly we are building programs that require intermediate interaction with people, both
to provide additional input to the program and to provide additional reassurance to the user. The
solitary problem, in which there is no intermediate communication and no demand for an
explanation of the reasoning process.

The conversational problem, in which intermediate communication is to provide either additional

assistance to the computer or additional information to the user.

Examples of AI Applications and Challenges Across Domains

1. Robotics
Problem: A delivery robot navigating a busy warehouse to locate and retrieve a specific item.

Characteristics:

o Complexity: Industrial storage is networked, in the middle of things, with obstacles, and
other robots and people moving unpredictably. This robot must process the visual scene,
plan the route effectively, and detect and avoid possible collisions.
o Dynamism: A combination of outside factors leads to change, which is a constant inside
the warehouse. Unpredictable system failures or spontaneous tasks can make the robot
change its means and decision-making at the moment of need.
o Uncertainty: Sensor data (such as images obtained from a camera) might be noisy,
incomplete, and unstable. The robot could be handling decisions based on fragmented or
formless pieces of information.

2. Natural Language Processing (NLP)

Problem: A sentiment analysis system in NLP classifying customer reviews as positive,
negative, or neutral.

Characteristics:

o Subjectivity: Human language is nuanced. Sarcasm, irony, and figurative expressions can
be difficult for machines to accurately interpret.
 o Need for Context: Understanding sentiment may depend on cultural references, product-
specific knowledge, or even the reviewer's prior interactions with the company.
o Ambiguity: A single word or phrase could have multiple meanings, affecting the overall
sentiment of the text.

3. Computer Vision
Problem: A medical image recognition system in Computer Vision designed to detect tumours in
X-rays or MRI scans.

Characteristics:

o Complexity: Medical images are highly detailed and can exhibit subtle variations. The
system needs to distinguish between healthy tissue and potential abnormalities.
o Uncertainty: Images may contain noise or artefacts. The presence of a tumour might not
be immediately obvious, requiring the system to handle ambiguity.
o Ethical Considerations: False positives or false negatives have serious consequences for
patient health. Accuracy, transparency, and minimizing bias are crucial.
Conclusion
The foundational elements of AI-based challenges-complexity, uncertainty, subjectivity, and
beyond-present an inherent difficulty that cannot be overlooked. Understanding these
characteristics is imperative for constructing AI solutions effectively. Leveraging machine
learning, probabilistic reasoning, and knowledge representation, which serve as the cornerstones
of AI development, alongside ethical considerations, designers and scientists can adeptly
navigate these complexities. This approach ensures that AI is shaped in a manner that is
beneficial to society.

2.5: Production Systems

Every automatic system with a specific algorithm must have rules for its proper functioning and
functioning differently. The production systems in artificial intelligence are rules applied to
different behaviors and environments.

In this article, we will learn about production systems, their components, and production system
rules.

Production System in AI
In artificial intelligence (AI), a production system refers to a type of rule-based system that is
designed to provide a structured approach to problem solving and decision-making. This
framework is particularly influential in the realm of expert systems, where it simulates human
decision-making processes using a set of predefined rules and facts.
Let's consider an example of Expert System for Medical Diagnosis.

Scenario: A patient comes to a healthcare facility with the following symptoms: fever, severe
headache, sensitivity to light, and stiff neck.

Mediacal diagnosis operates in the following manner:

Input: A healthcare professional inputs the symptoms into MediDiagnose.

Processing:
MediDiagnose reviews its knowledge base for rules that match the given symptoms.
It identifies several potential conditions but recognizes a strong match for meningitis based on
the combination of symptoms.
Output:
The system suggests that meningitis could be a possible diagnosis and recommends further tests
to confirm, such as a lumbar puncture.
It also provides a list of other less likely conditions based on the symptoms for comprehensive
differential diagnosis.
MediDiagnose uses its rule-based system to quickly filter through vast amounts of medical data
to provide preliminary diagnoses. This assists doctors in focusing their investigative efforts more
efficiently and potentially speeds up the process of reaching an accurate diagnosis.

Key Components of a Production System in AI

The key components of production system includes:

Knowledge Base: This is the core repository where all the rules and facts are stored. In AI, the
knowledge base is critical as it contains the domain-specific information and the if-then rules that
dictate how decisions are made or actions are taken.
Inference Engine: The inference engine is the mechanism that applies the rules to the known
facts to derive new facts or to make decisions. It scans the rules and decides which ones are
applicable based on the current facts in the working memory. It can operate in two modes:
Forward Chaining (Data-driven): This method starts with the available data and uses the
inference rules to extract more data until a goal is reached.
Backward Chaining (Goal-driven): This approach starts with a list of goals and works backwards
to determine what data is required to achieve those goals.
Working Memory: Sometimes referred to as the fact list, working memory holds the dynamic
information that changes as the system operates. It represents the current state of knowledge,
including facts that are initially known and those that are deduced throughout the operation of
the system.
Control Mechanism: This governs the order in which rules are applied by the inference engine
and manages the flow of the process. It ensures that the system responds appropriately to
changes in the working memory and applies rules effectively to reach conclusions or solutions.
Types of Production Systems
Production systems in AI can be categorized based on how they handle and process knowledge.
This categorization includes Rule-Based Systems, Procedural Systems, and Declarative Systems,
each possessing unique characteristics and applications.
1. Rule-Based Systems
Explanation of Rule-Based Reasoning
Rule-based systems operate by applying a set of pre-defined rules to the given data to deduce
new information or make decisions. These rules are generally in the form of conditional
statements (if-then statements) that link conditions with actions or outcomes.
Examples of Rule-Based Systems in AI
Diagnostic Systems: Like medical diagnosis systems that infer diseases from symptoms.
Fraud Detection Systems: Used in banking and insurance, these systems analyze transaction
patterns to identify potentially fraudulent activities.
2. Procedural Systems
Description of Procedural Knowledge
Procedural systems utilize knowledge that describes how to perform specific tasks. This
knowledge is procedural in nature, meaning it focuses on the steps or procedures required to
achieve certain goals or results.
Applications of Procedural Systems
Manufacturing Control Systems: Automate production processes by detailing step-by-step
procedures to assemble parts or manage supply chains.
Interactive Voice Response (IVR) Systems: Guide users through a series of steps to resolve
issues or provide information, commonly used in customer service.
3. Declarative Systems
Understanding Declarative Knowledge
Declarative systems are based on facts and information about what something is, rather than how
to do something. These systems store knowledge that can be queried to make decisions or solve
problems.
Instances of Declarative Systems in AI
Knowledge Bases in AI Assistants: Power virtual assistants like Siri or Alexa, which retrieve
information based on user queries.
Configuration Systems: Used in product customization, where the system decides on product
specifications based on user preferences and declarative rules about product options.
Each type of production system offers different strengths and is suitable for various applications,
from straightforward rule-based decision-making to complex systems requiring intricate
procedural or declarative reasoning.

How Production Systems Function?

The operation of a production system in AI follows a cyclic pattern:

Match: The inference engine checks which rules are triggered based on the current facts in the
working memory.
Select: From the triggered rules, the system (often through the control mechanism) selects one
based on a set of criteria, such as specificity, recency, or priority.
Execute: The selected rule is executed, which typically modifies the facts in the working
memory, either by adding new facts, changing existing ones, or removing some.
Applications of Production Systems in AI
Production systems are used across various domains where decision-making can be encapsulated
into clear, logical rules:
Expert Systems: For diagnosing medical conditions, offering financial advice, or making
environmental assessments.
Automated Planning: Used in logistics to optimize routes and schedules based on current data
and objectives.
Game AI: Manages non-player character behavior and decision-making in complex game
environments.
Conclusion
Production systems represent a structured approach in AI that emphasizes clear rules and
systematic processes. While they are powerful for scenarios where problems can be clearly
defined through rules, they may not be suitable for tasks requiring nuanced understanding or
adaptation beyond the pre-defined rules. In modern AI, production systems often work alongside
other AI techniques, such as machine learning, to leverage the strengths of both rule-based and
data-driven approaches.

Are you passionate about data and looking to make one giant leap into your career? Our Data
Science Course will help you change your game and, most importantly, allow students,
professionals, and working adults to tide over into the data science immersion. Master state-of-
the-art methodologies, powerful tools, and industry best practices, hands-on projects, and real-
world applications. Become the executive head of industries related to Data Analysis, Machine
Learning, and Data Visualization with these growing skills. Ready to Transform Your Future?
Enroll Now to Be a Data Science Expert!

2.6: Blind Search Tecniques

Artificial Intelligence is the study of building agents that act rationally. Most of the time, these
agents perform some kind of search algorithm in the background in order to achieve their tasks.
 A search problem consists of:

o A State Space. Set of all possible states where you can be.
o A Start State. The state from where the search begins.
o A Goal State. A function that looks at the current state returns whether or not it is
the goal state.
 The Solution to a search problem is a sequence of actions, called the plan that transforms
the start state to the goal state.
 This plan is achieved through search algorithms.
Types of search algorithms:
There are far too many powerful search algorithms out there to fit in a single article. Instead, this
article will discuss six of the fundamental search algorithms, divided into two categories, as
shown below.
Note that there is much more to search algorithms than the chart I have provided above.
However, this article will mostly stick to the above chart, exploring the algorithms given there.
Uninformed Search Algorithms:
A blind search (also called an uninformed search) is a search that has no information about its
domain The search algorithms in this section have no additional information on the goal node
other than the one provided in the problem definition. The plans to reach the goal state from the
start state differ only by the order and/or length of actions. Uninformed search is also
called Blind search. These algorithms can only generate the successors and differentiate
between the goal state and non goal state.

The following uninformed search algorithms are discussed in this section.

1. Depth First Search
2. Breadth First Search

2.6.1: Depth First Search

Depth-first Search

o Depth-first search isa recursive algorithm for traversing a tree or graph data structure.
o 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.
o DFS uses a stack data structure for its implementation.
o The process of the DFS algorithm is similar to the BFS algorithm.

Note: Backtracking is an algorithm technique for finding all possible solutions using recursion.
Advantage:

o 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.
 o It takes less time to reach to the goal node than BFS algorithm (if it traverses in the right
path).
o With the help of this we can stores the route which is being tracked in memory to save
time as it only needs to keep one at a particular time.
Disadvantage:

o There is the possibility that many states keep re-occurring, and there is no guarantee of
finding the solution.
o DFS algorithm goes for deep down searching and sometime it may go to the infinite loop.
o The de�pth-first search (DFS) algorithm does not always find the shorte�st path to a
solution.

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.

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.

2.6.2: Breadth First Search

Breadth-first Search:

o 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.
o 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.
o The breadth-first search algorithm is an example of a general-graph search algorithm.
o Breadth-first search implemented using FIFO queue data structure.
Advantages:

o BFS will provide a solution if any solution exists.

o 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.
o It also helps in finding the shortest path in goal state, since it needs all nodes at the same
hierarchical level before making a move to nodes at lower levels.
o It is also very easy to comprehend with the help of this we can assign the higher rank
among path types.
Disadvantages:

o It requires lots of memory since each level of the tree must be saved into memory to
expand the next level.
o BFS needs lots of time if the solution is far away from the root node.
 o It can be very inefficient approach for searching through deeply layered spaces, as it
needs to thoroughly explore all nodes at each level before moving on to the next

Example:
In the below tree structure, we have shown the traversing of the tree using BFS algorithm from
the root node S to goal node K. BFS search algorithm traverse in layers, so it will follow the path
which is shown by the dotted arrow, and the traversed path will be:

1. S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K

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.
 2.7: Summary

oblem formulation in AI involves representing real-world problems in a structured format to be

solved algorithmically. The first step in this process is defining the problem as a state space
search, where a problem is mapped to a set of possible states, starting from an initial state and
transitioning toward a goal state through defined operators. These states and transitions form the
state space, and the problem-solving process involves searching for a path from the initial state
to the goal state. State space search can be either uninformed (blind) or informed (using
heuristics).

Another critical component of problem formulation is problem reduction, which simplifies

complex problems by breaking them down into smaller, more manageable sub-problems. These
sub-problems are solved individually and combined to form the final solution, which is often
represented using an AND-OR graph structure. Problem characteristics help define the nature
of the problem, including whether it is deterministic or stochastic, fully observable or partially
observable, static or dynamic, and whether the state space is discrete or continuous. These
characteristics influence the choice of search techniques and the overall approach to problem-
solving.

Production systems are frameworks used in AI for problem-solving through rules and data.
They consist of a knowledge base, a set of rules (production rules), and a control system that
determines which rules to apply. These systems are common in expert systems and rule-based
reasoning.

When discussing blind search techniques, two of the most basic methods are Depth-First
Search (DFS) and Breadth-First Search (BFS). DFS explores a path to its deepest point before
backtracking, using a stack to track nodes. While it requires less memory, it does not guarantee
finding the shortest path. On the other hand, BFS explores all nodes at one depth level before
moving to the next, ensuring the shortest path is found if all actions have equal cost, but it
consumes more memory. Both DFS and BFS have their strengths and weaknesses, depending on
the problem's structure, and are foundational to more advanced search algorithms.

These concepts—problem formulation, reduction, state space search, and blind search techniques
—are essential for solving a wide range of AI problems, from game playing to navigation tasks,
and provide the foundation for more sophisticated algorithms in the field of artificial intelligence.

2.8: Unit End Questions

A. Multiple Choice Questions

1. Which of the following is true about Breadth-First Search (BFS)?

A) BFS uses a stack data structure to track nodes
B) BFS guarantees the shortest path when all actions have equal cost
C) BFS explores one path to its deepest point before backtracking
D) BFS is not guaranteed to find a solution in finite search spaces
2. What is the primary goal of state space search in problem-solving?
A) To find the optimal solution based on a set of heuristics
B) To explore all possible solutions systematically from an initial state to a goal state
C) To reduce the size of the problem space by eliminating unnecessary states
D) To generate random solutions until one matches the goal
3. What is problem reduction in AI problem-solving?
A) Reducing the size of the state space by eliminating redundant states
B) Simplifying a complex problem by breaking it into smaller, more manageable sub-
problems
C) Optimizing the search algorithm to avoid redundant exploration
D) Using heuristics to guide the search towards the solution
4. Which of the following describes a production system in AI?
A) A system based on a decision tree that explores all possible solutions
B) A set of rules applied to a knowledge base to transform one state into another
C) A process that minimizes the search space by using heuristics
D) A system that dynamically adjusts its rules based on new information
5. What is a disadvantage of Depth-First Search (DFS)?
A) It consumes a large amount of memory
B) It does not guarantee finding the shortest path
C) It explores shallow solutions before deep ones
D) It requires the use of a priority queue

ANSWERS
1 2 3 4 5
B B B B B

B. Answer the following questions

1. What is state space search, and how is it used in problem-solving in artificial

intelligence?
2. What is problem reduction, and how does it help in solving complex AI problems?
3. What are production systems in AI, and how do they work?
4. What are the advantages and disadvantages of using Depth-First Search in solving
problems?
5. How can production systems be applied to expert systems in AI?

2.9: References and Suggested Readings

Suggested/Readings &Books

1. [Link]–A Modern Approach, Pearson

Education Press, 2001.
2. Kevin Knight, Elaine Rich, [Link], Artificial Intelligence, McGraw Hill,2008.

3. George F. Luger, Artificial Intelligence,PearsonEducation,2001.

4. Nils J. Nilsson, Artificial Intelligence: A New Synthesis, Morgan Kauffman, 2002.

5. Artificial Intelligence, Nils [Link], ELSEVIER.
6 [Link] and [Link], Artificial Intelligence, - TMH

BOOKS:
 [Link]
 [Link]
 html [Link]
 [Link]