Next: Introduction

Journal of Artificial Intelligence Research 15 (2001), pp. 115-161. Submitted 4/01; published 8/01.
© 2001
AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.

The GRT Planning System: Backward Heuristic Construction
in Forward State-Space Planning

Ioannis Refanidis                                                             

Ioannis Vlahavas                                                            

Aristotle University

Dept. of Informatics

54006 Thessaloniki, Greece




This paper presents Grt, a domain-independent heuristic planning system for Strips worlds. Grt solves problems in two phases. In the pre-processing phase, it estimates the distance between each fact and the goals of the problem, in a backward direction. Then, in the search phase, these estimates are used in order to further estimate the distance between each intermediate state and the goals, guiding so the search process in a forward direction and on a best-first basis. The paper presents the benefits from the adoption of opposite directions between the preprocessing and the search phases, discusses some difficulties that arise in the pre-processing phase and introduces techniques to cope with them. Moreover, it presents several methods of improving the efficiency of the heuristic, by enriching the representation and by reducing the size of the problem. Finally, a method of overcoming local optimal states, based on domain axioms, is proposed. According to it, difficult problems are decomposed into easier sub-problems that have to be solved sequentially. The performance results from various domains, including those of the recent planning competitions, show that Grt is among the fastest planners.


1.     Introduction

2.     The GRT Heuristic

2.1      The ASP Heuristic

2.2      Backward Heuristic Construction

2.3      Related Facts

2.4      The Pre-Processing Algorithm

3.     Detecting and Enhancing Incomplete States

3.1      Detecting Missing Goal Facts

3.2      Enhancing the Goals

3.3      Domain Enrichment

4.     Reducing the Size of the Problems

4.1      Eliminating Irrelevant Objects

4.2      Numerical Representation of Resources

5.     Using XOR Constraints to avoid Local Optimal States

5.1      Local Optimal States

5.2      Defining XOR-constraints

5.3      Decomposing Problems into Sub-problems using XOR-constraints

6.     The GRT Operation

7.     Related Work

8.     Performance Results

8.1      Measuring the Effectiveness of the Related Facts

8.2      Using Several Methods to Enhance the Goals

8.3      Reducing the Size of the Problem

8.4      XOR Constraints

8.5      Best-First and Hill-Climbing Strategies

8.6      Comparison to other Planners

8.6.1       Logistics

8.6.2       Blocks-world

8.6.3       Freecell

8.6.4       Elevator

8.6.5       Gripper

8.6.6       Hanoi

8.6.7       Puzzle

9.     Conclusion and Future Work






Next: Introduction

Ioannis Refanidis