Typical search algorithms expand a wavefront from the start, evaluating edges discovered until the shortest path is found. Hence planning time is a sum of search effort and edge evaluation. How can we optimally trade-off between the two? We propose a general framework that toggles between a virtual search on the entire graph and lazy evaluation of only the shortest subpath. The framework both unifies previous approaches and provides insight on new algorithms that can better leverage prior information.
Papers:  ICAPS'19 (best paper)

The gold standard in motion planning is to find the shortest path in continous space. One way to achieve that is to create a dense fully-connected graph and search it, however, that will take O(N²) time. Our key insight is that we don't need to search the entire graph - we only need to search the right subgraph. We propose an iterative scheme of selecting a subgraph, searching it, and using the results to select a better subgraph till the shortest path on the original dense graph is found.
Papers:  ICRA'17,   arXiv'18

Sampling-based planners like BIT* are effective at exploring the whole solution space but are slow to exploit. On the other hand, trajectory optimizers like CHOMP locally exploit around an initial path but running it on all potential paths is too expensive. Our key insight is to interleave search by applying CHOMP to only a subset of promising edges in BIT* search tree. We propose an algorithm, RABIT*, that unifies global and local planning techniques.
Papers:  ICRA'16   /   Videos: Long,  Short

We address the problem of finding multiple diverse near-optimal solutions to a planning problem. There are several applications - finding alternate routes (as in Google Maps), planning to different goal locations, finding solutions in different homotopies, etc. Our key insight is to define equivalence classes in path space and not allow the search tree to have paths in the same class. We present an algorithm, RRT*-AR, to do this efficiently and evaluate it on a number of different planning tasks.
Papers:  ICRA'13,  CMU-TR   /   Videos: Short,  Long

We have designed a 3D planning algorithm, SPARTAN, that is orders of magnitude faster than sampling-based or discrete search alternatives. We do so by constructing the sparsest possible roadmap that contains the shortest 3D path. Our key insight is that the shortest path is a geodesic that can only deviate around surface normals. We extensively evaluate SPARTAN onboard a UAV flying outdoors through dense vegetation.
Papers:  JFR'15,  ICRA'13   /   Videos: Long

Nonlinear trajectory optimization for mobile robots has two main components - minimizing an objecting and enforcing dynamic constraints. The objective is often defined only on the 3D workspace (e.g. avoid obstacles, maximize smoothness) while constraints are on the full state space. Our key insight is to first optimize a workspace trajectory and then filter it with dynamics. We evaluate this approach on a fully autonomous helicopter and derive performance bounds using Lyapunov stability theory.
Papers:  ICRA'15   /   Videos: Short

We address the problem of planning long, dynamically feasible, time-optimal trajectories in the presence of wind (which creates a moving reference frame). We present an algorithm, KITE, that elegantly decouples the joint trajectory optimization problem into individual path optimization in a fixed ground frame and a velocity profile optimization in a moving reference frame.
Papers:  ICRA'17,  AHS'17

This paper presents a framework that integrates vector field based motion planning techniques with an optimal path planner. Our framework uses a vector field as a high level specification of a task and an optimal motion planner (in our case RRT*) as a local, on-line planner that generates paths that follow the vector field, but also consider the new obstacles encountered by the vehicle during the flight.
Papers:  ICUAS'16,  CBA'17   /   Videos: Clip1