Artificial Intelligence Asked by Kais Hasan on December 9, 2020

I was reading Artificial Intelligence: A Modern Approach 3rd Edition, and I have reached to the UCS algorithm.

I was reading the proof that UCS is complete.

The book state that:

Completeness is guaranteed provided the cost of every step exceeds some small positive constant $epsilon .$

And that’s because UCS will be stuck if there is a path with an infinite

sequence of zero-cost actions.

Why the step cost must exceed $epsilon$? Isn’t enough for it to be greater than zero?

Let's consider a problem where all edge costs are greater than zero, but not above some $epsilon$:

Image a problem where we have an infinite path where the first edge is cost $frac{1}{2}$, the next is $frac{1}{4}$, the following is $frac{1}{8}$, and so on forever. Every edge is greater than zero, meeting the condition being proposed in the question. However, this path overall has finite cost (1) even through there are an infinite number of states on that path. So, on this problem UCS will never reach paths with cost greater than 1. Thus, if the solution cost is 2, UCS will not find any solution to this problem, and thus it would not be a complete algorithm. So, all edges being greater than zero is not sufficient.

For most search algorithms to be complete, there must be a finite number of states with any given cost. (To be slightly more precise, there must exist some fixed $epsilon$ such that in each range size $epsilon$ there are a finite number of states.)

Correct answer by Nathan S. on December 9, 2020

0 Asked on December 16, 2021

0 Asked on December 16, 2021 by sirfroggy

bellman equations convergence proofs q learning reinforcement learning

1 Asked on December 13, 2021

convergence deep rl dqn function approximation reinforcement learning

1 Asked on December 13, 2021

3 Asked on December 11, 2021

categorical crossentropy comparison machine learning mean squared error objective functions

1 Asked on December 11, 2021

attention deep learning natural language processing transformer

1 Asked on December 11, 2021 by sports_stats

algorithm cross validation machine learning support vector machine

2 Asked on December 9, 2021

0 Asked on December 9, 2021 by blba

algorithmic bias neural networks reference request regularization training

0 Asked on December 9, 2021 by i_al-thamary

1 Asked on December 7, 2021

1 Asked on December 7, 2021 by jr123456jr987654321

activation function convolutional neural networks neural networks relu residual networks

1 Asked on December 7, 2021

data preprocessing machine learning neural networks normalisation standardisation

1 Asked on December 4, 2021 by nilsinelabore

convolutional neural networks keras machine learning neural networks

3 Asked on December 2, 2021 by pnar-demetci

deep learning deep neural networks feedforward neural network machine learning neural networks

2 Asked on December 2, 2021

geometric deep learning graph neural networks resource request

2 Asked on November 29, 2021 by ipsumpanest

6 Asked on November 29, 2021

bayesian deep learning convolutional neural networks keras tensorflow uncertainty quantification

1 Asked on November 29, 2021 by sanmu

architecture convolutional neural networks deep learning neural networks

1 Asked on November 29, 2021 by unter_983

actor critic methods ddpg policy gradients reinforcement learning

Get help from others!

Recent Answers

- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir