General Pseudocode for Depth/Breath/Best First Search



Sampreeth Chebolu, Theodoros Tavoulareas and Christoph F. Eick COSC 4368: Fundamentals of Artificial Intelligence Spring 2020Problem Set1 (Individual Tasks)Fourth DraftDeadline: Sa. February 22, 11:59p Last Updated: Feb. 16, 9aWeight: 35-44% of the points available for the 3 problem sets!Comment: Points allocated to each of the 5 tasks are tentative and subject to change. 1) Applying Various Search Strategies to a State Space (12 pts) Theodoros Assume that you have the following search graph, where S is the start node and G1 and G2 are goal nodes. Arcs are labeled with the cost of traversing them and the estimated cost to a goal is reported inside nodes. Apply the search strategies listed below to the search graph:, (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 there is a tie with respect to which node has to be expanded next, nodes should be expanded in alphabetical order. The used search strategies include;breadth-firstdepth-firstbest-first (using f = h)A* (using f = g + h) SMA* (using f=g+h and limiting the open-list to just 3 elements)General Pseudocode for Depth/Breath/Best First Search 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.General Pseudocode for SMA*/A*Search 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.Submission Guidelines: The solution needs to be as follow:GOAL Reached firstExpanded statesOPEN ListCLOSE ListFailure to follow above instruction will lead to point deductions2) Describe a Search Space (10 points) SampreethIn the water-jug puzzle we are given a 3 liter jug, named Three, and a 4 liter jug, named Four. Initially, Three and Four are empty. A jug can be filled from a tap T, and, we can discard the water from either jug into a drain, D. Water in one jug may also be poured into the other jug; however, this operation is only allowed if the receiver jug has sufficient capacity to receive the water. There are no other measuring devices. We want to find a set of operations that will leave precisely two liters of water in Four. (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 given state, when the operator is legal (i.e., a set of constraints on when the operator can be applied to an arbitrary state) and the description of the successor state 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 SpaceDraw 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.3) A* (10 points) Theodoros a) What characteristics should a good evaluation function h for A* have? Give reasons for your answer! b) Assume A* is used with a heuristic h(s) that sometimes overestimates the cost of reaching the goal state from s. Will A* in this case still find the optimal solution? If your answer is yes, give a reason for your answer! If your answer is now, gives an example of a search problem with the above characteristics for which A* no longer finds the optimal solution! c) Assume h1 and h2 are both admissible heuristics for A* for a search problem; is h(x)=max(h1(x), h2(x)) also an admissible heuristic? Do you prefer heuristic h over heuristics h1 and h2 or not? Give reasons for your answer! 4) Implementing and Experimenting with Randomized Hill Climbing (26 pts) Theodoros Implement Randomized Hill Climbing and apply it to a minimization problem involving the following function f: with x,y∈[?6,+6]Your procedure should be called RHC and have the following input parameters:sp: is the starting point of the Randomized Hill Climbing runp the number of neighbors of the current solution that will be generatedz neighborhood size; for example if z is set to z=0.5 p neighbors for the current solution s are generated by adding vectors v=(z1,z2) with z1 and z2 being random numbers in [-0.5,+0.5] uniformly distributed seed which is an integer that will be used as the seed for the random generator you employ in your implementation. RHC returns a vector (x,y) the value of f(x,y) and the number solutions that were generated during the run of RHC.Run your randomized hill climbing procedure RHC twice for the following parameters:sp= (2.9, 3.2), (-2.5,+3.2), (4.2,-2) and (0,0)p= 30 and 120z= 0.03 and z=0.1For each of the 32 runs report:a. the best solution (x,y) found and its value for fb. number of solutions generated during the run. Summarize your results in 4 tables; one for each p and z combination. Interpretthe obtained results evaluating solution quality, algorithm speed, impact of sp, p, and z on solution quality and algorithm speed. Do you believe with other values for p and r better results could be accomplished? At last, assess if RHC did a good, medium or bad job in computing a (local) minimum for f. Finally, produce one more run using sp=(4.2,-2)—the 33th run — by choosing parameters for p, z and seed of your own liking and report the solution s found, its value for f(s), and the number solutions searched. Solutions reported for the 33th run that are better will receive more credit. Submission Guidelines: p=30 & z=0.03Run1Run2#sol se#sol searchedS s sol f(sol)#solsearchedBest solF f(sol)(2.9, (2.9, 3.2)(-2.5( (-2.5,+3.2)((4.2 (4.2,-2)(0,0) ( (0,0)You should summarize your results in 4 tables formatted as the above, for each of the 4 combination of p & z. Don’t forget to summarize the results of the 33th run and to provide the other information asked for in the project specification!Failure to follow above instruction will lead to point deductions5) A Map Coloring Constraint Satisfaction Problem (32 pts) SampreethVariables = {X0, X1, X2, ….., X49}Domains = {Red, Green, Blue, Yellow}Constraints = bordering regions must have different colors.For Example, in the following graph, X0≠X1, X0≠X2, X1≠X2, …868680179070243824711521Refer to the following .csv files for state names and the state adjacency matrix of the US Map and Australia Map and for state names and solve the Constraint Satisfaction Problem for it based on the above mentioned constraints.adjacency_matrix_US.csvadjacency_matrix_Aust.csvadjacency_matrix_India.csvYour program have to read the .csv files that contain the adjacency matrix, such as those for the states of USA and Australia (these are the “Variables”) and solve the respective CSP-problem. Moreover, provide a counter nva (“number of variable assignments) that counts the number of times an initial color assigned to a variable or the color assigned to a a variable is changed; in addition to outputting the solution to the CSV also report the value of this variable at the end of the run.Since there are 50 states in the USA, number of variables, n= 50. Therefore, the adjacency_matrix_US.csv file contains a (50 X 50) matrix indicating whether a State “j” is adjacent to State “i”, where 1<= i,j <=50. Statei is adjacent to Statej iff Stateij =1, else not adjacent. The first row and first column of this .csv file are the names of the 50 states in the USA.Since there are 7 states in Australia, number of variables, n= 7. Therefore, the adjacency_matrix_Aust.csv file contains a (7 X 7) matrix indicating whether a State “j” is adjacent to State “i”, where 1<= i,j <=7. Statei is adjacent to Statej iff Stateij =1, else not adjacent. The first row and first column of this .csv file are the names of the 7 states in Australia.Since there are 28 states in India, number of variables, n= 28. Therefore, the adjacency_matrix_India.csv file contains a (28 X 28) matrix indicating whether a State “j” is adjacent to State “i”, where 1<= i,j <=28. Statei is adjacent to Statej iff Stateij =1, else not adjacent.The output of your program should be in the following format: state:color -> {adj_state1:color, adj_state2:color, adj_state3:color,…}Provide different output files for each test case.Notes on grading:More generic solutions to the problem that do not only solve the 2 example problems but are capable to read any CSV file with state names and the state adjacency matrix and solve the respective CSV problem will obtain 15% more points for the problem. A third test case to test this capability will be provided short before the submission deadline. Sophisticated approaches that lead to lower complexities in solving the respective CSPs—measured by the final value of the variable nva—might get 10-15% higher scores compared to programs that use brute force approaches.Submission Guidelines:Give a brief description of the strategy you used to solve the CSPPseudo Code of your CSP solverExplain the Pseudo Code in a paragraphSource Code for the implementation and instructions on how to run your code ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download