Reducing Planning Problems by Path Reduction

Book excerpt: Planning is among the characteristic features of intelligence and therefore it is a central research topic of Intellectics since its beginning. Although planning is a very hard task, recent planning systems have achieved an astonishing performance and are applied in various fields. One reason for the success of these systems lies, among others, in the exploitation of structural properties that are present in many but not all problems. The use of such structural properties therefore leads to a specialization on a class of problems. Their exploitation is often conducted by a preprocessing step, i.e., by the application of a special algorithm prior to the search for a plan. This work identifies and examines the class of c-invariants as such a structural property of planning problems. c-Invariants are state invariants and are present in many problems of practical interest. Building on the features of c-invariants, the dissertation presents path reduction, a preprocessing technique that can significantly simplify planning problems. Finally, the work describes an implementation of path reduction and examines its application.