CSCE 643-601: Seminar in Intelligent Systems and Robotics—Planning Focus
Instructor: Dr. Dylan Shell
| Office | : | Peterson 315 |
| Phone | : | (979) 845-2369 |
| : | dshell_at_tamu.edu | |
| Web | : | http://robots.cs.tamu.edu/dshell |
| Office hours | : | Thursdays 11:00am–noon, or by email appointments |
Spring 2025
| Time | : | Mon/Wed/Fri, 1:50pm-2:40pm |
| Location | : | HRBB 126 |
Course Description
Catalog Description: Problems, methods and recent developments in intelligent systems and robotics.
This offering of the course will focus on planning algorithms for robots, including some treatment of algorithms and challenges underlying estimation and planning, with the focus on motion planning, task planning, and their combination. Depending upon interest expressed within the class: synthesis techniques from formal methods for robots, fundamentals of reinforcement learning, and other recent developments (Google SayCan, RT-2, etc.)
Detailed Description
This course is a seminar-style survey of issues and approaches to planning in robot systems. Although the subject area is focused on robotics, it is an explicit goal of this course to advance students' critical thinking and communication skills. This will be achieved through discussions, presentations, and a final research paper (as a writing component).
Students will read a fundamentals-oriented textbook and original papers within the field, tracing the development, from early seminal contributions through subsequent developments to recent papers; they will gain a breadth of understanding through discussion and will sample particular approaches through representative case studies.
Students are expected to read all of the readings, with the exception of those marked optional. Each of the textbook chapters and papers will be discussed and critiqued by everyone in the class, with one person assigned as the lead for each item (chapter or paper). The student leading the discussion of the material in a given class should prepare a clear 10-minute overview and summary. The instructor will guide discussion, interactively raising points needing clarification and posing questions for the group.
For each topic being covered on a given day, each student (whether the lead or not) should bring to class their version of the paper (either in hard-copy or electronic form) including notes that they have made. The notes might be in the form of annotations on the material or separate text and/or diagrams, but should aim to include several queries and critiques which can be contributed to the discussion. (These notes are to serve as reminders to their authors—they are not required to be publicly shared.) Preparation for each class is part of the participation grade as what you're being assessed on is evidence of serious, thoughtful criticism of the chapters/papers.
The final project reports are intended to be written in the same tone as the topics read in class, in other words: a technical report with algorithmic content. The intention is that these include some original content. The course will be structured so that there will be writing and project sub-goals along the way.
In summary, for each class, you should bring:
- Printouts or digital versions of the papers being discussed;
- If you are to lead the discussion, a concise organized summary;
- Your personal notes, thoughts on and questions regarding the material you read;
- Great enthusiasm for discussing all of the topics.
Prerequisites
The only formal requirement is approval of the instructor. In practice, some (undergraduate-level) experience design and analysis of algorithms. Ideally a student will have had some contact with Complexity Theory (NP-Hardness, SAT, etc.), or be willing to pick up these aspects. (Please simply send an e-mail to the instructor or visit during the first class, if in doubt.)
Course Learning Outcomes
The following are the learning goals of this course:-
- Students should be able to list and explain the current techniques for planning for robots and related systems.
- Students should gain an appreciation for the development and process by which the state-of-the- art has been arrived at.
- Students will hone critical thinking and communication skills (including technical discussion, presentation and writing).
Texts
All the readings will be provided with full citations. Digital versions will be either easy to find, or will be made available from the class website. (If you have any doubt, please feel free to contact the instructor for help locating the document.)
We will start with the following textbook:
- Planning Algorithms, Steven M. LaValle, Cambridge Press, 2006.
Students who need (or wish) to read more widely to gain a thorough understanding of the material in the papers we will discuss later in the course, may find the following books to be useful in this regard:—
- Introduction to AI Robotics, Robin Murphy, MIT Press, 2000.
- Autonomous Robots, George Bekey, MIT Press, 2006.
- Probabilistic Robotics, Sebastian Thurn, Wolfram Burgard and Dieter Fox, MIT Press, 2005.
- The Sciences of the Artificial, Herbert Simon, MIT Press, Third edition, 1996.
- Swarm intelligence: From Natural to Artificial Systems, Eric Bonabeau, Marco Dorigo, and Guy Theraulaz, MIT Press, 1999.
In the second phase of the class, we will discuss research papers (items in proceedings from peer-reviewed conferences, journal articles, and technical reports). The current list of topics for papers includes the following topics: RRT*, sub-dimensional expansion, construction of certificates, minimum constrain removal, plans via randomness, active perception, TAMP, cycle swaps, topological constraints, hybrid methods, language-models as plans.
Calendar of readings
| Week | Description | |
|---|---|---|
| 1. | Jan 13/15/17 | Introduction / Ch. 1 / Ch. 2.1–2.3 |
| 2. | Jan (no class)/22/24 | (no reading) / Ch 2.4–Ch 2.5 / Ch.3.1–3.3 |
| 3. | Jan (no class)/29/31 | (no reading) / Ch. 3.4–3.5 / Ch. 4.1 |
| 4. | Feb 3/5/7 | Ch. 4.2–4.4 / Ch. 5.1–5.3 / Ch. 5.4–5.6 |
| 5. | Feb 10/12/14 | Ch. 6.1–6.2 / Ch. 6.3–6.5 / Ch. 7.1–7.3 |
| 6. | Feb 17/19/21 | Ch. 7.4–7.7 / Ch. 8 / Ch. 9.1–9.3 |
| 7. | Mar 3/5/7 | Ch. 9.4–9.5 / Ch. 10.1–10.3 / Ch. 10.4–10.6 |
| 8. | Mar 10/12/14 | [Spring break] |
| 9. | Mar 17/19/21 | Ch. 11.1–11.5 / Ch. 11.6–11.7 / Ch. 12.1–12.3 |
| [Final Paper Topic: Proposed] | ||
| 10. | Mar 24/26/28 | Ch. 12.4–12.5 / Paper discussion (details below) |
| 11. | Mar 31/Apr 2/4 | Paper discussion (details below) |
| 12. | Apr 7/9/11 | Paper discussion (details below) |
| [Paper Draft Submitted] | ||
| 13. | Apr 14/16/(no class) | Paper discussion (details below) |
| 14. | Apr 21/23/25 | Paper discussion (details below) |
| 15. | Apr 28 | [Final Paper Writing] |
These are examples (subject to change until assignment based on topic interest, class discussion)
| Sampling-based Algorithms for Optimal Motion Planning by Sertac Karaman, Emilio Frazzoli. The International Journal of Robotics Research, 30(7):846 2011. | ||
| Learning Proofs of Motion Planning Infeasibility by Sihui Li and Neil T. Dantam, Robotics: Science and Systems July 2021. | ||
| What are plans for? by Philip E. Agre and David Chapman. Robotics and Autonomous Systems, 6(1–2):17 1990. | ||
| The Minimum Constraint Removal Problem with Three Robotics Applications by Kris Hauser. The International Journal of Robotics Research, 33(1):5 2014. | ||
| Conflict-based search for optimal multi-agent pathfinding by Guni Sharon, Roni Stern, Ariel Felner, Nathan R Sturtevant. Artificial Intelligence, 219:40 2015. | ||
| Toward a deeper understanding of motion alternatives via an equivalence relation on local paths by Ross A Knepper, Siddhartha S Srinivasa and Matthew T. Mason. The International Journal of Robotics Research, 31(2):167 2012. | ||
| Online Coverage by a Tethered Autonomous Mobile Robot in Planar Unknown Environments by Iddo Shnaps and Elon Rimon, IEEE Transactions on Robotics, 30(4):966, 2014. | ||
| Integrated Task and Motion Planning by Caelan Reed Garrett, Rohan Chitnis, Rachel Holladay, Beomjoon Kim, Tom Silver, Leslie Pack Kaelbling, Tomás Lozano-Pérez. Annual Review of Control, Robotics, and Autonomous Systems, 4:265, 2021. | ||
| Winding Through: Crowd Navigation via Topological Invariance by Christoforos Mavrogiannis, Krishna Balasubramanian, Sriyash Poddar, Anush Gandra, Siddhartha S. Srinivasa.IEEE Robotics and Automation Letters, 8(1):121, 2023. | ||
| Topological complexity of motion planning by Michael Farber, Discrete & Computational Geometry, 29: 211 2003 (see also Topology of Robot Motion Planning). | ||
| Demonstrating Large Language Models on Robots Google DeepMind. Robotics: Science and Systems, July 2023. | ||
| Sensorless Pose Determination Using Randomized Action Sequences by Pragna Mannam, Alexander Volkov Jr., Robert Paolini, Gregory S. Chirikjian, Matthew T. Mason. Entropy, 21(2):154 2019. | ||
| Control Barrier Functions for Signal Temporal Logic Tasks by Lars Lindemann and Dimos V. Dimarogonas. IEEE control systems letters, 3(1):96 2018. | ||
| Complexity Results and Fast Methods for Optimal Tabletop Rearrangement with Overhand Grasps by S. D. Han, N. Stiffler, A. Krontiris, K. Bekris, and J. Yu. The International Journal of Robotics Research, 37(13):1775 2018. | ||
| On the Expressivity of Markov Reward by David Abel, Will Dabney, Anna Harutyunyan, Mark K Ho, Michael Littman, Doina Precup, Satinder Singh. NeurIPS 2021. |
The final paper is due is due Monday, April 28, 2025 at midnight (submission via e-mail to the instructor).
Assessment
Course grades will be based on the following components:—
| Participation and engagement during class time | : | 50% |
| Research paper | : | 50% |
Notice, the significant weight given to participation: as a seminar-style course, students are expected to demonstrate active engagement (this depends upon, of course, being prepared for class, including preparation of several serious critique) and also to miss only few sessions. Unless circumstances are particularly extreme, it is expected that a person who is to lead the discussion, but is forced to be absent that day, shall find a suitable replacement (e.g., by negotiating to swap with somebody else). Prior arrangements with the instructor must be made when feasible and official verification of circumstances necessitating the absence will be required.
The portion of the grade devoted to the research paper reflects cumulative effort across the semester: from identification of a topic, drafting of a initial formulation, review and refinement, along with quality of the final report. Assessment will consider the sophistication of the algorithmic problem being treated, insight and creativity, care with which language and logical argument have been mustered to explain the problem and to explore the topic. Ideally, as a piece of technical writing, the report would be shaped through learning from the material read throughout the semester, including things identified as good (which should be adopted) and bad (to be avoided).
Please seek assistance immediately if you are having difficulty with the course. Help that will be effective can only be made available from the instructor if he is notified promptly.
Students with Disabilities
The Americans with Disabilities Act (ADA) is a federal anti-discrimination 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 Disability Services, in Cain Hall, Room B118, or call (979) 845-1637. For additional information visit http://disability.tamu.edu.
Academic Integrity
This course has a zero-tolerance policy to academic misconduct of any kind including: cheating, fabrication, falsification, multiple submissions, plagiarism. Ignorance of the rules does not exclude any student from the requirements or the processes of the Honor System. Definitions and further information is at http://www.tamu.edu/aggiehonor. Note in particular the seriousness of the disciplinary action.
For further details, please refer to the syllabus document.