Potential search: A new greedy anytime heuristic search Conference Paper

abstract

  • Abstract In this paper we explore a novel approach for anytime heuristic search, in which the node that is most probable to improve the incumbent solution is expanded first. This is especially suited for the" anytime aspect" of anytime algorithms-the possibility that the algorithm will be be halted anytime throughout the search. The potential of a node to improve the incumbent solution is estimated by a custom cost function, resulting in Potential Search, an anytime best-first search. Experimental results on the 15-puzzle and on the key player problem in communication networks (KPP-COM) show that this approach is competitive with state-of-the-art anytime heuristic search algorithms, and is more robust.

publication date

  • January 1, 2010
{"cc_re__cc_re__cc_by_3_0": ["a class=\"powered-by-vivo\" href=\"http://vivoweb.org\" target=\"_blank\" title=\"Powered by VIVO\">VIVO</a>\n    </p>\n    <p class=\"right\">\n      <small>Automatic Data Acquisition by <a href=\"http://www.omnisol.co.il\" target=\"_blank\">Omnisol</a></small>\n    </p>\n  </div>\n  <section class=\"icons-copyright\">\n    <p>Icons made by <a href=\"http://www.flaticon.com/authors/dave-gandy\" title=\"Dave Gandy\">Dave Gandy</a> from <a href=\"http://www.flaticon.com\" title=\"Flaticon\">www.flaticon.com</a> is licensed by <a href=\"http://creativecommons.org/licenses/by/3.0/\" title=\"Creative Commons BY 3.0\" target=\"_blank\">CC 3.0 BY</a></p>\n    <p>Icons made by <a href=\"http://www.flaticon.com/authors/madebyoliver\" title=\"Madebyoliver\">Madebyoliver</a> from <a href=\"http://www.flaticon.com\" title=\"Flaticon\">www.flaticon.com</a> is licensed by <a href=\"http://creativecommons.org/licenses/by/3.0/\" title=\"Creative Commons BY 3.0\" target=\"_blank\">CC 3.0 BY</a></p>\n  </section>\n</footer>\n\n\n<script type=\"text/javascript\" src=\"/js/individual/propertyGroupControls.js\"></script>\n<script type=\"text/javascript\" src=\"/js/imag", "ef=\"http://www.flaticon.com/authors/dave-gandy\" title=\"Dave Gandy\">Dave Gandy</a> from <a href=\"http://www.flaticon.com\" title=\"Flaticon\">www.flaticon.com</a> is licensed by <a href=\"http://creativecommons.org/licenses/by/3.0/\" title=\"Creative Commons BY 3.0\" target=\"_blank\">CC 3.0 BY</a></p>\n    <p>Icons made by <a href=\"http://www.flaticon.com/authors/madebyoliver\" title=\"Madebyoliver\">Madebyoliver</a> from <a href=\"http://www.flaticon.com\" title=\"Flaticon\">www.flaticon.com</a> is licensed by <a href=\"http://creativecommons.org/licenses/by/3.0/\" title=\"Creative Commons BY 3.0\" target=\"_blank\">CC 3.0 BY</a></p>\n  </section>\n</footer>\n\n\n<script type=\"text/javascript\" src=\"/js/individual/propertyGroupControls.js\"></script>\n<script type=\"text/javascript\" src=\"/js/imageUpload/imageUploadUtils.js\"></script>\n<script type=\"text/javascript\" src=\"/js/individual/moreLessController.js\"></script>\n<script type=\"text/javascript\" src=\"/js/individual/individualUriRdf.js\"></script>\n<script type=\"text/javascript\" src=\"/js/individual/individualUtils.js\"></script>\n<script type=\"text/javascript\" src=\"http"], "copyright__copyright__copyright": [" possibility that the algorithm will be be halted anytime throughout the search. The potential of a node to improve the incumbent solution is estimated by a custom cost function, resulting in Potential Search, an anytime best-first search. Experimental results on the 15-puzzle and on the key player problem in communication networks (KPP-COM) show that this approach is competitive with state-of-the-art anytime heuristic search algorithms, and is more robust.\n\npublication date\n\n  \u2022 January 1, 2010", " possibility that the algorithm will be be halted anytime throughout the search. The potential of a node to improve the incumbent solution is estimated by a custom cost function, resulting in Potential Search, an anytime best-first search. Experimental results on the 15-puzzle and on the key player problem in communication networks (KPP-COM) show that this approach is competitive with state-of-the-art anytime heuristic search algorithms, and is more robust.\n\npublication date\n\n  \u2022 January 1, 2010", " possibility that the algorithm will be be halted anytime throughout the search. The potential of a node to improve the incumbent solution is estimated by a custom cost function, resulting in Potential Search, an anytime best-first search. Experimental results on the 15-puzzle and on the key player problem in communication networks (KPP-COM) show that this approach is competitive with state-of-the-art anytime heuristic search algorithms, and is more robust.\n\npublication date\n\n  \u2022 January 1, 2010", " possibility that the algorithm will be be halted anytime throughout the search. The potential of a node to improve the incumbent solution is estimated by a custom cost function, resulting in Potential Search, an anytime best-first search. Experimental results on the 15-puzzle and on the key player problem in communication networks (KPP-COM) show that this approach is competitive with state-of-the-art anytime heuristic search algorithms, and is more robust.\n\npublication date\n\n  \u2022 January 1, 2010"]}