
^{4 credit points}
_{Start: September 2008}
_{End: }_{December 2008}
_{Frequency: Annually, fall semester}
Angele Schöllig, Sebastian Trimpe
Wednesdays
14pm, ML F38
Dynamic Programming and Optimal Control by Dimitri P. Bertsekas, Vol. I, 3rd edition, 2005, 558 pages, hardcover.
Description:
Dynamic Programming Algorithm; Deterministic Systems and Shortest Path Problems; Deterministic Continuous Time Optimal Control; HamiltonJacobiBellman Equation; Pontryagin Minimum Principle; Problems with Perfect and Imperfect State Information; Infinite Horizon Problems.
Book: Dynamic Programming and Optimal Control by Dimitri P. Bertsekas, Vol. I, 3rd edition, 2005, 558 pages, hardcover.
Requirements: Knowledge of advanced calculus, introductory probability theory, and matrixvector algebra.
Apr 01 
The class Dynamic Programming and Optimal Control will be taught again by Prof. D'Andrea in Fall 2009. 
Feb 23 
An exemplary solution of the final exam can be downloaded here. 
Feb 06 
We have reported your final grades to the student administration, so you should find them soon on your mystudies account. You may look at your exam on Feb 23 from 17:30 to 19:30 in ML K33. 
Jan 21 
Final examination The final exam takes place on Jan 28, 2009 from 09:0011:30 in ETF C 1. Please make sure you arrive on time. You are allowed to bring all courserelated material: the
textbook, your homework, solutions to the homework, and your class notes. You cannot bring other textbooks, etc. Also, calculators or other electronic devices are not allowed. 
Jan 21 
For clarification (some of you asked about the "Testat"): We do not require an attendance confirmation
(“Testat”) to be allowed to take the exam. Therefore we did not assign “Testats” for
this lecture.
PhD students will get credits for the class if they pass the class. 
Dec 15 
The final exam takes place on Jan 28. (Please refer to the ETH examination office for further information.) There will be two extra office hours in the week before the exam on Jan 21 from 16:00 to 18:00 and on Jan 26 from 14:00 to 16:00, both in ML K 33. 
Dec 15 
Problem Set 5 is due on Wednesday (Dec 17). You can pick up the corrections and solutions on Dec 19 (Fri) or Dec 22 (Mon) in front of Angela's and Sebastian's office (ML K33). 
Dec 03 
Next week's lecture will deal with timeoptimal control. As an application of optimal control techniques, we will discuss a paper on trajectory generation for omnidirectional vehicles (Paper1, can be downloaded in the Lectures Section below). Paper2 will not be covered in class, but it is an interesting extension of the ideas developed in Paper1. The lecture will be given by Sebastian. 
Dec 03 
We have received the evaluation results. We will discuss them in the last lecture on Dec 17. Thank you for your valuable feedback. 
Dec 03  An updated version of Problem Set 5 is available with changed measurement noise characteristics. 
Nov 29 
Next week's lecture will be held by Prof. D'Andrea on Dec 02 from 18:30 to 20:30 in ML F38.
The same material will be repeated by Angela on Dec 03 at the original lecture
time.
There will be no recitation on Dec 03. The rest of Problem Set 4 will be covered in the recitation on Dec 10. 
Nov 29 
We have changed the schedule for the last problem set, since we wanted to include also a problem on the material that will be covered in the lecture on Dec 10. Thus, Problem Set 5 will be online on Dec 2 and you have to hand in the solution on Dec 17. 
Nov 26 
The sample solutions of the midterm can be downloaded here. 
Nov 18  A slightly updated version of Problem Set 4 is available including an additional footnote on the definition of the termination time T and the correct discretetime equation: x(k+1) = Ax(k)+Bu(k). In Question 3, we want you to hand in your controller matrix F which was accidentally called K before. 
Nov 17 
Midterm Results

Nov 05 
Problem set 4 will be online on Nov 12. As usual, you will have two weeks to solve the problem set. 
Nov 05 
You can pick up the solutions of problem set 3 in the office hours or on Thursday (Nov 6) from 15:00 to 18:00 in ML K 33. 
Oct 31 
The office hours have been rescheduled. Effective from today, the office hours take place (same location as before (ML K37.1)):

Oct 31 
Midterm Examination The midterm exam takes place on Nov 12 in ML H 44. Please make sure you arrive before 13:15. Timeline: 13:15 Latest arrival of examinees 13:20 Hand out of the exam (no writing allowed, only reading) 13:30 Start of the exam 16:00 End of the exam

Oct 30 
Problem Set 3, Problem 3 (Bertsekas, 3.5): The hint given in the textbook is partly misleading. Instead of "Show that the sine of the optimal u*(t) depends linearly on on t" it should read: Show that the sine of the angle phi, defined by tan(phi) = dx/dt, is affine linear in t, i.e. c*t+d with constants c and d. 
Oct 23 
UPDATE Class Repetition regulations: The final exam is only offered in the session after the course unit. Repetition is only possible after reenrolling. Students who have to retake the course have the option of keeping their old homework grades, in which case they have to inform us before the beginning of the new class. (The information on the ETH course catalogue will be updated shortly.) 
Oct 22 
Problem Set 3 is online. 
Oct 13  Problem Set 2, Exercise 3: According to the notation introduced in the lecture last Wednesday, matrix P should be transposed. Note that our notations is different to the notation in the book's appendix. 
Oct 13 
UPDATE Exam regulations: The final exam will NOT take place in the last lecture; the exam will be a session examination. Regulations regarding the midterm exam are unchanged (midterm inclass on Nov 12). 
Oct 13 
UPDATE Recitations/Problem Sets: From now on, recitations will take place every week (Wed, 15:00 to 16:00). All solutions to a problem set will be covered in the two recitation after the due date of the problem set.
For students who need more detailed solutions to the problem sets we will provide copies of our solutions, which can be picked up individually during office hours. The problem sets will be graded as follows: You get 1 credit per problem if your solution includes the important elements and proves that you got the main idea of the problem; 0 credits per problem otherwise. [Thanks to all students who provided valuable feedback regarding the class.] 
Oct 06 
The first problem set is to due at the beginning of the lecture on Wednesday. After the lecture, the solutions will be covered in the recitation (from 15:00 to 16:00). 
Sep 28  No office hours on Tuesday, September 30. That day, the second lecture will be held by Prof. D'Andrea from 18:30 to 21:30 (ML F38). 
Sep 24 
The information sheet that was distributed in today's class can be downloaded here. 
Sep 24 
The information on the official ETH course catalogue concerning date/place of the two extra lectures on Sep 30 and Dec 02 was wrong. The lectures will take place from 18:30 to 21:30 in ML F38. 
Sep 23 
The grading policy has been updated. 
Sep 23 
The reference book by Bertsekas will be sold by the Polybuchhandlung in the first lecture (Sep 24, in the break at 14:00) for CHF 135.00 (Master students: CHF 115.00). Only cash payments will be accepted. 
Sep 16 
The second lecture (Oct 01) will be given by Prof. D'Andrea the day before on Sep 30 from 18:30 to 21:30 in ML F38. The same material will be repeated by Sebastian at the original lecture time. 
Sep 12 
The first class will be held on September 24. 
Instructor  Prof. Raffaello D'Andrea 
Teaching Assistants  Angela Schoellig, Sebastian Trimpe 
Lecture  Wednesday, 13:00 to 15:00, ML F38 
Recitation 
Wednesday, 15:00 to 16:00, ML F38 
Recitations will take place every week. 

Office hours 
Monday, 14:00 to 16:00, ML K37.1 (IMRT library) Tuesday, 18:00 to 20:00, ML K37.1 (IMRT library) 
Office hours after the semester: Jan 21 (Wednesday), 16:00 to 18:00, ML K33 Jan 26 (Monday), 14:00 to 16:00, ML K33 

Exams 
Midterm Exam: November 12, 2.5 hours, inclass, covers everything up to, and including, problem set 3 Final Exam: session examination, 2.5 hours, covers all material 
Grading 
20% problem sets, 30% midterm exam, 50% final exam if the grade in the midterm is better than the grade in the final exam
20% problem sets, 80% final exam if the grade in the midterm is not better than the grade in the final exam 
Repetition 
The final exam is only offered in the session after the course unit. Repetition is only possible after reenrolling. Students who have to retake the course have the option of keeping their old homework grades, in which case they have to inform us before the beginning of the new class. 
#  date  topic  reading 
1 
Sep 24 
The Dynamic Programming Algorithm: Introduction, The Basic Problem; Review Probability Theory 
1.1, 1.2, Appendix C 
2 (*) 
Sep 30 
The Dynamic Programming Algorithm: The Dynamic Programming Algorithm, State Augmentation and Other Reformulations; Mathematical Review 
1.3, 1.4, Appendix A 
2R (*) 
Oct 01 
" 
" 
3 
Oct 08 
Optimization Theory, FiniteState Markov Chains 
Appendices B, D 
4 
Oct 15 
Deterministic Systems and the Shortest Path Problem: FiniteState Systems and Shortest Paths, Some Shortest Path Applications, Shortest Path Algorithms 
2.1, 2.2, 2.3 
5 
Oct 22 
Deterministic ContinuousTime Optimal Control: ContinuousTime Optimal Control, The HamiltonJacobiBellman Equation 
3.1, 3.2 
6 
Oct 29 
Deterministic ContinuousTime Optimal Control: The Pontryagin Minimum Principle, Extensions of the Minimum Principle 
3.3, 3.4 
7 
Nov 05 
Problems with Perfect State Information: Linear Systems and Quadratic Cost 
4.1 
8 (**) 
Nov 12 
MIDTERM INCLASS EXAM 

9 
Nov 19 
Problems with Perfect State Information: Optimal Stopping Problems, Scheduling and the Interchange Argument 
4.4, 4.5 
10 
Nov 26 
Problems with Imperfect State Information: Reduction to the Perfect Information Case, Linear Systems and Quadratic Cost 
5.1, 5.2 
11 (*) 
Dec 02 
Problems with Imperfect State Information: Linear Systems and Quadratic Cost (cont'd), Sufficient Statistics and FiniteState Markov Chains 
5.2, 5.4 
11R (*) 
Dec 03 
" 
" 
12 
Dec 10 
BangBang Control, Trajectory Generation Paper 
Paper1, Paper2 
13 
Dec 17 
Review 
Remarks:
(*) The lecture will be held by Prof. D'Andrea on Tuesday evening (18:30 to 21:30, ML F38). The same lecture is given by one of the Teaching Assistants on Wednesday at the regular place/time.
(**) The midterm exam takes place in ML H 44.
# 
topic 
download 
hand out 
due 
recitation 
PS1 
The Dynamic Programming Algorithm 
problemSet1 
Sep 24 
Oct 08 
Oct 08, Oct 15 
PS2 
Static Optimization, Markov Chains, Shortest Path Problems  problemSet2 
Oct 08 
Oct 22 
Oct 22, Oct 29 
PS3 
Deterministic ContinuousTime Optimal Control 
problemSet3 
Oct 22 
Nov 05 
Nov 05, Nov 19 
PS4 
Problems with Perfect State Information 
problemSet4 
Nov 12 
Nov 26 
Nov 26, Dec 10 
PS5  Problems with Imperfect State Information  problemSet5 
Dec 02 
Dec 17 
Dec 17 
Remarks:
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf
folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser.
More
information