A generalized practical approach to the free path finding problem, applied to a planar two-links robot with four degrees of freedom moving amidst polygonal obstacles

摘要

To cope with the vast variety of applications of the free pathfinding problem, a generalized but still practical approach was developed. A preliminary implementation for the special case of a planar two-link manipulator with four degrees of freedom is reported. Conceptually, two functions lead to a general free path finding algorithm: the pseudodistance function (PD(C)) which describes a relationship between the robot and its environment for any configuration (C); and the function PDL(t), which describes the variation of PD along a hyperline in configuration space. By properly capturing the concepts of adaptive discretization of configuration space, the approximate description of free space, a stepwise path improvement, a heuristic driven goal search, and of geometrical coherency, the algorithm can be practically implemented.