MLM-III

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING3.If solution found, quit. Otherwise return to step 1.HILL CLIMBING Variant of generate-and-test in which feedback from the testprocedure is used to help the generator decide which direction to move in the searchspace.  Simple Hill Climbing  Steepest Ascent Hill ClimbingSimple Hill ClimbingSteps:  Evaluate the initial state. If it is a goal state then quit, else make current state as initial state.  Select a new operator that could be applied to this state and generate a new state.  Evaluate the new state. (i) If it is a goal state, then return it and quit. (ii) If it is not a goal state ,but better than current state, then make it as current state. (iii) If it is not better than the current state, then continue in the loop.Eg. puzzle of 4 colored blocks.Steepest –Ascent Hill climbingIn this ,it considers all the moves from the current state and selects the best one as thenext state. This method is called steepest –ascent hill climbing or gradient search.Steps  Evaluate the initial state. If it is a goal state then quit, else make current state as initial state.  Loop until a solution is found (i) Let SUCC be any possible successor of the current state. (ii) For each operator that applies to the current state do: (a)Apply the operator and generate a new state. (b)Evaluate the new state. If it is a goal state then return and quit, else compare it to SUCC. If its better ,set SUCC as initial state, else leave it. (c)If SUCC is better than current state, then set current state to SUCC.Example:8 queens problemBoth the above hill climbing searches get stuck for the following reasons.1.local maxima2.plateau3.ridgeWays to deal with those problems:(1)Backtrack to some earlier node and try other direction.(2)Make a big jump & try to go to a new section.(3)Apply 2 or more rules. 151

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGAdded to this there are other hill climbing searches such Stochastic hill climbing, FirstChoice hill climbing, Random restart hill climbing.Simulated AnnealingVariation of hill climbing where at the beginning, some downhill moves are made andthen random walk moves are made.Annealing is the process used to harden metals and glasses.The innermost algorithm is similar to hill climbing ,instead of picking the best move itpicks a random move. If the move improves its accepted else the algorithm accepts themove with some probability less than 1.BEST FIRST SEARCHIt combines advantages of both BFS and DFS into a single method. Also called Greedybest first search or pure heuristic search.Explores the graph by expanding the most promising node chosen according to thespecified rule.  OR Graphs  The A* Algorithm  Agenda driven searchOR GraphsIt is sometimes important to search a graph instead ,so that duplicate paths will not bepursued. Or graph is one in which each of its branches represents alternative problemsolving path. It uses 2 list of nodes  OPEN –Nodes that have been generated but not examined  CLOSED—Nodes that have already been examined.The A* AlgorithmA Star algorithm is a best first graph search algorithm that finds a least cost path from agiven initial node to one goal node.It expands the nodes with minimal f(n)=g(n)+h(n).whereg(n) gives the path cost from the start node to node n,h(n) is the estimated cost of cheapest path from n to goalA* is optimal if h(n) is admissible heuristic i.e h(n) never overestimates the cost to reachthe goal. A* using graph search is optimal if h(n) is consistent.Agenda driven searchAn agenda is a list of tasks a system could perform. Each task has a list of justificationswhy it is proposed and a rating representing the overall weight of evidence suggesting itwould be a useful task. The idea is that we should pay attention when several pathsrecommend the same action.Agendas are good for implementing monotonic production systems, and bad fornonmonotonic ones.PROBLEM REDUCTION Planning how best to solve a problem that can be recursivelydecomposed into sub problems in multiple ways. 152

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  AND-OR graphs  The AO * AlgorithmAND-OR graphsAn OR node represents a choice between possible decompositionsAn AND node represents a given decomposition. As in OR graph several arcs mayemerge from a single node indicating variety of ways in which the problem can be solved.An AND arc must lead to its own solution node. As it involves both AND and ORgraphs its called as AND-OR graphs.AO* Algorithm 1. Initialize the graph to start node 2. Traverse the graph following the current path accumulating nodes that have not yet been expanded or solved 3. Pick any of these nodes and expand it and if it has no successors call this value FUTILITY otherwise calculate only f' for each of the successors. 4. If f' is 0 then mark the node as SOLVED 5. Change the value of f' for the newly created node to reflect its successors by back propagation. 6. Wherever possible use the most promising routes and if a node is marked as SOLVED then mark the parent node as SOLVED. 7. If starting node is SOLVED or value greater than FUTILITY, stop, else repeat from 2.CONSTRAINT SATISFACTION PROBLEMS(CSP)Problems whose states and goal test conforms to a standard, structured and very simplerepresentation.Formal definition:A constraint satisfaction problem (CSP) consists of  a set of variables,  a domain for each variable, and  a set of constraints.Given a CSP, there are a number of tasks that can be performed:  Determine whether or not there is a model.  Find a model.  Find all of the models or enumerate the models.  Count the number of models.  Find the best model, given a measure of how good models are;  Determine whether some statement holds in all models. It requires 2 kinds of rules. To apply it in a problem domain requires the use of two kinds of rules. (1)Rules that define the way constraints may be propagated and (2)Rules that suggest guesses when guesses are necessary. 153

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGExample: Cryptarithematic Problem.MEANS- ENDS ANALYSISThe MEA technique is a strategy to control search in problem-solving. Given a currentstate and a goal state, an action is chosen which will reduce the difference between thetwo. The action is performed on the current state to produce a new state, and the processis recursively applied to this new state and the goal state.Algorithm:  Allows both backward and forward searching.  This means we could solve major parts of a problem first and then return to smaller problems when assembling the final solution. Very loosely the means-ends analysis algorithm is: 1. Until the goal is reached or no more procedures are available: o Describe the current state, the goal state and the differences between the two. o Use the difference the describe a procedure that will hopefully get nearer to goal. o Use the procedure and update current state. 2. If goal is reached then success otherwise fail. PART - A1.Define AI or What is AI? [May03,04]Artificial Intelligence is the study of how to make computers do things which atthe moment people do better.2.What is Robotic agent? [May 04]A machine that looks like human being & performs various complex acts ofhuman being. It can do the task efficiently without fault. It works on the basis of theprogram feeded to it, it can have previously stored knowledge and it can gather moreknowledge from environment through its sensors. Acts with Actuators. Also calledintelligent agent.3.Define an agent. [May 03,Dec 09,April 14]An agent is anything (a program machine assembly)that can be viewed asperceiving its environment through sensors and acting upon that environment throughactuators. It is a collection of intelligent beings.4.Define rational agent. [dec-05,May-10]A rational agent is agent which always works as per the expectation. It tries tomaximize expected behavioural performance.5.List down characteristics of Intelligent Agent.[May 2011] IA must learn and improve through interaction with the environment. IA must adapt online and real time situation IA must accommodate new problem solving rules inclemently 154

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING IA must have memory with storage and retrieval capacities.6.Define Abstraction. [May 2012]Abstraction is a fundamental mechanism underlying both human and artificialperception, representation of knowledge, reasoning and learning.7.State the concept of rationality. [May 2012]It is the capacity to generate maximum successful behavior give the availableinformation. It indicates the capacity compute perfect ratio decision given the initiallyavailable info. Perfect rationality constraints an agents actions to provide maximumexpectation of success given the info available.8.Define basic agent program. [May 13]It is a concrete implementation of the agent function which runs on agentarchitecture../It takes input as the current percept from the sensor and return an action tothe actuators.9.Why problem formulation must follow goal formulation? [May 2015]In goal formulation, we decide which aspects of the world we are interested in,and which can be ignored or abstracted away. Then in problem formulation we decidehow to manipulate the important aspects (and ignore the others). If we did problemformulation first we would not know what to include and what to leave out.10. What are the key features and limitations of Depth First Search?[ April 14]Key features1. Breadth first search will never get trapped exploring the useless path forever.2. If there is a solution, BFS will definitely find it out.3. If there is more than one solution then BFS can find the minimal one that requiresless number of steps.Limitations The main drawback of Breadth first search is its memory requirement. If the solution is farther away from the root, breath first search will consume lotof time.12.What is a constraint satisfaction problem? [April 14]It is one in which the goal is to discover some problem state that satisfies a givenconstraint. Examples of this sort of problem include Crypt arithmetic puzzles.13.List the criteria to measure performance of search strategies [Jun 14] Relevant to the goal and strategy Placed in context of a target to be reached in an identified time frame Capable of being tracked period after period Owned by the person who‘s responsible for the goal14.What are the steps to be followed for solving a problem?1.Define the problem precisely. It includes specification of initial situation and what finalsituations constitute acceptable solutions to the problem2.Analyze the problem. 155

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING3.Isolate and represent the task knowledge that is necessary to solve the problem.4.Choose the best problem solving technique and apply it to the particular problem.15.What are the control strategies?1.The first requirement of good control strategy is that it causes motion.2. The second requirement of good control strategy is that it be systematic16.What is production system?A production system consist of  A set of rules, each consisting of left side(pattern) and right side that describes operation to be performed if the rule is applied  One or more knowledge /database  A control strategy that specifies the order in which the rules will be compared to the data base.  A rule applier.17.Define heuristic function. A heuristic function is a function that maps from problem state descriptions tomeasures of desirability.18.What are the issues in the design of search programs?  The direction in which to conduct the search (forward Vs backward reasoning).  How to select applicable rule(matching).  How to represent each node of the search process(knowledge representation problem and the frame problem19.List some search strategies. Depth First search, Breadth first search, Generate and Test, Hill Climbing, BestFirst Search, Problem Reduction, Constraint satisfaction, Means End analysis.20.What is a ridge in Hill Climbing? A ridge is a local maximum. It is an area of search space that is higher thansurrounding areas and that itself has a slope. But it is impossible to traverse a ridge bysingle moves.21.Write about AND-OR Graphs.An OR node represents a choice between possible decompositions.An AND node represents a given decomposition. As in OR graph several arcs mayemerge from a single node indicating variety of ways in which the problem can be solvedAn AND arc must lead to its own solution node. As it involves both AND and OR graphsit's called as AND-OR graphs. PART - B1. Explain constraint satisfaction problem with example? [May2014] Constraint satisfaction problems (CSPs) are mathematical problems defined asa set of objects whose state must satisfy a number of constraints or limitations. CSPsrepresent the entities in a problem as a homogeneous collection of finite constraints over 156

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGvariables, which is solved by constraint satisfaction methods. CSPs are the subject ofintense research in both artificial intelligence and operations research, since the regularityin their formulation provides a common basis to analyze and solve problems of manyseemingly unrelated families. CSPs often exhibit high complexity, requiring acombination of heuristics and combinatorial search methods to be solved in a reasonabletime. The Boolean satisfiability problem (SAT), the satisfiability modulo theories (SMT)and answer set programming (ASP) can be roughly thought of as certain forms of theconstraint satisfaction problem.Examples of simple problems that can be modeled as a constraint satisfaction problem  Eight queens puzzle  Map coloring problem The eight queens puzzle is the problem of placing eight chess queens on an 8×8chessboard so that no two queens threaten each other. Thus, a solution requires that notwo queens share the same row, column, or diagonal. The eight queens puzzle is anexample of the more general n-queens problem of placing n queens on an n×nchessboard, where solutions exist for all natural numbers n with the exception of n=2 andn=3. Formal representation of 8 Queens problem Formulation for CSP o Initial state o Successor functions o Goal Test o Path cost  General Algorithm of finding solution in CSP 157

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING2.Explain Backtracking Search and write its algorithm and limitationsBasic steps in Backtracking search  DFS selects values for single variable at a given time  Apply constraint to the variable  Backtracking action -performed if a variable has no legal values left to assignBacktracking search Algorithm  Consider a CSP problem  Apply backtracking search  Recursive backtracking starts with empty set  Variable is assigned a specific value  Relational constraint is set which is i/p  If value is complete stop else continue.  Call the recursive backtracking until result or failure is reachedLimitations of Backtracking  Not effective for very large problems  General performance is not good3. Discuss any two uninformed search strategies with example.[Dec09,may'13,May'14] Uninformed search strategy: Also called blind search. They have no additionalinformation about states other than provided in the problem definition1.B.F.S2.D.F.SBreadth First Search Root node is expanded first then successor of the root node are expanded and thentheir successor and so on.Performance Evaluation  Completeness  Optimality  Time and space complexityAlgorithm BFS { for i:=1 to n do visited[i]=0; for i:=1 to n do if(visited[i]=0)then BFS(i); } 158

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGDepth First Search Depth-first search (DFS) is an algorithm for traversing or searching tree or graphdata structures. One starts at the root (selecting some arbitrary node as the root in the caseof a graph) and explores as far as possible along each branch before backtracking.For the following graph:a depth-first search starting at A, assuming that the left edges in the shown graph arechosen before right edges, and assuming the search remembers previously visited nodesand will not repeat them (since this is a small graph), will visit the nodes in the followingorder: A, B, D, F, E, C, G. The edges traversed in this search form a Trémaux tree, astructure with important applications in graph theory. Performing the same search without remembering previously visited nodes resultsin visiting nodes in the order A, B, D, F, E, A, B, D, F, E, etc. forever, caught in the A, B,D, F, E cycle and never reaching C or G.Iterative deepening is one technique to avoid this infinite loop and would reach all nodes.4.Explain Best First Search with OR Graphs.BEST FIRST SEARCH It combines advantages of both BFS and DFS into a single method. Also calledGreedy best first search or pure heuristic search.Explores the graph by expanding the most promising node chosen according to thespecified rule.  OR Graphs  The A* Algorithm  Agenda driven searchOR Graphs It is sometimes important to search a graph instead ,so that duplicate paths willnot be pursued. Or graph is one in which each of its branches represents alternativeproblem solving path. It uses 2 list of nodes  OPEN –Nodes that have been generated but not examined  CLOSED—Nodes that have already been examined. 159

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGThe A* Algorithm A Star algorithm is a best first graph search algorithm that finds a least cost pathfrom a given initial node to one goal node.It expands the nodes with minimal f(n)=g(n)+h(n).whereg(n) gives the path cost from the start node to node n,h(n) is the estimated cost of cheapest path from n to goalA* is optimal if h(n) is admissible heuristic i.e h(n) never overestimates the cost to reachthe goal. A* using graph search is optimal if h(n) is consistent.4. Explain Hill Climbing Search strategy with algorithm. HILL CLIMBING Variant of generate-and-test in which feedback from the testprocedure is used to help the generator decide which direction to move in the searchspace.  Simple Hill Climbing  Steepest Ascent Hill Climbing Simple Hill Climbing Steps:  Evaluate the initial state. If it is a goal state then quit, else make current state as initial state.  Select a new operator that could be applied to this state and generate a new state.  Evaluate the new state. (iv) If it is a goal state, then return it and quit. (v) If it is not a goal state ,but better than current state, then make it as current state. (vi) If it is not better than the current state, then continue in the loop.Eg.puzzle of 4 colored blocks.Steepest –Ascent Hill climbing In this ,it considers all the moves from the current state and selects the best one asthe next state. This method is called steepest –ascent hill climbing or gradient search.Steps  Evaluate the initial state. If it is a goal state then quit, else make current state as initial state. 160

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Loop until a solution is found (iii) Let SUCC be any possible successor of the current state. (iv) For each operator that applies to the current state do: (a)Apply the operator and generate a new state. (b)Evaluate the new state. If it is a goal state then return and quit, else compare it to SUCC. If its better ,set SUCC as initial state, else leave it. (c)If SUCC is better than current state, then set current state to SUCC.Example:8 queens problemBoth the above hill climbing searches get stuck for the following reasons.1.local maxima2.plateau3.ridgeWays to deal with those problems:(1)Backtrack to some earlier node and try other direction.(2)Make a big jump & try to go to a new section.(3)Apply 2 or more rules. Added to this there are other hill climbing searches such Stochastic hillclimbing, First Choice hill climbing, Random restart hill climbing.Simulated Annealing Variation of hill climbing where at the beginning, some downhill moves aremade and then random walk moves are made. Annealing is the process used to hardenmetals and glasses. The innermost algorithm is similar to hill climbing ,instead of pickingthe best move it picks a random move. If the move improves its accepted else thealgorithm accepts the move with some probability less than 1.5. Explain Iterative deepening and Bidirectional search. Iterative deepening depth-first search (IDDFS) is a state space search strategyin which a depth-limited search is run repeatedly, increasing the depth limit with eachiteration until it reaches d, the depth of the shallowest goal state. IDDFS is equivalent tobreadth-first search, but uses much less memory; on each iteration, it visits the nodes inthe search tree in the same order as depth-first search, but the cumulative order firstvisited is effectively breadth-first. Bidirectional search is a graph search algorithm that finds a shortest path froman initial vertex to a goal vertex in a directed graph. It runs two simultaneous searches:one forward from the initial state, and one backward from the goal, stopping when thetwo meet in the middle. The reason for this approach is that in many cases it is faster: forinstance, in a simplified model of search problem complexity in which both searchesexpand a tree with branching factor b, and the distance from start to goal is d, each of thetwo searches has complexity O(bd/2) (in Big O notation), and the sum of these two searchtimes is much less than the O(bd) complexity that would result from a single search fromthe beginning to the goal. 161

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING UNIT II REPRESENTATION OF KNOWLEDGEGame playing - Knowledge representation, Knowledge representation using Predicatelogic, Introduction to predicate calculus, Resolution, Use of predicate calculus,Knowledge representation using other logic-Structured representation of knowledge. KEY NOTESGAME PLAYINGTo improve effectiveness of search based problem-solving program  Improve the generate procedure so that only good moves(or paths) generated.  Improve the test procedure so that the best moves will be explored first.Two important components of good game playing program -a good plausible move generator -a good static evaluation functionThere are some search procedures (i)Minimax Search procedure (ii)B* algorithm(optional) (iii)Iterative DeepeningMinimax Search procedure: It is a depth first ,depth limited search procedure. It is astraightforward recursive procedure that depend on 2 sub procedures. 1.MOVEGEN(Position, Player)—Returns list of nodes representing moves that can be made by Player in Position. 2.STATIC(Position, Player)—Returns a number representing the goodness of Position from the standpoint of Player.ITERATIVE DEEPENING Used in CHESS programs. On each iteration the tree is searched one level deeper. An algorithm called depth first iterative deepening(DFID)combines the best aspects of depth-first and breadth-first search. Algorithm: 1.Set SEARCH-DEPTH=1 2.Conduct a depth first search to a depth of SEARCH-DEPTH. If a solution path is found then return it. 3.Otherwise increment SEARCH-DEPTH by 1 and go to step 2.KNOWLEDGE REPRESENTATIONTwo entities are taken into account  Facts: truth in some relevant World  Representation of Facts: Things which are to be manipulated.One way to think of structuring these entities is as two levels.1.Knowledge level-Facts(agents behaviors and current goals)are described. 162

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING2.Symbol level-Representation of objects at knowledge level are defined in terms ofsymbols.Representation mappings links two way mappings between fact and representations. Forward representation mapping Backward representation mappingAPPROACHES TO KNOWLEDGE REPRESENTATIONFollowing properties are needed for good knowledge representation.1.Representational Adequacy2.Inferential Adequacy3.Acquistional AdequacyTechniques for knowledge representation1.Simple Relational Knowledge2.Inheritable Knowledge3.Inferential knowledge4.Procedural knowledgeISSUES IN KNOWLEDGE REPRESENTATION Important Attributes Relationships among Attributes(i)Inverses(ii)Existence in hierarchy(iii)Techniques for reasoning about values(iv)Single-valued attributes Choosing the granularity of Representation Representing sets of objects Finding the right structures as neededTHE FRAME PROBLEMWhole problem of representing the facts that change as well as those that do not is knownas the frame problem.KNOWLEDGE REPRESENTATION USING PREDICATE LOGICOne way of representing the facts is the language of logic. Real World facts arerepresented as logical propositions written as well formed formulas(wff‘s).Eg. ‗It is raining‘ - RAININGA predicate name followed by a list of variables such as P(x, y), where P is a predicatename, and x and y are variables, is called an atomic formula.Wffs are constructed using the following rules:1. True and False are wffs.2. Each propositional constant (i.e. specific proposition), and each propositionalvariable (i.e. a variable representing propositions) are wffs.3. Each atomic formula (i.e. a specific predicate with variables) is a wff.4. If A, B, and C are wffs, then so are A, (A B), (A B), (A B), and (A B). 163

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING 5. If x is a variable (representing objects of the universe of discourse), and A is a wff, then so are x A and x A .PREDICATE CALCULUSPredicate calculus is a generalization of propositional calculus. Hence, besides terms,predicates, and quantifiers, predicate calculus contains propositional variables,constants and connectives as part of the language.First-order logic is a collection of formal systems used in mathematics, philosophy,linguistics, and computer science. It is also known as first-order predicate calculus, thelower predicate , quantification theory, and predicate logic.RESOLUTIONIt is a proof procedure which operates on statements that have been converted to a veryconvenient standard form.Algorithm in propositional logic  Propositional Resolution  Unification Algorithm  Resolution PART –A1.What is the significant use in Unification algorithm? [may 14] Unification, in computer science and logic, is an algorithmic process of solvingequations between symbolic expressions.2.Distinguish between Problem solving and Planning, [May 2014] Planning can be viewed as a type of problem solving in which the agent usesbeliefs about actions and their consequences to search for solution over the more abstractspace of plans. Problem Solving is the process of working through details of a problem to reach asolution. Problem solving may include mathematical or systematic operations and can bea gauge of an individual's critical thinking skills.3.How will you improve a search based problem solving program ?Two things can be done.  Improve the generate procedure so that only good moves(or paths)are generated.  Improve the best procedure so that best moves will be recognized and explored first.4.What is MINIMAX search procedure? It is a depth first ,depth limited search procedure. The idea is to start at the currentposition and use the plausible move generator to generate the set of possible successorpositions.5.What is representation mapping? They are two way mapping that must exist between facts and representations.The forward representation mapping maps from facts to representations. 164

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGThe backward representation mapping maps from representation to facts.6.What are the approaches to knowledge representation?  Inferential adequacy  Inferential Efficiency  Acquisitional Efficiency7.What is called “Waiting for Quiescence”? To make sure that short term measures do not influence the choice of move, weshould continue the search until no drastic change occurs from one level to the next. Thisis called waiting for quiescence.8.What is called secondary search? The search process executed for finding the motivational variables on which themotivation to search and the motivation to ignore depend is called the secondary searchprocess.9.What is called singular extensions? One particularly Successful form of secondary search is called singularextensions. The idea is that if a leaf node is judged to be far superior to its siblings and ifthe value of the entire search depends critically on the correctness of that node‘s value,then the node is expanded one extra level.10.What is alpha beta pruning? Alpha–beta pruning is a search algorithm that seeks to decrease the number ofnodes that are evaluated by the minimax algorithm in its search tree.11.What is Credit assignment problem? The problem of deciding which series of action is responsible for particularoutcome is called credit assignment problem.12.What is property inheritance? One of the most useful forms of inference is property inheritance in whichelements of specific classes inherit attributes and values from more general classes inwhich they are included.13.List the relationships among attributes?  Inverses  Existence in an is a hierarchy  Techniques for reasoning about values  Single valued attributes.14.Define Resolution. It is a procedure which gains its efficiency from the fact that it operates onstatements that have been converted to a very convenient standard form15.What is refutation? Resolution produces proofs by refutation. In other words to prove a statementresolution attempts to show that the negation of the statement produces a contradictionwith the known statements. 165

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING16.What is Conjunctive Normal form? A formula is in conjunctive normal form (CNF) or clausal normal form if it isa conjunction of clauses, where a clause is a disjunction of literals; otherwise put, it is anAND of ORs. As a normal form, it is useful in automated theorem proving.17.What is Unification Algorithm? It is a straightforward recursive procedure for solving the problem.18.What are the strategies for resolution in predicate logic?  Set of support strategy  Unit preference strategy19.What is called Unit preference strategy? Resolutions which generate new clauses with fewer literals than the larger of theirparent clauses and thus are and so are closer to the goal of resolvent with zero terms. Thismethod is calledUnit preference strategy.20.What is Predicate logic? Predicate calculus, or predicate logic, is a kind of mathematical logic, which wasdeveloped to provide a logical foundation for mathematics, but has been used forinference in other domains.21.What are the connectives used in propositions? Conjunction,DisjunctionNegation,Implication,Equivalence.23. What are the two important rules of Predicate logic?There are two important rules: 1. Universal instantiation (UI): From (∀x)F(x), infer F(a), where a is a constant, and F(a) is obtained from F(x) with x substituted by a throughout F. 2. Existential generalization (EG): From F(a), infer (∃x)F(x), where a is a constant, and F(x) is obtained from F(a) with a substituted by x throughout F.24.What is Procedural Knowledge Representation? One in which control information that is necessary to use the knowledge isconsidered to be embedded in knowledge itself.25.What is Declarative Knowledge Representation?One in which knowledge is specified but the use of th knowledge is not given.  Syntactic-Semantic Spectrum of Representation  Logic and Slot- And-Filler Structures PART - B1.What are the major components of game playing program? Explain Mini-MaxAlgorithm with example.[May 03,Dec 09]Components of game playing program  A plausible move generator  A static evaluation generator 166

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGMini-Max Algorithm  The start node is MAX node with current configuration  Expand nodes to some depth  Apply evaluation function to each leaf node  Back up values for each non leaf node.  At MIN nodes the backed up value is minimum.  At MAX nodes the backed up value is maximum.Example Problem: Tic Tac Toe2.Explain Alpha Beta Pruning.[Dec'10,may 10]α - β proposes to compute correct minimax alg decision without looking at every node inthe game tree.Steps in Alpha Beta Pruning1.MAX player cuts off search when he knows MIN-Player proves bad outcome.2.MIN player cuts off search when he knows MAX-Player proves bad outcome..3.Applying α cut offs means we stop search for a particular branch because we seebetter opportunity elsewhere.4. Applying β cut offs means we stop search for a particular branch because we seebetter opportunity elsewhere.5.Applying both forms is alpha beta pruning.Algorithm/*alpha is the best score for max along the path to state.beta is the best score for min along the path to state.*/3.Explain approaches to knowledge representation and its techniques.KNOWLEDGE REPRESENTATIONTwo entities are taken into account  Facts: truth in some relevant World  Representation of Facts: Things which are to be manipulated.One way to think of structuring these entities is as two levels.1.Knowledge level-Facts(agents behaviors and current goals)are described.2.Symbol level-Representation of objects at knowledge level are defined in terms ofsymbols.Representation mappings links two way mappings between fact and representations.  Forward representation mapping  Backward representation mappingAPPROACHES TO KNOWLEDGE REPRESENTATIONFollowing properties are needed for good knowledge representation.1.Representational Adequacy2.Inferential Adequacy3.Acquistional Adequacy 167

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGTechniques for knowledge representation1.Simple Relational Knowledge2.Inheritable Knowledge3.Inferential knowledge4.Procedural knowledgeISSUES IN KNOWLEDGE REPRESENTATION  Important Attributes  Relationships among Attributes (i)Inverses (ii)Existence in hierarchy (iii)Techniques for reasoning about values (iv)Single-valued attributes  Choosing the granularity of Representation  Representing sets of objects  Finding the right structures as needed4.Explain First Order Logic in detail. It is a expressive language which has well defined syntax and semantics. It uses 3things to represent World model.  Objects  Relations  FunctionProperties of First Order Logic:1.It has ability to represent some facts.2.Enables to represent law and rules extracted from real World3.Represents facts in more realistic manner.First Order Logic Extension to Propositional LogicIt extends Propositional logic in 2 directions:1.Provides inner structure for sentences2.Provides a mean to express and reason with generalization.Variations of First Order Logic1.Temporal logic2.High Order LogicSyntax for First Order Logic1.Model2.Domain of a model3.Relation4.Function5.SymbolsFirst Order Logic symbols1.truth symbols 168

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING2.Constant Symbols3.Variable symbols4.Predicate symbols5.Function symbolsQuantifiers1.Univerasal Quantifier2.Existential Quantifier5.Explain Weak and strong slot filler structures in knowledge representation UNIT III KNOWLEDGE INFERENCEKnowledge representation -Production based system, Frame based system. Inference -Backward chaining, Forward chaining, Rule value approach, Fuzzy reasoning - Certaintyfactors, Bayesian Theory-Bayesian Network-Dempster - Shafer theory. KEYNOTESRepresentation of knowledge using rulesProcedural Knowledge Representation-One in which control info that is necessary touse the knowledge is considered to be embedded in knowledge itself.Declarative Knowledge Representation-One in which knowledge is specified but theuse of the knowledge is not given.  Syntactic-Semantic Spectrum of Representation  Logic and Slot- And-Filler Structures Other representational Techniques  Representing Knowledge as Constraints  Models and model base Reasoning  Sub symbolic SystemsProduction systemA production system consists of four basic components:1.A set of rules of the form Ci→Ai where Ci is the condition part and Ai is the actionpart. The condition determines when a given rule is applied, and the action determineswhat happens when it is applied.2.One or more knowledge databases that contain whatever information is relevant for thegiven problem. Some parts of the database may be permanent, while others maytemporary and only exist during the solution of the current problem. The information inthe databases may be structured in any appropriate manner.3.A control strategy that determines the order in which the rules are applied to thedatabase, and provides a way of resolving any conflicts that can arise when several rulesmatch at once. 169

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING4.A rule applier which is the computational system that implements the control strategyand applies the rules.INFERENCE RULEWe are already familiar with the kind of rules our AI systems may use, e.g.Deductive Inference RuleModus PonensGiven ―A‖ and ―A implies B‖, we can conclude ―B‖:AA ⇒BBExample:It is rainingIf it is raining, the street is wetThe street is wetAbductive Inference RuleAbductionGiven ―B‖ and ―A implies B‖, it might be reasonable to expect ―A‖:BA ⇒BAExample:The street is wetIf it is raining, the street is wetIt is rainingFRAMESA frame is a collection of attributes(called as slots)and associated values(constraints onthose values)that describe some entity in the World. It describes an entity.  Frames as Sets and Instances  Slots as fully fledged objects.  Slot-Values as Objects  InheritanceLOGIC PROGRAMMINGLogic makes statements about the world which are true (or false) if the state of affairs itrepresents is the case (or not the case).A logic is defined by the following: 1. Syntax - describes the possible configurations that constitute sentences. 2. Semantics - determines what facts in the world the sentences refer to i.e. the interpretation. Each sentence makes a claim about the world. 3. Proof theory - set of rules for generating new sentences that are necessarily true given that the old sentences are true. The relationship between sentences 170

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING is called entailment. The semantics link these sentences (representation) to facts of the world. The proof can be used to determine new facts which follow from the oldIt is a programming language in which logical assertions are viewed asprograms.Eg:PROLOGForward Versus Backward Reasoning  Forward Chaining rule systems-  Backward Chaining rule system  Combining forward and backward reasoningMATCHING Some kind of matching is needed between the current state and the preconditionsof the rules. This matching can be done in the following ways  Indexing  Matching with variables  Complex and Approximate Matching  Conflict Resolution-Preferences based on rules, objects, StatesSTATISTICAL REASONING  Probability and Bayes Theorem  Certainty factors and Rule based systems  Bayesian Networks A Bayesian network, Bayes network, belief network, Bayes(ian) model or probabilistic directed acyclic graphical model is a probabilistic graphical model (a type of statistical model) that represents a set of random variables and their conditional dependencies via a directed acyclic graph (DAG).  Dempster Shafter Theory It considers sets of propositions and assigns to each of them an interval in which the degree of belief must lie. Belief (usually denoted bel) measures the strength of the evidence in favor of set of propositions. Ranges from 0 to 1.FUZZY LOGICFuzzy logic is an approach to computing based on \"degrees of truth\" rather than the usual \"true or false\" (1 or 0) Boolean logic on which the modern computer is based. PART - A1.State Bayes Rule.[Dec‟2014]An agent must update its belief when it observes new evidence. A new piece ofevidence is conjoined to the old evidence to form the complete set of evidence. Bayes'rule specifies how an agent should update its belief in a proposition based on a new pieceof evidence.Suppose an agent has a current belief in proposition h based on evidence k alreadyobserved, given by P(h|k), and subsequently observes e. Its new belief in h is P(h|e∧k). 171

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGBayes' rule tells us how to update the agent's belief in hypothesis h as new evidencearrives.Bayes' rule) As long as P(e|k)≠0,P(h | e ∧k) = P(e | h ∧k) ×P(h | k) / P(e | k).2.Define critical path.[Dec 2014,15] It is used to determine start and end times. Path is the linear sequence from start toend. Critical path is path with longest total duration. It should be executed without delay.3.What is a production system? A production system consists of four basic components  A set of rules of the form Ci→Ai where Ci is the condition part and Ai is the action part.  One or more knowledge databases that contain whatever information is relevant for the given problem  A control strategy that determines the order in which rules are applied to the database  A rule applier that implements control strategy and applies the rules..4.What is a Certainty factor? It is a measure of the extent to which the evidence that is described by theantecedent of the rule supports the conclusion that is given for a problem.5.List the components of Certainty Factors.[April „11] A Certainty Factor(CF[h,e] deals with two components  MB[h,e]-a measure (bet 0 &10 of belief in hypothesis h ,given the evidence e.MB measures the extent to which evidence supports the hypothesis.  MD[h,e]-a measure of disbelief in hypothesis h, given evidence e.MD measures the extent to which evidence supports the negation of the hypothesis.6.List two application of temporal probabilistic model?[April „11]  Used for speech recognition, part of speech tagging  Used for tracking of moving objects.7.Define Dempster –Shafer Theory.[April-11] It considers sets of propositions and assigns to each of them an interval in whichthe degree of belief must lie. Belief measures the strength of the evidence in favor of a setof propositions. It ranges from 0 to 1.[Belief,Plausability]Plausibility refers to comparison of different possible explanations. It ranges from 0 to 1.8.Define Temporal models.[Nov 2013] Modal logics allow us to talk about the truth of a set of propositions not only inthe current state of the real World, but also about their truth in the past or thefuture..These are called temporal logics. 172

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING9.What do you mean by Bayesian Network?[Nov 12] A Bayesian network is a graphical structure that allows us to represent a reasonabout an uncertain domain. The nodes in a Bayesian network represent a set of randomvariables=X1; ::Xi; :::Xn, from the domain. A set of directed arcs represents directdependencies between the variables.10.Define crisp sets in fuzzy logic? In fuzzy set theory, classical bivalent sets are usually called crisp sets.11.Define fuzzy set? Any set that empowers its members to have different grades of membership in ainterval[0,1] is a fuzzy set.12.Explain fuzzy set operations.  Union: The membership function of the union of two fuzzy sets  Intersection: The membership function of the intersection of two fuzzy sets.  Complement: It is the negation of the specified membership function ;It is equivalent to the Boolean NOT operation.13.How knowledge can be represented using frames? A frame is an artificial intelligence data structure used to divide knowledge intosubstructures. The frame contains information on how to use the frame, what to expectnext, and what to do when these expectations are not met. Some information in the frameis generally unchanged. Each piece of information about a particular frame is held in aslot. The information can contain:  Facts or data  Procedures  Default values  Sub frames14.How knowledge can be represented using production rules? One of the most popular approaches to knowledge representation is to useproduction rules, sometimes called IF-THEN rules. They can take various forms.e.g. IF condition THEN actionSome of the benefits of IF-THEN rules are that they are modular, each defining arelatively small and, at least in principle, independent piece of knowledge. New rulesmay be added and old ones deleted usually independently of other rules.15.What is forward chaining rule? Forward chaining starts with the available data and uses inference rules to extractmore data (from an end user, for example) until a goal is reached. It encodes knowledgeabout how to respond to certain input configurations.16.What is backward chaining rule? Backward chaining (or backward reasoning) is an inference method that can bedescribed (in lay terms) as working backward from the goal(s). Backward chaining startswith a list of goals and works backwards from the consequent to the antecedent to see if 173

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGthere is data available that will support any of these consequents. An inference engineusing backward chaining would search the inference rules until it finds one which has aconsequent (Then clause) that matches a desired goal. It encodes knowledge about howto achieve particular goals.17.What is the logic of Nonmonotonic reasoning? A logic is non-monotonic if some conclusions can be invalidated by adding moreknowledge. The logic of definite clauses with negation as failure is non-monotonic. Non-monotonic reasoning is useful for representing defaults. A default is a rule that can beused unless it overridden by an exception.18.What is Bidirectional search? It is a strategy which searches both forward from the start state and backwardfrom the goal simultaneously until two paths meet somewhere between.19.What is alpha beta pruning? Alpha–beta pruning is a search algorithm that seeks to decrease the number ofnodes that are evaluated by the minimax algorithm in its search tree.20.Terms used in knowledge representationObjects-Entities in the world of agent about which info needs to be stored.Events-Actions that occur in agent WorldPerformance-Behavior of an agentMeta knowledge-list of items about which agent has knowledgeFacts-truth about real WorldKnowledge level-Limit up to which facts are described.Entailment-logical association between two sentences.Inference algorithm-model checking PART - B1.Explain Forward and backward Chaining algorithm.[Dec '10] Forward chaining is one of the two main methods of reasoning when using aninference engine and can be described logically as repeated application of modus ponens.Forward chaining is a popular implementation strategy for expert systems, business andproduction rule systems. The opposite of forward chaining is backward chaining. Forward chaining starts with the available data and uses inference rules to extractmore data (from an end user, for example) until a goal is reached. An inference engineusing forward chaining searches the inference rules until it finds one where theantecedent (If clause) is known to be true. When such a rule is found, the engine canconclude, or infer, the consequent (Then clause), resulting in the addition of newinformation to its data. Inference engines will iterate through this process until a goal is reached.For example, suppose that the goal is to conclude the color of a pet named Fritz, giventhat he croaks and eats flies, and that the rule base contains the following four rules: 174

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING 1. If X croaks and X eats flies - Then X is a frog 2. If X chirps and X sings - Then X is a canary 3. If X is a frog - Then X is green 4. If X is a canary - Then X is yellow Let us illustrate forward chaining by following the pattern of a computer as itevaluates the rules. Assume the following facts:  Fritz croaks  Fritz eats flies Backward chaining (or backward reasoning) is an inference method that can be described (in lay terms) as working backward from the goal(s). It is used in automated theorem provers, inference engines, proof assistants and other artificial intelligence applications.[1]  In game theory, its application to (simpler) sub games in order to find a solution to the game is called backward induction. In chess, it is called retrograde analysis, and it is used to generate table bases for chess endgames for computer chess.  Backward chaining is implemented in logic programming by SLD resolution. Both rules are based on the modus ponens inference rule. It is one of the two most commonly used methods of reasoning with inference rules and logical implications – the other is forward chaining. Backward chaining systems usually employ a depth-first search strategy, e.g. Prolog.2.Explain about exact inference in Bayesian networks A Bayesian network, Bayes network, belief network, Bayes(ian) model orprobabilistic directed acyclic graphical model is a probabilistic graphical model (atype of statistical model) that represents a set of random variables and their conditionaldependencies via a directed acyclic graph (DAG). For example, a Bayesian networkcould represent the probabilistic relationships between diseases and symptoms. Givensymptoms, the network can be used to compute the probabilities of the presence ofvarious diseases. Formally, Bayesian networks are DAGs whose nodes represent random variablesin the Bayesian sense: they may be observable quantities, latent variables, unknownparameters or hypotheses. Edges represent conditional dependencies; nodes that are notconnected (there is no path from one of the variables to the other in the bayesian network)represent variables that are conditionally independent of each other. Each node isassociated with a probability function that takes, as input, a particular set of values for thenode's parent variables, and gives (as output) the probability (or probability distribution,if applicable) of the variable represented by the node. For example, if parent nodesrepresent Boolean variables then the probability function could be represented by atable of entries, one entry for each of the possible combinations of its parentsbeing true or false. Similar ideas may be applied to undirected, and possibly cyclic,graphs; such are called Markov networks. 175

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING Efficient algorithms exist that perform inference and learning in Bayesiannetworks. Bayesian networks that model sequences of variables (e.g. speech signals orprotein sequences) are called dynamic Bayesian networks. Generalizations of Bayesiannetworks that can represent and solve decision problems under uncertainty are calledinfluence diagrams.3.Explain Weak Slot and Filler structuresThis data structure  enables attribute values to be retrieved quickly o assertions are indexed by the entities o binary predicates are indexed by first argument. E.g. team(Mike-Hall , Cardiff).  Properties of relations are easy to describe .  allows ease of consideration as it embraces aspects of object oriented programming.So called because:  A slot is an attribute value pair in its simplest form.  A filler is a value that a slot can take -- could be a numeric, string (or any data type) value or a pointer to another slot.  A weak slot and filler structure does not consider the content of the representation.We will study two types:  Semantic Nets.  Frames.4.Explain strong slot and filler structures.Strong Slot and Filler Structures typically:  Represent links between objects according to more rigid rules.  Specific notions of what types of object and relations between them are provided.  Represent knowledge about common situationsConceptual Dependency originally developed to represent knowledge acquired fromnatural language input.The goals of this theory are:  To help in the drawing of inference from sentences.  To be independent of the words used in the original input.  That is to say: For any 2 (or more) sentences that are identical in meaning there should be only one representation of that meaning.It has been used by many programs that portend to understand English (MARGIE, SAM,PAM). CD developed by Schank et al. as were the previous examples.CD provides:  a structure into which nodes representing information can be placed  a specific set of primitives  at a given level of granularity. 176

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGSentences are represented as a series of diagrams depicting actions using both abstractand real physical situations.  The agent and the objects are represented  The actions are built up from a set of primitive acts which can be modified by tense.Examples of Primitive Acts5.Explain the need of fuzzy set and fuzzy logic with example.[Dec 2013]6..Explain Dempster_ Shafer Theory The theory of belief functions, also referred to as evidence theory or Dempster–Shafer theory (DST), is a general framework for reasoning with uncertainty, withunderstood connections to other frameworks such as probability, possibility andimprecise probability theories. In this formalism a degree of belief (also referred to as a mass) is represented as abelief function rather than a Bayesian probability distribution. Probability values areassigned to sets of possibilities rather than single events: their appeal rests on the factthey naturally encode evidence in favor of propositions.Dempster–Shafer theory assigns its masses to all of the non-empty subsets of thepropositions that compose a system. (In set-theoretic terms, the Power set of thepropositions.) For instance, assume a situation where there are two related questions, orpropositions, in a system. In this system, any belief function assigns mass to the firstproposition, the second, both or neither.Belief and plausibility[edit] Shafer's formalism starts from a set of possibilities under consideration, forinstance numerical values of a variable, or pairs of linguistic variables like \"date andplace of origin of a relic\" (asking whether it is antique or a recent fake). A hypothesis isrepresented by a subset of this frame of discernment, like \"(Ming dynasty, China)\", or\"(19th century, Germany)\".[2]:p.35f.Shafer's framework allows for belief about such propositions to be represented asintervals, bounded by two values, belief (or support) and plausibility: belief ≤ plausibility.In a first step, subjective probabilities (masses) are assigned to all subsets of the frame;usually, only a restricted number of sets will have non-zero mass (focal elements).[2]:39f.Belief in a hypothesis is constituted by the sum of the masses of all sets enclosed by it. Itis the amount of belief that directly supports a given hypothesis or a more specific one,forming a lower bound. Belief (usually denoted Bel) measures the strength of theevidence in favor of a proposition p. It ranges from 0 (indicating no evidence) to 1(denoting certainty).Plausibility is 1 minus the sum of the masses of all sets whose intersection with thehypothesis is empty. Or, it can be obtained as the sum of the masses of all sets whoseintersection with the hypothesis is not empty. It is an upper bound on the possibility that 177

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGthe hypothesis could be true, i.e. it ―could possibly be the true state of the system‖ up tothat value, because there is only so much evidence that contradicts that hypothesis.Plausibility (denoted by Pl) is defined to be Pl(p)=1-Bel(~p). It also ranges from 0 to 1and measures the extent to which evidence in favor of ~p leaves room for belief in p. UNIT IV PLANNING AND MACHINE LEARNINGBasic plan generation systems - Strips -Advanced plan generation systems –stripsStrategic explanations -Why, Why not and how explanations. Learning- Machinelearning, adaptive Learning. KEY NOTESPLANNING AND MACHINE LEARNINGPlanning is the process of deciding the sequence of actions that will achieve the goal.Basic Plan Generation System  Choose the best rule to apply next based on the best available heuristic information  Apply the chosen rule to compute the new problem state that arises from its application.  Detect when a solution has been found  Detect dead ends .  Detect when an almost correct solution has been found and make it correct.Example domain: The Blocks WorldThree types of Planning 1.Goal Stack Planning 2.Nonlinear Planning using Constraint Posting 3.Hierarchical PlanningGOAL STACK PLANNINGBasic Idea to handle interactive compound goals uses goal stacks, Here the stackcontains :  Goals  operators -- ADD, DELETE and PREREQUISITE lists  a database maintaining the current situation for each operator used.This was the approach used by STRIPS.Consider the following where wish to proceed from the start to goal state.Fig. 24 Goal Stack Planning ExampleWe can describe the start state: 178

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGON(B, A) ONTABLE(A) ONTABLE(C) ONTABLE(D) ARMEMPTYand goal state:ON(C, A) ON(B,D) ONTABLE(A) ONTABLE(D)  Initially the goal stack is the goal state.  We then split the problem into four sub problems..  Two are solved as they already are true in the initial state -- ONTABLE(A), ONTABLE(D).  With the other two -- there are two ways to proceed:The method is to  Investigate the first node on the stack i.e the top goal.  If a sequence of operators is found that satisfies this goal it is removed and the next goal is attempted.  This continues until the goal state is empty.Advanced Planning ApproachesIn order to solve nontrivial problems, it is necessary to combine  Basic problem solving strategies  Knowledge representation mechanisms  Partial solutions and at the end combine into complete problem solution (decomposition)Planning GraphThey are pictorial and effective tool for solving hard planning problems. They give goodheuristic estimates and can be applied to any search techniques. They can give a solutionusing specialized algorithm GRAPHPLANMACHINE LEARNINGMachine learning is a subfield of computer science that evolved from the study ofpattern recognition and computational learning theory in artificial intelligence. Machinelearning explores the study and construction of algorithms that can learn from and makepredictions on data. (i)Learning by Taking Advice(Adaptive Learning) (ii)Learning in Problem Solving  Learning by parameter Adjustment  Learning with Macro Operators  Learning by Chunking (iii)Induction based Learning  Winston‘s learning program  Version Spaces & Decision trees (iv)Explanation Based learning (v)Discovery (vi)Analogy (vii)Neural net Learning & Genetic Learning 179

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING PART - A1.What are the components of planning system?The components of planning system are  Choose the best rule to apply next  Apply the chosen rule to compute the new problem state that arises from its application.  Detect when a solution has been found.  Detect dead end so that they can be stopped.2.What is goal stack planning? It is a technique used for solving compound goals that may interact. Here theproblem solver makes use of a single stack that contains both goals and operators thathave been proposed to satisfy those goals. It depends on set of operators such asPRECONDITIION,ADD and DELETE lists.3.What is nonlinear planning using constraint posting? A plan generated by this method contains a sequence of operators for attaining thefirst goal followed by complete sequence for the second goal. Nonlinear plan is onewhich is not compose of a linear sequence of complete sub plans.4.What is model truth criterion? It tells us when a proposition is true. A proposition P is necessarily true in a stateS if and only if two conditions hold.5.What is step addition in planning? Introducing new steps to achieve goals or preconditions is called step addition.6.What is 'Declobbering'? Placing one possibly new step S2 between S1 and S3 such that S2 reasserts someprecondition of S3 that was negated(clobbered) by S1.7.What are plan modification operation? The four different heuristics to synthesize the plan such as step addition,promotion, declobbering and simple establishment are known as plan modificationoperation.8.What is hierarchical planning? It is one in which problem is decomposed into smaller sub problems which can beorganized as hierarchical representation.9.What is a consistent plan?[May'13]2 It is a plan in which there are no cycles in the ordering constraints and no conflictswith the casual link.A consistent plan with no open preconditions is a solution.10.List other planning techniques for problem solving.  Triangle tables  Metaplanning  Macro operators & Case Based Planning 180

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING11.What is learning? Learning modifies the agents decision mechanisms to improve performance. It isessential for unknown environments i.e. when designer lacks omniscience.12.What are the types of learning?  Rote learning  Learning by taking advice  Learning in problem solving  Induction learning  Explanation based learning13.List capabilities of rote learning?  Organized storage of information  Generalization14.What is induction based learning?[dec'13] It means learning from examples. It is a form of supervised learning which usesspecific examples to reach general conclusions. The concepts are learned from sets oflabeled instances.15.What is the basic concept of Winston's learning program?  Begin with a structural description of one known instance of the concept.  Examine descriptions of other known instances of the concept. Generalize it.  Examine descriptions of near misses of the concept.16.What is Candidate elimination algorithm? The algorithm for narrowing the version space is called candidate eliminationalgorithm.17.What is the idea of chunking in learning? The idea of chunking comes from the psychological literature on memory andproblem solving. A chunk is created when a large production does the work of an entiresequence of smaller ones.18.Define STRIPS In artificial intelligence, STRIPS (Stanford Research Institute Problem Solver) isan automated planner developed by Richard Fikes and Nils Nilsson in 1971 at SRIInternational.[1] The same name was later used to refer to the formal language of theinputs to this planner. This language is the base for most of the languages for expressingautomated planning problem instances in use today; such languages are commonlyknown as action languages.19.What is concept space and version space? Concept space: The entire partial ordering of the learning approach is called theconcept space. At the top of concept space is null description consisting only of variablesand at the bottom are all possible training instances which contains no variables.Version Space: The goal is to produce a description that is consistent with all positiveexamples but no negative examples in the training set. 181

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING20.What is Explanation based learning(EBL)? An EBL system attempts to learn from single example x by explaining why x isan example of the target concept. The explanation is then generalized and the system'sperformance is improved through the availability of this knowledge.21.What are the types of analogy in learning?  Transformational analogy  Derivational analogy PART - B1.Explain Decision tree algorithm with example. A Decision Tree takes as input an object given by a set of properties, output aBoolean value (yes/no decision). Each internal node in the tree corresponds to test of oneof the properties. Branches are labeled with the possible values of the test.  Aim: Learn goal concept (goal predicate) from examples  Learning element: Algorithm that builds up the decision tree.  Performance element: decision procedure given by the treeExampleProblem to wait for a table at a restaurant. A decision tree decides whether to wait or notin a given situation.Attributes: 1. Alternate: alternative restaurant nearby 2. Bar: bar area to wait 3. Fri/Sat: true on Fridays and Saturdays 4. Hungry: whether we are hungry 5. Patrons: how many people in restaurant (none, some, or full) 6. price: price range (£ , £ £ , £ £ £ ) 7. raining: raining outside 8. reservation: whether we made a reservation 9. type: kind of restaurant (French, Italian, Thai, or Burger) 10. Wait Estimate: estimated wait (<10, 10-30,30-60,>60)The following diagram is an example for decision tree algorithm. 182

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGOriginal Decision Tree2.Explain explanation based learning with example. An example of EBL using a perfect domain theory is a program that learns to playchess by being shown examples. A specific chess position that contains an importantfeature, say, \"Forced loss of black queen in two moves,\" includes many irrelevantfeatures, such as the specific scattering of pawns on the board. EBL can take a singletraining example and determine what are the relevant features in order to form ageneralization. A domain theory is perfect or complete if it contains, in principle, all informationneeded to decide any question about the domain. For example, the domain theory forchess is simply the rules of chess. Knowing the rules, in principle it is possible to deducethe best move in any situation. However, actually making such a deduction is impossiblein practice due to combinatoric explosion. EBL uses training examples to make searchingfor deductive consequences of a domain theory efficient in practice. In essence, an EBL system works by finding a way to deduce each trainingexample from the system's existing database of domain theory. Having a short proof ofthe training example extends the domain-theory database, enabling the EBL system tofind and classify future examples that are similar to the training example very quickly.The main drawback of the method---the cost of applying the learned proof macros, asthese become numerous---was analyzed by Minton. 183

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGBasic FormulationEBL software takes four inputs:  a hypothesis space (the set of all possible conclusions)  a domain theory (axioms about a domain of interest)  training examples (specific facts that rule out some possible hypotheses)  operationality criteria (criteria for determining which features in the domain are efficiently recognizable, e.g. which features are directly detectable using sensors)[3.Explain the concept of version space using Candidate elimination algorithm. A version space is a hierarchical representation of knowledge that enables you tokeep track of all the useful information supplied by a sequence of learning exampleswithout remembering any of the examples.The version space method is a concept learning process accomplished by managingmultiple models within a version space.Version Space CharacteristicsTentative heuristics are represented using version spaces.A version space represents all the alternative plausible descriptions of a heuristic.A plausible description is one that is applicable to all known positive examples and noknown negative example.A version space description consists of two complementary trees: 1. One that contains nodes connected to overly general models, and 2. One that contains nodes connected to overly specific models.Node values/attributes are discrete.Fundamental Assumptions 1. The data is correct; there are no erroneous instances. 2. A correct description is a conjunction of some of the attributes with values.Diagram of a Version SpaceIn the diagram below, the specialization tree is colored red, and the generalization tree iscolored green. 184

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGGeneralization and Specialization Leads to Version Space Convergence The key idea in version space learning is that specialization of the general modelsand generalization of the specific models may ultimately lead to just one correct modelthat matches all observed positive examples and does not match any negative examples.That is, each time a negative example is used to specialize the general models, thosespecific models that match the negative example are eliminated and each time a positiveexample is used to generalize the specific models, those general models that fail to matchthe positive example are eliminated. Eventually, the positive and negative examples maybe such that only one general model and one identical specific model survive.Version Space Method Learning Algorithm: Candidate-Elimination The version space method handles positive and negative examples symmetrically.Given:  A representation language.  A set of positive and negative examples expressed in that language.Compute: a concept description that is consistent with all the positive examples andnone of the negative examples. 185

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGMethod:  Initialize G, the set of maximally general hypotheses, to contain one element: the null description (all features are variables).  Initialize S, the set of maximally specific hypotheses, to contain one element: the first positive example.  Accept a new training example. o If the example is positive: 1. Generalize all the specific models to match the positive example, but ensure the following:  The new specific models involve minimal changes.  Each new specific model is a specialization of some general model.  No new specific model is a generalization of some other specific model. 2. Prune away all the general models that fail to match the positive example. o If the example is negative: 1. Specialize all general models to prevent match with the negative example, but ensure the following:  The new general models involve minimal changes.  Each new general model is a generalization of some specific model.  No new general model is a specialization of some other general model. 2. Prune away all the specific models that match the negative example. o If S and G are both singleton sets, then:  if they are identical, output their value and halt.  if they are different, the training cases were inconsistent. Output this result and halt.  else continue accepting new training examples.The algorithm stops when: 1. It runs out of data. 2. The number of hypotheses remaining is: o 0 - no consistent description for the data in the language. o 1 - answer (version space converges). o 2+ - all descriptions in the language are implicitly included.4.Explain Hierarchical planning and Reactive systems. 186

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING5.What is planning and explain components of planning ?Explain Goal stackplanning briefly.Planning System ComponentsSimple problem solving tasks basically involve the following tasks: 1. Choose the best rule based upon heuristics. 2. Apply this rule to create a new state. 3. Detect when a solution is found. 4. Detect dead ends so that they can be avoided.More complex problem solvers often add a fifth task: 1. Detect when a nearly solved state occurs and use special methods to make it a solved state. Goal stack planningBasic Idea to handle interactive compound goals uses goal stacks, Here the stackcontains :  goals,  operators -- ADD, DELETE and PREREQUISITE lists  a database maintaining the current situation for each operator used.Consider the following where wish to proceed from the start to goal state.Fig. 24 Goal Stack Planning ExampleWe can describe the start state:ON(B, A) ONTABLE(A) ONTABLE(C) ONTABLE(D) ARMEMPTYand goal state:ON(C, A) ON(B,D) ONTABLE(A) ONTABLE(D)  Initially the goal stack is the goal state.  We then split the problem into four sub problems  Two are solved as they already are true in the initial state -- ONTABLE(A), ONTABLE(D).  With the other two -- there are two ways to proceed: 1. ON(C,A) 2. 3. ON(B,D) 4. 5. ON(C,A) ON(B,D) 6. 7. ONTABLE(A) 8. ONTABLE(D) 9. 187

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING 10. 11. ON(B,D) 12. 13. ON(C,A) 14. 15. ON(C,A) ON(B,D) 16. ONTABLE(A) 17. ONTABLE(D) 18. 19.The method is to  Investigate the first node on the stack ie the top goal.  If a sequence of operators is found that satisfies this goal it is removed and the next goal is attempted.This continues until the goal state is empty. UNIT V EXPERT SYSTEMSExpert systems - Architecture of expert systems, Roles of expert systems - KnowledgeAcquisition – Meta knowledge, Heuristics. Typical expert systems - MYCIN, DART,XOON, Expert systems shells. KEY NOTESEXPERT SYSTEMSRole of Expert SystemsExpert Systems solve problems that are normally solved by human ―experts\". To solvethis, expert systems need access to a substantial domain knowledge base, which must bebuilt as efficiently as possible.Architecture of Expert SystemsExpert systems typically contain the following four components:  Knowledge-Acquisition Interface  User Interface  Knowledge Base  Inference Engine The most important modules that make up a rule-based expert system. The user interacts with the system through a user interface which may use menus, natural language or any other style of interaction). Then an inference engine is used to reason with both the expert knowledge (extracted from our friendly expert) and data specific to the particular problem being solved. The expert knowledge will typically be in the form of a set of IF-THEN rules. The case specific data includes both data provided by 188

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGthe user and partial conclusions (along with certainty measures) based on this data. Ina simple forward chaining rule-based system the case specific data will be theelements in working memory.Representing and using Domain KnowledgeThe most widely used way of representing domain knowledge in expert systems is as aset of production rules, Which are combined with frame system .Meta Knowledge  Meta-knowledge is knowledge about knowledge. For example, knowledge about how an expert system makes decisions would be considered meta-knowledge.  Knowledge AcquisitionIt is the process of extracting, structuring and organizing knowledge from one source,usually human experts, so it can be used in software such as an ES. The following stepsare followed.1.Initial knowledge base construction2.Refinement of the knowledge base.Several learning Techniques:MOLE,SALT,META-DENDRALEXPERT SYSTEM SHELLSThey act as an interpreter between the user interface and the computer O.S to manage theinput and output of the data. It also manipulates the information provided by the user inconjunction with the knowledge base to arrive at a particular conclusion. One example isEMYCIN(Empty MYCIN)To facilitate interaction, expert system must have two capabilities1.Explain its reasoning2.Acquire new knowledge and modification of old knowledge. 189

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING PART - A1. What are expert systems? Expert systems are complex AI programs. They solve problems that are normallysolved by human experts. To solve expert level problems, expert systems need access to asubstantial knowledge base which must be built as efficiently as possible.2.What are called expert system shells? Since the systems were constructed as a set of declarativerepresentations(rules)combined with interpreter for those representations, it was possibleto separate the interpreter from the domain specific knowledge and thus to create asystem by adding new knowledge corresponding to new problem domain. the resultinginterpreters are called shells.3.What are the capabilities which make expert system an effective tool? Expert systems must have the following capabilities.  Explain its reasoning  Acquire new knowledge and modifications of old knowledge.4.How are expert systems built/ A knowledge engineer interviews a domain expert to give expert knowledgewhich is then translated into rules. After the initial system is built it must be iterativelyrefined until it approximates expert level performance.5.What is the importance of knowledge acquisition?  Entering knowledge  maintaining knowledge base consistency  Ensuring knowledge based completeness6.What kind of things can we do with visual image?  Signal processing  Measurement Analysis  Pattern Recognition  Image understanding7.What is sensor fusion? Integrating different sense modalities is called sensor fusion.8.What are the main design issues in speech recognition system?  Speaker dependence versus speaker independence  Continuous verses Isolated word speech  Real time versus offline processing  Large versus small vocabulary  Broad versus narrow grammar9.What is Hidden Markova Model(HMM)?[April'12] It is a collection of states and transitions. Each transition leaving a state is markedwith  probability with which that transition is taken 190

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  an output symbol  the probability that the output symbol is emitted with the transition takenThe problem of decoding a speech waveform turns into the problem of finding the mostlikely path thro HMM.10.What is compliant motion? The type of motion which reacts to forces generated by the World is calledcompliant motion.11.Define knowledge. It is the fact or condition of knowing something with familiarity gained throughexperience or association.12.What are the types of knowledge?  Priori knowledge  Posteriori knowledge  Procedural knowledge  Declarative knowledge  Tacti knowledge13.What is MOLE? It is a knowledge acquisition system which is used for heuristic classificationproblems such as diagnosing diseases .It is used in conjunction with the cover anddifferentiate problem solving method.14.What are knowledge representation methods?  Production rule  Semantic nets  Schemata  Frames15.Define production rule It is frequently used method to formulate the knowledge in expert systems formalvariation of this methodology is Backus Naur form. Comprises of lang syntax, grammarand a parse tree.16.What are the application areas of expert systems?  Analysis  Control  Instruction  Monitoring  Repair  Planning  Prediction 191

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING17.What is MYCIN? It is an expert system developed in 1970‘s.Its job was to diagnose and recommendtreatment for certain blood infections. It was developed in order to explore how humanexperts make these rough guess based on partial information.18.What is inference engine? It is the main processing element of the expert system. It is the software thatprovide the reasoning mechanism in an expert system.19.What are the operators used in propositional logic?  AND  OR  IMPLICATION  DOUBLE IMPLICATION20.EPISTEMOLOGY It is the branch of philosophy that studies the nature, methods, limitations andvalidity of knowledge and belief. PART - B1.What is expert system? Write its advantages and disadvantages of ExpertSystems. An Expert System is a computer program coded to simulate knowledge andbehavior of an individual or an organization which is expert in some particular field,usually all expert systems contain a knowledge base which is accessible by a set of rulesdepending on specific situations. Among the number of expert systems the best examplesof they can be named as Chess Game or the medical diagnosis expert systemAdvantages  The knowledge base can be updated and extended  They can contain a large amount of informationDisadvantages  They are not able to learn from the mistakes  They cannot creatively come with new solutions for the issues  It‘s not easily achievable to mimic the exact knowledge of an Expert in Computer ProgramsComponents of an Expert System:An Expert System contains of 3 components, which are User Interface , InferenceEngine and Knowledge base.2.Explain Expert System Architecture.Architecture of Expert Systems Expert systems typically contain the following four components:  Knowledge-Acquisition Interface  User Interface 192

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING Knowledge Base Inference Engine The most important modules that make up a rule-based expert system. The userinteracts with the system through a user interface which may use menus, naturallanguage or any other style of interaction). Then an inference engine is used to reasonwith both the expert knowledge (extracted from our friendly expert) and data specificto the particular problem being solved. The expert knowledge will typically be in theform of a set of IF-THEN rules. The case specific data includes both data provided bythe user and partial conclusions (along with certainty measures) based on this data. Ina simple forward chaining rule-based system the case specific data will be theelements in working memory.3.Explain Knowledge Engineering in detail4.What are the steps to building expert system? Write its applications5.Explain MYCIN case study. 193

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING 194

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING 195

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING IT6004 - SOFTWARE TESTINGIT6004 SOFTWARE TESTING L T PC 3003UNIT I INTRODUCTION 9Testing as an Engineering Activity – Testing as a Process – Testing axioms – Basicdefinitions –Software Testing Principles – The Tester‘s Role in a Software DevelopmentOrganization – Origins of Defects – Cost of defects – Defect Classes – The DefectRepository and Test Design – Defect Examples – Developer/Tester Support ofDeveloping a Defect Repository – Defect Prevention strategies.UNIT II TEST CASE DESIGN 9Test case Design Strategies – Using Black Bod Approach to Test Case Design – RandomTesting –Requirements based testing – Boundary Value Analysis – Equivalence ClassPartitioning – Statebased testing – Cause-effect graphing – Compatibility testing – userdocumentation testing– domain testing – Using White Box Approach to Test design –Test Adequacy Criteria – static testing vs. structural testing – code functional testing –Coverage and Control Flow Graphs – Covering Code Logic – Paths – code complexitytesting – Evaluating Test Adequacy Criteria.UNIT III LEVELS OF TESTING 9The need for Levers of Testing – Unit Test – Unit Test Planning – Designing the UnitTests – The Test Harness – Running the Unit tests and Recording results – Integrationtests – Designing Integration Tests – Integration Test Planning – Scenario testing –Defect bash elimination System Testing – Acceptance testing – Performance testing –Regression Testing –Internationalization testing – Ad-hoc testing – Alpha, Beta Tests –Testing OO systems – Usability and Accessibility testing – Configuration testing –Compatibility testing – Testing the documentation –Website testing.UNIT IV TEST MANAGEMENT 9People and organizational issues in testing – Organization structures for testing teams –testing services – Test Planning – Test Plan Components – Test Plan Attachments –Locating Test Items –test management – test process – Reporting Test Results – The roleof three groups in Test Planning and Policy Development – Introducing the test specialist– Skills needed by a test specialist – Building a Testing Group.UNIT V TEST AUTOMATION 9Software test automation – skill needed for automation – scope of automation – designand architecture for automation – requirements for a test tool – challenges in automation– Test metrics and measurements – project, progress and productivity metrics.TEXT BOOKS:1. Srinivasan Desikan and Gopalaswamy Ramesh, ―Software Testing – Principles andPractices‖, Pearson Education, 2006. 196

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING2. Ron Patton, ―Software Testing‖, Second Edition, Sams Publishing, Pearson Education,2007.REFERENCES:1. Ilene Burnstein, ―Practical Software Testing‖, Springer International Edition, 2003.2. Edward Kit,‖ Software Testing in the Real World – Improving the Process‖, PearsonEducation, 1995.3. Boris Beizer,‖ Software Testing Techniques‖ – 2nd Edition, Van Nostrand Reinhold,New York, 1990.4. Aditya P. Mathur, ―Foundations of Software Testing _ Fundamental Algorithms andTechniques‖, Dorling Kindersley (India) Pvt. Ltd., Pearson Education, 2008. 197

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING IT6004 - SOFTWARE TESTING Index SheetUNIT TOPIC PAGE NUMBER No. Notes PART-A PART-B I Introduction 199 201 204II Test Case Design 209 211 214III Levels Of Testing 219 220 223IV Test Management 227 228 231V Test Automation 235 237 240ANNA UNIVERSITY QUESTIONS PAPER 244 198

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING UNIT I INTRODUCTIONTesting as an Engineering Activity – Testing as a Process – Testing axioms – Basicdefinitions –Software Testing Principles – The Tester‘s Role in a Software DevelopmentOrganization – Origins of Defects – Cost of defects – Defect Classes – The DefectRepository and Test Design – Defect Examples – Developer/Tester Support ofDeveloping a Defect Repository – Defect Prevention strategies. KEY NOTES1.The Role of process in Software quality.Process - DefinitionFigure - Components of an engineered process.Capability Maturity Model.Testing Maturity model ( TMM )2.Testing as a Process.ValidationVerificationFigure : Example Processes embedded in the software development process.TestingDebugging3.Overview of the Testing Maturity Model(TMM) & the test related activities thatshould be done for V-model architecture.Test related issuesBenefits of test process improvementIntroduction to TMMTMM levelsFigure : The internal Structure of TMM maturity level.Figure : Five level Structure of TMM.Figure : The Extended / Modified V model4.Software Testing Principles.Define - Principle.Principle 1 : Revealing defects and evaluating quality.Principle 2 : Effectiveness of testing effort.Principle 3 : Test results should be inspected.Principle 4 : Test case must contain the expected output.Principle 5 : Test case should be developed for both valid and invalid input conditions.Principle 6 : Defects ratio.Principle 7 : Testing should be carried out by a group.Principle 8 : Tests must be repeatable and reusable.Principle 9 : Testing should be planned. 199

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGPrinciple 10: Testing activities should be integrated into software lifecycle.Principle 11: Testing is a creative and challenging task.5.Origins of defects.Sources of defectsFigure : Origins of defects.Fault model.6.Defect Classes ,Defect Repository, and Test Design.Figure: Defect classes and a defect repository.Requirements and specification defects.Functional Description defects.Feature defects.Feature interaction defects.Interface description defects. Design defects. Algorithmic and processing defects. Control ,logic, and sequence defects. Data defects. Module interface description defects. Functional description defects. External interface description defects. Coding defects. Algorithmic and processing defects. Control ,logic, and sequence defects. Typographical defects. Initialization defects. Dataflow defects. Data defects. Module interface defects. Code document defects. External hardware and software interface defects. Testing defects. Test harness defects. Test case design and test procedure Defects.7.Defect Examples: The Coin ProblemPreconditionPost conditionFigure : a sample specification with defects.Figure : a sample design specification with defects. Algorithmic and processing defects. Control ,logic, and sequence defects. 200