Question

1. Give two examples of the limitations of the STRIPS representation for planning, i.e. things it cannot represent or cannot easily represent.

2.   a. In what sense is branch-and-bound search similar to A* search?

            b. In what sense is branch-and-bound search similar to depth-first search?

3. How does A* search extend best-first search?

4. If we have a search problem that does not involve costs, can we still use a heuristic function with A* in order to find the optimal solution? Explain your answer.

5. Define a plateau. Why are plateaus a problem for local search applied to constraint satisfaction problems?

6.  What are the two key weaknesses of Stochastic Local Search?

7. If we unroll a CSP planning problem to horizon k and do not find a solution, is there any point in unrolling it to a larger time horizon and trying again? Explain why or why not.

8.  If we have two admissible heuristics h1 and h2, would it be better to use min(h1, h2) or max(h1, h2) as a heuristic with A* search? Briefly explain your answer.

9. How many states can be represented by four variables, each of which can take five values?

Section C. Arc Consistency

Consider the following constraint network.

10. If the variables A, B and C each have the domain {1,2,3,4} before arc consistency is run, indicate what their domains will be after arc consistency has finished:

A = {                            }

B = {                            }

C = {                           }

11. If we have just considered the edge and reduce the domain of B as a result, do we need to add any arcs back to the To-Do Arcs list? If not, why not? If so, which edges?

Section D. Optimality of A*

Assume that we are running A* search on a problem and we find path p to a goal. In the lecture and text, we proved mathematically that, if we are using an admissible heuristic, there is no other path that is shorter than p. In other words, if path p' is still on the frontier, and p'' is a path to the goal that extends p', path p will always be less than (or equal to) p''. This is called proving the optimality of A*.

12. Explain why we cannot prove the optimality of A* if the heuristic is not admissible. Be as specific and detailed as possible, referring to the proof in your answer.

Answer 1

Answer to Question (1): Examples of the limitations of the STRIPS representation for planning

(a) STRIP can support only positive literals. For xample, STRIP can represent the state Poor^Unknown, but it cannot represent states with negative lietrals like ¬Rich^¬Famous

(b) STRIPS supports only ground literals in goals, such as Rich^Famous. It cannot represent quantified variables in goals, such as ∃x At(P1,x)∧AtP2, xis the goal of having P1 and P2 in the same place.

Answer to Question (2):

a. In what sense is branch-and-bound search similar to A* search?

A* is basically an extended version of branch-and-bound search and thus similarity exists between them. In branch-and-bound search, at each iteration the search expands the best path that found so far. In A*, the best path is picked by also considering how much additional cost is needed from the current state to the goal state by employing some heuristic evaluation function. In a sense, both using the current best node for exploring next.

Another similarity between the branch-and-bound and A* search algorithms is that both returns optimal solutions. A* algorithm returns global optimal solution, provided the heuristic evaluation function is admissible (do not over estimate). However, the optimal solution that may be returned by the branch-and-bound may be sub-optimal, as the branch-and-bound may overlook global optimal solutions.

b. In what sense is branch-and-bound search similar to depth-first search?

Branch-and-bound search maintains minimum and maximum bounds for solutions to search. If the current solution exceeds the bounds, the search will branch to another branch to proceed with another iteration of the search. Within an iteration, the branch-and-bound search proceeds exactly like Depth First Search (DFS), by selecting the node that created recently for exploring next.

Answer to Question (3): How does A* search extend best-first search?

A* search is an extended version of the Best First Search (BFS). In BFS, the next node for exploration is selected based on a heuristic evaluation function that evaluates the relative merits of the immediate successors of the current node. Due to this behavior, BFS is considered as a Greedy Search, as the currently promising path may not be the real optimal path.

To avoid this demerit of the BFS, A* search apply the heuristic functions till the expected goal state, from all the possible states of the current state. Not only that, when the current path started looks less promising, the A* algorithm switch to an earlier promising path.

Answer to Question (4): If we have a search problem that does not involve costs, can we still use a heuristic function with A* in order to find the optimal solution? Explain your answer.

Yes, it is possible to apply A* algorithm, even if the search problem does not have a cost associated with individual paths. In such cases, the cost of moving from one node to another is taken as uniform and the total estimated additional number of moves required from the current state to the goals state is taken as the heuristic function. This h value will be added to the g value (number moves so far taken to reach the current state) to get the f value (the cost, f=g+h)) of the current node