General Description

The basic planner

The GRT planner is a domain-independent heuristic planner, which adopts the pure STRIPS representation and searches forward in the space of the states. The planner has initially been inspired by the ASP/HSP planner, but it has been differentiated in several ways.

GRT solves planning problems in two phases: the pre-processing phase and the search phase. The main idea of the planner is to compute off-line, in the pre-processing phase, estimates for the distances between the domains facts and the goals. The word 'distance' refers to the number of goal regression levels needed to achieve a specific fact. This information is stored in a table, which is indexed by the facts of the domain. We call this table the Greedy Regression Table, which the acronym GRT comes from.

In order to produce better estimates, GRT introduces the notion of related facts in the goal regression process. These are facts that have been achieved either by the same or by subsequent actions, without the last action deleting the firstly achieved facts. The cost for achieving a set of un-related facts simultaneously is the sum of their individual costs, while the cost for achieving a set of related facts is the cost of the last achieved fact.

The search phase consists of a simple best-first search strategy. Based on the distances of the individual facts from the goals, and the information about their relations, GRT obtains estimates for the distances between the intermediate states and the goals, which are used to guide the search.

The original version of GRT participated at the AIPS-2000 with very promising results. Actually, GRT has not gained any prize, but most prizes in the domain-independent track of the competition were given to similar planners (FF and HSP-II).


The development of GRT started in 1999, in Aristotle University, Thessaloniki, by Ioannis Refanidis, as the main result of his PhD work, under the supervision of Ioannis Vlahavas. From 2002 and forth, reserarch in GRT continues in University of Macedonia, where Ioannis Refanidis serves as a lecturer.

GRT and XOR-Constraints

GRT supports the use of state-constraints, in the form of XOR-constraints, in order to increase its efficiency in domains where local-optinal states exist. XOR-constraints are relations between sets of ground facts, where exactly one of them can hold in each state. GRT uses these axioms in the pre-processing phase, in order to analyze a planning problem in a sequence of sub-problems that have to be solved sequentially. In general, these sub-problems are easily solved by heuristic planners, so the total time needed to solve them is substantially shorter than the time needed to solve the original problem.  

GRT with Resources

Concerning the problem of efficient resource representation, an evolution of GRT, called GRT-R, has been developed, where resources are explicitly represented in a numerical format. GRT-R assigns to the facts of a domain vectors of values, which denote the distance between each fact and the goals, together with the amount of resources needed to achieve that fact. GRT-R is embedded in the GRT planner, version 2.0.  

MO-GRT: MultiObjective GRT

Modern domain-independent heuristic planners (also GRT) evaluate their plans on the basis of their length only. However, in real-world problems there are other criteria that also play an important role, such as resource consumption, profit, safety, etc. MO-GRT is a recent version of GRT, having the ability to consider multiple criteria. It uses a weighted A* strategy and a multiobjective heuristic function, which is computed over a weighted hierarchy of user-defined criteria. Its computation is based on sets of non-dominated value-vectors assigned to the problem facts, which estimate the total cost of achieving the facts from the goals, using alternative paths. Experiments have shown that a change in the weights affects both the quality of the resulting plan and the planning time.

Note that in case where no criteria are provided, MO-GRT behaves exactly as the single-objective planner GRT.

You can get the executable files and other material of MO-GRT from the "downloads" page.


Last updated: 06/03/2003 , 12:11:37 by Ioannis Refanidis