Unit 2 - Search Techniques Notes

Problem Solving Agents

• Definition: Agents that formulate problems and use search to reach their goals.
• Characteristics:
  • Perceive environment.
  • Formulate goals and problems.
  • Search for solutions.
  • Execute plans to achieve goals.

Example: Route-finding agent for a delivery vehicle

• Scenario: Route planning in an office environment (illustrative diagram referenced as Office).

Problem Formulation

• Elements of a well-defined problem:
  • Initial State: Starting state of the agent.
  • Actions: Possible actions from each state.
  • Transition Model: Results of actions.
  • Goal Test: Determines if the current state is a goal state.
  • Path Cost: Numeric cost associated with a path solution.

Searching for Solutions

• Searching: The process of finding a sequence of actions that achieves the goal.
• Solution: Sequence of actions from initial state to goal state.

Example: Traveling Salesman Problem

• Used as an example to illustrate search problems (illustration: FROM THIS to THIS).

Search Types

• Uninformed Search (Uniformed Search): No domain-specific knowledge.
• Informed Search (Heuristic Search): Uses heuristic function to guide search.

Search Techniques

• Uninformed Search Techniques: BFS, DFS, Depth-limited Search, Bidirectional Search, Iterative Deepening DFS, Uniform Cost Search, A* Search, AO* Search.
• Informed/Search with heuristics: Best First Search (Greedy), A* Search, AO* Search.

Uninformed Search Strategies

• Definition: Search strategies with no additional information about states other than the problem definition.
• Algorithms include: Breadth-First Search (BFS), Depth-First Search (DFS), Depth-Limited Search (DLS), Bidirectional Search, Iterative Deepening DFS (ID-DFS), Uniform Cost Search (UCS).

Breadth-First Search (BFS)

• How it works: Expands shallowest unexpanded node first.
• Data Structure: FIFO Queue.
• Properties:
  • Complete: Yes.
  • Optimal: Yes (if step cost = 1).
• Time Complexity: $O(b^d)$
• Space Complexity: $O(b^d)$
• Example: Finding the shortest path in an unweighted graph.

BFS Diagram (illustrative levels)

• Level 0: A
• Level 1: B, C, …
• Level 2: D, E, …

Depth-First Search (DFS)

• How it works: Expands deepest unexpanded node first.
• Data Structure: LIFO Stack or recursion.
• Properties:
  • Complete: No (fails in infinite depth spaces).
  • Optimal: No.
• Time Complexity: $O(b^m)$
• Space Complexity: $O(bm)$
• Example: Puzzle solving using backtracking.

Depth-Limited Search (DLS)

• DFS with a predetermined depth limit.
• Properties:
  • Complete: No (if cutoff < solution depth).
  • Optimal: No.
• Time Complexity: $O(b^l)$
• Space Complexity: $O(bl)$
• Use case: Avoids infinite exploration in infinite state spaces.

Bidirectional Search

• How it works: Simultaneously searches forward from the initial state and backward from the goal state until both meet.
• Properties:
  • Complete: Yes.
  • Optimal: Yes.
• Time Complexity: $O(b^{d/2})$
• Space Complexity: $O(b^{d/2})$
• Limitation: Requires the ability to generate predecessor states.

Comparison of Uninformed Search Strategies

• BFS: Complete = Yes; Optimal = Yes (if step cost = 1); Time $O(b^d)$; Space $O(b^d)$
• DFS: Complete = No; Optimal = No; Time $O(b^m)$; Space $O(bm)$
• DLS (Depth-Limited Search): Complete = No; Optimal = No; Time $O(b^l)$; Space $O(bl)$
• Bidirectional: Complete = Yes; Optimal = Yes; Time $O(b^{d/2})$; Space $O(b^{d/2})$
• Note: An algorithm is optimal if it finds the best solution (lowest-cost). A complete algorithm is guaranteed to find a solution if one exists.

Informed Search

• Also called Heuristic Search.
• Uses problem-specific knowledge to guide the search.
• More efficient than uninformed search (e.g., BFS, DFS) by exploring better paths first.

Heuristic? (Definition)

• A heuristic is an estimate of the cost to reach the goal from a node.
• Purpose: Helps prioritize which paths to explore first.
• Notation: $h(n)$ = estimated cost from node $n$ to the goal.

Heuristic Search Strategies

• Definition: Uses heuristic to estimate cost to goal and guide search.
• Includes: Greedy Best-First Search, A* Search, AO* Search.

Greedy Best-First Search

• How it works: Expands the node with the lowest heuristic value $h(n)$.
• Properties:
  • Complete: No.
  • Optimal: No.
• Time & Space Complexity: $O(b^m)$
• Example: Nearest neighbor approach in route finding.

A* Search

• How it works: Uses evaluation function $f(n) = g(n) + h(n)$.
  • $g(n)$: Cost to reach node $n$ from the start.
  • $h(n)$: Estimated cost from $n$ to the goal.
• Properties:
  • Complete: Yes.
  • Optimal: Yes, if $h(n)$ is admissible and consistent.
• Time & Space Complexity: Exponential (in the worst case).
• Example: Google Maps route optimization.

AO* Search

• How it works: Used in AND-OR graphs where problems involve sub-goals.
• Application: Problem decomposition, planning, theorem proving.
• Properties: Finds minimal-cost solution graph.
• Example: Task planning with dependent sub-tasks.

Memory Bounded Heuristic Search

• Purpose: To overcome high memory requirements of A*.
• Examples:
  • Recursive Best-First Search (RBFS)
  • Simplified Memory Bounded A* (SMA*)
• Properties: Uses linear memory with near-optimal performance.

Local Search Algorithms & Optimization Problems

• Definition: Uses a single current state and moves to improve it; does not maintain a path.
• Applications: Optimization problems, Constraint Satisfaction Problems (CSPs), large state spaces.

Hill Climbing Search

• How it works: Moves to the neighbour with the highest value (greedy improvement).
• Limitations: Can get stuck in local maxima, ridges, plateaus.
• Variants: Stochastic hill climbing, first-choice hill climbing.

Simulated Annealing Search

• How it works: Allows bad moves probabilistically to escape local optima; probability decreases over time (temperature).
• Analogy: Annealing in metallurgy to reach a minimum energy state.
• Property: Converges to the global optimum with a suitable cooling schedule.

Local Beam Search

• How it works: Keeps track of k states; generates all successors and selects the k best for the next iteration.
• Advantage: Explores multiple paths simultaneously; less likely to get stuck in local optima.

Slide 21: Summary

• Problem Solving Agents formulate and solve problems using search.
• Uniform search does not use domain knowledge (BFS, DFS, Depth-Limited Search, Bidirectional Search).
• Heuristic search uses $h(n)$ for efficiency (Greedy Best-First Search, A, AO).
• Memory bounded and local search optimize performance and resource usage.

References

• Text Book: S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, 3rd Edition, 2015.
• Reference Book: Nils J. Nilsson, Artificial Intelligence: A New Synthesis, Morgan Kaufmann, 1998.

Question Bank

2-Mark Questions

• Define problem solving agent.
• What is the difference between search tree and search graph?
• Define heuristic function.
• What is the evaluation function used in A* search?
• Mention any two differences between BFS and DFS.
• What is depth limited search?
• Define admissible heuristic.
• What is hill climbing search?
• Write the formula for $f(n)$ in A* search.
• What is the purpose of simulated annealing in search?

7-Mark Questions

• Write short notes on problem formulation in AI.
• Explain Breadth First Search with an example.
• Explain Depth First Search with its properties.
• Differentiate between BFS and DFS.
• Write a short note on Greedy Best-First Search.
• Explain Hill Climbing algorithm and its limitations.
• What is simulated annealing? Explain its working principle briefly.
• Write a note on bidirectional search and its advantages.
• Explain Depth Limited Search with example.
• Write short notes on Local Beam Search.

13-Mark Questions

• Explain problem solving agents in detail with neat diagram.
• Discuss uniform search strategies in detail: BFS, DFS, Depth Limited Search, and Bidirectional Search.
• Explain A* search algorithm with example. What are its properties?
• Explain heuristic search strategies in detail: Greedy Best-First Search, A* Search, AO* Search.
• Describe local search algorithms and optimization problems with examples (Hill Climbing, Simulated Annealing, Local Beam Search).
• Discuss memory bounded heuristic search strategies and their significance.
• Compare various uniform search strategies with respect to completeness, optimality, time, and space complexity.
• With suitable example, explain AO* search and its application in problem solving.
• Explain in detail simulated annealing search with analogy.
• Discuss in detail the differences between heuristic search and uniform search strategies.