| Title |
Analog Celluar Nonlinear Circuits-Based Dynamic Programming with Subgoal Setting |
| Authors |
김형석(Kim, Hyong-Suk) ; 박진희(Park, Jin-Hee) ; 손홍락(Son, Hong-Rak) ; 이재철(Lee, Jae-Chul) ; 이왕희(Lee, Wang-Hee) |
| Keywords |
optimal path planning ; dynamic programming ; Cellular Nonlinear Circuits ; sub-goal algorithm |
| Abstract |
A fast optimal path planning algorithm using the analog Cellular Nonlinear Circuits(CNC) is proposed. The analog circuits based optimal path planning is very useful since most of the optimal path planning problems require real time computation. There has already been a previous study to implement the dynamic programming with analog circuits. However, it could not be applied for the practically large size of problems since the algorithm employs the mechanism of reducing its input current/voltage by the amount of cost, which causes outputs of distant cells to become zero. In this study, a subgoal-based dynamic programming algorithm to compute the optimal path is proposed. In the algorithm, the optimal paths are computed regardless of the distance between the starting and the goal points. It finds subgoals starting from the starting point when the output of the starting cell is raised from its initial value. The subgoal is set as the next initial position to find the next subgoal until the final goal is reached. The global optimality of the proposed algorithm is discussed and two different kinds of simulations have been done for the proposed algorithm. |