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 dis tance from any state satisfying that predicate to any goal state. The relat ionship of PWs to more traditional forms of search knowledge is explored wi th emphasis on macros and subgoals. It is shown how PWs may be used to over come some of the difficulties associated with macro-tables and lead to shor ter solution paths without replanning. An algorithm is given for converting a macro-table to a more powerful PW set. Superiority over the Squeeze algo rithm is demonstrated. It is also shown how PWs provide a mechanism for ach ieving dynamic subgoaling through the combination of knowledge from multipl e alternative subgoal sequences. The flexibility and execution time reasoni ng provided by PWs may have significant use in reactive domains, The main c ost associated with PWs is the cost of applying them at execution time. An associative retrieval algorithm is given that expedites this matching-evalu ation process. Empirical results are provided which demonstrate asymptotica lly improving performance with problem size of the PW technique over macro- tables.