Catalogue of Artificial Intelligence Techniques
Aliases: Parallel Planning, Partially-ordered Plans
Keywords: DEVISER, NOAH, NONLIN, hierarchical planning
Author(s): Austin Tate
Non-linear planners are able to maintain the emerging plan as a partially-ordered network of actions. Unnecessary ordering (or linearisation) of the actions is avoided. Only when there are conflicts between parallel branches of the plan (such as the inability to determine a required condition at some point) is an ordering imposed. The first such system was Sacerdoti's NOAH. A complete treatment of the handling of alternatives and all legal linearisations after an interaction between Subgoals is detected was included in Tate's NONLIN. The ability to use the same technique in the presence of time constraints on particular actions was a feature of Vere's DEVISER. Most non-linear planners also use hierarchical planning techniques.
- Vere, S.A., Planning in time: windows and durations for activities and goals
IEEE Trans. on Pattern Analysis and Machine Intelligence 5 (1983) no.3, 246--267, also appears in Readings in Planning (Allen, J., Hendler,
J. and Tate, A., eds.) Morgan Kaufmann, 1990, pp. 297--318