Curvature continuous path planning and path finding based on PH splines with tension. (July 2017)

• Record Type: Journal Article
• Authors: Donatelli, Marco; Giannelli, Carlotta; Mugnaini, Duccio; Sestini, Alessandra
• Is Part Of: Computer aided design. Volume 88(2017)
• Page Start: 14
• Page End: 30
• Publication Date: 2017-07
• Subjects: Path planning -- Path finding -- Obstacle avoidance -- Splines -- Pythagorean-hodograph curves -- Tension parameters; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2017.03.005
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: Planar curvature continuous path generation with obstacle avoidance is considered by dealing with environments described either in terms of a structure directly specifying the boundaries of the obstacles ( path planning ) or by an adjacency matrix associated with uniform cells covering the whole scene ( path finding ). The second representation can be obtained for example from an image segmentation method when only an image of the scene is available. The method is composed by two main steps: the first is devoted to produce an intermediate admissible polyline, while the second defines a final curvature continuous path. Since the shape of the intermediate piecewise linear path remarkably influences the smoothness of the final path, different approaches are proposed to solve the path planning/finding problem in the first step. Then the vertices of the previously produced polyline are interpolated by using a C 1 ∩ G 2 interpolation scheme with tension based on Pythagorean–hodograph (PH) splines which have attractive features for applications. A strategy based on the asymptotic analysis of the interpolation scheme is developed in order to get an automatic selection of the tension parameters. The results of several numerical experiments confirm the effectiveness of the method. Highlights: An automatic two–stage curvature continuous path planning approach is presented. The minimal cumulative angle polyline in the visibility graph is identified. Interpolation with C 1 ∩ G 2 PH splines with tension is adopted. A new strategy for the automatic selection of the tension parameters is introduced. Complex environments possibly described by images are also addressed.