motion planning
-
Coordinated Motion Planning Through Randomized k-OptJack Spalding-Jamieson, Paul Liu, Brandon Zhang, Da Wei Zheng
[pdf] [code]
This paper describes the heuristics and algorithms used by team gitastrophe in the CG:SHOP 2021 Competition. The contest was run in two categories with different optimization objectives: SUM and MAX. Team gitastrophe placed first overall in the SUM category, third overall in the MAX category, and first among junior teams for both categories.
-
Characterizing Minimum-Length Coordinated Motions for Two DiscsDavid Kirkpatrick and Paul Liu
[pdf]
We study the problem of planning coordinated motions for two disc robots in an otherwise obstacle-free plane. We give a characterization of collision-avoiding motions that minimize the total trace length of the disc centres, for all initial and final configurations of the robots. The individual traces are composed of at most six (straight or circular-arc) segments, and their total length can be expressed as a simple integral with a closed form solution depending only on the initial and final configuration of the robots.