MOTION PLANNING OF LEGGED ROBOTS: THE SPIDER ROBOT PROBLEM
Jean‐Daniel Boissonnat, Olivier Devillers, Leonbattista Donati, Franco P. Preparata · International Journal of Computational Geometry & Applications · 1995
We consider the problem of planning motions of a simple legged robot called the spider robot. The robot is modelled as a point where all its legs are attached, and the footholds where the robot can securely place its feet consist of a set of n points in the plane. We show that the space F of admissible and stable placements of such robots has size Θ(n 2 ) and can be constructed in O(n 2 log n) time and O(n 2 ) space. Once F has been constructed, we can efficiently solve several problems related to motion planning.