Reachable grasps on a polygon of a robot arm: Finding convex ropes without triangulation

December 2010

The convex rope problem, posed by Peshkin and Sanderson in IEEE J. Robotics & Automation, Vol. 2 (1986) pp. 53-58, is to find the counterclockwise and clockwise convex ropes starting at the vertex $a$ and ending at the vertex b of a simple polygon, where a is on the boundary of the convex hull of the polygon and $b$ is visible from infinity (i.e. there exists a ray m beginning at b, which does not intersect P anywhere else). Computation of these convex ropes is required to plan reachable grasps of a simple polygon by a simple robot arm. In this paper, we present a linear time algorithm for solving this problem without resorting to a linear-time triangulation algorithm and without resorting to a convex hull algorithm for the polygon. The counterclockwise (clockwise, respectively) convex rope consists of two polylines obtained in a basic incremental strategy described in convex hull algorithms for the polylines forming the polygon from a to b. The key idea is the use of Melkman's linear time convex algorithm for a polyline which loses its simplicity on the ray \bar m, beginning at b and in the opposite direction to m (such polyline is constructed by vertices inside the last convex hull in the incremental strategy and being left or on \bar m). Some advantages of the algorithm and numerical examples are presented.

Authors in the community:

• 

  P

  Phan Thanh An

  ist25034

International Journal of Robotics and Automation

304

310

25

4

computer-and-information-sciences - Computer and information sciences

eng - English