ABSTRACT
In this section, we present strategies to estimate narrow passages and improved sampling algorithms based on the medial axis of the workspace.
Our algorithm computes a discretized Voronoi diagram of the workspace. With each voxel, we associate a color that corresponds to an ID of the closest obstacle and a distance value, which stores the distance to that obsta cle. By comparing this value against the dimensions of the robot, we can estimate the narrow passage in many cases. Given a robot R, let rout be the radius of min imum enclosing sphere and Vin be the radius of the maximum inscribed sphere. If we are given a subset of voxels on the Voronoi boundary, whose distance value is less than rout, then all the configurations whose cor responding positions in workspace (translation compo nents) are close the location of these voxels may contain “narrow passages.” In such cases, it may be difficult to plan the motions of the robot through these narrow passages, even when only translational displacements are required to navigate through the narrow corridors. Furthermore, if any collection of voxels on the Voronoi boundary have a distance value less than Tin, then all configurations whose translation components (or the corresponding positions in workspace) are close to the location cannot be contained in the free space.
