Authors: Yulie Arad, Stav Ashur, Marta Markowicz, James Motes, Marco Morales, Nancy M. Amato

arXiv: https://arxiv.org/abs/2603.28674

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 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. 

@article{arad-serrgg-26,
  title={Serialized Red-Green-Gray: Quicker Heuristic Validation of Edges in Dynamic Roadmap Graphs},
  author={Arad, Yulie and Ashur, Stav and Markowicz, Marta and Motes, James D and Morales, Marco and Amato, Nancy M},
  journal={arXiv preprint arXiv:2603.28674},
  year={2026}
}