A pattern-weight formulation of search knowledge
Pattern-weight pairs (PWs) are a new form of search and planning knowledge. PWs are predicates over states coupled with a least upper bound on the distance from any state satisfying that predicate to any goal state. The relationship of PWs to more traditional forms of search knowledge is explored with emphasis on macros and subgoals. It is shown how PWs may be used to overcome some of the difficulties associated with macro-tables and lead to shorter solution paths without replanning. An algorithm is given for converting a macro-table to a more powerful PW set. Superiority over the Squeeze algorithm is demonstrated. It is also shown how PWs provide a mechanism for achieving dynamic subgoaling through the combination of knowledge from multiple alternative subgoal sequences. The flexibility and execution time reasoning provided by PWs may have significant use in reactive domains, The main cost associated with PWs is the cost of applying them at execution time. An associative retrieval algorithm is given that expedites this matching-evaluation process. Empirical results are provided which demonstrate asymptotically improving performance with problem size of the PW technique over macro-tables.
subgoals heuristic search knowledge representation macro-feature construction pattern retrieval reactive planning tile puzzles