Conspiracy Numbers and Caching for Searching And/Or Trees and Theorem-Proving
Proceedings of the Eleventh International Joint Conference on Artificial Intelligence. Search. Pages 341-347.
Abstract
This paper applies the idea of conspiracy numbers to derive two heuristic algorithms for searching and/or trees. The first algorithm is an AO* best-first algorithm but the standard guarantees do not apply usefully to it because it conforms to the economic principle of sunk costs. The second algorithm works depthfirst and guides the search done by an iterative deepening SLD-resolution theorem prover that we have implemented. To avoid repeated effort, the prover caches successes and failures. It exploits the fact that a new goal matches a cached goal if it is a substitution instance of the latter, not just if the two are identical. Experimental results indicate that conspiracy numbers and especially the new caching scheme are effective in practice.
@inproceedings{ijcai1989p54,
title = {Conspiracy Numbers and Caching for Searching And/Or Trees and Theorem-Proving},
author = {Elkan, Charles},
booktitle = {Proceedings of the Eleventh International Joint Conference on
Artificial Intelligence, {IJCAI-89}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {N. S. Sridharan},
pages = {341--347},
year = {1989},
month = {8},
note = {Search},
url = {https://ijcai.org/proceedings/1989/54},
}
TY - CPAPER TI - Conspiracy Numbers and Caching for Searching And/Or Trees and Theorem-Proving AU - Elkan, Charles T2 - Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, IJCAI-89 PB - International Joint Conferences on Artificial Intelligence PY - 1989 SP - 341 EP - 347 UR - https://ijcai.org/proceedings/1989/54 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
