## Thursday, July 8, 2010

### WaterJugProblem

WaterJugProblem
Statement :- We are given 2 jugs, a 4 liter one and a 3- liter one. Neither has any measuring markers on it. There is a pump that can be used to fill the jugs with water. How can we get exactly 2 liters of water in to the 4-liter jugs?
Solution:-
The state space for this problem can be defined as

{ ( i ,j ) i = 0,1,2,3,4 j = 0,1,2,3}

‘i’ represents the number of liters of water in the 4-liter jug and ‘j’ represents the number of liters of water in the 3-liter jug. The initial state is ( 0,0) that is no water on each jug. The goal state is to get ( 2,n) for any value of ‘n’.

To solve this we have to make some assumptions not mentioned in the problem. They are

1. We can fill a jug from the pump.

2. we can pour water out of a jug to the ground.

3. We can pour water from one jug to another.

4. There is no measuring device available.

The various operators (Production Rules) that are available to solve this problem may be stated as given in the following figure .

### AI Problem Solving.! Define the problem as State Space Search.

The steps that are required to build a system to solve 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.

Define the Problem as State Space Search

Consider the problem of “Playing Chess” . to build a program that could play chess, we have to specify the starting position of the chess board, the rules that define legal moves. And the board position that represent a win. The goal of the winning the game, if possible, must be made explicit.

The starting position can be described by an 8 X 8 array square in which each element square (x,y),(x varying from 1to 8 & y varying from 1 to 8) describes the board position of an appropriate chess coin, the goal is any board position in which the opponent does not have a legal move and his or her “king” is under attack. The legal moves provide the way of getting from initial state of final state.

The legal moves can be described as a set of rules consisting of two parts: A left side that gives the current position and the right side that describes the change to be made to the board position. An example is shown in the following figure.

Current Position
While pawn at square ( 5 , 2), AND Square ( 5 , 3 ) is empty,  AND Square ( 5 , 4 ). is empty.

Changing Board Position

Move pawn from Square ( 5 , 2 ) to Square ( 5 , 4 ) .

The current position of a coin on the board is its STATE and the set of all possible STATES is STATE SPACE. One or more states where the problem terminates is FINAL STATE or GOAL STATE . The state space representation forms the basis of most of the AI methods. It allows for a formal definition of the problem as the need to convert some given situation into some desired situation using a set of permissible operations. It permits the problem to be solved with the help of known techniques and control strategies to move through the problem space until goal state is found.

Some of the problems that fall within the scope of AI and the kinds of techniques will be useful to solve these problems.

S.No Problems Techniques

1. Chess Hill climbing

2. Water Jug Best – First Search, Branch and Bound

3. 8 – Puzzle A* Search . Depth First Search

4. Traveling Salesman Heuristic Search

5. Missionaries & Cannibals Best – First Search with backtracking

6. Tower of Hanoi Best First Search

7. Monkey and Bananas Breadth First Search , Best First Search

8. Cryprarithemetic Depth First Search

9. Bridge Depth First Search

## Tuesday, July 6, 2010

2. AI TECHNIQUE

AI problems are of many varieties and they appear to have very little in common. But there are techniques appropriate for the selection of variety of those problems, AI researches have show that “ Intelligence requires knowledge” , and knowledge itself posses some less desirable properties.

It voluminous

It is hard characterize accurately

It is constantly changing

It differs from data

It is organized data

AI techniques EXPLOIT knowledge and for this knowledge must be represented as follows.

AI techniques must be designed keeping in mind the above constraints imposed by AI problems. AI techniques EXPLOIT knowledge and for this knowledge must be represented as follows.

1. Knowledge captures generalizations: Instead of representing individual situations separately , situation that share important properties grouped together . this avoids wastage of ,memory and unnecessary updation.

2. In many AI domains, most of the knowledge a program has, must be provided by people in terms of they understand.

3. It can be easily modified to correct errors.

4. It can be used in several situations even if it is not totally accurate or complete.

5. It can be used to help overcome its own sheer bulk, by helping to narrow the range of possibilities that must be considered.

AI techniques must be designed keeping in mind the above constraints imposed by AI problems.

### AI Languages, Fifth Generation Project.!

AI LANGUAGES

For developing the AI application the researchers use the two languages.

1. LISP – List Processing

2. PROLOG – PROgramming in LOGic.

LISP is used mainly in America for developing the AI application. PROLOG is used in Japan and the other Urop countries for develop the AI applications. Where as in image processing researchers use the natural computer languages FORTRAN & C.

In export systems the researchers use the “OOPS-5”.

FIFTH GENERATION PROJECT:-

To identify the importance of “Artificial Intelligence” JAPAN start the FIFTH GENERATION PROJECT 14 years back. JAPAN government gave the permission to make the special computers for AI applications.

INDIAN IN FIFTH GENERATION PROJECT:-

INDIA also started FIFTH GENERATIN PROJECT 8 years back, for this INDIAN GEOVERNMENT gave the permission to the IIT, ISI (Calcutta). IISI (Bangalore), till no there is no response.

Before studying an AI problem and trying to solve it, the following have to be considered:

- Assumption to be used in solving the problem

- Techniques to be used in solving the problem

- The level of detail at with we are trying to model human intelligence

- How to know when we have succeeded in building an intelligent program.

### Artificial Intelligence Applications.

Applications of Artificial Intelligence:-

1.Problem Solving

2.Game Playing

3.Theorem Proving

4.Natural Language Processing & Understanding

5.Perception General

· Speech Reorganization

· Pattern Reorganization

6.Image Processing

7.Expert System

8.Computer Vision

9.Robotics

10.Intelligent Computer Assisted Instruction

11.Automatic programming

12.Planning & Decision Support systems

13.Engineering Design & Comical Analysis

14. Neural Architecture.

15. Heuristic Classification.

1 Problem Solving:-

This is the first application area of AI research., the objective of this particular area of research is how to implement the procedures on AI systems to solve the problems like Human Beings.

2 :- Game Playing:-
Much of early research in state space search was done using common board games such as checkers, chess and 8 puzzle. Most games are played using a well defined set of rules. This makes it easy to generate the search space and frees the researcher from many of the ambiguities and complexities inherent in less structured problems. The board Configurations used in playing these games are easily represented in computer, requiring none of complex formalisms. For solving large and complex AI problems it requires lots of techniques like Heuristics. We commonly used the term intelligence seems to reside in the heuristics used by Human beings to solve the problems.

3 :- Theorem Proving:-

Theorem proving is another application area of AI research., ie. To prove Boolean Algebra theorems as a humans we first try to prove Lemma., i.e it tell us whether the Theorem is having feasible solution or not. If the theorem having feasible solution we will try to prove it otherwise discard it., In the same way whether the AI system will react to prove Lemma before trying to attempting to prove a theorem., is the focus of this application area of research.

The main goal of this problem is we can ask the question to the computer in our mother tongue the computer can receive that particular language and the system gave the response with in the same language. The effective use of a Computer has involved the use off a Programming Language of a set of Commands that we must use to Communicate with the Computer. The goal of natural language processing is to enable people and language such as English, rather than in a computer language.

It can be divided in to Two sub fields.

Natural Language Understanding : Which investigates methods of allowing the Computer to improve instructions given in ordinary English so that Computers can understand people more easily.

Natural Language Generation : This aims to have Computers produce ordinary English language so that people an understand Computers more easily.

5. Perception:-

The process of perception is usually involves that the set of operations i.e. Touching , Smelling Listening , Tasting , and Eating. These Perceptual activities incorporation into Intelligent Computer System is concerned with the areas of Natural language Understanding & Processing and Computer Vision mainly. The are two major Challenges in the application area of Perception.

1. Speech Reorganization

2. Pattern Reorganization

¨Speech Reorganization:-

The main goal of this problem is how the Computer System can recognize our Speeches. (Next process is to understand those Speeches and process them i.e. Encoding & Decoding i.e producing the result in the same language.) Its one is very difficult; Speech Reorganization can be described in two ways.

1. Discrete Speech Reorganization

Means People can interact with the Computer in their mother tongue. In such interaction whether they can insert time gap in between the two words or two sentences (In this type of Speech Reorganization the computer takes some time for searching the database).

2. Continues Speech Reorganization

Means when we interact with the computer in our mother tongue we can not insert the time gap in between the two words or sentences , i.e. we can talk continuously with the Computer (For this purpose we can increase speed of the computer).
¨Pattern Reorganization: -

this the computer can identify the real world objects with the help of “Camera”. Its one is also very difficult , because

- To identify the regular shape objects, we can see that object from any angle; we can imagine the actual shape of the object (means to picturise which part is light fallen) through this we can identify the total structure of that particular object.

-To identify the irregular shape things, we can see that particular thing from any angle; through this we cannot imagine the actual structure. With help of that we can attach the Camera to the computer and picturise certain part of the light fallen image with the help of that whether the AI system can recognize the actual structure of the image or not? It is some what difficult compare to the regular shape things, till now the research is going on. This is related the application area of Computer Vision.

A Pattern is a quantitative or structured description of an object or some other entity of interest of an Image. Pattern is found an arrangement of descriptors. Pattern recognition is the research area that studies the operation and design of systems that recognize patterns in data. It encloses the discriminate analysis, feature extraction, error estimation, cluster analysis, and parsing (sometimes called syntactical pattern recognition). Important application areas are image analysis, character recognition, speech recognition and analysis, man and machine diagnostics, person identification and industrial inspection.

Closely Related Areas Pattern Recognition

Artificial Intelligence

Expert systems and machine learning

Neural Networks

Computer Vision

Cognition

Perception

Image Processing

6.Image Processing:-
Where as in pattern reorganization we can catch the image of real world things with the help of Camera. The goal of Image Processing is to identify the relations between the parts of image.

It is a simple task to attach a Camera to a computer so that the computer can receive visual images. People generally use Vision as their primary means of sensing their environment. We generally see more than we here. i.e. how can we provide such perceptual facilities touch, smell, taste, listen, and eat to the AI System. The goal of Computer Vision research is to give computers this powerful facility for understanding their surroundings. Currently, one of the primary uses of Computer Vision is in the area of Robotics.

Ex: - We can take a Satellite image to identify the roots and forests; we can make digitize all the image and place on the disk. With the help of particular scale to convert the image in to dots form, later we can identify that particular image at any time. Its one is time consuming process. With the help of “ image processing” how to reduce the time to process an image till now the AI research will be continuously going on.

In Image Processing the process of image recognition can be broken into the following main stages.

· Image capture

· Edge detection

· Segmentation

· Recognition and Analysis.

Image capturing can be performed by a simple Camera, which converts light signals from a scale of electrical signals., i.e., done by human visual system. We obtained these light signals in a set of 0’s and 1’s. Each pixel takes on one of a number of possible values often from 0 to 255. Color images are broken down in the same way, but with varying colors instead of gray scales. When a computer receives an image from sensor in form of set of pixels. These pixels are integrated to give the computer an understanding of what it is perceiving.

An image has been obtained, is to determine where the edges are in the image, the very first stage of analysis is called edge detection. Objects in the real world are almost all have solid edges of one kind or another, detecting those images is first step in the process of determining which objects are present in a scene.

Once the edges have been detected, in an image, this information can be used to Segment the image, into homogeneous areas. There are other methods available for segmenting an image, apart from using edge detection, like threshold method. This method involves finding the color of each pixel in an image and considering adjacent pixels to be in the same area as long as their color is similar enough.

A similar method for segmenting images is splitting and merging. Splitting involves taking an area that is not homogeneous and splitting it into two or more smaller areas, each of which is homogeneous. Merging involves taking two areas that are the same as each other, and adjacent to each other and combining them together into a large area. This provides a sophisticated interactive approach to segmenting an image.

Intermediate Level of processing

Low Level Processing High Level Processing

7.§Expert system:- Expert means the person who had complete knowledge in particular field, ie is called as an expert. The main aim of this problem is with the help of experts, to load their tricks on to the compute and make available those tricks to the other users. The expert can solve the problems with in the time.

The goal of this problem is how to load the tricks and ideas of an expert on to the computer, till now the research will be going on.

8. § Computer Vision:- It is a simple task to attach a camera to a computer so that the computer can receive visual images. People generally use vision as their primary means of sensing their environment. We generally see more than we here, feel, smell, or taste.

The goal of computer vision research is to give computers this powerful facility for understanding their surroundings. Currently, one of the primary uses of computer vision is in the area of Robotics.

9. § Robotics:-

A robot is an electro – mechanical device that can be programmed to perfume manual tasks. The robotics industries association formally defines to move a Robot as a “ Programmable multi-functional manipulator designed to move material, parts, tools, or specialized devices through variable programmed motions for the performance of variety of tasks”.

Not all robotics is considered to be part of AI. A Robot that perform sonly the actions that it is has been pre-programmed to perform is considered to be a “dumb” robot, includes some kind of sensory apparatus, such as a camera , that allows it to respond to changes in its environment , rather than just to follow instructions “mindlessly”.

10. § Intelligent Computer – Assisted Instruction:-
Computer - Assisted Instruction (CAI) has been used in bringing the power of the computer to bear on the educational process. Now AI methods are being applied to the development of intelligent computerized “ Tutors” that shape their teaching techniques to fit the leaning patterns of individual students.

11. § Automatic Programming:- Programming is the process of telling the computer exactly what we want to do . the goal of automatic programming is to create special programs that act as intelligent “Tools” to assist programmers and expedite each phase of the programming process. The ultimate aim of automatic programming is a computer system that could develop programs by itself, in response to an in according with the specifications of the program developer.

12. § Planning and Decision Support system:- When we have a goal, either we rely on luck and providence to achieve that goal or we design and implement a plan. The realization of a complex goal may require to construction of a formal and detailed plan. Intelligent planning programs are designed to provide active assistance in the planning process and are expected to the particularly helpful to managers with decision making responsibilities.

13. §Engineering Design & Camical Analysis:-

Artificial Intelligence applications are playing major role in Engineering Drawings & Camical analysis to design expert drawings and Camical synthesis.

14. § Neural Architecture:-

People or more intelligent than Computers,. But AI researchers are trying how make Computers Intelligent. Humans are better at interpreting noisy input, such as recognizing a face in a darkened room from an odd angle. Even where human may not be able to solve some problem, we generally can make a reasonable guess as to its solution. Neural architectures, because they capture knowledge in a large no. of units. Neural architectures are robust because knowledge is distributed somewhat uniformly around the network.

Neural architectures also provide a natural model for parallelism, because each neuron is an independent unit. This showdown searching the data base a massively parallel architecture like the human brain would not suffer from this problem.

15. § Heuristic Classification:-

The term Heuristic means to Find & Discover., find the problem and discover the solution. For solving complex AI problems it’s requires lots of knowledge and some represented mechanisms in form of Heuristic Search Techniques., i.e refered to known as Heuristic Classification.