VISION INSTITUTE OF TECHNOLOGY, Subject: Artificial intelligence

ALIGARH

Unit: 2

Problem solving Methods – Search Strategies- Uninformed – Informed – Heuristics – Local Search
Algorithms and Optimization Problems – Searching with Partial Observations – Constraint
Satisfaction Problems – Constraint Propagation – Backtracking Search – Game Playing – Optimal
Decisions in Games – Alpha – Beta Pruning – Stochastic Games

PROBLEM SOLVING METHODS:-

Problem-solving in Artificial Intelligence (AI) involves finding solutions to specific tasks by

modeling them in a structured and efficient way. AI uses various methods to achieve this,
often inspired by human reasoning and decision-making. Below are the primary problem-
solving methods in AI:

1. Search-based Methods

Search-based methods explore a problem's solution space to find the best or optimal solution.

Search-based methods are used to find the best possible subset of requirements that
match user requests. They are used in software engineering to select and optimize
requirements while considering constraints such as limited resources and
interdependencies.

Page1 Faculty: Kajal saxena

VISION INSTITUTE OF TECHNOLOGY, Subject: Artificial intelligence
ALIGARH

Unit: 2

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.

a. Uninformed Search (Blind Search):

These methods do not have prior knowledge about the solution's location. Examples:

• Breadth-First Search (BFS): Explores all nodes at the current depth before moving deeper.
• Depth-First Search (DFS): Explores as far as possible along one branch before backtracking.
• Uniform Cost Search: Explores nodes with the lowest cost first.

b. Informed Search (Heuristic Search):

These use domain-specific knowledge to guide the search. Examples:

• A* Algorithm: Combines the cost to reach a node (g) and heuristic estimate (h).
• Greedy Best-First Search: Selects nodes with the lowest heuristic cost.

2. Knowledge-based Systems

These rely on predefined knowledge to solve problems:

Page2 Faculty: Kajal saxena

VISION INSTITUTE OF TECHNOLOGY, Subject: Artificial intelligence
ALIGARH

Unit: 2
• Expert Systems: Use rule-based reasoning to mimic human expert decision-making.
• Inference Engines: Apply logical reasoning (deductive, inductive, or abductive) to derive
solutions.

3. Constraint Satisfaction Problems (CSPs)

Constraint Satisfaction Problems (CSPs) are a fundamental tool in artificial intelligence (AI)
that help solve complex problems. CSPs are a way to pose problems as a set of variables,
domains, and constraints, and then use general methods to find solutions.

These involve finding solutions that satisfy a set of constraints:

• Examples: Sudoku, scheduling, and map coloring.

• Techniques: Backtracking, constraint propagation, and local search.

4. Optimization Techniques

Used for problems that require the best solution among many:

• Linear Programming: Optimizes a linear objective function with constraints.

• Genetic Algorithms: Mimics natural evolution to find optimal solutions.
• Simulated Annealing: Uses probabilistic techniques to escape local optima.
• Gradient Descent: Optimizes problems in continuous spaces (e.g., neural networks).

5. Game Theory and Adversarial Search

Used for competitive environments where players act against each other:

• Minimax Algorithm: Finds optimal strategies for zero-sum games.

• Alpha-Beta Pruning: Optimizes Minimax by pruning suboptimal branches.
• Applications: Chess, Go, and other strategic games.

6. Logic and Theorem Proving

AI uses formal logic to prove mathematical theorems or solve logical problems:

• Propositional Logic: Deals with simple true/false statements.

• First-Order Logic: Extends propositional logic with quantifiers and predicates.
• Resolution: A rule-based inference mechanism for theorem proving.

Page3 Faculty: Kajal saxena

VISION INSTITUTE OF TECHNOLOGY, Subject: Artificial intelligence
ALIGARH

Unit: 2
7. Machine Learning Methods

Some problems are solved by learning patterns from data instead of explicit programming:

• Supervised Learning: Solves classification and regression problems.

• Reinforcement Learning: Solves sequential decision-making problems by learning through
rewards and penalties.

8. Divide and Conquer

Breaks a problem into smaller sub problems, solves them individually, and combines results.
Examples include algorithms like merge sort and quick sort.

9. Planning

Involves generating a sequence of actions to achieve a goal:

• State-Space Planning: Explores all possible actions and their outcomes.

• Hierarchical Task Network (HTN) Planning: Breaks tasks into smaller subtasks.

10. Case-Based Reasoning (CBR)

This method solves new problems by reusing solutions from similar past problems.

11. Stochastic and Probabilistic Methods

Handle uncertainty and randomness:

• Bayesian Networks: Represent probabilistic relationships among variables.

• Markov Decision Processes (MDPs): Model decision-making in probabilistic environments.

12. Swarm Intelligence

Inspired by collective behavior in nature, such as ants and birds:

• Examples: Ant Colony Optimization, Particle Swarm Optimization.

Page4 Faculty: Kajal saxena

VISION INSTITUTE OF TECHNOLOGY, Subject: Artificial intelligence
ALIGARH

Unit: 2
Local Search Algorithms and Optimization Problems

Local search algorithms are optimization techniques used for problems where the goal is to
find a solution that optimizes a given objective function. Unlike systematic search methods
(e.g., BFS or DFS), local search focuses on iteratively improving a single candidate solution
by exploring its "neighborhood" (small changes to the current solution).

Characteristics of Local Search Algorithms:

1. Single-State Search: Maintains only the current candidate solution rather than exploring a
full search tree.
2. Memory Efficiency: Requires minimal memory compared to exhaustive search methods.
3. Applicable to Large Spaces: Effective for problems with vast or infinite search spaces.
4. Optimization-Focused: Works well for finding solutions to optimization problems rather
than strict goal satisfaction.

Key Local Search Algorithms

1. Hill Climbing

• Description: Starts with an arbitrary solution and iteratively moves to a better neighbour
(based on objective value) until no improvement is possible.
• Variants:
o Simple Hill Climbing: Evaluates neighbors one at a time, moving to the first better
neighbor.
o Steepest-Ascent Hill Climbing: Evaluates all neighbors and chooses the best.
o Stochastic Hill Climbing: Chooses a neighbor randomly with some probability.
• Challenges:
o Local Maxima: Stops at a suboptimal peak.
o Plateaus: Flattens when neighboring states have equal values.
o Ridges: Narrow regions where improvement is difficult to navigate.

2. Simulated Annealing

• Description: Inspired by annealing in metallurgy, it occasionally accepts worse solutions to

escape local maxima. As time progresses, the probability of accepting worse solutions
decreases.
• Advantages:
o Escapes local maxima.
o Balances exploration and exploitation.
• Key Parameter: Cooling schedule (controls temperature decay).

Page5 Faculty: Kajal saxena

VISION INSTITUTE OF TECHNOLOGY, Subject: Artificial intelligence
ALIGARH

Unit: 2
3. Genetic Algorithms

• Description: Mimics natural evolution by maintaining a population of candidate solutions

that evolve over generations. Uses operations like:
o Selection: Picks better solutions for reproduction.
o Crossover: Combines solutions to create new ones.
o Mutation: Introduces random changes.
• Applications: Complex optimization problems, such as scheduling and network design.

4. Tabu Search

• Description: Extends hill climbing by keeping a "tabu list" of recently visited solutions to
avoid revisiting and cycling.
• Advantages: Overcomes local maxima and plateaus.

5. Beam Search

• Description: Maintains a limited number of candidate solutions and explores their neighbors
in parallel. Focuses on promising regions of the search space.

6. Iterative Improvement

• Description: Starts with an initial solution and iteratively makes local changes until a
termination condition is met.

7. Gradient Descent (for Continuous Spaces)

• Description: Iteratively adjusts a solution in the direction of the steepest descent of the
objective function. Commonly used in machine learning.

Optimization Problems and Applications

Optimization problems involve finding the "best" solution (maximum or minimum) under a
set of constraints. Local search is suitable for many such problems, including:

1. Traveling Salesperson Problem (TSP): Minimize the total distance of visiting a set of cities.
2. Job Scheduling: Assign tasks to resources to minimize total time or cost.
3. Knapsack Problem: Maximize value within weight constraints.
4. Graph Coloring: Minimize the number of colors needed for coloring a graph.
5. Pathfinding: Find the shortest or optimal path (e.g., robotics, logistics).

Page6 Faculty: Kajal saxena

VISION INSTITUTE OF TECHNOLOGY, Subject: Artificial intelligence
ALIGARH

Unit: 2
Searching with Partial Observations

In some cases, the full state of the problem is not observable (e.g., due to noise, hidden states,
or incomplete information). Local search with partial observations adapts by:

• Belief States: Representing uncertainty with a probability distribution over possible states.
• Heuristic Evaluation: Estimating the quality of a partial solution using domain knowledge.
• Exploration Strategies:
o Random restarts or simulated annealing to prevent getting stuck in poorly observed
areas.
o Probabilistic models, like Bayesian Networks or Markov Decision Processes, to
handle uncertainty.

Approaches for Partial Observations:

1. Sensor Models: Incorporate noisy or incomplete sensor data to estimate states.

2. Online Search: Make decisions based on current observations, revising as more information
becomes available.
3. Probabilistic Reasoning: Use techniques like particle filtering or Monte Carlo methods to
handle uncertainty.

Challenges of Local Search with Partial Observations

1. Local Optima: With incomplete information, finding the global optimum becomes more
challenging.
2. Dynamic Environments: The search space might change as new observations arrive.
3. Computational Cost: Managing probabilistic models or frequent re-evaluation can be
expensive.

Searching with Partial Observations

In many real-world scenarios, an agent does not have complete knowledge of the
environment or the current state of the system. Searching with partial observations refers to
problem-solving techniques where the agent must deal with uncertainty about the state of the
system, the effects of actions, or both.

Key Concepts in Searching with Partial Observations

1. Belief State:
o Represents the agent's knowledge or estimate of the possible states of the system.
o It is a probability distribution over all possible states (in probabilistic models) or a set
of possible states (in deterministic models).
o Example: If the agent knows it is in one of two rooms but is unsure which, the belief
state includes both room possibilities.
2. State Space under Uncertainty:

Page7 Faculty: Kajal saxena

VISION INSTITUTE OF TECHNOLOGY, Subject: Artificial intelligence
ALIGARH

Unit: 2
o The agent's search operates over belief states rather than concrete states.
o The belief state space can grow exponentially as the uncertainty increases.
3. Partial Observability:
o The agent may receive incomplete or noisy observations, making it difficult to
determine the exact state.
o Example: A robot navigating a maze may only know its immediate surroundings due
to limited sensors.
4. Observations and Actions:
o Actions: The agent interacts with the environment to change the state.
o Observations: Feedback received after performing an action, often noisy or
incomplete, used to update the belief state.

Approaches to Search with Partial Observations

1. Online Search

• The agent incrementally explores the environment, making decisions based on the current
observations and updating its belief state in real-time.
• Suitable for unknown or dynamic environments.

2. Heuristic Search with Belief States

• Use heuristics to evaluate the likelihood of achieving the goal from a belief state.
• Example: Planning under uncertainty using approximate methods like A* applied to belief
states.

3. Probabilistic Search

• Models the environment and uncertainty using probabilities.

• Techniques include:
o Bayesian Networks: Represent dependencies between variables and update belief
states.
o Particle Filtering: Uses a set of samples (particles) to approximate the belief state
and update it based on observations.

4. Markov Decision Processes (MDPs)

• Models decision-making under uncertainty where the agent knows the transition
probabilities between states.
• If observations are partial, Partially Observable Markov Decision Processes (POMDPs) are
used.
• POMDPs provide a framework for optimal decision-making by balancing exploration and
exploitation.

Page8 Faculty: Kajal saxena

VISION INSTITUTE OF TECHNOLOGY, Subject: Artificial intelligence
ALIGARH

Unit: 2
5. Deterministic Approximations

• Instead of modeling all uncertainties, approximate methods assume the most likely state or
reduce the complexity of the belief state space.
• Example: Greedy algorithms or reactive systems.

Challenges in Partial Observation Search

1. Belief State Explosion:

o Representing and managing belief states is computationally expensive as the state
space grows exponentially with uncertainty.
2. Noisy Observations:
o Observations may mislead the search process, requiring robust techniques for
filtering and error correction.
3. Real-Time Decision Making:
o In dynamic environments, the agent must update its belief state and make decisions
quickly.
4. Balancing Exploration and Exploitation:
o The agent must decide whether to gather more information (exploration) or act on
current beliefs to achieve its goal (exploitation).

Examples of Applications

1. Robot Navigation:
o Robots in unknown environments rely on sensor data to update their belief state
and plan a path.
o Example: SLAM (Simultaneous Localization and Mapping) combines mapping and
localization under uncertainty.
2. Game AI:
o Strategy games where the agent cannot see the entire game board but must infer
the opponent's moves.
3. Medical Diagnosis:
o Systems infer the most likely condition based on partial symptoms and test results.
4. Autonomous Vehicles:
o Self-driving cars operate in partially observable environments, relying on noisy
sensor data for decision-making.
5. Search and Rescue Operations:
o Agents must make decisions in environments with limited visibility or incomplete
maps.

Strategies for Effective Partial Observation Search

1. Use Filtering Techniques:

Page9 Faculty: Kajal saxena

VISION INSTITUTE OF TECHNOLOGY, Subject: Artificial intelligence
ALIGARH

Unit: 2
o Particle filters or Kalman filters to refine the belief state based on noisy data.
2. Exploit Domain Knowledge:
o Heuristics or pre-trained models can guide the search in uncertain environments.
3. Plan for Contingencies:
o Generate plans that account for different possible states (e.g., conditional planning).
4. Simplify the Problem:
o Use deterministic assumptions or reduce the dimensionality of the belief state for
faster computation.

Constraint Satisfaction Problems (CSPs)

Constraint Satisfaction Problems (CSPs) are a class of mathematical problems where the goal
is to find a solution that satisfies a set of constraints. CSPs are widely used in Artificial
Intelligence (AI) for solving problems in planning, scheduling, resource allocation, and many
other domains.

Definition of CSP

A CSP is defined by:

1. Variables (X1,X2,...,XnX_1, X_2, ..., X_nX1,X2,...,Xn):

o A finite set of variables, each representing a part of the solution.
o Example: In Sudoku, the variables represent cells in the grid.
2. Domains (D1,D2,...,DnD_1, D_2, ..., D_nD1,D2,...,Dn):
o A finite set of possible values for each variable.
o Example: In Sudoku, the domain is {1,2,...,9}\{1, 2, ..., 9\}{1,2,...,9}.
3. Constraints (C1,C2,...,CmC_1, C_2, ..., C_mC1,C2,...,Cm):
o Restrictions on the values that variables can take, often involving relationships
between variables.
o Example: In Sudoku, constraints ensure that no row, column, or sub grid has
repeated numbers.

Examples of CSPs

1. Sudoku: Fill a grid so each row, column, and subgrid contains unique numbers.
2. Graph Coloring: Assign colors to nodes such that no two adjacent nodes share the same
color.
3. N-Queens Problem: Place nnn queens on an n×nn \times nn×n chessboard such that no two
queens threaten each other.
4. Scheduling: Assign tasks to time slots without conflicts (e.g., exam scheduling).
5. Resource Allocation: Assign resources to tasks under constraints (e.g., bandwidth
allocation).

Page10 Faculty: Kajal saxena

VISION INSTITUTE OF TECHNOLOGY, Subject: Artificial intelligence
ALIGARH

Unit: 2

Solving CSPs

1. Backtracking Search

• A depth-first search algorithm that assigns values to variables incrementally.

• If a partial assignment violates a constraint, it backtracks to explore alternatives.
• Basic but can be inefficient for large CSPs.

2. Constraint Propagation

• Reduces the search space by enforcing constraints locally:

o Arc Consistency (AC): Ensures that for every value of one variable, there exists a
consistent value for another variable.
o Node Consistency: Ensures that each variable satisfies its unary constraints.
o Path Consistency: Considers pairs of variables and ensures consistency with a third
variable.

3. Heuristics for Variable and Value Selection

• Minimum Remaining Values (MRV): Choose the variable with the fewest legal values left.
• Degree Heuristic: Choose the variable involved in the largest number of constraints.
• Least Constraining Value (LCV): Choose the value that leaves the most options open for
others.

4. Local Search

• Starts with a complete assignment and iteratively modifies it to reduce constraint violations.
• Techniques include:
o Hill Climbing: Moves to a neighbor with fewer violations.
o Simulated Annealing: Accepts worse solutions with a probability to escape local
optima.

5. Constraint Optimization

• Extends CSPs to find the best solution according to an objective function.

• Example: Minimize cost or maximize utility while satisfying constraints.

Types of CSPs

1. Discrete CSPs:
o Variables take on discrete values.
o Example: Sudoku, N-Queens.
2. Continuous CSPs:
o Variables take on continuous values.
o Example: Motion planning for robots.

Page11 Faculty: Kajal saxena

VISION INSTITUTE OF TECHNOLOGY, Subject: Artificial intelligence
ALIGARH

Unit: 2
3. Over-Constrained CSPs:
o No complete solution exists, so the goal is to minimize constraint violations.
o Example: Real-world scheduling problems.
4. Dynamic CSPs:
o Constraints or variables can change over time.
o Example: Adaptive resource allocation in a network.
5. Stochastic CSPs:
o Some constraints are probabilistic, adding uncertainty.
o Example: Supply chain logistics.

Common Algorithms in CSP Solving

1. Backtracking with Forward Checking:

o After assigning a value, eliminates inconsistent values for neighboring variables.
2. Constraint Propagation with AC-3 Algorithm:
o Iteratively ensures arc consistency for all variable pairs.
3. Min-Conflict Heuristic:
o For local search, chooses the value that results in the fewest conflicts.
4. Branch and Bound:
o Used for optimization problems, explores branches of the search tree and prunes
suboptimal solutions.
5. Integer Programming:
o Converts CSPs into mathematical optimization problems solvable by linear
programming.

Applications of CSPs

1. Scheduling:
o Exam timetabling, workforce scheduling, and flight scheduling.
2. Planning:
o Logistics, robot path planning.
3. Configuration:
o Assembling systems with compatible components.
4. Vision:
o Image labelling and interpretation.
5. Natural Language Processing:
o Parsing and semantic interpretation.

Challenges in CSPs

1. Scalability: The number of variables and constraints can grow exponentially.

2. Dynamic Constraints: Adapting to changing constraints in real-time.
3. Over-Constrained Problems: Handling situations with no feasible solution.

Page12 Faculty: Kajal saxena

VISION INSTITUTE OF TECHNOLOGY, Subject: Artificial intelligence
ALIGARH

Unit: 2
4. Optimization Trade-offs: Balancing conflicting objectives.

Constraint Propagation

Constraint propagation is the process of systematically reducing the search space of a CSP by
enforcing constraints locally to simplify the problem before or during search.

Techniques for Constraint Propagation

1. Node Consistency:
o A variable is node-consistent if all its domain values satisfy unary constraints
(constraints involving only one variable).
2. Arc Consistency:
o A variable pair (X,Y)(X, Y)(X,Y) is arc-consistent if every value in XXX’s domain has a
corresponding value in YYY’s domain that satisfies the constraint.
o Algorithm: AC-3 (Arc Consistency Algorithm 3)
▪ Iteratively checks and enforces arc consistency for all variable pairs.
▪ Removes domain values that do not satisfy constraints.
3. Path Consistency:
o Extends arc consistency to triples of variables. Ensures that any consistent pair of
values can be extended to a third variable.
4. Constraint Propagation with Forward Checking:
o After assigning a value to a variable, eliminates inconsistent values from neighboring
variables' domains.
o Useful for reducing search space early.

Benefits of Constraint Propagation

• Reduces the search space by pre-emptively pruning inconsistent values.

• Improves the efficiency of backtracking search by avoiding unnecessary exploration of
invalid solutions.

Backtracking Search for CSPs

Backtracking Search is a systematic search technique for solving CSPs by incrementally

assigning values to variables and checking constraints.

Steps in Backtracking Search:

1. Select a Variable:
o Choose an unassigned variable.
o Use heuristics like Minimum Remaining Values (MRV) to prioritize variables with
fewer options.
2. Assign a Value:
o Select a value from the variable's domain.

Page13 Faculty: Kajal saxena

VISION INSTITUTE OF TECHNOLOGY, Subject: Artificial intelligence
ALIGARH

Unit: 2
o Use heuristics like Least Constraining Value (LCV) to minimize conflicts with other
variables.
3. Check Consistency:
o Ensure the assignment satisfies all constraints.
o If consistent, proceed to the next variable.
4. Backtrack if Necessary:
o If no valid assignments are possible, undo the last assignment and try a different
value.

Enhancements to Backtracking Search:

1. Forward Checking:
o After assigning a variable, propagate constraints to neighboring variables to prune
inconsistent values.
2. Constraint Propagation:
o Combine backtracking with arc or path consistency to dynamically enforce
constraints during search.
3. Iterative Improvement:
o For optimization problems, refine solutions iteratively instead of exploring all
possibilities.

Game Playing

Game playing is another AI domain that involves making decisions in an adversarial

environment, often modeled as a search problem.

Characteristics of Game Playing:

1. Adversarial Nature:
o Two or more players compete with opposing goals (e.g., chess, Go).
2. State Space:
o Represents the game's possible configurations.
3. Utility Function:
o Evaluates the desirability of a state (e.g., win, loss, or tie).

Search Techniques in Game Playing

1. Minimax Algorithm:
o A decision-making strategy for two-player zero-sum games.
o Assumes optimal play by both players:
▪ Maximizing Player: Tries to maximize the utility value.
▪ Minimizing Player: Tries to minimize the utility value.
2. Alpha-Beta Pruning:
o An optimization for the minimax algorithm that prunes branches that cannot
influence the final decision.
o Reduces computation time significantly, especially for large game trees.
3. Heuristic Evaluation:

Page14 Faculty: Kajal saxena

VISION INSTITUTE OF TECHNOLOGY, Subject: Artificial intelligence
ALIGARH

Unit: 2
o When the state space is too large, the algorithm evaluates non-terminal states using
heuristics to approximate utility values.
4. Monte Carlo Tree Search (MCTS):
o A probabilistic search technique that uses random simulations to estimate the utility
of moves.
o Widely used in games like Go and modern AI systems.

Relation between CSPs, Constraint Propagation, Backtracking, and Game Playing

• CSP Techniques in Games:

o CSP methods like backtracking and constraint propagation can model and solve
puzzles and combinatorial games (e.g., Sudoku, crossword puzzles).
o Game playing can also involve solving CSP-like subproblems, such as managing
resources or optimizing strategies within constraints.
• Optimization and Search:
o Both CSP solving and game playing require efficient search techniques, often
enhanced with heuristics and pruning.
o Games add the adversarial component, making the problem dynamic and requiring
strategies like minimax or MCTS.

Optimal Decisions in Games

In adversarial games, optimal decision-making involves choosing actions that maximize the
likelihood of achieving the best possible outcome while accounting for the opponent's
strategies. The process relies on search algorithms and evaluation functions that simulate
possible moves, predict opponents' responses, and evaluate game states.

Key Concepts in Optimal Decision Making

1. Game Representation:
o Games are modelled as game trees, where:
▪ Nodes represent states.
▪ Edges represent moves.
▪ Terminal nodes represent outcomes (win, loss, or draw).
2. Utility Function:
o Assigns a numerical value to terminal states:
▪ Positive values for favourable outcomes.
▪ Negative values for unfavourable outcomes.
▪ Example: In chess, utility might be

Page15 Faculty: Kajal saxena