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
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.
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.
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