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

Description

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 Do your computer and your Python installation have Tk support?

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