CS572: project3b In project2b you built a device that can generate behavior. You also added an energy predicate that combined the scores from all the different models. In this project you will build multiple search engines to find the fewest constraints on that device that most decreases the energy. Your task is to implement a set of search engines to find the minimum decisions that most reduce effort, defects, threats, months. Note that this is a non-linear problem: improving one may muck up the other. That's the fun of it! In the next project you will conduct elaborate comparative studies with those search engines in order to make a statement about the different benefits of the different search engines. At first pass, there seems a lot of work here. However: - You only have to show that each search engines work, just once. - There is no need (yet) for any optimizations, elaborate experiments, that is all part of the next project. ---------------------------------------------------------------------- DATES Due Friday week 10, March 21 Late assignments accepted (with deductions for late work) till March 25 ---------------------------------------------------------------------- YOUR TASK Show that N search engines can run, just once (each) on the models built in project2b. ---------------------------------------------------------------------- SPECIFIC TASKS 1) Some reading 2) Some minor extensions to the project 2b code. 3) Implement "completion" 4) Implement a bunch of search engines 5) Do a walk through of the code with me ---------------------------------------------------------------------- WHAT NOT TO DO (YET) Do not perform elaborate tests of the search enginers. That is for Project4. Do not perform optimizations studies. That is for Project4. For now, if your code limps over the finishing line, that is fine. ------------------------------------------------------------------ WHAT TO HAND IN To prove that all that is working, you will submit(*) - a demo.lisp file that demonstrates tasks 2,3,4,5 (listed above). I'll run this by first loading "make.lisp" the "demo.lisp" the calling "(proj3b)" - Before submission you will run demo.lisp and cache the output to doc/proj3b/demo.txt. Add comments to demo.txt to show off anything you want. Number each comment consecutively. As before, you won't "submit" you code. Rather, your code will be stored in a subversion repository located at the url I send out. So you won't "submit" the system. Instead, you will just commit your code regularly and on the submission date I'll just grab a copy ------------------------------------------------------------------ HOW TO DO TASK 1) : SOME READING For KEYS, read http://menzies.us/pdf/08keys.pdf. For full details, see http://unbox.org/wisp/tags/keys/1.0/lib/tool.c For ISSAMP and LDS and LDS-BBS, see http://menzies.us/csx72/doc/search/lds.pdf For the horrible full details on MAXWALKSAT, see http://unbox.org/wisp/trunk/keys/src/Maxwalksat20/maxwalksat.c. For a much simpler one, see http://unbox.org/wisp/trunk/keys/src/maxwalkeys/maxwalkeys.c. ------------------------------------------------------------------ HOW TO DO TASK 2) : Some minor extensions to the project2b code. Before combining threats with everything else, anything threat level less than five should be set to zero (this avoids a tedious variance problem). Add a mutator for the threat tables (for details, see section 3.3. of http://menzies.us/pdf/07casease.pdf Add a facility to do Monte Carlo over a space of possible project values. See Fig7 of http://menzies.us/pdf/07casease.pdf for two examples of project ranges. ------------------------------------------------------------------ HOW TO DO TASK 3) : "Completion" Your task is to search for the fewest constraints that most decrease the energy. This means that when you search through the space of possible project values (recall Fig7) then you might have, say, 20 things you can control. But your current best solution may only constrain 3 of them. So when you want to score your 3 new new constraints, you have to do 100 runs where, each time, you "complete" an entire set of decisions as follows: a) values are picked at random from the legal range of project values (Fig7) b) your preferred solution is imposed c) the rest of the values are selected at random. Search1.lisp does something like this (see random-policy) but if you don't understand that code, you are going to have to code up something yourself. ------------------------------------------------------------------ HOW TO DO TASK 4) : "Search engines" Getting going one run (each) of the following search engines to find the fewest constraints that most reduce energy. You have to try at least six. All of three dumb search engines: - KEYS - simulated annealing - ISSAMP (note that for ISSAMP, retries could be triggered if the new solution ever staggers into an energy worse than the least energy seen so far in any other solution) And any three of the following smart search engines - beam first search - DFID - A-star - MaxWalkSat - LDS - LBDS+BBS For extra credit, do all six. Feel free to use Norvig's code for any or all of the above. For more extra credit, do at least three of the above "smart" searches and any more of your own selection. For yet more extra credit, write two version of SA and beam: raw and biased where biased contains some heuristic knowledge of how to best nudge the COCOMO models (e.g. favor extreme values more than the middle ones- you might have other ideas based on the plots you generated at the end of Project2b). To show that each run works, present some graphical output. You'll have to be a little creative here but see the last figure of the KEYS paper for one idea. ------------------------------------------------------------------ HOW TO DO TASK 5) : "Code walk through" Same rules as before. Me doing round robin of the group.