Unit 3: Solving Problems by Searching & Uninformed Search Algorithm

 

Unit-3: Solving Problems by Searching & Uninformed Search Algorithms

Solving Problems by Searching: Problem Solving Agents: Well-Defined Problems and Solutions, Formulating problems, Example Problems: Toys Problems, Real-World Problems, Searching for Solutions, Uninformed Search Algorithms: BFS, Uniform-Cost Search, DFS, Depth Limited Search, Iterative Deepening, and Bidirectional Search.

Solving Problems by Searching:

In AI, Searching is the basic technique used for solving problems.
Whenever an agent (robot, software, etc.) doesn't know what to do immediately, it can search through possible actions and their outcomes to find a solution path.

Search = exploring possible actions until the goal is reached.       

Problem Solving Agents:

A Problem-Solving Agent is a type of intelligent agent designed to find sequences of actions that lead to desirable outcomes (i.e., solving a problem).

It operates by:

  1. Formulating the problem.
  2. Searching for a solution.
  3. Executing the solution.

Detailed Description about Problem-Solving Agents:

A problem-solving agent is a type of intelligent agent that is designed to find a sequence of actions that leads to a desired goal.
Instead of acting immediately, the agent thinks ahead, plans, and searches for the best course of action before making a move.

Problem-solving agents are used in environments where:

  • The environment is static (doesn't change while the agent is thinking),
  • Fully observable (the agent has complete information),
  • Deterministic (the outcome of actions is predictable),
  • And the goal is clearly defined.

Structure of a Problem-Solving Agent

The agent follows a simple cycle:

  1. Formulate a goal:
    Decide what to achieve.
  2. Formulate a problem:
    Define the starting point, actions, and the goal in a precise way.
  3. Search for a solution:
    Explore different sequences of actions using a search algorithm.
  4. Execute the solution:
    Carry out the planned sequence of actions.

Components of Problem Solving:

To solve a problem, an agent needs:

  • Initial State:
    Where the agent starts.
  • Action Set (Operators):
    All possible actions the agent can take.
  • Transition Model:
    Rules that describe what happens when an action is taken.
  • Goal Test:
    A way to check if the goal has been achieved.
  • Path Cost:
    A numerical cost assigned to each possible path (lower cost is usually better).

Example

Robot Delivery Agent:

  • Initial State: Robot is at warehouse.
  • Actions: Move to different locations, pick up packages, deliver packages.
  • Transition Model: If the robot moves north, it will reach the location to the north.
  • Goal Test: All packages have been delivered to the right places.
  • Path Cost: Total distance travelled or energy used.

Characteristics of Problem-Solving Agents:

  • Deliberative: Thinks before acting.
  • Flexible: Can change plans if new information is found.
  • Systematic: Searches through all possible actions carefully.
  • Goal-directed: Focuses on achieving a specific outcome.

Why is Problem-Solving Agents Important?

Problem-solving agents are important because they introduce intelligence into action.
Instead of reacting blindly, they think, plan, and choose the best actions to achieve their goals.

Here are the main reasons why they matter:

1. Planning Before Acting

  • They analyse possible actions before making a move.
  • This helps avoid mistakes and bad outcomes.
  • Example: A robot planning a safe path around obstacles.

2. Handling Complex Goals

  • They can deal with multi-step problems that need careful action sequences.
  • Example: A delivery drone planning multiple package drop-offs.

3. Flexibility

  • If the situation changes or if there are multiple ways to achieve a goal, a problem-solving agent can re-plan and adapt.

4. Efficiency

  • They can find the shortest, cheapest, or fastest solutions.
  • Saves time, energy, money, or resources.

 

 

5. Foundation for Advanced AI

  • They are the first step toward more advanced intelligent behaviour.
  • Learning agents, game-playing bots, robots, and autonomous systems are all built on the basic idea of problem-solving agents.

Example:

Imagine if Google Maps just showed you a map without giving you a calculated route. Thanks to problem-solving agents, it searches for the best path and suggests the most efficient way to reach your destination.

Short Definition:
Problem-solving agents = Thinking + Searching + Smart Action.
They are crucial for building any system that needs to make good decisions to reach goals.

Well-Defined Problems and Solutions:

A well-defined problem has:

  • Initial state: where you start.
  • Actions (operators): possible moves.
  • Transition model: what happens when an action is taken.
  • Goal test: how to know if the problem is solved.
  • Path cost: numerical cost of the solution path.

Example:
Maze-solving problem

  • Initial: At maze entrance
  • Actions: Move up/down/left/right
  • Goal test: Exit reached
  • Path cost: Steps taken (lower is better)

Detailed Description of Well-Defined Problems

A well-defined problem is a problem that is clearly specified and has all the information needed to find a solution.

A well-defined problem consists of

  • Initial state: Where you are starting from.
  • Possible actions: What moves you can make.
  • Transition model: What happens after each action?
  • Goal test: How to recognize if you have reached the goal.
  • Path cost: How much each path or solution will "cost" (time, distance, money, etc.).

Characteristics of a Well-Defined Problem:

  • Clear starting point
  • Clear rules and steps
  • Clear goal
  • Clear way to measure success

Example

Puzzle solving (like the 8-puzzle game):

  • Initial state: Random arrangement of tiles.
  • Actions: Slide tiles into an empty space.
  • Transition model: Each move results in a new tile arrangement.
  • Goal test: Tiles are in order.
  • Path cost: Number of moves made.

Everything is clearly defined, so the agent can find the best solution.

Why is it important?

  • It allows an agent (like a robot or a program) to search for a solution systematically.

·        Makes it easier to use algorithms like Breadth-First Search, Depth-First Search, A*, etc.

 

 

Formulating Problems:

Before solving, formulate the problem correctly by:

  • Understanding what the start is.
  • Understanding the possible actions.
  • Defining how actions change the world.
  • Setting clear goals.

Formulation is critical because wrong formulation = wrong solutions.

Detailed Description of Formulating Problems:

Formulating the problem means defining the problem clearly in a way that an agent can understand and solve it. It is the first and most important step before the agent can start searching for solutions.

Problem formulation answers questions like:

  • Where am I starting?
  • What actions can I take?
  • How do actions change my situation?
  • How do I know when I have succeeded?

Steps in Problem Formulation

A problem is formulated by specifying these five components:

  1. Initial State
    • The starting point of the agent.
    • Example: In a maze, the entrance.
  1. Actions (Operators)
    • All possible moves or actions the agent can perform.
    • Example: Move left, move right, move up, move down.

 

  1. Transition Model
    • Describes what happens when an action is performed.
    • Example: If you move right from position (2,3), you reach (3,3).
  1. Goal Test
    • A way to check if the current state is the goal state.
    • Example: In a maze, reaching the exit point.
  1. Path Cost
    • A number that measures how expensive a path is.
    • Example: Total number of moves or total distance travelled.

Example: Route Finding Problem

  • Initial State: Start at City A.
  • Actions: Drive to neighbouring cities.
  • Transition Model: Driving updates your location.
  • Goal Test: Have you reached City B?
  • Path Cost: Distance travelled or fuel used.

Importance of Problem Formulation

  • Correct formulation = Easier solution
  • Wrong formulation = Wasted time or no solution

Simple Definition:

Formulating the problem means creating a map of the situation so that the agent knows what to do, what options it has, and how to reach its goal.

Example Problems:

Toy Problems:

Detailed Description:

Toy problems are simple, abstract, and artificial problems used to study and understand problem-solving techniques. They are not meant to solve real-world issues directly, but to teach concepts, test algorithms, and develop intuition about how intelligent agents can work.

Characteristics of Toy Problems

  • Simplified environment: No unnecessary complications.
  • Fully observable: The agent can see everything it needs to know.
  • Deterministic: Actions always have predictable results.
  • Discrete: A limited number of actions and states.
  • Clear goal: It’s easy to check if the goal has been achieved.

Use of Toy Problems:
Because real-world problems are messy, and it’s easier to first learn problem-solving ideas on simple, clean examples.

Examples of Toy Problems:

1. 8-Puzzle Problem

  • Setup: A 3×3 grid with 8 numbered tiles and one empty space.
  • Goal: Arrange the tiles in a particular order (usually numerical order).
  • Actions: Slide a tile into the empty space.
  • Challenge: Find the minimum number of moves to reach the goal.

Teaches:  Search strategies, heuristics (like misplaced tile count).

2. Missionaries and Cannibals Problem

  • Setup:
    Three missionaries and three cannibals are on one side of a river.
    They must cross the river using a boat that can carry at most two people.
  • Constraints:

Cannibals can never outnumber missionaries on either side.

  • Goal: Get everyone safely across.
  • Actions: Move one or two people across the river.

Teaches:  State-space search, managing constraints.

3. Tower of Hanoi

  • Setup:
    Three pegs and a number of disks of different sizes stacked on one peg.
  • Goal:
    Move all disks to another peg, following rules:
    • Only one disk can be moved at a time.
    • No larger disk may be placed on top of a smaller disk.
  • Actions: Move the top disk from one peg to another.

Teaches:  Recursive problem-solving, planning multi-step actions.

5. Tic-Tac-Toe

  • Setup:
    Two players take turns marking spaces in a 3×3 grid.
  • Goal:
    Place three of their marks in a row (horizontally, vertically, or diagonally).
  • Actions: Place a mark on an empty space.

Teaches: Game trees, minimax algorithm, adversarial search.

Why Toy Problems are Important?

  • Easy to model: You can fully define initial states, actions, transitions, goals, and costs.
  • Focus on logic: You don’t get distracted by real-world messiness like uncertainty or partial observability.
  • Benchmarking: You can test and compare different algorithms easily.
  • Building intuition: Helps students and researchers understand how AI agents think.

Short Definition:

Toy Problems are "practice worlds" that teach agents (and students!) how to think, plan, and search before facing the real world.

Real-World Problems:

Real-World Problems are much messier and complex.

  • Route finding (like Google Maps).
  • Robotics navigation.
  • Scheduling tasks.
  • Medical diagnosis.

Here, actions might be uncertain, the world might be dynamic, and goals can change.

Searching for Solutions

Search Algorithm = method for exploring the possible actions to find a solution.

Common steps:

  1. Expand: Try all possible actions from a state.
  2. Search tree: Keep track of states reached.
  3. Choose next state: Based on some strategy (like lowest cost, or closest to goal).

Examples of Search Algorithms:

  • Breadth-First Search (BFS): Explore shallow states first.
  • Depth-First Search (DFS): Dive deep first.
  • A*: Smart search combining cost so far and estimate to goal.

Uninformed Search Algorithms:

Simple Description:

Uninformed Search (also called Blind Search) means the agent has no extra information about the goal location, except what is given in the problem definition.

It only knows:

  • What actions are available?
  • Whether it has reached the goal?

It does NOT know how far the goal is or which action is better?

 

 

Detailed Description of Uninformed Search Algorithms:

Uninformed Search Algorithms (also called Blind search algorithms) are search strategies that have no additional information about the location of the goal beyond the problem definition. They explore the search space without using heuristics or estimates about how close they are to the goal. In other words, they search blindly, only knowing what actions are available and whether a state is the goal.

Short Note on Uninformed Search Algorithms

Uninformed search algorithms are basic techniques used to find a solution when no extra knowledge about the goal's location is available. They systematically explore the state space until they find a solution.

Important Uninformed Search Algorithms:

  • Breadth-First Search (BFS): Explores all nodes at the current depth before going deeper.
  • Uniform-Cost Search (UCS): Expands the node with the lowest total cost so far.
  • Depth-First Search (DFS): Explores as far down a branch as possible before backtracking.
  • Depth-Limited Search (DLS): DFS with a limit on how deep it can go.
  • Iterative Deepening Search (IDS): Repeatedly applies DLS with increasing limits.
  • Bidirectional Search: Searches simultaneously from start and goal and meets in the middle.

Key features:

  • No use of heuristics.
  • Some are complete and optimal (like BFS and UCS).
  • Memory and time requirements vary depending on the strategy.

Uninformed search is important for understanding basic AI problem-solving before introducing more advanced methods like Heuristic (informed) Search.

 

 

1.     Breadth First Search:

What is Breadth First Search (BFS)?

Breadth-First Search (BFS) is a systematic graph traversal technique that explores all nodes at a given depth before moving on to nodes at the next depth level. Starting from a source node, BFS visits all its adjacent nodes first, proceeding to their neighbours in a level-by-level manner. This makes BFS an effective approach for finding the shortest path in un-weighted graphs or for performing an exhaustive search across graph structures.

BFS operates using a queue data structure, ensuring that nodes are processed in the order they are discovered. This traversal guarantees that the shortest path from the source to any other node is always found in un-weighted graphs. This systematic approach highlights BFS’s ability to explore all possibilities exhaustively, making it a cornerstone algorithm in AI and many other fields.

Key Characteristics of BFS

Breadth-First Search (BFS) has several defining characteristics that make it an essential algorithm for graph traversal and problem-solving:

  1. Completeness
    BFS guarantees to find a solution if one exists, provided the graph is finite. This property is particularly useful in AI applications like solving puzzles or navigating mazes.
  2. Optimality
    BFS is optimal for un-weighted graphs, ensuring that the shortest path from the source node to any other reachable node is always found.
  3. Time Complexity

The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This reflects the traversal of every node and edge once.

4.     Space Complexity

BFS requires O(V) space to store nodes in the queue during traversal. This can become a limitation for graphs with a large number of vertices.

 

Breadth First Search (BFS) Algorithms

BFS Pseudocode

1. Initialize an empty queue.
2. Enqueue the starting node and mark it as visited.
3. While the queue is not empty:
   a. Dequeue a node from the queue.
   b. Process the node (e.g., print or store it).
 c. Enqueue all unvisited adjacent nodes and mark them as visited.

Step-by-Step Explanation

Let’s break down the BFS algorithm with an example:

Consider the following graph:






Comments

Post a Comment

Popular posts from this blog

Intelligent Agents(Algorithms for Intelligent Systems)

    Unit II: Intelligent Agents   Intelligent Agents: Agents and Environments, The Concept of Rationality, The Nature of Environments (PEAS), The Structure of Agents: Simple Reflex Agents, Model-Based Reflex Agents, Goal-Based Agents, Utility-Based agents, Learning Agents. Agents and Environments: Agent An  agent  is an entity that perceives its environment through sensors and acts upon that environment through actuators. Agents can be anything from simple programs to complex systems like robots or humans. The key characteristic of an agent is its ability to take actions based on its perceptions to achieve specific goals. Environment The  environment  is the external context or world in which the agent operates. It includes everything the agent can perceive and interact with. The environment provides the agent with inputs (percepts) and receives outputs (actions) from the agent. Example Consider a  self-driving car : ...
Read more

2D-Transformations

Image
Transformation means changing some graphics into something else by applying rules. We can have various types of transformations such as translation, scaling up or down, rotation, shearing, etc. When a transformation takes place on a 2D plane, it is called 2D transformation. Transformations play an important role in computer graphics to reposition the graphics on the screen and change their size or orientation. Homogenous Coordinates To perform a sequence of transformation such as translation followed by rotation and scaling, we need to follow a sequential process − Translate the coordinates, Rotate the translated coordinates, and then Scale the rotated coordinates to complete the composite transformation. To shorten this process, we have to use 3×3 transformation matrix instead of 2×2 transformation matrix. To convert a 2×2 matrix to 3×3 matrix, we have to add an extra dummy coordinate W. In this way, we can represent the point by 3 numbers instead of 2 numbers, wh...
Read more

3D-Transformations(Including projections)

Image
In the 2D system, we use only two coordinates X and Y but in 3D, an extra coordinate Z is added. 3D graphics techniques and their application are fundamental to the entertainment, games, and computer-aided design industries. It is a continuing area of research in scientific visualization. Furthermore, 3D graphics components are now a part of almost every personal computer and, although traditionally intended for graphics-intensive software such as games, they are increasingly being used by other applications. Parallel Projection Parallel projection discards z-coordinate and parallel lines from each vertex on the object are extended until they intersect the view plane. In parallel projection, we specify a direction of projection instead of center of projection. In parallel projection, the distance from the center of projection to project plane is infinite. In this type of projection, we connect the projected vertices by line segments which correspond to connections o...
Read more