The paper proposes a collision avoidance algorithm to solve the problem of (local) path planning for a three-dimensional (3D) object moving among polyhedral obstacles. The algorithm is based on a generalized potential model of workspace (J.-H. Chuang, 1998) which assumes that the boundary of every 3D object is uniformly charged. According to the proposed approach, the repulsive force and torque between the moving object and the obstacles due to the above model is used to adjust the position and orientation of the object so as to keep it away from the obstacles while passing through a bottleneck in the free space. Simulation results demonstrate that the path of a 3D object thus obtained is indeed safe and spatially smooth. The adopted potential field is analytically tractable which makes the path planning efficient.

In this paper, the potential-based skeletonization approach for 2D medial axis transform (MAT), which identifies object skeleton as potential valleys using a Newtonian potential model in place of the distance function, is generalized to three dimensions. The generalized potential functions given by Chung (1998), which decay faster with distance than the Newtonian potential, is used for the 3D case. The efficiency of the proposed approach results from the fact that these functions and their gradients can be obtained in closed forms for polyhedral surfaces. According to the simulation results, the skeletons obtained with the proposed approach are closely related to the corresponding MAT skeletons. While the medial axis (surface) is 2D in general for a 3D object, the potential valleys, being one-dimensional, form a more realistic skeleton. Other desirable attributes of the algorithm include stability against perturbations of the object boundary, the flexibility to obtain partial skeleton directly, and low time complexity.

One of the existing approaches to path planning problems uses a potential function to represent the topological structure of the free space. Newtonian potential was used in Chuang and Ahuja (1998) to represent object and obstacles in the two-dimensional (2-D) workspace wherein their boundaries are assumed to be uniformly charged. In this paper, more general, nonuniform distributions are considered. It is shown that for linear or quadratic source distributions, the repulsion between two polygonal objects can be evaluated analytically. Simulation results show that by properly adjusting the charge distribution along obstacle/object boundaries, path planning results ran be improved in terms of collision avoidance, path length, etc.