On determining and completing incomplete states in STRIPS domains
Ioannis Refanidis, Ioannis P. Vlahavas, Lefteri H. Tsoukalas · 2003
GRT is an effective domain-independent heuristic for STRIPS worlds, based on greedy regression tables. The heuristic is able to provide quite accurate estimates for the distances between the intermediate states and the goals, guiding in this way the search of any state-space planner. This estimation is performed by repeatedly applying 'inverted' actions to the goals, trying to achieve the facts of the domain. The problem with this approach is that in many problem instances the goals do not constitute a complete state, so it is impossible to apply actions to them, since the preconditions of no one action are included within the goals. The solution adopted initially was to manually enriching the goals with more facts, that are not in contradiction with the existing ones. In this paper we present some approaches to automatically detect and complete incomplete (goal) states and test the impact of these algorithms to the GRT planner.