Class Project

Dates:

March 11: Project Proposal Due
March 13: Feedback on Project Proposal
April 3: Midterm Reports Due
April 15: Projects Due

Projects can be done individually or in teams of two but team projects have to be more substantial than individual ones. Projects should extend existing planning techniques but you might also be able to talk us into applying them in a substantial way. Please feel highly encouraged to come up with a project on your own that relates to your interests and uses techniques that we discussed in class, but below are some sample projects to give you a feel for what we are looking for. (All of the projects are true research projects in that you can spend an arbitrary amount of time on them and perhaps publish them if you have a tremendously good idea.)

Your project proposal should outline a) what you want to do, b) why this is interesting. c) how you want to do it, and d) how you want to test your ideas. The project proposal of a team should also state how the work will be divided among the team members.

You final project report should describe in detail a) what you did, b) why this is interesting, c) how you did it, d) how you tested your ideas, and - most importantly - e) which insights you gained. The description should explain your ideas, implementations, and experimental setup in sufficient detail to enable others to re-implement your idea. You should explain your insights in sufficient detail to enable other to understand a) what worked, b) what did not work, and - most importantly - c) why you believe something worked or did not work. (For example, depending on your project, you could compare your planner to a similar existing planner and experimentally characterize precisely which properties domains must have in order for your planner to outperform the traditional one and then try to argue why these properties benefit your planner.) 

Comparing D* and D* Lite

D* and D* Lite behave in a similar but not identical way. Implement them and verify the previous results on the number of vertices they expand and extend the previous results with timing information. Study experimentally or analytically (by studying their pseudo code) when one of them expands a vertex that they other one does not. Can one say that D* and D* Lite are versions of exactly the same base algorithm but optimize it differently?

Starting point: - http://www.cc.gatech.edu/fac/Sven.Koenig/greedyonline/papers/tr2002-3.ps.gz 

Comparing LRTA* and D* (or D* Lite)

LRTA* and D* (or D* Lite) can both be used to move a robot in initially unknown terrain to given goal coordinates. One can expect that LRTA* has a smaller run time while D* has a smaller travel distance. Implement them and study this trade-off experimentally. Then, investigate ideas for speeding up LRTA* (by making its search re-use results from previous searches) and decreasing its travel distance (for example, by making the search horizon adaptive).

Starting points: - http://www.cc.gatech.edu/fac/Sven.Koenig/greedyonline/papers/tr2002-3.ps.gz - R. Korf, Real-time heuristic search, Artificial Intelligence, 42 (1990), pp. 189--211. 

Making Graphplan Incremental

Graphplan is an off-line planning method that produces plans for given planning problems. Define a nontrivial class of re-planning problems, for example, one where the available operators change slowly over time. Then investigate methods for speeding up Graphplan by reusing information from previous searches. Implement them and characterize experimentally under which conditions your incremental version of Graphplan is faster than the original one and by how much. Can you improve on the ideas by Gerevini and Serina?

Starting points: Alfonso Gerevini, Ivan Serina: Fast Plan Adaptation through Planning Graphs: Local and Systematic Search Techniques. AIPS 2000: 112-121 

Something Old, Something New

Think of _one_ particular way of changing one of the modern planners (such as Graphplan, SATPlan, or HSP) so that it exploits the structure of planning problems more than it currently does. Alternatively, think of _one_ particular way of changing one of the more classical planners (such as UCPOP) to improve its search strategy. Implement your idea and characterize experimentally under which conditions your planner is faster than the original one and by how much. 

A* with BDDs

Implement A* with BDDs, for example SetA*. Characterize experimentally how different state representations affect the runtime of your implementation. Improve the runtime of your implementation for several typical search domains based on these insights and other ideas that you might have (for example, switching to Epsilon-A*). Then, compare your implementation to a regular implementation of A* and characterize whether and when A* with BDDs outperforms A*. Can you improve on the ideas by Jensen et al.?

Starting Points: SetA*: An efficient BDD-Based Heuristic Search Algorithm, R.M. Jensen, R.E. Bryant and M.M. Veloso, In Proceedings of 18th National Conference on Artificial Intelligence (AAAI'02), Pages 668-673, 2002.