The application of ψ-transform for determining a near-optimal path in the presence of polyhedral obstacles

Abstract

The problem can be stated as follows: Given a set of simple polyhedra and two points belonging to the exterior domain of the given polyhedra, determine a near-optimal polygonal line connecting the two points so that the intersection of this polygonal line and the given polyhedra is an empty set. To solve this problem an algorithm is formed for generation of a set of admissible polygonal lines. On the basis of this set, using the optimisation procedure based on ψ-transform, a near-optimal polygonal line is determined. © 1992 Springer-Verlag.