Abstract:
Search-based planning algorithms enable autonomous agents like robots to come up with well-reasoned long-horizon plans to achieve a given task objective. They do so by searching over the graph that results from discretizing the state and action space. However, in robotics, several dynamically rich tasks require high-dimensional planning in the continuous space. For such domains, kinodynamic planning and trajectory optimization techniques have been developed to synthesize dynamically feasible trajectories. The existing kinodynamic algorithms achieve this by discretizing the action space to roll out trajectory primitives in the discrete or continuous state space. On the other hand, trajectory optimization techniques do not discretize the state or action space but suffer local minima, lack convergence guarantees in nonlinear settings, and struggle to reason over long horizons.

The goal of this thesis is to develop motion planning algorithms for complex dynamical systems for planning over long horizons. First, we present the Interleaved Search And Trajectory Optimization (INSAT) algorithm. INSAT combines the benefit of graph search-based planning algorithms to find paths over non-convex state spaces and that of trajectory optimization to find dynamically feasible trajectories in high-dimensional spaces. We demonstrate the working of INSAT in two challenging domains 1) aggressive quadrotor flight in large environments (in simulation) and 2) torque-limited manipulation through contact in confined spaces. We also show that, by interleaving graph search and trajectory optimization, INSAT solves planning problems that a naively initialized trajectory optimization or standalone graph search does not solve. We then present our ongoing work to develop a provably optimal version of INSAT called INSAT*. Here we show the recent empirical results to demonstrate that INSAT* can find lower-cost solutions than discrete optimal planners.

For the proposed research, we seek to extend the INSAT framework to plan using inaccurate dynamical models. We build upon a recently introduced algorithm that plans using inaccurate models by updating the behavior of the planner and not the dynamics of the model. Our focus will be mainly on contact-rich manipulation and tasks where planning with dynamics using planners like INSAT is necessary. For the second proposed work, we deal with the problem of robot planning and reasoning to intercept multiple incoming projectiles with a shield. Here, we propose to extend the ideas developed in constant-time motion planning to generate dynamically efficient motion plans using INSAT with provable guarantees on planning time.

Thesis Committee Members:
Maxim Likhachev, Co-chair
Howie Choset, Co-chair
Zachary Manchester
Russ Tedrake, MIT

More Information