Artificial Intelligence

Download

UNIT 1

 

1.1Definition

It is the science and engineering of making intelligent machines, especially intelligent computer programs. It is related to the similar task of using computers to understand human intelligence, but AI does not have to confine itself to methods that are biologically observable.

It is the study of how to make computers do things which at the moment people do better. It fails to include some areas of potentially large impact namely problems that cannot now be solved well by either computers or people.

It is the automation of activities that we associate with human thinking, activities such as decision making, problem solving, learning .

Intelligence +System à AI

 

 

Applications of AI

AI currently encompasses a huge variety of subfields, ranging from general purpose areas such as learning and perception to such specific tasks as playing chess, proving mathematical theorems, writing poetry and diagnosing diseases.

Main application areas are:

1. Game playing

You can buy machines that can play master level chess for a few hundred dollars. There is some AI in them, but they play well against people mainly through brute force computation--looking at hundreds of thousands of positions. To beat a world champion by brute force and known reliable heuristics requires being able to look at 200 million positions per second.

2. Speech recognition

In the 1990s, computer speech recognition reached a practical level for limited purposes. Thus United Airlines has replaced its keyboard tree for flight information by a system using speech recognition of flight numbers and city names. It is quite convenient. On the other hand, while it is possible to instruct some computers using speech, most users have gone back to the keyboard and the mouse as still more convenient.

3. Understanding natural language

Just getting a sequence of words into a computer is not enough. Parsing sentences is not enough either. The computer has to be provided with an understanding of the domain the text is about, and this is presently possible only for very limited domains.

4. Computer vision

The world is composed of three-dimensional objects, but the inputs to the human eye and computers' TV cameras are two dimensional. Some useful programs can work solely in two dimensions, but full computer vision requires partial three-dimensional information that is not just a set of two-dimensional views. At present there are only limited ways of representing three-dimensional information directly, and they are not as good as what humans evidently use.

5. Expert systems

A ``knowledge engineer'' interviews experts in a certain domain and tries to embody their knowledge in a computer program for carrying out some task. How well this works depends on whether the intellectual mechanisms required for the task are within the present state of AI. When this turned out not to be so, there were many disappointing results. One of the first expert systems was MYCIN in 1974, which diagnosed bacterial infections of the blood and suggested treatments. It did better than medical students or practicing doctors, provided its limitations were observed. Namely, its ontology included bacteria, symptoms, and treatments and did not include patients, doctors, hospitals, death, recovery, and events occurring in time. Its interactions depended on a single patient being considered. Since the experts consulted by the knowledge engineers knew about patients, doctors, death, recovery, etc., it is clear that the knowledge engineers forced what the experts told them into a predetermined framework. In the present state of AI, this has to be true. The usefulness of current expert systems depends on their users having common sense.

6. Heuristic classification

One of the most feasible kinds of expert system given the present knowledge of AI is to put some information in one of a fixed set of categories using several sources of information. An example is advising whether to accept a proposed credit card purchase. Information is available about the owner of the credit card, his record of payment and also about the item he is buying and about the establishment from which he is buying it (e.g., about whether there have been previous credit card frauds at this establishment).

7. Commonsense reasoning

It is the branch of Artificial intelligence concerned with replicating human thinking. In theory, if the computer is endowed with good Knowledge Representation Database, including a comprehensive common sense database, and is able to process and respond in plain-text English, it will have the ability to process and reason with English texts. The task of Common Sense Knowledge is probably the least studied area, though it is included in many ways in knowledge representation task. There are two issues with this ,one is how to represent the knowledge gathered in a computer processible, and human accessible way. The second task is actually collecting the Common Sense knowledge. There are a couple of different groups who are doing this now. Knowledge Gathering is usually done for expert systems and is limited in its breadth to a limited domain. The two common sense projects are Open Mind Common Sense and Cycorp. To investigate this sort of problems General Problem Solver was developed.

1.2 Problem and Problem Spaces

State space search is a powerful technique for solving problems. However, in order to apply this technique we need to formulate the problem. A problem can be defined formally by 4 components:

• Initial state :- Specify one or more states within that space that describe possible situations from which the problem solving process may start. These states are called the initial sates.
• Successor function S(x) :- Description of all possible actions available. Given a particular state x, S(x) returns a set of < action, successor> ordered pairs in which each action is one of the legal actions in state x and each successor is a state that can be reached from x  by applying the action.
• Goal Test :– Goal states are one or more states that would be acceptable as solutions to the problem. Goal test determines whether a given state is a goal  state. They may or may not be explicitly specified.
• Path cost  :- Function that assigns a numeric cost to a path. It is usually the sum of the costs of individual actions along the path. Step cost of taking action ‘a’ to go from state ‘x’ to ‘y’ is denoted by c(x,a,y).

Problem Space is the environment in which search takes place. Problem Instance is the problem space combined with initial and goal state.

State space is the set of all states reachable from the initial state.(initial state + successor function).State space forms a graph in which nodes are states and the arcs between nodes are actions. A path in state space is a sequence of states connected by a sequence of actions.

A solution is a sequence of actions (path) leading from the initial state to a goal state. Solution quality is measured by the path cost function. An Optimal solution has the lowest path cost among all solutions.

 

Example Problems

1. 8 Puzzle

The eight puzzle consists of a three by three board with eight numbered tiles and a blank space. A tile adjacent to the blank space can slide into the space. A game consists of a starting position and a specified goal position. The goal is to transform the starting position into the goal position by sliding the tiles around. The object is to figure out the steps needed to get from one configuration of the tiles to another.

Arrange the tiles so that all the tiles are in the correct positions. You do this by moving tiles.  You can move a tile up, down, left, or right, so long as the following conditions are met:
A) there's no other tile blocking you in the direction of the movement; and

 B) you're not trying to move outside of the boundaries/edges. 

The 8-puzzle - also known as the sliding-block/tile-puzzle - is one of the most popular instrument in the artificial intelligence (AI) studies. It belongs to AI exercises commonly referred as toy-problems.

For example, suppose we wanted to get from the initial state to the goal state given below.

   Initial state:                             Goal state:                                       

                       

and the is a blank tile you can slide around. This 8 puzzle instance can be solved in 5 steps.

1. States – A state description specifies the location of each of the eight tiles and the blank in one of the nine squares.

2. Initial state – Any state can be designated as the initial state. Any given goal can be reached from exactly half of the possible initial states.

3. Successor function. – generates the legal states that result from trying the four actions(blank moves left, right, up, down).

4. Goal test – this checks whether the state matches the goal configuration.

5. Path cost -  Number of actions to reach goal.

 

2.  8-Queens Problem

The goal of 8-queens problem is to place 8 queens on a 8 by 8 chess board so that no queen can attack any other queen. A queen attacks another if they are in the same row either vertically, horizontally, or diagonally.

If we want to find a single solution, it is not difficult. If we want to find all possible solutions, the problem is difficult and backtrack method is the only known method. For 8-queen, we have 92 solutions. If we exclude symmetry, there are 12 solutions.

One Solution to the 8-Queens Problem:

7			X
6					X
5		X
4								X
3	X
2							X
1				X
0						X
	0	1	2	3	4	5	6	7

Although efficient special purpose algorithms exist for this problem and the whole ‘n’ queens family, it remains an interesting test problem for search algorithms. There are 2 main kinds of formulation.

1.Incremental formulation – involves operators that augment the state description starting with an empty state , ie each action adds a queen to the board.

2.Complete-state formulation – starts with all 8 queens on the board and moves them abroad.

In either case the path cost is of no interest because only the final state counts.

For eg: Incremental formulation

  1. States - Any arrangement of 0 to 8 queens on the board

  2. Initial state -  No queens on the board

  3. Successor function - Add a queen to any empty square

  4. Goal test -  8 queens on board and none attacked

There are 3 x 10¹⁴  possible sequences to investigate

3. Water-Jug Problem

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

The State Space for this problem can be described as a set of Ordered pairs of integers (x, y) such that x = 0, 1, 2, 3, or 4 and y = 0, 1, 2 , or 3; x represents the number of gallons of water in the 4-gallon jug and y represents  the number of gallons of water in the 3-gallon jug.

The Start State is (0, 0).The Goal States are (2, 0), (2, 1), (2, 2), (2, 3).The actions include :

1)      fill either jug with water

2)      empty either jug

3)      pour water from 4-gallon jug to 3-gallon jug

4)      pour water from 3-gallon jug to 4-gallon jug

4. Towers of Hanoi

There are three posts 1, 2, and 3. One of which, say post 1, has ‘n’ disks on it in ascending size. The Problem is: How to transfer all disks from the post 1 to post 2, keeping the order of ascending size. Each time only one disk can be moved. Post 2 is used for the intermediate storage

A good example of a problem solving domain is the "Tower of Hanoi" puzzle. This puzzle involves a set of three rings of different sizes that can be placed on three different pegs, like so:

The goal of this puzzle is start with the rings arranged as shown above, and to move them all to this configuration:

Only the top ring on a peg can be moved, and it may only be placed on a smaller ring, or on an empty peg. For the Tower of Hanoi, the problem space is the set of all possible configurations of rings on the pegs. Some of the configurations or states in the space are given special interpretations:

Initial States

           States where a given episode of problem solving starts. In the Tower of Hanoi puzzle, there is one initial state, as shown above. In other domains there may be a number of possible initial states.

Goal or Solution States
            States that are considered solutions to the problem. Again, the Tower of Hanoi problem has a single solution state, but usually there are a number of states that count as solutions.

Failure or Impossible States

          In some domains, there are states with the property that if they are ever encountered, the problem solving is considered a failure. In the Tower of Hanoi domain, one might define failure states as any in which the rule that rings can only be placed on bigger rings is violated

Real World Problems

1. Route finding problem

Route finding problem is defined in terms of specified locations and transitions along links between them. Route finding algorithms are used in a variety of applications such as routing in computer networks, military operations planning and airline travel planning system. These problems are typically complex to explain.

2. Travelling salesman problem

This is also a Route finding problem. A salesperson has to visit a number of cities. (S)He can start at any city and must finish at that same city. The salesperson must visit each city only once. A simple control structure could in principle solve the problem. It would simply explore all possible paths in the tree and return the one with the shortest length. This approach will work for very short list of cities. But it breaks down quickly as the no of cities grows.

If there are n cities then the number of possible paths among them is 1*2*3*4………*(n-1) or (n-1)! .The time required to examine a single path is proportional to n!. Assume there are 35 cities to visit. To solve this problem he would take more time than he would be willing to send. This phenomenon is called combinatorial explosion.

We can beat this using a simple strategy called Branch and bound. Begin generating complete paths keeping track of the shortest path found so far. Give up exploring any path as soon as its partial length becomes greater than the shortest path found so far. Using this technique we are still guaranteed to find the shortest path. Although this algorithm is efficient than the first one it still requires exponential time.

3. VLSI layout

A VLSI layout problem requires positioning millions of components and connections on a chip to minimize area, minimize circuit delay and maximize manufacturing yield. The layout problem comes after the logical design phase and is usually split into 2 parts : cell layout and channel routing. The aim is to place the cells on the chip so that they do not overlap and so that there is room for the connecting wires to be placed between the cells. Channel routing finds a specific route for each wire through the gaps between the cells.

4. Robot Navigation

It is a generalization of route problem. Rather than a discrete set of routes, a robot can move in a continuous space with an infinite set of possible actions and states. When robot has arms and legs or wheel that must also be controlled, the search space becomes multi-dimensional.

1.3  Problem Characteristics

To build a system to solve a particular problem we need to do 4 things.

1)      Define the problem precisely. The definition must include precise specifications of what the initial situations will be as well as what final situations constitute acceptable solutions to the problem.

2)      Analyse 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.

In order to choose an appropriate method for a particular problem it is necessary to analyze the problem along several key dimensions as:

•      Is the problem decomposable?

•      Can solution steps be ignored or undone?

•      Is the universe predictable?

•      Is a good solution absolute or relative?

•      Is the solution a state or a path?

•      What is the role of knowledge?

•      Does the task require human-interaction?

1. Is the problem decomposable?

Suppose we want to solve the problem of computing the expression:

 ò(x2 + 3x + sin2x.cos2x)dx

We can solve this problem by breaking down it into 3 smaller problems each of which we can be solved independently. Decomposable problem can be solved easily. This can be solved by a simple integration program that works as follows. At each step it checks to see whether the problem it is working on is immediately solvable. If so then the answer is returned directly. If the problem is not easily solvable, the integrator checks to see whether it can decompose the problem into smaller problems. If it can it creates those problems and calls itself recursively on them. The problem tree is shown below:

2. Can solution steps be ignored or undone?

                                                                                                                                           

           

In attempting to solve the 8-Puzzle we might make a stupid move. For eg in the game shown above we might start by sliding tile 5 into the empty space. Having done that we cannot change our mind and immediately slide tile 6 into the empty space since the empty space will essentially have moved. But we can backtrack and undo the first move sliding tile 5 back to where it was. Then we can move tile 6.

An additional step must be performed to undo each incorrect step, whereas no action was required to undo a useless lemma. In addition the control mechanism for an 8-Puzzle solver must keep track of the order in which operations are performed so that the operations can be undone one at a time if necessary.

Problem Classification

1)      Ignorable problems  - in which solution steps can be ignored. For eg in the case of Theorem Proving a lemma that has been proved can be ignored for next steps. Ignorable problems can be solved using a simple control structure that never backtracks. Such a control structure is easy to implement.

2)      Recoverable problems   - in which solution steps can be undone and backtracked. Eg :8- Puzzle. Recoverable problems can be solved by a slightly more complicated control strategy that does sometimes make mistakes. Backtracking will be necessary to recover from such mistakes, so the control structure must be implemented using a pushdown stack in which decisions are recorded in case they need to be undone.

3)      Irrecoverable problems   - in which moves cannot be retracted. Eg : Playing Chess. They will need to be solved by a system that expends a great deal of effort making each decision since the decision must be final. Irrecoverable problems can be solved by recoverable style methods via planning.

3.  Is the universe predictable?

In 8-Puzzle it is possible to plan an entire sequence of moves and be confident that we know what the resulting state will be. These are called certain outcome problems. For certain-outcome problems, planning can used to generate a sequence of operators that is guaranteed to lead to a solution.

In Bridge we cannot know exactly where all the cards are or what the other players will do on their turns. What we would like to do is to plan the entire hand before making the first play. These problems are called uncertain outcome problems. For uncertain-outcome problems, a sequence of generated operators can only have a good probability of leading to a solution.

           

Plan revision is made as the plan is carried out and the necessary feedback is provided. One of the hardest types of problems to solve is the irrecoverable uncertain outcome. Eg : controlling a robot arm.

4. Is a good solution absolute or relative?

Different reasoning paths lead to the answer. It does not matter which path we follow. For eg in the case of travelling Salesman Problem we have to try all paths to find the shortest one. Any-path problems can be solved in a reasonable amount of time using heuristics that suggest good paths to explore. If the heuristics are not perfect the search for the solution may not be as directly as possible. For best-path problems, much more exhaustive search will be performed. Best –path problems are computationally harder than any – path problems.

5. Is the solution a state or a path?

In the case of water Jug Problem solution is a path to the state. The path that leads to the goal must be reported. But in the case of natural language understanding solution is a state in the world. At one level this difference can be ignored and all problems can be formulated as ones in which only a state is required to be reported. A path-solution problem can be reformulated as a state-solution problem by describing a state as a partial path to a solution. The question is whether that is natural or not.

Download

****Further Reading Please download  the document from the above link***