Planning Methods for Robots, Games and Biomolecules

CS 591

Jump to: navigation, search

CS 591 - 009

Download the Syllabus
NOTE: Class time change to Tues/Thurs 2:00-3:15

About This Course

Planning Algorithms are used in robotics, control theory, artificial intelligence, puzzles, games, algorithms, computer graphics, and even molecular motions. There have been many exciting developments in the planning field in the last few years, with current research focusing on the development of novel, efficient, and general algorithms for planning in these domains.

Each domain has different planning goals to achieve. In robotics, planning problems addresses problems such as uncertainty, coordinating multiple robots, and the integration with complex controls. In AI, planning helped find a way from a start state to a goal state. However, recent research has extended planning for puzzles and games through the use of information theory including Markov Decision Processes, imperfect state information, and game-theory. In biomolecules, planning is used to identify ways that molecules move in order to better understand diseases such as Mad Cow disease.

Even though these domains, games, robotics, and biomolecules, sound distinct, they share common ground in planning. In this course, we will discuss the current research in planning. In the process, each student will develop a project in planning that is suited to their domain interests.



Analysis, implementation, and comparison of planning algorithms, including complete, heuristic-based, and intelligent algorithms; examination of methods applied to multiple domains including robotics, gaming, and molecular motions. Graphical interface to visualize motions will also be explored.


Students need to be proficient at object oriented programming in either Java or C++. Students should have taken some higher level computer science courses. Possible courses include artificial intelligence or software engineering. Undergraduates interested in taking this course should speak with the instructor.


Each topic will take 1-2 weeks. Each topic will include reading of related papers; students will write a summary and discussion of each paper. Each student will prepare and deliver a presentation based on a current or historic research paper. For some topics, programmatic assignments will be assigned. Students will develop a final project as part of the course. Students will have to write up results in journal formal and present their results.


  • Homework: 50%
  • Topic Presentation: 10%
  • Project: 30%
  • Class Participation: 10%

All assignments will be announced in class and posted on the course web page. If you miss class for any reason, it is your responsibility to find out what assignments you missed.

No late homework assignments will be accepted. Please discuss unusual circumstances in advance with the instructor.

Submit your reports either in electronic format over email or printed directly to the instructor.

Note, that once the presentations for the project have been scheduled, they cannot be moved easily. Failure to present on time, will result in a lower final grade.


Students will be expected to do a term project. The possible topics vary widely. Possible topics include:

  1. Planning smooth camera motions in virtual environments
  2. Planning for a racing game
  3. Anytime planning, especially for systems with dynamics, such as cars, helicopters, airplanes, spaceships, etc.
  4. Replanning, especially for systems with dynamics
  5. Computing good quality paths for high-dimensional systems
  6. Sensor-based planning
  7. Planning under uncertainty
  8. Formation control
  9. Planning for mobile sensor networks or network-guided motion planning
  10. Planning with minimalistic information and representations
  11. Planning involved in protein folding

Students will write a description of their project expressing why the techniques used were appropriate and why. Students should also thoroughly evaluate their algorithm.

Academic Integrity: For everyone's benefit, students should uphold the guidelines in the University of New Mexico Student Code of Conduct.

For the assignments in this class, discussion of concepts with others is encouraged, but all assignments must be done on your own, unless otherwise instructed. If you use any source other than the text, reference it/him/her, whether it be a person, a book, a solution set, a web page or whatever. You MUST write up the solutions in your own words. Copying is strictly forbidden.

Americans with Disabilities Act (ADA) Policy Statement: The Americans with Disabilities Act (ADA) is a federal antidiscrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact the Department of Student Affairs, Accessibility Resource Center in Mesa Vista Hall, Rm. 2021.


Instructor: Prof. Lydia Tapia
Office: 349E
Office Hours: TR 2:15-4:30; other times by appointment
Office Phone: 505-277-0858

Course URL:

Lecture: Tuesday, Thursday 2:00-3:15 PM, Mitchell Hall 207 NOTE TIME CHANGE FROM 11:00-12:15 PM

Textbook: There is no assigned textbook for this class. Course material will come from reading current papers in planning. However, a useful reference textbook is:

Planning Algorithms
by Steve LaValle
Cambridge University Press, 2006
Available Online


Below is a tentative schedule for the semester. This schedule will be refined as the semester progresses.
Week of Topic Reading Optional Reading from Planning Algorithms*
8/23 Introduction to Planning J-C Latombe, Motion Planning: A Journey of Robots, Molecules, Digital Actors, and Other Artifacts, IJRR, 1999.
Chapter 1
8/30 Topic 1: Discrete and "2D" Planning J. Walter, J. Welch, and N.M. Amato Concurrent Metamorphosis of Hexagonal Robot Chains into Simple Connected Configurations IEEE Transactions on Robotics and Automation, 18(6):945-956, Nov 2002.
Chapter 2
9/6 Topic 2: 3D Planning/Sampling Based MP L. Kavraki, P. Svestka, J.-C. Latombe, M. Overmars. Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces
Chapter 4/5
9/13 Topic 3: Bug Planning Vaughan, R.T.; Stoy, K.; Sukhatme, G.S.; Mataric, M.J.; , LOST: localization-space trails for robot teams, Robotics and Automation, IEEE Transactions on , vol.18, no.5, pp. 796- 812, Oct 2002
Chapter 12
9/20 Topic 4: Extensions of Basic MP no paper this week
Chapter 7
9/27 Project discussions/Guest Lecture Tuesday: Project meetings;
Thursday: Guest Lecturer: Prof. Meeko Oishi
10/4 Topic 5: Tree-based Planning Tuesday: ICRA paper submissions day
Thursday: Robot motion planning using adaptive random walks
Chapter 9
10/11 Topic 5: Intelligent and Adaptive Planning  
Chapter 10
10/18 Topic 5: More Intelligent and Adaptive Planning
An unsupervised adaptive strategy for constructing probabilistic roadmaps
10/25 Topic 6: Planning and Games The 2009 Mario AI Competition More info on the competition is available here
11/1 Topic 7: Molecular MP no paper this week
11/8 Topic 8: Planning for Games A motion-planning approach to folding: from paper craft to protein folding
11/15 Locomotion Skills for Simulated Quadrupeds (PDF) Mechanical Part Assembly Planning with Virtual Mannequins
Chapter 14
11/22 Brendan Burns and Oliver Brock. Sampling-Based Motion Planning with Sensing Uncertainty. IEEE International Conference on Robotics and Automation, 2007. No class- Thanksgiving
11/29 Final Project Presentations Prof. Fierro on robot formations and flocking
12/6 Final Project Presentations  
*Optional Reading is for more details on a specific topic. However, it is not assigned.


Homework Assignments

There will be 1-2 short introduction to planning homework assignments. As they are announced, they will be posted here.

  • Due: To be determined
  • Requirements: To be determined
Each student will be required to submit a summary and discussion of a current paper in planning for each topic.
  • Due: before class begins on the day the paper is presented in class
  • Requirements: Aim for about one page. Either hardcopy can be turned in at the start of class or a electronic copy (PDF ONLY) can be emailed before class. The paper should have two clear sections, summary and discussion.

Topic Presentation

Each student will be responsible for presenting the results from one current paper in motion planning during a single topic.

  • Due: On the schedule date for that topic
  • Requirements: Papers selected for presentation must be approved by the instructor at least one week before presentation. The student will have about one hour to do the presentation and associated discussion of the paper. Students can use whatever electronic medium they prefer to do the presentation. But, when resources other than a VGA projector are required, students should first check with the instructor.

Final Project

Step 1: Project Proposal

  • Due: 9/15 (extended to 10/6)
  • Requirements: A short one paragraph writeup should be turned in with a description of the proposed project. Either hardcopy can be turned in at the start of class or a electronic copy (PDF ONLY) can be emailed before class.

Step 2: Project Proposal Presentation

  • Due: 10/11
  • Requirements: A short presentation should be prepared and presented in class describing your proposed (and now approved) project.

Step 3: Project Final Report Peer Review

  • Due: 11/22
  • Requirements: Drafts of the papers will be exchanged during the previous week by the instructor. The instructor will provide a form for the review. Students will turn in either a hardcopy at the start of class or email an electronic copy (PDF ONLY) before class.

Step 4: Project Final Presentations

  • Due: 11/29
  • Requirements: To be determined

Step 5: Project Final Report

  • Due: 12/8
  • Requirements: A journal style research report will be turned in. Students should use LATEX (see helpful links) to generate the report. Students will turn in either a hardcopy to the instructor or email an electronic copy (PDF ONLY) by the end of the day.


All course deadlines will be posted here at least one week before they are due.

Helpful Links

A motion planning interface Interesting Robotics Stories Robotics Planning Resources Latex Resources

a template

General Info on what you can do with LaTeX:
Getting Started with Latex
The Not So Short Introduction to Latex
Comprehensive List of Latex Symbols
Latex for Logicians

Tex on Max OS X

The first link describes many alternatives that are available for installing Tex on a Mac. The second link forwards to the MacTex package, one of the alternatives mentioned in the first website. MaxTex provides everything that you need to use Latex on Mac except from a text editor. It is, however, compatible with a wide variety of popular editors (e.g., Alpha, BBEdit, Emacs, VIM, iTeXMac, TeXShop). Note that MaxTex is a large package.

Carbon Emacs has been successfully tested with MacTex. After installing MacTex, it is possible to directly compile and view *.tex files from Carbon Emacs's UI.

Note for Mac users: You will probably have problems previewing your PDF output when using the postscript images provided by the instructor for developing the notes. Nevertheless, the PDF file can be printed properly. Prepare your document without the images and then add them. You will probably still be able to preview the intermediate .dvi output file with the "xdvi" program.

Linux (Ubuntu)
Latex on Ubuntu
Tex Live

You just have to download and install the proper packages described above (e.g., through apt-get), use your favorite editor (e.g., emacs) to prepare a *.tex file and then you compile (run at least two times: "latex filename.tex") to get the *.dvi output. You can go from dvi to postscript with the command "dvips" and you can convert postscript to pdf with the command "ps2pdf".

Latex for Windows help
MikTex (Latex for Windows)

If you follow the instructions on the first link you should be able to get it working on a Windows system.


Announcements will be posted here with the most recent on top