BE COMPS RAIT, NERUL - HOME - BE



center-922969Department of Computer EngineeringLab ManualFinal Year Semester-VIISubject: Artificial IntelligenceOdd SemesterInstitutional Vision, Mission and Quality PolicyOur VisionTo foster and permeate higher and quality education with value added engineering, technology programs, providing all facilities in terms of technology and platforms for all round development with societal awareness and nurture the youth with international competencies and exemplary level of employability even under highly competitive environment so that they are innovative adaptable and capable of handling problems faced by our country and world at large.RAIT’s firm belief in new form of engineering education that lays equal stress on academics and leadership building extracurricular skills has been a major contribution to the success of RAIT as one of the most reputed institution of higher learning. The challenges faced by our country and world in the 21 Century needs a whole new range of thought and action leaders, which a conventional educational system in engineering disciplines are ill equipped to produce. Our reputation in providing good engineering education with additional life skills ensure that high grade and highly motivated students join us. Our laboratories and practical sessions reflect the latest that is being followed in the Industry. The project works and summer projects make our students adept at handling the real life problems and be Industry ready. Our students are well placed in the Industry and their performance makes reputed companies visit us with renewed demands and vigour.Our MissionThe Institution is committed to mobilize the resources and equip itself with men and materials of excellence thereby ensuring that the Institution becomes pivotal center of service to Industry, academia, and society with the latest technology. RAIT engages different platforms such as technology enhancing Student Technical Societies, Cultural platforms, Sports excellence centers, Entrepreneurial Development Center and Societal Interaction Cell. To develop the college to become an autonomous Institution & deemed university at the earliest with facilities for advanced research and development programs on par with international standards. To invite international and reputed national Institutions and Universities to collaborate with our institution on the issues of common interest of teaching and learning sophistication.RAIT’s Mission is to produce engineering and technology professionals who are innovative and inspiring thought leaders, adept at solving problems faced by our nation and world by providing quality education.The Institute is working closely with all stake holders like industry, academia to foster knowledge generation, acquisition, dissemination using best available resources to address the great challenges being faced by our country and World. RAIT is fully dedicated to provide its students skills that make them leaders and solution providers and are Industry ready when they graduate from the Institution.We at RAIT assure our main stakeholders of students 100% quality for the programmes we deliver. This quality assurance stems from the teaching and learning processes we have at work at our campus and the teachers who are handpicked from reputed institutions IIT/NIT/MU, etc. and they inspire the students to be innovative in thinking and practical in approach. We have installed internal procedures to better skills set of instructors by sending them to training courses, workshops, seminars and conferences. We have also a full fledged course curriculum and deliveries planned in advance for a structured semester long programme. We have well developed feedback system employers, alumni, students and parents from to fine tune Learning and Teaching processes. These tools help us to ensure same quality of teaching independent of any individual instructor. Each classroom is equipped with Internet and other digital learning resources.The effective learning process in the campus comprises a clean and stimulating classroom environment and availability of lecture notes and digital resources prepared by instructor from the comfort of home. In addition student is provided with good number of assignments that would trigger his thinking process. The testing process involves an objective test paper that would gauge the understanding of concepts by the students. The quality assurance process also ensures that the learning process is effective. The summer internships and project work based training ensure learning process to include practical and industry relevant aspects. Various technical events, seminars and conferences make the student learning complete.Our Quality PolicyOur Quality PolicyIt is our earnest endeavour to produce high quality engineering professionals who are innovative and inspiring, thought and action leaders, competent to solve problems faced by society, nation and world at large by striving towards very high standards in learning, teaching and training methodologies.Our Motto: If it is not of quality, it is NOT RAIT!Dr. Vijay D. Patil President, RAESDepartmental Vision, MissionVisionTo impart higher and quality education in computer science with value added engineering and technology programs to prepare technically sound, ethically strong engineers with social awareness. To extend the facilities, to meet the fast changing requirements and nurture the youths with international competencies and exemplary level of employability and research under highly competitive environments.MissionTo mobilize the resources and equip the institution with men and materials of excellence to provide knowledge and develop technologies in the thrust areas of computer science and Engineering. To provide the diverse platforms of sports, technical, cocurricular and extracurricular activities for the overall development of student with ethical attitude. To prepare the students to sustain the impact of computer education for social needs encompassing industry, educational institutions and public service. To collaborate with IITs, reputed universities and industries for the technical and overall upliftment of students for continuing learning and entrepreneurship.Departmental Program Educational Objectives (PEOs)Learn and IntegrateTo provide Computer Engineering students with a strong foundation in the mathematical, scientific and engineering fundamentals necessary to formulate, solve and analyze engineering problems and to prepare them for graduate studies.Think and Create To develop an ability to analyze the requirements of the software and hardware, understand the technical specifications, create a model, design, implement and verify a computing system to meet specified requirements while considering real-world constraints to solve real world problems.Broad BaseTo provide broad education necessary to understand the science of computer engineering and the impact of it in a global and social context.Techno-leaderTo provide exposure to emerging cutting edge technologies, adequate training & opportunities to work as teams on multidisciplinary projects with effective communication skills and leadership qualities.Practice citizenshipTo provide knowledge of professional and ethical responsibility and to contribute to society through active engagement with professional societies, schools, civic organizations or other community activities.Clarify Purpose and PerspectiveTo provide strong in-depth education through electives and to promote student awareness on the life-long learning to adapt to innovation and change, and to be successful in their professional work or graduate studies. Departmental Program Outcomes (POs)Foundation of computing - An ability to apply knowledge of computing, applied mathematics, and fundamental engineering concepts appropriate to the discipline.Experiments & Data Analysis - An ability to understand, identify, analyze and design the problem, implement and validate the solution including both hardware and software. Current Computing Techniques – An ability to use current techniques, skills, and tools necessary for computing practice . Teamwork – An ability to have leadership and management skills to accomplish a common goal.Engineering Problems - an ability to identify, formulates, and solve engineering problems.Professional Ethics – An understanding of professional, ethical, legal, security and social issues and responsibilities. Communication – An ability to communicate effectively with a range of audiences in both verbal and written form. Impact of Technology – An ability to analyze the local and global impact of computing on individuals, organizations, and society. Life-long learning – An ability to recognize the need for, and an ability to engage in life-long learning.Contemporary Issues – An ability to exploit gained skills and knowledge of contemporary issues.Professional Development – Recognition of the need for and an ability to engage in continuing professional development and higher studies.Employment - An ability to get an employment to the international repute industries through the training programs, internships, projects, workshops and seminars. IndexSr. No.ContentsPage No.1.List of Experiments82.Course Objectives, Course Outcomes and Experiment Plan93.Study and Evaluation Scheme124.Experiment No. 1135.Experiment No. 2206.Experiment No. 3247.Experiment No. 4288.Experiment No. 5339.Experiment No. 64410.Experiment No. 74911.Experiment No. 86312.Experiment No. 96813.Experiment No. 1086List of ExperimentsSr. No.Experiments Name1Introduction to PROLOG programming & to Write simple prolog program in SWI PROLOG.2Description of PEAS for various task environments.3To analyse the implementation of water jug problem.4Write a Program to implement BFS search method.5Write a Program to implement informed A* search method.6Case Study on NLP/Expert system based paper published in IEEE/ACM/Springer or any prominent journal.7Write a Program to implement Minmax search algorithm.8Case Study on Belief network based paper published in IEEE/ACM/Springer or any prominent journal.9Write a Program to implement Eight puzzle problems.10Write a Program to implement hill Climbing search algorithm. Course Objective, Course Outcome& Experiment PlanCourse Objectives:To conceptualize the basic ideas and techniques underlying the design of intelligent systems.To make students understand and explore the mechanism of mind that enable intelligent thought and action.To make students understand advanced representation formalism and search techniquesTo make students understand how to deal with uncertain and incomplete informationCourse Outcomes:CO1Ability to develop a basic understanding of AI building blocks presented in intelligent agents.CO2Ability to choose an appropriate problem solving method and knowledge representation technique.CO3Ability to analyze the strength and weaknesses of AI approaches to knowledge– intensive problem solving.CO4Ability to design models for reasoning with uncertainty as well as the use of unreliable information.CO5Conceptualize the basic ideas of planning and learning process of a system.CO6Ability to design and develop the AI applications in real world scenario.Experiment Plan:ModuleNo.WeekNo.Experiments NameCourseOutcomeWeightage1W1,W2Introduction to PROLOG programming & to Write simple Prolog program in SWI PROLOGCO452W3Description of PEAS for various task environmentCO153W4To analyse the implementation of water jug problem.CO154W5Write a Program to implement BFS search method.CO235W6, W7Write a Program to implement informed A* search method.CO236W8Case Study on NLP/Expert system based paper published in IEEE/ACM/Springer or any prominent journalCO647W9Write a Program to implement Minmax search algorithm.CO3108W10Case Study on Belief network based paper published in IEEE/ACM/Springer or any prominent journalCO459W11Write a Program to implement Eight puzzle problem.CO51010W12Write a Program to implement hill Climbing search algorithmCO210Mapping Course Outcomes (CO) - Program Outcomes (PO)Subject WeightCourse OutcomesContribution to Program outcomesPaPbPcPdPePfPgPhPiPjPkPlPRATICAL40%CO1: Ability to develop a basic understanding of AI building blocks presented in intelligent agents. 1121212CO2: Ability to choose an appropriate problem solving method and knowledge representation technique.13222CO3: Ability to analyze the strength and weaknesses of AI approaches to knowledge– intensive problem solving.2224CO4: Ability to design models for reasoning with uncertainty as well as the use of unreliable information.2233CO5: Conceptualize the basic ideas of planning and learning process of a system.2323CO6: Ability to design and develop the AI applications in real world scenario1111111111Study and Evaluation SchemeCourse CodeCourse NameTeaching SchemeCredits AssignedCPC703Artificial IntelligenceTheoryPracticalTutorialTheoryPracticalTutorialTotal0402--0401--05Course CodeCourse NameExamination SchemeCPC703Artificial IntelligenceTerm WorkOralTotal252550Term Work:Term work assessment must be based on the overall performance of the student with every experiment graded from time to time. The grades should be converted into marks as per the Credit and Grading System manual and should be added and averaged.The final certification and acceptance of term work ensures satisfactory performance of laboratory work and minimum passing marks in term work.Practical & Oral:Oral exam will be based on the entire syllabus of Artificial Intelligence.Artificial IntelligenceExperiment No. : 1Introduction to SWI- PROLOG Programming with the help of simple programsExperiment No. 1Aim: Introduction to SWI- PROLOG Programming with the help of simple programsObjectives: From this experiment, the student will be able to Understand logical programming syntax and semanticsDesign programs in PROLOG languageOutcomes: The learner will be able to Use current techniques, tools necessary for computing practice using PROLOG.Applying knowledge of computing, applied mathematics to solve engineering problems using logical programming.Ability to recognize the need and to engage in lifelong learning for logical programming. Software Required : SWI-PrologTheory: Prolog?is a general purpose?logic programming?language associated with?artificial intelligence?and?computational linguistics.Prolog has its roots in?first-order logic, a?formal logic, and unlike many other?programming languages, Prolog is?declarative: the program logic is expressed in terms of relations, represented as facts and?rules. A computation is initiated by running a?query?over these relations. Prolog is well-suited for specific tasks that benefit from rule-based logical queries such as searching databases, voice control systems, and filling templates.Rules and facts:Prolog programs describe relations, defined by means of clauses. Pure Prolog is restricted to Horn clauses. There are two types of clauses: facts and rules. A rule is of the formHead:- Body.and is read as "Head is true if Body is true". A rule's body consists of calls to predicates, which are called the rule's goals. The built-in predicate, /2 (meaning a 2-arity operator with name,) denotes conjunction of goals, and; /2 denotes disjunction. Conjunctions and disjunctions can only appear in the body, not in the head of a rule.Clauses with empty bodies are called facts. An example of a fact is:cat (tom).which is equivalent to the rule:cat(tom) :- true.The built-in predicate true/0 is always true.Given the above fact, one can ask:is tom a cat??- cat(tom). Yeswhat things are cats? ?- cat(X). X = tomClauses with bodies are called rules. An example of a rule is:animal(X) :- cat(X).If we add that rule and ask what things are animals? ?- animal(X). X = tomProlog must be able to handle arithmetic in order to be a useful general purpose programming language. However, arithmetic does not fit nicely into the logical scheme of things. That is, the concept of evaluating an arithmetic expression is in contrast to the straight pattern matching we have seen so far. For this reason, Prolog provides the built-in predicate 'is' that evaluates arithmetic expressions. Its syntax calls for the use of operators.X is <arithmetic expression>The variable X is set to the value of the arithmetic expression. On backtracking it is unassigned. The variable X is set to the value of the arithmetic expression. On backtracking it is unassigned. The arithmetic expression looks like an arithmetic expression in any other programming language.Here is how to use Prolog as a calculator.?- X is 2 + 2.X = 4?- X is 3 * 4 + 2.X = 14Parentheses clarify precedence.?- X is 3 * (4 + 2).X = 18?- X is (8 / 4) / 2.X = 1In addition to 'is,' Prolog provides a number of operators that compare two numbers. These include 'greater than', 'less than', 'greater or equal than', and 'less or equal than.' They behave more logically, and succeed or fail according to whether the comparison is true or false. Notice the order of the symbols in the greater or equal than and less than or equal operators. They are specifically constructed not to look like an arrow, so that the use arrow symbols in programs is without confusion.X > YX < YX >= YX =< YProcedure/ Program: 1 (A). Sample program to demonstrate Rules and facts.1.(B) Sample program to demonstrate the relationship in prolog.1.(C) Sample program to demonstrate the relationship in prolog.Results:1 (A). Sample program to demonstrate Rules and facts.1.(B) Sample program to demonstrate the relationship in prolog.1.(C) Sample program to demonstrate the relationship in prolog.Conclusion:Demonstration and implementation of arithmetic operations, rules and facts, relationship is done using SWI-Prolog software. Semantics and syntax of prolog language is well understood. Logical programming concepts required to execute aritificial intelligence problem is well understood Viva Questions: Note how SWI-Prolog is better than turbo prolog.What are rules and facts? Explain syntax and semantics. References:1. Ivan Bratko "PROLOG Programming for Artificial Intelligence", Pearson Education,Third Edition.2. Elaine Rich and Kevin Knight "Artificial Intelligence "Third Edition3. Davis E.Goldberg, "Genetic Algorithms: Search, Optimization and Machine Learning",Addison Wesley, N.Y., 1989.Han Kamber, “Data Mining Concepts and Techniques”, Morgann Kaufmann PublishersArtificial IntelligenceExperiment No. : 2Description of PEAS for various task environmentExperiment No. 2Aim: Description of PEAS for various task environmentObjectives: From this experiment, the student will be able to Understand different types of agent.Identify PEAS description for different task environment.Outcomes: The learner will be able to Understand, identify, analyse and design the problem, implement and validate the solution for the given task environment.Applying fundamental engineering concepts appropriate to the discipline. Potential to formulate and solve engineering problems in identifying the task environment.Software Required: Given problem definition.Theory:An agent is something that perceives and acts in an environment. The agent function for an agent specifies the action taken by the agent in response to any percept sequence. An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.Figure: Agents interact with environments through sensors and actuators.A performance measure embodies the criterion for success of an agent's behavior. When an agent is plunked down in an environment, it generates a sequence of actions according to the percepts it receives. This sequence of actions causes the environment to go through a sequence of states. If the sequence is desirable, then the agent has performed well.A rational agent acts so as to maximize the expected value of the performance measure, given the percept sequence it has seen so far. A task environment specification includes the performance measure, the external environment, the actuators, and the sensors. In designing an agent, the first step must always be to specify the task environment as fully as possible. Task environments vary along several significant dimensions. They can be fully or partially observable, deterministic or stochastic, episodic or sequential, static or dynamic, discrete or continuous, and single-agent or multiagent.The task environment for an agent is comprised of PEAS (Performance measure, Environment, Actuators, Sensors)PEAS specify the setting of an intelligent agent:P: The performance measure defines degree of success.E: What does the agent know about the environment?A: The actions that the agent can perform.S: Everything that an agent as perceived so far through its sensors.Procedure/ Program: Example of Agent types and their PEAS (performance, environment, actuators, sensor) Descriptions.English Tutor Example: PEASAgent: Interactive English tutor Performance measure: Maximize student's score on test Environment: Set of students Actuators: Screen display (exercises, suggestions, corrections) Sensors: Keyboard7. Result:Robot : PEAS Agent: Part-picking robot Performance measure: Percentage of parts in correct bins Environment: Convey p, or belt with parts, bins Actuators: Jointed arm and hand Sensors: Camera, joint angle sensorsMedical Example: PEAS Agent: Medical diagnosis system Performance measure: Healthy patient, minimize costs, lawsuits Environment: Patient, p, hospital, staff Actuators: Screen display (questions, tests, diagnoses, treatments, referrals) Sensors: Keyboard (entry of symptoms, findings, patient's answers)Taxi Example - PEASFirst specify the setting for agent design. Consider, e.g., the task of designing an automated taxi driver: Performance measure: Safe, fast, legal, comfortable trip, maximize profits Environment: Roads other traffic Environment: Roads, other traffic, pedestrians, customers Actuators: Steering wheel, accelerator, brake, signal, horn Sensors: Cameras, sonar, speedometer, GPS, odometer, engine sensors, keyboardChess player Performance measure: 2 points/win, 1 points/draw, 0 for loss Environment: Chess board, pieces, rules, move history Actuators: move pieces, resign Sensors: observe board positionInternet shopping AgentPerformance: measure (price, quality, efficiency, appropriateness, environment)Environment: Current or future websites, vendors, shippersActuators: Display to user, follow url, fill in form Sensors : HTML pages(text ,graphics ,scripts)Spam FilterPerformance measure: Interetspeed, sort able mailsEnvironment: A user’s email accountActuators: Mark as spam, delete, etc.Sensors: Incoming messages, other information about user’s accountAutomated taxi driverPerformance measure: Safe, fast, legal, comfortable trip, maximize Environment: Roads, other traffic, pedestrians, customers Actuators: Steering wheel, accelerator, brake, signal, horn Sensors: Cameras, sonar, speedometer, GPS, odometer, engine sensors, keyboardPart-Sorting RobotPerformance measure: Percentage of parts in correct binsEnvironment: Conveyor belt Actuators: Robotic armSensors: Camera, joint angle sensors8. Conclusion: For any given problem for a particular agent the required performance measure to measure the accuracy of an agent, the environment behaviour of an agent, the sensors required to receive the input from environment and the actuators required to perform the task is carefully observed and analysed.9. Viva Questions:Develop a PEAS description of the task environment for “Autonomous Mars Rover” agent.Explain utility based agent with help of a neat diagram .Explain learning agent with help of a neat diagram Explain goal based agent with a neat diagram10. References:1. Elaine Rich and Kevin Knight "Artificial Intelligence "Third Edition2. Davis E.Goldberg, "Genetic Algorithms: Search, Optimization and Machine Learning",Addison Wesley, N.Y., 1989.3. Han Kamber, “Data Mining Concepts and Techniques”, Morgann Kaufmann PublishersArtificial IntelligenceExperiment No. : 3To analyse the implementation of water jug problem.Experiment No. 3Aim: To analyse the implementation of water jug problem.Objectives: From this experiment, the student will be able to Understand and analyse state space problem.Solving water jug problem.Outcomes: The learner will be able to Understand, identify, analyse and design the problem, implement and validate the solution for the given water jug problem.Applying fundamental engineering concepts appropriate to the discipline. Potential to formulate and solve engineering problems in identifying the state space for given water jug problem.Software Required : SWI-Prolog/C language/Java languageTheory: This is the jug problem using simple depth-first search of a graph. The modified water-jug problem is as follows: Jug A holds 4 liters, and jug B holds 3 liters. There is a pump, which can be used to fill either Jug. How can you get exactly 2 liters of water into the 4-liter jug?Assumptions:We can fill a jug from the pumpWe can pour water out of the jug onto the ground We can pour water from one jug to anotherThere are no other measuring devices availableTo solve the water jug problem, apart from problem statement we also need a control structure that loops through a simple cycle in which some rule whose left side matches the current state is chosen, the appropriate change to state is made as described in corresponding right side and the resulting state is checked to see if it corresponds to a goal state. As long as it does not the cycle continues.Procedure/ Program: Production rules for the water-jug problemRule Current stateNew stateRules 1(x, y)if x<4(4,y)Fill the 4-gallon jug.2(x, y)if y<3(x,3)Fill the 3-gallon jug.3(x, y)if x>0(x-d, y)Pour some water out of 4-gallon jug.4(x, y)if y>0(x, y-d)Pour some water out of 3-gallon jug.5(x, y)if x>0(0, y)Empty the 4-gallon jug on ground.6(x, y)if y>0(x, 0)Empty the 3-gallon jug on ground.7(x, y)if (x+y)>=4&(y>0)(4,y-(4-x))Pour water from 3-gallon jug into the 4-gallon jug until the 4-gallon jug is full.8if (x+y)>=3&(x>0)(x-(3-y),3)Pour water from 4-gallon jug into the 3-gallon jug until the 3-gallon jug is full.9(x, y)if (x+y)<=4&(y>0)(x+y,0)Pour all the water from 3-gallon jug into the 4-gallon jug.10(x, y)if (x+y)<=3&(x>0)(0,x+y)Pour all the water from 4-gallon jug into the 3-gallon jug.11(0,2)(2,0)Pour the 2 gallons from the 3-gallon jug into the 4-gallon jug.12(2,y)(0,y)Empty 2 gallons in the 4-gallon jug on the ground. Results: Output+-----------------------------4-3 Water Jug Problem--------------------------+?Fill the 4-Gallon Jug: (0,0) --> (4,0) ??Fill the 3-Gallon Jug: (4,0) --> (4,3) ??Empty the 4-Gallon jug on ground: (4,3) --> (0,3) ??Pour all the water from 3-Gallon jug to 4-gallon: (0,3) --> (3,0) ??Fill the 3-Gallon Jug: (3,0) --> (3,3) ??Pour water from 3-Gallon jug to 4-gallon until it is full: (3,3) --> (4,2) ??Empty the 4-Gallon jug on ground: (4,2) --> (0,2) ??Pour all the water from 3-Gallon jug to 4-gallon: (0,2) --> (2,0) ?? ??Press the SPACE bar ?? ?? ?? ?Conclusion: In state space problem, the problem consists of four components: initial state, a set of actions, a goal test functions and a path cost function is analysed. The environment of the problem is represented by a state space and path from initial state to goal state is been analysed.Viva Questions: Give the initial state , goal test, successor function, and cost function for each of the following a. A 3 foot tall monkey is in a room where some bananas are suspended from the 8 foot ceiling . He would like to get the bananas. The room contains 2 stackable, moveable, climbable 3 foot high crates. b. You have three jugs, measuring 12 gallons , 8 gallons and 3 gallons and a water faucet . You can fill the jugs up or empty them out from one to another or onto the ground. You need to measure out exactly one gallon.Explain 8-puzzle problem.Describe state space problem for vacuum cleaner problem References:1. Elaine Rich and Kevin Knight "Artificial Intelligence "Third Edition2. Davis E.Goldberg, "Genetic Algorithms: Search, Optimization and Machine Learning",Addison Wesley, N.Y., 1989.3. Han Kamber, “Data Mining Concepts and Techniques”, Morgann Kaufmann PublishersArtificial IntelligenceExperiment No. : 4Write a Program to implement BFS search method.Experiment No. 4Aim: Write a program to implement BFS search method.Objectives: From this experiment, the student will be able to Understand and implement BFS algorithm.Analyse time complexity of the search algorithm.Outcomes: The learner will be able to Ability to analyse the local and global impact of computing in searching techniques.Understand, identify, analyse and design the problem, implement and validate the solution for the BFS search method.Ability to applying knowledge of computing in search technique areas.Software Required : C language/Java languageTheory: Uninformed strategies use only the information available in the problem definitionBreadth-first searchUniform-cost searchDepth-first searchDepth-limited searchIterative deepening searchBreadth-first searchBreadth-first search is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. Breadth-first search can be implemented by calling TREE-SEARCH with an empty fringe that is a first-in-first-out (FIFO) queue, assuring that the nodes that are visited first will be expanded first. It uses two queues for its implementation: open, close QueueChildren are added from backend of queue.AlgorithmCreate single member queue comprising of root node.If 1st Member of Queue is GOAL then goto Step 5.If first member of queue is not GOAL then remove it and add to CLOSE or Visited Queue. Consider its Children/ successor, if any add them from BACK/REAR [FIFO]If queue is not empty then goto Step 2, If queue is empty then goto Step 6Print “SUCCESS” and stop.Print “FALIURE” and stop.[Note: Trace the algorithm with example.]Performance Comparison:Completeness: yes, it gives shallowest goalOptimality: yes, provided path cost is non- decreasingTime complexity: O(b ? + ?)Space complexity: O(b ? + ?)Procedure/ Program: Code:import java.util.InputMismatchException;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner; public class BFS{ private Queue<Integer> queue; public BFS() { queue = new LinkedList<Integer>(); } public void bfs(int adjacency_matrix[][], int source) { int number_of_nodes = adjacency_matrix[source].length - 1; int[] visited = new int[number_of_nodes + 1]; int i, element; visited[source] = 1; queue.add(source); while (!queue.isEmpty()) { element = queue.remove(); i = element; System.out.print(i + "\t"); while (i <= number_of_nodes) { if (adjacency_matrix[element][i] == 1 && visited[i] == 0) { queue.add(i); visited[i] = 1; } i++; } } } public static void main(String... arg) { int number_no_nodes, source; Scanner scanner = null; try { System.out.println("Enter the number of nodes in the graph"); scanner = new Scanner(System.in); number_no_nodes = scanner.nextInt(); int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1]; System.out.println("Enter the adjacency matrix"); for (int i = 1; i <= number_no_nodes; i++) for (int j = 1; j <= number_no_nodes; j++) adjacency_matrix[i][j] = scanner.nextInt(); System.out.println("Enter the source for the graph"); source = scanner.nextInt(); System.out.println("The BFS traversal of the graph is "); BFS bfs = new BFS(); bfs.bfs(adjacency_matrix, source); } catch (InputMismatchException inputMismatch) { System.out.println("Wrong Input Format"); } scanner.close(); }}Results:Conclusion: BFS is an uniformed search technique. It selects the shallowest unexpanded node in the search tree for expansion. It is complete, optimal for unit step costs and has time and space complexity of O(bd). BFS is implemented in C or java .Viva Questions: Explain time and space complexity of BFS.DFS can be viewed as a special case of depth limited search with l=∞. Give reason to support the above statement.Explain any two uninformed search strategy used in problem solving by searching. References:1. Elaine Rich and Kevin Knight "Artificial Intelligence "Third Edition2. Davis E.Goldberg, "Genetic Algorithms: Search, Optimization and Machine Learning",Addison Wesley, N.Y., 1989.3. Han Kamber, “Data Mining Concepts and Techniques”, Morgann Kaufmann PublishersArtificial IntelligenceExperiment No. : 5Write a Program to implement informed A* search method.Experiment No. 5Aim: Write a Program to implement informed A* search method.Objectives: From this experiment, the student will be able to Understand the working of informed search algorithmImplement A* search algorithm.Outcomes: The learner will be able to Ability to analyse the local and global impact of computing in searching techniques.Understand, identify, analyse and design the problem, implement and validate the solution for the A* search method.Ability to applying knowledge of computing in search technique areas.Software Required : C language/Java languageTheory: An informed search strategy-one that uses problem-specific knowledge-can find solutions more efficiently.A key component of these algorithms is a heuristic function h(n)h(n) = estimated cost of the cheapest path from node n to a goal node.Admissible /heuristic never over estimated i.e. h(n)≤ Actual cost. For example, Distance between two nodes(cities)=> straight line distance and for 8-puzzel problem- Admissible heuristic can be number of misplaced tiles h(n)= 8.A* Search techniqueIt is informed search technique. It uses additional information beyond problem formulation and tree. Search is based on Evaluation function f(n).Evaluation function is based on both heuristic function h(n) and g(n).f(n)=g(n) + h(n)It uses two queues for its implementation: open, close Queue. Open queue is a priority queue which is arranged in ascending order of f(n)Algorithm:Create a single member queue comprising of Root nodeIf FIRST member of queue is goal then goto step 5If first member of queue is not goal then remove it from queue and add to close queue.Consider its children if any, and add them to queue in ascending order of evaluation function f(n).If queue is not empty then goto step 2.If queue is empty then goto step 6Print ‘success’ and stopPrint ‘failure’ and stop.Performance Comparison:Completeness: yesOptimality: yesLimitation:It generate same node again and againLarge Memory is requiredObservationAlthough A*generate many nodes it never uses those nodes for which f(n)> c* where c* is optimum cost.Consider an example as belowOPEN/FRINGECLOSE[A][ ][C,B][A][D,B,E,A][A,C][F,E,B,C,A][G,E,B,C,A,D][A,C,D][A,C,D,F]SUCCESSNode A:f(B)=g(B) + h(B)=3+5=8f(C) =g(C) + h(C)=1 + 6=7Node C:f(A) = g(A) + h(A)=2+7=10f(D) = g(D) + h(D)=3+4=7f(E) = g(E) + h(E)=7+1=8Node D:f(F) = g(F) + h(F)=6+1=7f(C) = g(C) + h(C)= 5+6=11f(B) = g(B) + h(B)=4+5=9Node F:f(E) = g(E) + h(E)=7+1=8f(D) = g(D) + h(D)= 9+4=13f(G) = g(G) + h(G)=7+0=7Final path: A C DF GTotal cost= 7Procedure/ Program: Code:import java.util.PriorityQueue;import java.util.HashSet;import java.util.Set;import java.util.List;import java.parator;import java.util.ArrayList;import java.util.Collections;public class AstarSearchAlgo{ //h scores is the stright-line distance from the current city to Bucharest public static void main(String[] args){ //initialize the graph base on the Romania map Node n1 = new Node("Arad",366); Node n2 = new Node("Zerind",374); Node n3 = new Node("Oradea",380); Node n4 = new Node("Sibiu",253); Node n5 = new Node("Fagaras",178); Node n6 = new Node("Rimnicu Vilcea",193); Node n7 = new Node("Pitesti",98); Node n8 = new Node("Timisoara",329); Node n9 = new Node("Lugoj",244); Node n10 = new Node("Mehadia",241); Node n11 = new Node("Drobeta",242); Node n12 = new Node("Craiova",160); Node n13 = new Node("Bucharest",0); Node n14 = new Node("Giurgiu",77); //initialize the edges //Arad n1.adjacencies = new Edge[]{ new Edge(n2,75), new Edge(n4,140), new Edge(n8,118) }; //Zerind n2.adjacencies = new Edge[]{ new Edge(n1,75), new Edge(n3,71) }; //Oradea n3.adjacencies = new Edge[]{ new Edge(n2,71), new Edge(n4,151) }; //Sibiu n4.adjacencies = new Edge[]{ new Edge(n1,140), new Edge(n5,99), new Edge(n3,151), new Edge(n6,80), }; //Fagaras n5.adjacencies = new Edge[]{ new Edge(n4,99), //178 new Edge(n13,211) }; //Rimnicu Vilcea n6.adjacencies = new Edge[]{ new Edge(n4,80), new Edge(n7,97), new Edge(n12,146) }; //Pitesti n7.adjacencies = new Edge[]{ new Edge(n6,97), new Edge(n13,101), new Edge(n12,138) }; //Timisoara n8.adjacencies = new Edge[]{ new Edge(n1,118), new Edge(n9,111) }; //Lugoj n9.adjacencies = new Edge[]{ new Edge(n8,111), new Edge(n10,70) }; //Mehadia n10.adjacencies = new Edge[]{ new Edge(n9,70), new Edge(n11,75) }; //Drobeta n11.adjacencies = new Edge[]{ new Edge(n10,75), new Edge(n12,120) }; //Craiova n12.adjacencies = new Edge[]{ new Edge(n11,120), new Edge(n6,146), new Edge(n7,138) }; //Bucharest n13.adjacencies = new Edge[]{ new Edge(n7,101), new Edge(n14,90), new Edge(n5,211) }; //Giurgiu n14.adjacencies = new Edge[]{ new Edge(n13,90) }; AstarSearch(n1,n13); List<Node> path = printPath(n13); System.out.println("Path"+ path); } public static List<Node> printPath(Node target){ List<Node> path = new ArrayList<Node>(); for(Node node = target; node!=null; node = node.parent){ path.add(node); } Collections.reverse(path); return path; } public static void AstarSearch(Node source, Node goal){ Set<Node> explored = new HashSet<Node>(); PriorityQueue<Node> queue = new PriorityQueue<Node>(20, new Comparator<Node>(){ //override compare method public int compare(Node i, Node j){ if(i.f_scores > j.f_scores){ return 1; } else if (i.f_scores < j.f_scores){ return -1; } else{ return 0; } } } ); //cost from start source.g_scores = 0; queue.add(source); boolean found = false; while((!queue.isEmpty())&&(!found)){ //the node in having the lowest f_score value Node current = queue.poll(); explored.add(current); //goal found if(current.value.equals(goal.value)){ found = true; } //check every child of current node for(Edge e : current.adjacencies){ Node child = e.target; double cost = e.cost; double temp_g_scores = current.g_scores + cost; double temp_f_scores = temp_g_scores + child.h_scores; /*if child node has been evaluated and the newer f_score is higher, skip*/ if((explored.contains(child)) && (temp_f_scores >= child.f_scores)){ continue; } /*else if child node is not in queue or newer f_score is lower*/ else if((!queue.contains(child)) || (temp_f_scores < child.f_scores)){ child.parent = current; child.g_scores = temp_g_scores; child.f_scores = temp_f_scores; if(queue.contains(child)){ queue.remove(child); } queue.add(child); } } } }}class Node{ public final String value; public double g_scores; public final double h_scores; public double f_scores = 0; public Edge[] adjacencies; public Node parent; public Node(String val, double hVal){ value = val; h_scores = hVal; } public String toString(){ return value; }}class Edge{ public final double cost; public final Node target; public Edge(Node targetNode, double costVal){ target = targetNode; cost = costVal; }Results:Output:Conclusion: A good example of heuristic search is A* search algorithm. The performance of such heuristic search algorithm depends upon the quality of heuristic function. A* algorithm is executed and the path with minimum cost from source node to destination node is calculated. Viva Questions: Explain A* algorithm with an example.Difference between A* and IDA* searching methods.References:1. Elaine Rich and Kevin Knight "Artificial Intelligence "Third Edition2. Davis E.Goldberg, "Genetic Algorithms: Search, Optimization and Machine Learning",Addison Wesley, N.Y., 1989.3. Han Kamber, “Data Mining Concepts and Techniques”, Morgann Kaufmann PublishersArtificial IntelligenceExperiment No. : 6Case Study on NLP/Expert system based paper published in IEEE/ACM/Springer or any prominent journal.Experiment No. 61. Aim: Case Study on NLP/Expert system based paper published in IEEE/ACM/Springer or any prominent journal.2. Objectives: From this experiment, the student will be able to Analyse expert system.Analyse projects on NLP.3. Outcomes: The learner will be able to Ability to apply gained skills and knowledge to a particular application.Ability to match industrial requirements in the field of AI.Ability to recognize the need and to engage in lifelong learning.4. Software Required: 5. Theory: Title: Expert Systems in Real world BusinessAbstract of the paperNowadays firms are required to reach high levels of specialization in order to increase their competitiveness in complex markets. Expert Systems play a fundamental role in this process as the correct implementation of strategies is determined by the information transfer and dissemination within the organization. In this paper, expert system focused on increasing accuracy and quality of the knowledge for decision making is designed. Business intelligence as the basis for the development and application in business information is becoming an important information technology framework that can help organization to manage, develop and communicate their intangible assets, such as information and knowledge based economy. Particularly in this paper a technical framework is proposed to review the ES approach that will be practically feasible for organizational settings. It will also provide executives and scholars with pragmatic understanding about integrating knowledge management strategy and technologies in business processes for successful performance. The purpose of this paper is to review the use of experts systems and artificial intelligence (AI) in business and examines domain applications, the use of different knowledge representations, unique contributions for knowledge acquisition from the development of systems for business applications, and models of explanation for systems developed for business. Using an ES approach to Business Systems will be able to more effectively use their limited resources to reap the more benefits from their investments in both people and technology. Keywords: Artificial Intelligence; Expert Systems, Business.6. Procedure/ Program: Details of paper:These information systems draw upon several areas of artificial intelligence to perform their operations. Developing an expert system requires an understanding of knowledge representation. In other words, Business Intelligence can be a weapon that allows a company to identify threats and opportunities, to establish defensive strategies, and to conquer market shares. He created theories based upon observations and knowledge about the real world. Knowledge can be characterized in terms of the "strength" of the knowledge. The Expert Systems that companies are starting to use, and the AI groups.Some examples of real-world systems based on artificial intelligence are:GoogleIntelligence Distribution Agent (IDA), developed for the U.S. Navy, helps assign sailors new jobs at the end of theirTours of duty by negotiating with them via email. Systems that trade stocks and commodities without human intervention. Banking software for approving bank loans and detecting credit card fraud (developed by Fair Isaac Corp.). Search engines such as Brain Boost (or even Google.) Intelligent robots, such as ASIMO, QRIO, AIBO.Intelligent help systems capable of providing context sensitive help to software system users. These systems are able to infer the correct level of help needed to provide because they can a) make inferences about the level of skill of the user and b) utilize deep knowledge about the software application itself. Using these areas of knowledge it is possible to identify the types of mistakes that users of varying skill levels are likely to make.Ai In Business: AI has a broad discipline in today’s world that promises to simulate numerous inherent human skills such as automatic programming, case-based reasoning, neural networks, decision-making, expert systems, natural language processing, pattern recognition, speech recognition and market competition due to technological advancement etc. AI technologies bring more complex data analysis features to existing applications. I think of AI as a science that investigates knowledge and intelligence, possibly the intelligent application of knowledge. Knowledge and Intelligence are as fundamental as the universe within which they exist, it may turn out that they are more fundamental. Enterprises that utilize AI-enhanced applications are expected to become more diverse, as the needs for the ability to analyze data across multiple variables, fraud detection and customer relationship management emerge as key business drivers to gain competitive advantage. Artificial Intelligence is a branch of Science which deals with helping machines, finds solutions to complex problems in a more human-like fashion. This generally involves borrowing characteristics from human intelligence, and applying them as algorithms in a computer friendly way. A more or less flexible or efficient approach can be taken depending on the requirements established, which influences how artificial the intelligent behavior appears.7. Results:AI will impact businesses now and more so in the future.Change in knowledge management in the workplace as AI will be used to develop more sensitive and interactive, virtual learning and working environment. Here the use of telepresence will be further employed.AI will be more widely used for complex problem-solving and decision-support techniques especially in real-time business applications. More applicability of AI techniques will be spread across business areas ranging from smart finance management to increased accuracy of weather predictions.Tasks too dangerous for humans like as mining, firefighting and even bomb disarming will be carried out by special artificial intelligence aided machines.8. Conclusion: By reading this paper, we understand the architecture of expert system and its application. Expert system focusses on accuracy and quality of the knowledge for decision making. By using an ES approach to Business Systems there will be limited use of resources to reap more benefits from investments in both people and technology.9. Viva Questions: Explain architecture of Expert system.Explain the need of the natural language processing.10. References:1. Available online at: Artificial IntelligenceExperiment No. : 7Write a Program to implement Minmax search algorithm.Experiment No. 71. Aim: Write a Program to implement Minmax search algorithm.2. Objectives: From this experiment, the student will be able to Understand and analyse adversarial search. Implement Minmax algorithm.3. Outcomes: The learner will be able to Ability to understand, identify, analyse and design adversarial search.Ability to use current techniques for computing minmax algorithm.Potential to identify, formulate and solve engineering problems.4. Software Required: C language/Java language5. Theory: The minimax algorithm computes the minimax decision from the current state. It uses a simple recursive computation of the minimax values of each successor state, directly implementing the defining equations. The recursion proceecls all the way down to the leaves of the tree, and then the minimax values are backed up through the tree as the recursion unwinds.The minimax algorithm performs a complete depth-first exploration of the game tree. If the maximum depth of the tree is m, and there are b legal moves at each point, then the time complexity of the minimax algorithm is O(b m). The space complexity is O(bm) for an algorithm that generates all successors at once, or O(m) for an algorithm that generates successors one at a time. For real games, of course, the time cost is totally impractical, but this algorithm serves as the basis for the mathematical analysis of games and for more practical algorithmsfunction MINIMAX-DECISION(state)returns an actioninputs: state, current state in gamev MAX-VALUE(state)return the action in SUCCESSORS(state) vfunction MAX-VALUE(state)returns a utility valueif TERMINAL-TEST(state) then return UTILITY(state)v -infinityfor a, s in SUCCESSORS(state)dov MAX(V, MIN-VALUE(S))return vfunction MIN-VALUEif TERMINAL-TEST(state) then return UTILITY(state)V infinityfor a , s in SUCCESSORS(state)dov MIN(V, MAX-VALUE(S))return v6. Procedure/ Program: Code:#include<conio.h>#include<iostream.h>#include<stdlib.h>int i,t, k=1,head=1;int arr[10];class node{ public: int data; int value; int Turn; int E; int kk; int path[10]; int final[10]; int childs; node *parent; node *child[10]; node(int x) { data=x; value=-1; E=-1; kk=1; }};class tree { node *root;void inorder1(node *T); void print1(node *T); node *create1(); int findmax(int a[],int); int findmin(int a[],int); public: node *prev; tree() { root=NULL; root->parent=root;root->Turn=2;} void create() {root->parent=root;root->Turn=2;root=create1(); } void display(){inorder1(root);} void print(){print1(root);} }; node * tree::create1() { node *p; int x; int nchild=0;cout<<"\n Enter a data (unique number for designating the node) : "; cin >> x; p=new node(x); if(head==1) { p->parent=p; head=0; } else { p->parent=prev; } for( i=1;i<=10;i++) { p->child[i]=NULL; p->child[i]->data=-1; p->child[i]->parent=p; } if((p->parent->Turn)== 2) p->Turn=1; else p->Turn=2; for(i=1;i<=10;i++) { p->path[i]=-1; p->final[i]=-1; } cout<<"\n Enter the no of children of "<<x<<" :"; cin >> nchild; p->childs=nchild; p->value=-1; p->kk=1; if(nchild==0) { cout<<"\n Enter the value of node "<<x<<" : "; cin>>(p->value); p->E=1; p->path[1]=p->data; for(i=2;i<=10;i++) p->path[i]=-1; } for(i=1;i<=nchild;i++) { prev=p; cout<<"\nEnter child"<<i<<" of "<<x ; p->child[i]->parent=p; p->child[i]=create1(); } return p; }void tree::inorder1(node *T) { if(T!=NULL) { cout<<" "<<T->data; for(int i=1;i<=(T->childs);i++) { if(i==1) k=T->kk; if(T->value==-1) inorder1(T->child[i]); } if((T->value!=-1) && (T->childs==0)) { node *p; p=T->parent; p->final[k]=T->value; k++; T->parent->kk=k; } if(T->value==-1) { int index; int trf=T->Turn; k=T->kk; for(t=1;t<=10;t++) arr[t]=0; for(t=1;t<k;t++) { arr[t]=T->final[t]; } if(trf==2) index=findmax(arr,k); else index=findmin(arr,k); for(t=1;t<=10;t++) { if(T->child[index]->path[t] == -1) break; T->path[t]=T->child[index]->path[t]; } T->path[t]=T->data; T->E=1; T->value=T->child[index]->value; k=T->parent->kk; T->parent->final[k]=T->value; k++; T->parent->kk=k; } } }void tree::print1(node *T){ cout<<"\n\nActual Path of traversing is "; for(int i=1;i<=10;i++) { if(T->path[i]==-1) break; cout<<(T->path[i])<<" "; } cout<<"\nAssociated Cost will be "<<T->value;}int tree::findmax(int a[],int k){int temp=-1;int i,tindex;for(i=1;i<k;i++){ if(a[i]>temp) { temp=a[i]; tindex=i; }}return tindex;}int tree::findmin(int a[],int k){int temp=999;int i,tindex;for(i=1;i<k;i++){ if(a[i]<temp) { temp=a[i]; tindex=i; }}return tindex;}int main(){ tree t1; node *p; int x,op; //clrscr(); do { cout<<"\n\n1)Create\n2)Display\n3)Quit"; cout <<"\nEnter Your Choice :"; cin>>op; switch(op) { case 1: t1.create();break; case 2: t1.display(); t1.print(); break; } }while(op!=3); getch();}7. Results:Output:1)Create2)Display3)QuitEnter Your Choice :1 Enter a data (unique number for designating the node) : 1 Enter the no of children of 1 :2Enter child1 of 1 Enter a data (unique number for designating the node) : 2 Enter the no of children of 2 :2Enter child1 of 2 Enter a data (unique number for designating the node) : 4 Enter the no of children of 4 :0 Enter the value of node 4 : 3Enter child2 of 2Enter a data (unique number for designating the node) : 5Enter the no of children of 5 :0Enter the value of node 5 : 5Enter child2 of 1Enter a data (unique number for designating the node) : 3Enter the no of children of 3 :3Enter child1 of 3Enter a data (unique number for designating the node) : 6Enter the no of children of 6 :2Enter child1 of 6Enter a data (unique number for designating the node) : 9Enter the no of children of 9 :2Enter child1 of 9Enter a data (unique number for designating the node) : 13Enter the no of children of 13 :0Enter the value of node 13 : 0Enter child2 of 9Enter a data (unique number for designating the node) : 14Enter the no of children of 14 :0Enter the value of node 14 : 0Enter child2 of 6Enter a data (unique number for designating the node) : 10Enter the no of children of 10 :0Enter the value of node 10 : 5Enter child2 of 3Enter a data (unique number for designating the node) : 7Enter the no of children of 7 :2Enter child1 of 7Enter a data (unique number for designating the node) : 11Enter the no of children of 11 :0Enter the value of node 11 : 7Enter child2 of 7Enter a data (unique number for designating the node) : 12Enter the no of children of 12 :0Enter the value of node 12 : 8Enter child3 of 3Enter a data (unique number for designating the node) : 8Enter the no of children of 8 :0Enter the value of node 8 : 41)Create2)Display3)QuitEnter Your Choice :2 1 2 4 5 3 6 9 13 14 10 7 11 12 8Actual Path of traversing is 5 2 1Associated Cost will be 51)Create2)Display3)QuitEnter Your Choice :38. Conclusion: Competitive environment in which the agents goals are in conflict give rise to adversarial search problems often known as games. Minmax is one such problem. Given a game tree, the optimal strategy can be determined by examining the minmax value of each node. Minmax algorithm is analysed and implemented.9. Viva Questions: Explain Minmax algorithm with an example.How optimal calculation is done with the help of Minmax algorithm.10. References:1. Elaine Rich and Kevin Knight "Artificial Intelligence "Third Edition2. Davis E.Goldberg, "Genetic Algorithms: Search, Optimization and Machine Learning",Addison Wesley, N.Y., 1989.3. Han Kamber, “Data Mining Concepts and Techniques”, Morgann Kaufmann PublishersArtificial IntelligenceExperiment No. : 8Case Study on Belief network based paper published in IEEE/ACM/Springer or any prominent journal.Experiment No. 81. Aim: Case Study on Belief network based paper published in IEEE/ACM/Springer or any prominent journal.2. Objectives: From this experiment, the student will be able to Understand and learn the concept of Belief networkLearn the Baye’s Theorem3. Outcomes: The learner will be able to Analyse local and global impact of computing for specific problem using belief network.To formulate and solve belief network problemAnalyse current techniques and tools for solving Baye’s theorem.4. Software Required:5. Theory: Title: A differential approach to inference in Bayesian networksThe paper present a new approach to inference in Bayesian networks, which is based on representing the network using a polynomial and then retrieving answers to probabilistic queries by evaluating and differentiating the polynomial. The network polynomial itself is exponential in size, but we show how it can be computed efficiently using an arithmetic circuit that can be evaluated and differentiated in time and space linear in the circuit size. The proposed framework for inference subsumes one of the most influential methods for inference in Bayesian networks, known as the tree-clustering or joins tree method, which provides a deeper understanding of this classical method and lifts its desirable characteristics to a much more general setting. We discuss some theoretical and practical implications of this plete specification of a probability distribution over these instantiations. A Bayesian network is a compact, graphical model of a probability distribution [Pearl 1988]. It consists of two parts: a directed acyclic graph which represents direct influences among variables, and a set of conditional probability tables that quantify the strengths of these influences. Figure 1 depicts an example Bayesian network relating to a scenario of potential fire in a building. This Bayesian network has six Boolean variables, leading to sixty–four different variable instantiations. The network is interpreted as a complete specification of a probability distribution over these instantiations.Fig. 1. A Bayesian network over six Boolean variables. The network has two parts: a directed acyclic graph over variables of interest, and a conditional probability table (CPT) for each variable in the network. The CPT for a variable provides the distribution of that variable given its parents.Bayesian Networks As Multi–Linear FunctionsOur goal in this section is to show that the probability distribution induced by a Bayesian network can be represented using a multi–linear function that has very specific properties. We then show in the following sections how this function can be the basis of a comprehensive framework for inference in Bayesian networks.right2381256. Procedure/ Program: 7. Results:8. Conclusion: A belief network defines a factorization of the joint probability distribution, where the conditional probabilities form factors that are multiplied together. A belief network is also called as Bayesian network, is an acyclic directed graph where the nodes are random variables. A sample case study is considered and analysed.9. Viva Questions: Discuss inference in belief network.Explain concept of belief network.10. References:1. IntelligenceExperiment No. : 9Write a program to implement eight-puzzle problem.Experiment No. 91. Aim: Write a program to implement eight-puzzle problem.2. Objectives: From this experiment, the student will be able to Understand and analyse the problem definition of 8- puzzle problem.Implement eight puzzle problem.3. Outcomes: The learner will be able to Analyse local and global impact of computing for specific problem using 8-puzzle problem.To formulate and solve 8-puzzle problemAnalyse current techniques and tools for solving 8-puzzle problem.4. Software Required: C language/Java language5. Theory: The eight puzzle consists of 3-by-3 square frame which holds eight movable square tiles which are numbered from 1 to 8 .One square is empty, permitting tiles to be shifted. The objective of the puzzle is to find the sequence of tile movements that leads from a starting configuration to a goal configuration such as that shown in the figure a. 381625 47 A start configuration12384765 A goal configuration (Fig a) The states of the eight puzzles are the different permutations of the tiles within the frame. The operations are the permissible moves (one may consider the empty space as being movable rather than the tiles): up, down, left and right. An optimal or good solution is one that maps an initial arrangement of tiles to the goal configuration with the smallest number of moves. Algorithm:This problem solved by using A* algorithm.function A*(start,goal) closedset := the empty set // The set of nodes already evaluated. openset := set containing the initial node // The set of tentative nodes to be evaluated. came_from := the empty map // The map of navigated nodes. g_score[start] := 0 // Distance from start along optimal path. h_score[start] := heuristic_estimate_of_distance(start, goal) f_score[start] := h_score[start] // Estimated total distance from start to goal through y. while openset is not empty x := the node in openset having the lowest f_score[] value if x = goal return reconstruct_path(came_from, came_from[goal]) remove x from openset add x to closedset foreach y in neighbor_nodes(x) if y in closedset continue tentative_g_score := g_score[x] + dist_between(x,y) if y not in openset add y to openset tentative_is_better := true elseif tentative_g_score < g_score[y] tentative_is_better := true else tentative_is_better := false if tentative_is_better = true came_from[y] := x g_score[y] := tentative_g_score h_score[y] := heuristic_estimate_of_distance(y, goal) f_score[y] := g_score[y] + h_score[y] return failure function reconstruct_path(came_from, current_node) if came_from[current_node] is set p = reconstruct_path(came_from, came_from[current_node]) return (p + current_node) else return current_node6. Procedure/ Program: Code:#include<stdio.h>#include <conio.h>#include <malloc.h>#include <string.h>#include <stdlib.h>struct node{ int s[9],children,to_goal,path[50],pi; struct node *c1,*c2; struct node *c3,*c4;};typedef struct node board;board *open[50],*found;int front=-1,rear=-1;void copyarray(int s[],int d[],int n){ int i; for(i=0;i<n;i++) d[i]=s[i];}int moves[9][5] ={ { 1, 3, -1, -1, 2 }, { 0, 2, 4, -1, 3 }, { 1, 5, -1, -1, 2 }, { 0, 4, 6, -1, 3 }, { 1, 3, 5, 7, 4 }, { 2, 4, 8, -1, 3 }, { 3, 7, -1, -1, 2 }, { 4, 6, 8, -1, 3 }, { 5, 7, -1, -1, 2 }};int level=-1,imp_count; int flag=0;void enq(board *b){ if(rear==-1) { front++; open[++rear]=b; } else if(rear>=50) { printf("\nQueue is full."); getch(); exit(0); } else { open[++rear]=b; }}void deq(){ front++; if(front>rear) { front=-1; rear=-1; } else if(front==-1) printf("\nQueue is empty.");}board* getboard(){ board *b=(board*)malloc(sizeof(board)); if(b==NULL) { printf("\nMemory underflow."); getch(); exit(0); } else { b->children=0; b->to_goal=0; b->pi=0;; b->c1=NULL; b->c2=NULL; b->c3=NULL; b->c4=NULL; return b; } return NULL;}void printboard(board *b){ int i,c=0; printf("\n"); for(i=0;i<9;i++) { printf(" %d ",b->s[i]); if(c==2) { printf("\n"); c=0; } else c++; } getch();}void makemove(board *init,board *c,int mi,int ni){ int i,j,temp; for(i=0;i<9;i++) { c->s[i]=init->s[i]; } temp=c->s[mi]; c->s[mi]=c->s[moves[mi][ni]]; c->s[moves[mi][ni]]=temp;}void is_on_path(board *goal,board *c){ int i,cnt=0; for(i=0;i<9;i++) { if(goal->s[i]==c->s[i]) cnt++; } imp_count=cnt;}int is_prev(board *cur,board *prev){ int i,cnt=0; for(i=0;i<9;i++) { if(cur->s[i]==prev->s[i]) cnt++; } if(cnt==9) return 0; else return 1;}void spantree(board *init){ int i,j,mi,ni=-1; for(j=0;j<9;j++) { if(init->s[j]==0) { mi=j; break; } } level++; if(level==5) { level--; return; } else init->children=moves[mi][4]; for(i=0;i<init->children;i++) { board *temp=getboard(); for(j=0;j<9;j++) { if(init->s[j]==0) { mi=j; break; } } for(j=0;j<4;j++) { if(moves[mi][j]!=-1 && j>ni) { ni=j; break; } } switch((i+1)) { case 1: init->c1=temp; copyarray(init->path,temp->path,init->pi); temp->pi=init->pi; temp->path[(temp->pi)++]=1; makemove(init,init->c1,mi,ni); spantree(init->c1); break; case 2: init->c2=temp; copyarray(init->path,temp->path,init->pi); temp->pi=init->pi; temp->path[(temp->pi)++]=2; makemove(init,init->c2,mi,ni); spantree(init->c2); break; case 3: init->c3=temp; copyarray(init->path,temp->path,init->pi); temp->pi=init->pi; temp->path[(temp->pi)++]=3; makemove(init,init->c3,mi,ni); spantree(init->c3); break; case 4: init->c4=temp; copyarray(init->path,temp->path,init->pi); temp->pi=init->pi; temp->path[(temp->pi)++]=4; makemove(init,init->c4,mi,ni); spantree(init->c4); break; default: printf("\nNot able to allocate childs."); } } level--; return;}int solve_by_bfs(board *prev,board *init,board *goal){ int i,j,mi,ni=-1,s1; if(front>rear && flag==0) { return 0; } else if(front>rear && flag==1) { return 1; } for(i=0;i<9;i++) { if(init->s[i]==0) { mi=i; break; } } for(i=0;i<init->children;i++) { for(j=0;j<4;j++) { if(moves[mi][j]!=-1 && j>ni) { ni=j; break; } } switch((i+1)) { case 1: is_on_path(goal,init->c1); if(imp_count==9) { init->c1->to_goal=1; init->c1->path[(init->c1->pi)++]=-1; found=init->c1; return 1; } else { s1=is_prev(prev,init->c1); if(s1==1 && init->c1->children!=0) { enq(init->c1); } } break; case 2: is_on_path(goal,init->c2); if(imp_count==9) { init->c2->to_goal=1; init->c2->path[(init->c2->pi)++]=-1; found=init->c2; return 1; } else { s1=is_prev(prev,init->c2); if(s1==1 && init->c2->children!=0) { enq(init->c2); } } break; case 3: is_on_path(goal,init->c3); if(imp_count==9) { init->c3->to_goal=1; init->c3->path[(init->c3->pi)++]=-1; found=init->c3; return 1; } else { s1=is_prev(prev,init->c3); if(s1==1 && init->c3->children!=0) { enq(init->c3); } } break; case 4: is_on_path(goal,init->c4); if(imp_count==9) { init->c4->to_goal=1; init->c4->path[(init->c4->pi)++]=-1; found=init->c4; return 1; } else { s1=is_prev(prev,init->c4); if(s1==1 && init->c4->children!=0) { enq(init->c4); } } break; default: printf("\nNot able to MOVE."); } } deq(); s1=is_prev(prev,open[front]); if(s1==1) { flag=solve_by_bfs(init,open[front],goal); open[front]->to_goal=flag; if(flag==1) return 1; else return 0; } return 0;}void getpath(board *init,board *b){ int i=0; int c=b->path[i++]; board *p=init; while(c!=-1) { switch(c) { case 1: printboard(p->c1); getch(); p=p->c1; break; case 2: printboard(p->c2); getch(); p=p->c2; break; case 3: printboard(p->c3); getch(); p=p->c3; break; case 4: printboard(p->c4); getch(); p=p->c4; break; default: printf("\nPath error."); } c=b->path[i++]; }}void printpuzzle(board *b){ int i; for(i=0;i<4;i++) { switch((i+1)) { case 1: if(b->c1!=NULL && b->c1->to_goal==1) { printboard(b->c1); getch(); printpuzzle(b->c1); } break; case 2: if(b->c2!=NULL && b->c2->to_goal==1) { printboard(b->c2); getch(); printpuzzle(b->c2); } break; case 3: if(b->c3!=NULL && b->c3->to_goal==1) { printboard(b->c3); getch(); printpuzzle(b->c3); } break; case 4: if(b->c4!=NULL && b->c4->to_goal==1) { printboard(b->c4); getch(); printpuzzle(b->c4); } break; default: return; } }}int main(){ board *init,*goal; int i,j,t[9]; clrscr(); init=getboard(); printf("\nEnter initial state for 8-puzzle problem(order:left to right and top to bottom):\n"); for(i=0;i<9;i++) scanf("%d",&init->s[i]); int cnt=0; for(i=0;i<9;i++) { int lcnt=0; for(j=i+1;j<9;j++) { if(init->s[j]<init->s[i] && init->s[j]!=0) lcnt++; } cnt=cnt+lcnt; } goal=getboard(); printf("\ncount:%d\n",cnt); if((cnt%2)==0) { goal->s[0]=0; goal->s[1]=1; goal->s[2]=2; goal->s[3]=3; goal->s[4]=4; goal->s[5]=5; goal->s[6]=6; goal->s[7]=7; goal->s[8]=8; } else { goal->s[0]=1; goal->s[1]=2; goal->s[2]=3; goal->s[3]=8; goal->s[4]=0; goal->s[5]=4; goal->s[6]=7; goal->s[7]=6; goal->s[8]=5; } printf("\nYour goal state is:\n"); printboard(goal); printf("\nYour inital state is:\n"); printboard(init); printf("\nPress any key to move towards the goal state...\n"); getch(); is_on_path(goal,init); init->to_goal=1; enq(init); spantree(init); flag=solve_by_bfs(init,init,goal); if(flag==1) { getpath(init,found); getch(); printf("\nYour goal state is reached."); getch(); } else { printf("\nToo complex problem. Please try again."); getch(); } return 0;}7.Results:Output:Input:1 2 34 5 6 7 8Output:1 2 34 5 67 88. Conclusion: 8-puzzle is a simple game consisting of a 3*3 grid containing 9 squares. One of the square is empty. From the given states a program is executed to reach the goal state. It is analysed and implemented.9. Viva Questions: How to do you represent knowledge in an uncertain domain.Is 8-puzzle a multi agent or single agent problem? Justify.10. References:1. Elaine Rich and Kevin Knight "Artificial Intelligence "Third Edition2. Davis E.Goldberg, "Genetic Algorithms: Search, Optimization and Machine Learning",Addison Wesley, N.Y., 1989.3. Han Kamber, “Data Mining Concepts and Techniques”, Morgann Kaufmann PublishersExperiment No. : 10Write a Program to implement hill Climbing search algorithmExperiment No. 10Aim: Write a Program to implement hill Climbing search algorithm Objectives: From this experiment, the student will be able to Understand and implement hill climbing algorithm.Analyse time complexity of the search algorithm.Analyse how hill climbing algorithm is better than BFS.Outcomes: The learner will be able to Ability to analyse the local and global impact of computing in searching techniques.Understand, identify, analyse and design the problem, implement and validate the solution for the hill climbing search method.Ability to applying knowledge of computing in search technique areas.Software Required : SWI-PrologTheory: Hill Climbing is a local search algorithm. The search algorithms that we have seen so far are designed to explore search spaces systematically. This is achieved by keeping one or more paths in memory and by recording which alternatives have been explored at each point along the path and which have not. In many problems, however, the path to the goal is irrelevant. For example, in the 8-queens problem, what matters is the final configuration of queens, not the order in which they are added. It is used for continuous state space problem or when numbers of states are very large. Search algorithms operate using a single current state (rather than multiple paths) and generally move only to neighbors of that state.They have two key advantages:they use very little memory-usually a constant amountThey can often find reasonable solutions in large or infinite (continuous) state spaces for which systematic algorithms are unsuitable.To understand local search, we will find it very useful to consider the state space landscape shown in Figure. A landscape has both "location" (defined by the state) and "elevation" (defined by the value of the heuristic cost function or objective function). If elevation corresponds to cost, then the aim is to find the lowest valley-a global minimum. If elevation corresponds to an objective function, then the aim is to find the highest peak-a global maximum. The hill-climbing search algorithm is shown in Figure. It is simply a loop that continually moves in the direction of increasing value-that is, uphill. It terminates when it reaches a "peak" where no neighbour has a higher value. 266700238125The algorithm does not maintain a search tree, so the current node data structure need only record the state and its objective function value.Unfortunately, hill climbing often gets stuck for the following reasons: Local maxima: a local maximum is a peak that is higher than each of its neighbouring states, but lower than the global maximum. Hill-climbing algorithms 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 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.Procedure/ Program: Code: %tracedomains heuristic_val = integer top_type = top(integer) node_type = on(integer,integer) nodetype_list = node_type* top_list = top_type* file = xoutput database curr_db_list(nodetype_list,top_list,heuristic_val) child_db_list(nodetype_list,top_list,heuristic_val) best_child(nodetype_list,top_list,heuristic_val) db_on(integer,integer) db_top(integer) heuristic_value_db(integer) temp_nodelist(nodetype_list) temp_toplist(top_list)predicates block(integer) initial_state retract_all_db write_list writelist(nodetype_list) get_heuristic_value(integer) compute_heuristic create_node_top_list(nodetype_list,top_list) create_node_list create_top_list append_node(nodetype_list,nodetype_list,nodetype_list) append_top(top_list,top_list,top_list) find_children(nodetype_list,top_list,integer) find_path find_best_child move_block(integer,nodetype_list,top_list) copy_on_top_to_db(nodetype_list,top_list) copy_on_to_db(nodetype_list) copy_top_to_db(top_list) delete_curr_best_dbclauses write_list:- curr_db_list(NodeList,TopList,HVal), writelist(NodeList), nl, nl, fail. writelist([]):- nl. writelist([Head|Tail]):- write(Head), writelist(Tail). retract_all_db:- retractall(curr_db_list(_,_,_)), retractall(db_on(_,_)), retractall(db_top(_)), retractall(heuristic_value_db(_)), retractall(temp_nodelist(_)), retractall(temp_toplist(_)), retractall(child_db_list(_,_,_)), retractall(best_child(_,_,_)). block(1). block(2). block(3). block(4). block(5). block(6). block(7). block(8). block(0). initial_state:- assert(db_on(1,8)), assert(db_on(8,7)), assert(db_on(7,6)), assert(db_on(6,5)), assert(db_on(5,4)), assert(db_on(4,3)), assert(db_on(3,2)), assert(db_on(2,0)), assert(db_top(1)), create_node_top_list(NodeList,TopList), get_heuristic_value(HeuristicVal), assert(curr_db_list(NodeList,TopList,HeuristicVal)), writelist(NodeList). delete_curr_best_db:- retractall(best_child(_,_,_)), assert(best_child([],[],-9999)), retract(curr_db_list(_,_,_)), !. find_path:- curr_db_list(NodeList,TopList,HeuristicVal),% retract(curr_db_list(NodeList,TopList,HeuristicVal)), delete_curr_best_db, find_children(NodeList,TopList,HeuristicVal), find_best_child, best_child(BestNodeList,BestTopList,BestHVal), writelist(BestNodeList), BestHVal <> 8, assert(curr_db_list(BestNodeList,BestTopList,BestHVal)),% write("BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB\n"), find_path. find_path:-!. find_children(NodeList,TopList,HeuristicVal):- retractall(db_top(_)), retractall(db_on(_,_)), retractall(child_db_list(_,_,_)), copy_on_top_to_db(NodeList,TopList), db_top(X), move_block(X,NodeList,TopList), fail. find_children(NodeList,TopList,HeuristicVal):-!. find_best_child:- child_db_list(NodeList,TopList,HeuristicValue),% write("-----CHILD-----------\n"),% writelist(NodeList), best_child(A,B,BestValue), HeuristicValue >= BestValue, not(best_child(NodeList,TopList,HeuristicValue)), retract(best_child(A,B,BestValue)), assert(best_child(NodeList,TopList,HeuristicValue)), fail. find_best_child:-!. get_heuristic_value(X):- assert(heuristic_value_db(0)), compute_heuristic(), heuristic_value_db(X), retract(heuristic_value_db(X)).% write(X,"\n"). compute_heuristic:- block(Y), db_on(Y,Z), Y = Z + 1, heuristic_value_db(OLD_VAL), retract(heuristic_value_db(OLD_VAL)), NEW_VAL = OLD_VAL + 1, assert(heuristic_value_db(NEW_VAL)), fail. compute_heuristic:- block(Y), db_on(Y,Z), Y > Z + 1, heuristic_value_db(OLD_VAL), retract(heuristic_value_db(OLD_VAL)), NEW_VAL = OLD_VAL - 1, assert(heuristic_value_db(NEW_VAL)), fail. compute_heuristic:- block(Y), db_on(Y,Z), Y < Z, heuristic_value_db(OLD_VAL), retract(heuristic_value_db(OLD_VAL)), NEW_VAL = OLD_VAL - 1, assert(heuristic_value_db(NEW_VAL)), fail. compute_heuristic. move_block(X,OldNodeList,OldTopList):- block(Y), X <> Y, Y <> 0, retractall(db_on(_,_)), retractall(db_top(_)), copy_on_top_to_db(OldNodeList,OldTopList), db_top(Y), db_on(X,Z), Z <> 0, retract(db_on(X,Z)), retract(db_top(Y)), assert(db_on(X,Y)), assert(db_top(Z)), get_heuristic_value(HeuristicValue), create_node_top_list(NodeList,TopList), not(child_db_list(NodeList,TopList,HeuristicValue)), assert(child_db_list(NodeList,TopList,HeuristicValue)),% write("MOVED--------------\n"),% writelist(NodeList), fail. move_block(X,OldNodeList,OldTopList):- block(Y), X <> Y, Y <> 0, retractall(db_on(_,_)), retractall(db_top(_)), copy_on_top_to_db(OldNodeList,OldTopList), db_top(Y), db_on(X,Z), Z = 0, retract(db_on(X,Z)), retract(db_top(Y)), assert(db_on(X,Y)), get_heuristic_value(HeuristicValue), create_node_top_list(NodeList,TopList), not(child_db_list(NodeList,TopList,HeuristicValue)), assert(child_db_list(NodeList,TopList,HeuristicValue)),% write("MOVED--------------\n"),% writelist(NodeList), fail. move_block(X,OldNodeList,OldTopList):-% write("\nEntering YYYY"), block(Y), X <> Y, Y = 0, retractall(db_on(_,_)), retractall(db_top(_)), copy_on_top_to_db(OldNodeList,OldTopList), not(db_on(X,Y)), db_on(X,Z), Z <> 0, retract(db_on(X,Z)), assert(db_on(X,Y)), assert(db_top(Z)), get_heuristic_value(HeuristicValue), create_node_top_list(NodeList,TopList), not(child_db_list(NodeList,TopList,HeuristicValue)), assert(child_db_list(NodeList,TopList,HeuristicValue)),% write("MOVED--------------\n"),% writelist(NodeList), fail. move_block(X,OldNodeList,OldTopList). create_node_top_list(NodeList,TopList):- retractall(temp_nodelist(_)), retractall(temp_toplist(_)), assert(temp_nodelist([])), assert(temp_toplist([])), create_node_list, create_top_list, temp_nodelist(NodeList), temp_toplist(TopList), retractall(temp_nodelist(_)), retractall(temp_toplist(_)). create_top_list:- db_top(X), temp_toplist(TopList), retract(temp_toplist(TopList)), append_top([top(X)],TopList,TopList1), assert(temp_toplist(TopList1)), fail. create_top_list. create_node_list:- db_on(X,Y), temp_nodelist(NodeList), retract(temp_nodelist(NodeList)), append_node([on(X,Y)],NodeList,NodeList1), assert(temp_nodelist(NodeList1)), fail. create_node_list. append_node([],ListB,ListB). append_node([X|List1],List2,[X|List3]):- append_node(List1,List2,List3). append_top([],ListB,ListB). append_top([X|List1],List2,[X|List3]):- append_top(List1,List2,List3). copy_on_top_to_db(NodeList,TopList):- retractall(db_on(_,_)), retractall(db_top(_)), copy_on_to_db(NodeList), copy_top_to_db(TopList), !. copy_on_to_db([]). copy_on_to_db([on(X,Y)|Tail]):- assert(db_on(X,Y)), copy_on_to_db(Tail). copy_top_to_db([]). copy_top_to_db([top(X)|Tail]):- assert(db_top(X)), copy_top_to_db(Tail).goal clearwindow, retract_all_db, openwrite(xoutput,"hill.dat"), writedevice(xoutput), initial_state, find_path, closefile(xoutput), writedevice(screen).Results:Output: on(2,0)on(3,2)on(4,3)on(5,4)on(6,5)on(7,6)on(8,7)on(1,8)on(1,0)on(8,7)on(7,6)on(6,5)on(5,4)on(4,3)on(3,2)on(2,0)on(8,0)on(2,0)on(3,2)on(4,3)on(5,4)on(6,5)on(7,6)on(1,0)on(7,0)on(1,0)on(6,5)on(5,4)on(4,3)on(3,2)on(2,0)on(8,0)on(6,0)on(8,0)on(2,0)on(3,2)on(4,3)on(5,4)on(1,0)on(7,0)on(5,0)on(7,0)on(1,0)on(4,3)on(3,2)on(2,0)on(8,0)on(6,0)on(4,0)on(6,0)on(8,0)on(2,0)on(3,2)on(1,0)on(7,0)on(5,0)on(3,0)on(5,0)on(7,0)on(1,0)on(2,0)on(8,0)on(6,0)on(4,0)on(2,1)on(4,0)on(6,0)on(8,0)on(1,0)on(7,0)on(5,0)on(3,0)on(3,2)on(5,0)on(7,0)on(1,0)on(8,0)on(6,0)on(4,0)on(2,1)on(4,3)on(2,1)on(6,0)on(8,0)on(1,0)on(7,0)on(5,0)on(3,2)on(5,4)on(3,2)on(7,0)on(1,0)on(8,0)on(6,0)on(2,1)on(4,3)on(6,5)on(4,3)on(2,1)on(8,0)on(1,0)on(7,0)on(3,2)on(5,4)on(7,6)on(5,4)on(3,2)on(1,0)on(8,0)on(2,1)on(4,3)on(6,5)on(8,7)on(6,5)on(4,3)on(2,1)on(1,0)on(3,2)on(5,4)on(7,6)Conclusion: Informed search covers algorithms that perform purely local search in the state space, evaluating and modifying one or more current states. These algorithms are suitable for the problem in which the path cost is irrelevant and all that matters is the solution state itself. One of the informed search method that is hill climbing search algorithm is executed.Viva Questions: Why is hill climbing called greedy local search algorithm? Drawbacks hill climbing algorithm. Compare different informed search strategies in detail.References:1. Ivan Bratko "PROLOG Programming for Artificial Intelligence", Pearson Education,Third Edition.2. Elaine Rich and Kevin Knight "Artificial Intelligence "Third Edition3. Davis E.Goldberg, "Genetic Algorithms: Search, Optimization and Machine Learning",Addison Wesley, N.Y., 1989.4. Han Kamber, “Data Mining Concepts and Techniques”, Morgann Kaufmann Publishers ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download