Friday, December 10, 2010

Expert System.

DEFINITION - An expert system is a computer program that simulates the judgement and behavior of a human or an organization that has expert knowledge and experience in a particular field. Typically, such a system contains a knowledge base containing accumulated experience and a set of rules for applying the knowledge base to each particular situation that is described to the program. Sophisticated expert systems can be enhanced with additions to the knowledge base or to the set of rules.

Among the best-known expert systems have been those that play chess and that assist in medical diagnosis.
An expert system is software that attempts to provide an answer to a problem, or clarify uncertainties where normally one or more human experts would need to be consulted. Expert systems are most common in a specific problem domain, and is a traditional application and/or subfield of artificial intelligence (AI). A wide variety of methods can be used to simulate the performance of the expert; however, common to most or all are: 1) the creation of a knowledge base which uses some knowledge representation structure to capture the knowledge of the Subject Matter Expert (SME); 2) a process of gathering that knowledge from the SME and codifying it according to the structure, which is called knowledge engineering; and 3) once the system is developed, it is placed in the same real world problem solving situation as the human SME, typically as an aid to human workers or as a supplement to some information system. Expert systems may or may not have learning components.
 
factors


The MYCIN rule-based expert system introduced a quasi-probabilistic approach called certainty factors, whose rationale is explained below.

A human, when reasoning, does not always make statements with 100% confidence: he might venture, "If Fritz is green, then he is probably a frog" (after all, he might be a chameleon). This type of reasoning can be imitated using numeric values called confidences. For example, if it is known that Fritz is green, it might be concluded with 0.85 confidence that he is a frog; or, if it is known that he is a frog, it might be concluded with 0.95 confidence that he hops. These certainty factor (CF) numbers quantify uncertainty in the degree to which the available evidence supports a hypothesis. They represent a degree of confirmation, and are not probabilities in a Bayesian sense. The CF calculus, developed by Shortliffe & Buchanan, increases or decreases the CF associated with a hypothesis as each new piece of evidence becomes available. It can be mapped to a probability update, although degrees of confirmation are not expected to obey the laws of probability. It is important to note, for example, that evidence for hypothesis H may have nothing to contribute to the degree to which Not_h is confirmed or disconfirmed (e.g., although a fever lends some support to a diagnosis of infection, fever does not disconfirm alternative hypotheses) and that the sum of CFs of many competing hypotheses may be greater than one (i.e., many hypotheses may be well confirmed based on available evidence).

The CF approach to a rule-based expert system design does not have a widespread following, in part because of the difficulty of meaningfully assigning CFs a priori. (The above example of green creatures being likely to be frogs is excessively naive.) Alternative approaches to quasi-probabilistic reasoning in expert systems involve fuzzy logic, which has a firmer mathematical foundation. Also, rule-engine shells such as Drools and Jess do not support probability manipulation: they use an alternative mechanism called salience, which is used to prioritize the order of evaluation of activated rules.

In certain areas, as in the tax-advice scenarios discussed below, probabilistic approaches are not acceptable. For instance, a 95% probability of being correct means a 5% probability of being wrong. The rules that are defined in such systems have no exceptions: they are only a means of achieving software flexibility when external circumstances change frequently. Because rules are stored as data, the core software does not need to be rebuilt each time changes to federal and state tax codes are announced.


Chaining


Two methods of reasoning when using inference rules are forward chaining and backward chaining.

Forward chaining starts with the data available and uses the inference rules to extract more data until a desired goal is reached. An inference engine using forward chaining searches the inference rules until it finds one in which the if clause is known to be true. It then concludes the then clause and adds this information to its data. It continues to do this until a goal is reached. Because the data available determines which inference rules are used, this method is also classified as data driven.

Backward chaining starts with a list of goals and works backwards to see if there is data which will allow it to conclude any of these goals. An inference engine using backward chaining would search the inference rules until it finds one which has a then clause that matches a desired goal. If the if clause of that inference rule is not known to be true, then it is added to the list of goals.

SW Architecture.

The following general points about expert systems and their architecture have been outlined:

1. The sequence of steps taken to reach a conclusion is dynamically synthesized with each new case. The sequence is not explicitly programmed at the time that the system is built.

2. Expert systems can process multiple values for any problem parameter. This permits more than one line of reasoning to be pursued and the results of incomplete (not fully determined) reasoning to be presented.

3. Problem solving is accomplished by applying specific knowledge rather than specific technique. This is a key idea in expert systems technology. It reflects the belief that human experts do not process their knowledge differently from others, but they do possess different knowledge. With this philosophy, when one finds that their expert system does not produce the desired results, work begins to expand the knowledge base, not to re-program the procedures.
 
End user

There are two styles of user-interface design followed by expert systems. In the original style of user interaction, the software takes the end-user through an interactive dialog. In the following example, a backward-chaining system seeks to determine a set of restaurants to recommend:

Q. Do you know which restaurant you want to go to?

A. No

Q. Is there any kind of food you would particularly like?

A. No

Q. Do you like spicy food?

A. No

Q. Do you usually drink wine with meals?

A. Yes

Q. When you drink wine, is it French wine?

A. Yes
 
 
Participants
 
There are generally three individuals having an interaction in an expert system. Primary among these is the end-user, the individual who uses the system for its problem solving assistance. In the construction and maintenance of the system there are two other roles: the problem domain expert who builds the system and supplies the knowledge base, and a knowledge engineer who assists the experts in determining the representation of their knowledge, enters this knowledge into an explanation module and who defines the inference technique required to solve the problem. Usually the knowledge engineer will represent the problem solving activity in the form of rules. When these rules are created from domain expertise, the knowledge base stores the rules of the expert system.

 Inference rule

An understanding of the "inference rule" concept is important to understand expert systems. An inference rule is a conditional statement with two parts: an if clause and a then clause. This rule is what gives expert systems the ability to find solutions to diagnostic and prescriptive problems. An example of an inference rule is:

If the restaurant choice includes French and the occasion is romantic,

Then the restaurant choice is definitely Paul Bocuse.
 
Procedure node interface

The function of the procedure node interface is to receive information from the procedures coordinator and create the appropriate procedure call. The ability to call a procedure and receive information from that procedure can be viewed as simply a generalization of input from the external world. In some earlier expert systems external information could only be obtained in a predetermined manner, which only allowed certain information to be acquired. Through the knowledge base, this expert system disclosed in the cross-referenced application can invoke any procedure allowed on its host system. This makes the expert system useful in a much wider class of knowledge domains than if it had no external access or only limited external access.

In the area of machine diagnostics using expert systems, particularly self-diagnostic applications, it is not possible to conclude the current state of "health" of a machine without some information. The best source of information is the machine itself, for it contains much detailed information that could not reasonably be provided by the operator.

The knowledge that is represented in the system appears in the rulebase. In the rulebase described in the cross-referenced applications, there are basically four different types of objects, with the associated information:

1. Classes: Questions asked to the user.

2. Parameters: Place holders for character strings which may be variables that can be inserted into a class question at the point in the question where the parameter is positioned.

3. Procedures: Definitions of calls to external procedures.

4. Rule nodes: Inferences in the system are made by a tree structure which indicates the rules or logic mimicking human reasoning. The nodes of these trees are called rule nodes. There are several different types of rule nodes.



Wednesday, December 8, 2010

Artificial Neural Networks

Neural Networks

Artificial neural networks are among the most powerful learning models. They have the versatility to approximate a wide range of complex functions representing multi-dimensional input-output maps. Neural networks also have inherent adaptability, and can perform robustly even in noisy environments. An Artificial Neural Network (ANN) is an information processing paradigm that is inspired by the way biological nervous systems, such as the brain, process information. The key element of this paradigm is the novel str ucture of the information processing system. It is composed of a large number of highly interconnected simple processing elements (neurons) working in unison to solve specific problems. ANNs, like people, learn by example. An ANN is configured for a specific application, such as pattern recognition or data classification, through a learning process. Learning in biological systems involves adjustments to the synaptic connections that exist between the neurons.

This is true of ANNs as well. ANNs can process information at a great speed owing to their highly massive parallelism. Neural networks, with their remarkable ability to derive meaning from complicated or Imprecise data, can be used to extract patterns and detect trends that are too complex to be noticed by either humans or other computer techniques. A trained neural network can be thought of as an "expert" in the category of information it has been given to analyse.

This expert can then be used to provide projections given new situations of interest and answer "what if" questions. Other advantages include: 1. Adaptive learning: An ability to learn how to do tasks based on the data given for raining or initial experience. 2. Self-Organisation: An ANN can create its own organisation or representation of the information it receives during learning time.

3. Real Time Operation: ANN computations may be carried out in parallel, and special hardware devices are being designed and manufactured which take advantage of this capability.

4. Fault Tolerance via Redundant Information Coding: Partial destruction of a network leads to the corresponding degradation of performance. However, some network capabilities may be retained even with major network damage.


Biological Neural Networks

Much is still unknown about how the brain trains itself to process information, so theories abound. In the human brain, a typical neuron collects signals from others through a host of fine structures called dendrites . The neuron sends out spikes of electrical activity through a long, thin stand known as an axon , which splits into thousands of branches. At the end of each branch, a structure called a synapse converts the activity from the axon into electrical effects that inhibit or excite activity from the axon into electrical effects that inhibit or excite activity in the connected neurones. When a neuron receives Artificial Neural Networks Artificial neural networks are represented by a set of nodes, often arranged in layers, and a set of weighted directed links connecting them. The nodes are equivalent to neurons, while the links denote synapses. The nodes are the information processing units and the links acts as communicating media. There are a wide variety of networks depending on the nature of information processing carried out at individual nodes, the topology of the links, and the algorithm for adaptation of link weights. Some of the popular among them include:

Perceptron: This consists of a single neuron with multiple inputs and a single output. It has restricted information processing capability. The information processing is done through a transfer function which is either linear or non-linear. Multi-layered Perceptron (MLP): It has a layered rchitecture consisting of input, hidden and output layers. Each layer consists of a number of perceptrons. The output of each layer is transmitted to the input of nodes in other layers through weighted links. Usually, this transmission is done only to nodes of the next layer, leading to what are known as feed forward networks। MLPs were proposed to extend the limited information processing capabilities of simple percptrons, and are highly versatile in terms of their approximation ability. Training or weight adaptation is done in MLPs using supervised backpropagation learning. Recurrent Neural Networks: RNN topology involves backward links from output to the input and hidden layers. The notion of time is encoded in the RNN information processing scheme. They are thus used in applications like speech processing where inputs are time sequences data. Self-Organizing Maps : SOMs or Kohonen networks have a grid topology, wit unequal grid weights. The topology of the grid provides a low dimensional visualization of the data distribution. These are thus used in applications which typically involve rganization and human browsing of a large volume of data. Learning is performed using a winner take all strategy in a unsupervised mode. In this module we will discuss perceptrons and multi layered perceptrons.


The nueron sends out spikes of electrical activity through a long, thin strand known as an axon, which splits into thousands of brahches. At the end of each branch, a structure called a synapse converts the activity from te axon into electrcal effects that inhibit the activity in the connected neurons. When a nueron receieves excitatory input that sufficiently large compared to its inhiitary input, it sends a spike of electrical activity down its axon. Learning occurs by changing the effectiveness of the synapses so that the influence of one neuron on another changes.










Learning

Machine Learning is the study of how to build computer systems that adapt and improve with experience. It is a subfield of Artificial Intelligence and intersects with cognitive science, information theory, and probability theory, among others. Classical AI deals mainly with deductive reasoning, learning represents inductive reasoning. Deductive reasoning arrives at answers to queries relating to a particular situation starting from a set of general axioms, whereas inductive reasoning arrives at general axioms from a set of particular instances. Classical AI often suffers from the knowledge acquisition problem in real life applications where obtaining and updating the knowledge base is costly and prone to errors. Machine learning serves to solve the knowledge acquisition bottleneck by obtaining the result from data by induction. Machine learning is particularly attractive in several real life  problem because of the following reasons: • Some tasks cannot be defined well except by example • Working environment of machines may not be known at design time

• Explicit knowledge encoding may be difficult and not available

• Environments change over time

• Biological systems learn Recently, learning is widely used in a number of application areas including,

• Data mining and knowledge discovery

• Speech/image/video (pattern) recognition

• Adaptive control

• Autonomous vehicles/robots

• Decision support systems

• Bioinformatics

• WWW

Formally, a computer program is said to

learn from experience  E  with respect to some class of tasks T  and performance measure P

, if its performance at tasks in  T , as measured  by  P, improves with experience E

Thus a learning system is characterized by:

• task T

• experience E, and

• performance measure P



Learning - Machine Learning

Machine Learning is the study of how to build computer systems that adapt and improve with experience. It is a subfield of Artificial Intelligence and intersects with cognitive science, information theory, and probability theory, among others.

Classical AI deals mainly with  deductive reasoning, learning represents  inductive reasoning. Deductive reasoning arrives at answers to queries relating to a particular situation starting from a set of general axioms, whereas inductive reasoning arrives at general axioms from a set of particular instances.

Classical AI often suffers from the knowledge acquisition problem in real life applications where obtaining and updating the knowledge base is costly and prone to errors. Machine learning serves to solve the knowledge acquisition bottleneck by obtaining the result from data by induction.

Machine learning is particularly attractive in several real life problem because of the following reasons:

• Some tasks cannot be defined well except by example

• Working environment of machines may not be known at design time

• Explicit knowledge encoding may be difficult and not available

• Environments change over time

• Biological systems learn Recently, learning is widely used in a number of application areas including,

• Data mining and knowledge discovery

• Speech/image/video (pattern) recognition

• Adaptive control

• Autonomous vehicles/robots

• Decision support systems

• Bioinformatics

• WWW

Formally, a computer program is said to learn  from experience E  with respect to some class of tasks T

and performance measure P , if its performance at tasks in T , as measured  by P, improves with experience

E  Thus a learning system is characterized by:

• task T

• experience E, and

• performance measure P



Tuesday, November 30, 2010

Fuzzy Inferencing

Fuzzy Inferencing


The process of fuzzy reasoning is incorporated into what is called a Fuzzy Inferencing System. It is comprised of three steps that process the system inputs to the appropriate system outputs. These steps are 1) Fuzzification, 2) Rule Evaluation, and 3) Defuzzification. The system is illustrated in the following figure.



1Fuzzification

is the first step in the fuzzy inferencing process. This involves a domain formation where crisp inputs are transformed into fuzzy inputs. Crisp inputs are exact inputs measured by sensors and passed into the control system for processing, such as temperature, pressure, rpm's, etc.. Each crisp input that is to be processed by the FIU has its own group of membership functions or sets to which they are transformed. This group of membership functions exists within a universe of discourse that holds all relevant values that the crisp input can possess. The following shows the structure of membership functions within a universe of discourse for a crisp input.

2 Degree of membership:


degree to which a crisp value is compatible to a membership function, value from 0 to 1, also known as truth value or fuzzy input.membership function, MF: defines a fuzzy set by mapping crisp values from its domain to the sets associated degree of membership.

3.crisp inputs: distinct or exact inputs to a certain system variable, usually measured

4.parameters external from the control system, e.g. 6 Volts.

5.label: descriptive name used to identify a membership function.

6.scope: or domain, the width of the membership function, the range of concepts, usually numbers, over which a membership function is mapped.

7.universe of discourse: range of all possible values, or concepts, applicable to a system variable. When designing the number of membership functions for an input variable, labels must initially be determined for the membership functions. The number of labels correspond to the number of regions that the universe should be divided, such that each label describes a region of behavior. A scope must be assigned to each membership function that numerically identifies the range of input values that correspond to a label. The shape of the membership function should be representative of the variable. However this shape is also restricted by the computing resources available. Complicated shapes require more complex descriptive equations or large lookup tables. The next figure shows examples of possible shapes for membership functions.
Classical Planners use the STRIPS (Stanford Research Institute Problem Solver)

language to describe states and operators. It is an efficient way to represent

planning algorithms.

Fuzzy Concepts. Hedges

Another important feature of fuzzy systems is the ability to define "hedges," or

modifier of fuzzy values. These operations are provided in an effort to maintain

close ties to natural language, and to allow for the generation of fuzzy statements

through mathematical calculations. As such, the initial definition of hedges and

operations upon them will be quite a subjective process and may vary from one

project to another. Nonetheless, the system ultimately derived operates with the

same formality as classic logic. The simplest example is in which one transforms

the statement "Jane is old" to "Jane is very old." The hedge "very" is usually

defined as follows:

m"very"A(x) = mA(x)^2 Thus, if mOLD(Jane) = 0.8, then mVERYOLD(Jane) = 0.64.

Other common hedges are "more or less" [typically SQRT(mA(x))], "somewhat,"

"rather," "sort of," and so on. Again, their definition is entirely subjective, but

their operation is consistent: they serve to transform membership/truth values in a

systematic manner according to standard mathematical functions.

A more involved approach to hedges is best shown through the work of Wenstop

in his attempt to model organizational behavior. For his study, he constructed

arrays of values for various terms, either as vectors or matrices. Each term and

hedge was represented as a 7-element vector or 7x7 matrix. He ten intuitively

assigned each element of every vector and matrix a value between 0.0 and 1.0,

inclusive, in what he hoped was intuitively a consistent manner. For example, the

term "high" was assigned the vector 0.0 0.0 0.1 0.3 0.7 1.0 1.0

and "low" was set equal to the reverse of "high," or 1.0 1.0 0.7 0.3 0.1 0.0 0.0

Wenstop was then able to combine groupings of fuzzy statements to create new

fuzzy statements, using the APL function of Max-Min matrix multiplication.

These values were then translated back into natural language statements, so as to

allow fuzzy statements as both input to and output from his simulator. For

example, when the program was asked to generate a label "lower than sortof

low," it returned "very low;" "(slightly higher) than low" yielded "rather low,"

etc. The point of this example is to note that algorithmic procedures can be

devised  which translate "fuzzy" terminology into numeric values, perform

reliable operations upon those values, and then return natural language statements

in a  reliable manner.

Fuzzy Concepts.

The notion central to fuzzy systems is that truth values (in fuzzy logic) or membership values (in fuzzy sets) are indicated by a value on the range [0.0, 1.0], with 0.0 representing absolute Falseness and 1.0 representing absolute Truth. For example, let us take the statement: "Jane is old."

If Jane's age was 75, we might assign the statement the truth value of 0.80. The statement could be translated into set terminology as follows:

"Jane is a member of the set of old people."

This statement would be rendered symbolically with fuzzy sets as:

mOLD(Jane) = 0.80

where m is the membership function, operating in this case on the fuzzy set of old people, which returns a value between 0.0 and 1.0.

At this juncture it is important to point out the distinction between fuzzy systems and probability. Both operate over the same numeric range, and at first glance both have similar values: 0.0 representing False (or non- membership), and 1.0 representing True (or membership). However, there is a distinction to be made between the two statements:

The probabilistic approach yields the natural-language statement, "There is an 80% chance that Jane is old," while the fuzzy terminology corresponds to "Jane's degree of membership within the set of old people is 0.80." The semantic difference is significant:

the first view supposes that Jane is or is not old (still caught in the Law of the Excluded Middle); it is just that we only have an 80% chance of knowing which set she is in. By contrast, fuzzy terminology supposes that Jane is "more or less" old, or some other term corresponding to the value of 0.80. Further distinctions arising out of the operations will be noted below.

The next step in establishing a complete system of fuzzy logic is to define the operations of EMPTY, EQUAL, COMPLEMENT (NOT), CONTAINMENT, UNION (OR), and INTERSECTION (AND). Before we can do this rigorously, we must state some formal definitions:

Definition 1

: Let X be some set of objects, with elements noted as x. Thus,

X = {x}.

Definition 2

: A fuzzy set A in X is characterized by a membership function mA(x) which maps each point in X onto the real interval [0.0, 1.0]. As mA(x) approaches 1.0, the "grade of membership" of x in A increases.

Definition 3

: A is EMPTY iff for all x, mA(x) = 0.0.

Definition 4

: A = B iff for all x: mA(x) = mB(x) [or, mA = mB].

Definition 5

: mA' = 1 - mA.

Definition 6

: A is CONTAINED in B iff mA <= mB.

Definition 7

: C = A UNION B, where: mC(x) = MAX(mA(x), mB(x)).

Definition 8:

C = A INTERSECTION B where: mC(x) = MIN(mA(x), mB(x)).

It is important to note the last two operations, UNION (OR) and INTERSECTION

(AND), which represent the clearest point of departure from a probabilistic theory for sets to fuzzy sets. Operationally, the differences are as follows:

For independent events, the probabilistic operation for AND is multiplication,

which (it can be argued) is counterintuitive for fuzzy systems. For example, let us

presume that x = Bob, S is the fuzzy set of smart people, and T is the fuzzy set of

tall people. Then, if mS(x) = 0.90 and uT(x) = 0.90, the probabilistic result would

be: mS(x) * mT(x) = 0.81 whereas the fuzzy result would be:

MIN(uS(x), uT(x)) = 0.90

The probabilistic calculation yields a result that is lower than either of the two

initial values, which when viewed as "the chance of knowing" makes good sense.

However, in fuzzy terms the two membership functions would read something

like "Bob is very smart" and "Bob is very tall." If we presume for the sake of

argument that "very" is a stronger term than "quite," and that we would correlate

"quite" with the value 0.81, then the semantic difference becomes obvious. The

probabilistic calculation would yield the statement If Bob is very smart, and Bob

is very tall, then Bob is a quite tall, smart person.The fuzzy calculation, however,

would yield If Bob is very smart, and Bob is very tall, then Bob is a very tall,

smart person.Another problem arises as we incorporate more factors into our

equations (such as the fuzzy set of heavy people, etc.). We find that the ultimate

result of a series of AND's approaches 0.0, even if all factors are initially high.

Fuzzy theorists argue that this is wrong: that five factors of the value 0.90 (let us

say, "very") AND'ed together, should yield a value of 0.90 (again, "very"), not

0.59 (perhaps equivalent to "somewhat").

Similarly, the probabilistic version of A OR B is (A+B - A*B), which approaches

1.0 as additional factors are considered. Fuzzy theorists argue that a sting of low

membership grades should not produce a high membership grade instead, the limit

of the resulting membership grade should be the strongest membership value in

the collection. The skeptical observer will note that the assignment of values to

linguistic meanings (such as 0.90 to "very") and vice versa, is a most imprecise

operation. Fuzzy systems, it should be noted, lay no claim to establishing a formal

procedure for assignments at this level; in fact, the only argument for a particular

assignment is its intuitive strength. What fuzzy logic does propose is to establish a

formal method of operating on these values, once the primitives have been

established.


Planning as Search

Planning as Search:

There are two main approaches to solving planning problems, depending on the kind of search space that is explored:

1. Situation-space search

2. Planning-space searchIn situation space search

In Situation-Space search

• the search space is the space of all possible states or situations of the world

• initial state defines one node

• a goal node is a state where all goals in the goal state are satisfied

• a solution plan is the sequence of actions (e.g. operator instances) in the path 
  from the start node to a goal node.

In Plan-Space Search

• the search space is the space of all possible plans

• a node corresponds to a partial plan

• initially we will specify an "initial plan" which is one node in this space

• a goal node is a node containing a plan which is complete, satisfying all of the
  goals in the goal state

• the node itself contains all of the information for determining a solution plan  
   (e.g.sequence of actions)

Goal Interaction

Most planning algorithms assume that the goals to be achieved are independent or nearly independent in the sense that each can be solved separately and then the solutions concatenated together. If the order of solving a set of goals (either the original goals or a  set of sub-goals which are the preconditions of an operator) fails because solving a latter goal undoes an earlier goal, then this version of the STRIPS algorithm fails. Hence, situation-space planners do not allow for interleaving of steps in any solution it finds.

Principle of Least Commitment:The principle of least commitment is the idea of never making a choice unless required to do so. The advantage of using this principle is you won't have to backtrack later! In planning, one application of this principle is to never order plan steps unless it's necessary for some reason. So, partial-order planners exhibit this property because constraint ordering steps will only be inserted when necessary. On the other hand, situation-space progression planners make commitments about the order of steps as they try to find a solution and therefore may make mistakes from poor guesses about the right order of steps.





Monday, November 29, 2010

Situation Calculus

Situation Calculus


Situation calculus is a version of first-order-logic (FOL) that is augmented so that it can reason about actions in time.

• Add situation variables to specify time. A situation  is a snapshot of the world at

an interval of time when nothing changes

• Add a special predicate holds(f,s) that means "f is true in situation s"

• Add a function result(a,s) that maps the current situations into a new situation as

a result of performing action a.

Saturday, November 27, 2010

Planning Systems

Classical Planners use the STRIPS (Stanford Research Institute Problem Solver)

language to describe states and operators. It is an efficient way to represent planning

algorithms.
Representation of States and Goals


States are represented by conjunctions of function-free ground literals, that is, predicates

applied to constant symbols, possibly negated.

An example of an initial state is:

At(Home)

/\ -

Have(Milk)

/\ -

Have(Bananas)

/\ -

Have(Drill)

/\ ...

A state description does not have to be complete. We just want to obtain a successful plan

to a set of possible complete states. But if it does not mention a given positive literal, then

the literal can be assumed to be false.

Goals are a conjunction of literals. Therefore the goal is
Algorithm of a simple planning agent:


1. Generate a goal to achieve

2. Construct a plan to achieve goal from current state

3. Execute plan until finished

4. Begin again with new goal

Friday, November 26, 2010

ProblemSolving Vs Planning.

Problem Solving vs. Planning


A simple planning agent is very similar to problem-solving agents in that it constructs

plans that achieve its goals, and then executes them. The limitations of the problem-

solving approach motivates the design of planning systems.

To solve a planning problem using a state-space search approach we would let the:

• initial state = initial situation

• goal-test predicate = goal state description

• successor function computed from the set of operators

• once a goal is found, solution plan is the sequence of operators in the path from

the start node to the goal node In searches, operators are used simply to generate successor states and we

can not look "inside" an operator to see how it’s defined. The goal-test predicate also is used as a

"black box" to test if a state is a goal or not. The search cannot use properties of how a

goal is defined in order to reason about finding path to that goal.

Hence this approach is all algorithm and representation weak.

Planning is considered different from problem solving because of the difference in the

way they represent states, goals, actions, and the differences in the way they construct

action sequences. Remember the search-based problem solver had four basic elements:

• Representations of actions: programs that develop successor state descriptions which

represent actions.

• Representation of state: every state description is complete. This is because a

complete description of the initial state is given, and actions are represented by a program

that creates complete state descriptions.

• Representation of goals: a problem solving agent has only information about it's

goal, which is in terms of a goal test and the heuristic function.

• Representation of plans: in problem solving, the solution is a sequence of actions.

In a simple problem:

"Get a quart of milk and a bunch of bananas and a variable speed

cordless drill" for a problem solving exercise we need to specify:

Initial State: the agent is at home without any objects that he is wanting.

Operator Set: everything the agent can do.


Heuristic function: the # of things that have not yet been acquired.

Problems with Problem solving agent: It is evident from the above figure that the actual branching factor

would be in the thousands or millions. The heuristic evaluation function can only choose states to

determine which one is closer to the goal. It cannot eliminate actions from

consideration. The agent makes guesses by considering actions and the evaluation

function ranks those guesses. The agent picks the best guess, but then has no idea

what to try next and therefore starts guessing again. It considers sequences of actions beginning from the

initial state. The agent is

forced to decide what to do in the initial state first, where possible choices are to

go to any of the next places. Until the agent decides how to acquire the objects, it

can't decide where to go.Planning emphasizes what is in operator and goal representations. There are three

key ideas behind planning:to "open up" the representations

of state, goals, and operators so that a reasoner

can more intelligently select actions when they are needed

the planner is free to add actions to the plan

wherever they are needed, rather

than in an incremental sequence starting at the initial state

most parts of the world are independent of most other parts

which makes it feasible to take a conjunctive goal and solve it with a divide-and-conquer strategy

Algorithem simple Planning Agent.

1. Generate a goal to achieve


2. Construct a plan to achieve goal from current state

3. Execute plan until finished

4. Begin again with new goal

The agent first generates a goal to achieve, and then constructs a plan to achieve it from


the current state. Once it has a plan, it keeps executing it until the plan is finished, then

begins again with a new goal.

Assumptions:


A simple planning agent create and use plans based on the following assumptions:

Atomic time :each action is indivisible

No concurrent actions : allowed

Deterministic actions : result of each actions is completely determined by the

definition of the action, and there is no uncertainty in performing it in the world.

Agent is the sole cause of change: in the world.

Agent is omniscient : has complete knowledge of the state of the world

LogicBasedPlanning.

Introduction to Planning

The purpose of planning is to find a sequence of actions that achieves a given goal when

performed starting in a given state. In other words, given a set of operator instances

(defining the possible primitive actions by the agent), an initial state description, and a

goal state description or predicate, the planning agent computes a plan.

What is a plan?

A sequence of operator instances, such that "executing" them in the

initial state will change the world to a state satisfying the goal state description. Goals

are usually specified as a conjunction of goals to be achieved.

Simple Planning Agent:

Earlier we saw that

problem-solving agents

are able to plan ahead - to consider the

consequences of sequences

of actions - before acting. We also saw that a knowledge-based agents can select actions based on explicit, logical representations of the current state and the effects of actions. This allows the agent to succeed in complex, inaccessible environments that are too difficult for a problem-solving agent

Problem Solving Agents + Knowledge-based Agents = Planning Agents

In this module, we put these two ideas together to build

planning agents.

At the most abstract level, the task of planning is the same as problem solving. Planning can be
viewed as a type of problem solving in which the agent uses beliefs about actions and 
their consequences to search for a solution over the more abstract space of plans, rather  than over the space of situations


Planning.!

The students should understand the formulation of planning problems

The student should understand the difference between problem solving and planning
 and the need for knowledge representation in large scale problem solving
Students should understand the STRIPS planning language
Students should be able to represent a real life planning problem using STRIPS
operators
Students should understand planning using situation calculus and the related frame
problems
Students should understand the formulation of planning as a search problem
 Students should learn the following planning algorithms
Situation space planning
Plan space planning
Progression planning
Regression planning
The student should understand the difficulties of full commitment planning
Students should understand the necessity of least commitment
Students should learn partial order planning algorithms
At the end of this lesson the student should be able to do the following:
Represent a planning problem in STRIPS language
Use a suitable planning algorithm to solve the problem.

Friday, September 24, 2010

Artificial Intelligence Questions List.

Define Artificial Intelligence.?

What is the difference between Intelligence and Artificial Intelligence.?

The Birth and Development of Present day AI Research.

Important Events in the History of Artificial Intelligence Research.

What are the characterstics of Intelligence.?

What is AI Technique.?

What are the Knowledge Characterstics.?

What do you know about Production System,.?

Explain the concept of Control Stratagy.?

How can you analyze a Problem.?

Explain the concept of Operators or Production Rules.?

Define the problem as State Space Search Examine in detail.?

Define the problem as Satate Space Problem Sate and Prove Water Jug Proble,.?

Define the concept of Water Jug Problem. find three solutions to Water Jug Problem. Compare if there is a Water scarcity which solution is better and if there is no scarcity of Water which solution is better.?

Define the problem as State Space Problem state and prove Missionaries and Cannibals problem.?

By using State Space Problem write one solution to Tower of Honai Problem,.?

Explain the concept of AI problem characterstics in detail.?

What do you know about Heuristic Search.?

Explain the concept of Heuristic Search Techniques.?

Differentiate Problem Trees from Problem Graphs.?

Explain the concept of Depth First Search in detail.?

Explain the concept of Bredth First Search in detail.?

Explain the concept of Generate and Test Procedure.?

Why Heuristic Search Techniques are called WeekMethods.? Explain the same by using Nearest Neighbour Algorithem of Travelling Sales Man Problem.?

Explain the concept of Best First Search Procedure with an implementation of A* Algorithem.?

What do you know about OR arcs in A* algorithem.? explain in detail.?

Explain the concept of Problem Reduction Method with an implementation of AO* Algorithem.?

Difference between A* Algorithm and AO* Algorthm.?

What do you know about Constraint Satisfaction Procedure.? Explain the same with Constraint inference Rules by using search trees.?

Explain the concept of Means Ends Aanalysis Procedure.?

What do U mean by Knowledge Representation.?

Explain the concept of Symbolic Representaion of Knowledge.?

Knowledge Representation by using Pridicate Logic.

Knowledge Representation by using Proposational Logic.

Explain the Concept of Resolution Procedure.?

Explain the Concept of Resolution Pridicate Logic.?

Explain the Concept of Resolution in Proposational Logic.?

State and Prove Unification Algorithm.?

Explain the concept of Structured Representaion of Kowledge.?

Explain the concept of Semantic Net in detail.?

Explain the concept of Conceptual Dependency Diagrams.?

Write a Short Note on Frame and Script.

What do you know about Non-Monotonic Reasoning.?

Explain the concept of Probabilistic Reasoning.?

Expain the concept of Case Bsed Reasoning.?

What do U Know about Fuzzy Logic.?

Explain the concept of Goal Stack Planning.?

Explain the concept of Blocks world Problem.?

What do you know about Planning System.?

Explain the concept of Natural Language Processing.?

Explain the concept of Syntatic Analysis and Semantic Analysis.?

Expain the concept of CommonSence Aunthologies.?

Explain the concept of Qualitative Physics.?

What do U mean Expert System.? Explain the Architecture of Expert System.?

Explain about Expert System Development Process.?

What are the limitations of Expert System.? Differentiate a CaseBasedExpertSystem from ModelBasedExpertSystem.?

ARTIFICIAL INTELLIGENCE Dec-2010

Answer all the Questions.
1. a. Define AI.? give the Applications og AI,?
b. Define simple and steapest Hill Climbing.
c. What is heuristic function.?
d. Write the fact form of "Marcus was Tryassosinated by the Ceaser".?
e. What is inheritable Knowledge.?
f. What are the partitioned semantic nets.?
g. Define conditional planning.
h. What is expert system shell.?


Answer all the Questions 8 * 2 = 16 Marks.

1. Syntatic Processing.
2. Discourse.
3. semantic Net
4. Frames.
5. Natural Deduction.
6. Frame Problem
7. Means ends Analysis.
8. AI Technique.

UNIT-I
2. Explain the following Heuristic Search Techniques.
A Hill Climbing
B Best First Search
C Problem Reduction
3. A Explain Production System Characteristics.
B AI Technique with AI Problems.

UNIT II
4. A. Explain about Resolution Procedure in Pridicate Ligic.
B. Discuss the Instance of ISA RelarionShip.
5. A. Explain about Backward Vs Far ward Reasoning.
B. Write the Issues of the Knowledge Representation.

UNIT III
6. A. Explain about Closed World Assumption.
B. Hierarchical Planning.
7. A. Explain about Non Monotonic Reasoning.

UNIT IV
8. Explain SyntacticProcessing
9. Memory Organization and Case Based Reasoning.








UNIT -I

2. Tower of Honai Problem.

OR

3. a. State AO* Algorithem.?
b. Characterstics of Production System.?

UNIT -II

4. Difference between Procedural Knowledge and Declerative Knowledge.

OR

5. Discuss the steps involved in converting a Standard form to Clause form.

UNIT - III

6. Construct a Semantic Network with the suitable examples.?

OR

7. List out the Advantages and Disadvantages that occur in writing the Scripts to represent the Knowledge.?

UNIT - IV

8. What are the characterstics of an Ideal Expert System.?

OR

9. Explain the concept of Natural Language Processing System.?



THE PEDANANDIPADU COLLEGE OF ARTS & SCIENCES, PEDANANDIPADU

NOVEMBER/DECEMBER - 2007

Third Semeter

Paper V-ARTIFICIAL INTELLIGENCE



Time:Three Hours Maximum.Marks:80M

Answer Question No.1 compulsorily, (8x2=16)

Answer ONE question from each Unit.(4x16=64)

All questions carry equal marks.

1.a)Distinguish between forward reasoning and backward reasoning?

b)What is AI.

c)What are the issues in knowledge representation.

d)What is meant by unsupervised learning.

e)Explain the term monotonicity.

f)What is state space search?

g)Define Symbolic Reasoning.

h)What is a frame?



UNIT I

2.a)Write Best-first-search algorithm with suitable example.

b)Explain various steps in water jug problem .

Or

c)Discuss and distinguish b/w DFS and BFS .

d)Write Algorithm with suitable example.

UNIT II

3.a)What is a script? Write Restaurant Script in detail.

b)What are semantic nets? Explain with relavent example.

Or

c)Discuss different issues of representing the knowledge.

d)Describe the representation of instance and is a relation.

UNIT III

4.a)Explain the concepts of Symbolic Reasoning and non-monotonic Reasoning.

Or

b)Write short notes on Expert Systems.

UNIT IV

5.a)Write a set of logical predicates that will perform simple automobile diagnostics (ex. If the engine won’t turn over and the lights won’t come on, then the battery is bad) don’t try to be too elaborate, but cover the cases of bad battery out of gas, bad spark plugs and bad starter motor.

Or

b)Discuss the Unification Algorithm with suitable example.

c)What is Syntactic Analysis? Explain with suitable example.
THE PEDANANDIPADU COLLEGE OF ARTS & SCIENCES, PEDANANDIPADU


NOVEMBER/DECEMBER - 2006

Third Semeter

Paper V-ARTIFICIAL INTELLIGENCE



Time:Three Hours Maximum.Marks:80M

Answer Question No.1 compulsorily, (8x2=16)

Answer ONE question from each Unit.(4x16=64)

All questions carry equal marks.

1.Write short notes on the following:

a)What do you mean by state space search?

b)Clause form.

c)What are the issues in knowledge presentation?

d)What is hill climbing?

e)Define Backward reasoning.

f)Represent the fact described by the following sentence as a set of wff’s in predicate

logic:

“Marcus tried to assassinate Caesar”.

g)Syntactic analysis.

h) What is the difference between forward and backward reasoning?



UNIT I

2.a)Write AO* algorithm with suitable example.

b)How do we define a problem as a state space search? Explain.

Or

c)What is depth-first search technique? Give the algorithm compare it with breacdth-first technique.

d)What is “means-ends” analysis? Illustrate with an example.

UNIT II

3.a)Explain the issues in knowledge representation.

b)Briefly discuss property inheritance algorithm.

Or

c)Describe about representation of instance and ‘Isa’ relationship.

d)Briefly explain about computable functions and predicates.

UNIT III

4.a)Explain the concept of non-monotonic reasoning.

b)Explain the concept of Dependency-Directed backtracking approach.

Or

c)What are Frames ? Explain with example.

d)Explain the procedure of goal stack planning with suitable example.

UNIT IV

5.a)What is Syntactic Analysis? Explain with suitable example.

b)Describe Unification grammars.

Or

c)Discuss about Case-Based Reasoning.

d) Write short notes on Expert Systems.

(Examination at the end of Second Year of 3 Year Course)
NOVEMBER/DECEMBER - 2006
Paper - V ---ARTIFICIAL INTELLIGENCE
Time:Three Hours Maximum.Marks:80M
Answer Question.No.1 compulsorily.
Answer ONE question from each Unit.
  1. a) What do you mean by state space search?
b)Clause form.
c)What are the issues in knowledge presentation?
d)What is hill climbing?
e)Define Backward reasoning.
f)Represent the fact described by the following tense as a set of wff”s in
predicate logic:
‘Marcus tried to assassinate Caesar’
g)Syntactic analysis.
h)What is the difference between forward and backward reasoning?

UNIT 1

2.a)Write AO’ algorithm with suitable example.
b)How do we define a problem as a state search? Example.

Or

c)What is depth-first search technique? Give algorithm compare it with breadth-first
technique.
d) What is “means-ends” analysis? Illustrate with an example.

UNIT II

3.a)Explain the issues in knowledge representation.
b)Briefly discuss property inherita algorithm.

Or

c)Describe about representation of instance “Isa” relationship.
d)Briefly explain about computable function and predicates.

UNIT III

4.a)Explain the concept of non-monotonic
b) Explain the concept of Dependency-Directed tracking approach.

Or

c)What are Frames? Explain with example.
d)Explain the procedure of Goal stack planning suitable example.

UNIT IV

5.a)What is Syntactic Analysis? Explain with suitable example.
b) Describe Unification grammars.

Or

c)Discuss about Case- Based Reasoning.
d) Write short notes on Expert Systems.

THE PEDANANDIPADU COLLEGE OF ARTS & SCIENCES, PEDANANDIPADU


(Examination at the end of Second Year of 3 Year Course)

MARCH - 2003

ARTIFICIAL INTELLIGENCE

Time:Three Hours Maximum.Marks:100M

PART A – (3X20=60 Marks)

Answer any THREE questions.

1.a) Define Physical Symbol System. State and pr0ve the corresponding hypothesis. (8)

b)With a suitable example explain how state space approach con be used to solve AI

problems (12)

2a)With suitable examples explain about ignorable, recoverable and irrecoverable

classes of problems. (10)

b)Explain the operation of bill climbing procedure and state the problems it has. (10)

3.a)With a suitable example explain how frames can be used to represent knowledge. (10)

b)Explain about property inheritance algorithm and show how it can be used for

default reasoning (10)

4.a)Show by resolution refutation that the following formula is a tautology.

(P ® Q) ® [ (R Ú P) ® (R Ú Q)] (8)

b)Consider the following statements: (12)

i)Whoever can read is literate.

ii)Dolphins are not literate.

iii)Some dolphins are intelligent and using, resolution prove the statement:

“Some who are intelligent can’t read”

5.a)Define Horn clause. Show how a Horn clause can be converted to PROLOG rule. (8)

b)With suitable examples show how ’cut’ and ‘fail’ predicates in PROLOG can be

used to control search. (12)

PART B --- (4X5=20 marks)

Answer any FOUR questions.

6.Explain the difference between forward and backward reasoning.

7.Define monotonic and partially commutative characteristics of a production system.

8.Briefly explain about means-ends analysis approach of solving problems.

9.Explain why scripts are called strong slot and filler structures.

10.Briefly explain about non-monotonic reasoning.

11.Write a PROLOG program to search for an element in a given list.

PART C --- ( 10X2=20marks)

13.Explain the following:

a)TURING TEST.

b)Heuristic function

c)Complimentary.

d)Dynamic programming principle.

e)And-Or graphs.
THE PEDANANDIPADU COLLEGE OF ARTS & SCIENCES, PEDANANDIPADU

NOVEMBER/DECEMBER - 2003

Third Semeter

Paper V-ARTIFICIAL INTELLIGENCE



Time:Three Hours Maximum.Marks:80M

Answer Question No.1 compulsorily, (8x2=16)

Answer ONE question from each Unit.(4x16=64)

All questions carry equal marks.

1.Write short notes on the following:

a)Forward reasoning>

b)Turing test.

c)Fuzzy logic

d)Granularity.

e)Heuristic search.

f)Clause form.

g) AND – OR graphs.

h)Backtraching.

UNIT 1

2.a)How do we define a problem as a state space search? Explain.

b)Explain the water jug problem and desctibe the production rules for the water jug

problem.

Or

c)What are the probem characteristics to be analyzed before trying for a solution?

Explain.

d)Analyse the traveling salesmen problem with respect to the characteristics discussed

above.

UNIT II

3.a)What are the approaches to knowledge representation? And what are the issues

involved in it?

b)Describe the method of resolution in predicate logic with an example.

Or

c)Consider the following sentences:

John likes all kinds of food.

Apples are food.

Chicken is food.

Anything anyone eats and isn’t killed by is food.

Bull eats peaqnuts and is still alive.

Sue eats everything Bull eats.

i)Translate these sentences into formulas in predicate logic.

ii)Convert the formulas of part a into clause form.

iii)Prove that John likes peanuts using resolution.

iv)Use resolution to answer the question “What food does Sue eat”?

UNIT III

4a)Explain the concept of nonmonotonic reasoning.

b)What is a semantic net? Explain, with an example, how partitioned semantic nets are

useful.

Or

c)What are frames? Give an example.

d) Explain how slots are used to describe objects and inheritance.

UNIT IV

5.a)Explain the cojncept of syntactic processing.

b) What is semantic analysis ? Explain.

Or

c)What is a rule based expert system? Explain with an example.

d)What are commonsense antologies?


(Examination at the end of Second Year of 3 Year Course)
MARCH - 2000
ARTIFICIAL INTELLIGENCE
Time:Three Hours Maximum.Marks:100M
PART A – (3X20=60 Marks)
Answer any THREE questions.

1.a)Write a PROLOG program for merge sort.
b)Explain the backtraackingusing fail and cut prodicates in PROLOG.

2.a)Distinguish the AI approach to solve a problem from a conventional computational
approach.
b)How to choose a problem solving strategy to solve a given problem? Explain.

3.a)Write A* algorithm and apply it on 8-puzzle problem.

4.Write unification algorithm and trace its operation on the following pairs of literals:
a) f(Marcus), f(Caesar)
b) f(x) and f(g(y))
c) f (Marcus, g(x,y)) and f(x,.g(Caesar, Marcus)).

5. Discuss the representational and reasoning aspects of Frames knowledge representation
scheme.
PART B –( 4X5=20M)
6.Write a PROLOG program for substitute (x,y,L1 L2) where L2 is the result of
substituting Y for, all occurrences of X In L1.

7.What factors determine the choice of direction of search?

8.Explain the principle of resolution with an example.

9.What are the various types production system? Explain.

10.Give good state space representation for missionaries and cannibals problem.

11.Describe the architecture of an Expert system.

PART- C ----(10 X2 = 20 marks)
12.What is an AI technique? Give example.

13.Write a PROLOG program to print a given list in the reverse order.

14.Compare BFS and DFS.

15.What is meant by problem reduction?

16.Explain natural deduction.

17.What is the difference between instances and is a relationships?

18.Write the properties of a good knowledge representation scheme.

19How to perform reasoning on semantic nets?

20.Briefly explain means-ends analysis.

21.What are the characteristics of a good control strategy?

(Examination at the end of Final Year of 3 Year Course)
MARCH - 1999
Paper - V ---ARTIFICIAL INTELLIGENCE
Tme: 3 Hours Max.Marks:70
Answer Question No.1 and ONE question from each Unit
Answer questions carry equal marks.
1.Explain the following terms in few sentences:
a)Dynamic data bases in prolog.
b)Conflict resolution.
c)Cell notaion for (a(bc D ))
d)Rules in prolog for tab (x) which prints x paces
e)Weak method.
f)Turing Test.
g)Game trees
h)AI Languages.
i)Control strategy
j)Assertion-time inferencing.
k)Default-reasoning.
l)Spatial reaoner.
m)Perception.
n)Skolemization.
UNIT I
2.a)Write a predicdate no-doubles (L1, L2 )which constructs L2 from L1 by removing
all repeated occurrences of any element.
Eg: ? - -no-doubles ([a,b, a,1,a,1,c],L2)
L2 = [a,b,1.c].
b)Give the list of all input output and arithmetic operations provided in PROLOG.
Using them write a program which prints the multiplication table for a given
Number.
Or
c) Write a prolog program to implement breadth first search.
d) Explain ‘CUT’ and ‘RETRACT’ predicates of PROLOG with examples.
e)Write a prolog program to reverse a given list.
UNIT II
3.a)Using constraint satisfaction, solve the following cryptarithmetic problem:
SEND
MORE
----------
MONEY
-----------
b)Derive the production rules for the water jug problem.
Or
c)Discuss about alpha-beta procedure.
d)Explain the characteristics of production systems.
UNIT III
4.a)Represent the following facts in predicate logic:
i)John only sees good movies
ii)People enjoy creativity.
iii)Some people make fun of everybody.
iv)An object which is heavy can n’t be moved , by a weak person.
v)Every student will be happy when examinations are just over.
b)Explain unification and resolution methods with examples.
Or
c)Explain connectionist AI and Symbolic AI.
d)Discuss learning in Neural Networks.
UNIT IV
5.a)Distinguish between forward and backward chaining.
b)Discuss the life-cycle of expert systems development.
Or
c)Build up the conceptual dependency structures for the following sentences:
i)Rama killed Ravana.
ii)While crossing sea, Hanuman saw a Cannnibal.
iii)American bombed Hiroshima.
d)Represent the following sentences using Semantic nets:
i)All students answered all questions in all possible ways.
ii)The score of Newzealand in todays Cricket match is 250 all out.


(Examination at the end of Final Year of 4 Year Course)
MARCH - 1998
Paper - V ---ARTIFICIAL INTELLIGENCE
Tme: 3 Hours Max.Marks:70
Answer Question No.1 and ONE question from each Unit
Answer questions carry equal marks.
1.a)Define heuristic.
b)problem space.
c)State space.
d) Perceptron.
e)neuron.
f)Boltzmann machine.
g)Hill climbing.
h)Problem reduction.
i)Means-Ends Analysis.
j)Isa relationship.
k)Inheritance.
l)Computable function.
m)Best-first search.
n)Connectionist AI.
UNIT I
2.a)Explain the use of out with an example in prolog.
b)Write a prolog program to find the minimum of a list of integers.

Or

c)Write a prolog program to implement depth-first search
d) Write a prolog program illustrating recursion.
UNIT II
3.a)Describe problem characteristics.
b)Explain what is a production system.

Or

c)Explain Hill climbing with an example.
d)Describe in detail Means-ends analysis.
UNIT II
4.a)Define Resolution.
b)Assume the following facts:
Steve only likes easy courses.
Science courses are hard.
All the courses in the basket weaving department are easy.
Bk 301 is a basket weaving course.
Use resolution to answer the question “What course would steve like”?

Or

c)Explain learning in neural networks with perceptrons.
d)Describe few applications of neural networks.
UNIT IV
5.a)Explain forward and backward reasoning with example.
b)Explain the architecture of an expert system
Or
c)Describe any two techniques fore matching.
d)Describe Semantic Nots with examples.


(Examination at the end of Final Year of 4 Year Course)
SEPTEMBER - 1998
Paper - V ---ARTIFICIAL INTELLIGENCE
Tme: 3 Hours Max.Marks:70
Answer Question No.1 and ONE question from each Unit
Answer questions carry equal marks.
1.Briefly explain the following:
a)Generate-and-test.
b)Inheritance
c)Constraint satisfaction.
d)Unification.
e)Instance relationship.
f)Back propagation network.
g)Chronological back tracking
h)Recursion.
i)Natural deduction.
j)Production rules.
k)Procedural knowledge
l)Declarative knowledge.
m)Give definition of script.
n)Semantic Net.
UNIT I
2.a)Write constraint satisfaction procedure.
b) Solve the crypt arithmetic problem.
CROSS
+ ROADS
-------------
DANGER
--------------
Or
c)Write the algorithm for problem reduction.
d)How problem reduction is different from Best-first search?
UNIT II
3.a)Write the algorithm for unification.
b)Consider the following sentences:
John likes all kinds of food.
Apples are food.
Chicken is food.
Anything anyone eats and isnot killed by is food.
Bill eats peanuts and is still alive.
Sue eats everything Bills eats.
Translate these sentences into formulas in predicate logic.
Or
c)Explain the working of Hop field Networks.
d) Describe what are recurrent networks.
UNIT III
4.a)Write a prolog program to implement power (X,N,V) where V equals Xn
b)Illustrate recursion with an example program to obtain factorial of given number.
Or
c)Write a prolog program to implement Best-first search.
UNIT IV
5.a)Describe the architecture of Expert system.
b)Explain conflict resolution.
Or
c)Explain conceptual dependency in detail with examples.