Chapter 4, Problem 9E

Explanation of Solution

Finding optimal solutions of A∗:

• Consider a very simple example: an initial belief state {S1,S2}, actions a and b both leading to goal state “G” from either initial state, and

  c(S1,a,G) = 3; c(S2,a,G) = 5;

  c(S1,b,G) = 2; c(S2,b,G) = 6.

• In the above case, solution “[a]” costs 3 or 5, the solution “[b]” costs 3 or 6. Either is “optimal” case in any obvious sense.
• Consider some other cases to find the optimal solution. Consider the deterministic case, in this case, think that the cost of a plan as mapping from initial physical state to the actual cost of executing plan.
• In this example, the cost of “[a]” is {S1:3,S2:5}. The cost of “[b]” is {S1:2,S2:6}.
• Here, the plan “p₁” weakly dominates plan “p₂”. The cost of “p₁” is less than the cost of “p₂”.
• If a plan “p” dominates all other plans, the user can say that it is optimal.
• Here note that the definition reduces to ordinary optimality in the observable case where every belief state is a singleton.
• So the above example does not have the optimal solutions. And the acceptable version of A* would be that whose solution do not dominate on another solution.
• To understand whether the “A*” is possible to apply or not its dependence on Bellman’s (1957) principle of optimality.
• principle of optimality:

  “An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision”

• the user must understand that this is a restriction on performance measures designed to facilitates efficient algorithm, not general definition of what it means to be optimal...