Artificial Intelligence: Condition for BFS being optimal

It is said in the book Artificial Intelligence: A Modern Approach for finding a solution on a tree using BFS that:

breadth-first search is optimal if the path cost is a nondecreasing function of the depth of the node. The most common such scenario is that all actions have the same cost.

From that I understand that if the path cost is non decreasing function of depth, the BFS algorithm returns an optimal solution, i.e., the only condition is the cost function being nondecreasing. But I think the only way for BFS to be optimal is the scenario in which all the path costs are identical, therefore a node found in a certain level is necessarily the optimal solution, as, if they exist, the others are. Therefore I think for BFS to be optimal, cost function should be non decreasing AND the costs of nodes should be identical. However, the book says only one of the conditions (former one) makes BFS optimal.

Is there a situation in which the costs are not identical, the cost function is nondecreasing and the solution returned by BFS is guaranteed to be optimal?

¡Nice question really!

The book is right and it just suffices for the path cost to be a nondecreasing function of the depth of the node ---though an additional note should be posted, see below. This directly implies that it is not necessary for nodes in the same level to have the same cost. Truth, however, is that it is hard to find such an example because the most obvious one consists just of considering all grounded actions to have the same cost.

Thus, let me try to start with the first statement (that it just suffices for the path cost to be a nondecreasing function of the depth of the node) with a theoretical example. Let $c(n,n')$ denote the cost of traversing the edge from node $n$ to node $n'$ and let us define it as:

$$c(n,n')=2^{g^*(s,n)}$$

where $g^*(s,n)$ is the minimum number of actions required to reach node $n$ from the start node $s$. I am certainly defining the cost of the edge as a function of the depth of the source node but it seems to be that this is absolutely okay with the statement in the book. Think of this as an attractive force exercised from the start state $s$ so that the farer you get, the more costly it is to progress. This function is clearly non-decreasing as it progresses as follows: 1, 2, 4, 8, ..., the total cost paths progressing as: 1, 3, 7, 15, ...

Now, let me show that Breadth First Search would certainly find an optimal solution. I will make it by induction:

Base case: the queue is seeded with the start state $s$. In the first iteration of BFS it is extracted from the queue and its children are generated, all of them with cost $2^0=1$. These nodes have been certainly reached through an optimal path so this satisfies the base case.

Induction step: let us assume that all nodes of depth $(d-1)$ have been already generated through optimal paths with a path cost $\sum\limits_{i=0}^{d-2}2^i=2^{d-1}-1$. In the induction step all nodes generated at depth $(d-1)$ are expanded to generate nodes at depth $d$ from the start state $s$. Obviously, all these nodes are generated through optimal paths as well since their cost corresponds to paths of minimum length from the start state (in other words, would there be a shorter path in terms of length instead of cost, it would have been discovered in a previous layer of the search tree traversed by BFS with a lower cost).

It seems to me that you would agree with this but it might not satisfy you because all nodes in the same level would have exactly the same path cost (and nodes at depth $d$ would have a total cost equal to $\sum\limits_{i=0}^{d-1}=2^d-1$), but the previous proof was necessary in order to consider the following case now:

Let us re-define the cost function as:

$$c(n,n')=\left\{\begin{array}{l} 2^{g^*(s,n)}, \mbox{in some cases, whichever}\\ 2^{g^*(s,n)}+\delta, \mbox{otherwise}\end{array}\right.$$

where $delta$ is just a small number, say $\frac{1}{2}$, such that it is smaller than the smallest of all costs $2^0=1$. Now you have a lot of different ways to get different path costs of nodes lying at the same level. In this particular case, the path cost of a node at depth $d$ ranges in the interval $[2^{d+1}-1, 2^{d+1}+\delta\times d-1]$.

However, the optimality condition of BFS still applies because the maximum difference ($\delta\times d$) is not enough to shift any node at depth $d$ after nodes that lie at depth $(d+1)$ in the queue the reason being that the path cost of those nodes ranges in the interval $[2^{d+2}-1, 2^{d+2}+\delta(d+1)-1]$. For a value of $\delta$ small enough nodes with different costs (even if they lie at the same depth) are found through optimal paths. However, note that I am assuming here $\delta$ to be small enough. If it is not, then BFS could be easily fooled and sub-optimal paths would be easily found by BFS.

Nice question, really! Hope this contributes somehow,

• I don't understand why assuming here $\delta$ to be small enough is so important. Could you please provide an example? – IggyPass Sep 26 '16 at 19:46
• Hi there! In the example given in second place, the idea is that even after introducing some noise in the form of $\delta$, paths to all nodes at depth $d$ are still optimal. Formally speaking, the real condition is that $\delta$ is smaller than $2^{g^*(s,n)}$ for every depth. However, for making the maths more readable I just simply assumed that it is smaller than the smallest of all costs, $2^0=1$. This way, the costs of all paths with the same length is different and, still, breadth-first search can compute optimal solutions. – Carlos Linares López Sep 28 '16 at 6:30

BFS is checking the nodes by depth levels. So it will check the nodes on level with depth D, before the ones with depth greater than D. If the cost function is not decreasing in depth , than a solution found on certain depth by BFS is optimal , because :

-all nodes that are not checked yet have greater or equal path cost and

-all nodes which have lower path cost are already checked and they are not a solution

I think that the definition should also imply that all nodes on the same depth level have equal path cost.

• That was my point actually. So, you say there is no situation in which the path costs are not identical and cost function is nondecreasing, yet bfs is optimal. Is that true? – Varaquilex Nov 6 '13 at 15:01
• Option 1: The path costs(NOT arc cost) at each depth level are the same. Option 2: The BFS checks all of the nodes at certain depth before returning the result, than f(D)>f(D+1) is enough. Where f is cost function and D is depth level. – Anton Nov 6 '13 at 15:45

Therefore I think for BFS to be optimal, cost function should be non decreasing AND the costs of nodes should be identical.

Firstly, the latter is a subset of the former.

Secondly, to see why the non-decreasability (if it's a word) of the path cost function is enough you have to remember that it's a function of the depth of the node. Meaning, all nodes at the same level will have the same cost. Thus, the only thing we are concerned with is it's non-decreasability, such that deeper solutions won't result in a better path cost.