In this paper, we present a meta-algorithm intended to accelerate many existing path optimization algorithms. The central idea of our work is to strategically break up a waypoint path into consecutive groupings called ``pods,'' then optimize over various pods concurrently using parallel processing. Each pod is assigned a color, either blue or red, and the path is divided in such a way that adjacent pods of the same color have an appropriate buffer of the opposite color between them, reducing the risk of interference between concurrent computations. We present a path splitting algorithm to create blue and red pod groupings and detail steps for a meta-algorithm that optimizes over these pods in parallel. We assessed how our method works on a testbed of simulated path optimization scenarios using various optimization tasks and characterize how it scales with additional threads. We also compared our meta-algorithm on these tasks to other parallelization schemes. Our results show that our method more effectively utilizes concurrency compared to the alternatives, both in terms of speed and optimization quality.

@InProceedings{RMG21a,
  author       = "Rakita, Daniel and Mutlu, Bilge and Gleicher, Michael",
  title        = "Strobe: An Acceleration Meta-algorithm for Optimizing Robot Paths using Concurrent Interleaved Sub-Epoch Pods",
  booktitle    = "IEEE International Conference on Robotics and Automation (ICRA).",
  month        = "jun",
  year         = "2021",
  ee           = "https://arxiv.org/abs/2106.00153",
  url          = "http://graphics.cs.wisc.edu/Papers/2021/RMG21a"
}