INSATxGCS (IxG): Implicit Graph Search for Planning on Graphs of Convex Sets

Ramkumar Natarajan1, Chaoqi Liu2, Howie Choset1, Maxim Likhachev1,
1The Robotics Institute, Carnegie Mellon University 2University of Illinois Urbana-Champaign
Paper arXiv Video Code

Abstract

Graphs of Convex Sets (GCS) is a recent motion planning and decision-making framework. To plan on GCS one must solve a Mixed Integer Convex Program (MICP). GCS-Opt proposed a tight relaxation to solve this MICP efficiently. Despite this, GCS-Opt for robot motion planning may contain millions of constraints and therefore can be slow. Motivated by the observation that the trajectory solution lies only on a fraction of the set of convex sets, we present two implicit graph search methods for planning on the graph of convex sets called INSATxGCS (IxG) and IxG*. INterleaved Search And Trajectory optimization (INSAT) is a previously developed algorithm that alternates between searching on a graph and optimizing partial paths to find a smooth trajectory. By using an implicit graph search method INSAT on the graph of convex sets, we achieve faster planning while ensuring stronger guarantees on completeness and optimality.

Graphs of Convex Sets (GCS)

say something

GCS-Opt

say something

Why not GCS-Opt for GCS?

say something

IxG

say something

IxG vs GCS-Opt

say something

IxG* - optimal variant of IxG

say something

Results

say something

BibTeX

@article{natarajan2024ixg,
  author    = {Natarajan, Ramkumar and Liu, Chaoqi and Choset, Howie and Likhachev, Maxim},
  title     = {Implicit Graph Search for Planning on Graphs of Convex Sets},
  journal   = {Robotics: Science and Systems (RSS)},
  year      = {2024},
}