Question posted in 
I’ve tried to figure what the A* algorithm would be in case the Heuristic function would not satisfy the monotonicity condition, where in
h(u) <= e(u,v) + h(v), for every u,v such that there is an edge between u and v
is the condition for monotonicity, where h is the heuristic function, u and v are vertices in the search graph, and the function e gives the edge cost between u and v (The search graph is undirected). However, wikipedia (here) does not give the algorithm for this, nor do other sources like Norvig’s book on Artificial Intelligence.
Is there a good source to study this. Pseudo code would be great!
Also, I do not wish to solve this by converting the non monotonic heuristic function to a heuristic one.
2
Answers
Assuming the heuristic function function is still admissible – A* algorithm will work fine.
However, for non-monotonic heuristic functions, you might need to update an already ‘closed’ node, and you should allow this behavior.
In the case of tree search it’s not required to be consistent to be optimal. Instead if it’s a graph search A* is optimal only in the case that the heuristic is admissible and consistent.
In this picture you can see an example of a non consistent heuristic: the A* algorithm doesn’t find the right path.
Maybe you can modify the standard A* algorithm as @amit said, but in that case you need to consider an already closed state, so the search will not be optimal. It may find the optimal path but it will expand more nodes than in the solution with a consistent heuristic, so it’ll be sub-optimal.