Coordinated Motion Planning Through Randomized k-Opt
This solves a specific motion planning problem for robotics competitions, but it is incremental as it builds on existing local search methods.
The paper tackled the CG:SHOP 2021 challenge of planning simultaneous moves for square robots to minimize total distance or makespan, achieving first place in distance and third in makespan.
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.