Modern robots are complex computer systems involving enormous amounts of software to handle everything from drivers to communicate to physical interfaces, middleware to communicate between disparate processes, and machine learning kernels to process incoming data to make decisions in real-time. Robots’ unique challenges (heterogeneous hardware, programmed and learned components, handling physical environments, emergent behavior in the real world, etc.) merit special consideration from the software used by practitioners and researchers. Developing software components, libraries, and robot systems requires understanding and shaping code around these distinguishing use cases.
Motion planning against sensor data is often a critical bottleneck in real-time robot control. For sampling-based motion planners, which are effective for high-dimensional systems such as manipulators, the most time-intensive component is collision checking. We present a novel spatial data structure, the collision-affording point tree (CAPT): an exact representation of point clouds that accelerates collision-checking queries between robots and point clouds by an order of magnitude, with an average query time of less than 10 nanoseconds on 3D scenes comprising thousands of points. With the CAPT, sampling-based planners can generate valid, high-quality paths in under a millisecond, with total end-to-end computation time faster than 60 FPS, on a single thread of a consumer-grade CPU. We also present a point cloud filtering algorithm, based on space-filling curves, which reduces the number of points in a point cloud while preserving structure. Our approach enables robots to plan at real-time speeds in sensed environments, opening up potential uses of planning for high-dimensional systems in dynamic, changing, and unmodeled environments.
@inproceedings{ramsey2024,author={Ramsey, Clayton W. and Kingston, Zachary and Thomason, Wil and Kavraki, Lydia E.},title={Collision-Affording Point Trees: SIMD-Amenable Nearest Neighbors for Fast Collision Checking},booktitle={Robotics: Science and Systems},year={2024},doi={10.15607/RSS.2024.XX.038},}
Modern sampling-based motion planning algorithms typically take between hundreds of milliseconds to dozens of seconds to find collision-free motions for high degree-of-freedom problems. This paper presents performance improvements of more than 500x over the state-of-the-art, bringing planning times into the range of microseconds and solution rates into the range of kilohertz, without specialized hardware. Our key insight is how to exploit fine-grained parallelism within sampling-based planners, providing generality-preserving algorithmic improvements to any such planner and significantly accelerating critical subroutines, such as forward kinematics and collision checking. We demonstrate our approach over a diverse set of challenging, realistic problems for complex robots ranging from 7 to 14 degrees-of-freedom. Moreover, we show that our approach does not require high-power hardware by also evaluating on a low-power single-board computer. The planning speeds demonstrated are fast enough to reside in the range of control frequencies and open up new avenues of motion planning research.
@inproceedings{thomason2024vamp,author={Thomason, Wil and Kingston, Zachary and Kavraki, Lydia E.},title={Motions in Microseconds via Vectorized Sampling-Based Planning},year={2024},booktitle={IEEE International Conference on Robotics and Automation},pages={8749--8756},doi={10.1109/ICRA57147.2024.10611190},}
Software Engineering for Robotics: Future Research Directions; Report from the 2023 Workshop on Software Engineering for Robotics
Claire Le Goues , Sebastian Elbaum , David Anthony , Z. Berkay Celik , Mauricio Castillo-Effen , and 5 more authors
@misc{Goues2024,title={Software Engineering for Robotics: Future Research Directions; Report from the 2023 Workshop on Software Engineering for Robotics},author={Goues, Claire Le and Elbaum, Sebastian and Anthony, David and Celik, Z. Berkay and Castillo-Effen, Mauricio and Correll, Nikolaus and Jamshidi, Pooyan and Quigley, Morgan and Tabor, Trenton and Zhu, Qi},journal={arXiv preprint arXiv:2401.12317},year={2024},note={Invited Contributor},}
Workshop
Dynamic Motion Planning from Perception via Accelerated Point Cloud Collision Checking
@inproceedings{Ramsey2024wksp,author={Ramsey, Clayton W. and Kingston, Zachary and Thomason, Wil and Kavraki, Lydia E.},title={Dynamic Motion Planning from Perception via Accelerated Point Cloud Collision Checking},booktitle={IEEE ICRA 2024 Workshop---Agile Robotics: From Perception to Dynamic Action},year={2024},}
Nominated for Best Paper for Industrial Robotics Research for Practicality.
Robowflex is a software library for robot motion planning in industrial and research applications, leveraging the popular MoveIt library and Robot Operating System (ROS) middleware. Robowflex takes advantage of the ease of motion planning with MoveIt while providing an augmented API to craft and manipulate motion planning queries within a single program. Robowflex’s high-level API simplifies many common use-cases while still providing access to the underlying MoveIt library. Robowflex is particularly useful for 1) developing new motion planners, 2) evaluation of motion planners, and 3) complex problems that use motion planning (e.g., task and motion planning). Robowflex also provides visualization capabilities, integrations to other robotics libraries (e.g., DART and Tesseract), and is complimentary to many other robotics packages. With our library, the user does not need to be an expert at ROS or MoveIt in order to set up motion planning queries, extract information from results, and directly interface with a variety of software components. We provide a few example use-cases that demonstrate its efficacy.
@inproceedings{kingston2022robowflex,author={Kingston, Zachary and Kavraki, Lydia E.},title={Robowflex: Robot Motion Planning with MoveIt Made Easy},booktitle={IEEE/RSJ International Conference on Intelligent Robots and Systems},year={2022},pages={3108--3114},doi={10.1109/IROS47612.2022.9981698},}
Recently, there has been a wealth of development in motion planning for robotic manipulationnew motion planners are continuously proposed, each with its own unique set of strengths and weaknesses. However, evaluating these new planners is challenging, and researchers often create their own ad-hoc problems for benchmarking, which is time-consuming, prone to bias, and does not directly compare against other state-of-the-art planners. We present MotionBenchMaker, an open-source tool to generate benchmarking datasets for realistic robot manipulation problems. MotionBenchMaker is designed to be an extensible, easy-to-use tool that allows users to both generate datasets and benchmark them by comparing motion planning algorithms. Empirically, we show the benefit of using MotionBenchMaker as a tool to procedurally generate datasets which helps in the fair evaluation of planners. We also present a suite of over 40 prefabricated datasets, with 5 different commonly used robots in 8 environments, to serve as a common ground for future motion planning research.
@article{chamzas2021mbm,author={Chamzas, Constantinos and Quintero-Peña, Carlos and Kingston, Zachary and Orthey, Andreas and Rakita, Daniel and Gleicher, Michael and Toussaint, Marc and Kavraki, Lydia E.},title={MotionBenchMaker: A Tool to Generate and Benchmark Motion Planning Datasets},journal={IEEE Robotics and Automation Letters},year={2021},volume={7},number={2},pages={882--889},doi={10.1109/LRA.2021.3133603},}
Over the years, many motion planning algorithms have been proposed. It is often unclear which algorithm might be best suited for a particular class of problems. The problem is compounded by the fact that algorithm performance can be highly dependent on parameter settings. This paper shows that hyperparameter optimization is an effective tool in both algorithm selection and parameter tuning over a given set of motion planning problems. We present different loss functions for optimization that capture different notions of optimality. The approach is evaluated on a broad range of scenes using two different manipulators, a Fetch and a Baxter. We show that optimized planning algorithm performance significantly improves upon baseline performance and generalizes broadly in the sense that performance improvements carry over to problems that are very different from the ones considered during optimization.
@inproceedings{moll2021hyper,author={Moll, Mark and Chamzas, Constantinos and Kingston, Zachary and Kavraki, Lydia E.},title={HyperPlan: A Framework for Motion Planning Algorithm Selection and Parameter Optimization},booktitle={IEEE/RSJ International Conference on Intelligent Robots and Systems},year={2021},pages={2511-2518},doi={10.1109/IROS51168.2021.9636651},}
2017
Robonaut 2 and You: Specifying and Executing Complex Operations
Crew time is a precious resource due to the expense of trained human operators in space. Efficient caretaker robots could lessen the manual labor load required by frequent vehicular and life support maintenance tasks, freeing astronaut time for scientific mission objectives. Humanoid robots can fluidly exist alongside human counterparts due to their form, but they are complex and high-dimensional platforms. This paper describes a system that human operators can use to maneuver Robonaut 2 (R2), a dexterous humanoid robot developed by NASA to research co-robotic applications. The system includes a specification of constraints used to describe operations, and the supporting planning framework that solves constrained problems on R2 at interactive speeds. The paper is developed in reference to an illustrative, typical example of an operation R2 performs to highlight the challenges inherent to the problems R2 must face. Finally, the interface and planner is validated through a case-study using the guiding example on the physical robot in a simulated microgravity environment. This work reveals the complexity of employing humanoid caretaker robots and suggest solutions that are broadly applicable.
@inproceedings{baker2017r2,author={Baker, William and Kingston, Zachary and Moll, Mark and Badger, Julia and Kavraki, Lydia E.},title={Robonaut 2 and You: Specifying and Executing Complex Operations},booktitle={IEEE Workshop on Advanced Robotics and its Social Impacts},year={2017},pages={1--8},address={Austin, TX},month=mar,doi={10.1109/ARSO.2017.8025204},}