In my AI textbook, the following has been said about uniform cost search:
Therefore, it will get stuck in an infinite loop if there is a path with an infinite sequence of zero-cost actions.
I understand this part.
However, it also mentions:
Completeness is guaranteed provided the cost of every step exceeds some small positive constant.
I don't understand how the positive constant helps. Even if this condition was satisfied, an infinite path would still cause the algorithm to not find a possible solution.
Could someone explain this part?
Because those small constants will eventually add up and in total become more than the cost to some node that does not continue that infinite path. At that point, the node continuing the infinite path will not be at the front of the priority queue, so some other node will be explored instead. After that, it may start exploring the infinite path again, but again the costs will add up until it loses to some other node in the queue.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With