Finding the maximally inscribed rectangle in a robot's workspace

In this paper we formulate an optimization based approach to determining th e maximally inscribed rectangle in a robot's workspace. The size and locati on of the maximally inscribed rectangle is an effective index for evaluatin g the size and quality of a robot's workspace. Such information is useful f or, e. g., optimal worktable placement, and the placement of cooperating ro bots. For general robot workspaces we show how the problem can be formulate d as a constrained nonlinear optimization problem possessing a special stru cture, to which standard numerical algorithms can be applied. Key to the ra pid convergence of these algorithms is the choice of a starting point; in t his paper we develop an efficient computational geometric algorithm for rap idly obtaining an approximate solution suitable as an initial starting poin t. We also develop an improved version of the algorithm of Haug et al. for calculating a robot's workspace boundary.