preload preload preload preload

Artificial Intelligence

What is AI?
AI is the study of how to make computers do things that at the moment we do better.
The automation activities that we associate with human thinking, activites such as decision making, problem solving, learning etc...

Some of the Application Area of AI:

Ordinary Tasks:

* Perceptional
   -vision
   -speech
*Natural Language
   -Understanding
   -Generation
   -Translation
* Common-sense Reasoning
* Robot Control

Formal Tasks:

*Games
  -Chess
  -Checkers
  -Go
  ......
*Mathematics
  -Geometry
  -Logic
  -Integral Calculus

Expert Tasks:  

*Engineering
   -Design
   -Fault finding
   -Manufacturing planning
*Scientific analysis
*Medical Diagnosis
*Financial analysis


Knowledge the Backbone of Intelligence?
It is proved that intelligence requires knowledge. Knowledge possess some un desirable properties though-
       -> It is huge
       -> Hard to characterize accurately
       -> It is always changing
       -> Differs greatly from data
       -> Organised in the way it would be used!!??


Some AI techniques to represent Knowledge

The knowledge captures generalisation. In other words, it is not necessary to present separately each individual situation. Instead, situation that share important properties are grouped together. 

It can be understood by people who must provide it. Most of the knowledge a program hast muslt ultimately be provided by people in terms they understand.

It can easily be modifies to correct errors and to reflect changes in the world and in our view.


It can be used in a great many situations even if it is not totally accurate or complete.


It can be used to help overcome its own sheer bulk by helping to narrow the range of possibilities.


To build a system to solve a problem we need four things-

1. Define the problem precisely.
This definition must include precise specifications of what the initial situations will be as well as what final situations constitute applicable


2. Analyse the problem.
A few very important features can have immense effect on the appropriateness of various possible techniques.


3. Isolate and represent the knowledge
Knowledge that is required to solve the problem


4. Choose the best problem solving technique and apply it.



Define you problem as a State Space Search-

1. Define the State Space.
This will include all the possible configuration of the relevant objects.

2. Specify start state
1or more state within the state space that describe possible situation where the problem solving process may start.

3. Specify Goal
1 or more states within the same State Space that would be acceptable as a solution to our problem.


4. Specify the set of rules
Rules that describe actions available from each state.



The "Water-jugs Problem"

Problem: You are given two jugs, a 4-gallon one and a 3-gallon
one. Neither has any measuering marks on it. There is a pump that can
be used to fill the jugs with water. How can you get exactly 2 gallons
of water in the 4-gallon jug?

A state in this problem may be represented as a two-tuple (x,y), 
where
x stands for the amount of water in the 4-gallon jug, and 
y denotes the amount of water in the 3-gallon jug.

The initial state is <0,0> and the goal state is (2,0)

%----------------------------------------------------------------------------

2. World Knowledge and Knowledge Representation

Solving problems requires knowledge of the world.  
World knowledge can of many kinds.
One kind of world knowledge is knowledge about the possible actions in
a given world.

Example: In the water jug problem, one possible action is to pump
water into the 4 gallon jug until the jug is full

An OPERATOR is knowledge of an action possible in the world.

This kind of world knowledge can be represented in the LANGUAGE of
PRODUCTION RULES.

Production rules offer one language for representing some kinds of
knowledge including that of operations (that is, knowledge of the
actions that can be performed in the world).

For this example, all ten basic operations can be represented in the
language of production rules as follows:
R1: (x,y) --> (4,y)
    if x < 4
R2: (x,y) --> (x,3)
    if y < 3
R3: (x,y) --> (x-d,y)
    if x > 0
R4: (x,y) --> (x,y-d)
    if y > 0
R5: (x,y) --> (0,y)
    if x > 0
R6: (x,y) --> (x,0)
    if y > 0
R7: (x,y) --> (4,y-(4-x))
    if x+y >= 4 and y > 0
R8: (x,y) --> (x-(3-y),y)
    if x+y >= 3 and x > 0
R9: (x,y) --> (x+y,0)
    if x+y =< 4 and y > 0
R10: (x,y) --> (0,x+y)
    if x+y =< 3 and x > 0
 
Production systems:
  It is useful to structure AI programs in a way that facilitates describing and performing the search process. Production systems provide such structures. A production system consists of-

1. A set of rules, each consisting of a left side (a pattern) that determines the applicability of the rule and right side that describes the operation which is to be performed if the rule is applicable.
 
2. One or more knowledge database that contain whatever information is appropriate for the particular tasks

3. A control strategy that describes the order in which the rules will be compared to the database and a way to resolve conflicts that arise when several rules are matched at once.


4. A rule applier.


Control Strategy:
  Control strategy is an important factor for a solution to a problem because it decides which rule to apply next during the searching process.



1. The first requirement of a good strategy is that it cause motion.
Control strategy that do not cause motion will never lead to a solution
 
2. Second requirement is Systematic.
When there are more than one applicable, choose at random. 
 
Heuristic Search:
  A technique that improves the efficiency of the search process by sacrificing claims of completeness.


Example...
A good general purpose heuristic that is useful for a variety of combinational problems is the nearest neighbour  heuristic. If we apply it for the TravelSalesmanProblem the following procedure will take-


1. Arbitrarily select a starting city.
2. To select the next city look at the cities not yet visited. and select the one closest . Go to it next.
3. Repeat step 2 until all the cities are visited.





Heuristic Function
A heuristic function is a function that maps from problem state descriptions to measure of desirability. usually represented as numbers. The purpose of a heuristic function is to guide the process in the most efficient direction by suggesting which path to follow first when more than one is available.


In our case of above the sum of distances.


Problem Characteristics:
  In order to choose the most appropriate method for a particular problem it is necessary to analyse the problem along several key dimensions.

1. Is the problem decomposable?    ex:    integrate(x^2 + 3x + sin^2( x))dx

2. Can solution steps be ignored or undone?  ex: recoverable 8puzzle, unrecoverable chess

3. Is the universe predictable? ex: predictable 8puzzle, unpredictable bridge

4. Is a good solution absolute or relative  ex: abs Best path, rltv any path

5. Is the solution a state or a path? ex: state waterjug, path TSP

6. What is the role of knowledge? ex:  Less playing chess, human language parsing

7. Does it require interaction ? ex: converstion (req), Solitary (dont req)



Thas all for my tomorrows class test!! pray for me ..