printlogo
http://www.ethz.ch/index_EN
Institute for Dynamic Systems and Control
 
print
  

Dynamic Programming and Optimal Control (Fall 2008)

Optimal Control

151-0563-00

4 credit points

Start: September 2008
End: December 2008

Frequency:  Annually, fall semester

 

Lecturer

Raffaello D'Andrea

 

Assistants

Angele Schöllig, Sebastian Trimpe

 

Day/Time/Location

Wednesdays

1-4pm, ML F-38

 

Book

Dynamic Programming and Optimal Control by Dimitri P. Bertsekas, Vol. I, 3rd edition, 2005, 558 pages, hardcover.

151-0563-00

Description:

Dynamic Programming Algorithm;  Deterministic Systems and Shortest Path Problems;  Deterministic Continuous Time Optimal Control;  Hamilton-Jacobi-Bellman 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 matrix-vector algebra.

Announcements

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:00-11:30 in ETF C 1.  Please make sure you arrive on time.

You are allowed to bring all course-related 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 time-optimal control.  As an application of optimal control techniques, we will discuss a paper on trajectory generation for omni-directional 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 discrete-time 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
  • The midterm results will be posted on the board at the IMRT (ML, hallway level K) on Nov 26.
  • Sample solutions to the midterm exam will be available on the class website from Nov 26.
  • You can take a look at the correction of your midterm at the office hours on Dec 1 (regular time, 14-16) and Dec 2 (17-18).
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)):


Monday, 14:00 to 16:00 (Angela)
Tuesday, 18:00 to 20:00 (Sebastian)

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

  • The midterm exam will cover everything up to and including problem set 3.
  • We will provide you with paper for the exam.
  • During the exam, you may use the class textbook (Bertsekas, Dynamic Programming and Optimal Control) and your notes.
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 re-enrolling.
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 in-class 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.

Class Facts

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, in-class, 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 re-enrolling.  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.

Lectures

# 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, Finite-State Markov Chains
Appendices B, D
 4 Oct 15
Deterministic Systems and the Shortest Path Problem: Finite-State Systems and Shortest Paths, Some Shortest Path Applications, Shortest Path Algorithms
2.1, 2.2, 2.3
 5 Oct 22
Deterministic Continuous-Time Optimal Control: Continuous-Time Optimal Control, The Hamilton-Jacobi-Bellman Equation
3.1, 3.2
 6 Oct 29
Deterministic Continuous-Time 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 IN-CLASS 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 Finite-State Markov Chains 5.2, 5.4
 11R (*)
Dec 03
        "    "
 12 Dec 10
Bang-Bang 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.

Problem Sets

# 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 Continuous-Time 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

© 2013 ETH Zurich | Imprint | Disclaimer | 25 August 2013
top