TSGP

TSGP: Transparent Sub-Goal Planner Strathclyde Planning Group

TSGP is a planner inspired by the work of Chih-Wei Hsu, Benjamin W. Wah, Ruoyun Huang and Yixin Chen on the planning system SGPlan. In our efforts to understand the workings of SGPlan we have attempted a reconstruction using our own solutions to problems that we encountered. Thus, TSGP is both inspired by and based on SGPlan, but it is an independent implementation, almost certainly using very different solutions to many of the problems that have to be solved when using the goal-decomposition approach that SGPlan has adopted so successfully.

Motivation and Direction

TSGP makes use of the decompose-and-resolve strategy used in SGPlan to solve problems, partitioning a problem based around top-level goals and resolving flaws by replanning.

Development of TSGP began as part of a project to tackle planning in domains with continuous change (processes and events). We recognised that tackling this much domain complexity requires that the planner has a way to decompose the problem and SGPlan is currently the most successful planner using a decomposition strategy. Therefore, we embarked on a careful study of SGPlan and its behaviour. In order to extend it to manage processes and other features we needed our own version and this was what led to our building TSGP.

Our immediate goals are to complete TSGP so that it can handle time and metric fluents (this is nearing completion) and then to embark on the exploration of our ideas for managing continuous change in processes.

The TSGP project is funded by the EPSRC, in a grant held by Maria Fox and Derek Long, funding research assistants Andrew Coles and Amanda Smith. The project also involves collaboration with Keith Bell and Stephen McArthur of the Department of Electronic and Electrical Engineering, who are contributing case studies in the management of power supplies.

Obtaining the Source Code

An important goal in our development is to make the solutions we adopt completely transparent. This end is served by making the source code available and, indeed, we encourage others to obtain and use the code.

Current release: 0.1 (Public Release 1)
TSGP is released under the GNU General Public License, and is hosted on SourceForge. Click the following link to visit the TSGP SourceForge repository and download the source code: SourceForge Page

Public Release 1 is TSGP as described in the ICAPS '07 paper, with a few bug fixes. It supports propositional STRIPS domains, so no ADL, time or fluents for the time being, but development for supporting fluents and time is well under way.

Getting Started

To compile TSGP, run make. This should build a binary, tsgp. To execute it, type:

tsgp domain problem

If the code fails to compile, check 'Known Issues' below, and if that fails email Andrew Coles.

Further Command-Line Options for TSGP

See the 'README' file in the code archive for details of command line parameters.

The Code

A few starting pointers to the key files of TSGP:

FFSolver.h / .cpp

Modified FF subsolver. Two central classes:

- FFEvent defines an action that can appear in a solution (new action, reuse or wait)
- FF is the 'FF' subsolver itself, implementing FF's key search strategy but with steepest descent rather than EHC and the obvious modifications needed for it to be used as a decomposition subsolver

GlobalSchedule.h / .cpp

Defines several central classes used to construct the global schedule

- ScheduleNode, a node in the schedule
- CandidateSchedule, a collection of nodes, ordered in a timeline
* CandidateSchedule::CandidateSchedule - copy constructor which can also return a new schedule without the actions for a given subproblem, and return a list of the removed actions (essentially, the previous solution for the subproblem)
* CandidateSchedule::getScheduleWithActions - adds a series of FFEvents to a schedule, detects any induced cycles due to waits, and returns a new schedule
- ScheduleEvaluator - an interface for a class to attach a penalty weight to a proposed schedule

ScheduleEvaluatorStandard.h / .cpp

Maintains the schedule penalty part of the decomposition framework. The 'evaluateSchedule' method steps through a CandidateSchedule, attempts to execute it using helper methods to track what propositions have been deleted and to accrue penalties when preconditions are unsatisfied. 'updatePenalties' updates the Lagrange multipliers.

Known Issues

Some older installations of g++ do not use the std namespace by default and so there is a line in Plan.h which needs to be corrected. There is now a switch in the start of the header: NO_STD_NAMESPACE which you can set to try to handle this problem if it affects you.

Note that the installation expects to have flex++ if you build it from clean, but the distribution includes the lex.yy.cc file built from pddl+.lex and the FlexLexer.h header file to avoid this dependency being too great a problem. In general, flex++ is quite variable from distribution to distribution, so we have attempted to remove the dependency as far as we can.

At least one person has reported a problem with the macros.h file. We are looking into this, but if you are included, please let us know.