Serialized Red-Green-Gray: Quicker Heuristic Validation of Edges in Dynamic Roadmap Graphs
Authors:
Yulie Arad,
Stav Ashur,
Marta Markowicz,
James D. Motes,
Marco Morales,
Nancy M. Amato
Abstract:
Motion planning in dynamic environments, such as robotic warehouses, requires fast adaptation to frequent changes in obstacle poses. Traditional roadmap-based methods struggle in such settings, relying on inefficient reconstruction of a roadmap or expensive collision detection to update the existing roadmap. To address these challenges we introduce the Red-Green-Gray (RGG) framework, a method that…
▽ More
Motion planning in dynamic environments, such as robotic warehouses, requires fast adaptation to frequent changes in obstacle poses. Traditional roadmap-based methods struggle in such settings, relying on inefficient reconstruction of a roadmap or expensive collision detection to update the existing roadmap. To address these challenges we introduce the Red-Green-Gray (RGG) framework, a method that builds on SPITE to quickly classify roadmap edges as invalid (red), valid (green), or uncertain (gray) using conservative geometric approximations. Serial RGG provides a high-performance variant leveraging batch serialization and vectorization to enable efficient GPU acceleration. Empirical results demonstrate that while RGG effectively reduces the number of unknown edges requiring full validation, SerRGG achieves a 2-9x speedup compared to the sequential implementation. This combination of geometric precision and computational speed makes SerRGG highly effective for time-critical robotic applications.
△ Less
Submitted 30 March, 2026;
originally announced March 2026.
SPITE: Simple Polyhedral Intersection Techniques for modified Environments
Authors:
Stav Ashur,
Maria Lusardi,
Marta Markowicz,
James Motes,
Marco Morales,
Sariel Har-Peled,
Nancy M. Amato
Abstract:
Motion planning in modified environments is a challenging task, as it
compounds the innate difficulty of the motion planning problem with a changing
environment. This renders some algorithmic methods such as probabilistic
roadmaps less viable, as nodes and edges may become invalid as a result of these
changes.
In this paper, we present a method of transforming any configuration
space g…
▽ More
Motion planning in modified environments is a challenging task, as it
compounds the innate difficulty of the motion planning problem with a changing
environment. This renders some algorithmic methods such as probabilistic
roadmaps less viable, as nodes and edges may become invalid as a result of these
changes.
In this paper, we present a method of transforming any configuration
space graph, such as a roadmap, to a dynamic data structure capable of updating
the validity of its nodes and edges in response to discrete changes in obstacle positions.
We use methods from computational geometry to compute 3D swept volume
approximations of configuration space points and curves to achieve 10-40
percent faster updates and up to 60 percent faster motion planning queries than previous algorithms while requiring a
significantly shorter pre-processing phase, requiring minutes instead of
hours needed by the competing method to achieve somewhat similar update times.
△ Less
Submitted 28 June, 2024;
originally announced July 2024.