WiTAH A*: Winding-Constrained Anytime Heuristic Search for a Pair of Tethered Robots

Abstract

In this paper, we propose a variant of the anytime hybrid A* algorithm that generates a fast but suboptimal solution before progressively optimizing the paths to find the shortest winding-constrained paths for a pair of tethered robots under curvature constraints. Specifically, our proposed algorithm uses a tangent graph as its underlying search graph and leverages an anytime A* search framework with appropriately defined cost metrics in order to reduce the overall computation and to ensure that a winding angle constraint is satisfied. Moreover, we prove the completeness and optimality of the algorithm for finding the shortest winding-constrained paths in an anytime fashion. The effectiveness of the proposed algorithm is demonstrated via simulation experiments.