PROBLEMS, PROBLEM SPACES AND SEARCH
To solve the problem of building a system you should take the following steps:
1. Define the problem accurately including detailed specifications and what constitutes a suitable
solution.
2. Scrutinize the problem carefully, for some features may have a central affect on the chosen method
of solution.
3. Segregate and represent the background knowledge needed in the solution of the problem.
4. Choose the best solving techniques for the problem to solve a solution.
Problem solving is a process of generating solutions from observed data.
• a ‘problem’ is characterized by a set of goals,
• a set of objects, and
• a set of operations.
These could be ill-defined and may evolve during problem solving.
• A ‘problem space’ is an abstract space.
A problem space encompasses all valid states that can be generated by the application of any
combination of operators on any combination of objects.
The problem space may contain one or more solutions. A solution is a combination of
operations and objects that achieve the goals.
A ‘search’ refers to the search for a solution in a problem space.
Search proceeds with different types of ‘search control strategies’.
The depth-first search and breadth-first search are the two common search strategies.
Problem definitions
A problem is defined by its ‘elements’ and their ‘relations’. To provide a formal description of a problem,
we need to do the following:
a. Define a state space that contains all the possible configurations of the relevant objects, including
some impossible ones.
b. Specify one or more states that describe possible situations, from which the problemsolving process
may start. These states are called initial states.
c. Specify one or more states that would be acceptable solution to the problem.
These states are called goal states.
Specify a set of rules that describe the actions (operators) available.
The problem can then be solved by using the rules, in combination with an appropriate control strategy,
to move through the problem space until a path from an initial state to a goal state is found. This
process is known as ‘search’. Thus:
Search is fundamental to the problem-solving process
Search is a general mechanism that can be used when a more direct method is not known.
Search provides the framework into which more direct methods for
solving subparts of a problem can be embedded. A very large number of AI problems are
formulated as search problems.
Problem space
A problem space is represented by a directed graph, where nodes represent search state and
paths represent the operators applied to change the state.
To simplify search algorithms, it is often convenient to logically and programmatically represent
a problem space as a tree. A tree usually decreases the complexity of a search at a cost. Here,
the cost is due to duplicating some nodes on the tree that were linked numerous times in the
graph, e.g. node B and node D
A tree is a graph in which any two vertices are connected by exactly one path. Alternatively, any
connected graph with no cycles is a tree.
Diagram
• Problem solving: The term, Problem Solving relates to analysis in AI. Problem solving may be
characterized as a systematic search through a range of possible actions to reach some
predefined goal or solution. Problem-solving methods are categorized as special purpose and
general purpose.
• A special-purpose method is tailor-made for a particular problem, often exploits very specific
features of the situation in which the problem is embedded.
• A general-purpose method is applicable to a wide variety of problems. One General-purpose
technique used in AI is ‘means-end analysis’: a step-bystep, or incremental, reduction of the
difference between current state and final goal.
DEFINING PROBLEM AS A STATE SPACE SEARCH
To solve the problem of playing a game, we require the rules of the game and targets for
winning as well as representing positions in the game. The opening position can be defined as
the initial state and a winning position as a goal state. Moves from initial state to other states
leading to the goal state follow legally. However, the rules are far too abundant in most games
— especially in chess, where they exceed the number of particles in the universe. Thus, the rules
cannot be supplied accurately and computer programs cannot handle easily. The storage also
presents another problem but searching can be achieved by hashing.
The number of rules that are used must be minimized and the set can be created by expressing
each rule in a form as possible. The representation of games leads to a state space
representation and it is common for well-organized games with some structure. This
representation allows for the formal definition of a problem that needs the movement from a
set of initial positions to one of a set of target positions. It means that the solution involves using
known techniques and a systematic search. This is quite a common method in Artificial
Intelligence
State Space Search
A state space represents a problem in terms of states and operators that change states. A state
space consists of:
A representation of the states the system can be in. For example, in a board game, the board
represents the current state of the game.
A set of operators that can change one state into another state. In a board game, the operators
are the legal moves from any given state. Often the operators are represented as programs that
change a state representation to represent the new state.
An initial state.
A set of final states; some of these may be desirable, others undesirable. This set is often
represented implicitly by a program that detects terminal state.
