Today I finished my semester exam on AI. While studying I did a googling on how UCS (Uniform Cost Search) and A* works. This site states that UCS is not always complete. Reason is if the zero cost path connects to the same node in a tree UCS will fall into an infinite loop. For some extent conceptually it is true. The below picture explains the idea.

If the start node is S then it goes to the A then B from B it will go to the S. This loop remains without going to the G. The same way A* also falls into an infinite loop if the heuristic values of A,B and S are same. Because here traversed path value g(n) is  zero. So ultimately f(n) remains unchanged.

f(n) = h(n) + g(n)

Here h(n) same and even after ‘n’ numbers of iteration g(n) = 0.

 

I thought about the above idea, and conceptually it is right. But in real world scenario it is very hard to get a situation like this. Even if we get a situation like this A to B zero cost. Then A and B same.

But in Semantic networks we may have a situation like this. In a self referencing documents, so the UCS can be cracked. But A* will not be cracked easily because even on a self referencing document the re-request cost will increase the g(n) value.

I just thought about the scenario and wrote this, there can be controversies and my assumption may be completely wrong. In case provide a comment here (not some where else, since I get blog comments direct to email or in FB) and let’s discuss.