Motion Planning for Spatial Closed-Chains without Obstacles
Problem statement:
Given start (purple) and goal (red) configurations of a closed polygonal chain, determine an optimal trajectory connecting the start to the goal. We assume no joint limits, links can pass through each other, and no obstacles.
We have developed a low-order polynomial-time complete algorithm for solving this problem in 3D; if a solution exists, it will be found; if not, nonexistence will be reported. Our results are for 3D systems, but our implementation is for 2D systems only. You can see some of our solutions in action by clicking on the images below.
|
|
|
|
Here are some related papers: theory, algorithm description, conference version of algorithm description.
Competing techniques based on triangle inequality and linear programming
developed Li Han and Lee Rudolph from