1
$\begingroup$

Why is it that Iterative-deepening A* is optimal, even without monotonicity? How can I be sure that the first goal reached is the optimal one?

$\endgroup$
  • $\begingroup$ I'm currently studying a course text about A* and it isn't explained, just stated. I'll have a look at wikipedia. Thx for -1. $\endgroup$ – Lieven Cardoen Oct 27 '13 at 18:39
  • $\begingroup$ Well, wikipedia on A* doesn't give me much, neither does the page on Iterative deepening depth-first search. neither does de book Artificial Intelligence by Patrick Henry Winston... So the question remains, and apparently you don't have the answer. $\endgroup$ – Lieven Cardoen Oct 27 '13 at 18:44
  • $\begingroup$ Yes, I know, but in my case it's IDA*, not A*, and that's my question, why is IDA* optimal, even without monotonicity. Where as A* is only optimal with monotonicity. $\endgroup$ – Lieven Cardoen Oct 28 '13 at 8:06
  • 2
    $\begingroup$ Just flesh the question out a bit, then people would be less likely to -1; its the time of year when people dump stupid homework questions here, so some people are twitchy on the -1s. Expand on it, make everyone happy. Make it a question that is descriptive, will look good for the site in the future, that will help other people, etc. Doing this will avoid the itchy trigger fingers to auto-spam. $\endgroup$ – Realz Slaw Oct 28 '13 at 9:53
  • $\begingroup$ I will make it more descriptive when my knowledge expands on the subject. Now it's still rather small... But I'll update it as soon as I know more. $\endgroup$ – Lieven Cardoen Oct 29 '13 at 14:01
6
$\begingroup$

In a nutshell: IDA* traverses all paths of lengths iteratively larger and it stops only when expanding (as opposed to generating) the goal node with a cost such that all paths of an inferior cost have been already examined. Monotonicity (or consistency) is not required but admissibility of the heuristic function is a must if optimal solutions are required.

Now, how can we achieve that? It is simple. Get rid of the condition of monotonicity and pay attention instead to the condition of admissibility, i.e., $h(n)\leq h^*(n)$ where $h(n)$ is the heuristic estimate to reach the goal $t$ from node $n$ and $h^*(n)$ is the optimal cost of reaching the target. In other words, all that is required is that we have a function (i.e., $h(n)$) which provides a lower bound on the cost-to-go.

In the following bear in mind that IDA$^*$ is nothing more and nothing less than a depth-first search algorithm which prunes children that exceed a particular $f(n)$ value. As in the case of A$^*$, $f(n)=g(n)+h(n)$ where $g(n)$ is the cost of the path from the start state $s$ to $n$. All we have to do is to decide how to handle $f(n)$ while achieving our goal ...

  • Step 1: Since we have a lower bound to reach the goal, start IDA$^*$ with a threshold equal to $h(s)$, the heuristic estimate of the start state. This simply amounts to traverse all paths stemming from $s$ until a node $n$ is found such that $f(n) > h(s)$. This operation is necessarily finite in locally finite graphs (i.e., with bounded branching factor). While generating paths, note that you stop at those nodes $n$ that meet the aforementioned condition so that you can easily save the minimum excess over $h(s)$

  • Step 2: Once the first step is over, you know: first, no path of length $h(s)$ gets to the target; second, the next cheaper paths that can be traversed from $s$ have a cost equal to the minimum excess computed in the previous iteration. This is all you need. Proceed now as in Step 1 but using the minimum excess computed in the previous iteration as the threshold. If the iteration ended withouth success apply iteratively until getting to the solution.

Notice the remark I made in the first paragraph: from the behaviour of this algorithm, admissibility is guaranteed if you stop when expanding the goal node. This means that all paths of an inferior cost have been already traversed. If you ever stop when generating the goal, then you might incurr in suboptimal solutions since those paths might have a cost that exceeds the current threshold of that iteration.

In no place, consistency is required. From Steps 1 and 2, a proof of correctness can be easily derived by induction on the number of iterations.

Hope this helps,

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.