Strobe: 並列サブエポックPodでロボット経路最適化を加速するメタアルゴリズム
Strobe: An Acceleration Meta-algorithm for Optimizing Robot Paths using Concurrent Interleaved Sub-Epoch Pods
経路を「ポッド」と呼ばれる連続区間に分割し、隣接同色ポッドの干渉を避けつつ並列最適化するメタアルゴリズムを提案し、シミュレーションで速度と品質の両面で優れることを示した。
著者: Daniel Rakita, Bilge Mutlu, Michael Gleicher
分類: cs.RO
原文アブストラクト
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.
