Here I will send you 3 more files to help for the coding part of the assigment.
2 CAP 6635 Artificial Intelligence Homework 2 [If you have multiple pictures, please include all pictures in one Word/pdf file] 1. [1 pt] Given two admissible heuristics and , which of the following heuristic are admissible or may be admissible (explain why) a. b. c. , where d. e. (a) Initial State (b) Goal State Figure 1: Eight Puzzle Game 2. [1 pt]. Figure 1 lists the initial state and the goal state of Eight Puzzle game (with eight letter-tiles and one empty tile, i.e., the white tile). Please use A* search to build a search tree to carry out search from the initial state to the goal state. (No need to show the complete tree. Just report the portion from the initial state to the goal state) a. Please use number of misplaced letter-titles as the heuristic function, and report the search tree from the initial nodes to the goal node (please include the evaluation function values f(N), g(N), and h(N) for each node). [0.5] b. Please use Manhattan distance between each letter-tile and its goal position as the heuristic function, and report the search tree from the initial nodes to the goal node (please include the evaluation function values f(N), g(N), and h(N) for each node). [0.5] 3. [1 pt] Figure 2 shows a robot navigation field, where the red square (d2) is the robot, and green square (c7) is the goal. The shad squares (such as b2, c2, etc.) are obstacles. The robot is not allowed to move in diagonal line. Please use best first search to find the path from d2 to c7 · Report nodes in the fringe (including their f(N) values), in the orders they are included in the fringe. [0.5] · Report the order of the nodes being expanded. [0.25] · Report the final path from d2 to c7. [0.25] Figure 2 Robot navigation field. 4. [1 pt] Figure 2 shows a robot navigation field, where the red square (d2) is the robot, and green square (c7) is the goal. The shad squares (such as b2, c2, etc.) are obstacles. The robot is not allowed to move in diagonal line. Please use A* search to find the path from d2 to c7 · Report nodes in the fringe (including their f(N) values), in the orders they are included in the fringe. [0.5] · Report the order of the nodes being expanded. [0.25] · Report the final path from d2 to c7. [0.25] 5. [1 pt] Figure 3 shows a search tree where A denotes the node corresponding to the initial state, and E is the goal node. In the figure, h=x denotes the heuristic function value and c=x denotes the actual cost between nodes (i.e., arch cost). a. Please explain why (or why not) the heuristic function in Figure 2 is (or is not) a consistent heuristic. [0.25 pt] b. When carrying out A* search using the heuristic values, what are the order of the nodes being expanded? Please explain your solutions [0.25 pt] c. What are the possible problem of using A* search using the heuristic values in Figure 2 to search the goal node? [0.25 pt] What is solution to solve the problem? [0.25 pt] Figure 3: A search tree and husirtic function values 6. [1 pt]. Prove that if a heuristic is consistent, it must be an admissble heuristic. [hint: consier proof by induction] 7. [1 pt] Figure 4 shows a roadmap with four cities. The value next to each edge denotes the actual distance between two nodes. The heuristic value of each city is given in Table 1. a. Use greedy Best-First Search to create a search tree to find path from source node S to the goal node G. The three must show f(N) value of each node, and report final path discovered by the Best-First Search (either highlight the path on the tree, or report the path separately) [0.5 pt] b. Use A* Search to create a search tree to find path from source node S to the goal node G. The three must show f(N) value of each node, and report final path discovered by the Best-First Search (either highlight the path on the tree, or report the path separately) [0.5 pt] Figure 4: A field map with eight nodes. Value next to each edge denotes actual cost between two nodes. Heuristic value of each city is given in Table 1. Table 1: Heuristic values h(N) of each node to the goal (G) node. A 10.4 B 6.7 C 4.0 D 8.9 E 6.9 F 3.0 G 0 S 11.0 8. [1 pt] Describe simulated annealing search [0.25 pt]. How does simulated annealing search behavior when the temperature T is very large vs. T is very small [0.25 pt]. What is main difference between simulated annealing vs. Monte Carlo descent [0.25 pt]. If T=0 at all times, which search method is the simulated annealing search equivalent to [0.25]? 9. [1 pt] Assume you were asked to place 8 queens on an 8x8 chessboard such that no two queens can attack each other (i.e. share the same row, column, or diagonal). Please introduce a solution to use genetic algorithm to solve the game. a. Please explain the encoding of the state for genetic algorithm (i.e., the representation of the chromosome). Show at least one state and the corresponding encoding [0.5 pt] b. Explain the fitness function, the cross over, and the mutation process, respectively [0.5 pt]. For all programming tasks, please submit the Notebook as html or pdf files for grading (your submission must include scrips/code and the results of the script). For each subtask, please use task description (requirement) as comments, and report your coding and results in following format: 10. [1 pt + 1 Extra credit] The “Heuristic Search to Play Maze [Notebook, html]” posted on Canvas shows a Maze game using A-Star Search (AStar), Greedy Best First (GBF) and Uniform Cost Search (UCS) (using “AStar”, “GBF”, or “UCS” as parameters). Use Notebook as the skeleton code, validate and compare following settings and results. a. Using Figure 5 as the game field, and set initial state as [0, 0] and goal state as [9, 9]. Use A-Star Search (AStar), Greedy Best First (GBF) and Uniform Cost Search (UCS) to find path from initial state to goal state, respectively. Report path of each method [0.25 pt], and explain which method is optimal/not optimal, why? [0.25 pt]. b. What is advantage of AStar search, comparing to greedy best first search (GBF) and Uniform Cost Search [0.25 pt] c. What is advantage of Greedy Best First search, comparing to A-Star search (AStar) and Uniform Cost Search [0.25 pt] d. Bonus Question [1 extra credit]. Based on the randomly generated board in the program, revise the code to visually show generated nodes (color nodes in blue), expanded nodes (color nodes in brown), and the final discovered path from source to the goal node (color path in red). Your code should color all nodes and path as shown in the original board layout. Figure 5 11. [1 pt] The “Local Search N Queens [Notebook, html]” posted on Canvas shows examples of using local search, including hill-climbing Search (HC) and Simulated Annealing (SA) to solve N-Queens problem. Use Notebook as the skeleton code, validate and compare following settings and results. a. Set number of questions (N) as 8, 16, 32, 64, respectively. Repeat hill-climbing search (HC) and simulated annealing (SA) 10 times for each N values, calculate average runtime and success rates (1 divided by number of repetitions before success). Explain how HC and SA behave in terms of runtime and success rates. [0.25 pt] b. Compare costs plots (which show the costs, number of attacked pairs, with respect to the board updating) between HC and SA, explain why plot from HC is monotonically decreasing, whereas the plot from SA is going up and down [0.25] c. For simulated annealing method (SA), fix the number of Queen to d. Explain why SA is better local search method, in general, than HC [0.25] 12. [1 pt] The Genetic Algorithm N Queens [Notebook, html] posted on Canvas shows example of using genetic algorithm to solve N-Queens problem. Use Notebook as the selection code, answer following questions, and implement respective tasks. a. For the same number of Queens (E.g., N=16), comparing speed between hill-climbing vs. genetic algorithm, explain why genetic algorithm is much slower than hill-climbing algorithm [0.25 pt] b. One problem of genetic algorithm is that the cross-over and mutation process may generate off-spring whose genetic code is not a permutation (i.e., a clear attack case to the N-Queens) problem. For example, genetic code “23813754” is not a permutation, because there are two queens in a row (or column) [there are two “3”], and it also misses 8. Propose a solution to generate off-spring whose genetic code is a permutation [0.25] c. Implement your algorithm and compare its performance vs. the original genetic algorithm to solve N=16 queens problem (repeat 5 times and report average runtime). [0.5 pt] _1599286279.unknown _1599286281.unknown _1630908512.unknown _1630908614.unknown _1599286280.unknown _1599286277.unknown _1599286278.unknown _1599286276.unknown