The Missionaries and Cannibals Problem.

The Missionaries and Cannibals Problem Statement

Three missionaries and three cannibals find themselves on one side of a river. They have would like to get to the other side. But the missionaries are not sure what else the cannibals agreed to. So the missionaries managed the trip across the river in such a way that the number of missionaries on either side of the river is never less than the number of cannibals who are on the same side. The only boar available holds only two at a time. How can everyone get across the river without the missionaries risking being eaten?

Solution:-

The state for this problem can be defined as

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

where i represents the number missionaries in one side of a river . j represents the number of cannibals in the same side of river. The initial state is (3,3), that is three missionaries and three cannibals one side of a river , (Bank 1) and ( 0,0) on another side of the river (bank 2) . the goal state is to get (3,3) at bank 2 and (0,0) at bank 1.

To sole this problem we will make the following assumptions:

1. Number of cannibals should lesser than the missionaries on either side.

2. Only one boat is available to travel.

3. Only one or maximum of two people can go in the boat at a time.

4. All the six have to cross the river from bank.

5. There is no restriction on the number of trips that can be made to reach of the goal.

6. Both the missionaries and cannibals can row the boat.

This kind of problem is often solved by a graph search method. Represent the problem as a set of states which are snapshots of the world and operators which transform one state into another state are mapped to nodes of the graph and operators are the edges of the graph. The following procedure shows the graph search algorithm in PROLOG, for Missionaries and Cannibals Problem.

Path finding.

* Write a program to find path from one node to another.

* Must avoid cycles

* A template for the clause is

path(start, Finish, Visited, Path).
Start - the name of the starting node.
Finish - the name of the finishing node.
Visited - the list of nodes aready visited.
Path - the list of nodes on the path, including Start and Finish.

Program for finding a Path.

* The search for a path terminates when we have nowhere t0o go.

path {Node, Node,.., [Node]}

A path from start to Finish, starts with a node, X,connected to start followed by a path from X to Finish.

path (Start, Finish, Visited, {Start [ Path]} :-
edge (Start,X),
not (member( X,Visited)),
path(x,Finish, {X [vISITED],Path)
member (X,[X I_ I).
member (X,I_ IYI):- member(X,Y).

Representing the state.

Now we returen to the peoblem or rrepresenting tyhe missionaries and cannibals problem;
*A State is one "snapshot" in time.

*For this problem the only infoemation we need to fully characterize the state is :
*the number of missionaries on the left bank,
*the number of cannibals on the left bank,
*the side the boat is on.

All other information can be deduced from these thres items.

In PROLOG, the state can be representted by a 3-arity term, state (Missionaries,Cannibals, State).

Representing the solution.

*The solution consists of a list of moves, e.g.
[move( I.I. right), move 2.0, lift)].
*We take this to mean that I missionary and i cannibal moved to the right bank, then 2
missionaries moved to hte left bank.
*Like the graph search problem, we must avoid returing to state we have visited before.
The visited list will have the form:
[Most Recent State I list of previousstates]

Overview of solution.

We follow a simple graph search procedure:

*Start from an initial state
*Find a neighbouring state
*Check that the now stae has not been visited before
*Find a path from the neighbour to the goal.

The search terminates when we have found the state:

state(0, 0, right).

PROLOG Code.

% mandc(CurrentState, Visited, Path)

mandc(start(0, 0, right), -,[]).
mande(Currentstate, visited,[Move I Rest O fMoves]):-
newstate (Current state, NestState, Move).
not (member(NestState,Visited)0,
make., move(Current state, NestState, Move),
mande((Nextstate I visited,[Move I Rest O fMoves])

make_move (state(M1,C1,left) state (M2,C2,right) move(M,C,right)) :-
M is M1 - M2.
C is C1 - C2.

make_move(state(M1,C1,right),state(M2,C2,right),move M,C,left)) :-
M is M2 -M1
C is C2 - C1.

A move is characterized by the nummber of missionar5ies and the number of canniblls taken in the boal at6 one time.

Since the boat can carry no more than two peopel at once, the only possible combinations are:
carry (2,0)
carry (1,0)
carry (1,1)
carry (0,1)
carry (0,2).
Where carry (M,C) means the boat will carry M, missionaries and C.cannibals on one trip.

Feasible Moves

*Once we hafe found a possible move, we have to confirm that it is feasible It is not feasible to move more missionaries or more cannibals than that are present on one bank.
When the stae is stae(M1,C1,left) and we try carry (M,C)then

M ≤ M1 and C ≥ C1

must be true.

*When the state is state(M1, C1, left) and we try carry (M,C) then

M + M1 ≤ AND C + C1 ≤ 3

must be true.

Legal Moves.

* Once we have found a feasible move, we must check that it is legal, i.e no Missionaries must be eaten.

legal(X,X).

legal(3,X).

legal(O,X).

*The only safe combinations are when there are equal numbers of Missionaries and cannibals or all the Missionaries are on one side.

Generating the Next State.

newstate(state(M1,C1,left), state(M2,C2,right)):-

carry(M,C),

M ≤ M1

C ≤ C1

M2 is M1 - M2,

C2 is C1 - C,

legal(M2,C2)

newstate(M1, C1, right), state(M2, C2, left)):-

carry(M,C),

M2 is M1 + M,

C2 is C1 + C,

M2 ≤ 3,

C2 ≤ 3,

legal(M2, C2)

What is Production System .? Types., Characterstics.

Artificial Intelligence is the study of how to make computers do things at which at the movement people are better. - Its main aim is depend upon the situation to take the decisions automatically. - AI is the scientific research, this research will begin from past 30 years , its origin is JAPAN. - AI is the part of the Computer Science Concerned with designing, intelligent computer systems, that is systems that exhibits the characteristics we associate with intelligence in Human Behavior. Once again this definition will raise the following question. “Intelligent Behavior “, in view of the difficulty in defining the Intelligence, Let us try to characteristics that is a list of number of characteristics by which we can identify the Human Intelligence . - In AI problems that appear very little common, there are appropriate Techniques to solve these problems are called AI Techniques. A Production System is best suited AI Technique to solve the State Space Problems like Water Jug, and Missionaries and Cannibals. these problems consists of State, State Space and Goal State. State = Initial state of the Problem. State space = Intermediate States between Initial State and Goal State. Goal State = Final state of the problem. - to solve state space problems Production System is best suited AI Technique. A production system consists of rules and factors. Knowledge is encoded in a declarative from which comprises of a set of rules of the form and Control strategy. PRODUCTION SYSTEM SITUATION that implies ACTION. Example:- IF the initial state is a goal state THEN quit. The major components of an AI production system are i. A global database ii. A set of production rules and iii. A control system The goal database is the central data structure used by an AI production system. The production system. The production rules operate on the global database. Each rule has a precondition that is either satisfied or not by the database. If the precondition is satisfied, the rule can be applied. Application of the rule changes the database. The control system chooses which applicable rule should be applied and ceases computation when a termination condition on the database is satisfied. If several rules are to fire at the same time, the control system resolves the conflicts. Four classes of production systems:- 1. A monotonic production system 2. A non monotonic production system 3. A partially commutative production system 4. A commutative production system. Advantages of production systems:- 1. Production systems provide an excellent tool for structuring AI programs. 2. Production Systems are highly modular because the individual rules can be added, removed or modified independently. 3. The production rules are expressed in a natural form, so the statements contained in the knowledge base should the a recording of an expert thinking out loud. Disadvantages of Production Systems:-One important disadvantage is the fact that it may be very difficult analyse the flow of control within a production system because the individual rules don’t call each other. Production systems describe the operations that can be performed in a search for a solution to the problem. They can be classified as follows. Monotonic production system :- A system in which the application of a rule never prevents the later application of another rule, that could have also been applied at the time the first rule was selected. Partially commutative production system:- A production system in which the application of a particular sequence of rules transforms state X into state Y, then any permutation of those rules that is allowable also transforms state x into state Y. Theorem proving falls under monotonic partially communicative system. Blocks world and 8 puzzle problems like chemical analysis and synthesis come under monotonic, not partially commutative systems. Playing the game of bridge comes under non monotonic , not partially commutative system. For any problem, several production systems exist. Some will be efficient than others. Though it may seem that there is no relationship between kinds of problems and kinds of production systems, in practice there is a definite relationship. Partially commutative , monotonic production systems are useful for solving ignorable problems. These systems are important for man implementation standpoint because they can be implemented without the ability to backtrack to previous states, when it is discovered that an incorrect path was followed. Such systems increase the efficiency since it is not necessary to keep track of the changes made in the search process. Monotonic partially commutative systems are useful for problems in which changes occur but can be reversed and in which the order of operation is not critical (ex: 8 puzzle problem). Production systems that are not partially commutative are useful for many problems in which irreversible changes occur, such as chemical analysis. When dealing with such systems, the order in which operations are performed is very important and hence correct decisions have to be made at the first time itself.

Artificial Intelligence Short Questions.

The term artificial intelligence was first coined in 1956, at the Dartmouth conference, and since then Artificial Intelligence has expanded because of the theories and principles developed by its dedicated researchers.

Q. What is artificial intelligence?

A. 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.

Q. Yes, but what is intelligence?

A. Intelligence is the computational part of the ability to achieve goals in the world. Varying kinds and degrees of intelligence occur in people, many animals and some machines.

Q. Isn't there a solid definition of intelligence that doesn't depend on relating it

to human intelligence?

A. Not yet. The problem is that we cannot yet characterize in general what kinds of computational procedures we want to call intelligent. We understand some of the mechanisms of intelligence and not others.

Q. Is intelligence a single thing so that one can ask a yes or no question ``Is this machine intelligent or not?''?

A. No. Intelligence involves mechanisms, and AI research has discovered how to make computers carry out some of them and not others. If doing a task requires only mechanisms that are well understood today, computer programs can give very impressive performances on these tasks. Such programs should be considered ``somewhat intelligent''.

Q. Isn't AI about simulating human intelligence?

A. Sometimes but not always or even usually. On the one hand, we can learn something about how to make machines solve problems by observing other people or just by observing our own methods. On the other hand, most work in AI involves studying the problems the world presents to intelligence rather than studying people or animals. AI researchers are free to use methods that are not observed in people or that involve much more computing than people can do.

Q. What about IQ? Do computer programs have IQs?

A. No. IQ is based on the rates at which intelligence develops in children. It is the ratio of the age at which a child normally makes a certain score to the child's age. The scale is extended to adults in a suitable way. IQ correlates well with various measures of success or failure in life, but making computers that can score high on IQ tests would be weakly correlated with their usefulness. For example, the ability of a child to repeat back a long sequence of digits correlates well with other intellectual abilities, perhaps because it measures how much information the child can compute with at once. However, ``digit span'' is trivial for even extremely limited computers.

However, some of the problems on IQ tests are useful challenges for AI.

Q. What about other comparisons between human and computer intelligence?

A.Arthur R. Jensen [Jen98], a leading researcher in human intelligence, suggests ``as a heuristic hypothesis'' that all normal humans have the same intellectual mechanisms and that differences in intelligence are related to ``quantitative biochemical and physiological conditions''. I see them as speed, short term memory, and the ability to form accurate and retrievable long term memories.

Whether or not Jensen is right about human intelligence, the situation in AI today is the reverse.

Computer programs have plenty of speed and memory but their abilities correspond to the intellectual mechanisms that program designers understand well enough to put in programs. Some abilities that children normally don't develop till they are teenagers may be in, and some abilities possessed by two year olds are still out. The matter is further complicated by the fact that the cognitive sciences still have not succeeded in determining exactly what the human abilities are. Very likely the organization of the intellectual mechanisms for AI can usefully be different from that in people.

Whenever people do better than computers on some task or computers use a lot of computation to do as well as people, this demonstrates that the program designers lack understanding of the intellectual mechanisms required to do the task efficiently.

Q. When did AI research start?

A. After WWII, a number of people independently started to work on intelligent machines. The English mathematician Alan Turing may have been the first. He gave a lecture on it in 1947. He also may have been the first to decide that AI was best researched by programming computers rather than by building machines. By the late 1950s, there were many researchers on AI, and most of them were basing their work on programming computers.

Q. Does AI aim to put the human mind into the computer?

A. Some researchers say they have that objective, but maybe they are using the phrase metaphorically. The human mind has a lot of peculiarities, and I'm not sure anyone is serious about imitating all of them.

Q. What is the Turing test?

A. Alan Turing's 1950 article Computing Machinery and Intelligence [Tur50] discussed conditions for considering a machine to be intelligent. He argued that if the machine could successfully pretend to be human to a knowledgeable observer then you certainly should consider it intelligent. This test would satisfy most people but not all philosophers. The observer could interact with the machine and a human by teletype (to avoid requiring that the machine imitate the appearance or voice of the person), and the human would try to persuade the observer that it was human and the machine would try to fool the observer.

The Turing test is a one-sided test. A machine that passes the test should certainly be considered intelligent, but a machine could still be considered intelligent without knowing enough about humans to imitate a human.

Daniel Dennett's book Brainchildren has an excellent discussion of the Turing test and the various partial Turing tests that have been implemented, i.e. with restrictions on the observer's knowledge of AI and the subject matter of questioning. It turns out that some people are easily led into believing that a rather dumb program is intelligent.

Q. Does AI aim at human-level intelligence?

A. Yes. The ultimate effort is to make computer programs that can solve problems and achieve goals in the world as well as humans. However, many people involved in particular research areas are much less ambitious.

Q. How far is AI from reaching human-level intelligence? When will it happen?

A. A few people think that human-level intelligence can be achieved by writing large numbers of programs of the kind people are now writing and assembling vast knowledge bases of facts in the languages now used for expressing knowledge.

However, most AI researchers believe that new fundamental ideas are required, and therefore it cannot be predicted when human-level intelligence will be achieved.

Q. Are computers the right kind of machine to be made intelligent?

A. Computers can be programmed to simulate any kind of machine.

Many researchers invented non-computer machines, hoping that they would be intelligent in different ways than the computer programs could be. However, they usually simulate their invented machines on a computer and come to doubt that the new machine is worth building. Because many billions of dollars that have been spent in making computers faster and faster, another kind of machine would have to be very fast to perform better than a program on a computer simulating the machine.

Q. Are computers fast enough to be intelligent?

A. Some people think much faster computers are required as well as new ideas. My own opinion is that the computers of 30 years ago were fast enough if only we knew how to program them. Of course, quite apart from the ambitions of AI researchers, computers will keep getting faster.

Q. What about parallel machines?

A. Machines with many processors are much faster than single processors can be. Parallelism itself presents no advantages, and parallel machines are somewhat awkward to program. When extreme speed is required, it is necessary to face this awkwardness.

Q. What about making a ``child machine'' that could improve by reading and by learning from experience?

A. This idea has been proposed many times, starting in the 1940s. Eventually, it will be made to work. However, AI programs haven't yet reached the level of being able to learn much of what a child learns from physical experience. Nor do present programs understand language well enough to learn much by reading.

Q. Might an AI system be able to bootstrap itself to higher and higher level intelligence by thinking about AI?

A. I think yes, but we aren't yet at a level of AI at which this process can begin.

Q. What about chess?

A. Alexander Kronrod, a Russian AI researcher, said ``Chess is the Drosophila of AI.'' He was making an analogy with geneticists' use of that fruit fly to study inheritance. Playing chess requires certain intellectual mechanisms and not others. Chess programs now play at grandmaster level, but they do it with limited intellectual mechanisms compared to those used by a human chess player, substituting large amounts of computation for understanding. Once we understand these mechanisms better, we can build human-level chess programs that do far less computation than do present programs.

Unfortunately, the competitive and commercial aspects of making computers play chess have taken precedence over using chess as a scientific domain. It is as if the geneticists after 1910 had organized fruit fly races and concentrated their efforts on breeding fruit flies that could win these races.

Q. What about Go?

A. The Chinese and Japanese game of Go is also a board game in which the players take turns moving. Go exposes the weakness of our present understanding of the intellectual mechanisms involved in human game playing. Go programs are very bad players, in spite of considerable effort (not as much as for chess). The problem seems to be that a position in Go has to be divided mentally into a collection of subpositions which are first analyzed separately followed by an analysis of their interaction. Humans use this in chess also, but chess programs consider the position as a whole. Chess programs compensate for the lack of this intellectual mechanism by doing thousands or, in the case of Deep Blue, many millions of times as much computation.

Sooner or later, AI research will overcome this scandalous weakness.

Q. Don't some people say that AI is a bad idea?

A. The philosopher John Searle says that the idea of a non-biological machine being intelligent is incoherent. He proposes the Chainees room agrement . The philosopher Hubert Dreyfus says that AI is impossible. The computer scientist Joseph Weizenbaum says the idea is obscene, anti-human and immoral. Various people have said that since artificial intelligence hasn't reached human level by now, it must be impossible. Still other people are disappointed that companies they invested in went bankrupt.

Perception and Learning.

PERCEPTION

Perception is an essential component of intelligent behavior. We perceive the world around us through five basic senses of sight, hearing , touch, smell, and taste., of these, sight and hearing have been the main areas of Artificial Intelligence research leading to speech understanding . when we perceive some signal . it may a be sound or light. We respond appropriately to that signal. To produce an appropriate response we must categorize or analyze that signal. For example to analyze a sentence we must first identify individual sounds, then combine these sounds into words, and then combine words into a meaningful sentence structure . but this is hard because dividing sounds into words needs additional knowledge or information about the situation. A series of sounds may be interpreted in many ways . For instance

“Tigers care their kids”

and “Tiger scare their kids”

might both have been the possible interpretations of the same series of sounds.

To overcome the perceptual problems in speech understanding , the process of analyzing a speech is divided into five stages.

1. Digitization : The continuous input is divided into discrete chunks . in speech the division is done on a time scale and in images, it may be based on

color or area or tint.

2. Smoothing: Since the real world is usually continuous , large spikes and variation in the input is avoided.

3. Segmentation: Group the smaller chunks produced by digitization into larger chunks corresponding to logic components of the signal. For speech understanding segments correspond to individual sounds called phonemes.

4. Labeling: Each segment is given a label.

5. Analysis : The labeled segments are put together to form a coherent object.

LEARNING

Learning is the improvement of performance with experience over time.

Learning element is the portion of a learning AI system that decides how to modify the performance element and implements those modifications.

We all learn new knowledge through different methods, depending on the type of material to be learned, the amount of relevant knowledge we already possess, and the environment in which the learning takes place. There are five methods of learning . They are,

1. Memorization (rote learning)

2. Direct instruction (by being told)

3. Analogy

4. Induction

5. Deduction

Learning by memorizations is the simplest from of le4arning. It requires the least amount of inference and is accomplished by simply copying the knowledge in the same form that it will be used directly into the knowledge base.

Example:- Memorizing multiplication tables, formulate , etc.

Direct instruction is a complex form of learning. This type of learning requires more inference than role learning since the knowledge must be transformed into an operational form before learning when a teacher presents a number of facts directly to us in a well organized manner.

Analogical learning is the process of learning a new concept or solution through the use of similar known concepts or solutions. We use this type of learning when solving problems on an exam where previously learned examples serve as a guide or when make frequent use of analogical learning. This form of learning requires still more inferring than either of the previous forms. Since difficult transformations must be made between the known and unknown situations.

Learning by induction is also one that is used frequently by humans . it is a powerful form of learning like analogical learning which also require s more inferring than the first two methods. This learning re quires the use of inductive inference, a form of invalid but useful inference. We use inductive learning of instances of examples of the concept. For example we learn the

concepts of color or sweet taste after experiencing the sensations associated with several examples of colored objects or sweet foods.

Deductive learning is accomplished through a sequence of deductive inference steps using known facts. From the known facts, new facts or relationships are logically derived. Deductive learning usually requires more inference than the other methods.

Matching and Learning.

MATCHING:So far, we have seen the process of using search to solve problems as the application of appropriate rules to individual problem states to generate new states to which the rules can then be applied, and so forth, until a solution is found. Clever search involves choosing from among the rules that can be applied at a particular point, the ones that are most likely to lead to a solution. We need to extract from the entire collection of rules, those that can be applied at a given point. To do so requires some kind of matching between the current state and the preconditions of the rules.

How should this be done?

One way to select applicable rules is to do a simple search through all the rules comparing one’s preconditions to the current state and extracting all the ones that match . this requires indexing of all the rules. But there are two problems with this simple solutions:

A. It requires the use of a large number of rules. Scanning through all of them would be hopelessly inefficeint.

B. It is not always immediately obvious whether a rule’s preconditions are satisfied by a particular state.

Sometimes , instead of searching through the rules, we can use the current state as an index into the rules and select the matching ones immediately. In spite of limitations, indexing in some form is very important in the efficient operation of rules based systems.

A more complex matching is required when the preconditions of rule specify required properties that are not stated explicitly in the description of the current state. In this case, a separate set of rules must be used to describe how some properties can be inferred from others. An even more complex matching process is required if rules should be applied and if their pre condition approximately match the current situation. This is often the case in situations involving physical descriptions of the world.

LEARNING

Learning is the improvement of performance with experience over time.

Learning element is the portion of a learning AI system that decides how to modify the performance element and implements those modifications.

We all learn new knowledge through different methods, depending on the type of material to be learned, the amount of relevant knowledge we already possess, and the environment in which the learning takes place. There are five methods of learning . They are,

1. Memorization (rote learning)

2. Direct instruction (by being told)

3. Analogy

4. Induction

5. Deduction

Learning by memorizations is the simplest from of le4arning. It requires the least amount of inference and is accomplished by simply copying the knowledge in the same form that it will be used directly into the knowledge base.

Example:- Memorizing multiplication tables, formulate , etc.

Direct instruction is a complex form of learning. This type of learning requires more inference than role learning since the knowledge must be transformed into an operational form before learning when a teacher presents a number of facts directly to us in a well organized manner.

Analogical learning is the process of learning a new concept or solution through the use of similar known concepts or solutions. We use this type of learning when solving problems on an exam where previously learned examples serve as a guide or when make frequent use of analogical learning. This form of learning requires still more inferring than either of the previous forms. Since difficult transformations must be made between the known and unknown situations.

Learning by induction is also one that is used frequently by humans . it is a powerful form of learning like analogical learning which also require s more inferring than the first two methods. This learning re quires the use of inductive inference, a form of invalid but useful inference. We use inductive learning of instances of examples of the concept. For example we learn the

concepts of color or sweet taste after experiencing the sensations associated with several examples of colored objects or sweet foods.

Deductive learning is accomplished through a sequence of deductive inference steps using known facts. From the known facts, new facts or relationships are logically derived. Deductive learning usually requires more inference than the other methods.

Review Questions:-

1. what is perception ?

2. How do we overcome the Perceptual Problems?

3. Explain in detail the constraint satisfaction waltz algorithm?

4. What is learning ?

5. What is Learning element ?

6. List and explain the methods of learning?

Types of learning:- Classification or taxonomy of learning types serves as a guide in studying or comparing a differences among them. One can develop learning taxonomies based on the type of knowledge representation used (predicate calculus , rules, frames), the type of knowledge learned (concepts, game playing, problem solving), or by the area of application(medical diagnosis , scheduling , prediction and so on).

The classification is intuitively more appealing and is one which has become popular among machine learning researchers . it is independent of the knowledge domain and the representation scheme is used. It is based on the type of inference strategy employed or the methods used in the learning process. The five different learning methods under this taxonomy are:

Memorization (rote learning)

Direct instruction(by being told)

Analogy

Induction

Deduction

Learning by memorization is the simplest form of learning. It requires the least5 amount of inference and is accomplished by simply copying the knowledge in the same form that it will be used directly into the knowledge base. We use this type of learning when we memorize multiplication tables ,

for example.

A slightly more complex form of learning is by direct instruction. This type of learning requires more understanding and inference than role learning since the knowledge must be transformed into an operational form before being integrated into the knowledge base. We use this type of learning when a teacher presents a number of facts directly to us in a well organized manner.

The third type listed, analogical learning, is the process of learning an ew concept or solution through the use of similar known concepts or solutions. We use this type of learning when solving problems on an examination where previously learned examples serve as a guide or when we learn to drive a truck using our knowledge of car driving. We make frewuence use of analogical learning. This form of learning requires still more inferring than either of the previous forms, since difficult transformations must be made between the known and unknown situations. This is a kind of application of knowledge in a new situation.

The fourth type of learning is also one that is used frequency by humans. It is a powerful form of learning which, like analogical learning, also requires more inferring than the first two methods. This form of learning requires the use of inductive inference, a form of invalid but useful inference. We use inductive learning when wed formulate a general concept after seeing a number of instance or examples of the concept. For example, we learn the concepts of color sweet taste after experiencing the sensation associated with several examples of colored objects or sweet foods.

The final type of acquisition is deductive learning. It is accomplished through a sequence of deductive inference steps using known facts. From the known facts, new facts or relationships are logically derived. Deductive learning usually requires more inference than the other methods. The inference method used is, of course , a deductive type, which is a valid from of inference.

In addition to the above classification, we will sometimes refer to learning methods as wither methods or knowledge-rich methods. Weak methods are general purpose methods in which little or no initial knowledge is available. These methods are more mechanical than the classical AI knowledge – rich methods. They often rely on a form of heuristics search in the learning process.

Waltz Algorithm.

CONSTRAINT SATISFACTION – WALTZ ALGORIHTM

Many perceptual tasks appear to be highly complex . this is because the number of interpretations that can be assigned to individual components of an input is large and the number of combinations of those components also appears to be enormous. But a clear analysis well reveal that many do the combinations can not actually occur. These natural constraints can be exploited in the understanding process to reduce the complexity from unmanageable to manageable.

There are two important steps in the use of constraints in problem solving:

1. Analyze the problem domain to determine the actual constraints.

2. Solve the problem by applying a constraint satisfaction algorithm.

Consider for example a three dimensional line drawing . The analysis process is to determine the object described by the lines. The geometric relationships between different types of line junctions helped to determine the object types.

Three Dimentioal Polyhedral junction types.

In waltz’s algorithm, labels are assigned to lines of various types-say concave edges are produced by two adjacent toching surfaces which duce a concave (less than 180 Degrees) depth change .

Conversely, convex edges produce a convexly viewed depth (greater than 180 degrees), and a boundary edge outlines a surface that obstracts other objects.

To label a concave edge, a mints sign is used. Convex edges one labeled with a plus sign, and a right or left arrow is used to label the boundary edges. By restricting vertices to be the intersection of three object faces, it is possible to reduce the number of basic vertex types to only four : the L, the T , the Fork and the Arrow.

The L types Fork Types T types

Valid junction labels for three-dimensional shapes.

When a three-dimensional object is viewed from all possible positions, the four junction types, together with the valid edge labels, give rise to eighteen different permissible junction configurations as shown in figurre

Geometric constraints, together with a consistent labeling scheme, can simplify the object identification process. A set of labeling rules which facilitates this process can be developed for different classes of objects. The following rules will apply for many polyhedral objects.

1. The arrow should be directed to mark boundaries by traversing the object in a clockwise direction.

2. Unbroken lines should have the same lable assigned at both ends.

3. When a fork is labeled with a+ edge, it must have all three edges label as + , and

4. Arrow junctions which have aà label on both bard edges must also have a + label on the shaft.

These rules can be applied to a polygonal object as given in figure

example of object labeling.

Starting with any edge having an object face on its right, the external boundary is labeled with the à in a clockwise direction. Interior lines are then labeled with + or _ consistent with the ot

her labeling rules.

To see how waltz constraint satisfaction algorithm works, consider the image dr

awing of a pyramid as given in figure3 At the right side of the pyramid are all po

ssible labelings for the four u\junctions A, b, C and D.

Using these labels as mutual constraints on connected junctions, permissible labels for the whole pyramid can be determined. The constraint satisfaction procedure works as follows.

Starting at an arbitrary junction, say A, a record of all permissible labels is made

for that junction. An adjacent junction is then chosen, say , B and labels which are

inconsistent with the line AB are then eliminated from the p

ermissible A and B lists. In this case, the line joining B can only be a +, - or an up

arrowà consequently, two of the possible

A labelings can be eliminated and the remainin

g are

Choosing junction c next, we find that t

he BC constraints are

satisfied by all of the B and C lableings, so on reduction

is possible with this step. On the otherhand, the line AC must be labled as – or as an up-

left-arrow ß to be consistent. Therefore, an additional label for A can be eliminated to reduce the remainder to the following.

This new restriction on a now permit the elimination of one B leabeling to maintain consistency. Thus, the permissible B leabelings remaining are now







This reduction in turn, places a new restriction on BC, permitting the elimination of one C label, since BC must now be labeled as a + only. This leaves the remaining C labels as show in side diagram.



4. Moving now to junction d, we see that of the six possible D leadings, only three satisfy the BD constraint of a up or a down arrow. Therefore, the remaining permissible leabelings for d are now


Continuing with the above procedure, we see that further label eliminations are not possible since all constraints have been satisfied. This process is completed by finding the different combinations of unique lableings that can be assigned to the figure. An enumerations of the remaining label shows that its is possible to find only three different lableings.