CMSC421- Project 1: Vehicle Route-Finding Solved

Problem domain
•          Modified version of Racetrack I Invented in early 1970s

I          played by hand on graph paper

•         2-D polygonal region

I          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

I          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)

I          location pi−1 = (xi−1,yi−1), nonnegative integers

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

•         To move the vehicle

I          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)

I          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]

I          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:

I          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)

I          Final velocity must be (0,0)

•           Thus pn−1 = 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 tdraw.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

•              racetrack.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)

I          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:

I          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
•         racetrack.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

I          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

I          Warning: I don’t advise doing this one

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