Page 22 - DCAP506_ARTIFICIAL_INTELLIGENCE

Artificial Intelligence

Notes Introduction

Problems have the general form given such-and-such data, find x. A huge variety of types of
problem is addressed in AI. Some examples are: finding winning moves in board games;
identifying people from their photographs; and planning series of movements that enable a
robot to carry out a given task. In this unit, you will understand various concepts of problems,
problem spaces & search.

2.1 Defining the Problem as a State Space Search

The steps that are needed to make a system to work out a particular problem are:

1. Problem Definition that must include precise specifications of what the initial situation
will be as well as what final situations constitute acceptable solutions to the problem.
2. Problem Analysis, this can have immense impact on the appropriateness of varies possible
techniques for solving the problem.
3. Selection of the best technique(s) for solving the particular problem.
The thought of State Space Search is broadly used in Artificial Intelligence. The plan is that a
problem can be solved by probing the steps which might be taken for the solution. Every action
takes the solver to a novel state.

Example: The typical example is of the Farmer who is required to transport a Chicken,
a Fox and some Grain across a river separately. The Fox will eat the Chicken if left unconfirmed.
Similarly the Chicken will eat the Grain.
Here, the State is illustrated by the positions of the Farmer, Chicken, Fox and Grain. The solver
can move among States by making a legal move (which does not consequence in something
being eaten). Non-legal moves are not valued analyzing.
The clarification to such a problem is a record of linked States leading from the Initial State to the
Goal State. This may be found either by beginning at the Initial State and functioning towards
the Goal state or vice-versa.
The necessary State can be functioned towards by either:
 Depth-First Search: Discovering each strand of a State Space in turn.
 Breadth-First Search: Discovering every link encountered, analyzing the state space a
level at a time.
These techniques usually use lists of:
 Closed States: States whose links have all been discovered.

 Open States: States which have been came across, but have not been fully explored.
Supremely, these lists will also be used to avert endless loops.

Example: Take into account the problem of “Playing Chess”. To construct a program
that could play chess, we have to identify the beginning position of the chess board, the rules
that describe legal moves. And the board position that symbolize a win. The objective of the
winning the game, if possible, must be made unambiguous.
The beginning position can be illustrated by an 8 × 8 array square in which every element square
(x,y), (x ranging from 1 to 8 & y varying from 1 to 8) illustrates the board position of a suitable

16 LOVELY PROFESSIONAL UNIVERSITY