Artificial Intelligence - Unit - 2: Topic - 1 : Searching - Searching for Solutions

UNIT - II

1. SEARCHING – SEARCHING FOR SOLUTIONS

---

Part A: Introduction to Searching in AI

---

1. What is Searching in Artificial Intelligence?

In AI, searching is the process of exploring a problem space to find a sequence of steps (a solution) that leads from the start state to the goal state.

It’s like a path-finding process — the agent tries different actions to move closer to the goal.

Imagine a robot trying to get out of a maze. It has no map, so it explores one path, hits a wall, tries another, and keeps going until it finds the exit. This trial-and-error is a form of search.
In more advanced AI systems, this search is guided intelligently using algorithms.

---

2. Why Searching is Important?

• Most AI problems do not have direct answers.
• Searching helps the agent plan, navigate, and solve problems in unknown environments.
• Searching is used in:
• Pathfinding (like GPS)
• Solving puzzles (like Rubik's Cube)
• Game playing (like Chess)
• Decision making

Even everyday AI tasks like recommending a product or translating a sentence involve searching through possibilities.
Search helps AI handle uncertainty, find optimal solutions, and adapt to dynamic environments.

---

Part B: Key Terms in AI Searching

---

Term	Description
State	A condition or situation in which the agent can be (e.g., robot at A1)
Initial State	The starting point of the problem
Goal State	The desired end condition
Action	Possible move or step from one state to another
Path	Sequence of actions that leads from start to goal
Path Cost	Numeric value representing the cost of the path (e.g., distance, time)
Search Space	All possible states that can be explored
Search Tree	Tree structure where nodes = states and branches = actions

Think of a search tree as a decision tree. Each node is a possible world (or situation), and each branch is an action.
For example, in a chess game:

• A node represents the current arrangement of pieces.
• A branch is a move you can make.
• The goal node is a checkmate.

 

✅ Example: Maze Solver

• Initial State: Agent starts at entrance of maze
• Goal State: Agent reaches the exit
• Actions: Move up, down, left, right
• Search: Explore paths to find the shortest one to the goal

This concept is also used in robotics, where a robot vacuum finds the most efficient way to clean a room, avoiding obstacles and minimizing time.

---

Part C: Types of Search Techniques

---

There are two main types of search strategies in AI:

Search Type	Description
Uninformed Search	No additional information is used. The agent searches blindly (e.g., BFS, DFS)
Informed Search	Uses heuristics (extra knowledge) to guide the search (e.g., A*, Hill Climbing)

·  Uninformed Search (Blind Search):

·        No idea about where the goal lies.

·        Searches the entire space.

·        Examples:

o   BFS (Breadth-First Search) – Explores all nodes at one level before moving to the next.

o   DFS (Depth-First Search) – Explores as deep as possible along each branch before backtracking.

·  Informed Search (Heuristic Search):

·        Uses additional information (heuristics) to estimate the best direction.

·        Examples:

o   A* – Finds the shortest path efficiently using actual + estimated cost.

o   Hill Climbing – Always moves in the direction of increasing value (like climbing a hill toward the peak).

---

Part D: Problem Solving as Search

---

A problem can be solved by searching through a state space using the following process:

1. Formulate the Problem
   Define the initial state, actions, goal state, and cost function.
2. Search for Solution
   Use a suitable algorithm to explore paths.
3. Choose the Best Path
   Select the path with minimum cost or highest success.

---

✅ Example: Route Planning (Google Maps)

• Initial State: Current location
• Goal State: Destination
• Search: Tries all possible routes
• Solution: Chooses shortest or fastest path

🔍 Further Insight:
In Google Maps, if you search for a route:

·        It uses A search* to find the optimal path.

·        The heuristic is based on real-time traffic, road distance, and estimated travel time.

---

📝 Summary

• Searching is the core technique used by AI agents to solve problems by exploring possible solutions.
• The search process involves moving from the initial state to the goal state through a set of actions.
• Two main types of search strategies are:
• Uninformed (blind): No guidance
• Informed (heuristic): Uses knowledge to improve search
• Understanding search is essential for solving navigation, planning, game playing, and other AI problems.

Think of searching like “trying all doors to find the one that opens your goal room!”

In real AI systems, the smart agent learns to try the most promising doors first, saving time and effort.