ランダム化k-optによる協調動作計画
Coordinated Motion Planning Through Randomized k-Opt
複数の正方形ロボットを同時に動かす際の総移動距離やメイクスパンを最小化するため、初期解生成とランダム化k-opt局所探索を組み合わせた手法を提案し、CG:SHOP2021チャレンジで距離部門1位・メイクスパン部門3位を獲得した。
著者: Paul Liu, Jack Spalding-Jamieson, Brandon Zhang, Da Wei Zheng
分類: cs.CG, cs.RO
原文アブストラクト
This paper examines the approach taken by team gitastrophe in the CG:SHOP 2021 challenge. The challenge was to find a sequence of simultaneous moves of square robots between two given configurations that minimized either total distance travelled or makespan (total time). Our winning approach has two main components: an initialization phase that finds a good initial solution, and a $k$-opt local search phase which optimizes this solution. This led to a first place finish in the distance category and a third place finish in the makespan category.
