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 avoiding the obstacles in this thesis. This thesis will give a brief concern about the meaning of heuristic reasoning. To realize the heuristic reasoning, we propose several concepts of safety region and surface vector. Through computer simulations, we show that the performance of the proposed algorithm is superior to that of the virtual force field method in the local minima problem. Since the proposed algorithm is based on the vector approach, it has the metit of small demand for computing power. However, the proposed algorithm contains the local minima problem inherently. To remedy the oscillatory motion caused by new trap situation, we propose the variable coefficient method. Under the consideration of dynamic constraints for mobile robot, we present the local path-planner finally. To attain this, we introduce the angular transformation and the velocity control method. This proposed path-planner is feasible to guide on real time a mobile robot avoiding the stationary and moving obstacles and reaching the goal. Computer simulations are demonstrated to show the validity and effectiveness of the proposed algorithm.
일반적으로 이동 로봇의 경로 계획을 행하는 목적은 로봇의 초기점으로부터 목표점까지의 충돌 회피 최단 경로를 찾는 것이다. 이를 위한 경로 계획은 크게 전역적 경로 계획과 국지적 경로 계획으로 나뉜다. 본 논문에서는 이러한 전역적 경로 계획과 국지적 경로 계획 알고리즘을 각각 제안하였다.
우선 망/그래프 형태의 환경 모델 상에서 전역적 경로 계획을 행하는 것은 일반적인 그래프 모델 상에서의 최소 비용 경로 탐색 문제와 같음을 보이고, 흡필드 신경 회로망을 이용하여 이 문제를 해결하는 전역적 경로 계획 알고리즘을 제안하였다. 흡필드 신경 회로망의 동적 특성은 뉴런의 상태 변수가 주어진 에너지 함수의 경사 방향으로 움직여 최소점에 도달하게 되는 특징을 가지므로, 최소 비용 경로를 찾기 위해서는 에너지 함수의 최소점이 최소 비용 경로를 표현할 수 있어야 한다. 이를 위해서는 에너지 함수가 최소 비용 경로에 관한 제한 조건을 포함하여야 한다. 따라서 본 논문에서는 벡터를 이용한 망구조 모델을 제안하였다. 이 모델을 이용하여 에너지 함수를 표현한 뒤, 주어진 동적 특성식에서 흡필드 신경 회로망을 이용한 전역적 경로 계획 알고리즘을 구하였다. 일반적인 몇 가지 경우에 대한 모의 실험을 통하여 제안된 알고리즘이 타당함을 보였고, 제안된 알고리즘은 기존의 신경 회로망을 이용한 최소 비용 거리 탐색 알고리즘에 비하여 무비용 루프(zero cost loop)가 형성되지 않고 또한 양방향성이 없는 그래프 모델에 대해서도 적용할 수 있는 장점을 지닌다. 그리고 흡필드 신경 회로망은 전자 회로로 구현이 가능하므로, 기존의 알고리즘에 비하여 계산량이 작아지는 장점을 지닌다.
한편, 일반적으로 전체 환경 모델을 이용하여 실제 환경을 정확히 일치되게 표현하는 것의 거의 불가능하므로 전역적 경로 계획 외에도 센서 정보에 바탕을 둔 국지적 경로 계획이 필요하게 된다. 이러한 국지적 경로 계획에는 계산량이 작아서 이동 로봇을 실시간 제어할 수 있도록 하는 것이 일반적으로 요구된다. 본 논문에서는 경험적 추론은 이동 로봇이 장애물을 회피하기 위한 일종의 규칙을 나타내게 된다. 경험적 추론을 실제 경로 계획에 이용하기 위하여 안전 지역 및 표면 벡터의 개념을 제안하였다. 결국 벡터 방식에 근거하여 국지적 경로 계획을 행함으로써 계산량이 작아져서 이동 로봇의 실시간 제어가 가능해지는 장점을 얻을 수 있다. 모의 실험을 통하여 제안된 알고리즘이 가상힘계 방식 (virtual force field method)에서 발생하는 국부 최소점 문제를 해결하는 것을 보였고, 유효한 방법임을 보였다. 한편 기본적으로는 제안된 알고리즘은 벡터 방식에 기초하므로 벡터의 합이 0이 되는 곳에서 국부 최소점 문제를 가지게 된다. 따라서 새로이 발생한 국부 최소점 문제의 해결을 위해 가변 계수 방법 (variable coefficient method)을 제안하였다. 이러한 기본적인 국지적 경로 계획 알고리즘을 실제에 유사한 환경에 적용하기 위하여 조향각이나 속도에 제한이 있는 경우에 대하여 적용할 수 있도록 알고리즘을 수정하였다. 이를 위하여 각 변환과 속도 제어 방법(velocity control method)이 도입되었다. 이렇게 제안된 알고리즘은 움직이는 장애물이 존재하는 환경에서도 적용할 수 있는 장점을 지니며, 모의 실험을 통하여 제안된 알고리즘의 유효성과 타당성을 보였다.
