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 lineOKtostopatdistance1
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,zlocationpx,y,
nonnegative integers
velocityzu,v,integers
You choose new velocity zu, v, where
uu, u1, u2, v v, v1, v2.
If z0, 0, then the control system may make an error in your position
eq,r, where q,r1,0,1
Vehiclemovestolocationppzexuq,yvr
New state sp, 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 s25, 8, 0, 2 p2, z2
You choose
z3 z2 1,01,2
Control error e30, 1
Example
20
10
Newlocationp3 p2z3e35, 81, 20, 1
6, 11
New state s3p3, z36, 11, 1, 2
The control error doesnt change velocity, just your positionUnrealistic,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 s36, 11, 1, 2 p3, z3
Example
20
10
You choose
z4 z3 1,12,1
Control error e41, 1
Newlocationp4 p3z4e46, 112, 11, 1
7, 13
New state s4p4, z47, 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 s47, 13, 2, 1 p4, z4
Example
20
10
You choose
z5 z4 1,13,0
Control error e51, 1
Newlocationp5 p4z5e57, 133, 01, 1
11, 14
New state s5p5, z511, 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 stopMightnotbeabletoland
exactly on the line
Controlerrorscanpreventthat
OKtogettodistance1Need 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 goalIdontthinkitwillworkverywell
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
sstate, ffinish line, wlist 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 processLetsitrunfor5seconds,killsit,readsthelastvelocityitchose
After getting your chosen velocity u, v,
it lets the opponent choose what error to use
eq,r, where q,r1,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.zipthat version had an error in it
sample probsmodified 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.pytwo 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.pyenvironment 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.pya 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.pymodified version of racetrack from Project 1fsearch.py and tdraw.pysame 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 elsewhere35onperformance
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 n3 to 5 will get extra credit
17
Reviews
There are no reviews yet.