Let us suppose that a CSUC student needs to plan her after school activities for each day of a week.
The choices are constrained by weekly objectives: there must be (at least)
20 units of study
5 units of entertainment
5 units of exercise
Let us assume:
1. Mon, Tue, Wed, and Thurs are study days. She can study 0, 2, or 4 hours, each hour being one unit.
2. Fri is entertainment day. She can watch TV (2 units), dine out (5 units), go to a party (5 units), or do nothing (0 units)
3. Saturday is exercise and entertainment day. Entertainment choices are as on Friday. For exercise, she can go for a walk (1 unit), jog (2 units), go to the gym (3 units) or do nothing (0 units)
4. Sunday is study and exercise day. Exercise choices are as on Sat. Study choices are as on Monday through Thursday.
Let us consider the following plan:
Note that for simplicity, Saturday and Sunday
are divided into Sat1, Sat2 and Sun1,Sun2
Simple back-track
Backtacking (in general) is failure handling
When the student reaches node 10, she realizes that the study constraint has not been satisfied. So, she backtracks to 9 and makes a different choice. After node 9 is exhausted, she backtracks to node 8 and moves from there, ... and so on.
You can see that she is not going to succeed until she backtracks to node 4 and makes the choice of 4 study units. But before she reaches 4, she would have to try different choices at nodes 9, 8, 7, 6, and 5; and thereby waste a lot of effort.
A different eay of backtracking makes use of the fact that satisfaction of the constraint of studying for 20 hours depends on the choices made at some of the nodes but not at others. This
is called dependency-directed backtracking.
Here, some knowledge may be stored at each node indicating whether the node is relevant to the saatisfaction of a given constraint. Then the student, after trying node 9, tries only node 4 and thus avoids any wasted effort at nodes, 5, 6, 7,and 8.
MOLGEN
One of the experiments in molecular genetics involves the embedding of a DNA molecule in some bacterium. Stefik (1981) has built an AI system called MOLGEN that plans such an experiment.
A simplified version:
Suppose MOLGEN has to plan an experiment that embeds DNA1 into BacteriumA.
DNA1 is a type of DNA molecule that can instantiated (say) be DNAi, DNAii, DNAiii and DNAiv.
Similarly, BacteriumA can be instantiated (say) by Bacteriuma, Bacteriumb, or Bacteriumc.
Thus there are 12 possible combinations; MOLGEN succeeds if it can plan for any of the 12.
Alos available are several operators: MERGE, AMPLIFY, REACT, SORT, SELECT, CLEAVE, LIGATE, SCREEN, etc. Each of the operators simulate some specific laboratory step and has some preconditions and postconditions.
The problem solving is done in the means-ends manner of GPS. The present state is compared to the goal state, a subgoal is created, an operator is chosen (based on its pre- and post- conditions) and applied to the present state to reach the next stage. The process is iterated until the goal state is reached.
Let us consider step 6 (shown in the figure) where Bacteriumb is screened using an Antibiotic AB, thereby leaving the Bacteriumb-DNAiii, which is the goal state.
The problem arises when MOLGEN realizes that the Antibiotoc AB (proposed by the SCREEN operator) will kill not only Bacteriumb, but also Bacteriumb-DNAiii (DNAiii is not resistant (say) to Antibiotic AB).
The system could now backtrack; undo step 5, undo step 4, undo 3, undo 2, then redo 2 by selecting DNAiv and proceed forward from there. It may even succeed this time (DNAiv is resistant (say) to antibiotic AB) but not before a lot of wasted effort.
A better way is to recognize that there is a constraint present - the DNA must be resistant to Antibiotic AB. It is then clear that the satisfation of the constraint is dependent on the right choice of DNA at step 2. Thus step 5, 4, and 3 need not be undone; only step 2 needs to be changed to select DNAiv instead of DNAiii.
A still better way (the actual way used in MOLGEN) is to follow the Least-commitment strategy. According to this strategy, decisions about specific objects should be postponed as long as possible. Thus MOLGEN makes an (abstract) plan without making a specific choice for DNA in step 2. After the plan has been completed, the DNAiv molecule can be instatiated.
plan-generate-test. (propose and revise)