Homework1 (Individual Homework)

First Draft

Last Updated: 10/6/2017

Due: 10/17/2017 at 11p

(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.

(i) For each of the search strategies listed below,
(a) indicate which goal state is
reached if any, (b) list, in order, the states expanded,
and (c) show the final contents of the OPEN and CLOSED lists. (Recall that a
state is *expanded* when it is *removed* from the OPEN list.)
When all else is equal, nodes should be expanded in alphabetical order.

- breadth-first

- depth-first

*best-first*(using*f = h*)

*A**(using*f = g + h*)

*SMA* (using f=g+h and limiting the open-list to just 3 elements)*

OPEN = { startNode } // Nodes under consideration. CLOSED = { } // Nodes we're done with. while OPEN is not empty { remove an item from OPEN based on search strategy used - call it X if goalState?(X) return the solution found otherwise // Expand node X. { 1) add X to CLOSED 2) generate the immediate neighbors (ie, children of X) 3) eliminate those children already in OPEN or CLOSED 4) add REMAINING children to OPEN } } return FAILURE // Failed if OPEN exhausted without a goal being found.The following is the basic outline of the search strategy used for the A* and SMA* search algorithms.

OPEN = { startNode } // Nodes under consideration. CLOSED = { } // Nodes we're done with. while OPEN is not empty { remove an item from OPEN based on search strategy used - call it X if goalState?(X) return the solution found otherwise // Expand node X. { 1) add X to CLOSED 2) generate the immediate neighbors (ie, children of X) 3) add all children to OPEN } } return FAILURE // Failed if OPEN exhausted without a goal being found.

Two 2 versions v1 and v2 of alpha/beta search are used:

(v1) enumerating leaf nodes from left to right

(v2) enumerating leaf nodes from right to left

Will versions v1 and v2 always select the same move, if there is a single best move? Will version v1 and v2 always have the same runtime? Give reasons for your answers!

(b) Most game-playing programs do not save search results from one move to the next. Instead, they usually start completely over whenever it is the machine's turn to move. Why?

a. Choose a CSP formulation. In you formulation, what are the variables?

b. What are the possible values of each variable?

c. What sets of of variables are constrained on how?

d. Now give a sketch of a search strategy that solves this problem for a given k value or reports that it is infeasible.

Describe (outlining all partial and complete plans generated and explaining why
they are generated and also giving the goal-subgoal tree(s) for the final plan) how a
STRIPS-like (or NOAH-like, if you prefer that) classical AI planning system
will come up with a plan that accomplishes the following goal, assuming that the depicted state is the initial
state: