Premium
A Pattern‐Weight Formulation of Search Knowledge
Author(s) -
Levinson Robert,
Fuchs Gil
Publication year - 2001
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/0824-7935.00172
Subject(s) - computer science , macro , predicate (mathematical logic) , flexibility (engineering) , set (abstract data type) , algorithm , associative property , artificial intelligence , theoretical computer science , mathematics , statistics , programming language , pure mathematics
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.