STAN

STAN: An SPG Planning system

STAN is a domain-independent planner developed within the Strathclyde Planning Group. It has been developed through a succession of versions, currently at version 4. The original version of STAN, based on Graphplan, competed in the first international planning competition at AIPS'98 and demonstrated interesting performance. STAN extended basic Graphplan in several ways, including exploiting a powerful representational structure for the core plan-graph and using a wave-front mechanism to reduce search and graph construction costs once the plan-graph structure reaches a stable state. STAN has also always exploited a parallel domain analysis system, TIM, which can be used as a stand-alone component. The extent to which STAN has used the information TIM can supply has been extended significantly as it has been developed through subsequent versions.

Subsequent versions have added many new features, including:

• Symmetry exploitation. Symmetric objects in the problem domain are recognised and search is eliminated in cases in which symmetric choices would be considered unnecessarily.
• EBL/DDB, implemented using the techniques described by Kambhampati in his IJCAI'99 paper.
• Direct exploitation of mutex relations inferred by TIM. Graphplan generates mutex relations in an extensional form, exhaustively exploring the relationship between pair s of actions and facts in the plangraph structure it builds. TIM finds many of these relations in an intensional form, more efficiently than the exploration used in Graphplan. In addition, TIM can find mutexes that Graphplan's approach does not find and this can make a dramatic difference to planning performance.
• Exploitation of mobile and portable generic type analysis. Initial exploitation of TIM's discovery of these generic types allowed restricted instantiation of actio ns and certain search-reducing heuristics to be exploited. More recently, in a modified STAN architecture, this analysis allows a heuristic-search forward-planner to abstract path -planning out of planning problems altogether and perform the path-planning using a separate specialised module.
• Hybrid architecture. STAN has been extended to use several analyses of the domain in order to select an appropriate planning strategy. This work is still very preliminary and currently is restricted to heuristic-search forward planning and the origina l Graphplan-based planning strategy. We expect to extend this development.

To attempt to reduce confusion about what versions supply what, here is a short version history:

• Version 1: The original AIPS'98 version of STAN. Graphplan-based with initial exploitation of types from TIM. Includes wavefront and compact encoding of the graph.
• Version 2: The version built after the competition to clean up bugs and prepare STAN for public release.
• Version 3: This adds Kambhampati's EBL/DDB and symmetry. There are also bug-fixes and several implementation improvements for greater efficiency.
• Version 4: This is the AIPS'00 version and it includes a simple forward planning engine in addition to the Graphplan engine. The choice between the systems is automatic. It also uses TIM to carry out action filtering and is able to abstract certain kinds of sub-problems (path-planning and limited resouce-handling) automatically. This version is now available, but it should be noted that the release version is essentially identical to the AIPS 2000 competition version and is not extensively tested. We know that there are robustness issues and various bugs.