Backwards State-space Reduction for Planning in Dynamic Knowledge Bases
  In this paper we address the problem of planning in rich domains, where
knowledge representation is a key aspect for managing the complexity and size
of the planning domain. We follow the approach of Description Logic (DL) based
Dynamic Knowledge Bases, where a state of the world is represented concisely by
a (possibly changing) ABox and a (fixed) TBox containing the axioms, and
actions that allow to change the content of the ABox. The plan goal is given in
terms of satisfaction of a DL query. In this paper we start from a traditional
forward planning algorithm and we propose a much more efficient variant by
combining backward and forward search. In particular, we propose a Backward
State-space Reduction technique that consists in two phases: first, an Abstract
Planning Graph P is created by using the Abstract Backward Planning Algorithm
(ABP), then the abstract planning graph P is instantiated into a corresponding
planning graph P by using the Forward Plan Instantiation Algorithm (FPI). The
advantage is that in the preliminary ABP phase we produce a symbolic plan that
is a pattern to direct the search of the concrete plan. This can be seen as a
kind of informed search where the preliminary backward phase is useful to
discover properties of the state-space that can be used to direct the
subsequent forward phase. We evaluate the effectiveness of our ABP+FPI
algorithm in the reduction of the explored planning domain by comparing it to a
standard forward planning algorithm and applying both of them to a concrete
business case study.
