Posts

Analysis of Sampling-Based Planners: RRTs

Image
Continuing from my last blog post, I now want to look at the proof that the famous RRT algorithm (which stands for Rapidly-Exploring Random Tree ) is probabilistically complete (and the resulting bound on sample complexity that proof yields). On a somewhat-related note, I recently put out a preprint of my submission to IROS 2025. It examines sampling-based planning when the configuration space has discrete symmetries (such as those that arise when manipulating a symmetric object), and a key part of the paper is a theoretical analysis that suggests that various sampling-based planning algorithms should improve in performance when leveraging the underlying symmetries. Those analyses were built upon existing bounds (like the ones in this blog post and the previous one), so perhaps that gives a bit of a hint as to why I've been thinking about this stuff! The Rapidly-Exploring Random Tree (RRT) Algorithm Since Steven LaValle introduced the RRT algorithm in 1998, it has become one of t...
Post a Comment
Read more

Analysis of Sampling-Based Planners: PRMs

Image
It's been a while since I've done one of these! Turns out it can be hard to find the time to blog when PhD life gets busy. Today's blog post is the first in a series of several focused on the theoretical analysis of sampling-based planners. I'm currently making a push on an IROS paper that's dealing with sampling-based planning on a certain special class of manifolds, so I'm naturally thinking about the theoretical properties of these algorithms in that new domain. I also recently gave a short presentation to my lab about this subject, and figured I would convert those slides into a blog post. The Probabilistic Roadmap (PRM) Algorithm One of the most famous sampling-based planning algorithms is the probabilistic roadmap (PRM), introduced by now-Professor Lydia Kavraki in 1996. The algorithm itself is pretty simple. First, a bunch of collision free configurations are randomly sampled. Although we don't have an explicit representation of the obstacles in conf...
Post a Comment
Read more

Atomic Cycles and Finding Holes in Manifolds

Image
It's been a while! Turns out being in a PhD program keeps you pretty busy. I'm gonna try to get back into research blogging, but we'll see how long that lasts. This post is going back to manifold learning , my research focus during my undergrad at the University of Michigan. Machine learning theoreticians and practitioners frequently make use of the manifold hypothesis , which asserts that high-dimensional data generally lie along lower-dimensional latent manifolds. Manifold learning makes heavy use of that assumption: it tries to find a coordinate chart of that manifold, towards producing an explicit low-dimensional representation of the data. One potential shortcoming of this strategy is that not all manifolds can be represented using a single coordinate chart, due to holes in the manifold. One can get around this by making cuts to the manifold or embedding pieces of the manifold as an atlas of charts , but to do so, one must identify the holes. Since the manifold is un...
Post a Comment
Read more

RSS 2023 Recap

Image
Last week, I attended Robotics: Science and Systems in Daegu, South Korea. While there, I presented our paper, Non-Euclidean Motion Planning with Graphs of Geodesically-Convex Sets . This was my first experience presenting at a single-track conference, and giving a talk in front of hundreds of people was pretty anxiety-inducing! But I think the talk and poster session went very well. You can view the poster here , and I've clipped a recording of the talk from the RSS livestream here . There were several papers at the conference that I found particularly interesting. Path Planning for Multiple Tethered Robots Using Topological Braids presents a group-theoretic framework for tethered quadrotors, which may be in a knotted configuration. It would have been very nice to know about their work when I was working on my final project with Seiji Shaw for Underactuated this past spring. In that project, we ended up making the simplifying (and somewhat unrealistic) assumption that the cab...
Post a Comment
Read more