Project 2
RouteFinding for an Unreliable Vehicle
CMSC 421, Fall 2019 Last update October 16, 2019
Due date: November 1
Late date 20 off: November 3
1
Another kind of racetrack problem
Robot vehicle, starting point, finish line, walls are the same as in Project 1
Differences:
1 Vehicles control system is unreliable
Maymovetoaslightlydifferent location than you intended
upto1unitinanydirection
2 You can make bigger changes in velocity
Upto2unitsinanydirection
3 Dont need to stop exactly on the finish line OKtostopatdistance1
20
10
4,
obstac
5
le
0
start
1
0
24,8,
fi
ni
26
sh line
,8
2
0
3
0
2
Moving the vehicle
Currentstatesp,z locationpx,y,
nonnegative integers
velocityzu,v,integers
You choose new velocity z u, v, where
u u, u1, u2, v v, v1, v2.
If z 0, 0, then the control system may make an error in your position
e q,r, where q,r 1,0,1
Vehiclemovestolocationp pze xuq,yvr
New state s p, z
20
obstac
le
10
4,
5
24,8,
26
,8
start
fi
ni
sh line
0
1
0
2
0
3
0
3
obstac
p2
le
5,
8
p1
0
p
0
1
0
24,8,
fi
ni
26
sh line
,8
2
0
3
0
State s2 5, 8, 0, 2 p2, z2
You choose
z3 z2 1,01,2
Control error e3 0, 1
Example
20
10
Newlocationp3 p2z3e3 5, 8 1, 2 0, 1
6, 11
New state s3 p3, z3 6, 11, 1, 2
The control error doesnt change velocity, just your position Unrealistic,butitmakestheproblemseasiertosolve
4
obstac
p2
le
5,
8
0
p
0
p1
1
0
24,8,
fi
ni
26
sh line
,8
2
0
3
0
State s3 6, 11, 1, 2 p3, z3
Example
20
10
You choose
z4 z3 1,12,1
Control error e4 1, 1
Newlocationp4 p3z4e4 6, 11 2, 1 1, 1
7, 13
New state s4 p4, z4 7, 13, 2, 1
5
obstac
p2
le
5,
8
0
p
0
p1
1
0
24,8,
fi
ni
26
sh line
,8
2
0
3
0
State s4 7, 13, 2, 1 p4, z4
Example
20
10
You choose
z5 z4 1,13,0
Control error e5 1, 1
Newlocationp5 p4z5e5 7, 13 3, 0 1, 1
11, 14
New state s5 p5, z5 11, 14, 3, 0
Trajectory is unsafe
Would 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
6
Objective
Get to the finish line and stop Mightnotbeabletoland
exactly on the line
Controlerrorscanpreventthat
OKtogettodistance1 Need to stop
Lastmoveneedstohave velocity 0, as in Project 1
Want to get there as quickly as possible without crashing, despite control errors
20
obstac
le
10
4,
5
24,8,
26
,8
start
fi
ni
sh line
0
1
0
2
0
3
0
7
Strategy
20
obstac
le
10
p
0
24,8,
26
,8
fi
ni
sh line
0
1
0
2
0
3
0
Pretend the control system is an opponent thats trying to make you crash
Choose moves that will keep you from crashing, regardless of what it does
Write a gameplaying algorithm to do it move by move
asinchess,checkers,orgo
8
How to do it
One possibility: alphabeta gametree search
Limiteddepthsearch,staticevaluationfunction
Another possibility: Monte Carlo rollouts
Problem: randomly generated paths are very unlikely to go to the goal Idontthinkitwillworkverywell
Another idea: biased Monte Carlo rollouts
Generatepathsrandomly,butbiasthemovestoward
good evaluationfunction values
Howwellthiswillwork,Ihavenoidea
No way to guarantee you wont crash
9
Opponent
Well give you a simple opponent program
Itwilltrytomakeyoucrash,butwontbeveryintelligentaboutit
Warning: dont write a program that just tries to take advantage of the dumb opponent!
Whenwegradeyourprogram,welluseamoreintelligentopponent
Need to choose moves that wont crash, no matter what the opponent does
10
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
Youcanmodifyitifyouwish
Caveat: most of it wont be very useful
Youllneedtowriteagametreesearchalgorithm andor a Monte Carlo rollout algorithm
Youll need a heuristic function
YoucanusetheoneyoudevelopedforProject1
YoucanuseanyoftheonesIgaveyouforProject1
work well as a gametreesearch heuristic? Youmightneedtomakemodifications
e.g., h walldist
Caveat: Will a heuristic function for Project 1
11
What you need to submit
You need to submit a file called proj2.py containing a program called main
Well give you a game environment for running it
Itwillsimulateturnbyturninteractionswiththeopponent
Ateachturn,itwillrunproj2.mains,f,w
s state, f finish line, w list of walls
Your proj2.main program should print to standard output a sequence of choices for what velocity to use. Each choice should
be a pair of integers u, v followed by a linebreak.
2, 2
1, 3
1, 2
1, 2
Keep searching for better and better recommendations
e.g., iterative deepening, or additional Monte Carlo rollouts
12
More about the game environment
Game environment runs your proj2.main program as a separate process Letsitrunfor5seconds,killsit,readsthelastvelocityitchose
After getting your chosen velocity u, v,
it lets the opponent choose what error to use
e q,r, where q,r 1,0,1
It computes the new state, and checks whether the game has ended
youcrashyoulose
youreachthefinishlineandyourvelocityis0,0youwin
otherwise,gamehasntendedgameenvironmentwillcallyour program again, with the new current state
If
runs your proj2.main program again
the game hasnt ended, it goes to the next turn
13
Files Ill provide
File on Piazza: project2b code.zip
Not project2 code.zip that version had an error in it
sample probs modified version of the test problems from Project 1.
Iremovedormodifiedtheonesthatwereobviouslyunsolvable.
Each problem is a list of the form name, p0, finish, walls
Ifaproblemsdimensionsaresosmallthattheproblemisunsolvable, you can call doublep where p is the problem, to return
a problem in which the x and y dimensions are both doubled.
opponents.py two simple opponent programs. opponent1 tries to head for the wall
opponent0 makes moves at random
By default, env.main uses opponent0
14
Files Ill provide continued
env.py environment for running your proj2.py file.
Heres what env.mainproblem does:
1. If you have a proj2.initialize, it launches proj2.initializes, f, w, waits 5 seconds, and kills the process if it hasnt exited.
Thisissoyoucancomputesomedatatouseinyourproj2.mainprogram
Yourproj2.initializeshouldwritethedatatoafilecalleddata.txt;
otherwise the data will be lost when the process exits
2. It repeats the following steps until you win or lose:
Launchproj2.main,wait5seconds,andkilltheprocess
Readthelastvelocityu,vinchoices.txt.Ifitisntlegal,returnlose
Ifu,v0,0anddistancefromfinishline1,returnwin.
Calltheopponenttoaddanerrortothevelocity
Drawthemoveusingturtlegraphics
Ifthemovecrashesintoawall,returnlose
15
Files Ill provide continued
proj2 example.py a deliberately stupid version of proj2.py
Renameittoproj2.pyifyouwanttouseitwithenv.py.
Iprovideditsoyoucanseehowenv.pyworksbeforeyoustart writing your own proj2.py.
Itcanwinifitslucky,butusuallyiteventuallycrashes
Youllneedtowritesomethingthatworksmuchbetter
Some files used by proj2 example.py
racetrack example.py modified version of racetrack from Project 1 fsearch.py and tdraw.py same as in Project 1
16
Grading
Evaluation criteria:
35 correctness: whether your algorithm works correctly,
whether your submission follows the instructions
15programmingstyleseethefollowing
Style guide: https:www.python.orgdevpepspep0008
Python essays: https:www.python.orgdocessays
15documentation
Docstrings at start of the file and in each function; comments elsewhere 35onperformance
Does your program crash? If so, then how frequently?
If it doesnt crash, then how many moves to reach the finish line? Top n performers n 3 to 5 will get extra credit
17