Edward Schmerling

Contacts:

Personal Webpage

Edward Schmerling


Ed Schmerling is a roboticist pursuing a Ph.D. with the Institute for Computational & Mathematical Engineering at Stanford University. He received a B.S. in Mathematics (with Honors) and Physics from Stanford in 2010.

Ed’s research interests span questions in robot motion planning and decision making under uncertainty -— how to model a robot’s interaction with its (possibly-sentient) environment, how to efficiently plan actions by closing the loop on only the most relevant data to the task at hand, how to quantify/certify the performance of these algorithms.

In a previous life, Ed was a captain and coach of the Stanford Prison Experiment, the men’s ultimate frisbee B-team and a force to be feared in regional competition. Nowadays he’s hung up the cleats unless rival labs are looking to further their higher education.

Awards:

  • Qualcomm Innovation Fellowship (2015)

Currently at Waymo Research

ASL Publications

  1. R. Luo, S. Zhao, J. Kuck, B. Ivanovic, S. Savarese, E. Schmerling, and M. Pavone, “Sample-Efficient Safety Assurances using Conformal Prediction,” in Proc. IEEE Conf. on Robotics and Automation, 2022. (Submitted)

    Abstract: When deploying machine learning models in high-stakes robotics applications, the ability to detect unsafe situations is crucial. Early warning systems can provide alerts when an unsafe situation is imminent (in the absence of corrective action). To reliably improve safety, these warning systems should have a provable false negative rate; i.e., of the situations than are unsafe, fewer than epsilon will occur without an alert. In this work, we present a framework that combines a statistical inference technique known as conformal prediction with a simulator of robot/environment dynamics, in order to tune warning systems to provably achieve an epsilon false negative rate using as few as 1/epsilon data points. We apply our framework to a driver warning system and a robotic grasping application, and empirically demonstrate guaranteed false negative rate and low false detection (positive) rate using very little data.

    @inproceedings{LuoZhaoEtAl2022,
      author = {Luo, R. and Zhao, S. and Kuck, J. and Ivanovic, B. and Savarese, S. and Schmerling, E. and Pavone, M.},
      title = {Sample-Efficient Safety Assurances using Conformal Prediction},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2022},
      month = may,
      note = {Submitted},
      keywords = {sub},
      owner = {rsluo},
      timestamp = {2021-09-20},
      url = {https://arxiv.org/abs/2109.14082}
    }
    
  2. B. Ivanovic, K. Leung, E. Schmerling, and M. Pavone, “Multimodal Deep Generative Models for Trajectory Prediction: A Conditional Variational Autoencoder Approach,” IEEE Robotics and Automation Letters, vol. 6, no. 2, pp. 295–302, Apr. 2021. (In Press)

    Abstract: Human behavior prediction models enable robots to anticipate how humans may react to their actions, and hence are instrumental to devising safe and proactive robot planning algorithms. However, modeling complex interaction dynamics and capturing the possibility of many possible outcomes in such interactive settings is very challenging, which has recently prompted the study of several different approaches. In this work, we provide a self-contained tutorial on a conditional variational autoencoder (CVAE) approach to human behavior prediction which, at its core, can produce a multimodal probability distribution over future human trajectories conditioned on past interactions and candidate robot future actions. Specifically, the goals of this tutorial paper are to review and build a taxonomy of state-of-the-art methods in human behavior prediction, from physics-based to purely data-driven methods, provide a rigorous yet easily accessible description of a data-driven, CVAE-based approach, highlight important design characteristics that make this an attractive model to use in the context of model-based planning for human-robot interactions, and provide important design considerations when using this class of models.

    @article{IvanovicLeungEtAl2020,
      author = {Ivanovic, B. and Leung, K. and Schmerling, E. and Pavone, M.},
      title = {Multimodal Deep Generative Models for Trajectory Prediction: A Conditional Variational Autoencoder Approach},
      journal = {{IEEE Robotics and Automation Letters}},
      volume = {6},
      number = {2},
      pages = {295--302},
      year = {2021},
      note = {In Press},
      month = apr,
      url = {https://arxiv.org/abs/2008.03880},
      keywords = {press},
      owner = {borisi},
      timestamp = {2020-12-23}
    }
    
  3. A. Cauligi, P. Culbertson, E. Schmerling, M. Schwager, B. Stellato, and M. Pavone, “CoCo: Online Mixed-Integer Control via Supervised Learning,” IEEE Robotics and Automation Letters, 2021. (Submitted)

    Abstract: Many robotics problems, from robot motion planning to object manipulation, can be modeled as mixed-integer convex programs (MICPs). However, state-of-the-art algorithms are still unable to solve MICPs for control problems quickly enough for online use and existing heuristics can typically only find suboptimal solutions that might degrade robot performance. In this work, we turn to data-driven methods and present the Combinatorial Offline, Convex Online (CoCo) algorithm for quickly finding high quality solutions for MICPs. CoCo consists of a two-stage approach. In the offline phase, we train a neural network classifier that maps the problem parameters to a (logical strategy), which we define as the discrete arguments and relaxed big-M constraints associated with the optimal solution for that problem. Online, the classifier is applied to select a candidate logical strategy given new problem parameters; applying this logical strategy allows us to solve the original MICP as a convex optimization problem. We show through numerical experiments how CoCo finds near optimal solutions to MICPs arising in robot planning and control with 1 to 2 orders of magnitude solution speedup compared to other data-driven approaches and solvers.

    @article{CauligiCulbertsonEtAl2021,
      author = {Cauligi, A. and Culbertson, P. and Schmerling, E. and Schwager, M. and Stellato, B. and Pavone, M.},
      title = {{CoCo}: Online Mixed-Integer Control via Supervised Learning},
      journal = {{IEEE Robotics and Automation Letters}},
      year = {2021},
      note = {Submitted},
      url = {http://arxiv.org/abs/2107.08143},
      keywords = {sub},
      owner = {acauligi},
      timestamp = {2021-07-20}
    }
    
  4. K. Solovey, L. Janson, E. Schmerling, E. Frazzoli, and M. Pavone, “Revisiting the Asymptotic Optimality of RRT*,” in Proc. IEEE Conf. on Robotics and Automation, Paris, France, 2020.

    Abstract: RRT* is one of the most widely used sampling-based algorithms for asymptotically-optimal motion planning. This algorithm laid the foundations for optimality in motion planning as a whole, and inspired the development of numerous new algorithms in the field, many of which build upon RRT* itself. In this paper, we first identify a logical gap in the optimality proof of RRT*, which was developed in Karaman and Frazzoli (2011). Then, we present an alternative and mathematically-rigorous proof for asymptotic optimality. Our proof suggests that the connection radius used by RRT* should be increased from γ(\frac\log nn)^1/d to γ’ (\frac\log nn)^1/(d+1) in order to account for the additional dimension of time that dictates the samples’ ordering. Here gamma, γ’ are constants, and n, d are the number of samples and the dimension of the problem, respectively.

    @inproceedings{SoloveyJansonETAL2020,
      author = {Solovey, K. and Janson, L. and Schmerling, E. and Frazzoli, E. and Pavone, M.},
      title = {Revisiting the Asymptotic Optimality of RRT*},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2020},
      address = {Paris, France},
      month = may,
      url = {https://ieeexplore.ieee.org/document/9196553},
      timestamp = {2020-02-25}
    }
    
  5. K. Leung, E. Schmerling, M. Zhang, M. Chen, J. Talbot, J. C. Gerdes, and M. Pavone, “On Infusing Reachability-Based Safety Assurance within Planning Frameworks for Human-Robot Vehicle Interactions,” Int. Journal of Robotics Research, vol. 39, no. 10–11, pp. 1326–1345, 2020.

    Abstract: Action anticipation, intent prediction, and proactive behavior are all desirable characteristics for autonomous driving policies in interactive scenarios. Paramount, however, is ensuring safety on the road—a key challenge in doing so is accounting for uncertainty in human driver actions without unduly impacting planner performance. This paper introduces a minimally-interventional safety controller operating within an autonomous vehicle control stack with the role of ensuring collision-free interaction with an externally controlled (e.g., human-driven) counterpart while respecting static obstacles such as a road boundary wall. We leverage reachability analysis to construct a real-time (100Hz) controller that serves the dual role of (1) tracking an input trajectory from a higher-level planning algorithm using model predictive control, and (2) assuring safety through maintaining the availability of a collision-free escape maneuver as a persistent constraint regardless of whatever future actions the other car takes. A full-scale steer-by-wire platform is used to conduct traffic weaving experiments wherein two cars, initially side-by-side, must swap lanes in a limited amount of time and distance, emulating cars merging onto/off of a highway. We demonstrate that, with our control stack, the autonomous vehicle is able to avoid collision even when the other car defies the planner’s expectations and takes dangerous actions, either carelessly or with the intent to collide, and otherwise deviates minimally from the planned trajectory to the extent required to maintain safety.

    @article{LeungSchmerlingEtAl2019,
      author = {Leung, K. and Schmerling, E. and Zhang, M. and Chen, M. and Talbot, J. and Gerdes, J. C. and Pavone, M.},
      title = {On Infusing Reachability-Based Safety Assurance within Planning Frameworks for Human-Robot Vehicle Interactions},
      journal = {{Int. Journal of Robotics Research}},
      year = {2020},
      volume = {39},
      issue = {10--11},
      pages = {1326--1345},
      url = {/wp-content/papercite-data/pdf/Leung.Schmerling.ea.IJRR19.pdf},
      timestamp = {2020-10-13}
    }
    
  6. E. Schmerling and M. Pavone, “Kinodynamic Planning,” in Encyclopedia of Robotics, First., Springer, 2019.

    Abstract:

    @incollection{SchmerlingPavone2019,
      author = {Schmerling, E. and Pavone, M.},
      title = {Kinodynamic Planning},
      booktitle = {Encyclopedia of Robotics},
      publisher = {{Springer}},
      edition = {First},
      year = {2019},
      url = {/wp-content/papercite-data/pdf/Schmerling.Pavone.EOR19.pdf},
      owner = {bylard},
      timestamp = {2019-10-07}
    }
    
  7. B. Ivanovic, E. Schmerling, K. Leung, and M. Pavone, “Generative Modeling of Multimodal Multi-Human Behavior,” in IEEE/RSJ Int. Conf. on Intelligent Robots & Systems, Madrid, Spain, 2018.

    Abstract: This work presents a methodology for modeling and predicting human behavior in settings with N humans interacting in highly multimodal scenarios (i.e. where there are many possible highly-distinct futures). A motivating example includes robots interacting with humans in crowded environments, such as self-driving cars operating alongside human-driven vehicles or human-robot collaborative bin packing in a warehouse. Our approach to model human behavior in such uncertain environments is to model humans in the scene as nodes in a graphical model, with edges encoding relationships between them. For each human, we learn a multimodal probability distribution over future actions from a dataset of multi-human interactions. Learning such distributions is made possible by recent advances in the theory of conditional variational autoencoders and deep learning approximations of probabilistic graphical models. Specifically, we learn action distributions conditioned on interaction history, neighboring human behavior, and candidate future agent behavior in order to take into account response dynamics. We demonstrate the performance of such a modeling approach in modeling basketball player trajectories, a highly multimodal, multi-human scenario which serves as a proxy for many robotic applications.

    @inproceedings{IvanovicSchmerlingEtAl2018,
      author = {Ivanovic, B. and Schmerling, E. and Leung, K. and Pavone, M.},
      title = {Generative Modeling of Multimodal Multi-Human Behavior},
      booktitle = {{IEEE/RSJ Int. Conf. on Intelligent Robots \& Systems}},
      year = {2018},
      address = {Madrid, Spain},
      month = oct,
      url = {https://arxiv.org/pdf/1803.02015.pdf},
      owner = {borisi},
      timestamp = {2018-10-14}
    }
    
  8. E. Schmerling, K. Leung, W. Vollprecht, and M. Pavone, “Multimodal Probabilistic Model-Based Planning for Human-Robot Interaction,” in Proc. IEEE Conf. on Robotics and Automation, Brisbane, Australia, 2018.

    Abstract: This paper presents a method for constructing human-robot interaction policies in settings where multimodality, i.e., the possibility of multiple highly distinct futures, plays a critical role in decision making. We are motivated in this work by the example of traffic weaving, e.g., at highway onramps/offramps, where entering and exiting cars must swap lanes in a short distance — a challenging negotiation even for experienced drivers due to the inherent multimodal uncertainty of who will pass whom. Our approach is to learn multimodal probability distributions over future human actions from a dataset of human-human exemplars and perform real-time robot policy construction in the resulting environment model through massively parallel sampling of human responses to candidate robot action sequences. Direct learning of these distributions is made possible by recent advances in the theory of conditional variational autoencoders (CVAEs), whereby we learn action distributions simultaneously conditioned on the present interaction history, as well as candidate future robot actions in order to take into account response dynamics. We demonstrate the efficacy of this approach with a human-in-the-loop simulation of a traffic weaving scenario.

    @inproceedings{SchmerlingLeungEtAl2018,
      author = {Schmerling, E. and Leung, K. and Vollprecht, W. and Pavone, M.},
      title = {Multimodal Probabilistic Model-Based Planning for Human-Robot Interaction},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2018},
      address = {Brisbane, Australia},
      month = may,
      url = {/wp-content/papercite-data/pdf/Schmerling.Leung.Vollprecht.Pavone.ICRA18.pdf},
      owner = {schmrlng},
      timestamp = {2017-09-18}
    }
    
  9. K. Leung, E. Schmerling, M. Chen, J. Talbot, J. C. Gerdes, and M. Pavone, “On Infusing Reachability-Based Safety Assurance within Probabilistic Planning Frameworks for Human-Robot Vehicle Interactions,” in Int. Symp. on Experimental Robotics, Buenos Aires, Argentina, 2018.

    Abstract:

    @inproceedings{LeungSchmerlingEtAl2018,
      author = {Leung, K. and Schmerling, E. and Chen, M. and Talbot, J. and Gerdes, J. C. and Pavone, M.},
      title = {On Infusing Reachability-Based Safety Assurance within Probabilistic Planning Frameworks for Human-Robot Vehicle Interactions},
      booktitle = {{Int. Symp. on Experimental Robotics}},
      year = {2018},
      address = {Buenos Aires, Argentina},
      url = {/wp-content/papercite-data/pdf/Leung.Schmerling.Chen.ea.ISER18.pdf},
      owner = {mochen72},
      timestamp = {2018-10-13}
    }
    
  10. B. Ichter, B. Landry, E. Schmerling, and M. Pavone, “Perception-Aware Motion Planning via Multiobjective Search on GPUs,” in Int. Symp. on Robotics Research, Puerto Varas, Chile, 2017.

    Abstract: In this paper we approach the robust motion planning problem through the lens of perception-aware planning, whereby we seek a low-cost motion plan subject to a separate constraint on perception localization quality. To solve this problem we introduce the Multiobjective Perception-Aware Planning (MPAP) algorithm which explores the state space via a multiobjective search, considering both cost and a perception heuristic. This perception-heuristic formulation allows us to both capture the history dependence of localization drift and represent complex modern perception methods. The solution trajectory from this heuristic-based search is then certified via Monte Carlo methods to be robust. The additional computational burden of perception-aware planning is offset through massive parallelization on a GPU. Through numerical experiments the algorithm is shown to find robust solutions in about a second. Finally, we demonstrate MPAP on a quadrotor flying perception-aware and perception-agnostic plans using Google Tango for localization, finding the quadrotor safely executes the perception-aware plan every time, while crashing over 20% of the time on the perception-agnostic due to loss of localization.

    @inproceedings{IchterLandryEtAl2017,
      author = {Ichter, B. and Landry, B. and Schmerling, E. and Pavone, M.},
      title = {Perception-Aware Motion Planning via Multiobjective Search on {GPUs}},
      booktitle = {{Int. Symp. on Robotics Research}},
      year = {2017},
      address = {Puerto Varas, Chile},
      month = dec,
      url = {https://arxiv.org/pdf/1705.02408.pdf},
      owner = {ichter},
      timestamp = {2018-01-16}
    }
    
  11. E. Schmerling and M. Pavone, “Evaluating Trajectory Collision Probability through Adaptive Importance Sampling for Safe Motion Planning,” in Robotics: Science and Systems, Cambridge, Massachusetts, 2017.

    Abstract: This paper presents a tool for addressing a key component in many algorithms for planning robot trajectories under uncertainty: evaluation of the safety of a robot whose actions are governed by a closed-loop feedback policy near a nominal planned trajectory. We describe an adaptive importance sampling Monte Carlo framework that enables the evaluation of a given control policy for satisfaction of a probabilistic collision avoidance constraint which also provides an associated certificate of accuracy (in the form of a confidence interval). In particular this adaptive technique is well-suited to addressing the complexities of rigid-body collision checking applied to non-linear robot dynamics. As a Monte Carlo method it is amenable to parallelization for computational tractability, and is generally applicable to a wide gamut of simulatable systems, including alternative noise models. Numerical experiments demonstrating the effectiveness of the adaptive importance sampling procedure are presented and discussed.

    @inproceedings{SchmerlingPavone2017,
      author = {Schmerling, E. and Pavone, M.},
      title = {Evaluating Trajectory Collision Probability through Adaptive Importance Sampling for Safe Motion Planning},
      booktitle = {{Robotics: Science and Systems}},
      year = {2017},
      address = {Cambridge, Massachusetts},
      month = jul,
      url = {https://arxiv.org/pdf/1609.05399.pdf},
      owner = {schmrlng},
      timestamp = {2018-01-16}
    }
    
  12. B. Ichter, E. Schmerling, A. Agha-mohammadi, and M. Pavone, “Real-Time Stochastic Kinodynamic Motion Planning via Multiobjective Search on GPUs,” in Proc. IEEE Conf. on Robotics and Automation, Singapore, 2017.

    Abstract: In this paper we present the PUMP (Parallel Uncertainty-aware Multiobjective Planning) algorithm for addressing the stochastic kinodynamic motion planning problem, whereby we seek a low-cost, dynamically-feasible motion plan subject to a constraint on collision probability (CP). As a departure from previous methods for chance-constrained motion planning, PUMP directly considers both CP and the optimization objective at equal priority when planning through the free configuration space, achieving an unprecedented combination of cost performance, certified safety, and speed. Planning is conducted through a massively parallel multiobjective search, here implemented with a particular application focus on GPU hardware. PUMP explores the configuration space while maintaining a Pareto optimal front of motion plans, considering cost and approximate collision probability. We introduce a novel particle-based CP approximation scheme, designed for efficient GPU implementation, which accounts for dependencies over the history of a trajectory execution. Upon termination of the exploration phase, PUMP performs a search over the Pareto optimal set of solution motion plans to identify the lowest cost motion plan that is certified to satisfy the CP constraint (according to an asymptotically exact estimator). We present numerical experiments for quadrotor planning wherein PUMP identifies solutions in  100 ms, evaluating over one hundred thousand partial plans through the course of its exploration phase. The results show that this multiobjective search achieves a lower motion plan cost, for the same collision probability constraint, compared to a safety buffer-based search heuristic and repeated RRT trials.

    @inproceedings{IchterSchmerlingEtAl2017,
      author = {Ichter, B. and Schmerling, E. and Agha-mohammadi, A. and Pavone, M.},
      title = {Real-Time Stochastic Kinodynamic Motion Planning via Multiobjective Search on {GPUs}},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2017},
      address = {Singapore},
      month = may,
      url = {http://arxiv.org/pdf/1607.06886.pdf},
      owner = {bylard},
      timestamp = {2017-03-07}
    }
    
  13. B. Ichter, E. Schmerling, and M. Pavone, “Group Marching Tree: Sampling-Based Approximately Optimal Motion Planning on GPUs,” in IEEE Int. Conf. on Robotic Computing, Taichung, Taiwan, 2017.

    Abstract: This paper presents a novel approach, named the Group Marching Tree (GMT*) algorithm, to planning on GPUs at rates amenable to application within control loops, allowing planning in real-world settings via repeated computation of near-optimal plans. GMT*, like the Fast Marching Tree (FMT*) algorithm, explores the state space with a “lazy” dynamic programming recursion on a set of samples to grow a tree of near-optimal paths. GMT*, however, alters the approach of FMT* with approximate dynamic programming by expanding, in parallel, the group of all active samples with cost below an increasing threshold, rather than only the minimum cost sample. This group approximation enables low-level parallelism over the sample set and removes the need for sequential data structures, while the “lazy” collision checking limits thread divergence—all contributing to a very efficient GPU implementation. While this approach incurs some suboptimality, we prove that GMT* remains asymptotically optimal up to a constant multiplicative factor. We show solutions for complex planning problems under differential constraints can be found in  10 ms on a desktop GPU and  30 ms on an embedded GPU, representing a significant speed up over the state of the art, with only small losses in performance. Finally, we present a scenario demonstrating the efficacy of planning within the control loop ( 100 Hz) towards operating in dynamic, uncertain settings.

    @inproceedings{IchterSchmerlingEtAl2017b,
      author = {Ichter, B. and Schmerling, E. and Pavone, M.},
      title = {Group Marching Tree: Sampling-Based Approximately Optimal Motion Planning on {GPUs}},
      booktitle = {{IEEE Int. Conf. on Robotic Computing}},
      year = {2017},
      address = {Taichung, Taiwan},
      month = apr,
      url = {/wp-content/papercite-data/pdf/Ichter.Schmerling.Pavone.ICRC17.pdf},
      owner = {bylard},
      timestamp = {2017-03-07}
    }
    
  14. J. A. Starek, E. Schmerling, G. D. Maher, B. W. Barbee, and M. Pavone, “Fast, Safe, Propellant-Efficient Spacecraft Motion Planning Under Clohessy-Wiltshire-Hill Dynamics,” AIAA Journal of Guidance, Control, and Dynamics, vol. 40, no. 2, pp. 418–438, 2017.

    Abstract: This paper presents a sampling-based motion planning algorithm for real-time and propellant-optimized autonomous spacecraft trajectory generation in near-circular orbits. Specifically, this paper leverages recent algorithmic advances in the field of robot motion planning to the problem of impulsively-actuated, propellant-optimized rendezvous and proximity operations under the Clohessy-Wiltshire-Hill (CWH) dynamics model. The approach calls upon a modified version of the Fast Marching Tree (FMT*) algorithm to grow a set of feasible trajectories over a deterministic, low-dispersion set of sample points covering the free state space. To enforce safety, the tree is only grown over the subset of actively-safe samples, from which there exists a feasible one-burn collision avoidance maneuver that can safely circularize the spacecraft orbit along its coasting arc under a given set of potential thruster failures. Key features of the proposed algorithm include: (i) theoretical guarantees in terms of trajectory safety and performance, (ii) amenability to real-time implementation, and (iii) generality, in the sense that a large class of constraints can be handled directly. As a result, the proposed algorithm offers the potential for widespread application, ranging from on-orbit satellite servicing to orbital debris removal and autonomous inspection missions.

    @article{StarekSchmerlingEtAl2016,
      author = {Starek, J. A. and Schmerling, E. and Maher, G. D. and Barbee, B. W. and Pavone, M.},
      title = {Fast, Safe, Propellant-Efficient Spacecraft Motion Planning Under {Clohessy}-{Wiltshire}-{Hill} Dynamics},
      journal = {{AIAA Journal of Guidance, Control, and Dynamics}},
      volume = {40},
      number = {2},
      pages = {418--438},
      year = {2017},
      doi = {10.2514/1.g001913},
      url = {/wp-content/papercite-data/pdf/Starek.Schmerling.ea.JGCD16.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  15. J. A. Starek, E. Schmerling, G. D. Maher, B. W. Barbee, and M. Pavone, “Real-Time, Propellant-Optimized Spacecraft Motion Planning under Clohessy-Wiltshire-Hill Dynamics,” in IEEE Aerospace Conference, Big Sky, Montana, 2016.

    Abstract: This paper presents a sampling-based motion planning algorithm for real-time, propellant-optimized autonomous spacecraft trajectory generation in near-circular orbits. Specifically, this paper leverages recent algorithmic advances in the field of robot motion planning to the problem of impulsively-actuated, propellant-optimized rendezvous and proximity operations under the Clohessy-Wiltshire-Hill (CWH) dynamics model. The approach calls upon a modified version of the Fast Marching Tree (FMT*) algorithm to grow a set of feasible and actively-safe trajectories over a deterministic, low-dispersion set of sample points covering the free state space. Key features of the proposed algorithm include: (i) theoretical guarantees of trajectory safety and performance, (ii) real-time implementability, and (iii) generality, in the sense that a large class of constraints can be handled directly. As a result, the proposed algorithm offers the potential for widespread application, ranging from on-orbit satellite servicing to orbital debris removal and autonomous inspection missions.

    @inproceedings{StarekSchmerlingEtAl2016b,
      author = {Starek, J. A. and Schmerling, E. and Maher, G. D. and Barbee, B. W. and Pavone, M.},
      title = {Real-Time, Propellant-Optimized Spacecraft Motion Planning under {Clohessy-Wiltshire-Hill} Dynamics},
      booktitle = {{IEEE Aerospace Conference}},
      year = {2016},
      address = {Big Sky, Montana},
      doi = {10.1109/aero.2016.7500704},
      month = mar,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {/wp-content/papercite-data/pdf/Starek.Schmerling.ea.AeroConf16.pdf}
    }
    
  16. K. Leung, E. Schmerling, and M. Pavone, “Distributional Prediction of Human Driving Behaviours using Mixture Density Networks,” Stanford University, 2016.

    Abstract: Confident predictions of human driving behaviours are necessary in designing safe and efficient control policies for autonomous vehicles. A better understanding of how human drivers react to their surrounding may avoid the design of overly-conservative control policies which require greater cost (e.g., time, traffic flow disruption) to achieve their objective. In this paper, we explore ways to learn distributions over human driver actions that are typical of a highway setting. We use actions filtered from Next Generation SIMulation (NGSIM) vehicle trajectory data gathered on the US 101 highway as training data for a Recurrent Neural Network. In particular, we use a Mixture Density Network (MDN) model to represent predicted driver actions as a Gaussian Mixture Model. We present and discuss exploratory results on the filtering of the raw NGSIM data and design of the MDN model.

    @techreport{LeungSchmerlingEtAl2016,
      author = {Leung, K. and Schmerling, E. and Pavone, M.},
      title = {Distributional Prediction of Human Driving Behaviours using Mixture Density Networks},
      institution = {{Stanford University}},
      year = {2016},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {/wp-content/papercite-data/pdf/Leung.Schmerling.Pavone.2016.pdf}
    }
    
  17. E. Schmerling, L. Janson, and M. Pavone, “Optimal Sampling-Based Motion Planning under Differential Constraints: the Drift Case with Linear Affine Dynamics,” in Proc. IEEE Conf. on Decision and Control, Osaka, Japan, 2015.

    Abstract: In this paper we provide a thorough, rigorous theoretical framework to assess optimality guarantees of samplingbased algorithms for drift control systems: systems that, loosely speaking, can not stop instantaneously due to momentum. We exploit this framework to design and analyze a sampling-based algorithm (the Differential Fast Marching Tree algorithm) that is asymptotically optimal, that is, it is guaranteed to converge, as the number of samples increases, to an optimal solution. In addition, our approach allows us to provide concrete bounds on the rate of this convergence. The focus of this paper is on mixed time/control energy cost functions and on linear affine dynamical systems, which encompass a range of models of interest to applications (e.g., double-integrators) and represent a necessary step to design, via successive linearization, samplingbased and provably-correct algorithms for non-linear drift control systems. Our analysis relies on an original perturbation analysis for two-point boundary value problems, which could be of independent interest.

    @inproceedings{SchmerlingJansonEtAl2015b,
      author = {Schmerling, E. and Janson, L. and Pavone, M.},
      title = {Optimal Sampling-Based Motion Planning under Differential Constraints: the Drift Case with Linear Affine Dynamics},
      booktitle = {{Proc. IEEE Conf. on Decision and Control}},
      year = {2015},
      address = {Osaka, Japan},
      doi = {10.1109/CDC.2015.7402604},
      month = dec,
      url = {http://arxiv.org/pdf/1405.7421.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  18. Z. Zhu, E. Schmerling, and M. Pavone, “A Convex Optimization Approach to Smooth Trajectories for Motion Planning with Car-Like Robots,” in Proc. IEEE Conf. on Decision and Control, Osaka, Japan, 2015.

    Abstract: In the recent past, several sampling-based algorithms have been proposed to compute trajectories that are collision-free and dynamically-feasible. However, the outputs of such algorithms are notoriously jagged. In this paper, by focusing on robots with car-like dynamics, we present a fast and simple heuristic algorithm, named Convex Elastic Smoothing (CES) algorithm, for trajectory smoothing and speed optimization. The CES algorithm is inspired by earlier work on elastic band planning and iteratively performs shape and speed optimization. The key feature of the algorithm is that both optimization problems can be solved via convex programming, making CES particularly fast. A range of numerical experiments show that the CES algorithm returns high-quality solutions in a matter of a few hundreds of milliseconds and hence appears amenable to a real-time implementation.

    @inproceedings{ZhuSchmerlingEtAl2015,
      author = {Zhu, Z. and Schmerling, E. and Pavone, M.},
      title = {A Convex Optimization Approach to Smooth Trajectories for Motion Planning with Car-Like Robots},
      booktitle = {{Proc. IEEE Conf. on Decision and Control}},
      year = {2015},
      address = {Osaka, Japan},
      doi = {10.1109/CDC.2015.7402333},
      month = dec,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {http://arxiv.org/pdf/1506.01085.pdf}
    }
    
  19. L. Janson, E. Schmerling, and M. Pavone, “Monte Carlo Motion Planning for Robot Trajectory Optimization Under Uncertainty,” in Int. Symp. on Robotics Research, Sestri Levante, Italy, 2015.

    Abstract: This article presents a novel approach, named MCMP (Monte Carlo Motion Planning), to the problem of motion planning under uncertainty, i.e., to the problem of computing a low-cost path that fulfills probabilistic collision avoidance constraints. MCMP estimates the collision probability (CP) of a given path by sampling via Monte Carlo the execution of a reference tracking controller (in this paper we consider LQG). The key algorithmic contribution of this paper is the design of statistical variance-reduction techniques, namely control variates and importance sampling, to make such a sampling procedure amenable to real-time implementation. MCMP applies this CP estimation procedure to motion planning by iteratively (i) computing an (approximately) optimal path for the deterministic version of the problem (here, using the FMT* algorithm), (ii) computing the CP of this path, and (iii) inflating or deflating the obstacles by a common factor depending on whether the CP is higher or lower than a target value. The advantages of MCMP are threefold: (i) asymptotic correctness of CP estimation, as opposed to most current approximations, which, as shown in this paper, can be off by large multiples and hinder the computation of feasible plans; (ii) speed and parallelizability, and (iii) generality, i.e., the approach is applicable to virtually any planning problem provided that a path tracking controller and a notion of distance to obstacles in the configuration space are available. Numerical results illustrate the correctness (in terms of feasibility), efficiency (in terms of path cost), and computational speed of MCMP

    @inproceedings{JansonSchmerlingEtAl2015b,
      author = {Janson, L. and Schmerling, E. and Pavone, M.},
      title = {{Monte} {Carlo} Motion Planning for Robot Trajectory Optimization Under Uncertainty},
      booktitle = {{Int. Symp. on Robotics Research}},
      year = {2015},
      address = {Sestri Levante, Italy},
      month = sep,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {http://arxiv.org/pdf/1504.08053.pdf}
    }
    
  20. J. A. Starek, J. V. Gomez, E. Schmerling, L. Janson, L. Moreno, and M. Pavone, “An Asymptotically-Optimal Sampling-Based Algorithm for Bi-directional Motion Planning,” in IEEE/RSJ Int. Conf. on Intelligent Robots & Systems, Hamburg, Germany, 2015.

    Abstract: Bi-directional search is a widely used strategy to increase the success and convergence rates of sampling-based motion planning algorithms. Yet, few results are available that merge both bi-directional search and asymptotic optimality into existing optimal planners, such as PRM*, RRT*, and FMT*. The objective of this paper is to fill this gap. Specifically, this paper presents a bi-directional, sampling-based, asymptotically-optimal algorithm named Bi-directional FMT* (BFMT*) that extends the Fast Marching Tree (FMT*) algorithm to bidirectional search while preserving its key properties, chiefly lazy search and asymptotic optimality through convergence in probability. BFMT* performs a two-source, lazy dynamic programming recursion over a set of randomly-drawn samples, correspondingly generating two search trees: one in cost-to-come space from the initial configuration and another in cost-to-go space from the goal configuration. Numerical experiments illustrate the advantages of BFMT* over its unidirectional counterpart, as well as a number of other state-of-the-art planners.

    @inproceedings{StarekGomezEtAl2015,
      author = {Starek, J. A. and Gomez, J. V. and Schmerling, E. and Janson, L. and Moreno, L. and Pavone, M.},
      title = {An Asymptotically-Optimal Sampling-Based Algorithm for Bi-directional Motion Planning},
      booktitle = {{IEEE/RSJ Int. Conf. on Intelligent Robots \& Systems}},
      year = {2015},
      address = {Hamburg, Germany},
      doi = {10.1109/IROS.2015.7353652},
      month = sep,
      url = {/wp-content/papercite-data/pdf/Starek.Gomez.ea.IROS15.pdf},
      owner = {bylard},
      timestamp = {2017-03-07}
    }
    
  21. S. Singh, E. Schmerling, and M. Pavone, “Decentralized Algorithms for 3D Symmetric Formations in Robotic Networks - A Contraction Theory Approach,” in Proc. IEEE Conf. on Robotics and Automation, Seattle, Washington, 2015.

    Abstract: This paper presents distributed algorithms for formation control of multiple robots in three dimensions. In particular, we leverage the mathematical properties of cyclic pursuit along with results from contraction and partial contraction theory to design distributed control algorithms ensuring global convergence to symmetric formations. As a base case we consider regular polygons as desired formations and then provide extensions to Johnson solid formations. Finally, we analyze the robustness of the control algorithms under bounded additive disturbances and provide performance bounds with respect to the formation error.

    @inproceedings{SinghSchmerlingEtAl2015,
      author = {Singh, S. and Schmerling, E. and Pavone, M.},
      title = {Decentralized Algorithms for {3D} Symmetric Formations in Robotic Networks - A Contraction Theory Approach},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2015},
      address = {Seattle, Washington},
      doi = {10.1109/ICRA.2015.7139355},
      month = may,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {/wp-content/papercite-data/pdf/Singh.Pavone.ICRA2015.pdf}
    }
    
  22. E. Schmerling, L. Janson, and M. Pavone, “Optimal Sampling-Based Motion Planning under Differential Constraints: the Driftless Case,” in Proc. IEEE Conf. on Robotics and Automation, Seattle, Washington, 2015.

    Abstract: Motion planning under differential constraints is a classic problem in robotics. To date, the state of the art is represented by sampling-based techniques, with the Rapidly-exploring Random Tree algorithm as a leading example. Yet, the problem is still open in many aspects, including guarantees on the quality of the obtained solution. In this paper we provide a thorough theoretical framework to assess optimality guarantees of sampling-based algorithms for planning under differential constraints. We exploit this framework to design and analyze two novel sampling-based algorithms that are guaranteed to converge, as the number of samples increases, to an optimal solution (namely, the Differential Probabilistic RoadMap algorithm and the Differential Fast Marching Tree algorithm). Our focus is on driftless control-affine dynamical models, which accurately model a large class of robotic systems. In this paper we use the notion of convergence in probability (as opposed to convergence almost surely): the extra mathematical flexibility of this approach yields convergence rate bounds - a first in the field of optimal sampling-based motion planning under differential constraints. Numerical experiments corroborating our theoretical results are presented and discussed.

    @inproceedings{SchmerlingJansonEtAl2015,
      author = {Schmerling, E. and Janson, L. and Pavone, M.},
      title = {Optimal Sampling-Based Motion Planning under Differential Constraints: the Driftless Case},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2015},
      note = {{Extended version available at }\url{http://arxiv.org/abs/1403.2483/}},
      address = {Seattle, Washington},
      doi = {10.1109/ICRA.2015.7139514},
      month = may,
      url = {http://arxiv.org/pdf/1403.2483.pdf},
      owner = {bylard},
      timestamp = {2018-06-30}
    }
    
  23. L. Janson, E. Schmerling, A. Clark, and M. Pavone, “Fast Marching Tree: A Fast Marching Sampling-Based Method for Optimal Motion Planning in Many Dimensions,” Int. Journal of Robotics Research, vol. 34, no. 7, pp. 883–921, 2015.

    Abstract: In this paper we present a novel probabilistic sampling-based motion planning algorithm called the Fast Marching Tree algorithm (FMT*). The algorithm is specifically aimed at solving complex motion planning problems in high-dimensional configuration spaces. This algorithm is proven to be asymptotically optimal and is shown to converge to an optimal solution faster than its state-of-the-art counterparts, chiefly PRM* and RRT*. The FMT* algorithm performs a "lazy" dynamic programming recursion on a predetermined number of probabilistically-drawn samples to grow a tree of paths, which moves steadily outward in cost-to-arrive space. As a departure from previous analysis approaches that are based on the notion of almost sure convergence, the FMT* algorithm is analyzed under the notion of convergence in probability: the extra mathematical flexibility of this approach allows for convergence rate bounds–the first in the field of optimal sampling-based motion planning. Specifically, for a certain selection of tuning parameters and configuration spaces, we obtain a convergence rate bound of order O(n-1/d+rho), where n is the number of sampled points, d is the dimension of the configuration space, and rho is an arbitrarily small constant. We go on to demonstrate asymptotic optimality for a number of variations on FMT*, namely when the configuration space is sampled non-uniformly, when the cost is not arc length, and when connections are made based on the number of nearest neighbors instead of a fixed connection radius. Numerical experiments over a range of dimensions and obstacle configurations confirm our theoretical and heuristic arguments by showing that FMT*, for a given execution time, returns substantially better solutions than either PRM* or RRT*, especially in high-dimensional configuration spaces and in scenarios where collision-checking is expensive.

    @article{JansonSchmerlingEtAl2015,
      author = {Janson, L. and Schmerling, E. and Clark, A. and Pavone, M.},
      title = {{Fast} {Marching} {Tree:} A Fast Marching Sampling-Based Method for Optimal Motion Planning in Many Dimensions},
      journal = {{Int. Journal of Robotics Research}},
      volume = {34},
      number = {7},
      pages = {883--921},
      year = {2015},
      doi = {10.1177/0278364915577958},
      url = {http://arxiv.org/pdf/1306.3532.pdf},
      owner = {bylard},
      timestamp = {2017-02-20}
    }