MechE Colloquium: From Motion to Mission Planning via Augmented Graphs of Convex Sets
Event details
| Date | 06.10.2026 |
| Hour | 12:00 › 13:00 |
| Speaker | Prof. Tyler Summers, Mechanical engineering, The University of Texas at Dallas |
| Location | Online |
| Category | Conferences - Seminars |
| Event Language | English |
Abstract: Robot motion planning has traditionally focused on navigating obstacle-laden environments: computing smooth, collision-free trajectories from start to goal. Many real-world missions, however, require satisfying logical precedence constraints: collecting resources before accessing restricted zones, completing subtasks in a prescribed order, or acquiring tools before they can be used. This talk presents the augmented graph of convex sets (augmented GCS) framework, which unifies continuous trajectory optimization and combinatorial task sequencing within a single optimization problem.
The key insight is that a layered augmented GCS, built on an exact convex partition of the free space, simultaneously selects an optimal task completion sequence and computes an optimal continuous trajectory. A shortest path in the augmented GCS solves both problems at once, yielding an exact solution up to a finite Bézier curve parameterization. The layered structure of the augmented GCS turns out to implement precisely the Bellman-Held-Karp (BHK) dynamic programming algorithm for the Traveling Salesman Problem, establishing a formal correspondence between our framework and the combinatorial TSP literature. This makes augmented GCS a continuous-geometry generalization of BHK, achieving the same singly exponential worst-case complexity, an exponential improvement over general-purpose temporal logic tools. We further develop a library of mission specification variations (including ordered collection, disjunctive keys, conjunctive doors, timed constraints, and conditional logic) each with proven correctness, substantially expanding the range of expressible mission types. Numerical experiments confirm exponential speedups in practice and near-global-optimality on a large benchmark suite.
Time permitting, I will briefly discuss ongoing extensions, including spacetime augmented GCS for dynamic environments, safety-aware planning via conformal prediction sets, and a galactic survey benchmark inspired by space mission planning that stress-tests the framework at scale.
Biography: Tyler Summers is an associate professor at the University of Texas at Dallas. Prior to joining UT Dallas, he was an ETH Postdoctoral Fellow at the Automatic Control Laboratory at ETH Zurich from 2011 to 2015. He received a PhD degree in Aerospace Engineering at the University of Texas at Austin in 2010. He was a Fulbright Postgraduate Scholar at the Australian National University in Canberra, Australia in 2007-2008. He received the National Science Foundation CAREER Award in 2021 and a Young Investigator Program award from the US Army Research Office in 2017. His research interests are in feedback control, optimization, and learning in complex dynamical networks, with applications in robotics and power networks.
The key insight is that a layered augmented GCS, built on an exact convex partition of the free space, simultaneously selects an optimal task completion sequence and computes an optimal continuous trajectory. A shortest path in the augmented GCS solves both problems at once, yielding an exact solution up to a finite Bézier curve parameterization. The layered structure of the augmented GCS turns out to implement precisely the Bellman-Held-Karp (BHK) dynamic programming algorithm for the Traveling Salesman Problem, establishing a formal correspondence between our framework and the combinatorial TSP literature. This makes augmented GCS a continuous-geometry generalization of BHK, achieving the same singly exponential worst-case complexity, an exponential improvement over general-purpose temporal logic tools. We further develop a library of mission specification variations (including ordered collection, disjunctive keys, conjunctive doors, timed constraints, and conditional logic) each with proven correctness, substantially expanding the range of expressible mission types. Numerical experiments confirm exponential speedups in practice and near-global-optimality on a large benchmark suite.
Time permitting, I will briefly discuss ongoing extensions, including spacetime augmented GCS for dynamic environments, safety-aware planning via conformal prediction sets, and a galactic survey benchmark inspired by space mission planning that stress-tests the framework at scale.
Biography: Tyler Summers is an associate professor at the University of Texas at Dallas. Prior to joining UT Dallas, he was an ETH Postdoctoral Fellow at the Automatic Control Laboratory at ETH Zurich from 2011 to 2015. He received a PhD degree in Aerospace Engineering at the University of Texas at Austin in 2010. He was a Fulbright Postgraduate Scholar at the Australian National University in Canberra, Australia in 2007-2008. He received the National Science Foundation CAREER Award in 2021 and a Young Investigator Program award from the US Army Research Office in 2017. His research interests are in feedback control, optimization, and learning in complex dynamical networks, with applications in robotics and power networks.
Practical information
- General public
- Free