Spring 2023/2024, 0368-3412-01
Instructor: Dan Halperin, [email protected]
Office hours by appointment
Course hours: Monday, 17:00-19:00
Location: Orenstein 111
The first meeting of the seminar on Robot Algorithms will be held on the coming Monday, May 27th, 2024, at 17:10 in Orenstein 111. In this meeting I’ll give a brief introduction to the topic, I’ll review the seminar requirements and the various topics of the talks.
In-person attendance is mandatory! If you cannot attend ALL the meetings, please contact me in advance, as this may influence your grade or your ability to get a grade in the seminar altogether.
The students’ talks at the seminar are arranged in topics, one topic per week. Therefore I’m asking you to bid for topics in pairs. Eventually, after you split the subtopics between you, each student will be expected to give a talk of roughly 40 minutes.
Your slides are expected to be in English, and you are encouraged to give the talk in English.
The grade will be based on the quality of the talk (but not on the quality of the English), the presentation, the understanding of the material, and the attendance of and comments on other students’ talks.
You can already send me a message to [email protected] to ask for a topic. Let me mention that the first two topics are more basic and presumably easier to present, taking into account that students will have less time to prepare for these talks.
Notice that you can access papers through the library website. If it is an arxiv paper, then it is directly available from https://arxiv.org/.
Topics
Topic 1: Probabilistic roadmaps (PRM)
Lydia E. Kavraki, Petr Svestka, Jean-Claude Latombe, Mark H. Overmars:
Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robotics Autom. 12(4): 566-580 (1996)Probabilistic completeness proof:
Lydia E. Kavraki, Mihail N. Kolountzakis, Jean-Claude Latombe:
Analysis of probabilistic roadmaps for path planning. ICRA 1996: 3020-3025The algorithm may be better presented as it is in Chapter 7 of the book:
H. Choset, K.M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L.E. Kavraki, and S. Thrun, Principles of Robot Motion:
Theory, Algorithms, and Implementations, The MIT Press, 2005
Sampling-Based Motion Planning: A Comparative Review. Annu. Rev. Control. Robotics Auton. Syst. 7(1) (2024)
Motions in Microseconds via Vectorized Sampling-Based Planning. CoRR abs/2309.14545 (2023)
Topic 2: Rapidly exploring random trees (RRT)
The early papers:
(1) James J. Kuffner Jr., Steven M. LaValle:
RRT-Connect: An Efficient Approach to Single-Query Path Planning. ICRA 2000: 995-1001
(2) Steven M. LaValle, James J. Kuffner Jr.:
Randomized Kinodynamic Planning. Int. J. Robotics Res. 20(5): 378-400 (2001)
Probabilistic completeness proof:
Section III (the geometric case) in Version 2 (2022) of
Michal Kleinbort, Kiril Solovey, Zakary Littlefield, Kostas E. Bekris, Dan Halperin:
Probabilistic completeness of RRT for geometric and kinodynamic planning with forward propagation. CoRR abs/1809.07051 (2018)
Topic 3: Collision detection
Clayton W. Ramsey, Zachary Kingston, Wil Thomason, Lydia E. Kavraki
Topic 4: Learning robot grasping policies
Matthew Matl, Vishal Satish, Michael Danielczuk, Bill DeRose, Stephen McKinley, Ken Goldberg:
Learning ambidextrous robot grasping policies. Sci. Robotics 4(26) (2019)
Provide background material from other relevant papers on learning for grasping.
Topic 5: Convex cover of free (configuration) space
Peter Werner, Alexandre Amice, Tobia Marcucci, Daniela Rus, Russ Tedrake:
Approximating Robot Configuration Spaces with few Convex Sets using Clique Covers of Visibility Graphs. CoRR abs/2310.02875 (2023)
See also ICRA 2024
Also relevant:
Mikkel Abrahamsen, William Bille Meyling, André Nusser:
Constructing Concise Convex Covers via Clique Covers (CG Challenge). SoCG 2023: 66:1-66:9
Topic 6: Motion planning for large fleets of robots
Israela Solomon, Dan Halperin:
Motion Planning for Multiple Unit-Ball Robots in ℝd. CoRR abs/1807.05428 (2018)
(Demonstrate with the existing software.)
Topic 7: Legged robot navigation
Lorenz Wellhausen, Marco Hutter:
ArtPlanner: Robust Legged Robot Navigation in the Field. Field Robotics 3(1): 413-434 (2023)
(Open source software available.)