Search code examples
searchartificial-intelligenceheuristics

What are "depression regions" in heuristic searches?

While reading about weighted heuristic searches, I came to know that they don't perform well in depression regions; what are "depression regions"?

Solution

  • Per this paper, Multi-Heuristic A* (Aine et al., 2014), "depression regions" can be defined as:

    ...regions in the search space where the correlation between the heuristic values and the actual cost of the path to goal is weak

    The related references are:

    • C. Hernandez and J. A. Baier. Avoiding and Escaping Depressions in Real-Time Heuristic Search. J. Artif. Intell. Res. (JAIR), 43:523–570, 2012. [Link]
    • C. M. Wilt and W. Ruml. When Does Weighted A* Fail? In SOCS. AAAI Press, 2012. [Link]

    The former provides a similar definition:

    ...bounded areas of the search space in which the heuristic function is inaccurate compared to the actual cost to reach a solution.