Chapter 3

Solving Problems by Searching

• Reflex agent is simple
• base their actions on
• a direct mapping from states to actions
• but cannot work well in environments
• which this mapping would be too large to store
• and would take too long to learn
• Hence, goal-based agent is used
 Problem-solving agent
• Problem-solving agent
• A kind of goal-based agent
• It solves problem by
• finding sequences of actions that lead to
desirable states (goals)
• To solve a problem,
• the first step is the goal formulation, based on
the current situation
 Goal formulation
• The goal is formulated
• as a set of world states, in which the goal is
satisfied
• Reaching from initial state 🡪 goal state
• Actions are required
• Actions are the operators
• causing transitions between world states
• Actions should be abstract enough at a
certain degree, instead of very detailed
• E.g., turn left VS turn left 30 degree, etc.
 Problem formulation
• The process of deciding
• what actions and states to consider
• E.g., driving Amman 🡪 Zarqa
• in-between states and actions defined
• States: Some places in Amman & Zarqa
• Actions: Turn left, Turn right, go straight,
accelerate & brake, etc.
 Search
• Because there are many ways to achieve
the same goal
• Those ways are together expressed as a tree
• Multiple options of unknown value at a point,
• the agent can examine different possible
sequences of actions, and choose the best
• This process of looking for the best sequence
is called search
• The best sequence is then a list of actions,
called solution
 Search algorithm
• Defined as
• taking a problem
• and returns a solution
• Once a solution is found
• the agent follows the solution
• and carries out the list of actions –
execution phase
• Design of an agent
• “Formulate, search, execute”
Well-defined problems and solutions
A problem is defined by 5
components:
• Initial state
• Actions
• Transition model or
(Successor functions)
• Goal Test.
• Path Cost.
Well-defined problems and solutions
• A problem is defined by 4 components:
• The initial state
• that the agent starts in
• The set of possible actions
• Transition model: description of what each action
does.
(successor functions): refer to any state reachable from
given state by a single action
• Initial state, actions and Transition model define the
state space
• the set of all states reachable from the initial state by any
sequence of actions.
• A path in the state space:
• any sequence of states connected by a sequence of actions.
Well-defined problems and solutions
• The goal test
• Applied to the current state to test
• if the agent is in its goal
-Sometimes there is an explicit set of possible goal states.
(example: in Amman).
-Sometimes the goal is described by the properties
• instead of stating explicitly the set of states
• Example: Chess
• the agent wins if it can capture the KING of the opponent on
next move ( checkmate).
• no matter what the opponent does
Well-defined problems and solutions
• A path cost function,
• assigns a numeric cost to each path
• = performance measure
• denoted by g
• to distinguish the best path from others
• Usually the path cost is
• the sum of the step costs of the individual
actions (in the action list)
Well-defined problems and solutions
• Together a problem is defined by
• Initial state
• Actions
• Successor function
• Goal test
• Path cost function
• The solution of a problem is then
• a path from the initial state to a state satisfying the goal
test
• Optimal solution
• the solution with lowest path cost among all solutions
 Formulating problems
• Besides the four components for problem
formulation
• anything else?
• Abstraction
• the process to take out the irrelevant information
• leave the most essential parts to the description of the
states
( Remove detail from representation)
• Conclusion: Only the most important parts that are
contributing to searching are used
 Evaluation Criteria
• formulation of a problem as search task
• basic search strategies
• important properties of search
strategies
• selection of search strategies for
specific tasks
(The ordering of the nodes in FRINGE
defines the search strategy)
 Problem-Solving Agents
• agents whose task is to solve a particular
problem (steps)
• goal formulation
• what is the goal state
• what are important characteristics of the goal state
• how does the agent know that it has reached the goal
• are there several possible goal states
• are they equal or are some more preferable
• problem formulation
• what are the possible states of the world relevant for solving
the problem
• what information is accessible to the agent
• how can the agent progress from state to state
Example
From our Example
1. Formulate Goal

- Be In Amman

2. Formulate Problem

- States : Cities
- actions : Drive Between Cities

3. Find Solution

- Sequence of Cities : ajlun – Jarash - Amman

Our Example

1. Problem : To Go from Ajlun to Amman

2. Initial State : Ajlween

3. Operator : Go from One City To another .

4. State Space : {Jarash , Salat , irbed,……..}

5. Goal Test : are the agent in Amman.

6. Path Cost Function : Get The Cost From The Map.

7. Solution : { {Aj 🡪 Ja 🡪 Ir 🡪 Ma 🡪 Za 🡪 Am} , {Aj 🡪Ir 🡪 Ma 🡪 Za 🡪 Am} …. {Aj 🡪 Ja 🡪 Am} }

8. State Set Space : {Ajlun 🡪 Jarash 🡪 Amman}
 Example: Romania
• On holiday in Romania; currently in Arad.
• Flight leaves tomorrow from Bucharest

• Formulate goal:
• be in Bucharest

• Formulate problem:
• states: various cities
• actions: drive between cities

• Find solution:
• sequence of cities, e.g., Arad, Sibiu, Fagaras,
Bucharest
Example: Romania
 Single-state problem formulation
A problem is defined by four items:
initial state e.g., "at Arad"
1. actions or successor function S(x) = set of action–state pairs
• e.g., S(Arad) = {<Arad 🡪 Zerind, Zerind>, … }

2. goal test, can be

• explicit, e.g., x = "at Bucharest"
• implicit, e.g., Checkmate(x)

3. path cost (additive)

• e.g., sum of distances, number of actions executed, etc.
• c(x,a,y) is the step cost, assumed to be ≥ 0

• A solution is a sequence of actions leading from the initial state

to a goal state
 Example Problems
• The problem-solving approach has been applied to a vast array
of task environments. We list some of the best known here,
distinguishing between standardized and real-world problems.

• A standardized problem is intended to illustrate or exercise

various problem solving methods. It can be given a concise,
exact description and hence is suitable as a benchmark for
researchers to compare the performance of algorithms.

• A real-world problem, such as robot navigation, is one whose

solutions people actually use, and whose formulation is
idiosyncratic, not standardized, because, for example, each
robot has different sensors that produce different data.
 Standardized problem Types
• A grid world problem is a two-dimensional
rectangular array of square cells in which
agents can move from cell to cell.
• Typically the agent can move to any
obstacle-free adjacent cell— horizontally or vertically
and in some problems diagonally. Cells can contain objects,
which the agent can pick up, push, or otherwise act upon; a wall
or other impassible obstacle in a cell prevents an agent from
moving into that cell. The vacuum world from Section 2.1 can be
formulated as a grid world problem as follows:
 Standardized problems
• Example: vacuum world
• Number of states: 8
• Initial state: Any
• Number of actions: 4
• left, right, suck,
noOp
• Goal: clean up all dirt
• Goal states: {7, 8}
• Path Cost:
• Each step costs 1
The 8-puzzle
 The 8-puzzle
• States:
• a state description specifies the location of each of
the eight tiles and blank in one of the nine squares
• Initial State:
• Any state in state space
• Successor function:
• the blank moves Left, Right, Up, or Down
• Goal test:
• current state matches the goal configuration
• Path cost:
• each step costs 1, so the path cost is just the length
of the path
 The 8-queens
• There are two ways to formulate the
problem
• All of them have the common followings:
• Goal test: 8 queens on board, not attacking
to each other
• Path cost: zero
 8-Queen Puzzle
• The 8-Queens problem is a classic combinatorial puzzle and a well-known
example of the N-Queens problem. In the 8-Queens problem, the goal is to
place eight chess queens on an 8x8 chessboard in such a way that no two
queens threaten each other. This means that no two queens can share the same
row, column, or diagonal. The challenge is to find all distinct solutions to this
problem.
• A solution to the 8-Queens problem should satisfy the following constraints:1.
Each row must contain exactly one queen.2. Each column must contain exactly
one queen.3. No two queens can be placed in the same diagonal (both
ascending and descending diagonals).The problem is called the "8-Queens"
problem because it specifically involves an 8x8 chessboard. However, the
N-Queens problem is a more general version, where you try to place N queens
on an NxN chessboard while satisfying the same constraints.Solving the
8-Queens problem is not only an interesting puzzle but also has practical
applications in computer science and artificial intelligence, particularly in the field
of constraint satisfaction problems and backtracking algorithms. It serves as a
classic example for demonstrating problem-solving techniques, including
recursive algorithms and optimization strategies.
 The 8-queens
• (1) Incremental formulation
• involves operators that augment the state
description starting from an empty state
• Each action adds a queen to the state
• States:
• any arrangement of 0 to 8 queens on board
• Successor function:
• add a queen to any empty square
 The 8-queens
• (2) Complete-state formulation
• starts with all 8 queens on the board
• move the queens individually around
• States:
• any arrangement of 8 queens, one per column in
the leftmost columns
• Operators: move an attacked queen to a row,
not attacked by any other
 The 8-queens
• Conclusion:
• the right formulation makes a big difference
to the size of the search space
 Example: River Crossing
• Items: Man, Wolf, Corn, Chicken.
• Man wants to cross river with all items.
• Wolf will eat Chicken
• Chicken will eat corn.
• Boat will take max of two.