Proceedings of the 2003 IEEE International Conference on Robotics and Automation, 2242-2247, 2003.

Abstract:

This paper addresses the problem of capturing an arbitrary convex objectPin the plane with three congruent disc-shaped robots. Given two stationary robots in contact withP, we characterize the set of positions of a third robot that preventPfrom 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 whenPis 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.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 04 Dec 2003