ETH - IDSC - Optimal Control 2008

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. ct+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

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

Oct 08

Optimization Theory, Finite-State Markov Chains

Appendices B, D

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

Oct 22

Deterministic Continuous-Time Optimal Control: Continuous-Time Optimal Control, The Hamilton-Jacobi-Bellman Equation

3.1, 3.2

Oct 29

Deterministic Continuous-Time Optimal Control: The Pontryagin Minimum Principle, Extensions of the Minimum Principle

3.3, 3.4

Nov 05

Problems with Perfect State Information: Linear Systems and Quadratic Cost

4.1

8 (**)

Nov 12

MIDTERM IN-CLASS EXAM

Nov 19

Problems with Perfect State Information: Optimal Stopping Problems, Scheduling and the Interchange Argument

4.4, 4.5

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

Dec 10

Bang-Bang Control, Trajectory Generation Paper

Paper1, Paper2

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

Remarks:

The solutions to the problem sets will be covered in the recitation on the day, when the problem set is due, and the recitation in the following week.
In the recitation, all main ideas essential to solve the problems as well as the final results will be covered. For those students who need more detailed solutions we will provide copies of our (handwritten) solutions, which might be picked up individually during office hours.
Up to 3 students can work together on the problem set. If they do, they have to hand in one problem set per group and will all receive the same grade. One can also work alone, of course.
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.

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