Page 174 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes solve is not known in advance but must be determined by systematic trial-and-error exploration
of alternatives. The problems that are addressed by AI search algorithms fall into three general
classes: single-agent pathfinding problems, two players games, and constraint-satisfaction
problems

Example: There is a 4l container and 3l container; neither has any measuring markers on
it. There is a pump that can be used to fill the containers with water. Problem to solve is to get
exactly two liters of water in the 4l container.
Solution: From initial state to goal state through appropriate sequence of moves or actions such
as filling and emptying the containers are described as below:
Content of the two containers at any given time is a problem state:

Let x - content of the 4l container
y - content of the 3l container
Then (x,y) - problem state represented by an ordered pair. The set of all ordered pairs is the space
of problem states or the state-space of the problem.
State-space: { (x,y) | x = 0,1,2,3,4 y=0,1,2,3 }
Data structure to represent the state-space can be:

Vectors
Sets
Arrays

Lists

9.2.2 Problem Characteristics

The problem characteristics can be illustrated as:
Suppose: initial state (0,0)
and Goal state (2, y) where y = any possible number.
Moves transform from one state into another state. Operators determine the moves. Operators
for the problem state-space:

1. Fill the 4l container
2. Fill the 3l container
3. Empty the 3l container

4. Empty the 3l container
5. Pour water from 3l container into 4l container until 4l container is full
6. Pour water from 4l container into the 3l container until the 3l container is full

7. Pour all the water from 3l container into the 4l container
8. Pour all the water from 4l container into the 3l container
Preconditions need to be satisfied before an operator can be applied.

e.g.: # 1 can be applied if there is less than 4l water in the container.

168 LOVELY PROFESSIONAL UNIVERSITY