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
-
R. Sinha, A. Elhafsi, C. Agia, M. Foutter, E. Schmerling, and M. Pavone, “Real-Time Anomaly Detection and Planning with Large Language Models,” in Robotics: Science and Systems, 2024. (Submitted)
Abstract: Foundation models, e.g., large language models, trained on internet-scale data possess zero-shot generalization capabilities that make them a promising technology for anomaly detection for robotic systems. Fully realizing this promise, however, poses two challenges: (i) mitigating the considerable computational expense of these models such that they may be applied online, and (ii) incorporating their judgement regarding potential anomalies into a safe control framework. In this work we present a two-stage reasoning framework: a fast binary anomaly classifier based on analyzing observations in an LLM embedding space, which may trigger a slower fallback selection stage that utilizes the reasoning capabilities of generative LLMs. These stages correspond to branch points in a model predictive control strategy that maintains the joint feasibility of continuing along various fallback plans as soon as an anomaly is detected (while the selector decides), thus ensuring safety. We demonstrate that, even when instantiated with relatively small language models, our fast anomaly classifier outperforms autoregressive reasoning with state-of-the-art GPT models. This enables our runtime monitor to improve the trustworthiness of dynamic robotic systems under resource and time constraints.
@inproceedings{SinhaElhafsiEtAl2024, author = {Sinha, R. and Elhafsi, A. and Agia, C. and Foutter, M. and Schmerling, E. and Pavone, M.}, title = {Real-Time Anomaly Detection and Planning with Large Language Models}, booktitle = {{Robotics: Science and Systems}}, keywords = {sub}, note = {Submitted}, year = {2024}, owner = {rhnsinha}, timestamp = {2024-03-01} } -
L. Paparusso, S. Kousik, E. Schmerling, F. Braghin, and M. Pavone, “ZAPP! Zonotope Agreement of Prediction and Planning for Continuous-Time Collision Avoidance with Discrete-Time Dynamics,” in Proc. IEEE Conf. on Robotics and Automation, 2024. (Submitted)
Abstract: The past few years have seen immense progress on two fronts that are critical to safe, widespread mobile robot deployment: predicting uncertain motion of multiple agents, and planning robot motion under uncertainty. However, the numerical methods required on each front have resulted in a mismatch of representation for prediction and planning. In prediction, numerical tractability is usually achieved by coarsely discretizing time, and by representing multimodal multi-agent interactions as distributions with infinite support. On the other hand, safe planning typically requires very fine time discretization, paired with distributions with compact support, to reduce conservativeness and ensure numerical tractability. The result is, when existing predictors are coupled with planning and control, one may often find unsafe motion plans. This paper proposes ZAPP (Zonotope Agreement of Prediction and Planning) to resolve the representation mismatch. ZAPP unites a prediction-friendly coarse time discretization and a planning-friendly zonotope uncertainty representation; the method also enables differentiating through a zonotope collision check, allowing one to integrate prediction and planning within a gradient-based optimization framework. Numerical examples show how ZAPP can produce safer trajectories compared to baselines in interactive scenes.
@inproceedings{PaparussoKousikEtAl2024, title = {{ZAPP!} Zonotope Agreement of Prediction and Planning for Continuous-Time Collision Avoidance with Discrete-Time Dynamics}, author = {Paparusso, L. and Kousik, S. and Schmerling, E. and Braghin, F. and Pavone, M.}, booktitle = {{Proc. IEEE Conf. on Robotics and Automation}}, owner = {rdyro}, timestamp = {2023-09-28}, keywords = {sub}, year = {2024}, url = {/wp-content/papercite-data/pdf/Paparusso.ea.ICRA24.pdf} } -
R. Luo, R. Sinha, Y. Sun, A. Hindy, S. Zhao, S. Savarese, E. Schmerling, and M. Pavone, “Online Distribution Shift Detection via Recency Prediction,” in Proc. IEEE Conf. on Robotics and Automation, 2024. (In Press)
Abstract: When deploying modern machine learning-enabled robotic systems in high-stakes applications, detecting distributional shift is critical. However, most existing methods for detecting distribution shift are not well-suited to robotics settings, where data often arrives in a streaming fashion and may be very high-dimensional. In this work, we present an online method for detecting distributional shift with guarantees on the false positive rate — i.e., when there is no distribution shift, our system is very unlikely (with probability < ε) to falsely issue an alert; any alerts that are issued should therefore be heeded. Our method is specifically designed for efficient detection even with high dimensional data, and it empirically achieves up to 6x faster detection on realistic robotics settings compared to prior work while maintaining a low false negative rate in practice (whenever there is a distribution shift in our experiments, our method indeed emits an alert).
@inproceedings{LuoSinhaEtAl2023, author = {Luo, R. and Sinha, R. and Sun, Y. and Hindy, A. and Zhao, S. and Savarese, S. and Schmerling, E. and Pavone, M.}, booktitle = {{Proc. IEEE Conf. on Robotics and Automation}}, title = {Online Distribution Shift Detection via Recency Prediction}, year = {2024}, keywords = {press}, note = {In press}, url = {https://arxiv.org/abs/2211.09916}, owner = {rdyro}, timestamp = {2022-09-21} } -
A. Hindy, R. Luo, S. Banerjee, J. Kuck, E. Schmerling, and M. Pavone, “Diagnostic Runtime Monitoring with Martingales,” in Robotics: Science and Systems, 2024. (Submitted)
Abstract: Machine learning systems deployed in safety-critical robotics settings must be robust to distribution shifts. However, system designers must understand the cause of a distribution shift in order to implement the appropriate intervention or mitigation strategy and prevent system failure. In this paper, we present a novel framework for diagnosing distribution shifts in a streaming fashion by deploying multiple stochastic martingales simultaneously. We show that knowledge of the underlying cause of a distribution shift can lead to proper interventions over the lifecycle of a deployed system. Our experimental framework can easily be adapted to different types of distribution shifts, models, and datasets. We find that our method outperforms existing work on diagnosing distribution shifts in terms of speed, accuracy, and flexibility, and validate the efficiency of our model in both simulated and live hardware settings.
@inproceedings{HindyLuoEtAl2024, author = {Hindy, A. and Luo, R. and Banerjee, S. and Kuck, J. and Schmerling, E. and Pavone, M.}, title = {Diagnostic Runtime Monitoring with Martingales}, note = {Submitted}, booktitle = {{Robotics: Science and Systems}}, year = {2024}, address = {}, url = {}, keywords = {sub}, owner = {somrita}, timestamp = {2024-02-09} } -
R. Sinha, E. Schmerling, and M. Pavone, “Closing the Loop on Runtime Monitors with Fallback-Safe MPC,” in Proc. IEEE Conf. on Decision and Control, 2023.
Abstract: When we rely on deep-learned models for robotic perception, we must recognize that these models may behave unreliably on inputs dissimilar from the training data, compromising the closed-loop system’s safety. This raises fundamental questions on how we can assess confidence in perception systems and to what extent we can take safety-preserving actions when external environmental changes degrade our perception model’s performance. Therefore, we present a framework to certify the safety of a perception-enabled system deployed in novel contexts. To do so, we leverage robust model predictive control (MPC) to control the system using the perception estimates while maintaining the feasibility of a safety-preserving fallback plan that does not rely on the perception system. In addition, we calibrate a runtime monitor using recently proposed conformal prediction techniques to certifiably detect when the perception system degrades beyond the tolerance of the MPC controller, resulting in an end-to-end safety assurance. We show that this control framework and calibration technique allows us to certify the system’s safety with orders of magnitudes fewer samples than required to retrain the perception network when we deploy in a novel context on a photo-realistic aircraft taxiing simulator. Furthermore, we illustrate the safety-preserving behavior of the MPC on simulated examples of a quadrotor.
@inproceedings{SinhaSchmerlingEtAl2023, author = {Sinha, R. and Schmerling, E. and Pavone, M.}, title = {Closing the Loop on Runtime Monitors with Fallback-Safe MPC}, year = {2023}, keywords = {pub}, booktitle = {{Proc. IEEE Conf. on Decision and Control}}, url = {/wp-content/papercite-data/pdf/Sinha.Pavone.CDC23.pdf}, owner = {rhnsinha}, timestamp = {2023-04-12} } -
S. Newdick, N. Ongole, T. G. Chen, E. Schmerling, M. Cutkosky, and M. Pavone, “Motion Planning for a Climbing Robot with Stochastic Grasps,” in Proc. IEEE Conf. on Robotics and Automation, London, United Kingdom, 2023.
Abstract: Motion planning for a multi-limbed climbing robot must consider the robot’s posture, joint torques, and how it uses contact forces to interact with its environment. This paper focuses on motion planning for a robot that uses nontraditional locomotion to explore unpredictable environments such as a martian cave. Our robotic concept, ReachBot, uses extendable and retractable booms as limbs to achieve a large reachable workspace while climbing. Each extendable boom is capped by a microspine gripper optimized for grasping in martian caves. ReachBot leverages its large workspace to navigate around obstacles, over crevasses, and through challenging terrain. Our planning approach must be versatile to accommodate variable terrain features and be robust to mitigate risks from the stochastic nature of spiny grippers. In this paper, we introduce a graph traversal algorithm to select a discrete sequence of grasps based on available terrain features suitable for grasping. This discrete plan is complemented by a decoupled motion planner that considers the alternating phases of body movement and end-effector movement, using a combination of sampling-based planning and sequential convex programming to optimize individual phases. We use our motion planner to plan a trajectory across a simulated 2D cave environment with at least 95% probability of success and demonstrate improved robustness over a baseline trajectory. Finally, we verify our motion planning algorithm through experimentation on a 2D planar prototype.
@inproceedings{NewdickOngoleEtAl2023, author = {Newdick, Stephanie and Ongole, Nitin and Chen, Tony G. and Schmerling, Edward and Cutkosky, Mark and Pavone, Marco}, title = {Motion Planning for a Climbing Robot with Stochastic Grasps}, year = {2023}, booktitle = {{Proc. IEEE Conf. on Robotics and Automation}}, address = {London, United Kingdom}, doi = {10.1109/ICRA48891.2023.10160218}, owner = {somrita}, timestamp = {2024-02-29}, url = {https://arxiv.org/abs/2209.10687} } -
S. Newdick, T. G. Chen, B. Hockman, E. Schmerling, M. R. Cutkosky, and M. Pavone, “Designing ReachBot: System Design Process with a Case Study of a Martian Lava Tube Mission,” in IEEE Aerospace Conference, Big Sky, Montana, 2023.
Abstract: In this paper we present a trade study-based method to optimize the architecture of ReachBot, a new robotic concept that uses deployable booms as prismatic joints for mobility in environments with adverse gravity conditions and challenging terrain. Specifically, we introduce a design process wherein we analyze the compatibility of ReachBot’s design with its mission. We incorporate terrain parameters and mission requirements to produce a final design optimized for mission-specific objectives. ReachBot’s design parameters include (1) number of booms, (2) positions and orientations of the booms on ReachBot’s chassis, (3) boom maximum extension, (4) boom cross-sectional geometry, and (5) number of active/passive degrees-of-freedom at each joint. Using first-order approximations, we analyze the relationships between these parameters and various performance metrics including stability, manipulability, and mechanical interference. We apply our method to a mission where ReachBot navigates and gathers data from a martian lava tube. The resulting design is shown in Fig.1.
@inproceedings{NewdickChenEtAl2023, author = {Newdick, Stephanie and Chen, Tony G. and Hockman, Benjamin and Schmerling, Edward and Cutkosky, Mark R. and Pavone, Marco}, title = {Designing ReachBot: System Design Process with a Case Study of a Martian Lava Tube Mission}, year = {2023}, booktitle = {{IEEE Aerospace Conference}}, address = {Big Sky, Montana}, url = {https://arxiv.org/abs/2210.11534}, owner = {schneids}, timestamp = {2024-02-29} } -
R. Luo, S. Zhao, J. Kuck, B. Ivanovic, S. Savarese, E. Schmerling, and M. Pavone, “Sample-Efficient Safety Assurances using Conformal Prediction,” in Int. Journal of Robotics Research, 2023.
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{LuoZhaoEtAl2023, 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 = {{Int. Journal of Robotics Research}}, year = {2023}, owner = {rsluo}, timestamp = {2023-02-10}, url = {https://arxiv.org/abs/2109.14082} } -
A. Elhafsi, R. Sinha, C. Agia, E. Schmerling, I. A. D. Nesnas, and M. Pavone, “Semantic Anomaly Detection with Large Language Models,” Autonomous Robots, vol. 47, pp. 1035–1055, 2023.
Abstract:
@article{ElhafsiSinhaEtAl2023, author = {Elhafsi, A. and Sinha, R. and Agia, C. and Schmerling, E. and Nesnas, I. A. D and Pavone, M.}, title = {Semantic Anomaly Detection with Large Language Models}, journal = {{Autonomous Robots}}, volume = {47}, number = {}, pages = {1035–-1055}, year = {2023}, asl_month = oct, asl_abstract = {As robots acquire increasingly sophisticated skills and see increasingly complex and varied environments, the threat of an edge case or anomalous failure is ever present. For example, Tesla cars have seen interesting failure modes ranging from autopilot disengagements due to inactive traffic lights carried by trucks to phantom braking caused by images of stop signs on roadside billboards. These system-level failures are not due to failures of any individual component of the autonomy stack but rather system-level deficiencies in semantic reasoning. Such edge cases, which we call semantic anomalies, are simple for a human to disentangle yet require insightful reasoning. To this end, we study the application of large language models (LLMs), endowed with broad contextual understanding and reasoning capabilities, to recognize such edge cases and introduce a monitoring framework for semantic anomaly detection in vision-based policies. Our experiments apply this framework to a finite state machine policy for autonomous driving and a learned policy for object manipulation. These experiments demonstrate that the LLM-based monitor can effectively identify semantic anomalies in a manner that shows agreement with human reasoning. Finally, we provide an extended discussion on the strengths and weaknesses of this approach and motivate a research outlook on how we can further use foundation models for semantic anomaly detection. Our project webpage can be found at https://sites.google.com/view/llm-anomaly-detection.}, asl_doi = {10.1007/s10514-023-10132-6}, asl_url = {https://doi.org/10.1007/s10514-023-10132-6}, owner = {amine}, timestamp = {2024-02-29} } -
S. Banerjee, A. Sharma, E. Schmerling, M. Spolaor, M. Nemerouf, and M. Pavone, “Data Lifecycle Management in Evolving Input Distributions for Learning-based Aerospace Applications,” in IEEE Aerospace Conference, 2023.
Abstract: As input distributions evolve over a mission lifetime, maintaining performance of learning-based models becomes challenging. This paper presents a framework to incrementally retrain a model by selecting a subset of test inputs to label, which allows the model to adapt to changing input distributions. Algorithms within this framework are evaluated based on (1) model performance throughout mission lifetime and (2) cumulative costs associated with labeling and model retraining. We provide an open-source benchmark of a satellite pose estimation model trained on images of a satellite in space and deployed in novel scenarios (e.g., different backgrounds or misbehaving pixels), where algorithms are evaluated on their ability to maintain high performance by retraining on a subset of inputs. We also propose a novel algorithm to select a diverse subset of inputs for labeling, by characterizing the information gain from an input using Bayesian uncertainty quantification and choosing a subset that maximizes collective information gain using concepts from batch active learning. We show that our algorithm outperforms others on the benchmark, e.g., achieves comparable performance to an algorithm that labels 100% of inputs, while only labeling 50% of inputs, resulting in low costs and high performance over the mission lifetime.
@inproceedings{BanerjeeSharmaEtAl2022, author = {Banerjee, S. and Sharma, A. and Schmerling, E. and Spolaor, M. and Nemerouf, M. and Pavone, M.}, title = {Data Lifecycle Management in Evolving Input Distributions for Learning-based Aerospace Applications}, booktitle = {{IEEE Aerospace Conference}}, year = {2023}, url = {https://arxiv.org/abs/2209.06855}, owner = {somrita}, timestamp = {2022-09-14} } -
J. I. Alora, L. Pabon, J. Köhler, M. Cenedese, E. Schmerling, Z. M. N., G. Haller, and M. Pavone, “Robust Nonlinear Reduced-Order Model Predictive Control,” in Proc. IEEE Conf. on Decision and Control, Singapore, 2023.
Abstract: Real-world systems are often characterized by high-dimensional nonlinear dynamics, making them challenging to control in real time. While reduced-order models (ROMs) are frequently employed in model-based control schemes, dimensionality reduction introduces model uncertainty which can potentially compromise the stability and safety of the original high-dimensional system. In this work, we propose a novel reduced-order model predictive control (ROMPC) scheme to solve constrained optimal control problems for nonlinear, high-dimensional systems. To address the challenges of using ROMs in predictive control schemes, we derive an error bounding system that dynamically accounts for model reduction error. Using these bounds, we design a robust MPC scheme that ensures robust constraint satisfaction, recursive feasibility, and asymptotic stability. We demonstrate the effectiveness of our proposed method in simulations on a high-dimensional soft robot with nearly 10,000 states.
@inproceedings{AloraPabonEtAl2023, author = {Alora, J.I. and Pabon, L. and Köhler, J. and Cenedese, M. and Schmerling, E. and N., Zeilinger M. and Haller, G. and Pavone, M.}, title = {Robust Nonlinear Reduced-Order Model Predictive Control}, year = {2023}, keywords = {pub}, booktitle = {{Proc. IEEE Conf. on Decision and Control}}, address = {Singapore}, url = {https://arxiv.org/abs/2309.05746}, owner = {jjalora}, timestamp = {2023-09-11} } -
J. I. Alora, M. Cenedese, E. Schmerling, G. Haller, and M. Pavone, “Practical Deployment of Spectral Submanifold Reduction for Optimal Control of High-Dimensional Systems,” in IFAC World Congress, Yokohama, Japan, 2023.
Abstract: Real-time optimal control of high-dimensional, nonlinear systems remains a challenging task due to the computational intractability of their models. While several model-reduction and learning-based approaches for constructing low-dimensional surrogates of the original system have been proposed in the literature, these approaches suffer from fundamental issues which limit their application in real-world scenarios. Namely, they typically lack generalizability to different control tasks, ability to trade dimensionality for accuracy, and ability to preserve the structure of the dynamics. Recently, we proposed to extract low-dimensional dynamics on Spectral Submanifolds (SSMs) to overcome these issues and validated our approach in a highly accurate simulation environment. In this manuscript, we extend our framework to a real-world setting by employing time-delay embeddings to embed SSMs in an observable space of appropriate dimension. This allows us to learn highly accurate, low-dimensional dynamics purely from observational data. We show that these innovations extend Spectral Submanifold Reduction (SSMR) to real-world applications and showcase the effectiveness of SSMR on a soft robotic system.
@inproceedings{AloraCenedeseEtAl2023b, author = {Alora, J.I. and Cenedese, M. and Schmerling, E. and Haller, G. and Pavone, M.}, booktitle = {{IFAC World Congress}}, title = {Practical Deployment of Spectral Submanifold Reduction for Optimal Control of High-Dimensional Systems}, year = {2023}, address = {Yokohama, Japan}, owner = {somrita}, timestamp = {2024-02-29}, url = {/wp-content/papercite-data/pdf/Alora.Cenedese.IFAC23.pdf} } -
J. I. Alora, M. Cenedese, E. Schmerling, G. Haller, and M. Pavone, “Data-Driven Spectral Submanifold Reduction for Nonlinear Optimal Control of High-Dimensional Robots,” in Proc. IEEE Conf. on Robotics and Automation, London, United Kingdom, 2023.
Abstract: Modeling and control of high-dimensional, nonlinear robotic systems remains a challenging task. While various model- and learning-based approaches have been proposed to address these challenges, they broadly lack generalizability to different control tasks and rarely preserve the structure of the dynamics. In this work, we propose a new, data-driven approach for extracting low-dimensional models from data using Spectral Submanifold Reduction (SSMR). In contrast to other data-driven methods which fit dynamical models to training trajectories, we identify the dynamics on generic, low-dimensional attractors embedded in the full phase space of the robotic system. This allows us to obtain computationally-tractable models for control which preserve the system’s dominant dynamics and better track trajectories radically different from the training data. We demonstrate the superior performance and generalizability of SSMR in dynamic trajectory tracking tasks vis-a-vis the state of the art.
@inproceedings{AloraCenedeseEtAl2023, author = {Alora, J.I. and Cenedese, M. and Schmerling, E. and Haller, G. and Pavone, M.}, booktitle = {{Proc. IEEE Conf. on Robotics and Automation}}, title = {Data-Driven Spectral Submanifold Reduction for Nonlinear Optimal Control of High-Dimensional Robots}, year = {2023}, address = {London, United Kingdom}, doi = {10.1109/ICRA48891.2023.10160418}, owner = {somrita}, timestamp = {2024-02-29}, url = {https://arxiv.org/abs/2209.05712} } -
A. Wu, T. Lew, K. Solovey, E. Schmerling, and M. Pavone, “Robust-RRT: Probabilistically-Complete Motion Planning for Uncertain Nonlinear Systems,” in Int. Symp. on Robotics Research, 2022.
Abstract: Robust motion planning entails computing a global motion plan that is safe under all possible uncertainty realizations, be it in the system dynamics, the robot’s initial position, or with respect to external disturbances. Current approaches for robust motion planning either lack theoretical guarantees, or make restrictive assumptions on the system dynamics and uncertainty distributions. In this paper, we address these limitations by proposing the robust rapidly-exploring random-tree (Robust-RRT) algorithm, which integrates forward reachability analysis directly into sampling-based control trajectory synthesis. We prove that Robust-RRT is probabilistically complete (PC) for nonlinear Lipschitz continuous dynamical systems with bounded uncertainty. In other words, Robust-RRT eventually finds a robust motion plan that is feasible under all possible uncertainty realizations assuming such a plan exists. Our analysis applies even to unstable systems that admit only short-horizon feasible plans; this is because we explicitly consider the time evolution of reachable sets along control trajectories. Thanks to the explicit consideration of time dependency in our analysis, PC applies to unstabilizable systems. To the best of our knowledge, this is the most general PC proof for robust sampling-based motion planning, in terms of the types of uncertainties and dynamical systems it can handle. Considering that an exact computation of reachable sets can be computationally expensive for some dynamical systems, we incorporate sampling-based reachability analysis into Robust-RRT and demonstrate our robust planner on nonlinear, underactuated, and hybrid systems.
@inproceedings{WuLewEtAl2022, author = {Wu, A. and Lew, T. and Solovey, K. and Schmerling, E. and Pavone, M.}, booktitle = {{Int. Symp. on Robotics Research}}, title = {{Robust-RRT}: Probabilistically-Complete Motion Planning for Uncertain Nonlinear Systems}, year = {2022}, month = may, keywords = {pub}, owner = {lew}, timestamp = {2022-05-22}, url = {https://arxiv.org/abs/2205.07728} } -
R. Luo, S. Zhao, J. Kuck, B. Ivanovic, S. Savarese, E. Schmerling, and M. Pavone, “Sample-Efficient Safety Assurances using Conformal Prediction,” in Workshop on Algorithmic Foundations of Robotics, 2022.
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 = {{Workshop on Algorithmic Foundations of Robotics}}, year = {2022}, month = may, owner = {rsluo}, timestamp = {2021-09-20}, url = {https://arxiv.org/abs/2109.14082} } -
R. Sinha, S. Sharma, S. Banerjee, T. Lew, R. Luo, S. M. Richards, Y. Sun, E. Schmerling, and M. Pavone, “A System-Level View on Out-of-Distribution Data in Robotics,” 2022.
Abstract: When testing conditions differ from those represented in training data, so-called out-of-distribution (OOD) inputs can mar the reliability of black-box learned components in the modern robot autonomy stack. Therefore, coping with OOD data is an important challenge on the path towards trustworthy learning-enabled open-world autonomy. In this paper, we aim to demystify the topic of OOD data and its associated challenges in the context of data-driven robotic systems, drawing connections to emerging paradigms in the ML community that study the effect of OOD data on learned models in isolation. We argue that as roboticists, we should reason about the overall system-level competence of a robot as it performs tasks in OOD conditions. We highlight key research questions around this system-level view of OOD problems to guide future research toward safe and reliable learning-enabled autonomy.
@inproceedings{SinhaSharmaEtAl2022, author = {Sinha, R. and Sharma, S. and Banerjee, S. and Lew, T. and Luo, R. and Richards, S. M. and Sun, Y. and Schmerling, E. and Pavone, M.}, title = {A System-Level View on Out-of-Distribution Data in Robotics}, year = {2022}, keywords = {}, url = {https://arxiv.org/abs/2212.14020}, owner = {rhnsinha}, timestamp = {2022-12-30} } -
F. Mahlknecht, J. I. Alora, S. Jain, E. Schmerling, R. Bonalli, G. Haller, and M. Pavone, “Using Spectral Submanifolds for Nonlinear Periodic Control,” in Proc. IEEE Conf. on Decision and Control, 2022.
Abstract: Very high dimensional nonlinear systems arise in many engineering problems due to semi-discretization of the governing partial differential equations, e.g. through finite element methods. The complexity of these systems present computational challenges for direct application to automatic control. While model reduction has seen ubiquitous applications in control, the use of nonlinear model reduction methods in this setting remains difficult. The problem lies in preserving the structure of the nonlinear dynamics in the reduced order model for high-fidelity control. In this work, we leverage recent advances in Spectral Submanifold (SSM) theory to enable model reduction under well-defined assumptions for the purpose of efficiently synthesizing feedback controllers.
@inproceedings{MahlknechtAloraEtAl2022, author = {Mahlknecht, F. and Alora, J.I. and Jain, S. and Schmerling, E. and Bonalli, R. and Haller, G. and Pavone, M.}, booktitle = {{Proc. IEEE Conf. on Decision and Control}}, title = {Using Spectral Submanifolds for Nonlinear Periodic Control}, year = {2022}, keywords = {pub}, owner = {jjalora}, timestamp = {2022-11-22}, url = {https://arxiv.org/abs/2209.06573} } -
R. Luo, A. Bhatnagar, H. Wang, C. Xiong, S. Savarese, Y. Bai, S. Zhao, S. Ermon, E. Schmerling, and M. Pavone, “Local Calibration: Metrics and Recalibration,” in Proc. Conf. on Uncertainty in Artificial Intelligence, 2022.
Abstract: Probabilistic classifiers output confidence scores along with their predictions, and these confidence scores should be calibrated, i.e., they should reflect the reliability of the prediction. Confidence scores that minimize standard metrics such as the expected calibration error (ECE) accurately measure the reliability on average across the entire population. However, it is in general impossible to measure the reliability of an individual prediction. In this work, we propose the local calibration error (LCE) to span the gap between average and individual reliability. For each individual prediction, the LCE measures the average reliability of a set of similar predictions, where similarity is quantified by a kernel function on a pretrained feature space and by a binning scheme over predicted model confidences. We show theoretically that the LCE can be estimated sample-efficiently from data, and empirically find that it reveals miscalibration modes that are more fine-grained than the ECE can detect. Our key result is a novel local recalibration method LoRe, to improve confidence scores for individual predictions and decrease the LCE. Experimentally, we show that our recalibration method produces more accurate confidence scores, which improves downstream fairness and decision making on classification tasks with both image and tabular data.
@inproceedings{LuoEtAl2022, author = {Luo, R. and Bhatnagar, A. and Wang, H. and Xiong, C. and Savarese, S. and Bai, Y. and Zhao, S. and Ermon, S. and Schmerling, E. and Pavone, M.}, title = {Local Calibration: Metrics and Recalibration}, booktitle = {{Proc. Conf. on Uncertainty in Artificial Intelligence}}, year = {2022}, keywords = {pub}, owner = {rdyro}, timestamp = {2022-01-26}, url = {https://arxiv.org/abs/2102.10809} } -
R. Dyro, E. Schmerling, N. Arechiga, and M. Pavone, “Second-Order Sensitivity Analysis for Bilevel Optimization,” in Int. Conf. on Artificial Intelligence and Statistics, 2022.
Abstract: In this work we derive a second-order approach to bilevel optimization, a type of mathematical programming in which the solution to a parameterized optimization problem (the “lower” problem) is itself to be optimized (in the “upper” problem) as a function of the parameters. Many existing approaches to bilevel optimization employ first-order sensitivity analysis, based on the implicit function theorem (IFT), for the lower problem to derive a gradient of the lower problem solution with respect to its parameters; this IFT gradient is then used in a first-order optimization method for the upper problem. This paper extends this sensitivity analysis to provide second-order derivative information of the lower problem (which we call the IFT Hessian), enabling the usage of faster-converging second-order optimization methods at the upper level. Our analysis shows that (i) much of the computation already used to produce the IFT gradient can be reused for the IFT Hessian, (ii) errors bounds derived for the IFT gradient readily apply to the IFT Hessian, (iii) computing IFT Hessians can significantly reduce overall computation by extracting more information from each lower level solve. We corroborate our findings and demonstrate the broad range of applications of our method by applying it to problem instances of least squares hyperparameter auto-tuning, multi-class SVM auto-tuning, and inverse optimal control.
@inproceedings{DyroSchmerlingEtAl2022, author = {Dyro, R. and Schmerling, E. and Arechiga, N. and Pavone, M.}, title = {Second-Order Sensitivity Analysis for Bilevel Optimization}, booktitle = {{Int. Conf. on Artificial Intelligence and Statistics}}, year = {2022}, keywords = {pub}, owner = {rdyro}, url = {https://arxiv.org/abs/2205.02329}, timestamp = {2022-02-05} } -
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, vol. 7, no. 2, pp. 1447–1454, 2022.
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{CauligiCulbertsonEtAl2022, 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}}, volume = {7}, number = {2}, pages = {1447--1454}, year = {2022}, url = {http://arxiv.org/abs/2107.08143}, keywords = {pub}, owner = {acauligi}, timestamp = {2022-03-10} } -
R. Brown, E. Schmerling, N. Azizan, and M. Pavone, “A Unified View of SDP-based Neural Network Verification through Completely Positive Programming,” in Int. Conf. on Artificial Intelligence and Statistics, 2022.
Abstract: Verifying that input-output relationships of a neural network conform to prescribed operational specifications is a key enabler towards deploying these networks in safety-critical applications. Semidefinite programming (SDP)-based approaches to Rectified Linear Unit (ReLU) network verification transcribe this problem into an optimization problem, where the accuracy of any such formulation reflects the level of fidelity in how the neural network computation is represented, as well as the relaxations of intractable constraints. While the literature contains much progress on improving the tightness of SDP formulations while maintaining tractability, comparatively little work has been devoted to the other extreme, i.e., how to most accurately capture the original verification problem before SDP relaxation. In this work, we develop an exact, convex formulation of verification as a completely positive program (CPP), and provide analysis showing that our formulation is minimal—the removal of any constraint fundamentally misrepresents the neural network computation. We leverage our formulation to provide a unifying view of existing approaches, and give insight into the source of large relaxation gaps observed in some cases.
@inproceedings{BrownSchmerlingEtAl2022, author = {Brown, R. and Schmerling, E. and Azizan, N. and Pavone, M.}, title = {A Unified View of SDP-based Neural Network Verification through Completely Positive Programming}, booktitle = {{Int. Conf. on Artificial Intelligence and Statistics}}, year = {2022}, owner = {rabrown1}, timestamp = {2022-02-17} } -
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.
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}, month = apr, url = {https://arxiv.org/abs/2008.03880}, owner = {borisi}, timestamp = {2020-12-23} } -
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} } -
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}, number = {10--11}, pages = {1326--1345}, url = {https://arxiv.org/abs/2012.03390}, timestamp = {2020-10-13} } -
E. Schmerling, “Multimodal Modeling and Uncertainty Quantification for Robot Planning and Decision Making,” PhD thesis, Stanford University, Inst. for Computational & Mathematical Engineering, Stanford, California, 2019.
Abstract: Advances in mobile robot autonomy are poised to transform society: there is enormous demand for robots that can handle our commutes, manage our homes, provide assistance to our loved ones, and explore places too dangerous or too distant for us humans to set foot. Before this potential may be realized, however, robots must be able to contend with uncertainties arising from the unstructured, unpredictable, and often unforgiving world they aim to enter. This dissertation develops concepts, algorithms, and modeling frameworks for quantifying uncertainty in how a robot plans its course of action, how it carries out that plan, and how it interacts with its environment (in particular, with the humans around it). In each of these cases, these tools are motivated by the purpose of yielding actionable insights that improve the quality and computational efficiency of robot planning and decision making.
@phdthesis{Schmerling2019, author = {Schmerling, E.}, title = {Multimodal Modeling and Uncertainty Quantification for Robot Planning and Decision Making}, school = {{Stanford University, Inst. for Computational \& Mathematical Engineering}}, year = {2019}, address = {Stanford, California}, month = mar, url = {https://stacks.stanford.edu/file/druid:xx848nq8857/SchmerlingPhD-augmented.pdf}, owner = {bylard}, timestamp = {2021-12-06} } -
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} } -
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} } -
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} } -
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} } -
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} } -
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} } -
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} } -
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} } -
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} } -
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} } -
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} } -
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} } -
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} } -
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} } -
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} } -
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} } -
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} } -
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} }