Skip to Content

    Research Proposal

    Add your abstract and contact information and we will be in touch

    Thanks We will be in touch soon

    Contact us

    Leave a massage and we’ll get back to you

      You can also reach us at:

      Cyber Security Research Center @ Ben-Gurion University of the Negev
      P.O.B. 653
      Beer Sheva, 84105,

      +972 8 6428005
      +972 8 6428121

      Cooperation with IBM

      Rational deployment of multiple heuristics in optimal state-space search‏

      E Karpas, O Betzalel, SE Shimony, D Tolpin, A Felner

      The obvious way to use several admissible heuristics in searching for an optimal solution is to take their maximum. In this paper, we aim to reduce the time spent on computing heuristics within the context of A⁎ and IDA⁎ . We discuss Lazy A⁎ and Lazy IDA⁎ , variants of A⁎ and IDA⁎ , respectively, where heuristics are evaluated lazily: only when they are essential to a decision to be made in the search process. While these lazy algorithms outperform naive maximization, we can do even better by intelligently deciding when to compute the more expensive heuristic. We present a new rational metareasoning based scheme which decides whether to compute the more expensive heuristics at all, based on a myopic regret estimate. This scheme is used to create rational lazy A⁎ and rational lazy IDA⁎ . We also present different methods for estimating the parameters necessary for making such decisions. An empirical evaluation in several domains supports the theoretical results, and shows that the rational variants, rational lazy A⁎ and rational lazy IDA⁎ , are better than their non-rational counterparts.

      Back to top
      Font Resize