Tommy's Research Blog

In case you haven't heard of it before, GCS stands for "Graph of Convex Sets", and it is a framework for certain mixed integer convex optimization problems, primarily used for robot motion planning. I previously wrote a blog post on my experience implementing a basic version of it, which you can find here . I'd recommend reading that blog post before looking at this one. If you've read that previous blog post, you may recall that I described two different ways of transcribing the motion planning problem into a graph of convex sets. I implemented one version, which seems more faithful to the original GCS paper . However, the other transcription, presented in the planning-specific followup paper , has several benefits over the previous approach. In this blog post, I'll briefly present both methodologies, and explain their costs and benefits. Formulation 1: Conjugate Graph Fig. 1 of Shortest Paths in Graphs of Convex Sets The classic picture of GCS is the one sho

A Heuristic Approach to Finding Diverse Short Paths (Caleb Voss, Mark Moll, and Lydia E. Kavraki) is a motion planning paper from Rice University's Kavraki Lab . The paper specifically examines graph-based motion planning, and aims to produce multiple diverse plans from the start to the goal, to make a robotic system robust to changing conditions. In particular, it would be computationally expensive to constantly update the edge weights in a graph if the underlying environment it models were dynamically changing. With the authors' approach, one only needs to check the potential paths for validity. The diversity of the paths makes it more likely that the system will succeed, since an obstacle blocking one path will likely block similar paths. 20 diverse paths from a start to a goal through downtown Houston, from Fig 6 of the paper. Background Graph-based motion planners represent the set of robot configurations as nodes in a graph, where edges indicate it's possible to move