Using this code as a guide:

$"""$

Motion planning on a rectangular grid using A$*$ search

$"""$

from random import random

from random import seed

from queue import PriorityQueue

from copy import deepcopy

class State$($object$)$:

def $\_\_$init$\_\_($self$,$ start$\_$position, goal$\_$position, start$\_$grid$)$:

self.position $=$ start$\_$position

self.goal $=$ goal$\_$position

self.grid $=$ start$\_$grid

self.total$\_$moves $=0$

#$---$ Fill in the rest of the class...

def create$\_$grid$()$:

$"""$

Create and return a randomized grid

$0\text{'}$s in the grid indcate free squares

$1\text{'}$s indicate obstacles

DON'T MODIFY THIS ROUTINE.

DON'T MODIFY THIS ROUTINE.

DON'T MODIFY THIS ROUTINE.

DON'T MODIFY THIS ROUTINE.

ARE YOU MODIFYING THIS ROUTINE?

IF SO$,$ STOP IT$.$

$"""$

# Start with a num$\_$rows by num$\_$cols grid of all zeros

grid $=[[0$ for c in range$($num$\_$cols$)]$ for r in range$($num$\_$rows$)]$

# Put ones around the boundary

grid$[0]=[1$ for c in range$($num$\_$cols$)]$

grid$[$num$\_$rows $-1]=[1$ for c in range$($num$\_$cols$)]$

for r in range$($num$\_$rows$)$:

grid$[$r$][0]=1$

grid$[$r$][$num$\_$cols $-1]=1$

# Sprinkle in obstacles randomly

for r in range$(1,$ num$\_$rows $-1)$:

for c in range$(2,$ num$\_$cols $-2)$:

if random$()<$ obstacle$\_$prob:

grid$[$r$][$c$]=1$;

# Make sure the goal and start spaces are clear

grid$[1][1]=0$

grid$[$num$\_$rows $-2][$num$\_$cols $-2]=0$

return grid

def print$\_$grid$($grid$)$:

$"""$

Print a grid, putting spaces in place of zeros for readability

DON'T MODIFY THIS ROUTINE.

DON'T MODIFY THIS ROUTINE.

DON'T MODIFY THIS ROUTINE.

DON'T MODIFY THIS ROUTINE.

ARE YOU MODIFYING THIS ROUTINE?

IF SO$,$ STOP IT$.$

$"""$

for r in range$($num$\_$rows$)$:

for c in range$($num$\_$cols$)$:

if grid$[$r$][$c$]==0$:

print$(\text{'}\text{'},$ end$=\text{'}\text{'})$

else:

print$($grid$[$r$][$c$],$ end$=\text{'}\text{'})$

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

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

return

def main$()$:

$"""$

Use A$*$ search to find a path from the upper left to the lower right

of the puzzle grid

Complete this method to implement the search

At the end, print the solution state

Each State object has a copy of the grid

When you make a move by generating a new State, put a $*$ on its grid

to show the solution path

$"""$

# Setup the randomized grid

grid $=$ create$\_$grid$()$

print$\_$grid$($grid$)$

# Initialize the starting state and priority queue

start$\_$position $=(1,1)$

goal$\_$position $=($num$\_$rows $-2,$ num$\_$cols $-2)$

start$\_$state $=$ State$($start$\_$position, goal$\_$position, grid$)$

start$\_$state.grid$[1][1]=\text{'}*\text{'}$

# A$*$ priority: implement the Manhattan distance in the State class

priority $=$ start$\_$state.total$\_$moves $+$ start$\_$state.manhattan$\_$distance$()$

queue $=$ PriorityQueue$()$

# Insert as a tuple

# The queue orders elements by the first tuple value

# A call to queue.get$()$ returns the tuple with the minimum first value

queue.put$(($priority$,$ start$\_$state$))$

# Maybe you should use a dictionary to keep track of visited positions?

#$---$ Fill in the rest of the search...

if $\_\_$name$\_\_==\text{'}\_\_$main$\_\_\text{'}$:

seed$(0)$

#$---$ Easy mode

# Global variables

# Saves us the trouble of continually passing them as parameters

num$\_$rows $=8$

num$\_$cols $=16$

obstacle$\_$prob $=\mathrm{.}20$

for trial in range$(5)$:

print$(\text{'}$

$-----$Easy trial $\text{'}+$ str$($trial $+1)+\text{'}-----\text{'})$

main$()$

#$---$ Uncomment the following sets of trials when you're ready

#$---$ Hard mode

num$\_$rows $=15$

num$\_$cols $=30$

obstacle$\_$prob $=\mathrm{.}30$

for trial in range$(5)$:

print$(\text{'}$

$-----$Harder trial $\text{'}+$ str$($trial $+1)+\text{'}-----\text{'})$

###main$()$

#$---$ INSANE mode

num$\_$rows $=20$

num$\_$cols $=60$

obstacle$\_$prob $=\mathrm{.}35$

for trial in range$(5)$:

print$(\text{'}$

$-----$INSANE trial $\text{'}+$ str$($trial $+1)+\text{'}-----\text{'})$

###main$()$

Help code a Python assignment using these guidelines:

Motion planning

Consider a robot planning a path through a grid$-$based world. Its goal is to move from a start square in the upper$-$left to a goal square in the lower$-$right, moving around any obstacles in its way.

$11111111111111111111111111111$

$1**********11$

$111111*11$

$11111***11111111$

$1*1111111111111111$

$1*****1$

$111$

Write a program that uses A$*$ search to find the shortest path from the start to the goal in a randomly generated grid world, or discover that no path exists. Use the Manhattan distance from the current position to the goal square as your heuristic.

Use the motion.py script as a starting point, which includes code to randomly generate ten trial worlds. Your program should print out the solution grid, showing the shortest path in stars, as in the example above, or a message that no path exists if the search fails.