1 Instructions We consider a maze under a windy condition as shown in the following figure. We assume that the wind comes from the south and the cost of one step for the agent is defined as follows: 1 for moving northward; 2 for moving westward or eastward; 3 for moving southward. We assume that the square labeled with O is the starting square and the goal square is labelled with G and all dark-shaded squares and all edges are obstacles. Depth-First Search We consider the graph-search version, i.e., using explored set to void redundant paths. A* Search We use a modified Manhattan distance used in class as the heuristic function h(n) by considering the windy situation. For example, for the start node, the agent has to move at least 3 steps eastward and 3 steps southward in order to reach the goal. Therefore, we have h(n) = 3* 3+3* 2 = 15 at the start node. We use a label we did in class to indicates the order of choosing the corresponding unlabeled square and adding it to the frontier. To break tier for unlabeled squares (expanding children nodes), use this order: first westward; then northward; then eastward; then southward. To break tier for labeled squares (picking one child node to expand), the smallest label is picked first. Follow the same way as done in the class to show the search steps with labels inside circles for the following search algorithms: Depth-first search and A* search ignoring the subscripts which we use in class). Your outcome should be displayed as these: DFS: 01 00 04 03 06 05 07 ## 08 09 10 11 02 ## ## ## 13 12 26 ## 28 27 15 14 25 24 ## ## ## 29 ## ## ## 16 17 23 22 21 20 19 18 01 00 02 04 07 09 11 05 03 ## ## ## ## 13 08 06 ## 25 ## 16 10 ## ## 23 26 ## 19 12 14 17 20 ## ## 22 15 18 21 24 2 Submission Form a group on Canvas if you want to work with another student. In your report, please provide the screenshots of all outcomes. Each screenshot should include your usernames and the current time, which show that you did it by yourselves. The report should be written in a ".docx", ".doc", or ".pdf format. Submit the report and the source code to the assignment folder P1 on Canvas. Any compression file format such as .zip is not permitted. 1 Instructions We consider a maze under a windy condition as shown in the following figure. We assume that the wind comes from the south and the cost of one step for the agent is defined as follows: 1 for moving northward; 2 for moving westward or eastward; 3 for moving southward. We assume that the square labeled with O is the starting square and the goal square is labelled with G and all dark-shaded squares and all edges are obstacles. Depth-First Search We consider the graph-search version, i.e., using explored set to void redundant paths. A* Search We use a modified Manhattan distance used in class as the heuristic function h(n) by considering the windy situation. For example, for the start node, the agent has to move at least 3 steps eastward and 3 steps southward in order to reach the goal. Therefore, we have h(n) = 3* 3+3* 2 = 15 at the start node. We use a label we did in class to indicates the order of choosing the corresponding unlabeled square and adding it to the frontier. To break tier for unlabeled squares (expanding children nodes), use this order: first westward; then northward; then eastward; then southward. To break tier for labeled squares (picking one child node to expand), the smallest label is picked first. Follow the same way as done in the class to show the search steps with labels inside circles for the following search algorithms: Depth-first search and A* search ignoring the subscripts which we use in class). Your outcome should be displayed as these: DFS: 01 00 04 03 06 05 07 ## 08 09 10 11 02 ## ## ## 13 12 26 ## 28 27 15 14 25 24 ## ## ## 29 ## ## ## 16 17 23 22 21 20 19 18 01 00 02 04 07 09 11 05 03 ## ## ## ## 13 08 06 ## 25 ## 16 10 ## ## 23 26 ## 19 12 14 17 20 ## ## 22 15 18 21 24 2 Submission Form a group on Canvas if you want to work with another student. In your report, please provide the screenshots of all outcomes. Each screenshot should include your usernames and the current time, which show that you did it by yourselves. The report should be written in a ".docx", ".doc", or ".pdf format. Submit the report and the source code to the assignment folder P1 on Canvas. Any compression file format such as .zip is not permitted