Problem-solving agents:

  • In Artificial Intelligence, Search techniques are universal problem-solving methods.
  • Rational agents or Problem-solving agents in AI mostly used these search strategies or algorithms to solve a specific problem and provide the best result.
  • Problem-solving agents are the goal-based agents and use atomic representation.
  • In this topic, we will learn various problem-solving search algorithms.

Some of the most popularly used problem solving with the help of artificial intelligence are:
  1. Chess.
  2. Travelling Salesman Problem.
  3. Tower of Hanoi Problem.
  4. Water-Jug Problem.
  5. N-Queen Problem.

Problem Searching

  • In general, searching refers to as finding information one needs.
  • Searching is the most commonly used technique of problem solving in artificial intelligence.
  • The searching algorithm helps us to search for solution of particular problem.
  • Problem: Problems are the issues which comes across any system. A solution is needed to solve that particular problem.

The three classes of problem:

  • Ignorable, in which solution steps can be ignored.
  • Recoverable, in which solution steps can be undone.
  • Irrecoverable, in which solution steps cannot be undone.

Steps : Solve Problem Using Artificial Intelligence

The process of solving a problem consists of five steps. These are:
  1. Defining The Problem: The definition of the problem must be included precisely. It should contain the possible initial as well as final situations which should result in acceptable solution.
  2. Analysing The Problem: Analysing the problem and its requirement must be done as few features can have immense impact on the resulting solution.
  3. Identification of Solutions: This phase generates reasonable amount of solutions to the given problem in a particular range.
  4. Choosing a Solution: From all the identified solutions, the best solution is chosen basis on the results produced by respective solutions.
  5. Implementation: After choosing the best solution, its implementation is done.

Search Algorithm Terminologies:

  • Search: Searching is a step by step procedure to solve a search-problem in a given search space. A search problem can have three main factors:
  • Search Space: Search space represents a set of possible solutions, which a system may have.
  • Start State: It is a state from where agent begins the search.
  • Goal test: It is a function which observe the current state and returns whether the goal state is achieved or not.
  • Search tree: A tree representation of search problem is called Search tree. The root of the search tree is the root node which is corresponding to the initial state.
  • Actions: It gives the description of all the available actions to the agent.
  • Transition model: A description of what each action do, can be represented as a transition model.
  • Path Cost: It is a function which assigns a numeric cost to each path.
  • Solution: It is an action sequence which leads from the start node to the goal node.
  • Optimal Solution: If a solution has the lowest cost among all solutions.

Example Problems

A Toy Problem is intended to illustrate or exercise various problem-solving methods. A real- world problem is one whose solutions people actually care about.

Toy Problems:


Vaccum World

States : The state is determined by both the agent location and the dirt locations. The agent is in one of the 2 locations, each of which might or might not contain dirt. Thus there are 2*2^2=8 possible world states.

Initial state: Any state can be designated as the initial state.

Actions: In this simple environment, each state has just three actions: Left, Right, and Suck. Larger environments might also include Up and Down.

Transition model: The actions have their expected effects, except that moving Left in the leftmost

square, moving Right in the rightmost square, and Sucking in a clean square have no effect. The complete state space is shown in Figure.

Goal test: This checks whether all the squares are clean.

Path cost: Each step costs 1, so the path cost is the number of steps in the path.


8- Puzzle Problem

States: A state description specifies the location of each of the eight tiles and the blank in one of the nine squares.

Initial state: Any state can be designated as the initial state. Note that any given goal can be reached

from exactly half of the possible initial states.

Actions: The simplest formulation defines the actions as movements of the blank space Left, Right, Up, or Down. Different subsets of these are possible depending on where the blank is.

Transition model: Given a state and action, this returns the resulting state; for example, if we apply

Left to the start state in Figure 3.4, the resulting state has the 5 and the blank switched. Goal test: This checks whether the state matches the goal configuration shown in Figure. Path cost: Each step costs 1, so the path cost is the number of steps in the path.


8 – Queens Problem:


States: Any arrangement of 0 to 8 queens on the board is a state.


Initial state: No queens on the board.


Actions: Add a queen to any empty square.


Transition model: Returns the board with a queen added to the specified square.


Goal test: 8 queens are on the board, none attacked.