Path-planning algorithm of mobile robot based on hopfield type neural network and heuristic reasoning

Abstract

Generally, the objective of path-planning algorithm is to find a collision-free optimal path between robot``s initial position and the goal. The path-planners for attaining this task may be divided into two groups: a global path-planner and a local path-planner. In this thesis, we focus on the development of the global and local path-planning algorithm respectively. We propose the global path-planner with the architecture of Hopfield type neural network for finding the minimum cost path on the directed graph, after showing that the global path-planning problem on the network/graph environmental model such as the MAKLINK graph model can be regarded as the minimum cost path finding problem on the directed graph. Since the dynamics of Hopfield model goes to the stable state in the gradient direction of the given energy function, we require an energy function so that the minimum cost path can be decoded from the final stable state of neural network. Therefore, the desired energy function should include the constrained conditions for the minimum cost path. To describe these constrained conditions, we present the vector-represented network model. After defining the energy function based on this model, we can design the global path-planner and then solve the global path-planning problem. Through computer simulations, we confirm the validity of the proposed algorithm. The proposed algorithm has some advantages that it does not form the zero cost loop and can be applied to the directional network model case, compared with previous algorithms using neural networks. On the other hand, the lack of information for entire environment often causes the failure of global path-planner. This is due to the reason that we cannot describe the real environment perfectly. Hence, we require a local path-planner. We establish the basic structure of local path-planner based on the heuristic reasoning. The new terminology, "heuristic reasoning" is introduced to represent the rule for avoi...