人工智能课件：AIChapter08StrongMethodProblemSolving.ppt

1、 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingChapter 8 Strong MethodProblem Solving 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingThe first principle of knowledge engineering is that the problem solving power exhibited by an intelligent agents performance is primarily the consequence of its knowledge

2、base, and only secondarily a consequence of inference method employed. Expert system, must be knowledge rich even is they are methods poor. 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingThis is an important result and one that only recently become well understood in AI. For a long time AI has focus it

3、s attentions almost exclusively on the development of clever inference methods, almost any inference method will do, The power resides in the knowledge. Edward Feigenbaum, Stanford universityKnowledge is Power Francis Bagon 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving8.0 Introduction8.1 Overview of

4、Expert System Technology8.2 Rule-Based Expert System8.3 Model-based Case-based and Hybrid System8.4 Planning 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving8.0 Introduction Expert system: a computer system, which has a knowledge base for a given special domain and inference ability. While given a speci

5、fic problem to the system, it can provide “expert quality” answer in that application area. 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingThe abilities of the Expert System: 1. Support inspection of their reasoning process, both in presenting intermediate steps and in answering question process. 2. Al

6、low easy modification in adding and deleting skills from the knowledge base. 3. Reason heuristically, using(often imperfect) knowledge to get useful solution. 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingThe general problems solved by Expert System: 1. Interpretation forming high level conclusions fr

7、om collections of raw datas. 2. Prediction projecting probable consequence of given situation. 3. Diagnosis-determining the cause of malfunction in complex situation based on observable symptom. 4. Design-finding a configuration of system components that meet performance goals while satisfying a set

8、 of constraints 5. Planning-devising a sequence of actions that will achieve a set of goals given certain starting condition and run-time constraints. 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving 6. Monitoring comparing a systems observed behavior to its expected behavior. 7. Instruction assisting i

9、n the education process in technical domain. 8. Control-governing the behavior of a complex environment. 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving8.1 Overview of Expert System Technology8.1.1 The Design of Rule-Based Expert System 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingUserUser interfacemay

10、employQuestion-and-AnswerMenu-dravenNatruralLanguage, orGraphics interfacesystemKnowledge-based editorInference engineExplanation subsystemGenneralKnowledge baseCase-specificdataThe architecture of typical expert system 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingThe reasons that we use the separati

11、on mode in the typical expert system: 1. to represent knowledge in a more natural fashion. The rules in knowledge base is closer to the way in which human describe their problem solving skills. 2. The knowledge base is separated from the lower level computer codes, the expert system builders can foc

12、us on capturing and organizing problem solving knowledge. 3. The architecture allows to change the one part of knowledge base without creating side effects in others. 4. The architecture allows to build some controls and interface, called expert system shell, to be used in a new domain when the know

13、ledge base are filled with new rules . 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving8.1.2 Selecting a Problem and Knowledge Engineering Process Expert systems involve a considerable investment of money and human effort. In order to avoid failures, a set of guidelines to determine whether a problem is

14、 appropriate forExpert system solution: 1. The need for solution justifies the cost and effort of building an expert system. 2. Human expertise is not available in all situations where it is needed. 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving 3. The problem may be solved using symbolic reasoning. 4

15、. The problem domain is well structured and does not require common sense using reasoning. 5. The problem may not be solved using traditional computing methods. 6. Cooperative and articulate experts exist. 7. The problem is of proper size and scope. 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingBeginD

16、efine problem and goalDesign and construct prototypeTest/use systemAnalyze and correct shortcomingsAre designAssumptions still correctReady forFinal evaluationFinal evaluationyesnoyesfailednopassed 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingThe steps of building a expert system 1. research the avai

17、lability of the project. 2. acquire the knowledge from the experts of domain. 3. build knowledge database 4. select the inference engine 5. build prototype. 6. test/use system 7. evaluate system 8. improve system 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving8.1.3 Conceptual Model and Their Role in Kn

18、owledge Acquisition The humans knowledge is often vague, imprecise, and only partially verbalized. The knowledge engineer must translate this informal expertise into a formal language suited to computation system. There are some difficulties for this translation: 1. Human skill is often inaccessible

19、 to the conscious mind. 2. Human expertise often takes the form of knowing how to cope in a situation rather than knowing what a rational characterization of the situation might be. 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving 3. The knowledge acquisition is a process of recognition of “real world”.

20、 The recognition is different by individuals and communitys model of the world. Such models are such influenced by convention, social process. 4. Expertise changes. 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingWhat should the knowledge engineers to do during the development of a expert system besides

21、 the ordinary developing steps ? 1. Save recordings of interviews with domain experts. 2. refine the expertise in the more precise knowledge representation, such as predicate representation, networks 3. communicate with the domain experts frequently, in order to use the more appropriate mode. 4. The

22、 eventual users needs should also be addressed. 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving8.2 Rule-Based Expert System8.2.1 The production System and Goal-Driven Problem Solving 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingAn example of goal-driven problem by asking the user for information. Rule 1

23、: if the engine is getting gas, and the engine will turn over, then the problem is spark plugs. Rule 2: if the engine does not turn over, and the light do not come on, then the problem is battery or cables. 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving Rule 3: if the engine does not turn over, and th

24、e light do come on, then the problem is the starter motor. Rule 4: if there is gas in the fuel tank, and there is gas in the carburetor, then the problem is getting gas. 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingThe problem is XRule1Rule2Rule3Rule4Working memoryProduction RuleThe production system

25、 at start 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingRule1Rule2Rule3Rule4Working memoryProduction RuleThe production system after Rule1 has firedthe problem is spark plugsthe engine will turn overthe engine is getting gas 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingRule1Rule2Rule3Rule4Working memor

26、yProduction RuleThe production system after Rule4 has firedthe problem is spark plugsthe engine will turn overthe engine is getting gasGas in fueltankGas in carburetor 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingThe problem is XRule1the problem is spark plugsRule2the problem is battery or cableRule1

27、the problem is start motorthe engine is getting gasthe engine will turn overthe engine does not turn overthe light do not come onthe engine does not turn overthe light do come onRule4the engine is getting gasgas in fuel tankgas in carburetor 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving8.2.2 Explanat

28、ion and Transparency in Goal-Driven Reasoning Two kinds of problems are usually presented by users, they are “why” problem and “how” problem “why” problem: why did you ask for that information? “how” problem: how did you get that result? The dialogue between the computer and the user: C: gas in fuel

29、 tank? U: yes C: gas in carburetor? U yes C: engine will turn over? U: why 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingThe system responds: It has been established that: 1. the engine is getting gas, therefore if 2. the engine will turn over, then the problem is spark plugsSuppose the user asks: how

30、 the engine is getting gas 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingThe system responds: This follows from rule4: gas in fuel tank, and gas in carburetor then engine is getting gas gas in fuel tank was given by the user gas in carburetor was given by the user 超级计算学院 人工智能 第 8 章 StrongMethodProblem

31、Solving8.2.3 Using the production System for Data-Driven Reasoning In dada-driven reasoning, the Breadth-first search is more common. The algorithm for this is simple: compare the contents of working memory with the condition of each rule in the rule base according to the order of the rules in the r

32、ule dabs. If the data in working memory supports the a rules firing the result is placed in working memory and then control moves on to the next rule. For example, the automobile diagnosis If a piece of information that makes up(part of) the premise of a rule is not the conclusion of some other rule

33、, then that fact will be deemed “askable” 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingRule1Rule2Rule3Rule4Working memoryProduction RuleThe production system at start for data-driving reasoning 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingRule1Rule2Rule3Rule4Working memoryProduction RuleThe production

34、 system after evaluating the first premise of Rule 2 The engineTurning over 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingRule1Rule2Rule3Rule4Working memoryProduction RuleThe production system after considering Rule 4, beginning its second pass through the rules. The engineturning overThere is gas in

35、carburetorThere is gas in the fuel tankThe engineIs getting gas 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingThis process is called opportunistic search. Whenever a rule fires to conclude new information, control moves to consider those rules which have that new information as a premise. 超级计算学院 人工智能

36、第 8 章 StrongMethodProblemSolving8.2.4 Heuristics and Control in Expert System In Expert system, an important method for the programmer to control search is through the structuring and ordering of the rules in the knowledge base. for example, rule p, q, rs although the rule is similar to a logic form

37、ula, the rule contains a lot of control information. The procedural method of rule interpretation is an essential component of practical knowledge use and often reflects the human experts solution stretegy. for example, the order of the premises in Rule1 in the automotive example. 超级计算学院 人工智能 第 8 章

38、StrongMethodProblemSolvingThe planning of rule order, the organization of a rules premises, and the cost of the different test are all fundamentally heuristic in nature.Data-driven for control reasoning. We can divide the solution process into 4 stages: 1) organize situation 2) collect the data 3) d

39、o the analysis 4) report the conclusion create descriptor for each stage put “organize situation” in working memory, it fires data cllection. And then into analysis and give conclusion 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving8.3 Model-Based Case-Based and Hybrid System8.3.1 Introduction to Model

40、-Based Reasoning Rule-based system and Model-based system Rule-based system : MYCIN, Dendral, Prospect advantages: Use human experts knowledge High efficiency Give explanation 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingDisadvantage: 1. shortage of structural knowledge about system 2. strongly depen

41、dent on the human experts sometimes can not get the conclusion of the problem.Model-based system: the system is composed of a number of components, each of them has its function, they are connected to implement a overall goal. We describe these components, functions and connections(model), if the ou

42、tput of the system is different from the expecting output. Through nalysis of the model, we can find out the fault components. 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingQualitative model-based reasoning includes:1. A description of each component in the device, These descriptions can simulate the

43、behavior of the component.2. A description of the devices internal structure. This is typically a representation of its components and their interconnections, along with the ability to simulate component interaction. The extent of knowledge of internal structure required depends on the level of abst

44、raction applied and diagnosis desired. 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving3. Diagnosis of a particular problem required observations of the devices actual performance, typically measurements of its input and output. I/O measurements are easiest to obtain, but any measure could be used. 超级计算

45、学院 人工智能 第 8 章 StrongMethodProblemSolvingA+BCC-BABC-A 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingIf we know the value at A and B, then the value C is A+BIf we know the value at C and A, then the value B is C-AIf we know the value at C and B, then the value A is C-B 超级计算学院 人工智能 第 8 章 StrongMethodProb

46、lemSolvingMULT-1MULT-2MULT-3ADD-1ADD-2B=3(F=12)C=2D=2E=3A=3(G=12)G=12G=10 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving8.3.2 Model-Based Reasoning: a NASA Example (Willian and Nayak) NASA: National Aeronautics and Space Administration Project: fleet of Intelligent space probes goal of the project: au

47、tonomously explore solar system. 1997 begun 1998, Deep space 1 Livingstone is a kernel software in flight control software. the function: can response to failure, and then plan around these failure during its remaining flight. one-of-a-kind modules will have to put together quickly to automatically

48、generate software in acceptable cost. 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingDifficulty: harsh condition of space. the set of potential failure scenario and possible response will be too much to use software that supports preflight enumeration of all contingencies, the space craft wil have to r

49、eactively think through all the consequences of its reconfiguration optionsTheoretical basis: model based reasoning representation language propositional calculus, a shift from the first-order predicate calculus.Process: Keeping track of developing plan 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving c

50、onfirm hardware modes reconfiguring hardware detecting anomalies diagnosis fault recoveryregulator 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolving 超级计算学院 人工智能 第 8 章 StrongMethodProblemSolvingMEMRSystemPlannerHigh-levelgoalConfigurationManagerConfigurationSensedvalueConfigurationgoalControlactionsA Mode