Additive AND/OR Graphs
Proceedings of the Third International Joint Conference on Artificial Intelligence. Theory of Heuristic Search. Pages 1-10.
Abstract
Additive AND/OR graphs are defined as AND/ /OR graphs without circuits, which can be considered as folded AND/OR trees; i.e. the cost of a common subproblem is added to the cost as many times as the subproblem occurs, but it is computed only once. Additive AND/OR graphs are naturally obtained by reinterpreting the dynamic programming method in the light of the problem-reduction approach. An example of this reduction is given. A top-down and a bottom-up method are proposed for searching additive AND/OR graphs. These methods are, respectively, extensions of the "arrow" method proposed by Nilsson for searching AND/OR trees and Dijkstra's algorithm for finding the shortest path. A proof is given that the two methods find an optimal solution whenever a solution exists.
@inproceedings{ijcai1973p1,
title = {Additive AND/OR Graphs},
author = {Martelli, Alberto and Montanari, Ugo},
booktitle = {Proceedings of the Third International Joint Conference on
Artificial Intelligence, {IJCAI-73}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Nils J. Nilsson},
pages = {1--10},
year = {1973},
month = {8},
note = {Theory of Heuristic Search},
url = {https://ijcai.org/proceedings/1973/1},
}
TY - CPAPER TI - Additive AND/OR Graphs AU - Martelli, Alberto AU - Montanari, Ugo T2 - Proceedings of the Third International Joint Conference on Artificial Intelligence, IJCAI-73 PB - International Joint Conferences on Artificial Intelligence PY - 1973 SP - 1 EP - 10 UR - https://ijcai.org/proceedings/1973/1 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
