# CMSC421 Project 1-Vehicle Route-Finding Solved

30.00 \$

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . ` zip` solution files instantly, after Payment

5/5 - (1 vote)

1

# Problem domain

• Modified version of Racetrack I Invented in early 1970s
• played by hand on graph paper
• 2-D polygonal region
• Inside are a starting point, finish line, maybe obstacles
• All walls are straight lines
• All coordinates are nonnegative integers
• Robot vehicle begins at starting point, can make certain kinds of moves
• Want to move it to the finish line as quickly as possible I Without crashing into any walls
• Need to come to a complete stop on the finish line

# Moving the vehicle

• Before the i’th move, current state is si−1 = (pi−1,zi−1)
• location pi−1 = (xi−1,yi−1), nonnegative integers

I velocity zi−1 = (ui−1,vi−1), integers

• To move the vehicle
• First choose a new velocity zi = (ui,vi), where
 ui ∈{ui−1 − 1, ui−1, ui−1 + 1}, (1) vi ∈{vi−1 − 1, vi−1, vi−1 + 1}. (2)

I New location:        pi = (xi−1 + ui,yi−1 + vi)

I New state:      si = (pi,zi)

Example

• Initial state: p0 = (4,5) z0 = (0,0) s0 = (p0,z0) = ((4,5),(0,0))
• First move:

z1 = (0,0) + (1,1) = (1,1) p1 = (4,5) + (1,1) = (5,6) s1 = ((5,6), (1,1))

• Second move:

z2 = (1,1) + (−1,1) = (0,2) p2 = (5,6) + (0,2) = (5,8) s2 = ((5,8), (0,2))

• Third move:

z3 = (0,2) + (1,0) = (1,2) p3 = (5,8) + (1,2) = (6,10) s3 = ((6,10), (1,2))

# Walls

• edge: a pair of points (p,q)

I p = (x,y), q = (x0,y0)

• coordinates are nonnegative integers
• wall: an edge that the vehicle can’t cross
• List of walls in the example:

[((0,0),(10,0)), ((10,0),(10,10)), ((10,10),(20,10)), ((20,10),(30,0)), ((30,0),(30,10)), ((30,10),(10,20)),

((10,20),(0,20)),    ((0,20),(0,0)),      ((3,14),(10,14)),

((10,14),(10,16)), ((10,16),(3,16)), ((3,16),(3,14))]

# Moves and paths

• move: an edge m = (pi−1,pi)
• pi−1 = (xi−1,yi−1)

I pi = (xi,yi)

I represents change in location from time i − 1 to time i

• Example:

m1 = ((4,5), (5,6)) m2 = ((5,6), (5,8)) m3 = ((5,8), (6,10)) m4 = ((6,10), (8,12))

• path: list of locations [p0,p1,p2,…,pn]
• represents sequence of moves (p0,p1), (p1,p2), (p2,p3), ,…, (pn−1,pn) I Example: [(4,5), (5,6), (5,8), (6,10), (8,12)]
• If a move or path intersects a wall, it crashes, otherwise it is safe

# Objective

• Finish line:
• an edge f = ((q,r),(q0,r0))

I always horizontal or vertical

• Want to reach the finish line with as few moves as possible
• Find a path [p0,p1,…,pn] I pn must be on the finish line
• t, 0 ≤ t ≤ 1, such that pn = t(q,r) + (1 − t)(q0,r0)
• Final velocity must be (0,0)
• Thus pn1 = pn

Example:      [(4,5), (5,6), (5,8), (6,10), (8,12), (11,13), (15,13),

(19,12), (22,11), (24,10), (25,9), (25,8), (25,8)]

# Things I’ll provide

I’ll post a zip archive that includes the following:

I fsearch.py – domain-independent forward search algorithm

• can do depth first, best first, uniform cost, A*, and GBFS
• has hooks for calling a drawing package to draw search spaces I py – code to draw search spaces for racetrack problems

I racetrack.py – code to run fsearch.py on racetrack problems

I sample probs.py – Some racetrack problems I created by hand

I make random probs.py – Code to generate random racetrack problems

• not very good; we probably won’t use it

I sample heuristics.py – Some heuristic functions for Racetrack problems

I nmoves.py – An admissible heuristic function for Racetrack problems

I run tests.bash – a customizable shell script to run experiments

• you must customize it in order to use it

Here are some details

# fsearch.py

Domain-independent forward-search algorithm

I Implementation of Graph-Search-Redo

• main(s0,next states,goal test,strategy, h=None,verbose=2,draw edges=None) I s0 – initial state

I next states(s) – function that returns the possible next states after s

I goal test(s) – function that returns True if s is a goal state, else False

I strategy – one of ‘bf’, ‘df’, ‘uc’, ‘gbf’, ‘a*’

I h(s) – heuristic function, should return an estimate of h(s)

I verbose – one of 0, 1, 2, 3, 4

• how much information to print out (see documentation in the file)

I draw edges – function to draw edges in the search space

# racetrack.py

Code to run fsearch.main on racetrack problems

• main(problem,strategy,h,verbose=0,draw=0,title=”)

I problem – [s0, finish line, walls]

I strategy – one of ‘bf’, ‘df’, ‘uc’, ‘gbf’, ‘a*’

I h(s,f,w) – heuristic function for racetrack problems

• s = state, f = finish line, w = list of walls
• py converts this to the h(s) function that fsearch.main needs

I verbose – one of 0, 1, 2, 3, 4 (same as for fsearch.py)

I draw – either 0 (draw nothing) or 1 (draw problems, node expansions, solutions)

I title – a title to use at the top of the graphics window

• default is the names of the strategy and heuristic
• Some subroutines that may be useful

• intersect(e1,e2) returns True if edges e1 and e2 intersect, False otherwise
 intersect([(0,0),(1,1)], [(0,1),(1,0)]) returns True intersect([(0,0),(0,1)], [(1,0),(1,1)]) returns False intersect([(0,0),(2,0)], [(0,0),(0,5)]) returns True intersect([(1,1),(6,6)], [(5,5),(8,8)]) returns True intersect([(1,1),(5,5)], [(6,6),(8,8)]) returns False

Basic idea (except for some special cases)

I Suppose e1), e2

I Calculate the lines that contain the edges

• y = m1x + b1; y = m2x + b2

I If m1 = m2 and b1 6= b2 then parallel, don’t intersect

I If m1 = m2 and b1 = b2 then collinear ⇒ check for overlap

• Does either edge have an endpoint that’s inside the other edge?

I If m1 6= m2 then calculate the intersection point p

• The edges intersect if they both contain p
• crash(e,walls)
• e is an edge
• walls is a list of walls

I True if e intersects at least one wall in walls, else False

• Example:

crash([(8,12),(10,13)],walls) returns False crash([(8,12),(9,14)],walls) returns True

• children(state,walls)
• state, list of walls

I Returns a list [s1,s2,…,sn]

• each si is a state that we can move to from state without crashing
• Example:
• current state is ((8,12),(2,2))

I 9 possible states, 5 of them crash into the obstacle

I children(((8,12),(2,2)), walls) returns

[((9,13),(1,1)), ((10,13),(2,1)), ((11,13),(3,1), ((11,14),(3,2))]

# tdraw.py

• py draws search search graphs using Python’s turtle graphics I You won’t interact with turtle graphics directly
• In most cases it should run with no problem
• If it doesn’t:

I If not, probably you can install Tk on your computer and re-install Python

I If that doesn’t work, you can run racetrack.main with draw = 0

# sample heuristics.py

Three heuristic functions for the Racetrack domain:

• h edist(s,f,walls) returns Euclidean distance from s to the goal, ignoring walls

I Not admissible, but finds near-optimal solutions

I Problems

• can go in the wrong direction because it ignores walls
• can overshoot because it ignores the number of moves needed to stop
• h esdist(s,f,walls) is a modified version of h edist I includes an estimate of how many moves it will take to stop
• avoids overshooting

I still can go in the wrong direction because it ignores walls

sample heuristics.py (continued)

• h walldist(s,f,walls):

I The first time it’s called:

• For each gridpoint that’s not inside a wall, cache a rough estimate of the distance to the finish line
• Breadth-first search backwards from the finish line, one gridpoint at a time

I On all subsequent calls

• Retrieve the cached value
• Add an estimate of how many moves needed to stop

# nmoves.py

Another heuristic function:

• h nmoves(s,f,walls):

I Calculates how many moves would be needed to reach the finish line if there were no walls

I It’s admissible, but I don’t recommend using it

• A* finds optimal solutions (vs. near-optimal with h esdist), but does about 10 times as many node expansions
• With h esdist, GBFS expands about the same number of nodes, and h esdist has lower overhead

– simple calculations vs. a recursive computation

• Like h esdist, h nmoves ignores walls, so can go in the wrong direction

# What to do

• Write a better heuristic function than h walldist
• Don’t just make minor modifications to h walldist, you need to write something of your own
• Look for something that works just as well, but runs faster I Avoid caching distances for all the gridpoints I Some of them don’t matter; others don’t matter much I How to tell which ones?
• Experiment to see what works best
• Another possibility might be to try improving the heuristic estimates so that A* expands fewer nodes or GBFS finds shorter solutions
• Warning: I don’t advise doing this one

I I doubt you’ll be able to get significant improvements