One of the central characteristics of almost any natural, complex problem is that parts of its solution are fixed by available resources, while other parts may have a wide variability in possible solutions. For instance, in planning a cross-country trip, a traveler might have some general goals such as ``visit as many places as possible'', ``enjoy the vacation'', etc.. There may be some specific goals such as ``see the Grand Canyon''. Unfortunately, there will be some general constraints as well: ``spend less than 1000 dollars'', ``get back home in two weeks''. There probably will be some very specific constraints as well. For example, ``go to the meeting in Phoenix on Monday, 4-13, at 10 AM (so you can write-off the vacation)'' and ``visit Aunt Millie on her birthday''. Some other constraints are fairly restrictive when combined with other constraints: ``visit Cousin Fred while I am in Phoenix''.
When planning, the smart traveler will first determine the areas where he has no choices. The other decisions will then be made in relation to the fixed islands of certainty in the schedule. Upon making an initial assessment of the island constraints, other islands may appear, such as ``visit Fred while in Phoenix'' in the context of ``go to the meeting in Phoenix on 4-13...''. Islands constraints can pop up at even with the most general of constraints. For instance, if the piggy bank is empty after the Grand Canyon, there is only one place to go.
Considering that island driving is such a central component of human planning, it is surprising that it receives so little emphasis in the planning literature. This project seeks to remedy that situation with respect to planning in text generation systems. It is my hope that the methods used here will be extended to other types of planning environments as well.
In this project, island driving has two aspects. First, there are the islands created naturally as a result of the problem definition and the inter-related constraints. In the main example described above, because rule 0 in RELATION-20 was failed due to an impossible precondition, there was only one possible rule that could be applied to it. Therefore, that rule could be instantiated, and any effects it had could be propagated.
The second aspect to island driving in this project concerns the artificial creation of islands by the modified recursive descent processor. At each node in the recursive descent, one of the active rules is chosen and instantiated. This creates an artificial island. The effects of the rule can be propagated out. Again, this might cause other rules to fail, creating other islands that are also artificial, in the sense that they were created by a combination of constraints imposed by planning choices rather than by the problem itself.
Whether natural or artificial, island driving is an important part of planning in this system. Whenever a rule fails, for any reason, its corresponding node is checked to determine if it is an island. If it is, its constraints are applied, which, in turn, may cause other rule failures and begin the whole process again.