Difference between revisions of "ME/CS 132b, Spring 2013"

From Murray Wiki
Jump to navigationJump to search
(Created page with "{| width=100% |- | colspan=2 align=center | <font color='blue' size='+2'>Advanced Robotics: Navigation and Vision</font> |- valign=top |} <table width=100%> <tr valign=top> <t...")
 
 
(109 intermediate revisions by 3 users not shown)
Line 14: Line 14:
 
</td><td width=5%></td><td width=45%>
 
</td><td width=5%></td><td width=45%>
 
'''Teaching Assistants'''  (me132-tas@caltech.edu)
 
'''Teaching Assistants'''  (me132-tas@caltech.edu)
* Yifei Huang (yifei.huang@caltech.edu)
+
* Alex Jose (ajose@caltech.edu)
* Ilya Nepomnyashchiy (ilyanep@caltech.edu)
+
* Mary Nguyen (mary.nguyen@caltech.edu)
* Office hours: TBD
+
* Office hours: By appointment
 +
'''Course Mailing List''': me132-students@caltech.edu ([https://utils.its.caltech.edu/mailman/listinfo/me132-students sign up])
  
'''Course Mailing List''': me132-students@caltech.edu ([https://utils.its.caltech.edu/mailman/listinfo/me132-students sign up])
+
* This list has been updated. If you did not receive a subscription email, please subscribe using the link.
 
</td></tr>
 
</td></tr>
 
</table>
 
</table>
  
 
== Announcements ==
 
== Announcements ==
* '''2/11''': Office hours today (Monday) 5-6pm in SFL 2-2.
+
* <b>4/30/2013:</b> No class on May 7th and 9th. Instead, this week will be spent on the lab.
* '''2/1''': Office hours for the upcoming week will be Sun 9-10pm, Mon 5-6pm and Wed 9-10pm.
+
* <b>4/16/2013:</b> A handout on [[media:cobstacle_param.pdf | Parametrizing C-obstacles]] was distributed in class
* '''1/15''': Problem Set 1 is now due Tue Jan 22. Also, there will be additional Office Hours this week only: Wed Jan 16 9-10pm in SFL 2-2.
+
* <b>4/11/2013:</b> A handout on the [[media:StarAlgorithm.pdf | Star Algorithm]] for computing fixed orientation c-obstacle slices was handout out in class.
* '''1/11''': Problem Set 1 has been posted. Also, fill out this doodle poll for office hour times before next week: http://doodle.com/k3itpfnzdhspyzbs
+
* <b>4/11/2013:</b> A handout on [[media:cobstacle.pdf | configuration space obstacles]] was handed out in class.  
* '''1/10: Note about signing up for the mailing list: ''' Once you sign up, you will receive an email containing a confirmation link which you must go to in order to be on the mailing list. There are only 10 people signed up, so check that you did the confirmation step!
+
* <b>4/11/2013:</b> Homework #1 has been distributed. An online version can be [[media:ME132Homework1.pdf | found here]]
* There is a link under 'Course Texts' to Chapter 1 of Forsyth if you haven't bought the book yet. You will still need the book for all other chapters.
+
* First lecture on 4/2 at 2:30 pm in Room 306 Thomas.  An [[media:ME132Overview.pdf | Overview of the course]].
* First lecture on 1/8.  
+
* Link to [https://www.cds.caltech.edu/~murray/wiki/index.php/ME/CS_132a,_Winter_2013 ME 132(a) Wiki Page]
  
 
== Course Information ==
 
== Course Information ==
 
=== Prerequisites ===
 
=== Prerequisites ===
There are no formal prerequisites for the course. Students are expected to have basic understanding of linear algebra, probability and statistics. We will review some of the required background materials during the first week of lectures. Besides these, students should have some prior programming experience and know at least one of the following languages: C, Python, or MATLAB. Depending on the background of the class, we will hold tutorials for some of the programming languages to help students get started.
+
There are no formal prerequisites for the course, other than ME/CS 132(a).   Some of the required background material will be reviewed during the first weeks of lecture. The theory part of ME/CS 132(b) is largely independent of the material in ME/CS 132(a), but students are expected to be able to use the experimental lab equipment introduced in the first quarter of the course, and are expected to be able to apply the sensor processing and mapping techniques learned in the first quarter.  The greater emphasis on a final project in this quarter will require a good comfort level with computer programming in at least one of the following languages: C, C++, Python, or MATLAB.
  
 
=== Grading ===
 
=== Grading ===
There are no midterm/final exams for this course. The grade will be based on weekly homework (60%) and two week-long labs (20% each). Late homework will not be accepted without a letter from the health center or the Dean. However, you are granted a grace period of '''five''' late days throughout the entire term for weekly homework. Please email the TAs and indicate the number of late days you have used on the homework. '''No grace period is allowed for week-long labs'''.  
+
ME/CS 132(b) is primarily a project-based course. The grade will be based on <b> 2 homeworks</b> (20% of total grade) and <b> two week-long labs </b> (10% of total grade each). Sixty percent (60%) of the grade will be based on a <b> final project</b> which is due on the last day of the finals period. The final project can potentially be done in teams, with the instructor's approval.  
  
* '''Homework''': Homework is usually due in one week after it is assigned. You can choose to turn in a hard copy in class or send an electronic copy to Yifei Huang (yifei.huang at caltech.edu). If you are unable attend the lecture, contact the TAs to find an alternative way to turn in your homework.
+
* '''Homework''': Homework is usually due in one week after it is assigned. You can choose to turn in a hard copy in class or send an electronic copy to the TAs (me132-tas at caltech.edu). If you are unable attend the lecture, contact the TAs to find an alternative way to turn in your homework.
* '''Labs''': Students will form groups of 2-3 people and perform lab experiments together. Detail of this will be announced later in the course.
+
* '''Labs''': Students will form groups of 2-3 people and perform lab experiments together. The lab will consist of implementing and testing basic algorithms on a mobile robot, and demonstrating the result, as well as submitting a copy of the code underlying the lab demonstration. The one-week labs this quarter are intended to help get the students prepared for the final project.
  
 
=== Collaboration Policy ===
 
=== Collaboration Policy ===
Line 45: Line 46:
  
 
=== Course Texts ===
 
=== Course Texts ===
There are two required textbooks:
+
There is only one required textbook, which is freely available on the web:  
* David A. Forsyth and Jean Ponce, ''Computer Vision: A Modern Approach'' (2nd Edition), Prentice Hall, 2011.
+
* <b> Planning Algorithms</b> by <em> Steve LaValle</em> (Cambridge Univ. Press, New York, 2006).
** [http://www.cds.caltech.edu/~murray/courses/me132-wi12/caltech/Forsyth_1st_edition_ch1.pdf Chapter 1] (Caltech access only)
+
* The [http://msl.cs.uiuc.edu/planning book website is here];  If you plan to continue work in the field of robotics, then you should consider buying the text (the last time I checked, it was reasonably priced).  Information is available on the book website.
* Sebastian Thrun, Wolfram Burgard, and Dieter Fox, ''Probabilistic robotics'', MIT Press, 2005.
+
 
Additionally, there is an optional textbook that is available as a free download
+
Some of the course material on <em> sensor-based robot motion planning </em> is better covered in this <em> optional </em>
* Richard Szeliski, [http://szeliski.org/Book/ ''Computer Vision: Algorithms and Applications''], Springer, 2010.
+
reference book:
 +
* <b> Principles of Robot Motion: Theory, Algorithms, and Implementation</b>, by <em> H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki, and S. Thrun </em>, MIT Press, 2007.
 +
* An on-line [http://biorobotics.ri.cmu.edu/book/booboo_book.pdf Errata Page] is available.
 +
 
 +
The Thrun, Burgard, and Fox book used last quarter will continue to be a useful optional reference.  If you have bought the book, then hold on to it for this quarter.  If you haven't yet got the book, it is not necessary to purchase it, as there is very little specific information from that text that is needed this quarter.  This book is most likely to come in handy for some choices of final project.
  
== Lecture Notes ==  
+
== Lecture Schedule/handouts/homeworks/lab ==  
 
{| border=1 width=85%
 
{| border=1 width=85%
 
|Week
 
|Week
Line 58: Line 63:
 
|Topic
 
|Topic
 
|Reading
 
|Reading
|Instructor
+
|Homework
 
|-
 
|-
 
|rowspan=2 align="center" | 1
 
|rowspan=2 align="center" | 1
|8 Jan (Tu)
+
|2 Apr (Tu)
|[http://www.cds.caltech.edu/~yhhuang/lectures/lecture1.pdf Course Overview, Illumination, Radiometry]
+
|Course Overview, Intro. to Motion Planning
|Forsyth 2.1, 3.1, 3.2
+
|Lavalle Chapter 1
|Larry Matthies
+
| -N/A-
 
|-
 
|-
|10 Jan (Th)
+
| 4 Apr (Th)
|[http://www.cds.caltech.edu/~yhhuang/lectures/lecture2.pdf Cameras and Calibration]
+
| <b> No Class on this date </b>
|Forsyth Ch. 1
+
| Lavalle Chapter 1
|Larry Matthies
+
| -N/A -
 
|-
 
|-
 
|rowspan=2 align="center" | 2
 
|rowspan=2 align="center" | 2
|15 Jan (Tu)
+
| 9 Apr (Tu)
|[http://www.cds.caltech.edu/~yhhuang/lectures/lecture3.pdf Radiometry, Reflectance, and Color]
+
| Configuration Space Obstacles (c-obstacles)
|Forsyth 3.3, 3.4, 3.5
+
| Lavalle Chapter 4.3 (starting on Page 155) on Configuration Space Obstacles
|Larry Matthies
+
|
 
|-
 
|-
|17 Jan (Th)
+
| 11 Apr (Th)
|[http://www.cds.caltech.edu/~yhhuang/lectures/lecture4.pdf Low Level Image Processing]
+
| C-Obstacles (cont.) and overview of c-space planning
|Forsyth 4.1, 4.2, 4.5
+
| [[media:StarAlgorithm.pdf| Notes on the Star Algorithm]]; [[media:cobstacle.pdf | Notes on configuration space Obstacles]]
|Roland Brockers
+
| [[media:ME132Homework1.pdf | Homework 1]] <br> '''due 04/19/13'''
 
|-
 
|-
 
|rowspan=2 align="center" | 3
 
|rowspan=2 align="center" | 3
|22 Jan (Tu)
+
| 16 Apr (Tu)
|[http://www.cds.caltech.edu/~yhhuang/lectures/lecture5.pdf Feature Detection and Matching]
+
| Parametrizing Configuration Space Obstacles, <br> Intro to Classical Motion Planning
|Forsyth ch 5
+
| [[media:cobstacle_param.pdf | Notes on parametrizing c-obstacles]]
|Roland Brockers
+
|
 
|-
 
|-
|24 Jan (Th)
+
| 18 Apr (Th)
|[http://www.cds.caltech.edu/~yhhuang/lectures/lecture6.pdf Stereo Vision]
+
| Classical Motion Planning: roadmaps and the Visibility Graph
|Forsyth ch 7
+
| Lavalle 250-251, 261-264
|Roland Brockers
+
|  
 
|-
 
|-
 
|rowspan=2 align="center" | 4
 
|rowspan=2 align="center" | 4
|29 Jan (Tu)
+
| 23 Apr (Tu)
|[http://www.cds.caltech.edu/~yhhuang/lectures/lecture7.pdf Tracking and Outlier Detection]
+
| More Roadmaps: The Voronoi Diagram
|Forsyth 10.4, 11
+
|
|Yang Cheng
+
| [[media:ME132Homework2.pdf | Homework 2]] <br> '''due 05/02/13'''
 
|-
 
|-
|31 Jan (Th)
+
| 25 Apr (Th)
|[http://www.cds.caltech.edu/~yhhuang/lectures/lecture8.pdf Structure from motion and visual odometry]
+
| Cell Decomposition and Approximation Cell Decomposition
|Forsyth ch 8
+
| Lavalle 264-280
|Adnan Ansar
+
|
 
|-
 
|-
 
|rowspan=2 align="center" | 5
 
|rowspan=2 align="center" | 5
|5 Feb (Tu)
+
| 30 Apr (Tu)
|[http://www.cds.caltech.edu/~yhhuang/lectures/lecture9.pdf Overview of Range Sensors, Introduction to Lab 1]
+
| Voronoi Diagrams continued and Potential Field Methods 
|Forsyth ch 14
+
|  
|Jeremy Ma
+
|  
 
|-
 
|-
|7 Feb (Th)
+
| 2 May (Th)
|No Class (Lab 1)
+
| Graph Searching Methods.
|
+
| Lavalle pages 28-39
|
+
|
 
|-
 
|-
 
|rowspan=2 align="center" | 6
 
|rowspan=2 align="center" | 6
|12 Feb (Tu)
+
| 7 May (Tu)
|No Class (Lab 1)
+
| ''No Class'' (travel to ICRA conference)  
|
+
| -N/A-
|
+
| [[media:Lab1.pdf | Lab 1]]
 
|-
 
|-
|14 Feb (Th)
+
| 9 May (Th)
|Introduction to Estimation, [http://www.cds.caltech.edu/~yhhuang/lectures/notes_est.pdf Notes on Estimation]
+
| ''No Class'' (travel to ICRA conference) 
|Thrun 1, 2
+
| -N/A-
|Paul Hebert
+
| -N/A-
 
|-
 
|-
 
|rowspan=2 align="center" | 7
 
|rowspan=2 align="center" | 7
|19 Feb (Tu)
+
| 14 May (Tu)
|Linear Kalman Filter, [http://www.cds.caltech.edu/~yhhuang/lectures/notes_est_2.pdf Notes on Kalman Filters], [http://www.cds.caltech.edu/~yhhuang/lectures/auton_car_kf.m Car example], [http://www.cds.caltech.edu/~yhhuang/lectures/moon_lander_kf.m Moon Lander example]  
+
| The '''Bug''' Algorithms.
|Thrun 3.2
+
| Slides on [[media:BugSlides.pdf | Slides on the Bug Algorithms]];
|Nick Hudson
+
|  
 
|-
 
|-
|21 Feb (Th)
+
| 16 May (Th)
|[http://www.cds.caltech.edu/~yhhuang/lectures/lecture12.pdf Extended Kalman Filter], [http://www.cds.caltech.edu/~yhhuang/lectures/EKF_ackermann.m EKF example], [http://www.cds.caltech.edu/~yhhuang/lectures/UKF_ackermann.m UKF example]  
+
| Tangent Bug
|Thrun 3.3
+
| [[media:BugSlides.pdf | Slides on the Bug Algorithms]]; [[media:TangentBug.pdf | Tangent Bug Paper by Kamon, Rimon, and Rivlin]];
|Nick Hudson
+
| -N/A-
 
|-
 
|-
 
|rowspan=2 align="center" | 8
 
|rowspan=2 align="center" | 8
|26 Feb (Tu)
+
|21 May (Tu)
|[http://www.cds.caltech.edu/~yhhuang/lectures/lecture13.pdf Particle Filter and Unscented Kalman Filter], [http://www.cds.caltech.edu/~yhhuang/lectures/ParticleFilterTutorial.pdf Particle Filter Notes]
+
| On-line generation of the Voronoi Diagram   
|Thrun 3.4
+
|  
|Nick Hudson
+
|
 
|-
 
|-
|28 Feb (Th)
+
|23 May (Th)
|Vision and Space Systems
+
| D* Algorithm, Intro to Sample Based Planners 
 +
|
 
|
 
|
|Yang Cheng
 
 
|-
 
|-
 
|rowspan=2 align="center" | 9
 
|rowspan=2 align="center" | 9
|5 Mar (Tu)
+
|28 May (Tu)
|[http://www.cds.caltech.edu/~yhhuang/lectures/lecture14.pdf Examples, Intro to Mapping], [http://www.cds.caltech.edu/~yhhuang/lectures/icra2012.pdf Paper on LS3 Robot] [http://www.cds.caltech.edu/~yhhuang/lectures/icra2012_ws.pdf Paper on Mapping]
+
| Sample-Based Planners continued, intro to SLAM   
|Thrun 9
+
|  
|Jeremy Ma
 
|-
 
|7 Mar (Th)
 
|[http://www.cds.caltech.edu/~yhhuang/lectures/lecture15.pdf Occupancy Grid Maps, Intro to Lab 2]
 
|
 
 
|
 
|
 
|-
 
|-
|align="center" | 10
+
|30 May (Th)
|12 Mar (Tu)
+
| SLAM 
|No class (Lab 2)
+
|  
|
 
 
|
 
|
 
|}
 
|}
  
== Homework ==
+
== Homework/Labs ==
Please pay attention to the [http://www.cds.caltech.edu/~yhhuang/homework/implementation_guidelines.pdf implementation guidelines] when writing code for homework.
+
* [[media:ME132Homework1.pdf | Homework 1]]
 +
** '''Subject:'''  configuration space obstacles of planar polygonal bodies.
 +
** '''Due Date:''' Friday, April 19, 2013 by 5pm.
 +
** '''Solution:''' [[media:HW1Solution.zip | Homework 1 Solution]]
 +
* [[media:ME132Homework2.pdf | Homework 2]]
 +
** '''Subject:'''  2D roadmaps.
 +
** '''Due Date:''' Thurs, May 2, 2013 by 5pm.
 +
** '''Solution:''' [[media:set2.tar.gz | Homework 2 Solution]]
 +
* [[media:Lab1.pdf | Lab 1]]
 +
** '''Subject:'''  Wall Following.
 +
** '''Due Date:''' Thurs, May 16, 2013 by 5pm.
 +
** '''Template Code:''' [[media: sp2013_lab01_material.zip | This]] takes care of (most of) the occupancy grid and is one way to started. Change planning.png in the configs folder to change the obstacles in Player/Stage. The only parts you have to follow are those that interface your code with the robot. We care about seeing the robot navigate around an L-shaped obstacle and that your code is commented so we can understand what you're doing.
 +
 
 +
== Final Project Information ==
 +
* [[media: FinalProject.pdf | Final Project]]
 +
** '''Preproposal Due Date:''' Tues, May 21, 2013 by 5pm (in hard copy) to Joel Burdick (TOM 319)
 +
** '''Project Due Date:''' Fri, June 14, 2013 by 5pm (June 10 by 7am for seniors) to Maria Koeper (TOM 321, under her door if she's not in)
  
*[http://www.cds.caltech.edu/~yhhuang/homework/homework1.pdf Homework 1] - Due: Tue Jan 22 at 11:59pm ([http://www.cds.caltech.edu/~yhhuang/solutions/Solution1.pdf Solutions ])
+
* The Original [http://robotics.caltech.edu/~jwb/courses/ME132/handouts/LumelskyBug.pdf Lumelsky Bug Algorithm] paper.
**[http://www.cds.caltech.edu/~yhhuang/homework/Forsyth1.2_2ndEd.pdf Ch. 1.2 of Forsyth (2nd Edition)] - equations for problem 3
+
* Early papers on the D* AlgorithmL [http://robotics.caltech.edu/~jwb/courses/ME132/handouts/Dstar_icra94.pdf ICRA 94]; [http://robotics.caltech.edu/~jwb/courses/ME132/handouts/Dstar_ijcai95.pdf IJCAI 95];[http://robotics.caltech.edu/~jwb/courses/ME132/handouts/Dstar_aaai96.pdf AAAI 96];
*[http://www.cds.caltech.edu/~yhhuang/homework/homework2.pdf Homework 2] - Due: Tue Jan 29 at 11:59pm ([http://www.cds.caltech.edu/~yhhuang/solutions/Solution2.zip Solutions ])
 
**[http://www.cds.caltech.edu/~yhhuang/homework/homework2_images.zip Homework 2 Images]
 
*[http://www.cds.caltech.edu/~yhhuang/homework/homework3.pdf Homework 3] - Due: Thurs Feb 7 at 11:59pm ([http://www.cds.caltech.edu/~yhhuang/solutions/Solution3.zip Solutions ])
 
**[http://www.cds.caltech.edu/~yhhuang/homework/homework3_data.zip Homework 3 Data]
 
*Lab 1: Due: Fri Feb 15 at 11:59pm - email to me132-tas@caltech.edu
 
**[http://www.cds.caltech.edu/~yhhuang/homework/lab01.pdf Lab Description]
 
**[http://www.cds.caltech.edu/~yhhuang/homework/lab01_material.zip Lab Material]
 
**[https://www.cds.caltech.edu/~murray/wiki/index.php/ME/CS_132a,_Winter_2013,_Lab_1_Sign-Up Sign up page]
 
**[https://www.cds.caltech.edu/~murray/wiki/index.php/ME/CS_132a,_Winter_2013,_Lab_1 Additional Instructions]
 
*[http://www.cds.caltech.edu/~yhhuang/homework/homework4.pdf Homework 4] - Due: Thurs Feb 21 at 11:59pm ([http://www.cds.caltech.edu/~yhhuang/solutions/Solution4.m Solutions ])
 
**[http://www.cds.caltech.edu/~yhhuang/homework/ME132_DB.m Homework 4 matlab code]
 
*[http://www.cds.caltech.edu/~yhhuang/homework/homework5.pdf Homework 5] - Due: Tue Mar 5 at 11:59pm - turn in set to Ilya (ilyanep@caltech.edu)
 
**[http://www.cds.caltech.edu/~yhhuang/homework/homework5_material.zip Homework 5 material]
 
*Lab 2: Due: Fri Mar 15 at 11:59pm - email to me132-tas@caltech.edu
 
**[http://www.cds.caltech.edu/~yhhuang/homework/lab02.pdf Lab2 Description]
 
**[http://www.cds.caltech.edu/~yhhuang/homework/lab02_material.zip Lab Material]
 
**[https://www.cds.caltech.edu/~murray/wiki/index.php/ME/CS_132a,_Winter_2013,_Lab_2_Sign-Up Sign up page]
 
**[http://www.cds.caltech.edu/~yhhuang/homework/LMSTechnicalDescription.pdf Laser Scanner Spec Sheet]
 
**[http://www.cds.caltech.edu/~yhhuang/homework/forward_model_thrun.pdf Forward Sensor Models (for 3-person group)]
 

Latest revision as of 21:34, 6 June 2013

Advanced Robotics: Navigation and Vision

Instructors

  • Joel Burdick, jwb@robotics.caltech.edu
  • Lectures: Tue/Thu, 2:30-4 pm, 206 TOM
  • Office hours: After class/by appointment

Teaching Assistants (me132-tas@caltech.edu)

  • Alex Jose (ajose@caltech.edu)
  • Mary Nguyen (mary.nguyen@caltech.edu)
  • Office hours: By appointment

Course Mailing List: me132-students@caltech.edu (sign up)

  • This list has been updated. If you did not receive a subscription email, please subscribe using the link.

Announcements

Course Information

Prerequisites

There are no formal prerequisites for the course, other than ME/CS 132(a). Some of the required background material will be reviewed during the first weeks of lecture. The theory part of ME/CS 132(b) is largely independent of the material in ME/CS 132(a), but students are expected to be able to use the experimental lab equipment introduced in the first quarter of the course, and are expected to be able to apply the sensor processing and mapping techniques learned in the first quarter. The greater emphasis on a final project in this quarter will require a good comfort level with computer programming in at least one of the following languages: C, C++, Python, or MATLAB.

Grading

ME/CS 132(b) is primarily a project-based course. The grade will be based on 2 homeworks (20% of total grade) and two week-long labs (10% of total grade each). Sixty percent (60%) of the grade will be based on a final project which is due on the last day of the finals period. The final project can potentially be done in teams, with the instructor's approval.

  • Homework: Homework is usually due in one week after it is assigned. You can choose to turn in a hard copy in class or send an electronic copy to the TAs (me132-tas at caltech.edu). If you are unable attend the lecture, contact the TAs to find an alternative way to turn in your homework.
  • Labs: Students will form groups of 2-3 people and perform lab experiments together. The lab will consist of implementing and testing basic algorithms on a mobile robot, and demonstrating the result, as well as submitting a copy of the code underlying the lab demonstration. The one-week labs this quarter are intended to help get the students prepared for the final project.

Collaboration Policy

Students are encouraged to discuss and collaborate with others on the homework. However, you should write your own solution to show your own understanding of the material. You should not copy other people's solution or code as part of your solution. You are allowed to consult the instructors, the TAs, and/or other students. Outside reference materials can be used except for solutions from prior years or similar courses taught at other universities. Outside materials must be cited if used.

Course Texts

There is only one required textbook, which is freely available on the web:

  • Planning Algorithms by Steve LaValle (Cambridge Univ. Press, New York, 2006).
  • The book website is here; If you plan to continue work in the field of robotics, then you should consider buying the text (the last time I checked, it was reasonably priced). Information is available on the book website.

Some of the course material on sensor-based robot motion planning is better covered in this optional reference book:

  • Principles of Robot Motion: Theory, Algorithms, and Implementation, by H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki, and S. Thrun , MIT Press, 2007.
  • An on-line Errata Page is available.

The Thrun, Burgard, and Fox book used last quarter will continue to be a useful optional reference. If you have bought the book, then hold on to it for this quarter. If you haven't yet got the book, it is not necessary to purchase it, as there is very little specific information from that text that is needed this quarter. This book is most likely to come in handy for some choices of final project.

Lecture Schedule/handouts/homeworks/lab

Week Date Topic Reading Homework
1 2 Apr (Tu) Course Overview, Intro. to Motion Planning Lavalle Chapter 1 -N/A-
4 Apr (Th) No Class on this date Lavalle Chapter 1 -N/A -
2 9 Apr (Tu) Configuration Space Obstacles (c-obstacles) Lavalle Chapter 4.3 (starting on Page 155) on Configuration Space Obstacles
11 Apr (Th) C-Obstacles (cont.) and overview of c-space planning Notes on the Star Algorithm; Notes on configuration space Obstacles Homework 1
due 04/19/13
3 16 Apr (Tu) Parametrizing Configuration Space Obstacles,
Intro to Classical Motion Planning
Notes on parametrizing c-obstacles
18 Apr (Th) Classical Motion Planning: roadmaps and the Visibility Graph Lavalle 250-251, 261-264
4 23 Apr (Tu) More Roadmaps: The Voronoi Diagram Homework 2
due 05/02/13
25 Apr (Th) Cell Decomposition and Approximation Cell Decomposition Lavalle 264-280
5 30 Apr (Tu) Voronoi Diagrams continued and Potential Field Methods
2 May (Th) Graph Searching Methods. Lavalle pages 28-39
6 7 May (Tu) No Class (travel to ICRA conference) -N/A- Lab 1
9 May (Th) No Class (travel to ICRA conference) -N/A- -N/A-
7 14 May (Tu) The Bug Algorithms. Slides on Slides on the Bug Algorithms;
16 May (Th) Tangent Bug Slides on the Bug Algorithms; Tangent Bug Paper by Kamon, Rimon, and Rivlin; -N/A-
8 21 May (Tu) On-line generation of the Voronoi Diagram
23 May (Th) D* Algorithm, Intro to Sample Based Planners
9 28 May (Tu) Sample-Based Planners continued, intro to SLAM
30 May (Th) SLAM

Homework/Labs

  • Homework 1
    • Subject: configuration space obstacles of planar polygonal bodies.
    • Due Date: Friday, April 19, 2013 by 5pm.
    • Solution: Homework 1 Solution
  • Homework 2
  • Lab 1
    • Subject: Wall Following.
    • Due Date: Thurs, May 16, 2013 by 5pm.
    • Template Code: This takes care of (most of) the occupancy grid and is one way to started. Change planning.png in the configs folder to change the obstacles in Player/Stage. The only parts you have to follow are those that interface your code with the robot. We care about seeing the robot navigate around an L-shaped obstacle and that your code is commented so we can understand what you're doing.

Final Project Information

  • Final Project
    • Preproposal Due Date: Tues, May 21, 2013 by 5pm (in hard copy) to Joel Burdick (TOM 319)
    • Project Due Date: Fri, June 14, 2013 by 5pm (June 10 by 7am for seniors) to Maria Koeper (TOM 321, under her door if she's not in)