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
computational semantic systems. HUNTER-GATHERER automatically uses its constraint
satisfaction engine to take advantage of islands. Whenever a
variable's plan, or value,
is failed for any reason, constraint satisfaction will fail any other
plans that critically
depend on effects from the failed plan, If a
variable has all of its possible plans failed except one, forming
an island, then only plans that do not critically rely on those failed
plans will remain. In addition, when the non-failed plan that forms the island is
processed, all plans that conflict with it will also be failed. Thus,
by dynamically implementing constraint satisfaction techniques,
islands are automatically identified and their effects propagated.
The second aspect to island driving in this project concerns the artificial creation of islands by the solution synthesis processor. In the solution synthesizer, valid combinations of plans are created and tested. For each combination, one of the plans, or values, is chosen and instantiated for each variable in the combination. This, in effect, creates artificial islands at each of these variables. The ``island effects'' can then be propagated out for each. Again, this might cause other plans 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.
An interesting sidepoint in this discussion is that we treat text generation and semantic analysis equivalently; that is, they are both instances of planning. The ``variables'' in analysis are words, the ``plans'' are word senses. The analyzer then tries to plan the combination of word senses that best describes the semantics of the input. In generation, the ``variables'' are semantic concepts or relations that need to be realized, the ``plans'' are textual directions for implementing those ``variables,'' and the generator plans the combination of textual directions that best implements the input semantics. With the exception of the ``usage constraints'' introduced by PICARD which enable HUNTER-GATHERER's solution synthesis mechanism in the slightly more ``fluid'' world of generation, analysis and generation are processed equivalently.