Courses:

When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more.

For your 16.413 final projects this year, you will be writing a tutorial article, with accompanying code, describing basic building blocks for coordinating autonomous and robotic systems. Each article will be in the spirit of a "Numerical Recipes in C" chapter. Note that, while Numerical Recipes in C is one source of inspiration, you should improve upon this model in any way you see fit. Other examples are recent texts on programming with templates. That is, the article provides a pedagogical description of a particular building block that is accessible to a wide audience, and that is made concrete through pseudo code, implementation and application examples. Each of your articles is to be provided as a Web document. We will then bind them together, as chapters, and as a set of "Autonomy recipes in Java®," so to speak.

One motivation for this project is the success of other departmental courses that have generated an innovative product. We have seen through the Aerospace capstone projects, like Spheres, that student projects can be very influential to the aerospace field. These projects rival the best in industry and government, within their mission class. With your approval, we plan to publish your articles on the Web for wide dissemination. Such a text doesn't exist, but is sorely needed by the large community. We hope that by providing a wide audience for your projects, this will provide you value for your hard work.

The Web publication of your chapters also means that in your writing you should focus carefully on quality over quantity. Each of your chapters is a first introduction to a particular category of method. Please lay out the basics carefully, only going as deep as is reasonably manageable given your available time.

Collectively, the set of articles will also be the starting point of a "Model-based autonomy toolbox." In future years we plan to grow this toolbox towards one that will provide all the necessary elements for constructing a range of autonomous systems. Outside of the course we are beginning to develop a "Virtual Solar System," which is a simulation based environment for deploying autonomous systems, which is persistent and shared. We optimistically hope that we will be able to use a first generation of the Virtual Solar System in next semesters' Cognitive Robotics and Space CDIO capstone courses. If your tutorial articles are written well, then in upcoming years you will hopefully see your code used by future students, in order to deploy a Mars rover or Venus "aerobot" within the Virtual Solar System.

The learning objective of this final project is to increase your depth of understanding of more advanced building blocks for autonomy and decision making, by going deep on one concrete instance. It has often been said that one only truly understands a topic when you teach it. It is in this sprit that I ask you to write this article. The value of a tutorial article is that it requires you to describe a method precisely, simply, intuitively, concretely and with good motivation. These five principles should guide the writing of your article.

• Precisely: You will state precisely the problem that you are solving, independent of the solution method. You will describe your solution method precisely through pseudo code.
• Simply: You will strive for a simple, but precise statement of problem and solution.
• Intuitively: You will explain your problem and solution method in plain English, as well as through more formal notation. You will state up front the key insights underlying your method. You will use pedagogical examples to explain your concepts and algorithms as you introduce them, not just after the fact.
• Concretely: You will make your precise descriptions concrete through executable Java® code and executable benchmark examples.
• With Good Motivation: In addition to describing what problem you are solving and how you are solving them, you will carefully motivate why one wants to solve this problem and why your solution method is appropriate. Careful motivation is a key element of good writing.

This year we will introduce eight introductory topics to the model-based autonomy toolbox, through the following teams:

Topic 1: Integer Programming
Team: Masahiro Ono and Larry Chang

Topic 2: Valued Constraint Satisfaction
Team: Erica Gralla and Wilfried Hofstetter

Topic 3: Activity Planning
Team: Tom Krenzke and Stephen Thrasher

Topic 4: Temporal Constraint Satisfaction
Team: Michael Park and Amy Brzezinski

Topic 5: Propositional Inference
Team: Han-Lim Choi and Chung-sang Teo

Topic 6: Bayesian Inference
Team Tom Temple and Jeremie Pouly

Topic 7: Path Planning Using Potential Fields
Team Matt Greytak

In addition, one team will apply one advanced model-based autonomous control system, to a real-world space application:

Topic 8: Model-based Programming Applied to Orbital Express
Team: Diane Levine, Peter Sienkewicz, and Joe Bondi

Each team will have access to an additional handout and selection of background slides, papers and chapters that you may find useful. While this is one source of input, you are ultimately responsible for finding the materials that you find most suitable.

Your final project report will be structured as described below. To support uniformity of presentation, we will be providing an html template that supports this structure.

We will also provide information in the future for how to submit your final projects. Nominally, you will package your final html report, your code, benchmark examples, course presentation, and any other supporting materials within a .zip file, and submit this file by the final project due date. At the same time, you will provide three hardcopies ofthe final html project report. The following is the project report outline.

1. Introduction
2. Problem Description
   • Motivation for Problem
   • Formal Problem Statement
     • Inputs
     • Outputs
     • Specification of a Correct Solution
   • A Pedagogical Example (probably best interleaved with "Formal Problem Statement")
   • Java® Application Programmer Interface (API)
   • Example Run of API on an Example
3. Method Description
   • Introduction of Big Ideas
   • Algorithm Description with Pseudo-code
   • Walked Through Example (also interweaved with "Algorithm Description with Pseudo-code")
4. Implementation
   • (Very Well) Commented Java® Code
5. Demonstration
   • How to Load The Package.
   • Run of Java® Code on Pedagogical Example
   • Discussion of Performance on Benchmarks
   • Benchmark Examples (possibly in an appendix)
   • (Extra Credit) Java® Applet Demonstrating Package

In Phase 1 you will:

1. Implement the first two sections of the report; and
2. Develop a detailed plan for completing the rest of the project. You will present the plan portion of the assignment to the staff in short meetings that will be schedules for this purpose.

The introduction section should give an overview of the solution method including discussion of what kind of problems it can reasonably be applied to, what other methods might be considered (if any), and what benefits this method may have over competing methods. Section 2 should elaborate by developing:

1. Motivation for the problem (see learning objectives section above);
2. A formal problem statement;
3. A pedagogical example; and
4. An API with examples.

The pedagogical example developed in section 2 will be used to demonstrate the Java® implementation in Phase 4 (see below).

In the second week you will complete section 3 of the report.

Section 3 should introduce the reader to the specific details of the algorithm including:

1. The "Big Ideas" - what insights does the algorithm bring to bear on the problem in order to solve it effectively and efficiently?
2. The algorithm described with the help of a pseudo code implementation. Pseudo code helps a reader understand an algorithm by the reader to focus on the salient steps of the algorithm uncluttered by implementation details.
3. A walked through example. This is best done by using the example to describe how the pseudo code works Rather than writing the pseudo code description and the example as separate sections, it is usually more effective to interleave the two.

Feedback Group Table

When this assignment is done you will have written the first three sections. You will bring five copies of your report (the first three sections) to class. One copy will be handed in and two copies will be given to each of your feedback groups (see the feedback group table above to find the team that will be providing feedback for your topic). Each group will provide detailed feedback to two other groups and will be due as part of Phase 3 (see below). The feedback is intended to help to improve the quality of the reports. The feedback is part of the assignment and must be turned in for grading in addition to delivering it to the other group. Your feedback must be handed in in class and two copies of your feedback must be given to each of the groups to whom your group is providing feedback (five copies in all).

Phase 3 gives you two weeks to:

1. Respond to all of the feedback that you receive from both groups of reviewers by updating your first three sections appropriately;
2. Develop your, well written and documented, code for section 4; and
3. Develop your project presentation.

Presentation slides should be submitted electronically as part of your assignment and will be presented in class. You will, however, not be graded on your presentation.

Your code should be demonstrated on your pedagogical example. More comprehensive demonstrations of your code will be developed in Phase 4.

In this final phase you will complete your tutorial article by adding section 5.

In order to comprehensively demonstrate your implementation you will develop a sequence of tests that demonstrate the performance of your implementation on non-trivial examples.

You will submit the full tutorial; the presentation; and the working code, tests, and examples. Your submitted tutorial should include revisions that reflect all of the useful feedback that you received from your two feedback groups, and from your returned assignments from the prior phases. The goal of the feedback groups and on the incremental grading of the tutorial is to produce a high quality final document.

[AIMA] Russell, Stuart, and Peter Norvig. Artificial Intelligence: A Modern Approach. 2nd ed. Upper Saddle River, NJ: Prentice Hall/Pearson Education, c2003. ISBN: 0137903952.

[IOR] Hillier, Frederick S., and Gerald J. Lieberman. Introduction to Operations Research. 8th ed. Boston, MA: McGraw-Hill Higher Education, 2005. ISBN: 0072527447.

[JINS] Flanagan, David. Java® in a Nutshell. Sebastopol, CA : O'Reilly, 2005. ISBN: 0596007736.

The table below contains a selection of student projects and relevant recommended readings for each group. All work is courtesy of the students names and used with permission.

Project files.

Topic #	Topics	Readings
1	Integer Programming Team - Masahiro Ono and Larry Chang	16.410/13, "Integer Programming and Branch and Bound." Lecture 15-16, Spring 2003. "Integer Programming." Chapter 11 in IOR. Topics should include "branch and bound" and if time permits, then "cutting planes".
2	Valued Constraint Satisfaction (PDF - 1.5 MB) Team - Erica Gralla and Wilfried Hofstetter	Lecture notes from 16.412J, "Soft Constraint Processing." Lecture 7 are relevant. Dechter, Rina. "Constraint Optimization." Chapter 13 in Constraint Processing. San Francisco, CA: Morgan Kaufmann Publishers, c2003. ISBN: 1558608907. ———. "Advances in Inference and Search for Combinatorial Optimization." Tutorial from the Constraint Programming Conference, September, 2005 is relevant. (TXT) (PDF - 1.9 MB) You may find optional topics to cover by looking for recent papers on the Web by Dechter, by Schiex and by Sachenbacher. Focus on a solution method that combines search and inference, and on methods for solution bounding through relaxation.
3	Activity Planning (PDF) Team - Tom Krenzke and Stephen Thrasher	16.410/413, "GraphPlan." Lectures 12-13, Fall 2005. Blum, A., and M. Furst. "Fast Planning Through Planning Graph Analysis." Journal of Artificial Intelligence 90 no. 1-2 (1997): 281-300. Weld, Dan. "Recent Advances in AI Planning." AI Magazine (1999). Focus on the basic graph plan algorithm; this is of sufficient complexity, that it makes a good focus for your whole tutorial.
4	Temporal Constraint Satisfaction (PDF) Team - Michael Park and Amy Brzezinski	Dechter, R., I. Meiri, and J. Pearl. "Temporal Constraint Networks." Journal of Artificial Intelligence 49 (1991): 81-95. 16.410/413 "Planning and Execution in a Changing World." Lecture 14, Fall 2005. Russell, and Norvig. "Time Schedules and Resources." Section 12.1 in AIMA. This describes the role of time in planning. Cormen, Thomas, Charles Leiserson, Ronald Rivest, and Clifford Stein. Chapters 25 and 26 in Introduction to Algorithms. Cambridge, MA: MIT Press, 2001. ISBN: 0262032937. These chapters cover Single Source and All-Pairs Shortest Path algorithms, which are used in the Dechter paper. Developing a tutorial based on the Dechter paper is a good focus.
5	Propositional Inference (PDF) Team - Han-Lim Choi and Chung-sang Teo	Russell, and Norvig. Chapter 7 in AIMA. Covers basic propositional logic, reduction to CNF, and inference and satisfiability algorithms. 16.410/13, "Propositional Logic and Satisfiability." Lecture 20, Fall 2004. You might find useful the following tutorial: Bacchus, F. "SAT Solving and its Relationship to CSPs." Constraint Programming 2005. Advances in Search, Inference and Hybrids for Solving Combinatorial Optimization Tasks (TXT) Advances in Search and Interface for Combinatorial Optimization. (PDF - 1.9 MB) As optional more advanced topics, you may want to look at recent articles on the Chaff and RelSat solvers. The witness algorithm for unit propagation is very effective. Another optional topic is the Bucket Elimination algorithm for performing propositional resolution. SeeConstraint Processing, by Rina Dechter or one of her tutorials, such as, Principles and Methods for Automated Inference (PDF) slides 13-15 (among others). AIMA, chapter 7 provides a good focus for your tutorial, including reduction to CNF, the DPLL algorithm and resolution. Advanced algorithms might be interesting, but be careful about scope.
6	Bayesian Inference (PDF) Team - Tom Temple	Russell, and Norvig. Chapters 13 and 14 in AIMA. Look on the Web for tutorials; there are many out there (e.g., by Daphne Koller, by Rina Dechter,...) Its easy to find these using GoogleTM and there are some Bayes net Web sites with materials. The text by R. Jensen is good; I hear that there are good draft texts by Michael Jordan, as well as by D. Koller and N. Friedman. A good focus is basic exact inference within a Bayesian network. Be careful to contain the scope of the project.
7	Path Planning Using Potential Fields (PDF - 1.1 MB) Team - Matt Greytak	16.410/13, Lecture notes. "Path Planning." Lecture 7, Fall 2004 by Nick Roy.
8	Model-based Programming Applied to Orbital Express (PDF) Team - Diane Levine, Peter Sienkewicz, and Joe Bondi	Williams, Brian C., Michel Ingham, Seung H. Chung, and Paul H. Elliott. "Model-based Programming of Intelligent Embedded Systems and Robotic Space Explorers." Invited paper in Proceedings of the IEEE: Special Issue on Modeling and Design of Embedded Software 9, no. 1 (January 2003): 212-237. Kim, P., B. Williams, and M. Abramson. "Executing Reactive, Model-based Programs through Graph-based Temporal Planning." IJCAI (2001): 487-493.