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

Popular posts from this blog

Zoho Second round - adding a digit to all the digits of a number