Homework #1 Due Dates: Task1: 09/28/20, 9PM; Task2: 10/7/2020, 9PM Submit the zip files on Canvas by the deadlines 1. Programming Assignment: The goal of this assignment is to develop a program, in...

Python A* search


Homework #1 Due Dates: Task1: 09/28/20, 9PM; Task2: 10/7/2020, 9PM Submit the zip files on Canvas by the deadlines 1. Programming Assignment: The goal of this assignment is to develop a program, in JAVA, C++, or PYTHON, that implements search algorithms for solving a seventeen-tile puzzle (6 rows X 3 columns). The search-based solution must follow the strategy of using a priority queue for the Open List and another data structure of your choice for the Closed List. The main steps of the search algorithm must be the same as described in class, that is, a repetition of the following steps until either a path to the Goal State is discovered, or you determine that enough effort has been spent a path to thee goal node may not exist. 5 19 7 9 11 10 14 6 16 12 2 4 15 1 3 8 13 [5 19 7 9 11 10 14 6 16 16 12 0 2 4 15 1 3 8 13] Notice that the blank slot on the board is represented by a ‘0’ in the State-vector. · The g(n) value for the state. · The h(n) value for the state · The f(n) (= g(n)+h(n)) value of the state. · Priority value assigned to this state by your algorithm. It could be the level number in the search tree, g(n), h(n), or f(n), or any other value depending on the search algorithm being used. The characteristics of your program must include the following: a. The program takes as inputs two vectors, the first one describing a start state and the second one describing a goal state. For example, the input to the program may look like: [5 15 7 8 9 11 10 3 12 0 2 13 4 14 1 6 16 17] [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 17 16] b. The output of the program must include the following items: i. TASK-1: A* algorithm using h1 heuristic (described in (d) below): 1. A sequence of State descriptions in which the first state is the start (or the goal) state and the last state is the goal (or the start) state as obtained by the A* algorithm using the h1 heuristic (described below). Show the details of each state description including the ID’s, g(n), h(n) and f(n) values. 2. Length of the path between the start and the goal state in terms of the number of moves; the count of nodes added to the Open List during the search process; and the count of nodes added to the Closed List during the search process (A* Search using heuristic h1). c. The heuristic function h1 for the A* search is as follows: The estimated cost of taking a board B to the goal state G is the number of tiles in B that are not in the correct location as required by G. d. Make sure that your program has the provision to suspend the search process if a solution has not been found after significant resources (time or memory) have been exhausted. The following items, bundled in a single zip file, must be submitted on Blackboard in response to this assignment: a. Source code file for your program, named ’SourceCodeFile’.___ Your program must be written in one of these three languages: JAVA, PYTHON, or C++. b. A README.pdf file listing the command line instructions needed for (i) compiling your program, and (ii) executing your program with two 1X20 vectors as inputs. c. Output of your program obtained for the following two cases, included in a file named:

.OutPutFile.pdf: i. [1 13 3 5 6 9 11 0 8 12 14 10 7 16 15 4 17 2] [1 13 3 5 6 9 11 14 8 12 16 10 7 17 15 0 4 2] ii. [1 13 3 5 17 9 11 0 8 12 14 10 7 16 15 4 6 2] [5 1 3 13 17 9 11 0 8 12 14 10 7 16 15 4 6 2] BFS SEARCH CODE ALREADY DONE: # Raja Vaze # BFS Algorithm - 17 Tile Puzzle import numpy as np import time class Node: # Constructor def __init__(self, state, parent, action, depth, step_cost, path_cost, heuristic_cost): self.state = state self.parent = parent # Parent node self.action = action # Action self.depth = depth # Node level self.step_cost = step_cost # g(n), cost to take step self.path_cost = path_cost # f(n), cost to reach maybe self.heuristic_cost = heuristic_cost # h(n),cost from current to goal node # Child Nodes self.move_up = None self.move_down = None self.move_left = None self.move_right = None # Functions which test move right, left, up and down def try_move_down(self): zero_index = [i[0] for i in np.where(self.state == 0)] if zero_index[0] == 0: return False else: up_value = self.state[zero_index[0] - 1, zero_index[1]] # Upper tile value new_state = self.state.copy() new_state[zero_index[0], zero_index[1]] = up_value new_state[zero_index[0] - 1, zero_index[1]] = 0 return new_state, up_value def try_move_right(self): zero_index = [i[0] for i in np.where(self.state == 0)] if zero_index[1] == 0: return False else: left_value = self.state[zero_index[0], zero_index[1] - 1] # Left Tile Value new_state = self.state.copy() new_state[zero_index[0], zero_index[1]] = left_value new_state[zero_index[0], zero_index[1] - 1] = 0 return new_state, left_value def try_move_up(self): zero_index = [i[0] for i in np.where(self.state == 0)] if zero_index[0] == 5: return False else: lower_value = self.state[zero_index[0] + 1, zero_index[1]] # Lower Tile Value new_state = self.state.copy() new_state[zero_index[0], zero_index[1]] = lower_value new_state[zero_index[0] + 1, zero_index[1]] = 0 return new_state, lower_value def try_move_left(self): zero_index = [i[0] for i in np.where(self.state == 0)] if zero_index[1] == 2: return False else: right_value = self.state[zero_index[0], zero_index[1] + 1] # Right Tile Value new_state = self.state.copy() new_state[zero_index[0], zero_index[1]] = right_value new_state[zero_index[0], zero_index[1] + 1] = 0 return new_state, right_value # Unused Functions def get_h_cost(self, new_state, goal_state, heuristic_function, path_cost, depth): if heuristic_function == 'num_misplaced': return self.h_misplaced_cost(new_state, goal_state) elif heuristic_function == 'manhattan': return self.h_manhattan_cost(new_state, goal_state) elif heuristic_function == 'fair_manhattan': return self.h_manhattan_cost(new_state, goal_state) - path_cost + depth def h_misplaced_cost(self, new_state, goal_state): cost = np.sum(new_state != goal_state) - 1 if cost > 0: return cost else: return 0 def h_manhattan_cost(self, new_state, goal_state): current = new_state goal_position_dic = {1: (0, 0), 13: (0, 1), 3: (0, 2), 5: (1, 0), 6: (1, 1), 9: (1, 2), 11: (2, 0), 14: (2, 1), 8: (2, 2), 12: (3, 0), 16: (3, 1), 10: (3, 2), 7: