Remark: Problems 1-4 are paper and pencil problems, whereas problem 5 involves some programming and experimentation.
(a) Formulate this problem as a state-space search problem Give a precise definition of a state, the start state, the goal state or goal condition, and the operators. Operators should be specified as "schemas" that indicate for a general state, when the operator is legal (i.e., a set of constraints on when the operator can be applied to an arbitrary state, which is given as an n-tuple) and the description of the successor state (given as an n-tuple that is completely specified from the previous state's n-tuple and the parameters associated with the given operator) after the operator is applied. In other words, each operator should be specified in a way that it would easily implemented in a program to solve this problem.
(b) Show the State Space Draw the complete state-space graph that includes all nodes (and legal directed arcs connecting these nodes) for this problem. Inside each node show the state description, and label each arc with its associated operator. Highlight a path that gives a solution to the problem.
(a) Depth-First Search
Copy the grid and then mark the grid squares with the number(s) indicating when that square is expanded during a Depth-First search from S to G. Assume children nodes are visited in the order up, left, right, down. Assume cycle checking is done so that a node is not generated in the search tree if the grid square position associated with the node occurs somewhere on the path from this node back to the root node. Highlight the solution path found, if any, or explain why none is found.
(b) Greedy Best-First Search
Copy the grid again and then mark the grid squares with the number(s) indicating when that square is expanded during a Greedy Best-First search from S to G. Use as the heuristic function h(n) = |xn - xg| + |yn - yg| where the grid square associated with node n is at coordinates (xn, yn) in the grid and the goal node G is at coordinates (xg, yg). Assume you do not generate a node if that node's associated grid position has previously been generated. (That is, the third way to deal with repeated states as described on page 82.) In the case of ties in evaluation function values, for siblings expand them in the precedence order up, left, right, down. In the case of ties between non-siblings, use FIFO order to expand first the node that has been in the NODES list the longest. Highlight the solution path found, if any, or explain why none is found.
(d) Hill-Climbing Search
Copy the grid again and use Hill-Climbing Search. As above, number the squares when a node is expanded. Use the heuristic function defined in (b). Use the same tie-breaking rules as defined in (b). Highlight the solution path found, if any, or explain why none is found.
(e) An Infinite Grid
Suppose the grid is extended infinitely in all directions but S, G and the dark squares remain as before. Which of the following methods will not be able to find a solution to this problem? Breadth-First, Depth-First, Depth-First Iterative Deepening, Greedy Best-First, and A*. Which of these would be the best method, and why? Again, in the case of ties in ordering nodes on the NODES list, use the precedence defined in (b).
Be sure to explain your answers. For those cases where h3(s) is not admissible, show a counter example.
Which of the above four combinations do you feel is the best one? Why?
(0,0) (0,1) (0,2) (0,3) (0,4)… (1,0) (1,1) (1,2) (1,3) (1,4)… (2,0) (2,1) (2,2) (2,3) (2,4)… (3,0) (3,1) (3,2) (3,3) (3,4)… (4,0) (4,1) (4,2) (4,3) (4,4)…
Assume best-first search is used for this particular problem, and the objective is to find a path to the reachable goal position. Three evaluation functions, listed on the next page, are used to solve this problem (assume that states with the lowest values will be expanded first). For each of the three evaluation functions answer the following two questions: If the evaluation function is used will best-first always find a solution? If your answer to the first question is yes, also evaluate the efficiency of the search! Give reasons for your answers!
1) h1(x,y):= |x|+|y|
2) h2(x,y):= if x< 200 then |x-100| + |y-300|
else if x<400 then |x-300| + |y-100|
3) h3(x,y):= min(|x-100| + |y-300|, |x-300| + |y-100|)
(b) Now assume you have to use backtracking for the above problem. Is backtracking a suitable search strategy for the problem? Give reasons for your answer!
(1) randomized hill climbing
(2) simulated annealing
Design your program in such a way that parameters for each techniques (size of a neighborhood, number of samples in a neighborhood for hill-climbing; size of neighborhood, cooling schedule,... in the case of simulated annealling) can be selected (or propose a technique that automatically selects/finds the "best parameter" setting during the run). Run your program for the 3 functions of a benchmark that is provided to you in the third week of September also trying to find the best parameter settings of each technique for each function. Write a short (2-4 single space pages) report that explains the capabilities and interfaces of a program and techniques that your program uses. Moreover, your report should also compare the two techniques for the 3 optimization problems in the benchmark. Be also prepared to demo your program. Moreover, add a simple visualization component to your program that visualizes the search your program conducts for a particular optimization problem.