Crawly Crypt Collection 2

home *** CD-ROM | disk | FTP | other *** search

/ Crawly Crypt Collection 2 / crawlyvol2.bin / program / compiler / clips / clip_doc / clips9.man < prev next >

Wrap

Text File | 1993-09-01 | 26.9 KB | 728 lines

Chapter 9 Backwards And Forwards Up to this point, you've been learning the basic syntax of CLIPS. In this chapter you will learn more advanced techniques of overall program design. Forward And Backward Chaining There are two fundamental control strategies that a program can follow. One type is called forward chaining and the other is called backward chaining. The control strategies should not be confused with controlling a loop. Instead, the control strategy of a program refers to the most basic design philosophy of the program. The influence of these control strategies is so important that languages are usually designed to optimize one or the other. For example, CLIPS is designed as a forward chaining language while PROLOG is backward chaining. With appropriate programming, a forward chaining language can be used for backward chaining and vice versa. So far the programs you've been writing have been forward chaining. Forward chaining reasons from known facts to the resulting conclusions. In contrast, backward chaining reasons from known conclusions to the facts which caused them. The determination of which control strategy to use depends on the application. Consider the problem of writing an expert system program to diagnose illness. If a patient has certain symptoms, the program should try to determine the nature of the illness which caused the illness. In this case, a backward chaining strategy is desired. In contrast, if a patient is known to have a certain disease, an expert system program could be written for a prognosis of the disease. That is, the program could predict the course of the disease and suggest a therapy. Another consideration in the choice of forward or backward chaining strategies is the extent of the search space. The search space is the set of possible states a program must search to find an acceptable solution. The term state means the collection of information which defines a configuration of the system. For many problems, a brute-force approach by searching all possible states is impractical because there are too many states. Instead, the production rules contain knowledge about which paths to follow in the search space that are likely to lead to the desired goal. Sometimes it is necessary for the program to backtrack to a state that was searched earlier to take an alternate path from that state because the first path chosen did not lead to an acceptable state. An example is searching through a maze and coming to a dead end. You would then go back along your path and take a different path. The knowledge encoded in rules may be heuristic in nature. The term heuristic means a method that may aid in the solution of a problem. A heuristic is not guaranteed to aid in the solution. Only an algorithm is guaranteed to determine a solution. Very often the knowledge of experts is heuristic. The person writing an expert system program, the knowledge engineer, must interview the expert and implement this knowledge in an expert system program. In a good forward chaining application, there are many possible final states and few initial states. Information is known about the initial states and the problem is to find an acceptable path from the initial state to the final state. Forward chaining reasons from given facts to the conclusions which follow from them. The production rules in CLIPS are written in a forward chaining syntax. The known facts are the conditional elements which imply the conclusions which are the actions of the rule. In a good backward chaining case, there are relatively few final states and many initial states. The goal in backward chaining is to reason backward from conclusions to the facts which caused them. A Forward Engine Let's first look at an example of an application written in the standard forward chaining method of CLIPS and then see it written in a backward chaining format. The following program simulates the action of a one-cylinder, four-stroke gasoline engine. Figure 9-1 illustrates the basic operation of the engine. The engine works in the following way. 1st Stroke-Intake Stroke: While the intake valve is open and the exhaust valve is closed, the descending piston draws a fresh air and gasoline fuel mixture into the cylinder. 2nd Stroke-Compression Stroke: The intake valve closes and the ascending piston compresses the fuel mixture. Ignition: The compressed mixture is ignited by an electrical spark from the spark plug. 3rd Stroke-Power Stroke: The pressure of the burned gases from the mixture forces the piston to descend. 4th Stroke-Exhaust Stroke: The exhaust valve is opened and the ascending piston expels the burned gases from the cylinder. As the piston ascends and descends, it rotates the crankshaft which supplies mechanical power to the wheels. The crankshaft is a rod going into the paper and symbolized by the black dot. Enter the following program which simulates the operation of the engine. ;***** forward engine program ***** ;forward chaining model of a one-cylinder, four-stroke ;gasoline engine (defrule make-initial-fact (initial-fact) => (assert (engine intake-valve open exhaust-valve closed gas good air good sparkplug nofire piston descending))) (defrule intake-stroke ?engine <- (engine intake-valve open exhaust-valve closed gas good air good sparkplug nofire piston descending) => (printout crlf "1st stroke" crlf) (retract ?engine) (assert (engine intake-valve closed exhaust-valve closed gas good air good sparkplug nofire piston ascending))) (defrule compression-stroke ?engine <- (engine intake-valve closed exhaust-valve closed gas good air good sparkplug nofire piston ascending) => (printout "2nd stroke" crlf) (retract ?engine) (assert (engine intake-valve closed exhaust-valve closed gas good air good sparkplug fire piston ascending))) (defrule ignition ?engine <- (engine intake-valve closed exhaust-valve closed gas good air good sparkplug fire piston ascending) => (printout "ignition" crlf) (retract ?engine) (assert (engine intake-valve closed exhaust-valve closed gas burned air burned sparkplug nofire piston descending))) (defrule power-stroke ?engine <- (engine intake-valve closed exhaust-valve closed gas burned air burned sparkplug nofire piston descending) => (printout "3rd stroke" crlf) (retract ?engine) (assert (engine intake-valve closed exhaust-valve open gas burned air burned sparkplug nofire piston ascending))) (defrule exhaust-stroke ?engine <- (engine intake-valve closed exhaust-valve open gas burned air burned sparkplug nofire piston ascending) => (printout "4th stroke" crlf) (retract ?engine) (assert (engine intake-valve open exhaust-valve closed gas good air good sparkplug nofire piston descending))) To run the engine, (reset) and issue a (run 21). The partial output of the program should look like the following for one cycle and the start of another. 1st stroke 2nd stroke ignition 3rd stroke 4th stroke 1st stroke 2nd stroke A Backward Example The basic algorithm of the backward chaining method can be stated recursively as follows. Solve the goal: If the goal has been solved then return else make an appropriate subgoal Solve the goal In backward chaining, the program tries to satisfy a goal. If the goal cannot be satisfied directly, the program creates one or more new goals, called subgoals. The goal is said to be split up into simpler subgoals for solution. The goal which is split is called the parent goal and the subgoals are also called child goals. The subgoals are designed so that their solution should enable the parent goal to be satisfied. A large complex problem may have many subgoals created. Of course, not all the subgoals will be active at once. As appropriate subgoals are satisfied, the parent goal is satisfied. When appropriate parent goals are satisfied, their parent is satisfied. If a subgoal cannot be solved or leads to an undesirable consequence, that information must be relayed back to the parent goal so that some other action by the parent is taken. For the example of the four-stroke engine, the initial goal is to produce an engine cycle. That is, the first goal is to have the engine complete a complete cycle of four strokes. To complete a cycle means that the exhaust-stroke must be done. To complete the exhaust-stroke means that a power-stroke must be done. To complete a power-stroke means that the ignition must be done. To complete ignition requires that a compression-stroke must be done. To complete a compression-stroke requires that an intake-stroke must be done. As you can see by this analysis, the backward chaining method is a very appropriate name. Each goal generates a subgoal in a backward manner from the desired initial goal of an engine cycle to generating an intake goal. The goals act as if they linked by a chain. In fact, the chain can be considered as the chain of logical inferences which specified the creation of subgoals to satisfy the parent goal. When each subgoal is created, the program checks to see if it has enough information to solve the subgoal. In the case of our engine, subgoals are created until there is a subgoal for an intake stroke. The initial conditions of the engine are such that it is set up for an intake stroke. That is, the make-initial-fact rule will set the intake-valve to open, the exhaust-valve to closed, the air good, the gas good, the sparkplug to nofire and the piston to descending. The intake-stroke rule will be designed to fire if there is a goal whose parent is split-compression-stroke and whose name is intake-stroke and there is a engine element with the above initial configuration. The following program shows a backward chaining version of the engine. The four rules which split goals operate first. Then the engine fires the four strokes. Finally, the continue-cycle rule initial-facts another engine cycle. As before, you'll need to issue a (run 21) command to stop after 21 cycles. Enter and run this program. You should also issue (watch facts) and (watch activations) commands to watch facts and activations. ;***** backward engine program ***** ;backward chaining model of a one-cylinder, four-stroke ;gasoline engine (defrule make-initial-fact (initial-fact) => (assert (engine intake-valve open exhaust-valve closed gas good air good sparkplug nofire piston descending)) (assert (goal parent complete-cycle name exhaust-stroke action nil))) (defrule split-exhaust-stroke (goal parent complete-cycle name exhaust-stroke action nil) => (assert (goal parent split-exhaust-stroke name power-stroke action nil))) (defrule split-power-stroke (goal parent split-exhaust-stroke name power-stroke action nil) => (assert (goal parent split-power-stroke name ignition action nil))) (defrule split-ignition (goal parent split-power-stroke name ignition action nil) => (assert (goal parent split-ignition name compression-stroke action nil))) (defrule split-compression-stroke (goal parent split-ignition name compression-stroke action nil) => (assert (goal parent split-compression-stroke name intake-stroke action nil))) (defrule intake-stroke ?goal <- (goal parent split-compression-stroke name intake-stroke action nil) ?engine <- (engine intake-valve open exhaust-valve closed gas good air good sparkplug nofire piston descending) => (printout crlf "1st stroke" crlf) (retract ?engine) (assert (engine intake-valve closed exhaust-valve closed gas good air good sparkplug nofire piston ascending)) (retract ?goal) (assert (goal parent split-compression-stroke name intake-stroke action delete))) (defrule compression-stroke ?goal <- (goal parent split-ignition name compression-stroke action nil) ?engine <- (engine intake-valve closed exhaust-valve closed gas good air good sparkplug nofire piston ascending) => (printout "2nd stroke" crlf) (retract ?engine) (assert (engine intake-valve closed exhaust-valve closed gas good air good sparkplug fire piston ascending)) (retract ?goal) (assert (goal parent split-ignition name compression-stroke action delete))) (defrule ignition ?goal <- (goal parent split-power-stroke name ignition action nil) ?engine <- (engine intake-valve closed exhaust-valve closed gas good air good sparkplug fire piston ascending) => (printout "ignition" crlf) (retract ?engine) (assert (engine intake-valve closed exhaust-valve closed gas burned air burned sparkplug nofire piston descending)) (retract ?goal) (assert (goal parent split-power-stroke name ignition action delete))) (defrule power-stroke ?goal <- (goal parent split-exhaust-stroke name power-stroke action nil) ?engine <- (engine intake-valve closed exhaust-valve closed gas burned air burned sparkplug nofire piston descending) => (printout "3rd stroke" crlf) (retract ?engine) (assert (engine intake-valve closed exhaust-valve open gas burned air burned sparkplug nofire piston ascending)) (retract ?goal) (assert (goal parent split-exhaust-stroke name power-stroke action delete))) (defrule exhaust-stroke ?goal <- (goal parent complete-cycle name exhaust-stroke action nil) ?engine <- (engine intake-valve closed exhaust-valve open gas burned air burned sparkplug nofire piston ascending) => (printout "4th stroke" crlf) (retract ?engine) (assert (engine intake-valve open exhaust-valve closed gas good air good sparkplug nofire piston descending)) (retract ?goal) (assert (goal parent complete-cycle name exhaust-stroke action delete))) (defrule continue-cycle (engine $?) (not (goal $?)) => (printout crlf "***** Engine cycle complete *****") (assert (goal parent complete-cycle name exhaust-stroke action nil))) (defrule remove-satisfied-goal ?goal <- (goal $? action delete) => (retract ?goal)) Strictly speaking, not all of the patterns need be written so explicitly for the (engine) in all the strokes. They are written out to just help you understand what's happening in the engine. For example, in the exhaust-stroke, the conditional element for ?engine could be written more correctly with wildcards as ?engine <- (engine intake-valve closed exhaust-valve open gas ? air ? sparkplug ? piston ascending) because the exhaust-stroke does not depend on the state of the gas, air, or sparkplug. In fact, the conditional element could even be written more briefly as ?engine <- (engine intake-valve closed exhaust-valve open $? piston ascending) Specifying the engine patterns more explicitly does help reduce the work that CLIPS does in pattern matching. When wildcards are used, CLIPS does a lot more work because it must try all possible matches. Even with wildcards, the "?" is less work for CLIPS than "$?" and so it's better to use "?". Give a (run 21) command and observe the speed at which the program executes. You'll see the same kind of output as in the forward chaining version. However, notice that the backward chaining version runs slower. Also, there is less output for a given number of run cycles because CLIPS is doing more work compared to the forward chaining version. These factors slow down the execution speed of the backward version. A Good Explanation In this particular example of the four-stroke engine, the backward chaining is not the best choice of a design strategy. Since the strokes of the engine follow each other in a sequential manner, the simulation problem is inherently forward chaining and should best be done by a forward chaining program. However, the backward chaining method is useful in providing an explanation facility. The term explanation facility means that a program can explain its reasoning as it fires rules. That is, the program can explain why it is trying to satisfy certain goals. An explanation facility is a very important feature in both program development and also in real runs by users. As the number of rules and facts grow, it becomes harder for a programmer to just look at the code and understand how a program works. In contrast to programs written in sequential languages like Pascal, rule-based programs execute in a parallel manner since all the rules have simultaneous access to the working memory. The solution to this problem is to use the program to debug itself. By designing with parent and subgoals in mind, the program can tell its reasons to perform certain actions. Let's add an explanation facility to the Backward Engine Program so that you can see how it works. Modify the make-initial-fact rule as follows so that it will ask the user if an explanation is desired. (defrule make-initial-fact (initial-fact) => (assert (engine intake-valve open exhaust-valve closed gas good air good sparkplug nofire piston descending)) (printout "Explain goals (yes or no) ?" crlf) ;* add this * (assert (explain =(read))) ;* add this * (assert (goal parent complete-cycle name exhaust-stroke action nil))) Now add the following rule to explain the creation of subgoals. Notice the salience fact so that this rule will fire before a competing split type rule in the agenda. After you run the program with this salience, try running it with no salience and note the difference in output. (defrule explain-subgoal (declare (salience 10)) (explain yes) (goal parent ?parent name ?name action nil) => (printout "Must create subgoal :" ?name crlf "in order to satisfy parent :" ?parent crlf)) Also, add this rule to explain the satisfaction of subgoals as the stroke rules fire. (defrule explain-remove-satisfied-goal (explain yes) ?goal <- (goal parent ?parent name ?name action delete) => (retract ?goal) (printout "Subgoal: " ?name " was satisfied" crlf "Now satisfying parent : " ?parent crlf)) Finally, modify the remove-satisfied-goal rule by adding the (explain no) condition element as follows. (defrule remove-satisfied-goal (explain no) ?goal <- (goal $? action delete) => (retract ?goal)) Now do a (reset) and (run 22). Answer "yes" to the explain question as shown and you'll see the following output of one complete engine cycle and start of another. Explain goals (yes or no) ? yes Must create subgoal :exhaust-stroke in order to satisfy parent :complete-cycle Must create subgoal :power-stroke in order to satisfy parent :split-exhaust-stroke Must create subgoal :ignition in order to satisfy parent :split-power-stroke Must create subgoal :compression-stroke in order to satisfy parent :split-ignition Must create subgoal :intake-stroke in order to satisfy parent :split-compression-stroke 1st stroke Subgoal: intake-stroke was satisfied Now satisfying parent : split-compression-stroke 2nd stroke Subgoal: compression-stroke was satisfied Now satisfying parent : split-ignition ignition Subgoal: ignition was satisfied Now satisfying parent : split-power-stroke 3rd stroke Subgoal: power-stroke was satisfied Now satisfying parent : split-exhaust-stroke 4th stroke Subgoal: exhaust-stroke was satisfied Now satisfying parent : complete-cycle ***** Engine cycle complete ***** Must create subgoal :exhaust-stroke in order to satisfy parent :complete-cycle What's The Trouble In addition to providing an explanation of goals, a program can also be used for diagnostic tasks by adding rules that look for problems. For example, suppose the compression-stroke rule is changed to give a bad sparkplug action. In a system which had inputs from engine sensors, the bad sparkplug information could come directly from a sensor and be accepted into the rule. You can simulate the engine sensor data by changing the sparkplug action in the rule as follows to give a bad sparkplug. (defrule compression-stroke ?goal<-(goal parent split-ignition name compression-stroke action nil) ?engine<-(engine intake-valve closed exhaust-valve closed gas good air good sparkplug nofire piston ascending) => (printout "2nd stroke" crlf) (retract ?engine) (assert (engine intake-valve closed exhaust-valve closed gas good air good sparkplug bad ; changed from fire to bad piston ascending)) (retract ?goal) (assert (goal parent split-ignition name compression-stroke action delete))) Now when the compression-stroke rule fires, it produces a working memory element with a bad sparkplug. To detect a bad sparkplug, let's add a diagnostic rule to look for a bad sparkplug. (defrule bad-sparkplug (goal parent ? name ignition action ?) ?engine <- (engine intake-valve closed exhaust-valve closed gas good air good sparkplug bad piston ascending) => (printout "????? No ignition ?????" crlf "Type fire for ignition" crlf) (retract ?engine) (assert (engine intake-valve closed exhaust-valve closed gas good air good sparkplug =(read) piston ascending))) If the sparkplug is bad, the ignition rule won't fire. But that doesn't tell us why the ignition didn't fire. The rule above, bad-sparkplug, will look for a bad sparkplug and tell us the reason. Additional rules could be added to diagnose other conditions such as bad gas or bad air. As more diagnostic rules are added, the program acts more and more like an expert. In fact, expert system programs are usually designed to grow in an incremental fashion like this. In a conventional sequential program, we usually have a good idea of the algorithm to be programmed. However, in an expert system, we may not have a good algorithm because our knowledge is incomplete or heuristic. The goal in expert system programming is basically rapid prototyping. That is, we want to produce a prototype program quickly. This consideration is very important if the source of knowledge is a human expert. A knowledge engineer may spend a lot of time interviewing the expert and trying to extract the knowledge needed for the program. The expert is the best judge of the performance of the program and it is important to provide rapid feedback to the expert so that the system can be improved. .PA Problem Write a program to play tic-tac-toe for these criteria. (a) The program should never lose. It will either win or draw. (a) Display the board on the screen with unfilled squares numbered in the following pattern, and ask the user for the number of the square that the user wishes to move to. The user always goes first with an X. 1 | 2 | 3 ---------------- 4 | 5 | 6 ---------------- 7 | 8 | 9 (b) After each move, the board should be redrawn and updated. (c) The program should print out messages for a draw or win. (d) If the user inputs "why" after the computer moves, the computer should explain why it moved to that square in terms of its goals and which squares it plans to win on. Print out three games showing computer wins and three draws. In one game of each type, ask a "why" question after moves. Hint: The board can be considered to have values associated with each square that add up to a magic square of 15. 8 | 3 | 4 ---------------- 1 | 5 | 9 ---------------- 6 | 7 | 2 The goal is to move pieces to obtain a sum of 15 so that you can win while preventing your opponent from getting 15. Optional: (1) The program should give the user a initial-facting choice of X or O and choice of moving first. (2) An error messageis printed if the user specifies a number out of the range 1-9 or already taken. (3) The program should be able to predict a draw.