Catalogue of Artificial Intelligence Techniques
Interactions Between Sub-Solutions
Keywords: HACKER, INTERPLAN, NONLIN, WARPLAN, critics, goal regression
Author(s): Austin Tate (adapted from Mark Stefik)
Whenever a planner makes the assumption that conjunctive goals can be solved independently (either one after the other or in parallel) there is likely to be interference between the partial solutions. Techniques have been developed to recognise and correct for these interactions between solutions to conjunctive goals. Sussman's HACKER solved problems by assuming an ordered solution was feasible. It then had critics to recognise interactions and HACKER was often able to repair the plan by re-arranging the steps in the plan. In his INTERPLAN program, Tate's approach was to abstract the original goals and to determine holding periods over which these could be assumed to be true. INTERPLAN analysed this Goal Structure with a view towards ordering the approach taken to solve the sub-goals to ease conflict situations. Waldinger developed an approach called `goal regression' in which a solution to one goal was built and then the plan was constructively modified to achieve the further plans (by moving new goals backwards through a partial plan to a position where they did not interfere). A scheme similar to that used by Waldinger was incorporated in WARPLAN, a planner written in Prolog. All the above-mentioned planners produce their plans as a linear sequence of actions. The Non-linear Planner NONLIN, also dealt with interactions between sub-goals in plans which are produced as partially ordered networks of actions.
- Tate, A., Interacting goals and their use Proceedings of IJCAI-75 (1975), 215--218.