CMSC421- Project 2: Route-Finding for an Unreliable Vehicle Solved

Another kind of racetrack problem

Robot vehicle, starting point, finish line, walls are the same as in Project 1
Differences:

Vehicle’s control system is unreliableMay move to a slightly different location than you intended
I up to 1 unit in any direction

You can make bigger changes in velocity I Up to 2 units in any direction
Don’t need to stop exactly on the finish lineOK to stop at distance ≤ 1
Moving the vehicle
Current state s = (p,z)location p = (x,y), nonnegative integers
I velocity z = (u,v), integers

You choose new velocity z0 = (u0,v0), where
u0 ∈{u, u ± 1, u ± 2},

v0 ∈{v, v ± 1, v ± 2}.

If z0 6= (0,0), then the control system may make an error in your position I e = (q,r), where q,r ∈{−1,0,1}
Vehicle moves to location p0 = p + z0 + e = (x + u0 + q, y + v0 + r)
New state s0 = (p0,z0)
 

2 = ((5,8),(0,2)) p2,   z2

You choose z3 = z2 + (1,0) = (1,2)
Control error e3 = (0,1)
New location p3 = p2 + z3 + e3
= (5,8) + (1,2) + (0,1)

= (6,11)

New state s3 = (p3,z3) = ((6,11),(1,2))
The control error doesn’t change velocity, just your position I Unrealistic, but it makes the problems easier to solve
3 = ((6,11),(1,2)) p3,        z3

You choose z4 = z3 + (1,−1) = (2,1)
Control error e4 = (−1,1)
New location p4 = p3 + z4 + e4
= (6,11) + (2,1) + (−1,1)

= (7,13)

New state s4 = (p4,z4) = ((7,13),(2,1)) 4 = ((7,13),(2,1)) p4, z4
You choose z5 = z4 + (1,−1) = (3,0)
Control error e5 = (1,1)
New location p5 = p4 + z5 + e5
= (7,13) + (3,0) + (1,1)

= (11,14)

New state s5 = (p5,z5) = ((11,14),(3,0))
Trajectory is unsafeWould have crashed if e5 were (0,1) or (−1,1)
Ideally, you want a strategy that will always keep you from crashing regardless of what control errors occur
 

Objective
Get to the finish line and stop

I Might not be able to land exactly on the line

I Control errors can prevent that

OK to get to distance ≤ 1
Need to stopLast move needs to have velocity 0, as in Project 1
Want to get there as quickly as possible without crashing, despite control errors
Strategy

Pretend the control system is an opponent that’s trying to make you crash

Choose moves that will keep you from crashing, regardless of what it does
Write a game-playing algorithm to do it move by moveas in chess, checkers, or go
How to do it
One possibility: alpha-beta game-tree searchLimited-depth search, static evaluation function
Another possibility: Monte Carlo rolloutsProblem: randomly generated paths are very unlikely to go to the goal I I don’t think it will work very well
Another idea: biased Monte Carlo rolloutsGenerate paths randomly, but bias the moves toward good evaluation-function values
I How well this will work, I have no idea

No way to guarantee you won’t crash
 

Opponent
We’ll give you a simple opponent programIt will try to make you crash, but won’t be very intelligent about it
Warning: don’t write a program that just tries to take advantage of the dumb opponent!When we grade your program, we’ll use a more intelligent opponent
Need to choose moves that won’t crash, no matter what the opponent does
Other comments
You may use any of the code I gave you for Project 1, and any of the code you developed for Project 1 I You can modify it if you wish
Caveat: most of it won’t be very usefulYou’ll need to write a game-tree-search algorithm and/or a Monte Carlo rollout algorithm
You’ll need a heuristic functionYou can use the one you developed for Project 1
I You can use any of the ones I gave you for Project 1

g., h walldist
Caveat: Will a heuristic function for Project 1 work well as a game-tree-search heuristic?You might need to make modifications