Collision-free Linkages
This section provides an overview on the collision-free linkage optimization problem.
Combinatorial Optimization
One of the approaches implements the algorithm developed by Li et al.[1]. A special thanks goes to the authors Zijia Li from KLMM, Chinese Academy of Sciences, China and Georg Nawratil from the Institute of Discrete Mathematics and Geometry, TU Wien, Austria, who kindly helped us to implement the algorithm.
Initial Configuration
The initial configuration is given as a set of points on a given mechanism joint axes.
In case of 6R mechanism, there will be 6 points that form the smallest polyline
connecting the axes. This is an unconstrained minimization problem, solved by
method CollisionFreeOptimization.smallest_polyline().
The objective function is to minimize the length of the polyline.
Collision Check
The collision check is performed by the method
RationalMechanism.collision_check(),
where the argument only_links is set to True, so only the links are checked
for collision. Additionally, it also excludes the check of the neighboring links,
which is not necessary. Then, for example in case of 6R mechanism, the collision check
is in this way reduced to solving 9 polynomial equations.
Combinatorial Search
The algorithm is implemented in the class
CollisionFreeOptimization.CombinatorialSearch.
It is based on shifting the initial configuration points along
the joint axes. The shift distance \(k\) is given as
where \(\tau\) is the step value (iteration index), \(l\) is the length of the smallest polyline and \(p\) is a user-defined length factor, by default set to 10.
The combination for every axis constist of 3 possible shifts \(\{-k, 0, k\}\). Therefore, for example in the case of 6R, one of the possible shifts of a single search is \(\{-k, -k, 0, 0, 0, k\}\), which is one of the 3^6 possible combinations, i.e. 729.
The large number of combinations and slow collision check using the polynomial solver makes the algorithm slow.
Offsetting the initial configuration
When a solution from the previous step is found, the algorithm continues in a similar way by adding an offset on the joint axes between link connections.
References: