Capturing a convex object with three discs

This paper addresses the problem of capturing an arbitrary convex object P in the plane with three congruent disc-shaped robots. Given two stationary robots in contact with P, we characterize the set of positions of a third robot that prevent P from escaping to infinity and show that the computation of this so-called capture region reduces to the resolution of a visibility problem. We present two algorithms for solving this problem and computing the capture region when P is a polygon and the robots are points (zero-radius discs). The first algorithm is exact and has polynomial-time complexity. The second one uses simple hidden-surface removal techniques from computer graphics to output an arbitrarily accurate approximation of the capture region; it has been implemented and examples are presented.

Authors

• Jeff Erickson 0001
• Shripad Thite
• Fred Rothganger
• Jean Ponce

Keywords

• Robot sensing systems
• Robotics and automation
• H infinity control
• Mobile robots
• Computer graphics
• Kinematics
• Computer science
• Polynomials
• Grippers
• Fixtures
• Convex Objective
• Position Of The Robot
• Capture Region
• Polynomial Time Complexity
• Loss Of Generality
• Time Constant
• Free Space
• Robotic System
• Line Segment
• Object Motion
• Configuration Space
• Rigid Transformation
• Exact Algorithm
• Positive Axis
• Surface Patches
• Circular Arc
• Pair Of Edges
• Symmetric Way
• Critical Orientation
• Minkowski Sum