Authors: Stav Ashur, Marta Markowicz, Maria Lusardi, James Motes, Marco Morales, Sariel Har-Peled, Nancy M. Amato

arXiv: https://arxiv.org/pdf/2407.00259

Venue: WAFR 2024
DOI: 10.1007/978-3-032-09967-9_8
Link to Publication

Abstract:
In this paper, we present a method of transforming any configuration space graph, such as a roadmap produced by a sampling-based motion planning (SBMP) algorithm, 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. We achieve 10–40% faster updates and up to 60% faster motion planning queries than previous algorithms while requiring a significantly shorter pre-processing phase, on the order of minutes instead of the hours required by the previously best known method to achieve somewhat similar update times. 

@InProceedings{ashur-spite-24,
  author="Ashur, Stav
  and Lusardi, Maria
  and Markowicz, Marta
  and Motes, James
  and Morales, Marco
  and Har-Peled, Sariel
  and Amato, Nancy M.",
  title="SPITE: Simple Polyhedral Intersection Techniques for Motion Planning in Modified Environments",
  booktitle="Algorithmic Foundations of Robotics XVI, Volume 1",
  year="2026",
  publisher="Springer Nature Switzerland",
  address="Cham",
  pages="151--168",
  isbn="978-3-032-09967-9"
}