Recent research from Rice University’s Kavraki Lab has made important advancements in the realm of motion planning, i.e., the breakdown of robotic movements for safety and optimization. With these hardware and algorithmic discoveries, robots can begin to move into a dynamic, unpredictable environment and make decisions faster and more reactively.
Motion planning has evolved drastically over the last few decades. Researchers have a strong understanding of motion planning—enabling a robot to compute continuous motions in a modeled, planned-out environment. But historically, this work has been hardware-intensive and time-intensive, not to mention infeasible outside a model space.
"Motion planning was classically considered to be an offline problem: you would have to do all your planning ahead of time," explains Clayton Ramsey, PhD student at Rice University. "These algorithms, which enable a robot to find collision-free movements, require thousands or tens of thousands of collision checks to produce a single plan. So if we want to create a motion plan in milliseconds, we need to have collision checks complete in nanoseconds."
"Can we start thinking about needing to plan as our environment changes, or under a strict time budget? What can we do to make these run efficiently in an online and somewhat more realistic environment?" he adds.
Lydia E. Kavraki, Noah Harding Professor of Computer Science and director of the Kavraki Lab at Rice University, is the senior author on a paper titled "Motions in Microseconds via Vectorized Sampling-Based Plan" with lead authors Wil Thomason and Zachary Kingston. This vector-accelerated planning work addresses the operational speed of classical motion planning: how fast can researchers accelerate motion planning in a static, fixed environment? Without specialized hardware, they were able to develop algorithmic improvements that resulted in better performance that was 500 times faster than existing models—meaning motion planning in microseconds.
“This is an amazing result. The state-of-the-art was a fraction of a second,” Kavraki said. “Our method required both algorithmic advances and excellent engineering. It applies to a whole class of algorithms called Sampling-Based Motion Planners. And what is more impressive is that the resulting planners can run on a low power architecture such as the Orange Pi with an ARM CPU.”
In a second paper titled, "Collision-Affording Point Trees: SIMD-Amenable Nearest Neighbors for Fast Collision Checking," researchers propose the collision affording point tree (CAPT), a data structure for collision checking. First author Ramsey, senior author Kavraki, and co-authors Kingston and Thomason take the aforementioned improved motion planning algorithms into the online domain, where robots can react to a changing environment while still avoiding obstacles.
Their research uses SIMD (single instruction/multiple data) parallelism, which unlocks algorithmic improvements that allow the proposed method to jump between purely sequential and purely parallel code very quickly with very little loss. SIMD parallelism offers big speedups for collision-checking by batching, but unlike typical multithreaded parallelism, SIMD requires that each parallel unit perform the same instruction at the same time. Thus, SIMD-parallel algorithms must be branchless (i.e., there are no "if" statements). The CAPT is special because it has a branchless collision-checking routine, which is not possible using traditional nearest-neighbor search methods for collision checking.
This work also reduces the hardware requirements of reactive online planning, as SIMD can be found on consumer-grade computers. By reducing the power-intensive needs of motion planning—which can be hard to deploy in a robot in the field—it enables robots with limited or low power computational capacity to effectively plan their motions, both in modeled environments in a lab and dynamic environments outside the lab.
Thus, robots can plan "in the loop": as their environment changes, they don't have to stop, plan, and then execute, but they can instead come up with a new plan in milliseconds and begin executing it immediately. Having a complete motion plan from start to goal is beneficial because it guarantees obstacle avoidance and progress toward the goal. This methodology can also be a building block for larger, more complex systems that require motion planning as an essential prerequisite capability.
As Ramsey explains, "The-long term goal of this work is to develop planning algorithms for robots that enable them to work in changing environments, around humans, and potentially around adversaries or unpredictable obstacles. Reactive planning is extremely hard to get right, and is generally considered to be very computationally expensive. And so if we can make it easier to develop reactive planning algorithms, if we can make it easier to run them on low power, low cost hardware. This can facilitate making robots more ubiquitous and more reliable in the real world."
“I am excited about this line of research,” Kavraki said. “This development, combined with recent advancements in AI, forces us to re-examine many of the choices and the solutions developed in robotics over the last decade. Our goal is to build reliable robots that will work for people and in support of people.”