Is it just me or does the Vanilla-A* algorithms look too bad? I mean especailly in the second image [(d) A* (Adaptive Depth)], why does it search behind itself?
It's a graph search. Imagine adding an out-of-plane edge that travels from behind the starting point to the goal. Since taming that path could be optimal it has to check - it doesn't attempt to reason that such a path would necessarily be obstructed by what's been explored thus far. It's just a graph search.