Brian Paden

Doctoral Candidate
Laboratory for Information and Decision Systems, MIT


Generalized Label Correcting Methods for Optimal Motion and Trajectory Planning

The main thrust of my dissertation research has been on the development of what I am calling the generalized label correcting (GLC) method. This method is used to compute approximations to globally optimal trajectories in kinodynamic motion planning and trajectory optimization problems. I call it a method instead of an algorithm because it relies on a numerical approximation of the problem together with an approximate shortest path graph search algorithm. A careful balance between numerical approximation accuracy and the approximate graph search leads to a method which converges to an optimal solution with increasing numerical resolution.

The benefit of this approach is that it is extremely simple to implement and can be applied to a very broad class of problems (e.g. 3D mobile robot with nonlinear drag and inertia on the left and an acrobot on the right). Like many motion planning algorithms the interface with an autonomous system includes a feasibility checking module for candidate trajectories, and a numerical integration module for simulating the system dynamics and evaluating the merit of a trajectory. One of the main advantages of the GLC method is that does not require any local planning.

Synthesis of Admissible Heuristics for Optimal Kinodynamic Motion Planning

Methods that approximate motion planning and trajectory optimization problems by graphs often benefit from an admissible heuristic (an underestimate of the optimal cost to reach the goal) to guide the search. Generally, one guesses a heuristic and by some clever argument proves that it is admissible.

In this work I have been developing techniques for the analysis and construction of admissible heuristics. I have derived an admissitility condition that is closely related to viscosity super-solutions of the Hamilton-Jacobi-Bellman equation. With this condition, checking admissibility of a heuristic becomes straight forward. An interesting connection with optimal control theory is that this condition lends itself to a concave maximization whose solution is exactly the optimal cost to reach the goal. Although the objective is concave over a convex set, it is over an infinite dimensional space. By using sum-of-squares techniques an approximate solution can be obtained which is guaranteed to be admissible. The graphic to the left illustrates polynomial heuristics approximating an nonsmooth value function. The graphic to the right shows the shortest curvature-constrained path computed by the generalized label correcting method using an admissible heuristic to guide the search.

Performance Limitations of Conventional kD-trees for Sub-Riemannian Metrics

This work is being pursued by my colleague Valerio Varricchio and I have been fortunate enough to be able to participate in this very exciting investigation.

The k-D tree is a binary tree structure for managing large k-dimensional datasets. The principal use is efficiently finding the nearest point in the data set to a query point. This is a critical operation in almost all randomized motion planning algorithms. The advangage of a k-D tree over an exhaustive linear search is that the nearest neighbor query can be solved in O(log(n)) time. This famous result by Jon Louis Bently makes certain assumptions on the notion of distance to define a nearest point in the dataset. Even with logarithmic complexity, the nearest neighbor query dominates the iteration complexity of randomized planning algorithms.

The appropriate distance function in these motion planning algorithms is the length of the geodesic curve on the configuration manifold. Nonholonomic systems give rise to sub-Riemannian distance functions. On the chart for the manifold the distance function becomes distorted and the assumptions used to prove logarithmic complexity of the nearest neighbor query break down (cf the image above). We have been able to proove the average case asymptotic complexity of a classically built k-D tree for sub-Riemannian metrics. It turns out that the complexity converges to that of an exhaustive search as the system becomes "more nonholonomic" (more iterated Lie-brackes of the horizontal distribution to span the tangent bundle).

The next step is to design a strategy for selecting the splitting planes (cf right image) of the k-D tree so that the complexity of nearest neighbor query is indeed logarithmic.

Design and Fabrication of a Novel Electromechanical Engine Valve-train

Conventional engine valve-trains have limited or no control over the duration and phase of the valve timing. This limits optimal performance to a single operating condition. Many electromechanical or electrohydraulic designs have been proposed to provide fully variable timing, but these designs are plagued by excessive power consumption and challenging control problems.

This novel design introduces a heteroclinic cycle between the open and closed valve positions. This enables very fast transitions between configurations with a minimal amount of power consumption. The mechanism shown in the video on the left introduces these nonlinear dynamics while the voice coil actuator that can be seen in the video on the right actuates and stabilizes the motion. In the interest of achieving the best performance possibe, the entire valve-train was designed and fabricated for the task. This ranged from fabricating and fine tuning the temper on some of the cam/follower parts to machining the coil bobbin and winding the coil in the actuator.

Necessary Conditions of an Optimal Plant and Controller for Efficient Motion Control

Critical design variables of the valve-train described above were a cam profile together with the reference trajectory between the two configurations. This research, which was the focus of my Master's thesis, investigated the optimal co-design of the reference control and trajectory along with the cam profile. Necessary conditions on the optimal cam profile were derived and ultimately used in the design. The figure to the left illustrates the optimal free response vector field of the system subject to design constraints together with the minimum energy trajectory between two configurations.

Planning and Control of Helicopter Landing Maneuvers onto Sloped Terrain

This project was carried out in collaboration with Aurora Flight Sciences. My colleague Sze Zheng Yong and I developted motion planning and trajectory stabilization routines for helicopter landing manuvers on sloped terrain. While this was fairly routine motion planning and control we made some interesting observations. The first was that the concept of differential flatness is equivalent to strong observability in the context of linear systems. Secondly, we identified the subspace of stabilizable, or asymptotically reachable states in a linear system is not related to the controllable subspace. The consequence is that, even for a controllable system, certain states are hard to reach with high precision since they cannot be stabilized.