Artificial Intelligence
Artificial Intelligence
1. What is AI technique?
Artificial Intelligence (AI) is the study of how to make computers do things which, at the
moment, people do better.
It is a method that exploits knowledge that should be represented in such a way that:
· The knowledge captures generalizations.
· It can be understood by people who must provide it.
· It can be easily modified to correct errors and to reflect changes.
· It can be used in situations even if it is not accurate and complete.
· It helps to narrow the range of possibilities that is has to be considered.
2. What are the steps to be considered to solve a problem?
To solve a particular problem, the following steps are taken into account,
· Define the problem precisely.
· Analyze the problem.
· Isolate and represent the task knowledge that is necessary to solve a problem.
· Choose the best problem-solving techniques and apply it to a particular problem.
3. How state space representation is is related to the problem solving?
The structure of state space representation corresponds to the structure of problem solving in two
important ways:
· It allows for a formal definition of a problem as the need to convert some given situation
into some desired situation using a set of permissible operations.
· It permits to define the process of solving a particular problem as a combination of
known techniques. Search is a very important process in the solution of hard problems for
which no more direct techniques are available.
4. What is production systems?
A production system consists of:
· A set of rules that describes the operations and applicability of the rule.
· One or more knowledge/databases that contains the informations appropriate for the
particular task.
· A control strategy that specifies the order in which the rules will be compared to the
database and a way of resolving the conflicts that arise when several rules match at once.
· A rule applier.
5. Write the Breadth-First Search algorithm.
1. Create a variable called NODE-LIST and set it to the initial state.
2. Until the goal state is found or NODE-LIST is empty:
a) Remove the first element from the NODE-LIST and call it E. If NODE-LIST was empty,
quit.
b) For each way that each rule can match the state described in E do,
i. Apply the rule to generate a new state.
ii. If the new state is a goal state, quit and return this state.
iii. Otherwise, add the new state to the end of NODE-LIST.
6. What are the advantages of Breadth-First Search algorithm?
· Breadth-first search will not get trapped by following a single, unfruitful path for a very
long time.
· If there is a solution, then breadth-first search is guaranteed to find it.
· Longer paths are never explored until all shorter ones have already been examined.
7. Write the Depth-First Search algorithm.
1. If the initial state is a goal state, quit and return success.
2. Otherwise, do the following until success or failure is signaled.
a) Generate the successor, E, of the initial state. If there are no more successors, signal
failure.
b) Call Depth-first search with E as the initial state.
c) If success is returned, signal success. Otherwise continue in this loop.
8. What are the advantages of Depth-First Search algorithm?
· Depth-first search requires less memory since only the nodes on the current path are
stored.
· It may find the solution without examining much of the search space at all. The process
can be stopped once the solution is found.
9. What are the different dimensions to be analyzed for a problem?
· Is the problem decomposable into a set of independent smaller or easier sub problems?
· Can solution steps be ignored or at least undone if they prove unwise?
· Is the problem’s universe predictable?
· Is the good solution to the problem obvious without comparison to all other possible
solutions?
· Is the desired solution a state of the world or a path to the state?
· Is a large amount of knowledge absolutely required to solve a problem, or is knowledge
important only to constraint the search?
· Will the solution of the problem requires interaction between the computer and a person?
10. What are the three classes of problem?
· Ignorable, in which solution steps can be ignored.
· Recoverable, in which solution steps can be undone.
· Irrecoverable, in which solution steps cannot be undone.
11. How is production system classified?
· Monotonic production system- It is a production system in which the application of a
rule never prevents the later application of another rule that could also have been applied
at the time the first rule was selected.
· Partially commutative production system- It is a production system with the property
that if the application of a particular sequence of rules transforms state x and state y, then
any permutations of those rules that is allowable also transforms state x into state y.
· Commutative production system- It is a production system that is both monotonic and
partially commutative.
12. What are the important issues of general-purpose search techniques?
· The direction in which to conduct the search (forward versus backward reasoning).
· How to select applicable rules (matching).
· How to represent each node in the search process (the knowledge representation problem
and the frame problem).
13. What are the problems faced by hill-climbing search?
Hill-climbing often get stuck for the following reasons :
· Local maxima – A local maxima is a peak that is higher than each of its neighboring
states, but lower than the local maximum. Hill climbing algorithm that reach the vicinity
of a local maximum will be drawn upwards towards the peak, but will then be stuck with
nowhere else to go.
· Ridges – Ridges result in a sequence of local maxima that is very difficult for greedy
algorithms to navigate.
· Plateau – a plateau is an area of state space landscape where the evaluation function is
flat. A hill-climbing search might be unable to find its way off the plateau.
14. How can we avoid ridge and plateau in hill climbing? (NOV/DEC 2012)
Ridges result in sequence of local maxima that is very difficult for greedy algorithm to navigate.
A plateau is an area to the state space landscape where the evaluation function is flat. It can be a
flat local maximum, from which no uphill exit exists, or a shoulder, from which it is possible to
make progress. In case of plateau a sideways move is allowed in hope that the plateau is really a
shoulder. If a sideways move is always allowed an infinite loop might occur. So a limit is placed
on the number of consecutive sideways moves allowed.
15. List the criteria to measure the performance of search strategies. (MAY/JUNE 2014)
The criteria to measure the performance of search strategies are:
· Completeness: is the algorithm guaranteed to find a solution when there is one?
· Optimality: does the strategy find the optimal solution?
· Time complexity: how long does it take to find a solution?
· Space complexity: how much memory is needed to perform the search?
16. Define heuristics. Why are heuristics crucial for the efficient design of an expert system?
Heuristics is the study of the methods and rules of discovery and invention. In state space search,
heuristics define the rules for choosing branches in a state space that are most likely to lead to an
acceptable solution. There are two cases in AI searches when heuristics are needed:
· The problem has no exact solution. For example, in medical diagnosis doctors use
heuristics to choose the most likely diagnoses given a set of symptoms. (medical expert
systems)
· The problem has an exact solution but is too complex to allow for a brute force solution.
Key Point: Heuristics are fallible. Because they rely on limited information, they may lead to a
suboptimal solution or to a dead end.
17. State the significance of using heuristic functions. (NOV/DEC 2011)
A heuristic function is used to estimate the cost of cheapest path from node n to a goal node.
18. What is AND-OR graphs?
· AND-OR graph (or tree) are useful for representing the solution of problems that can be
solved by decomposing them into a smaller problems.
· One AND arc may point to any number of successor nodes.
· Several arcs may emerge from a single node, indicating a variety of ways in which the
problem can be solved.
19. What is Constraint satisfaction?
Constraint satisfaction is a search procedure that operates in a space of constraint sets. The initial
state contains the constraints that are originally given in the problem description. A goal state is
any state that has been constrained “enough”, where “enough” must be defined for each problem.
20. What are the steps involved in Constraint satisfaction?
· Constraints are discovered and propogated as far as possible throughout the system.
· If the union of constraints defines a solution, then quit and report the solution.
· If the union of constraints defines a contradiction, then return failure.
· If neither of the above occurs, then it is necessary to make a guess at something in order
to proceed.
21. What are the significant considerations of Constraint satisfaction?
· Constraints are propagated by using rules that correspond to the properties of arithmetic.
· A value is guessed for some letter whose values are not determined.
22. What are the different kinds of constraints?
· Simple Constraints- They list possible values for a single object.
· Complex Constraints- They describe relationships between or among objects.
23. Define a CSP.
A constraint satisfaction problem or CSP is defined as a set of variables, X1, X2,……,Xn and a set
of constraints C1, C2,……,Cm. Each variable Xi has a nonempty domain Di of possible values.
Each constraint Ci involves some subset of the variables and specifies the allowable combinations
of values for that subset. A state of the problem is defined by an assignment of values to some or
all of the variables. An assignment that does not violate any constraints is called a consistent or
legal assignment and a solution to a CSP is a complete assignment that satisfies all the
constraints.
24. What is means-end analysis?
The means-end analysis process centers around the detection of differences between the current
state and the goal state. Once the difference is isolated, an operator that reduces the differences
must be found but cannot be applied to the current state.
25. What is operator subgoaling?
The kind of backward chaining in which operators are selected and then subgoals are setup to
establish the preconditions of the operators is called operator subgoaling.
PART-B
1. (i) Describe a state space in which iterative deepening search performs much worse than depth-
first search.
(ii) Prove that the breadth first search is a special case of uniform cost search.(MAY/JUNE 2012)
2. Explain the Control strategies in detail.
3. Explain how different problem characteristics are analyzed in detail.
4. Explain production systems and discuss the major issues in the design of search programs.
5. What is heuristic search technique? Explain Hill climbing in detail.
6. Explain Best-first search algorithm in detail.
7. Write algorithm for the following:
i. Generate-and-test
ii. A* Algorithm
iii. Agenda-driven search
iv. Means-end analysis
8. Explain problem-reduction algorithm in detail.
9. Explain AO* algorithm with a suitable example. State the limitations in the algorithm.
(APRIL/MAY 2011, NOV/DEC 2011& NOV/DEC 2012)
10. Explain the constraint satisfaction procedure to solve the crypt arithmetic problem.
C R O S S
+ R O A D S
D A N G E R (NOV/DEC 2011)
UNIT-2
PART-A
1. What is Knowledge representation?
Knowledge representation is the field of artificial intelligence (AI) dedicated to representing
information about the world in a form that a computer system can utilize to solve complex tasks
such as diagnosing a medical condition or having a dialog in a natural language.
2. What are the levels of knowledge representation?
· Knowledge level, at which facts such as agent’s behaviors and current goals are described.
· Symbol level, at which representation of objects at the knowledge level are defined in terms
of symbols that can be manipulated by the programs.
3. Define facts.
Facts are truth in some relevant world and they are represented in some chosen formalism.
4. What are forward and backward representation mappings?
The forward representation mapping maps from facts to representation whereas backward
representation mapping maps from representation to facts.
5. What are the properties of a good system for the representation of knowledge?
Representational Adequacy- the ability to represent all of the kinds of knowledge that are
needed in that domain.
Inferential Adequacy- the ability to manipulate the representational structures in such a way as
to derive new structures corresponding to new knowledge inferred from old.
Inferential Efficiency- the ability to incorporate into the knowledge structure additional
information that can be used to focus the attention of the inference mechanisms in the most
promising directions.
Acquisitional Efficiency- the ability to acquire new information easily.
6. What are the issues in knowledge representation?
· Are any attributes of objects so basic that they occur in almost every problem domain? If so,
What are the attributes?
· Are there any important relationships that exist among attributes of objects?
· At what level should knowledge be represented? Is there a good set of primitives into which
all knowledge can be broken down? Is it helpful to use such primitives?
· How should set of objects be represented?
· Given a large amount of knowledge stored in a database, how can relevant parts be accessed
when they are needed?
7. Define predicate logic.
Predicate logic is an extension of propositional logic to formulas involving terms and predicates.
It is un-decidable but serves as a useful way of representing and manipulating some of the kind of
knowledge that an AI system might need.
8. Represent the following sentence in predicate form “All the children likes sweets”.
(NOV/DEC 2012)
"x Likes (x,sweets)
9. Define resolution.
· Resolution is a procedure which gains efficiency from the fact that it operates on statements
that have been converted to a very convenient standard form.
· It is a simple iterative process in which two parent clauses are compared, yielding a new
clause that has been inferred from them.
10. State Herbrand’s theorem.
· To show that a set of clauses S is unsatisfiable, it is necessary to consider only interpretations
over a particular set, called the Herbrand universe of S.
· A set of clauses S is unsatisfiable if and only if a finite subset of ground instances (in which
all bound variables have had a value substituted for them) of S is unsatisfiable.
11.What is the significance in using the unification algorithm?(NOV/DEC 2012)
In order to apply the rules of inference, an inference system must be able to determine when two
expressions match. Unification used for determining the substitutions needed to make two
predicate calculus expressions match.
· All variables must be universally quantified.
· Existentially quantified variables may be eliminated by replacing them with constants
that make the sentence true.
For example, in ∃X mother(X,bill), we can replace X with a constant designating bill's mother,
ann, to get: mother(ann, bill).
The UNIFY algorithm takes two sentences and returns a unifier for them if one exists:
UNIFY(p,q)=q where SUBST(q,p)=SUBST(q,q)
The problem arises only because two sentences happen to use the same variable name x. the
problem can be avoided by standardizing apart one of the two sentences being unified, which
means renaming its variables to avoid name clashes.
12. Is games appeared to be a good domain to explore machine intelligence? Justify.
Yes, Games appeared to be a good domain to explore machine intelligence for the following
reasons:
· They provide the structured task I which it is very easy to measure success of failure.
· They did not obviously require large amounts of knowledge for simpler games.
13. What is MINIMAX Search Procedure?
The MINIMAX Search Procedure is a depth-first, depth-limited search procedure. The idea is to
start at the current position and use the plausible-move generator to generate the set of possible
successor positions.
14. What is Alpha-Beta pruning?
The problem with minimax search is that the number of game states it has to examine is
exponential in the number of moves. Unfortunately, exponent cannot be eliminated but can be
effectively cut it in half. By performing pruning, large part of the tree can be eliminated from
consideration.
· α : the value of the best(i.e.,highest-value) choice we have found so far at any
· β: the value of best (i.e., lowest-value) choice we have found so far at any choice point
along the path of MIN.
15. Write Depth-First Iterative Deepening.
a. Set SEARCH-DEPTH=1
b. Conduct a depth-first search to a depth of SEARCH-DEPTH. If the solution path is
found, then return it.
c. Otherwise, increment SEARCH-DEPTH by 1 and go to step b.
16. Write Iterative-Deepening –A* Algorithm.
a. Set THRESHOLD=the heuristic evaluation of the start state.
b. Conduct a depth-first search, pruning any branch when its total cost function (g+h’)
exceeds THRESHOLD. If the solution path is found during the search, return it.
c. ‘Otherwise, increment THRESHOLD by the minimum amount it was exceeded during
the previous step, and then go to step b.
17. Give some examples of structured representation of knowledge.
· Semantic Nets
· Frames
· Scripts
· Conceptual dependency
· CYC
18. Define Semantic Nets.
CS6659-Artificial Intelligence
Dept of CSE/IT 2015-2016
In Semantic Net, information is represented as a set of nodes connected to each other by a set of
labeled arcs, which represent relationships among the modes.
19. What are frames?
A frame is a collection of attributes and associated values that describe some entity in the world.
20. What is frame language?
The idea of a frame system as a way to represent declarative knowledge has been encapsulated in
a series of frame-oriented knowledge representation languages, whose features have evolved and
been driven by an increased understanding of the sort of representation issues.
Eg. KRL,FRL,KRYPTON,CYCL etc.
21. Define Conceptual Dependency.
Conceptual Dependency is a theory of how to represent the kind of knowledge about events that
is usually contained in natural language sentences.
22. State the goal of Conceptual dependency.
The goal is to represent the knowledge in a way that,
· Facilitates drawing inferences from the sentences.
· Is independent of the language in which the sentences were originally stated.
23. What are scripts?
A script is a structure that describes the stereotyped sequence of events in a particular context. A
script consists of a set of slots and associated with each slot may be some information about what
kind of values it may contain as well as a default value to be used if no other information is
available.
24. What is CYC?
CYC is a very large knowledge base project aimed at capturing human commonsense knowledge.
The goal of CYC is to encode the large body of knowledge that is so obvious that it is easy to
forget to state it explicitly.
25. What are the fundamental problems of Structured knowledge representation?
· Knowledge acquisition: Learning a schema system is long, tedious, and ad hoc process.
· Context Recognition (The Frame problem): Many problems are easily solved when the
context is known. Recognizing the correct context can be very difficult.
PART-B
1. Explain in detail the approaches to Knowledge Representation.
2. Explain the various issues in knowledge Representation in detail.
3. Differentiate predicate and propositional logic. Explain predicate logic with suitable illustrations.
4. Explain the unification algorithm used for reasoning under predicate logic with an example.
(APRIL/MAY 2011)
5. Consider the following facts
a. Team India
b. Team Australia
c. Final match between India and Australia
d. India scored 350 runs, Australia scored 350 runs, India lost 5 wickets, Australia lost 7
wickets.
e. The team which scored the maximum runs wins.
f. If the scores are same the team which lost minimum wickets wins the match.
Represent the facts in predicate, convert to clause form and prove by resolution “India wins the
match”. (NOV/DEC 2011)
6. Consider the following facts and represent them in predicate form:
F1. There are 500 employees in ABC company.
F2. Employees earning more than Rs. 5000 pay tax.
F3. John is a manager in ABC company.
F4. Manager earns Rs. 10,000.
Convert the facts in predicate form to clauses and then prove by resolution: “John pays tax”.
(NOV/DEC 2012)
7. Explain with an example concept of resolution. (NOV/DEC 2012)
8. Explain MINIMAX Search Procedure algorithm with suitable illustration.
9. Explain alpha-beta pruning in detail along with example.
10. Explain various structured knowledge representations in detail.
Part- A
1. What factors determine the selection of forward or backward reasoning approach
for an AI problem? (APRIL/MAY 2011)
Forward chaining is an example of the general concept of data-driven reasoning-
ie) reasoning in which the focus of attention starts with the known data. It can be used
within an agent to derive conclusions from incoming percepts, often without a query in
mind.
Backward chaining is a form of goal-directed reasoning. It is useful for answering
specific questions such as “What shall I do now?” and “Where are my keys?” As the
name suggests, it works backwards from the goal.
2. Define Inference.
Inference is the act or process of deriving logical conclusions from premises
known or assumed to be true. The conclusion drawn is also called as idiomatic.
3. Define Forward chaining.
The problem solver begins with the given facts and a set of legal moves or rules
for changing the state. Search proceeds by applying rules to facts to produce new facts.
This process continues until (hopefully) it generates a path that satisfies the goal
condition.
Data-driven search uses knowledge and constraints found in the given data to search
along lines known to be true. Use data-driven search if:
Ø All or most of the data are given in the initial problem statement.
Ø There are a large number of potential goals, but there are only a few ways to use
the facts and the given information of a particular problem.
Ø It is difficult to form a goal or hypothesis.
4. Define Backward chaining.
The problem solver begins with the goal to be solved, then finds rules or moves
that could be used to generate this goal and determine what conditions must be true to use
them. These conditions become the new goals, subgoals, for the search. This process
continues, working backward through successive subgoals, until (hopefully) a path is
generated that leads back to the facts of the problem.
Goal-driven search uses knowledge of the goal to guide the search. Use goal-driven
search if;
Ø A goal or hypothesis is given in the problem or can easily be formulated.
(Theorem proving; medical diagnosis; mechanical diagnosis)
Ø There are a large number of rules that match the facts of the problem and would
thus produce an increasing number of conclusions or goals. (inefficient)
Ø Problem data are not given but must be acquired by the problem solver. (e.g.,
medical tests determined by possible diagnosis)
5. List various knowledge representation schemes.
Ø Rules
Ø Semantic nets
Ø Schemata (frames, scripts)
Ø Logic
6. What is semantic network
Formalism for representing information about objects, people, concepts and
specific relationship between them.
7. Define inheritance
Inheritance mechanism allows knowledge to be stored at the highest possible
level of abstraction which reduces the size of knowledge base.
8. Mention the advantages of Production based system.
Ø Simple and easy to understand.
Ø Straightforward implementation in computers possible.
Ø Formal foundations for some variants.
9. What are the disadvantages of Production Rules
· Simple implementation are very difficult
· Some types of knowledge are not easily expressed in such rules.
· Large sets of rules become difficult to understand and maintain.
10. What are the advantages of frame based system.
Ø Fairly intuitive for many applications
o Similar to human knowledge organization.
o Suitable for casual knowledge.
o Easier to understand than logic or rules.
Ø Very flexible.
11. Mention the issues of fame based system
Ø It is tempting to use fames as definitions of concepts
o Not appropriate because there may be valid instances of a concept that do
not fit the stereotype.
o Exceptions can be used to overcome this.
Ø Inheritance
o Not all properties of a class stereotype should be propagated to subclasses.
o Alternation of slots can have unintended consequences in subclasses.
12. Define frame.
A frame is a data structure with typical knowledge about a particular object or
concept. Each frame has its own name and a set of attributes associated with it.
Ex: Name, weight, age are slots in the frame person.
13. Give the full specification of a Bayesian network. (MAY/JUNE 2013)
A Bayesian network is a directed graph in which each node is annotated with quantitative
probability information. The full specification is as follows:
Ø A set of random variables makes up the nodes of the network. Variables may be
discrete or continuous.
Ø A set of directed links or arrows connects pairs of nodes. If there is an arrow from
node X to node Y, X is said to be a parent of Y.
Ø Each node X, has a conditional probability distribution P(Xi|Parents(Xi)) that
quantifies the effect of the parents on the node.
Ø The graph has no directed cycles (and hence a directed, acyclic graph or DAG)
14. What do you mean by Hybrid Bayesian network? (NOV/DEC 2012)
A network with both discrete and continuous variables is called a hybrid Bayesian
network. Two kinds of distributions are needed to specify a hybrid network:
Ø The conditional distribution for a continuous variable given discrete or continuous
parents.
Ø The conditional distribution for a discrete variable given continuous parents.
15. Define Dempster-Shafer theory. (APRIL/MAY 2011)
The Dempster-Shafer theory uses interval-valued degrees of belief to represent an
agent’s knowledge of the probability of a proposition. The Dempster-Shafer theory is
designed to deal with the distinction between uncertainty and ignorance. Rather than
computing the probability of a proposition, it computes the probability that the evidence
supports the proposition. This measure of belief is called a belief function, written as
Bel(X).
16. Define Bayes’ rule. (NOV/DEC 2012& MAY/JUNE 2013)
The simple equation of Bayes’ rule underlies all modern AI systems for probabilistic
inference.
The product rule can be written in two forms because of the commutativity of
conjuction.
P (a Ù b) = P(a|b) . P(b)
P (a Ù b) = P(b|a) . P(a)
Equating the two right hand sides and dividing by P(a), the Bayes’ rule is given as
P(b|a) =P(a|b)P(b)
P(a)
17. Define Certainty factors.
MYCIN represents most of its diagnostic knowledge as a set of rules. Each rule
has associated with it a certainty factor, which is a measure of the extent to which the
evidence that is described by the antecedent of the rule supports the conclusion is given
in the rule’s consequent.
18. Write the values of certainty factor
Ø Positive CF- evidence supports the hypothesis
Ø CF=1- evidence definitely proves the hypothesis
Ø CF=0- there is no evidence or the belief and disbelief cancel each other
Ø Negative CF- evidence favours negation of the hypothesis- more reason to
disbelieve the hypothesis than believe it.
19. Write briefly about fuzzy set theory.
Fuzzy set theory is a means of specifying how well an object satisfies a vague
description. For example, consider the proposition "He is tall." This proposition cannot
be answered with an exact "true" or "false" because it is relative. That is, if the person is a
three-year old and standing alongside a baby, then he is tall. But if the person is standing
beside his father. Then he is not tall. Therefore, the degree of tallness needs to be
considered here. Fuzzy set theory treats Tall as a fuzzy predicate and says that the truth
value of Tall(Nate) is a number between 0 and 1, rather than being just true or false. The
name "fuzzy set" derives from the interpretation of the predicate as implicitly defining a
set of its members-a set that does not have sharp boundaries.
20. What is Noisy-OR relation? Give an example.
Uncertain relationships can often be characterized by so-called "noisy" logical
relationships. The standard example is the noisy-OR relation. In propositional logic, we
might say that Fever is true if and only if Cold, Flu, or Malaria is true. The noisy-OR
model allows for uncertainty about the ability of each parent to cause the child to be true the causal relationship between parent and child may be inhibited, and so a patient could
have a cold, but not exhibit a fever.
The model makes two assumptions:
Ø It assumes that all the possible causes are listed. (Leak node can be added that
covers "miscellaneous causes.")
Ø It assumes that inhibition of each parent is independent of inhibition of any other
parents: for example, whatever inhibits Malaria from causing a fever is
independent of whatever inhibits Flu from causing a fever.
21. Give the full specification of a Bayesian network. (MAY/JUNE 2013)
A Bayesian network is a directed graph in which each node is annotated with quantitative
probability information. The full specification is as follows:
Ø A set of random variables makes up the nodes of the network. Variables may be
discrete or continuous.
Ø A set of directed links or arrows connects pairs of nodes. If there is an arrow from
node X to node Y, X is said to be a parent of Y.
Ø Each node X, has a conditional probability distribution P(Xi|Parents(Xi)) that
quantifies the effect of the parents on the node.
Ø The graph has no directed cycles (and hence a directed, acyclic graph or DAG)
22. What are the various kinds of knowledge?
· Declarative
o A symbolic expression of competence
o Declarative knowledge is abstract
o Declarative knowledge is used to communicate and to reason
· Procedural
o A series of steps to solve a problem
o A compiled expression of knowledge
· Reactive
o Stimulus- response
Part-B
1. Describe the various issues in knowledge representation.
2. How does an inference engine work in a frame based system?
3. Explain the need of fuzzy set and fuzzy logic with example. (MAY/JUNE 2012 &
NOV/DEC 2013)
4. Explain the method of performing exact inference in Bayesian networks. (NOV/DEC
2012)
5. Explain in detail about forward and backward chaining with suitable example.
6. Explain knowledge representation in detail with example.
7. Explain Rule based system with example.
8. Explain Dempster - Shafer theory with example.
9. i. Write the enumeration algorithm for answering queries on Bayesian networks. (8)
ii. Describe a method for constructing Bayesian networks. (8) (MAY/JUNE 2013)
10. Write notes on:
i) Fuzzy reasoning
ii) Bayesian probability
iii) Certainty factors
Part- A
1. Define planning.
Planning is arranging a sequence of actions to achieve a goal.
Ex: Navigation, Language processing.
2. What is Non Linear Plan.
Ø Non linear planning uses goal set instead of goal stack.
Ø Include in the search space all possible subgoal orderings
o Handles goal interactions by interleaving.
3. What are the advantages and disadvantages of Non linear plan
Advantages:
· Non linear planning is sound, complete.
· Optimal with respect to plan length(depending on search strategy employed)
Disadvantages:
· Larger search space, since possible goal orderings may have to be considered.
· Somewhat more complex algorithms.
4. Define STRIPES.
STRIPES (Stanford Research Institute Problem Solver) is an automated planner.
This language is the base for most of the languages for expressing automated planning
problem instances. A STRIPS instance is composed of:
An Initial state, the specification of goal states, A set of actions (each action
includes- Preconditions and post conditions).
5. Mention the components of Planning system.
Ø Choosing Rules to Apply
Ø Applying Rules
Ø Detecting a Solution
Ø Detecting Dead Ends
Ø Repairing a almost correct solution
6. What is Goal Stack?
One of the earliest technique to be developed for solving compound goals that
may interact was the use of a goal stack. This was the approach used by STRIPS. In this
method, the problem solver makes use of a single stack that contains both goals and
operators that have been proposed to satisfy those goals.the problem solver also relies on
a database that describes as PRECONDITION,ADD, and DELETE lists.
7. List out the various planning techniques. (MAY/JUNE 2014)
The various planning techniques are:
Ø Planning with state-space search
® Forward state-space search
® Backward state-space search
Ø Partial order planning
® Partial-order planning with unbound variables
Ø Planning with propositional logic
Ø Hierarchical task network planning
CS6659-Artificial Intelligence
Dept of CSE/IT 2015-2016
Ø Planning and acting in nondeterministic domains
® Sensorless planning
® Conditional planning
® Execution monitoring and replanning
® Continuous planning
8. What are the basic operations in the Blocks world?
stack(X,Y): Put block X on block Y
unstack(X,Y): remove block X from block Y
pickup(X): pickup block X
putdown(X): put block X on the table
9. Distinguish between problem solving and planning. (NOV/DEC 2012)
Problem solving is a mental process which is concluding part of a larger problem
process that includes problem finding and problem shaping where problem is defined as
state of desire for reaching a definite goal from a present condition that either is not
directly moving toward the goal or stepping towards the goal. Planning systems are
problem solving algorithms that operate on explicit propositional representations of states
and actions. These representations make possible the derivation of effective heuristics
and development of powerful and flexible algorithms for solving problems.
10. What is a consistent plan? (MAY/JUNE 2013)
A consistent plan is one in which there are no cycles in the ordering constraints
and no conflicts with causal links. A consistent plan with no open preconditions is a
solution.
11. Define contingency plan. (MAY/JUNE 2012 & MAY/JUNE 2014)
Conditional planning is also known as contingency planning, this approach deals with
bounded indeterminacy by constructing a conditional plan with different branches for the
different contingencies that could arise.
12. What is learning?
An agent tries to improve its behaviour through observation, reasoning, or reflection.
Ø Learning from experience
Ø Forecasting
Ø Theories
13. Explain the concept of learning from example. (APRIL/MAY 2011)
The idea behind learning is that percepts should be used not only for acting but also for
improving the agent’s ability to act in the future.
14. Define Machine learning.
A computer program is said to learn from experience E with respect to some class of
tasks T and performance P, if its performance at the tasks improves with the experiences.
15. Explain Machine learning with an example.
Ø Learns from past experience.
Ø Improves the performance of intelligent programs.
16. Mention the advantages of Machine Learning.
· Alleviate knowledge acquisition bottleneck
o Does not require knowledge engineers.
o Scalable in constructing knowledge base.
· Adaptive
o Adaptive to the changing conditions.
o Easy in migrating to new domains.
17. What is generalization
The number of distinct objects that might potentially be stored can be very large.
To keep the number of stored objects down to a manageable level, some kind of
generalization is necessary.
18. Give examples for planning problem.
· Route search
o Find a route from source to destination.
· Military operations
o Develop an air campaign.
· Game playing
o Plan the behaviour of computer controlled player.
· Resources control
o Plan the stops of several of elevators in a skyscraper building.
19. What are the components of a Learning agent
Ø Learning element
Ø Performance element
Ø Critic
Ø Problem generator
20. What are the various forms of learning?
· Supervised learning
· Unsupervised learning
· Reinforcement learning
21. Define concept- learning.
The idea of producing a classification problem that can evolve its own class
definitions is appealing. This task of constructing class definition is called
Part-B
1. Explain STRIPES mechanism with example.
2. Explain the various components of a Planning system.
3. What do you mean by plan generation? Explain Basic plan generation system with an
example.
4. Briefly explain the advanced plan generation system.
5. Distinguish:
i) Production based system
ii) Frame based system
6. Explain the concept of planning with the Block world example.
7. Discuss simple planning using a Goal Stack.
8. Write briefly the concept of Learning.
9. Explain Machine learning and Adaptive learning with example.
10. Solve the blocks world problem using strips. How does it act as a planning system?
Part-A
1. Define Expert systems.
An expert system is software that attempts to reproduce the performance of one or
more human experts, most commonly in a specific problem domain. Developed via
specialized software tools called shells.
Ex: Diagnostic applications, servicing.
2. Explain expert system development
Ø Problem definition
Ø System design (knowledge acquisition)
Ø Formalization (logical design, tree structures)
Ø System implementation (building a prototype)
Ø System validation
3. What are the characteristics of Expert system?
· Inferential processes
o Uses carious reasoning techniques
· Heuristics
o Decisions based on experience and knowledge
· Waterman
o Expertise
o Depth
o Symbolic reasoning
o Self knowledge
4. What are the limitations of Expert systems
Ø Not widely used or tested.
Ø Limited to relatively narrow problems
Ø Cannot readily deal with “mixed” knowledge
Ø Possibility of error
Ø Cannot refine own knowledge base
Ø Difficult to maintain
Ø May have high developed costs
Ø Raise legal and ethical concerns
5. What are the capabilities of Expert system.
Ø Explore impact of strategic goals
Ø Impact of plans on resources
Ø Integrated general design principles and manufacturing limitations\
Ø Provide advice on decisions
Ø Monitor quality and assist in finding solutions
Ø Look for causes and suggest solutions
6. What is a shell
A piece of software which contains:
· The user interface
· A format for declarative knowledge in the knowledge base
· An interface engine
7. What are the various types of Expert systems
· Rule base expert systems
· Frame based expert systems
CS6659-Artificial Intelligence
· Hybrid systems
· Model based systems
· Ready-made systems
Dept of CSE/IT 2015-2016
· Real-time expert systems
8. Mention the 3 major components of an Expert system
· Knowledge base
· Inference engine
· User interface
9. What is knowledge acquisition?
it provides convenient and efficient means of capturing and storing all
components of the knowledge base.
Knowledge Base
Knowledge
Acquisition
Expert
10. What are the advantages of Expert systems
Ø Easy to develop and modify
Ø The use of satisficing
Ø The use of heuristics
Ø Development by knowledge engineers and users
11. Mention applications of Expert system.
· Credit granting
· Information management and retrieval
· Hospital and medical facilities
· Loan analysis
· Virus detection
· Repair and maintenance
· Warehouse optimization
12. What is heuristic?
Heuristics are formalized as rules for choosing those branches in a state space that
are most likely to lead to an acceptance problem solution. Problem solver employ
heuristics in two basic situations:
· A problem may not have an exact solution because of inherent ambiguity
in the problem statement or available data.
· A problem may have an exact solution, but the computational cost of
finding it may be prohibitive.
13. Define MYCIN
It is a program for treating blood infections. MYCIN is used to diagnose patients
based on reported symptoms and medical test results. The program could further
information concerning the patient, as well as suggest additional laboratory tests, to
arrive at a probable diagnosis, after which it would recommend a course of treatment.
14. Define DART
DART (Dynamic Analysis and Replanning Tool) is an program used to optimize
and schedule the transportation of supplies or personnel and solve other logistical
problems.DART uses intelligent agents to aid decision support systems. It integrates a
CS6659-Artificial Intelligence
Dept of CSE/IT 2015-2016
set of intelligent data processing agents and database management systems to give
planners the ability to rapidly evaluate plans for logistical feasibility.
15. Describe how Expert systems perform inference
The brain of an expert system is the inference engine that provides a methodology
for reasoning about information in the knowledge base. Inference can be performed using
semantics networks, production rules, and logic statements.
16. What are real time expert system
In real time expert system the conclusions are derived fast so a process can be
impacted immediately. They are used in quality control and robotics(ex: to correct a mal
function).
17. What are the classifications of expert systems?
Classification is based on expertness or purpose
Ø An assistant
Ø A colleague
Ø A true expert
18. Mention the features of Expert system.
· Dealing with uncertainty
o Certainty factors
· Explanation
· Ease of modification
· Transportability
· Adaptive learning
19. Write the steps to create an Expert system
Ø Extracting knowledge and methods from the expert (knowledge acquisition).
Ø Reforming knowledge/methods into an organised form (knowledge
representation).
20. What are the categories of knowledge
· Declarative
o Descriptive, facts, shallow knowledge
· Procedural
o Way things work, tell how to make inferences
· Semantic
o Symbols
· Episodic
o Autobiographical, experimental
· Meta-knowledge
o Knowledge about the knowledge
Part- B
1. What are Expert systems? Explain in detail.
2. Elaborately explain the process of knowledge acquisition.
3. i) Explain the various stages of Expert system development.
ii) Explain heuristics with a example
4. Draw the schematic diagram of an expert system. Explain all the relevant components.
5. i) Explain the components of expert systems with a neat diagram.
ii) Discuss the features of Expert systems
6. Discuss the advantages and limitations of expert systems.
7. i) Explain briefly about Meta knowledge
ii) Explain the role of expert system
8. Write short notes on:
a. MYCIN and its applications
b. DART and its applications
9. Write notes on:
i) Expert system shell
ii) Limitations of Expert systems
10. Explain the pitfalls in selecting an expert system.
Comments
Post a Comment