( 1 )

The first term represents the case that a is not visible, which occurs with probability 1 — pna. In this case the only choice is to remain at n and acquire another image, which incurs cost lnn and results in an expected length of lnn + Eng. The second term represents the case that a is visible, which occurs with probability pna. In this case the expected length of the shortest path is the smaller of lna + Eag and lnn + Eng, corresponding to the options of going to a or staying at n. Recall that we are assuming that the goal is reachable from any node, and thus Eag < oo. Given that the edge n —> a is the only edge leaving n, we know that all paths from n to g have to go through a, and thus that Eng > lna + Eag· This allows us to solve Equation 2 for Eng, yielding:

Now, let us consider a node n with two outgoing edges n —» a and n —» b. The relation for the expected length of the shortest path from n to g can be expressed analogously, except that now there are four cases, de­ pending on which of a and b are visible. Using the shorthand p to denote (1 — p), we obtain the following relation for Eng:

Unlike in the case for only a single edge, it is no longer possible to explicitly solve these equations for Eng because of the minimum expressions, which recur­ sively relate the unknown quantities Eig. For example, to determine the value of the minimum expressions in Equation 4, we need to know the ordering among K a, Kb, and K n, where Ki denotes lni + Eig. While one can still deduce that K n cannot be the smallest of the three, each of the remaining 4 orderings is possible:

Note that if such orderings were known for all nodes, Equations 4 and 5 would simplify to linear equations involving the unknowns Eng. The expected lengths of the shortest paths could then be computed simply by solving a system of N — 1 linear equations, where N is the total number of landmarks (including the goal). The presence of the minima, however, prohibits this approach.