Optimal Searches From AND and OR Nodes

Barnett, Jeffrey A.

Optimal Searches From AND and OR Nodes

Download BibTeX Cite

Proceedings of the Eighth International Joint Conference on Artificial Intelligence. Planning and Search. Pages 786-787.

Abstract

The problem is to organize search from an AND node in a way thatminimizes expected cost. The result is derived as a corollary toea rlier work of Simon and Kadane. It is shown that, unless knowledge gained during the search changes the probability or cost estimates of remaining parts of the search, the original a priori strategy remains optimal. The effect of approximating the searc h statistics used to determine the optimal strategy is examined , and it is found that the impact on expected cost is linearly bounded by the quality of the approximation . Then the case of searching an infinite conjunct is considered. Finally, some related research top ics are discussed.

Jeffrey A. Barnett. 1983. Optimal Searches From AND and OR Nodes. In Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI-83. IJCAI, 786–787. https://ijcai.org/proceedings/1983/191

@inproceedings{ijcai1983p191,
  title     = {Optimal Searches From AND and OR Nodes},
  author    = {Barnett, Jeffrey A.},
  booktitle = {Proceedings of the Eighth International Joint Conference on
               Artificial Intelligence, {IJCAI-83}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Alan Bundy},
  pages     = {786--787},
  year      = {1983},
  note      = {Planning and Search},
  url       = {https://ijcai.org/proceedings/1983/191},
}

TY  - CPAPER
TI  - Optimal Searches From AND and OR Nodes
AU  - Barnett, Jeffrey A.
T2  - Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI-83
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1983
SP  - 786
EP  - 787
UR  - https://ijcai.org/proceedings/1983/191
ER  -