Reducing Search and Learning Goal Preferences

Abstract

This chapter presents a framework for search heuristics in domains that have subgoals represented as terms over variables (relations). Search in such domains can be reduced when a subgoal gets specialized via instantiation of its variables, these instantiations then specialize other subgoals that share those variables. These communicated variable bindings constrain subsequent search during the expansion of these other subgoals. Search heuristic functions might be developed that choose which subgoal of a state to expand next, on the basis of two types of information: (1) the degree of each subgoal's connectivity to other subgoals and (2) the expected search required to specialize each subgoal, where this latter type of information is learned from past search experience with similar subgoals.