[SOLVED] CMSC421- Project 2: Route-Finding for an Unreliable Vehicle

Description

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 unreliable
  • May 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 line
  • OK 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 z⁰ = (u⁰,v⁰), where

u⁰ ∈{u, u ± 1, u ± 2},

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

• If z⁰ 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 p⁰ = p + z⁰ + e = (x + u⁰ + q, y + v⁰ + r)
• New state s⁰ = (p⁰,z⁰)

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

• You choose z₃ = z₂ + (1,0) = (1,2)
• Control error e₃ = (0,1)
• New location p₃ = p₂ + z₃ + e₃

= (5,8) + (1,2) + (0,1)

= (6,11)

• New state s₃ = (p₃,z₃) = ((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 z₄ = z₃ + (1,−1) = (2,1)
• Control error e₄ = (−1,1)
• New location p₄ = p₃ + z₄ + e₄

= (6,11) + (2,1) + (−1,1)

= (7,13)

• New state s₄ = (p₄,z₄) = ((7,13),(2,1)) 4 = ((7,13),(2,1)) p4, z4
• You choose z₅ = z₄ + (1,−1) = (3,0)
• Control error e₅ = (1,1)
• New location p₅ = p₄ + z₅ + e₅

= (7,13) + (3,0) + (1,1)

= (11,14)

• New state s₅ = (p₅,z₅) = ((11,14),(3,0))
• Trajectory is unsafe
  • Would have crashed if e₅ 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 stop
  • Last 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 move
  • as in chess, checkers, or go

How to do it

• One possibility: alpha-beta game-tree search
  • Limited-depth search, static evaluation function
• Another possibility: Monte Carlo rollouts
  • Problem: 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 rollouts
  • Generate 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 program
  • It 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 useful
  • You’ll need to write a game-tree-search algorithm and/or a Monte Carlo rollout algorithm
• You’ll need a heuristic function
  • You 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