## Description

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*s**i*âˆ’1 = (*p**i*âˆ’1*,z**i*âˆ’1)- location
*p**i*âˆ’1 = (*x**i*âˆ’1*,y**i*âˆ’1), nonnegative integers

- location

I velocity *z**i*âˆ’1 = (*u**i*âˆ’1*,v**i*âˆ’1), integers

- To move the vehicle
- First choose a new velocity
*z*= (_{i }*u*), where_{i},v_{i}

- First choose a new velocity

ui âˆˆ{uiâˆ’1 âˆ’ 1, uiâˆ’1, uiâˆ’1 + 1}, |
(1) |

vi âˆˆ{viâˆ’1 âˆ’ 1, viâˆ’1, viâˆ’1 + 1}. |
(2) |

I New location:Â Â Â Â Â Â Â *p _{i }*= (

*x*

_{i}_{âˆ’1 }+

*u*

_{i},y_{i}_{âˆ’1 }+

*v*)

_{i}I New state:Â Â Â Â Â *s _{i }*= (

*p*)

_{i},z_{i}Example

- Initial state:
*p*_{0 }= (4*,*5)*z*_{0 }= (0*,*0)*s*_{0 }= (*p*_{0}*,z*_{0}) = ((4*,*5)*,*(0*,*0)) - First move:

*z*_{1 }= (0*,*0) + (1*,*1) = (1*,*1) *p*_{1 }= (4*,*5) + (1*,*1) = (5*,*6) *s*_{1 }= ((5*,*6)*, *(1*,*1))

- Second move:

*z*_{2 }= (1*,*1) + (âˆ’1*,*1) = (0*,*2) *p*_{2 }= (5*,*6) + (0*,*2) = (5*,*8) *s*_{2 }= ((5*,*8)*, *(0*,*2))

- Third move:

*z*_{3 }= (0*,*2) + (1*,*0) = (1*,*2) *p*_{3 }= (5*,*8) + (1*,*2) = (6*,*10) *s*_{3 }= ((6*,*10)*, *(1*,*2))

# Walls

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

I *p *= (*x,y*), *q *= (*x*^{0}*,y*^{0})

- 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*= (*p*_{i}_{âˆ’1}*,p*)_{i}*p**i*âˆ’1 = (*x**i*âˆ’1*,y**i*âˆ’1)

I *p _{i }*= (

*x*)

_{i},y_{i}I represents change in location from time *i *âˆ’ 1 to time *i*

- Example:

*m*_{1 }= ((4*,*5)*, *(5*,*6)) *m*_{2 }= ((5*,*6)*, *(5*,*8)) *m*_{3 }= ((5*,*8)*, *(6*,*10)) *m*_{4 }= ((6*,*10)*, *(8*,*12))

*path*: list of locations [*p*_{0}*,p*_{1}*,p*_{2}*,…,p*]_{n}- represents sequence of moves (
*p*_{0}*,p*_{1})*,*(*p*_{1}*,p*_{2})*,*(*p*_{2}*,p*_{3})*, ,…,*(*p*_{n}_{âˆ’1}*,p*) I Example: [(4_{n}*,*5)*,*(5*,*6)*,*(5*,*8)*,*(6*,*10)*,*(8*,*12)]

- represents sequence of moves (
- If a move or path intersects a wall, it
*crashes*, otherwise it is*safe*

# Objective

*Finish line*:- an edge
*f*= ((*q,r*)*,*(*q*^{0}*,r*^{0}))

- an edge

I always horizontal or vertical

- Want to reach the finish line with as few moves as possible
- Find a path [
*p*_{0}*,p*_{1}*,…,p*] I_{n}*p*must be on the finish line_{n } - âˆƒ
*t,*0 â‰¤*t*â‰¤ 1, such that*p*=_{n }*t*(*q,r*) + (1 âˆ’*t*)(*q*^{0}*,r*^{0})- Final velocity must be (0
*,*0)

- Final velocity must be (0
- Thus
*p*âˆ’_{n}_{1 }=*p*_{n}

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*=*m*_{1}*x*+*b*_{1};*y*=*m*_{2}*x*+*b*_{2}

I If *m*_{1 }= *m*_{2 }and *b*_{1 }6= *b*_{2 }then parallel, donâ€™t intersect

I If *m*_{1 }= *m*_{2 }and *b*_{1 }= *b*_{2 }then collinear â‡’ check for overlap

- Does either edge have an endpoint thatâ€™s inside the other edge?

I If *m*_{1 }6= *m*_{2 }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 [*s*_{1}*,s*_{2}*,…,s _{n}*]

- each
*s*is a state that we can move to from state without crashing_{i } - Example:
- current state is ((8
*,*12)*,*(2*,*2))

- current state is ((8

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