My research spans topics relating to motion planning and machine learning for robots solving complex tasks.


2018 - Present

2019_gls

Generalized Lazy Search

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)

2016 - 2017

2016_densification

Incremental Densification

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(N2) 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

2015 - 2016

2016_rabitstar

Hybrid Local and Global Search

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: LongShort

2012 - 2013

2013_rrrstar

Planning Alternate Routes using a Sampling Based Planner

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'13CMU-TR   /   Videos: ShortLong

2013 - 2014

2013_spartan

Speedy Search on Sparse 3D Visibility Roamdaps

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'15ICRA'13   /   Videos: Long

2014 - 2015

2014_trajoptfiltering

Fast Nonlinear Trajectory Optimization using Filtering Techniques

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

2016 - 2017

2017_kite

Trajectory Optimization in a Moving Frame

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'17AHS'17

2015 - 2016

2015_repairingvectorfields

Optimal Repairing of Vector Fields

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'16CBA'17   /   Videos: Clip1