Module 3
What is problem solving agent? How to formulate a problem? State space of a problem: -
1. The problem-solving agent is a type of goal-based agent which uses atomic representation with no
internal states visible to the problem-solving algorithms and performs precisely by defining problems
and its several solutions.
2. “A problem-solving refers to a state where we wish to reach to a definite goal from a present state or
condition”
3. Problem formulation is the process of deciding what actions and states to consider, given a goal.
4. Process of looking for action sequence (number of actions that agent carried out to reach to goal) is
called search.
5. A search algorithm takes a problem as input and returns a solution in the form of an action sequence.
Once a solution is found, the actions it recommends can be carried out. This is called the execution
phase.
6. Thus, we have a simple "formulate, search, execute" design for the agent.
7. A problem is defined by following items:
a. Initial State: It is the starting state or initial step of the agent towards its goal.
b. Actions: It is the description of the possible actions available to the agent.
c. Transition Model/successor function: It describes what each action does. This function returns a set
of ordered pair where each action is one of the legal actions in state x and each successor is a state
that can be reached from x by applying the action
d. Goal Test: It determines if the given state is a goal state.
e. Path cost: It assigns a numeric cost to each path that follows the goal.
Compare and contrast problem solving agent and planning agent: -
State space representation for 8 puzzle problem: -
1. States: It describes the location of each numbered tiles and the blank tile.
2. Initial State: We can start from any state as the initial state.
3. Actions: Here, actions of the blank space are defined, i.e., either left, right, up or down
4. Transition Model: It returns the resulting state as per the given state and actions.
5. Goal test: It identifies whether we have reached the correct goal-state.
6. Path cost: The path cost is the number of steps in the path where the cost of each step is 1.
State space representation for 8-queens problem: -
1. States: Arrangement of any 0 to 8 queens on the chessboard.
2. Initial State: An empty chessboard
3. Actions: Add a queen to any empty box.
4. Transition model: Returns the chessboard with the queen added in a box.
5. Goal test: Checks whether 8-queens are placed on the chessboard without any attack.
6. Path cost: There is no need for path cost because only final states are counted.
State space representation for Missionaries and Cannibals Problem: -
Representation of a State of the World:
The state of the world is represented by two lists:
L<MCB>R<MCB>
L is the left bank, and R is the right bank.
M and C represent the number of missionaries and cannibals on each of their respective banks such that
M = {0,1,2,3} and C = {0,1,2,3}
B represents the boat such that B = {0,1}. When B=1 it is on that bank, when B=0 it is on the other.
Initial state: L < 3 3 1 > R < 0 0 0 >
Goal state: L < 0 0 0 > R < 3 3 1 >
State Space Graph:
State Space Solution
< CCR, CL, CCR, CL, MMR, MCL, MMR, CL, CCR, CL, CCR >