Aepsilon - An Efficient Near Admissible Heuristic Search Algorithm
Proceedings of the Eighth International Joint Conference on Artificial Intelligence. Planning and Search. Pages 789-790.
Abstract
The algorithm A* (Nilsson, 1979) presents two significant drawbacks. First, in seeking strict optimal solution paths it necessarily has high order of complexity. Second, the algorithm doesnot explicitly descriminate between the cost of a solution path and the cost of finding the solution path. To confront these problems we propose the algorithm A£, a generalization of A*. Instead of seeking an optimal solution, it seeks one which is within a factor (I+E) of optimum (E0). The basic idea is to avoid doing any search at all on most near optimal partial solutions by sticking to a small number of most fruitful paths. Various strategies for searching for near optimal partial solutions are discussed . Experimental results are pres e nted indicating that AE has average complexity of lower order than A* and compares favorably to the related algorithm AE* (Pearl and Kim, 1982).
@inproceedings{ijcai1983p192,
title = {Aepsilon - An Efficient Near Admissible Heuristic Search Algorithm},
author = {Ghallab, Malik and Allard, Dennis G.},
booktitle = {Proceedings of the Eighth International Joint Conference on
Artificial Intelligence, {IJCAI-83}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Alan Bundy},
pages = {789--790},
year = {1983},
note = {Planning and Search},
url = {https://ijcai.org/proceedings/1983/192},
}
TY - CPAPER TI - Aepsilon - An Efficient Near Admissible Heuristic Search Algorithm AU - Ghallab, Malik AU - Allard, Dennis G. T2 - Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI-83 PB - International Joint Conferences on Artificial Intelligence PY - 1983 SP - 789 EP - 790 UR - https://ijcai.org/proceedings/1983/192 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
