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 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 z_i = (u_i,v_i), where

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₀ = (4,5) z₀ = (0,0) s₀ = (p₀,z₀) = ((4,5),(0,0))
• First move:

z₁ = (0,0) + (1,1) = (1,1) p₁ = (4,5) + (1,1) = (5,6) s₁ = ((5,6), (1,1))

• Second move:

z₂ = (1,1) + (−1,1) = (0,2) p₂ = (5,6) + (0,2) = (5,8) s₂ = ((5,8), (0,2))

• Third move:

z₃ = (0,2) + (1,0) = (1,2) p₃ = (5,8) + (1,2) = (6,10) s₃ = ((6,10), (1,2))

Walls

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

I p = (x,y), q = (x⁰,y⁰)

• 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)
  • pi−1 = (xi−1,yi−1)

I p_i = (x_i,y_i)

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

• Example:

m₁ = ((4,5), (5,6)) m₂ = ((5,6), (5,8)) m₃ = ((5,8), (6,10)) m₄ = ((6,10), (8,12))

• path: list of locations [p₀,p₁,p₂,…,p_n]
  • represents sequence of moves (p₀,p₁), (p₁,p₂), (p₂,p₃), ,…, (p_n−1,p_n) 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),(q⁰,r⁰))

I always horizontal or vertical

• Want to reach the finish line with as few moves as possible
• Find a path [p₀,p₁,…,p_n] I p_n must be on the finish line
• ∃t, 0 ≤ t ≤ 1, such that p_n = t(q,r) + (1 − t)(q⁰,r⁰)
  • Final velocity must be (0,0)
• Thus p_n−₁ = 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₁x + b₁; y = m₂x + b₂

I If m₁ = m₂ and b₁ 6= b₂ then parallel, don’t intersect

I If m₁ = m₂ and b₁ = b₂ then collinear ⇒ check for overlap

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

I If m₁ 6= m₂ 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₁,s₂,…,s_n]

• each s_i 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