Chapter Three
Problem Solving
What is a Problem? It is a gap between the existing scenario and the expected scenario (situation). A
problem exists when an individual becomes aware of the existence of an obstacle which makes it
difficult to achieve a desired goal or objective. A number of problems are addressed in AI. Mainly there
are two types of problems:
1. Problems with discrete environment: These problems need limited number of actions to achieve
a goal.
Example: The problems like computing the area of a square. These can be solved by using
deterministic procedure and success is guaranteed. However, in real world, there are very few
problems which can be solved using straight-forward methods.
2. Problems with continuous environment: sometimes, problems can be continuous duet to
environmental factors. For such problems, a number of actions are required to get the solution.
Most real world problems are solved by searching for solution. Artificial Intelligence is concerned
with such type of problems.
Problem Solving: Deals with finding a solution for a given problem. This is done by finding an ordered
sequence of operators that transform the current state (initial state) into a goal state. There are
restrictions in problem solving, which are expected to happen that deals with the quality of the solution.
Finding the shortest solution
Finding the least expensive defining cost
Finding any sequence as quickly as possible
Moreover, problems can be solved either in a general problem solving approach or in a well-defined
problem solving approach.
Well-defined problems and solutions
A problem in general can be defined formally by the following components. The initial state, actions,
and state transition implicitly define the state space of the problem. If the problem is well-defined then,
it incorporates goal test and path cost functions.
1. Initial State: the agents starting point (s).
2. Actions (Operators): A description of the possible actions available to the agent given a
particular state s, actions returns the set of actions that can be executed in s.
3. Transition States: A description of what each action does. The term successor generator can
be used to refer to any state reachable from a given state by a single action.
1
4. Goal Test: Determines whether a given state is a goal state. Sometimes there is an explicit set of
possible goal states, and the test simply checks whether the given state is one of them.
5. Path Cost: is a sequence of states connected by a sequence of actions.
State Space of a problem incorporates the set of all states reachable from the initial state by any
sequence of actions. The state space forms a directed network or graph in which the nodes are states
and the links arc/curve between nodes are actions. Path cost function determines the cost of sequence of
states connected by a sequence of edges (actions). Moreover, goal test function determines whether a
given state is a goal state. Sometimes there are many possible set of goals indicated explicitly.
Structure of state space
(Graph & Tree)
To simplify search algorithms, it is convenient to represent a problem in tree instead of a graph. Tree
usually decreases complexity of search at cost. There are duplicating nodes in a graph linked more than
one time. Tree is a graph in which any two vertices are connected by exactly one path.
N.B: Alternatively any graph with directed arrows/ no cycle are a tree.
• Tree:
– Hierarchical structure in a graphical form which has only one path to a given node.
• Graph:
– Non-hierarchical structure with several paths to a given node.
2
Steps in problem solving
1. Goal Formulation: This is a step that specifies exactly what the goal based agent is trying to
achieve. This step narrows down the scope that the agent has to look at by selecting certain states
as goals from the rest of the set of states in the problem definition.
2. Problem Formulation: Is a step that puts down the actions and states that the agent has to
consider given a goal by avoiding any redundant states; such as, the initial state and the
allowable actions.
N.B: Problem formulation has a serious influence on the difficulty of finding a solution for a
problem. If you have a good problem formulation then, it will be easy to find the solution. On the
other hand if the problem formulation is bad, finding the solution will be difficult. Therefore, the
quality of a goal (solution) highly depends on the quality of problem formulation.
3. Search: This step deals with the process of looking for the various sequences of actions that
lead to a goal state, evaluating them and choosing the optimal sequence as much as possible.
Searching is done on the implicit sate of states so that reaching a goal is very challenging or else
on an explicit set of state hence, searching will be easy.
4. Execute: Is the final step that the agent executes and declares that, the chosen sequence of
actions leads to the solution and/or goal.
Examples of
Problems
3
Example: Vacuum Cleaner World
Problem definition for vacuum cleaner world
States space: The state is determined by both the agent location and the dirt locations. The agent is in
one of two locations, each of which might or might not contain dirt. That means, the world state space
has only 2 positions, dirt or no dirt, with 8 possible states. Possible actions are Move Left (L), Move
Right (R), or Suck the dirt (S). The goal is to clear all the dirt from the rooms and the path costs is one
unit per action.
1. Initial state: Any state can be designated and taken as the initial state.
2. Actions: In this simple environment, each state has just three actions: Left, Right, and Suck.
However, larger environments can also include other actions such as move Up and move Down
in the state space.
3. Transition State: 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.
4. Goal Test: This checks whether all the rooms are clean or not.
5. Path Cost: Each step costs a unit cost (1), so the path cost is the number of steps in the path.
Move right cost=>1, Move Left cost=>1.
Clean House Task
It is obvious that the world is too complex for a single robot to observe what is in the environment and
take some sequences actions accordingly. To simplify the complexity of the problem (rather than seen
the full version of the problem); let us assume that:
4
• The world has only two locations for the sake of simplicity even though the world is so complex
and very challenging to come up with limited number of states and actions.
• Each location may or may not contain dirt
• The agent may be in one location or the other,
– Hence, there 8 possible world states and 3 possible actions (Left, Right, Suck)
• Suck operator clean the dirt
• Left and Right operators move the agent from location to location. The agent
cannot move outside the rooms.
• Goal: to clean up all the dirt in the rooms, if and only if there is dirt in both or one
of the rooms. Otherwise, the agent will end up with failure if it tries to clean a
room which is already with no dirt.
Vacuum Cleaner state Space
• The assumption is that the agent is in fully observable world. The world is accessible to the
agent, hence:
– It can determine its exact state through its sensors
– The agent’s sensor knows in which state it is currently
• Furthermore, the agent is in a deterministic environment and knows exactly the effect of its
actions. Moreover, the calculate exactly which state it will be in after any sequence of actions
• Action sequence is completely planned and known. The agent is clear with what action to be
taken.
Example - Vacuum cleaner world:
Q. What will happen if the agent is initially at [state = 5] and formulates action sequence [Right,
Suck]? Agent calculates and knows that it will get to a goal state.
5
• If the agent moves Right then, it is on state {6}
• After taking the action Suck the dirt in state six, the agent is finally on state {8}
N.B: If the environment is completely observable, the vacuum cleaner always knows where it is
and where the dirt is. The solution then is reduced to searching for a path from the initial state to
the goal state easily.
8-Puzzle Problem
Given an initial configuration of 8 numbered tiles on a 3 x 3 board, move the tiles so as to
produce a desired goal configuration of the tiles.
Missionaries and Cannibals
There are 3 missionaries, 3 cannibals, and 1 boat that can carry up to two people on one side of a
river. Move all the missionaries and cannibals across the river.
N-Queens
• States: Any arrangement of 0 to 8 queens on the board is a state.
1. Initial state: No queens on the board.
2. Actions: Add a queen to any empty square.
3. Transition State: Returns the board with a queen added to the specified squares
4. Goal Test: 8 queens are on the board, none of them are attacked each other.
6
Formalize the problem: Identify the collection of information that the agent will use to decide what to
do.
1. Define states: States describe distinguishable stages during the problem-solving process
Example: What are the various states in route finding problem? The various places
including the current location of the agent
2. Define state operators/rules: Identify the available operators for getting from one state to
the next operators cause an action that brings transitions from one state to another by
applying on a current state
3. Construct state space: Suggest a suitable representation (such as graph, tree or a
combination of them) to construct the final state space.
State Space of the Problem
The state space defines the set of all relevant states reachable by any sequence of actions from
the initial state until the goal state is reached.
State space which is also called search space and/or problem space of the problem includes
the various states:
– Initial state: defines where the agent starts or begins its task
– Goal state: defines the situation the agent attempts to achieve
– Transition states: other states in between initial and goal states
– Our aim is building goal-based agent; that is
– An agent which has a goal to reach by applying a sequence of actions starting the initial
state
Here are some examples of goals to be achieved by an intelligent goal based agents.
– To drive from city A to city B crossing many intermediate transition states.
– To put 8 queens on a chess board such that no one attacks another
To build a goal based agent, which solves certain problems, we need to answer the following basic
questions:
7
– What is the goal to be achieved?
– What are the actions?
– What relevant information is necessary to encode about the world to describe the state of
the world, describe the available transitions, and solve the problem?
Example: Coloring problem
• There are 3 rectangles. Both are initially white. The problem is to change all rectangles with
white color to black color. Color change is one rectangle at a time.
– Identify possible states and Operators?
• Fill-Color(whiteRectangle, Black)
– Construct state space for coloring problem?
Initial Goal
– N.B: there are different routes to reach a goal state
The 8 puzzle problem
Puzzles are problems designed to have value as entertainments. The term puzzle typically refers to
problems in recreational mathematics, geometry, and language often as a means for education, cognitive
skills enhancement in symbolic reasoning or logic. This is the problem of arranging the tiles so that all
the tiles are in the correct positions. This is done by moving tiles or space up, down, left, or right, so
long as the following conditions are met:
– a) there's no other tile blocking you in the direction of the movement; and
– b) It is not possible to move outside of the boundaries/ edges of the problem box.
• Identify possible states & operators?
• Construct state space?
8
Initial State Goal State
Exercise: River Crossing Puzzles
Missionary-and-cannibal problem
Three missionaries and three cannibals are on one side of a river that they wish to cross. There is a boat
that can hold one or two people. Find an action sequence that brings everyone safely to the opposite
bank (i.e. Cross the river). But you must never leave a group of missionaries outnumbered by cannibals
on the same bank (in any place).
1. Identify the set of possible states and operators
2. Construct the state space of the problem using suitable representation
Goat, Wolf and Cabbage problem
A farmer returns from the market, where he bought a goat, a cabbage and a wolf. On the way home he
must cross a river. His boat is small and unable to transport more than one of his purchases. He cannot
leave the goat alone with the cabbage (because the goat would eat it), nor he can leave the goat alone
with the wolf (because the goat would be eaten). How can the farmer get everything safely on the other
side?
1. Identify the set of possible states and operators
2. Construct the state space of the problem using suitable representation
Problem Formulation: means choosing a relevant set of states to consider and a feasible set of
operations for moving from one state to another.
Search is the process of imagining sequences of operations applied to the initial state and checking
which sequence reaches a goal state.