The feasible path problem is solved for planning a collision-free path to translate an arbitrary polyhedral robot from an initial position to some goal position in a polyhedral environment. The shortest path problem entails finding the shortest feasible path. The authors present two versions of the window corner (WC) algorithm, which is a novel solution to the problems for the case of single and multistep translational paths for two dimensions, and then summarize the extension to the three-dimensional WC algorithm, for feasible paths. The concept of window corners in the polyhedral cone representation (PCR) is introduced, which reduces the search space. The PCR cones store constraints between boundary elements. The PCO representation has O(m) vertices compared to O(m/sup 2/) in a C-space representation. The WC algorithm was tested and an example from assembly path planning is presented.>

In this paper, we present a complete and ex- act algorithm for planning a geometrically feasible path for a polyhedral subassembly (robot) translating amongst poly- hedral obstacles. Our algorithm can be used to determine whether a pair of non-convex subassemblies can be separated by a sequence of fine-motions and, possibly, contact-motions, when the amount of free space tends to be severly limited. We present the three-dimensional Window Corner algorithm to plan feasible paths. The algorithm solves the FeosiblePath problem, in worst-case time O(m5) where m is the product of the number of vertices describing the robot and obstacles respectively. A Feasiblepath solution hierarchy, for assembly sequence planning, is described for incremental, straight-line and multi-step paths. The Polyhedral Cone Representation (PCR) is introduced to efficiently represent the geometrical constraints on trans- lation and as a basis for fast collision avoidance checks. We introduce the concept of Window Corners in the PCR and this results in a finite search space. The Polyhedral Cone Obstacle Representation (PCUR), which is a constructive representation of all boundary contact configurations, trans- forms the problem into that of a point moving amongst a col- lection, O(m), of convex obstacles. In comparison, the worst- case space complexity of the C-space boundary is O(m3). Certain contact-constrained, feasible motions, which lie on surfaces without interior points can be inaccessible in a typ id C-space representation.

An approach to geometric reasoning about the feasibility of translation motion of parts of assembly operations is demonstrated. The feasibility problem has been broken down hierarchically such that necessary conditions for less complex motions may be evaluated early, and the problem of planning arbitrarily complex part trajectories is not treated unless required for the specific design implementation. The determination of local motion feasibility using the polyhedral convex cone representation of contact constraints has been extended to the analysis of global transition feasibility using a polyhedral cone algebra. This representation has further been used for the formulation of the multistage translation problem where a simulated annealing optimization strategy and a reachability wave algorithm was used to efficiently search for feasible solutions.>