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 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 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
Reviews
There are no reviews yet.