Content area
Full text
Articles
* Planning domains often feature subproblems such as route planning and resource handling. Using static domain analysis techniques, we have been able to identify certain commonly occurring subproblems within planning domains, making it possible to abstract these subproblems from the overall goals of the planner and deploy specialized technology to handle them in a way integrated with the broader planning activities. Using two such subsolvers our hybrid planner, sTAN4, participated successfully in the Fifth International Conference on Artificial Intelligence Planning and Scheduling (AIPS'00) planning competition.
The philosophy underlying our work on domain analysis is that uninformed, knowledge-sparse planning is impractical for real application. Although such strategies can be impressive when applied to toy domains, they cannot address highly structured problem domains effectively. However, when knowledge-sparse approaches are supplemented by domain knowledge, they can perform impressively (Bacchus and Kabanza 2000) at the cost of an increased representation burden on the domain designer. We have been exploring the use of automatic domain analyses to identify structure in a planning domain that a planner can exploit to combat search.
In this article, we introduce a way of decomposing planning problems to identify instances of common subproblems. In many cases, highperformance approximation strategies exist for solving such problems, and it is inappropriate to address them using brute-force search. We have been experimenting with using the automatic domain analysis techniques of TIM (Fox and Long 2001a, 2001b, 1998; Long and Fox 2000a, 2000b) to recognize and isolate subproblems and integrate their solution, by means of specialized algorithms, with the search behavior of a knowledge-sparse planner. Full descriptions of the processes involved can be found in Fox and Long (2001a, 2001b).
A preliminary hybrid architecture was successfully implemented in version 4 of the sTarr system (sTAN4) and has proved very promising. sT,kN4 competed in the Fifth International Conference on Artificial Intelligence Planning and Scheduling (AIPS'00) planning competition where it excelled in problems involving routeplanning subproblems and certain simple resource-allocation subproblems involving a restricted form of discrete, reusable resource. This article describes the key features of the competition version of STAN4.
The Architecture of STAN4
The way in which TiM recognizes the presence of combinatorial subproblems in a planning domain builds on its identification of generic types.
Generic types...