Progressive Horizon Planning

In an earlier paper [Rymon et a1 89], we showed how domain localities and regularities can be used to reduce the complexity of finding a trauma management plan that satisfies a set of diagnostic and therapeutic goals. Here, we present another planning idea - Progressive Horizon - useful for optimizing such plans in domains where planning can be regarded as an incremental process, continuously interleaved with situation - goals analysis and plan execution. In such domains, planned action cannot be delayed until all essential information is available: A plan must include actions intended to gather information as well as ones intended to change the state of the world. Interleaving planning with reasoning and execution, a progressive horizon planner constructs a plan that answers all currently known needs but has only its first few actions optimized (those within its planning horizon). As the executor cames out actions and reports back to the system, the current goals and the plan are updated based on actual performance and newly discovered goals and information. The new plan is then optimized within a newly set horizon. In this paper, we describe those features of a domain that are salient for the use of a progressive horizon planning paradigm. Since we believe that the paradigm may be useful in other domains, we abstract from the exact techniques used by our program to discuss the merits of the general approach.