Artificial Intelligence Unit-1

Unit-1

Lecture-1

Introduction to Artificial Intelligence

• Artificial Intelligence is a rapidly evolving field of engineering with an ultimate objective to build machines capable of acting and thinking like human beings.
• —  However, the process involved in building intelligent systems is not a fish that can be caught easily, as it would have been imagined by early researchers, rather it is one of most intricate, complex and in one way or other, most challenging job ever taken by human beings on their hands, since human is trying to prototype his own mind. 

Artificial Intelligence is concerned with the design of intelligence in an artificial device.

• —  The term was coined by John McCarthy in 1956.
• —  There are two ideas in the definition.

1. Intelligence
2. Artificial device 

Intelligence

• —  Intelligence is the ability to reason, to trigger new thoughts, to perceive and learn.
• —  Intelligence is the ability to learn, to deal with different situations, to acquire, understand and apply knowledge and to analyze and reason.

Artificial Intelligence

“Developing computer programs to solve complex problems by application of processes that are analogous to human reasoning processes”

Or

“AI is a branch of computer science concerned with the study and creation of computer systems and exhibit some form of intelligence: systems that learn new concepts and tasks, systems that can reason and draw useful conclusions about the world around us, systems that can understand a natural language or perceive and comprehend a visual scene, and systems that perform other types of feats that require human types of intelligence”

Weak and Strong AI

• —  There are two themes of thoughts in Artificial Intelligence, namely weak AI and strong AI.
• —  The Strong AI line of thinking is very enthusiastic about AI and makes a bold claim that computers can be made to think almost equal to the level of human being and they can possibly be conscious about themselves.
• —  Hence if asked whether computers be intelligent, the strong AI says yes, just wait for the faster computers.
• —  The Weak AI is however not so enthusiastic about the outcomes of AI and it simply says that some thinking like features can be added to computers to make them more useful tools. It says that computers cannot be made intelligent equal to human beings, unless constructed significantly differently.
• —  Strong AI is the supposition that some forms of artificial intelligence can truly reason and solve problems; strong AI supposes that it is possible for machines to become sapient, or self-aware, but may or may not exhibit humanlike thought processes.
• —  The term Strong AI was originally coined by John Searle, who writes-
• “According to strong AI, the computer is not merely a tool in the study of the mind; rather, the appropriately programmed computer really is a mind.”
• —  In contrast to strong AI, weak AI refers to the use of software to study or accomplish specific problem solving or reasoning tasks that do not encompass the full range of human cognitive abilities.

Turing Test

• —  Turing in 1950 published an article in the Mind magazine, which triggered a controversial topic “Can a Machine Think?”
• —  Turing proposed an ‘imitation game’ which was later modified to “Turing Test”. In the imitation game, the players are three humans- a male, a female and an interrogator. The interrogator who is shielded from the other two; asks questions to both of them and based on their typewritten answers determines who is male and who is female.
• —  The aim of the male is to imitate the female and deceive the interrogator and the role of female is to provide replies that would inform the interrogator about her true gender.
• —  The “Turing Test” is a slight variation of this imitation game wherein the human interrogator now communicates with the players via a teletype – one human and the other, a machine. The diagrammatic representation is given below:
  
• Turing proposed that if the human interrogator in Room C is not able to identify who is in room A or in room B, then the machine possesses intelligence. Turing considered this as a sufficient test for attributing thinking capacity to a machine.
• —  However, the test is not that easy as proposed. Humans are far more superior in creativity, common sense and reasoning. If any question is put on these topics, humans are sure to excel. On the numerical computation part, machines are accurate and faster.
• —  Even though a delay loop can be introduced to provide answers after some time, machines can never be wrong in their computations whereas there exist a probability that humans may give incorrect answers after taking sufficiently long time.
• —  As of today, Turing test is the ultimate test a machine must pass in order to be called as intelligent.

Turing test has come under severe criticism for the following reasons:

•    Assuming that the machine has passed the Turing test, the question that has to be answered is what level of proficiency it has achieved. It is easier to say that it is the level of the programmer who has programmed it. In fact, the machine demonstrates the intelligence of the human being only.
• Searle proposed an argument called Chinese room argument to bring into limelight the major flaw in Turing test. According to this argument, he, Searle who did not know Chinese was locked in a room with a set of Chinese alphabets. He was provided with a small writing in Chinese (a story, for e.g.) with instructions in English that would co-relate the first and second set of symbols. Lastly he was provided with a set of questions to be answered supported by instructions in English. Searle claimed that he could manipulate the Chinese symbols in a very formal way and provide satisfactory answers to the people outside thereby creating an illusion that he knows Chinese.
• Actually, what was done was mere manipulation of the symbols without understanding what they were. Searle argued that the machine that passes the Turing test and assumed to be intelligent behaves in the same fashion, manipulates formal symbols but lacks understanding.

Difference between Human brain and Computer

Lecture-2

Problem Solving through AI

Let us first discuss some terms related with AI problem solution methodology:

• —  Problem: It is the question which is to be solved. For solving a problem it needs to be precisely defined. The definition means, defining the start state, goal state, other valid states and transitions.
• —  Search Space: It is the complete set of states including start and goal states, where the answer of the problem is to be searched.
• —  Search: It is the process of finding the solution in search space. The input to search space algorithm is problem and output is solution in form of action sequence.
• —  Well defined problem: A problem description has three major components. Initial state, final state, space including transition function or path function. A path cost function assigns some numeric value to each path that indicates the goodness of that path.
• —  Solution of the problem: A solution of the problem is a path from initial state to goal state. The movement from start states to goal states is guided by transition rules. Among all the solutions, whichever solution has least path cost is called optimal solution.
• —  Hence, it is evident that the method of solving problem through AI techniques involves the process of defining the search space, deciding about start and goal state and then finding a path from start state to goal state through search space. The movement from start state to goal state is guided by transition rules or production rules.

• —  Thus, to build an AI computational system to solve a particular problem the following activities are needed to be performed

1. Define the problem precisely: This definition must include precise specifications of initial states and final states of the problem.
2. Analyze the problem: This phase abstracts the salient features of the problem that can have an immense impact on the appropriateness of various possible techniques used for solving the problem.
3. Isolate and represent the task knowledge that is necessary to solve the problem.
4. Choose the best problem solving technique and apply it to the particular problem.

Problem Representation in AI

Before a solution can be found, the prime condition is that the problem must be very precisely defined. By defining it properly, one converts the abstract problem into real workable states that are really understood.

The most common methods of problem representation in AI are:-

• State Space Representation
• Problem Reduction

State Space Representation:  A set of all possible states for a given problem is known as the state space of the state space of the problem. Suppose you are asked to make a cup of coffee. What will you do? You will verify whether the necessary ingredients like instant coffee powder, milk powder, sugar, kettle, stove etc. are available.

If so, you will follow the following steps:

1.     Boil necessary water in the kettle.

2.     Take some of the boiled water in a cup add necessary amount of instant coffee powder to make decoction.

3.     Add milk powder to the remaining boiling water to make milk.

4.     Mix decoction and milk.

5.     Add sufficient quantity of sugar to your taste and the coffee is ready.

Now think a bit what has exactly happened. You started with the ingredients (initial state), followed a sequence of steps (called states) and at last had a cup of coffee (goal state). You added only needed amount of coffee powder, milk powder and sugar (operators). The following fig. shows the sequence:

Problem Reduction: In this method a complex problem is broken down or decomposed into a set of primitive sub problems. Solutions for these primitive sub-problems are easily obtained. The solutions for all the sub-problems collectively give the solution for the complex problem.

In fact, the human mind adopts this strategy for finding solutions to majority of problems it encounters.

For e.g. consider the activities that must be done to set right a punctured tyre.  The following fig. shows the activities. The top level specifies the overall goal which is combination of tasks given in level 2, level 3 and level 4 indicate primitive sub-problems.

The above fig. is actually a pictorial representation of the problem by an AND/OR tree. An arc connecting different branches is called an AND tree.

Between the complex and the sub-problem, there exist two kinds of relationships, viz. AND relationship and OR relationship.

In AND relationship, the solution for the problem is obtained by solving all the sub problems.

In OR relationship, the solution for the problem is obtained by solving any of the sub problems.

AI and Search Process

• —  Every AI program has to do the process of searching for the solution steps are not explicit in nature.
• —  This searching is needed for solution steps that are not known beforehand and have to be found out.
• —  Basically, to do a search process, the following are needed.

1. The Initial State description of the problem. For example, the initial positions of all pieces in the chess board.
2. A set of logical operators that change the state. In chess game, it is the rules of the game.
3. The final or the goal state. The final position that a problem solver has to reach in order to succeed.

Searching can be defined as a sequence of steps that transforms the initial state to the goal state.

The searching process in AI can be broadly classified into two major types:

1. Brute Force Search
2. Heuristic Search

Brute Force Search:- Brute force search is also known as Uninformed search or Blind search. These are commonly used search procedures which explore all the alternatives during the search process. They do not have any domain-specific knowledge. All they need are the initial state, the final state and a set of legal operators. It is a search methodology having no additional information about states beyond that provided in the problem definitions. In this search total search space is looked for the solution.

Very important brute force techniques are:

1.     Depth-First Search

2.     Breadth-First Search

Depth First Search

• —  In Depth-First Search, search begins by expanding the initial node, i.e., by using an operator, generate all successors of the initial node and test them
• —  Let us discuss the working of DFS with the help of the algorithm given below:

Algorithm for Depth-First Search

1. Put the initial node on the list of START.

2. If (START is empty) or (START = GOAL) terminate search.

3. Remove the first node from START. Call this node a.

4. If (a = GOAL) terminate search with success.

5. Else if node a has successors, generate all of them and add them at the beginning of START.

6. Go to step 2.

Search tree for Depth-first search 

—  In DFS the time complexity and space complexity are two important factors that must be considered. As the algorithm and Fig. shows, a goal would be reached early if it is on the left hand side of the tree.

—  The major drawback of Depth-First Search is the determination of the depth (cut-off depth) until which the search has to proceed. The value of cut-off depth is essential because otherwise the search will go on and on. If the cut-off depth is smaller, solution may not be found and if cut-off depth is large, time complexity will be more.

—  Time Complexity=O(b^d)

—  Space Complexity = O(d)

Breadth First Search

Breadth first search is also like depth first search. Here searching progresses level by level. Unlike depth first search, which goes deep into the tree. An operator is employed to generate all possible children of a node. Breadth first search being the brute force search generates all the nodes for identifying the goal.

Algorithm for Breadth-First Search

1. Put the initial node on the list of START.

2. If (START is empty) or (START = GOAL) terminate search.

3. Remove the first node from START. Call this node a.

4. If (a = GOAL) terminate search with success.

5. Else if node a has successors, generate all of them and add them at the tail of START.

6. Go to step 2.

Search tree for Breadth-first search

·        Time-complexity= O(b^d)

·        Space complexity= O(b^d)

The major problems of this search procedure are: -

·        Amount of time needed to generate all the nodes is considerable because of the time complexity.

·        Memory constraint is also a major hurdle because of space complexity.

The Searching process remembers all unwanted nodes, which is of no practical use for the search.

Lecture-3

Heuristic Search: Heuristic search is also known as guided search or informed search. These are search techniques where additional information about the problem is provided in order to guide the search in a specific direction.

Heuristics are approximations used to minimize the searching process. Generally, two categories of problems use heuristics.

1.     Problems for which no exact algorithms are known and one needs to find an approximate and satisfying solution. e.g. speech recognition.

2.     Problems for which exact solutions are known, but computationally infeasible e.g. Rubik’s Cube, Chess etc.

The heuristics which are needed for solving problems are generally represented as a heuristic function which maps the problem states into numbers. These numbers are then approximately used to guide search.

The following algorithms make use of heuristic evaluation functions:

Ø Hill Climbing

Ø Best-First Search

Ø A* Algorithm

Ø AO* Algorithm

Ø Beam Search

Ø Constraint Satisfaction

Hill Climbing: This algorithm, also called discrete optimization algorithm, uses a simple heuristic function viz., the amount of distance the node is from the goal.

The ordering of choices is a heuristic measure of the remaining distance one has to traverse to reach the goal node.

In fact, there is practically no difference between hill-climbing and depth-first search except that the children of the node that has been expanded are sorted by the remaining distance.

Algorithm for  Hill Climbing

1. Put the initial node on the list of START.

2. If (START is empty) or (START = GOAL) terminate search.

3. Remove the first node from START. Call this node a.

4. If (a = GOAL) terminate search with success.

5. Else if node a has successors, generate all of them. Find out how far they are from the goal node. Sort them by the remaining distance from the goal and add them to the beginning of START.

6. Go to step 2.

Search tree for hill-climbing procedure

Hill-climbing technique is being used in some activity or other in our day-to-day chore. Some of them are:-

1.     While listening to somebody playing flute on the transistor, tone and volume control are adjusted in a way that makes the music melodious.

2.     While tuning the carburettor of a scooter, the accelerator is raised to its maximum once and the carburettor is tuned so that the engine keeps on running for a considerably long period of time.

3.     An electronics expert, while making the transistor for the first time, tunes the radio set at mid-afternoon when the signal is weak for proper reception.

Problems of Hill Climbing Technique

Ø Local Maximum: A state that is better than all its neighbours but not so when compared to states that are farther away.

Ø Plateau: A flat area of the search space, in which all neighbours have the same value.

In order to overcome these problems, adopt one of the following or a combination of the following methods:

Ø Backtracking for local maximum. Backtracking helps in undoing what has been done so far and permits to try a totally different path to attain the global peak.

Ø A big jump is the solution to escape from the plateau. A huge jump is recommended because in a plateau all neighboring points have the same value.

Lecture-4

Best First Search:

This search procedure is an evaluation function variant of breadth first search. The heuristic function used here called an evaluation function is an indicator of how far the node is from the goal node. Goal nodes have an evaluation function value of zero. Best first search is explained using a search given in the following fig:

Algorithm for  Best First Search

1. Put the initial node on the list of START.

2. If (START is empty) or (START = GOAL) terminate search.

3. Remove the first node from START. Call this node a.

4. If (a = GOAL) terminate search with success.

5. Else if node a has successors, generate all of them. Find out how far they are from the goal node. Sort all the children generated so far by the remaining distance from the goal.

6. Name the list as START1.

7. Replace START with START1.

8. Go to step 2.

The paths found by best first search are likely to give solutions faster because it expands a node that seems closer to the goal.

Lecture-5

A* Algorithm:

In best first search, we brought in a heuristic value called evaluation function value. It is a value that estimates how far a particular node is from the goal. Apart from the evaluation function values, one can also bring in cost functions. Cost functions indicate how much resources like time, energy, money etc. have been spent in reaching a particular node from start. While evaluation function values deal with the future, cost function values deal with the past.

If it is possible for one to obtain the evaluation function values and the cost function values, then A* can be used.

The basic principle is that sum the cost and evaluation function values for a state to get its “goodness” worth & use this as a yardstick instead of the evaluation function value in best-first search. The sum of the evaluation value & the cost along the path leading to that state is called fitness number.

Now associated with each node are three numbers, the evaluation function, the cost function value & the fitness number.

The fitness number is the total of the evaluation function value and the cost function value.

e.g., consider node K, the fitness number is 20, which is obtained as follows:-

(Evaluation function of K) + (Cost function involved from Start node S to node K) =1+6+5+7+1=20.

While best first search uses the evaluation function value only for expanding the best node, A* uses the fitness number for its computation.

Algorithm for  A* Search

1. Put the initial node on the list of START.

2. If (START is empty) or (START = GOAL) terminate search.

3. Remove the first node from START. Call this node a.

4. If (a = GOAL) terminate search with success.

5. Else if node a has successors, generate all of them. Estimate the fitness number of the successors by totaling the evaluation function value & the cost function value. Sort the list by fitness number.

6. Name the list as START1.

7. Replace START with START1.

8. Go to step 2.

Beam Search:

This searching process is similar to breadth first search wherein searching proceeds level by level. At each level; heuristic functions are applied to reduce the number of paths to be explored. In fact, it is done to keep the width of the beam to be minimal. The width of the beam is fixed and whatever be the depth of the tree.

Let the width of the beam in the following fig. is 3

Algorithm for  Beam Search

1. Let width of beam=w

2. Put the initial node on the list of START.

3. If (START is empty) or (START = GOAL) terminate search.

4. Remove the first node from START. Call this node a.

5. If (a = GOAL) terminate search with success.

6. Else if node a has successors, generate all of them & add them at the tail of START.

7. Use a heuristic function to rank & sort all the elements of START.

8. Determine the nodes to be expanded. The no. of nodes should not be greater than w. Name these as START1.

9. Replace START with START1.

10. Go to step 2.

Lecture-6

AO* Algorithm

Problem Reduction (AND-OR Graph)

·        If we look just at the nodes and choose for expansion the one with the lowest ‘f’ value, we must select C.

·        But here in this case it is better to explore the path going through B. Since to use C we must also use D for a total cost of 9(C+D+2) compared to the cost of 6 that we get by going through B.

·        The most promising single node is G with an ‘f’ value of 3. It is even part of the most promising arc G-H, with a total cost of 9.

·        But that arc is not part of the current best path. Since to use it we must also use the arc I-J with a cost of 27.

·        The path from A through B to E & F is better, with a total cost of 18.

·        So we should not expand G next; rather we should examine either E or F.

FUTILITY: In order to describe an algorithm for searching an AND-OR graph we need to exploit a value that we call FUTILITY. If the estimated cost of a solution becomes greater than the value of FUTILITY, than we abandon search. FUTILITY should be chosen to correspond to a threshold such that any solution with a cost above is too expensive to be practical, even if it could ever be found.

Algorithm for  AO* Search

1. Initialize the graph to start node.

2. Traverse the graph following the current path accumulating nodes that have not yet been expanded or solved.

3. Pick any of these nodes & expand it and if it has no successors call this value FUTILITY otherwise calculate f for each of the successors.

4. If f is 0 then mark the node as solved.

5. Change the value of f for the newly created node to reflect its successors by back propagation.

6. Whenever possible use the most promising routes & if a node is marked as SOLVED then mark the parent node as SOLVED.

7. If starting node is SOLVED or value greater than FUTILITY, stop else repeat step 2.

Lecture-7

Production System

—  AI system developed for solution of any problem is called production system.

—  Once the problem is defined, analyzed and represented in a suitable formalism, the production system is used for application of rules and obtaining the solution.

A production system consists of following components:

1.     A set of production rules: which are of the form P—>Q. Each rule consists of a left hand side constituent that represents the current problem state and a right hand side that represents a result or generated output state. A rule is applicable if its left hand side matches with the current problem state. Thus, the left side of the rule determines the applicability of the rule and the right side that describes the output, if rule is applied. It is important to note that there may be multiple constituents on the left hand side of a rule (i.e. P1^P2^……Pn àQ). In this situation, all constituents of left hand side should be satisfied for applying the rule. After applying the rule, the left hand side of the rule becomes the current state.

2.     One or more knowledge/data bases: that contains all appropriate information for the particular task. Some parts of the database may be permanent while some part of this may pertain only to the solution of current problem. The information in these databases may be structured in an appropriate way.

3.     A control strategy: that specifies order in which the rules will be compared to the database of rules and a way of resolving the conflicts that arise when several rules match simultaneously.

4.     A rule applier: which checks the applicability of rule by matching the current state with the left hand side of the rule and finds the appropriate rule from the database of rules.

Salient Features of Production Rules

1.     Expressiveness and intuitiveness: In real world, many times a situation is encountered, which says if this happen- I will do this, if this is so-then this should happen. The production rules essentially tell us what to do in a given situation. This type of situation can be coded in ‘IF-THEN’ form of structures. The representing and coding of rules in IF-THEN type of structures is quite common   in AI applications and the rules of almost all types of expert systems and rule-based systems are coded in this way.

2.     Simplicity: The uniform structure of ‘IF-THEN-ELSE’ coding structure of rule based system provides simplicity in knowledge representation. This feature improves the readability of production rules and communication between various parts of a single program.

3.     Modularity and modifiability: Modularity means, production rules code the knowledge available in discrete pieces. In real world, the knowledge is available in discrete pieces hence, their coding in modular form suits very much. Information can be treated as a collection of independent facts which may be added or deleted from the system with essentially no side effects. Modifiability stands for the facility of modifying the rule.

4.     Knowledge Intensive: The knowledge base of production system stores extensive and pure knowledge. This part contains no control or programming information. The problem of semantics is resolved by representing knowledge in proper structure.

5.     Absence of Learning: The simple rule based production system does not store the results of computations for later use. Hence, it does not exhibit any type of learning capabilities.

6.     Opacity: Along with the advantages, there are certain disadvantages also associated with production systems. Opacity is the problem generated by combination of production rules. Though, the individual production rules may be models of clarity, the combined operation and effects of control program may be opaque. The opacity is generated because of less prioritization of rules.

7.     Inefficiency: Sometimes, several of the rules become active during execution. A well devised control strategy reduces this problem. As the rules of production system are large in number and they are hardly written in hierarchical manner, it requires exhaustive search through all the production rules for each cycle of control program. It makes the functioning efficient.

8.     Conflict Resolution: The rules in ideal production system should not have any type of conflict. The new rule whenever added in the database should ensure that it does not have any conflict with the existing rules. Besides this, there may be more than one number of rules that can be applied in one situation. While choosing the rule also the conflict should not happen. If conflict is found, it should be resolved in following ways:-

·        Assign priority to the rules and fire the rule with the highest priority.

·        Choose most recently used rule for firing.

Characteristics of Production System

v Data Structure: After defining the problem, it will be required to be represented in a suitable data structure. The data structures best suited for traditional AI problems are graphs and trees. Nodes in the graph correspond to problem state and arcs between nodes correspond to valid transitions, e.g. in an 8-puzzle problem, various different states derived from a single state will be put as children of that State. While searching for the solution, the graph sometimes needs to be converted into tree. There is a special type of tree represented called AND-OR graph which is used in AI problem.

Ø Control Strategies: These are also called search strategies. Control strategies are adopted for applying the rules and searching the problem solution in search space. The control strategy is responsible for obtaining the solution of the problem. Hence, if the wrong control strategy is applied, it may be possible that a solution is never obtained, even if it exists.

    The salient characteristics of control strategies are described below:

Ø The first requirement of good control strategy is that it should cause motion. It means that whenever we apply a rule the movement of the problem should be in the direction of obtaining the solution.

Ø It should be systematic. That means there should be systematic method to select a rule for application.

Water-Jug Problem: This problem is defined as: “ We are given two water jugs having no measuring marks on these. The capacities of jugs are 3 liter and 4 liter. It is required to fill the bigger jug with exactly 2 liter of water. The water can be filled in a jug from a tap.”

In this problem, the start state is that both jugs are empty and the final state is that 4 liter jug has exactly 2 liter of water.

The production rules involve filling a jug with some amount of water, filing the water from one jug to other or emptying the jug.

The search will be finding the sequence of production rules which transform the initial state to final state.

Partial Search tree of water jug problem

The state space for this problem can be described by set of ordered pairs of two variables (x, y) where, variable x represents the water in the 4 liter jug and y represents the water in the 3 liter jug. Variable x can take the value 0, 1, 2, 3, 4 and variable y can take the value 0,1,2,3.

The start state is (0, 0) and the goal state is (2, 0).

The production rules are formulated as follows:-

Rule 1: (x, y) -> (4, y)    (Fill the 4 liter jug)

Rule 2: (x, y) -> (x, 3)    (Fill the 3 liter jug)

Rule 3: (x, y) -> (x-x1, y) (Pour some water out from 4 liter jug)

Rule 4: (x, y) -> (x, y-x1)   (Pour some water out from 3 liter jug)

Rule 5: (x, y) -> (0, y)    (Empty the 4 liter jug)

Rule 6: (x, y) -> (x, 0)   (Empty the 3 liter jug)

Rule 7: (x, y) -> (4, y-(4-x)) (Fill the 4 liter jug by pouring some water from 3 liter jug)

Rule 8: (x, y) -> (x-(3-y), 3)   (Fill the 3 liter jug by pouring some water from 4 liter jug)

Rule 9:  (x, y) -> (x +y, 0)   (Empty 3 liter jug by pouring all its water in to 4 liter jug)

Rule 10: (x, y) -> (0, x +y)   (Empty 4 liter jug by pouring all its water in to 3 liter jug)

Rule 11: (0, 2) -> (2, 0) (Pour the 2 liters from 3 liter jug into 4 liter jug)

Rule 12: (2, y) -> (0, y)   (Empty the 2 liters in the 4 liter jug on the ground)

These are set of rules, which can be applied to solve water-jug problem. Solution of the problem will include applying appropriate rules in the specific sequence to transform the start state to goal state.

One solution is applying the rules in the sequence 2, 9, 2, 7, 5, 9. The solution is presented in the following table:-

Rule Applied	Water in 4 liter jug	Water in 3 liter jug
Start State	0	0
2	0	3
9	3	0
2	3	3
7	4	2
5	0	2
9	2	0

Artificial Intelligence Notes

Unit-1

Lecture-8

Constraint Satisfaction

Every one of us, in the real world works in an environment wherein there exist a lot of constraints. Even then solutions are found without violating the constraints.

Suggestive examples for constraint satisfaction are design problems in manufacturing, planning an optimal travel tour covering major tourist spots with minimal expense of resources.

Cryptarithmetic problems are typical constraint satisfaction problems.

To explain what a cryptarithmetic problem is, consider the following example:

     S    E    N    D
+  M   O    R    E

M O   N     E    Y

Here, the constraints are:

« All alphabets used are to have different numeric values.

« Since addition operation is involved, rules of addition are to be adhered to.

The solution is to find the values of the alphabets S, E, N, D, M, O, R, Y

Variables- S, E, N, D, M, O, R, Y

Domains-{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Solution is:

M=1

S=9

O=0

E=5

N=6

R=8

D=7

Y=2

Putting the values we get:

     9   5   6   7
+   1   0   8   5
 1  0   6   5   2

Applications of AI or AI-Related Fields

1.     Game Playing: - Games are fun. Partly may be because they challenge our ability to think. Even simple games like Tic-Tac-Toe or puzzles like eight puzzle are challenging to children. More complex games like checkers, chess, bridge etc. are difficult enough that it takes years for gifted adults to master them. Nearly all games require seeing patterns, making plans, searching combinations, judging alternative moves and learning from experience, all being skills which are also involved in many daily tasks. So game playing has become one of the research areas of AI. We can buy machines that can play master level chess for a few hundred dollars.

e.g. Deep Blue, a chess computer built by IBM researcher, defeated world champion Gary Kasparov in a landmark performance.

2.     Natural Language Understanding: Natural Language Processing (NLP) is a subfield of AI. Natural language understanding is devoted to, making computers “understand” statements written in human languages. In NLP a range of computational techniques are used for analyzing and representing naturally occurring text during analysis (e.g. morphological, syntactic, semantic, and pragmatic). This is done for the purpose of achieving human like language processing for knowledge intensive applications. Just getting a sequence of words into a computer is not enough. Parsing sentences is not enough either. In general the user may communicate with the system by speaking or by typing. Understanding spoken language is much harder than understanding typed language- our input is just the raw speech signals.

3.     Robotics: - Robotics is a field of AI which enhances the ability to move and act in the world, possibly responding to new perceptions. An AI application is in simple terms a system that possesses knowledge about an application domain, takes in data from its environment and reasons about these data to derive information. This information is then used to make decisions and act. Often a human will make the decision and perform the action but technology is developing so that more of this responsibility resides in the machine. The central hypothesis of traditional AI, known as the physical symbol system hypothesis, is that any facet of human intelligence can be understood and described precisely enough for a machine to simulate it.

4.     Pattern Recognition: Pattern recognition is the act of taking in raw data and taking an action based on the   category of the data. Most research in pattern recognition is about methods for supervised learning and unsupervised learning. Pattern recognition aims to classify data (patterns) based either on a priori knowledge or on statistical information extracted from the patterns.

Artificial Intelligence Notes

Unit-1

Lecture-9

Major Components of an AI System

Characteristics of AI Programs

« AI programs manipulate symbolic information to a larger extent, in contrast to conventional programs, which deal with numeric processing.

« In order to classify a system as an AI program, the fundamental criteria is that it must have vast quantities of knowledge and the knowledge must be represented in such a form that the system working on it can easily manipulate it.

« AI programs deal with real life problems to a large extent. These assist humans in taking right decisions. Just as a human expert has the capacity to handle uncertain, incomplete and irrelevant information, AI system must also have it.

« A very vital characteristic of an AI program is its ability to learn. An amateur in a field becomes a professional gradually by learning the intricacies of the domain of work. Learning is an essential feature which present-day system has not succeeded to a level of competence.

Importance of Artificial Intelligence

« Artificial Intelligent machines can replace human beings in some specific jobs for e.g. in business stores and household day to day activities and will help to sort out the manpower problem.

« By applying AI in machines, it can help in hospitals, providing food and medicines where human being feared to be attacked by such diseases. Robotics is a good example.

« Through AI we can send the machines in bad circumstances where we cannot afford to send a human being due to the fear of causalities and can take feedback.

« With the help of AI we can manage wireless applications and securities.

« By applying  AI to the databases we can make our data warehousing and data mining techniques more useful