Optimal Robot Path Planning With Cellular Neural Network

Related Work

The earliest work on robot path planning was by Lozano-Perez and Wesley (1979), who presented a path planning algorithm to avoid polyhedral obstacles based on a visibility graph. Since then, various approaches have been studied, especially during the past twenty years. Plenty of global approaches such as decomposition, road-map, distance transform and retraction methods, randomized approaches and genetic algorithms were reported to search the possible paths in the work space (Latombe, 1991; Hwang & Ahuja, 1992; Zelinsky, 1994; Henrich, 1997). A number of local methods such as potential field methods were also reported (Khatib, 1986; Barraquand & Latombe, 1991; Glasius, Komada, & Gielen, 1994; Li & Bui, 1998). Oriolo et al. (1998) proposed a method by combining global and local approaches for robot path planning, in which a global path planning plus a local graph search algorithm and several cost functions are used. Seshadri and Ghosh (1993) presented a path-planning model by using an iterative approach. This method is computationally complicated, especially in a complex work space. Ong and Gilbert (1998) presented a method for robot path planning with penetration growth distance. This method searches over collision paths instead of the free space, and it can generate optimal and continuous robot paths only in a static environment. In general, although most of the above methods can generate the accessible path with free collision in the work space, they can only deal with the static environment. A moving object or introduction of new objects requires that the whole work environment be constructed dynamically. In addition, with the increase of obstacles, the complexity of the algorithms increases exponentially.