Catalogue of Artificial Intelligence Techniques
Aliases: Common Subgoals, Infinite Recursion
Categories: Game Theory , Problem Solving , Search
Author(s): Don Cohen
When searching a goal tree, an unbounded amount of work can be wasted solving the same problem over and over. Even worse, an unbounded amount of work can be wasted in an infinite recursion. The standard technique of caching previous results can solve both problems. The cache is indexed by goal, normally implemented as a hash table. Each goal is associated with its current solution status: either it is solved (in which case the answer is stored), it has failed, or it is still open. Whenever a goal is to be proved, the cache is searched first. If it is not there, a cache entry marked open should be created. If the cached goal has succeeded or failed just use the stored answer. In the special case of Depth-first Search, infinite recursion occurs when an open cached goal is re-encountered; in this situation, the goal should be treated as though it has failed, though it should not be recorded as such in the cache since an alternative path might still succeed. It also worthwhile canonicalising the cache entries so that similar goals can be recognised. Earley's Algorithm is an example of the use of caching. See also Case-based Reasoning.
- Cohen, D. and Mostow, J., Automatic program speedup by deciding what to cache, Proceedings of IJCAI-85 , 1985, pp.165--172.