We study the problem of motion-planning for free-flying multi-link robots and develop a sampling-based algorithm that is specifically tailored for this type of robots. Our work is based on the simple observation that the set of configurations for which the robot is self-collision free is independent of the obstacles or of the exact placement of the robot. This allows us to eliminate the need to perform costly self-collision checks online when solving motion-planning problems, assuming some offline preprocessing. In particular, given a specific robot our algorithm precomputes a tiling roadmap, which efficiently and implicitly encodes the self-collision free (sub-)space over the entire configuration space, where the latter can be infinite for that matter. To answer any query, in any given scenario, we traverse the tiling roadmap while only testing for collisions with obstacles. Our algorithm suggests more flexibility than the prevailing paradigm in which a precomputed roadmap depends both on the robot and on the scenario at hand. We show through various simulations the effectiveness of this approach. Specifically, in certain settings our algorithm is ten times faster than the RRT algorithm.
Illustration of the scenarios used in our experiments. Robot links and anchor points are depicted in solid blue lines and blue circles respectively. The head of the robot (red) needs to move to the target region (green circle) while avoiding the obstacles (gray polygons) and self intersection. In (a)–(c) the robot (with 11-13 degrees of freedom, respectively) is free-flying while in (d) the robot’s middle joint is anchored (black square) and both endpoints need to reach the target region (10 degree of freedom problem).