Assignment 4 Solution

Part 1: Programming




You are going to do the 7 programming questions about adversarial search given here: http://ai. berkeley.edu/tracking.html. You are only required to change bustersAgent.py and inference.py. If you have any issues with other parts of the code let your instructor or TA know ASAP, even if you manage to solve your problem. Use the data structures in util.py for the autograder to work properly. If the you think you have the right answer but the autograder is not giving you any points, try to run it on individual questions (look at P0 for details on how to use the autograder.py).













1
Hints




The rst 5 programming questions are fairly straightforward especially if you paid attention in the class. Furthermore, both the website and the code comments include a lot of hints so make sure you read them!




Website and the Comments




I cannot stress this enough so I am just going to repeat. This homework has a lot of guidance, both in its webpage and in the code comments. I suggest you read them carefully. Also read the rst 5 questions and the last 2 questions together.




Exact Inference




There is really nothing else to hint at. One minor warning is that to pay attention of the time elapse loop. The required summation can happen \out of sequence".




Uniform Initialization of Particles




As stated in the comments, do not initialize randomly (even with a uniform distribution!) but do it uniformly. Imagine I give you 10 slots and 100 balls. How would you ll those slots uniformly? Find the number of particles per ghost position you need to have and take it from there. There are cases analogous to you having 104 balls for 10 slots. I leave it up to you to deal with the remainder (i.e 4) as you like, ran-dom is ne. A piece of information; the number of particles is much bigger than the legal ghost positions.




Particle Weight Representation and Particle Resampling




You may nd it easier to use util.Counter() data structure to keep track of particle weights instead of having another list. This will be indexed by the ghost positions. However, we have more particles than these positions. I leave it up to you to gure out how to deal with this in case you chose this. Note that this data structure can represent any number given an index in general, they do not have to be probabilities.




Note that you need to resample after updating the particle weights in the observe() method of the inference class. The advantage of using the util.Counter() data structure is that the existence of the util.sample() function.




You can always use another list or keep a combined list for the weights, in which case you will need to implement your own sampling function.




Dynamic Bayes Nets




When you are done with the rst 5 questions, I suggest you take a break and answer the relevant questions in your report before working on these last 2 questions. I do not want to spoil all the fun for when you get back. So I will only brie y mention a few things.




A particle will include positions of two ghosts. The emission models are for individual ghosts. To get a particle weight, you need to multiply the emission probabilities together. If a ghost is in a jail cell, then its emission probability becomes 1.




In the previous cases, a ghost had legal positions which you used to pick uniformly distributed particles. In the DBN case, this gets slightly tricky. Think carefully about what you need to pick from. We will give a small example without explaining it:




Let f(1,3),(2,2),(2,3)g be a list of legal positions. Assuming that two ghosts cannot be in the same position, you need to pick from f[(1,3)(2,2)],[(1,3)(2,3)],[(2,2)(1,3)],[(2,2)(2,3)],[(2,3)(1,3)],[(2,3)(2,2)]g




Part 2: Report




This part includes answering the following questions based on your program’s output on the given pac-man tests. You are expected to answer the questions concisely. Five sentences is more than enough for most of them. Limit yourself to 300 words. It is okay if you over-generalize, as long as your direction is clear and correct.




Create a PDF le named report.pdf containing your answers for submission. Write your name and your number on the report as well! We forgot to mention this in the previous homeworks.




Written Q1:




Run the autograder on q2 and watch the probabilities. Why do they settle even though the ghost is







2



moving? Can you tell the two ghosts apart and if so how? (Hint: Run these test cases q2/1-ExactElapse, q2/2-ExactElapse, if you need to observe them individually)




Written Q2:




Try the following lines of code and watch the probabilities settle:




python autograder.py -t test cases/q1/2-ExactObserve python autograder.py -t test cases/q1/3-ExactObserve







Why is it the case that in one of them we can nd the ghost but not in the other one?




Written Q3:




Run the autograder on q4 and watch the probabilities. Can you tell when the particles get re-initialized? Comment on the reason(s) on why pacman gets in that situation? Would increasing the number of particles be a solution?




Written Q4:




Compare how the probabilities evolve between the exact inference and the approximate inference cases (q1, q2 vs q4, q5). Also comment on if 5000 particles make sense for the problems you have seen.




Written Q5:




In the DBN questions (q6, q7), you had to work on a particle that had multiple ghost positions. Their transition were dependent on each other but their emissions were not. How did you create a new particle with elapsed time and how did you calculate its weight? You can use mathematical equations to help you explain this.




Submission




You are going to submit a compressed archive through the blackboard site. The le should extract to a folder with your student ID without the leading zeros. This folder should only contain report.pdf, bustersAgents.py and inference.py. Other les will be deleted and/or overwritten. Do not submit any code if you only want us to grade your report.




Important: Download your submission to make sure it is not corrupted and it has your latest report/code. You are only going to be graded by your blackboard submission.




Submission Instructions




You are going to submit a compressed archive through the blackboard site. The le can have zip, rar, tar, rar, tar.gz or 7z format.




This compressed le should extract to a folder with your student identi cation number with the two leading zeros removed which should have 5 digits. Multiple folders (apart from operating system ones such as MACOSX or DS Store) greatly slows us down and as such will result in penalties




Code that does not run or that does not terminate will not receive any credits.




Do not trust the way that your operating system extracts your le. They will mostly put the contents inside a folder with the same name as the compressed le. We are going to call a program (based on your le extension) from the command line. The safest way is to put everyting inside a folder with your ID, then compress the folder and give it your ID as its name.




Once you are sure about your assignment and the compressed le, submit it through Blackboard. After you submit your code, download it and check if it is the one you intended to submit.




DO NOT SUBMIT CODE THAT DOES NOT TERMINATE OR THAT BLOWS UP THE MEMORY.




Let us know if you need any help with setting up your compressed le. This is very important. We will put all of your compressed les into a folder and run multiple scripts to extract, clean up, grade and do plagiarism checking. If you do not follow the above instructions, then scripts might fail.







3