Artificial Intelligence

Machine Problem $1$ A$*$ for Solving a Maze

give a unique solution for this problem without plagarism with step by step clear explaination

IMPORTANT NOTICE: You do not have permission to share the description of this assignment or discuss it with anyone outside the

class. Also, you cannot share your code $($or solution in general$)$ with anyone, nor can you ask anyone for the code or solution.

Failure to adhere to this policy will result in a zero grade for the assignment and may result in a dismissal from Lewis University.

Introduction

For this assignment, you will implement the A$*$ algorithm to find an exit out of a maze. Your goal is to return the instructions for

solving the maze and show the configuration after each move. The maze is a rectangular grid containing passageways, walls, and a

single exit point that the agent must reach. The agent can move in four directions: 'down', 'right', 'left', and $\text{'}$up$\text{'},$ but cannot move to

a location containing a wall.

Requirements

For this assignment, you are given base Python $3$ code that contains a part of the implementation. Download this code first, and

then do the following:

$1.$ Determine a heuristic function that can be used with A$*$ to solve the search problem. Make sure the A$*$ heuristic satisfies

the admissibility and consistency properties.

$2.$ Modify that code so it solves the maze problem using the A$*$ algorithm.

$3.$ Modify the print statements from the base code to include your info in the printed heading.

$4.$ Run the code and verify it finds the correct path and generates the right number of states visited.

Additional Requirements

$1.$ The name of your source code file should be mp$1.$py$.$ All your code should be within a single file.

$2.$ You can only import numpy, queue, and heapq packages.

$3.$ Your code should follow good coding practices, including good use of whitespace and use of both inline and block

comments.

$4.$ You need to use meaningful identifier names that conform to standard naming conventions.

$5.$ At the top of each file, you need to put in a block comment with the following information: your name, date, course name,

semester, and assignment name.

$6.$ The output should exactly match the sample output shown on the last page.

What to Turn In

You will turn in the single mp$1.$py file using BlackBoard.

#$!/$usr$/$bin$/$env python$3$

# $-*-$ coding: utf$-8-*-$

$"""$

@author: szczurpi

This program implements a search algorithm for solving a grid maze

It allows moves in $4$ directions $(1$ point cost for each move$)$

$"""$

import numpy as np

import queue # Needed for frontier queue

from heapq import heapify

class MazeState$()$:

$"""$ Stores information about each visited state within the search $"""$

# Define constants

SPACE $=0$

WALL $=1$

EXIT $=2$

START $=(1,1)$

END $=(9,1)$

maze $=$ np$.$array$([$

$[0,1,1,0,1],$

$[0,0,0,0,1],$

$[0,0,1,1,1],$

$[1,0,0,0,0],$

$[1,1,0,1,0],$

$[1,0,0,1,0],$

$[1,0,0,1,0],$

$[1,0,1,1,0],$

$[1,0,0,0,0],$

$[0,0,1,1,1]],$ dtype$=$np$.$int$32)$

maze$[$END$]=$ EXIT

def $\_\_$init$\_\_($self$,$ conf$=$START, g$=0,$ pred$\_$state$=$None, pred$\_$action$=$None$)$:

$"""$ Initializes the state with information passed from the arguments $"""$

self.pos $=$ conf # Configuration of the state $-$ current coordinates

self.gcost $=$ g # Path cost

self.pred $=$ pred$\_$state # Predecesor state

self.action$\_$from$\_$pred $=$ pred$\_$action # Action from predecesor state to current state

### TODO $-$ heuristic value for A$*/$greedy search ###

def $\_\_$hash$\_\_($self$)$:

$"""$ Returns a hash code so that it can be stored in a set data structure $"""$

return self.pos.$\_\_$hash$\_\_()$

def $\_\_$eq$\_\_($self$,$ other$)$:

$"""$ Checks for equality of states by positions only $"""$

### TODO ###

def $\_\_$lt$\_\_($self$,$ other$)$:

$"""$ Allows for ordering the states by the path $($g$)$ cost $"""$

### TODO ###

def $\_\_$str$\_\_($self$)$:

$"""$ Returns the maze representation of the state $"""$

a $=$ np$.$array$($self$.$maze$)$

a$[$self$.$pos$]=4$

return np$.$str$($a$)$

def is$\_$goal$($self$)$:

$"""$ Returns true if current position is same as the exit position $"""$

### TODO ###

move$\_$num $=0$ # Used by show$\_$path$()$ to count moves in the solution path

def show$\_$path$($self$)$:

$"""$ Recursively outputs the list of moves and states along path $"""$

if self.pred is not None:

self.pred.show$\_$path$()$

if MazeState.move$\_$num$==0$:

print$(\text{'}$START$\text{'})$

else:

print$(\text{'}$Move$\text{'},$MazeState.move$\_$num, 'ACTION:$\text{'},$ self.action$\_$from$\_$pred$)$

MazeState.move$\_$num $=$ MazeState.move$\_$num $+1$

print$($self$)$

def can$\_$move$($self$,$ move$)$:

$"""$ Returns true if agent can move in the given direction $"""$

### TODO ###

def gen$\_$next$\_$state$($self$,$ move$)$:

$"""$ Generates a new M