人工智能课件：AIChapter06BuildingControlAlgorithms.ppt

1、 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsChapter 6 Building ControlAlgorithms forState Space Search 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithms6.0 Introduction6.1 Recursion-based Search6.2 production system6.3 The Blackboard Architecture for Problem Solving 超级计算学院 人工智能 第 6 章 BuildingControlAlgori

2、thms6.1 Recursion-based Search6.1.1 Recursive SearchA Recursive procedure consists of : 1. A recursive step: the procedure calls itself to repeat a sequence of actions. 2. A termination conditions that stop the procedure from recurring endlessly(the recursive version of an endless loop) 超级计算学院 人工智能

3、第 6 章 BuildingControlAlgorithmsfuntion depth-first-searchbegin open:=Start; closed:= ; while open do begin removed leftmost state from open, call it x; if x is a goal then return SUCCSESS else begin generate children of x; put x on closed; discard children of x if already on open or closed put remai

4、ning children on left end of open; end end return FAILend 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsfuntion depthsearch (current_state)begin current_state :=Start; closed:= ; if current_state is a goal state then return SUCCSESS add current_state to closed while current_state has unexamined child b

5、egin child :=next unexamined child; if child not member of closed; then if depthsearch(child)=SUCCESS then return SUCCESS end; return FAILend 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsNote of the recursive procedure1. The combination of recursive and iterative2. The open list is ommitted3. Backtrac

6、king is effected when all descendants of a state fail to include a goal.4. the closed contain the SUCCESS nodes 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithms6.1.2 Recursive Search Examplefuntion pattern_search (current_goal)begin if current_goal is a member of closed; then return FAIL else add current

7、_goal to closed while there remain in data base unifying facts or rules do begin case current_goal unifies with a fact return SUCCESS current_goal is a conjunction(pq ) begin 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsExample： prove a, b, c, abd, ac e, bdf, f g = g cabedfgh 超级计算学院 人工智能 第 6 章 Buildin

8、gControlAlgorithms for each conjunct to call pattern_search on conjunct; if all pattern_search succeeds for all conjuncts then return SUCCESS else return FAIL end current_goal unifies with rule conclusion (p in q p) begin applying goal unifying substitutions to premise(q); call pattern_search on pre

9、mise; if pattern_search on premise succeeds then return SUCCESS else return FAIL end end endreturn FAILend 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsThe advantage of the above procedure1. We have a mean of separating problem-solving knowledge from its control and implementation on the computer.2. S

10、ome subtleties must be addressed: the order with which the algorithm tries alternative matches and proper handing of the full set of logical operatorsThe revisions needed to do:1. Add ability to deal with negation and disjunction 2. The algorithm should return a bindings 超级计算学院 人工智能 第 6 章 BuildingCo

11、ntrolAlgorithmsfuntion pattern_search (current_goal)begin if current_goal is a member of closed; then return FAIL else add current_goal to closed while there remain in data base unifying facts or rules do begin case current_goal unifies with a fact return unifying substitutions; current_goal is nega

12、ted(p) begin 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithms call pattern_search on p; if pattern_search return FAIL then return ; else return FAIL; end;current_goal is a conjunction(pq ) begin for each conjunct to call pattern_search on conjunct; if pattern_search return FAIL then return FAIL else appl

13、y substitutions to other conjuncts then return composition of unifications; else return FAIL end; 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmscurrent_goal is a conjunction(pq ) begin repeat for each disjunct to call pattern_search on disjunct; until no more disjuncts or SUCCESS if pattern_search retu

14、rn SUCCESS then return substitutions else return FAIL; end; 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithms current_goal unifies with rule conclusion (p in q p) begin applying goal unifying substitutions to premise(q); call pattern_search on premise; if pattern_search on premise succeeds then return com

15、position of p and q substitutions else return FAIL end end endreturn FAILend 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsNote: the recursive call can go into the inside of a integer formula, and be used to its components. 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithms6.2 Production System6.2.1 Definitio

16、n and HistoryDefinition: production System A production system is defined by 1. The set of production rules. These rules often simply called productions. The production rule is a condition- action pair and defines a single chunk of problem- solving knowledge. The condition part of the rule is a patt

17、ern that determine when that rule may be applied to a problem instance. The action part defines the associated problem-solving step. 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithms 2. Working memory contains a description of the current state of the world in a reasoning process. The description is a pat

18、tern that is matched against the condition part of a production rule to select appropriate problem-solving action. When the condition element of a rule is matched by the content of working memory. the action associated with that condition may then be performed. The action of production rules are spe

19、cifically designed to alter the contents of working memory 3. The recognized-act cycle. The control structure for a production system is simple: working memory is initialized with the beginning problem description. The current state of the problem-solving is maintained as a 超级计算学院 人工智能 第 6 章 Buildin

20、gControlAlgorithms a set of pattern in working memory. These patterns are matched against the condition part of a production rule, this produces a subset he of the production rules, called the conflict set, whose conditions match the patterns in working memory. The production rules in the conflict s

21、et are said to be enabled. One of the production rule in the conflict set is then selected(conflict resolution) and the production rule is fired, To fire a rule, its action is performed, changing the contents of working memory. After the selected production rule is fired, the control cycle repeats w

22、ith modified working memory. The process terminates when the contents of working memory do not match any rule conditions. 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsWorkingMemoryPatternC1A1C2A2C3A3 PatternActio CnAnA production system. Control loops until working memory pattern no longer matches the

23、 conditions of any productions 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsA simple example of production systemSort the string composed of the letters a, b and cThe set of production rules 1. ba ab 2. ca ac 3. cb bc 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsIteration Working memory Conflict set rul

24、e fired 0 cbaca 1, 2, 3, 1 1 cabca 2 2 2 acbca 2, 3 2 3 acbac 1, 3 1 4 acabc 2 2 5 aacbc 3 3 6 aabcc HaltTrace of a simple production system 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithms6.2.2 Example of Production SystemExample: 8-Puzzle A production system is defined by The set of production rules co

25、ndition Action goal state in working memory halt blank is not on the left edge move the blank left blank is not on the top move the blank up blank is not on the right edge move the blank right blank is not on the bottom edge move the blank down 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsControl regi

26、me 1. Try production rules in order. 2. do not allow loop 3. Stop when goal is found 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithms 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithms6.2.2 Example of Production SystemExample: The knights Tour ProblemThe move of a knight in the chess board. The knights Tour Pro

27、blem find a series of legal moves in which the knight lands on each square of the chess board exactly once.Simplified version: 33 chess board. It asks whether there is a series of legal moves that will take the knight from one square to another 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithms 超级计算学院 人工智能

28、 第 6 章 BuildingControlAlgorithms312645978move(1,8) move(6,1)move(1,6) move(6,7)move(2,9) move(7,2)move(2,7) move(7,6)move(3,4) move(8,3)move(3,8) move(8,1)move(4,9) move(9,2)move(4,3) move(9,4)Predicate expression of knights move 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsThe general recursive defin

29、ition of path X path(X,X) X, Y (path(X,Y) Z path(X,Z) path(Z,Y) The set of production rules RULE# CONDODITION ACTION 1 knight on square 1 move knight to square 8 2 knight on square 1 move knight to square 6 3 knight on square 2 move knight to square 9 4 knight on square 2 move knight to square 7 5 k

30、night on square 3 move knight to square 4 6 knight on square 3 move knight to square 8 7 knight on square 4 move knight to square 9 8 knight on square 4 move knight to square 3 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsWhether a path exists from square1 to square 2?irerationworking memoryCurrent sq

31、uare goal squareconflict set fire rule01211,21821313,1423255,634277,84921515, 16522haltA production system solution to the 33 knight problem 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsHow to prevent the search from looping preserve the visited nodes in the working memory. Predicate assert(x): it is

32、always true, it puts node x into the working memory, been(x): x is visited.The modified recursive path definitionX path(X,X) X, Y path(X,Y) Z( path(X,Z) been(z) assert(been(Z) path(Z,Y) 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsGeneralize the solution to the full 33 chessboardProduction rule CONDIT

33、ION: current row 6 current column 7 ACTION: new row=current row+2 new column=current column+1 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithms6.2.3 Control of Search in Production SystemControl through choice of Data-Driven or Goal-Driven Search StrategyData-Driven: If the production ruler are formulated

34、 as logical implication, and the action adds assertions to working memory.The set of production rules1. p q goal2. r s p3. w r q4. t u q5. v s6. start v r q 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsirerationworking memoryconflict set fire rule0start661start, v,r,q56,52start, v, r, q, s26,5,2316,5,

35、2,14haltReasoning process of examplestart, v, r, q, s,pstart, v, r, q, s,p, goal6,5,2,1 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsstartrvgoalpsqdirectionof search 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsstartrtgoalpsqdirectionof searchGoal driven modewruv 超级计算学院 人工智能 第 6 章 BuildingControlAlgorit

36、hmsBidirectional search combine the data-driven search and goal-driven search. if we use appropriately, can raise efficiency and save memory space.However, we have the danger is the two searches missIn both directions, resulting in excessive search. 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmstwo sea

37、rches miss in both directions, resulting in excessive search.startGoal-drivengoaldata-driven 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsControl of Search through Rule Structure X (foo(X) goo(x) moo(x) (1)X foo(X) ( moo(x) goo(x) (2)(1) is suitable to be used in goal-driven deduction.(2) is suitable

38、to be used in data-driven deduction.In the expert system, the rules contain very important information about the usage on rules.“If the engine wont turn over and the lights dont come on, the check the battery” 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithms“If the engine turns over or the lights come on

39、 or check the battery”This rule is equivalent to the above rule, but it can not be used conveniently 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsControl of Search through Conflict Resolution1. Refraction. Refraction specifies that once a rule has fired, it may not fire again until the working memory

40、elements that match its condition has been mordified. This discourages looping.2. Recency. The recency strategy prefers rules whose conditions match the pattern most recently added to working memory. This focuses the search on a single line of reasoning.3. Specificity. This strategy assumes that it

41、is appropriate to use a more specific problem solving rules than to use a more general one. One rule is specific than another if it has more conditions, which implies that it will match fewer working memory pattern. 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithms6.2.4 Advantages of Production System for

42、 AI1.Separation of Knowledge and Control2.Natural Mapping onto State Space Search3.Modularity of Production Rules4.Pattern-directed Control5.Opportunities for Heuristic Control Search 6.Tracing and Explanation7.Language Independence8.A Plausible Model of Human Problem Solving 超级计算学院 人工智能 第 6 章 Build

43、ingControlAlgorithms6.3 The Blackboard Architecture for Problem SolvingBlackboard Many practical systems require the cooperationof multiple experts. For example, a speech understanding may first manipulate an utterance represented as a digitizedwaveform, then must find words in this utterance, then

44、form these words into sentences, and finally produce semantics of the utterances meaning. Blackboard extend production system by allowing to organize production memory into separate modules, each of which corresponding to a different subset of the production rules. Blackboard integrate these separat

45、e set of production rules and coordinate the actions of these multiple expert systems. 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsWhat is Blackboard Architecture The whole system is working for a large purpose, which can be divided into several subsystems, these subsystemshave their independent subg

46、oals. They are relevant, working for the unifying goal. The Blackboard Architecture is a large production system. Its working area is divided into several parts, coordinate the subsystems. 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsKS1KS2KSjKSn.Blackboard architecture 超级计算学院 人工智能 第 6 章 BuildingContr

47、olAlgorithmsSpeech understanding system HEARSAY-II(1980) containsthe following subsystems:KS1: The waveform of the acoustic signal KS2: The phonemes of possible sound segments of the acoustic signalKS3: The syllables that the phonemes could produce. KS4: The possible words as analyzed by one KS.KS5:

48、 The possible words as analyzed by a second KS(usually considering words from different parts of the data). KS6: A KS to try to generate possible word sequence.KS7: A KS that put word sequence into possible phrases. 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithmsThank YouThe end of Chapter 0 超级计算学院 人工智能

49、 第 6 章 BuildingControlAlgorithmsPage 192, 5.6 Exercises 13 Show that the statement p(A,B|C) =p(A|C) p(B|C) is equivalent to both p(A|B,C) =p(A|C) and p(B|A,C) =p(B|C)(=) p(A,B|C) = p(AB|C) = p(AB C) / p( C ) (1) p(A|C) p(B|C)=p(A C) / p( C )* p(B C) / p( C ) (2)From (1) and (2) p(AB C)= p(A C) * p(B

50、 C) / p( C ) p(A|B,C)=p(AB C)/ p(B C) = p(A C) * p(B C) / p( C )/ p(B C) = p(A C) / p( C ) = p(A|C) by same reason, the second part can be proved. 超级计算学院 人工智能 第 6 章 BuildingControlAlgorithms(=) p(A,B|C) = p(AB|C) = p(AB C) / p( C ) =p(A |B, C) * p(B C) / p( C ) =p(A|C)*p(B|C) (use p(A|B,C) =p(A|C) )