Title: Resolution-Exact Planner for Thick Non-Crossing 2-Link Robots,
Abstract: We consider the path planning problem for a 2-link robot amidst polygonal
obstacles. Our robot is parametrizable by the lengths $\ell_1, \ell_2>0$ of its
two links, the thickness $\tau \ge 0$ of the links, and an angle $\kappa$ that
constrains the angle between the 2 links to be strictly greater than $\kappa$.
The case $\tau>0$ and $\kappa \ge 0$ corresponds to "thick non-crossing"
robots. This results in a novel 4DOF configuration space ${\mathbb R}^2\times
({\mathbb T}\setminus\Delta(\kappa))$ where ${\mathbb T}$ is the torus and
$\Delta(\kappa)$ the diagonal band of width $\kappa$. We design a
resolution-exact planner for this robot using the framework of Soft Subdivision
Search (SSS). First, we provide an analysis of the space of forbidden angles,
leading to a soft predicate for classifying configuration boxes. We further
exploit the T/R splitting technique which was previously introduced for
self-crossing thin 2-link robots. Our open-source implementation in Core
Library achieves real-time performance for a suite of combinatorially
non-trivial obstacle sets. Experimentally, our algorithm is significantly
better than any of the state-of-art sampling algorithms we looked at, in timing
and in success rate.