AI-02 Problem Solving in AI

AI Problem

• A problem in AI is a task or situation where a computer or machine needs to think, decide, or learn in order to solve something intelligently

• A problem in AI is defined by: Inputs, a goal, and a way to reach that goal using logic, rules, or learning.

• Example:

  • Problem: A self-driving car reaching a destination safely.
  • Inputs: Current location, Map data, Traffic signals, Nearby vehicles, Weather conditions
  • Goal: Reach the destination safely, quickly, and without breaking any traffic rules.
  • Way to reach the goal: Use AI to analyze surroundings, make decisions (like when to stop or turn), and learn from past drives to improve navigation.

• AI problem components:

  • Initial State – Starting point
  • Goal State – What we want to achieve
  • Actions – What can be done
  • Transition Model – What happens when actions are taken
  • Path Cost (optional) – How much each step costs (used in optimization)

• Real-life examples:

  • Diagnosing diseases from symptoms
  • Translating languages (e.g., Google Translate)
  • Recommending movies (e.g., Netflix)
  • Detecting banking fraud

Problem Type	Description	Example
Search problem	Find the best solution from many options .	GPS finding the shortest route
Planning problems	Decide steps to reach a goal.	Robot making tea
Classification	Group data into categories.	Spam or Not Spam emails
Prediction	Guess future results from past data.	Weather forecasting
Decision making	Pick the best option from choices.	Chess AI choosing next move
Perception	Understand inputs like images, sounds.	Face recognition, self-driving
Learning problems	Learn from past experience to improve.	Machine learning model training

What does it mean to define AI Problem

• In Artificial Intelligence, before solving a problem, we need to clearly define it — just like we need to understand the rules before playing a game

• We define:

  • Where we are (Initial State)
  • Where we want to go (Goal State)
  • What we can do (Possible Actions / Rules)

• Example-1: Taxi Booking App (AI finding the best route)

  • Initial State: Your current location
  • Goal State: Your destination
  • Actions: Choose among different routes, avoid traffic, follow navigation rules

• Example-2: Cooking Assistant AI

  • Initial State: Ingredients you have
  • Goal State: Desired dish (e.g., pasta)
  • Actions: Mix, boil, chop – in correct sequence

• Example-3: Washing Clothes with AI Washing Machine

  • Initial State: Dirty clothes in the basket
  • Goal State: Clean, dry clothes
  • Actions: Fill water, add detergent, wash, rinse, dry

Problem Space & State Space

• In AI, before solving any problem, we must clearly define what the problem is and how to approach it — that’s where problem space and state space come in.
• Problem space and state space help AI understand: "Where can I go, what can I do, and how do I get to my goal efficiently?"

State Space

• All possible situations (states) the system can be in while solving the problem
• It includes:
  • The initial state
  • The goal state
  • All intermediate states you can reach by applying different actions

Problem Space

• Problem Space = The combination of: State Space + All possible actions (rules or moves that change one state to another)
• Problem Space = State Space + Actions
• It defines the entire environment in which the AI must operate to reach a goal.
• It defines all possible steps AI can use to reach the goal

Example

• Making a burger: AI as a cooking assistant
  • Imagine you're teaching a robot (AI) how to make a burger.
  • Problem space = Every action AI can take (adding patty, adding cheese etc)
  • State space = Every stage in burger-making
  • Goal = Perfect burger

Search Strategies

• Search strategies help an AI find the path from the starting point to the goal, especially when the AI has many choices to make.
• Imagine AI is playing a maze game, and it needs to find the quickest way out.
• Search strategies guide how it explores the maze.
• Two main types:
  • Informed Search
  • Uninformed Search

Informed	Uninformed
Search with extra information	Search without an information
Uses knowledge to guide steps	No prior knowledge
Finds solution quickly	Slower & time-consuming
Less complex (Time + Space)	More complex (Time + Space)
Uses: DFS and BFS	Uses A*, Heuristic DFS,

Travelling Salesman Problem

• Given a list of cities and the distances between each pair, what is the shortest possible route that:

  • Visits each city exactly once, and
  • Returns to the starting city

• Example: A salesman needs to visit 5 cities: Surat → Mumbai → Pune → Nashik → Ahmedabad

• Goal:

  • Visit each city once
  • Travel the least distance (or time/cost)
  • Return to the starting city

• Uninformed Search (Brute Force):

  • Tries every possible route
  • For n cities, number of possible paths = (n − 1)!
  • For 5 cities: (5 − 1)! = 24 possible paths
  • Guaranteed to find optimal solution
  • But not scalable — what if 99 cities?

• Informed Search (Heuristics):

  • Uses smart logic or heuristics
  • Doesn’t check every path
  • Much faster and more efficient

Breadth First Search (BFS)

• BFS is a traversal approach in which we first walk through all nodes on the same level (horizontal movement) before moving on to the next level.
• BFS visits siblings before children
• BFS uses Queue data structure for finding the shortest path.
• It works on the concept of FIFO (First In First Out).
• BFS is more suitable for searching vertices closer to the given source.
• In BFS, each node is traversed only once.
• BFS will definitely find a solution if it exists
• BFS uses more memory than DFS
• How it works:
  • Start from the root/start node
  • Visit all its immediate neighbours
  • Then go to next level of their neighbours
  • Keep repeating until goal is found or all nodes are visited
• Real-life example:
  • Social Media Friend Suggestions: Starting from you, BFS checks all your direct friends (level 1). Then their friends (level 2), and so on.
  • Web Crawlers: Search engines like Google crawl the web page level by level. First links on page → then links inside those links
• Use cases:
  • Shortest path in maps (like Google Maps)
  • Puzzle solvers (like 8-puzzle, word ladder)
  • Web Crawling
  • Social networks – friend suggestion

Depth First Search (DFS)

• DFS is a traversal approach in which the traverse begins at the root node and proceeds through the nodes as far as possible until we reach the node with no unvisited nearby nodes
• DFS visits children before siblings
• DFS uses Stack data structure.
• It works on the concept of LIFO (Last In First Out).
• DFS is more suitable when there are solutions away from source.
• In DFS each node is traversed twice due to backtracking.
• DFS may lead to situations where the algorithm gets stuck in an infinite loop.
• DSF may not give shortest path
• The amount of memory required for DFS is less than that of BFS.
• How it works:
  • Start from the root/start node
  • Visit one child node deeply until no further move
  • Then backtrack and explore other branches
  • Continue until goal is found or all paths are explored
• Real-life examples:
  • File System Traversal: Opening folders inside folders (deep nesting). DFS goes till the last subfolder, then comes back. Used in file explorers (Windows, Mac, Linux)
  • Puzzle Solving (Sudoku, 8-Puzzle, etc.): DFS explores one possible solution path fully. If it doesn’t work, it backtracks. Useful in game trees or AI bots solving puzzles.
• Use Cases:
  • Topological Sorting
  • Cycle detection in graphs
  • Solving puzzles and mazes
  • Searching deep decision trees

---