Mobile robot applications are found in a wide range of areas and demand for applications rises nowadays, which increases the study of mobile robotics. A path planning problem is one of the important issues. The path planning problem is to find a collision-free and optimal path for a mobile robot from a start point to a goal point in the given environment. There are many algorithms for the path planning of a mobile robot. Ant Colony Optimization (ACO) algorithm is one of the these algorithms. The first ACO algorithm has been successfully applied in the combinatorial optimization problems such as Traveling Salesman Problem (TSP) and Quadratic Assignment Problem (QAP). The path planning problem for the mobile robot is also one of the combinatorial optimization problems and there are many studies of the ACO algorithms for the path planning. However, these algorithms followed the lead of the previous ACO algorithm that applied the first time. As a result of these follow, it takes a lot of time to get the solution and it is not to easy to obtain the optimal path every time. It is also difficult to apply to the more complex and big-size maps that need increases.
The study of path planning can be divided in two classes: local and global. In the local planning case, the planning is based on the information given by sensors (ultrasonic, infrared, laser, cameras) installed on the robot. So this planning provides details about the local and unknown environment in real-time. On the other hand, in the global planning case, the model of environment is precisely defined and the planning is based on the information given previously. This approach improves the convergence towards the goal point. In the global path planning problem, we need to express the given environment as a considerable type of representation. There are generally four different types of representation. Among them, the composite-space map method is a very efficient and widely used. In the composite-space map method, the space is discretized into a grid of rectangular cells (or voxels) and each cell is marked as an obstacle or a non-obstacle. Eventually, the path is represented as a consecutive sequence of cells from a start point cell to a goal point cell. The complexity of the scene is expressed by the number of the cells n in the map. There are many algorithms using the composite-space map method such as $A^*$ algorithm, ACO algorithm, GA and so on. However, most algorithms with the composite-space map method use discrete state transitions that artificially constrain an agent`s movement to a small set of possible headings (e.g., 0, π/4, π/2 etc.). As a result, these algorithms produce unnatural, suboptimal and zigzag path and it is hard to apply to a physical mobile robot.
In this thesis, an novel ACO algorithm is proposed to solve the global path planning problems, called Heterogeneous ACO (HACO) algorithm. We study to improve the performance and to optimize the algorithm for the path panning of the mobile robot. The HACO algorithm differs from the Conventional ACO (CACO) algorithm for the path planning in three respects. We modify the Transition Probability Function (TPF) and the Pheromone Update Rule (PUR). We also propose the first introduction of the heterogeneous ants in the ACO algorithm. In the simulation, we apply the proposed HACO algorithm to general path planning problems. At the last, we compare the performance with the CACO algorithm.
이동 로봇의 응용 범위는 매우 광범위하며, 요즘은 이동 로봇을 응용한 제품의 수요도 증가하고 있어 이동 로봇에 관한 연구도 활발히 진행되고 있다. 이 중에서도 이동 로봇의 경로 계획의 문제는 중요한 연구 주제 중 하나이다. 이동 로봇의 경로 계획 문제는 이동 로봇이 출발점에서부터 도착점까지 장애물과의 충돌이 없는 최적의 경로를 찾는 문제인데, 많은 알고리즘들이 이동 로봇의 경로 계획 문제를 풀기 위해 개발되었다. 개미 군집 최적화 알고리즘도 그 중 하나이다. 개미 군집 최적화 알고리즘은 처음 제안될 때, TSP (Traveling Salesman Problem)나 QAP (Quadratic Assignment Problem)와 같은 조합 최적화 문제에 적용하여 성공적인 결과를 얻었다. 이동 로봇의 경로 계획 문제 또한 일종의 조합 최적화 문제로 개미 군집 최적화 알고리즘을 이용한 이동 로봇의 경로 계획에 관한 연구가 많이 이루어졌다. 하지만 이들은 기존의 최적화 문제에 적용되던 방식을 그대로 따르는 데에 따른 한계점을 드러냈다. 경로를 찾는데 많은 시간이 필요했고, 매번 최적의 경로를 찾는 것이 쉽지 않았다. 또한 요즘 요구되고 있는 보다 복잡하고 크기가 큰 지도에 적용하여 최적의 경로를 찾는 문제를 풀기에도 적합하지 않다.
이동 로봇의 경로 계획에는 크게 지역 경로 계획과 전역 경로 계획, 두 가지로 분류된다. 지역 경로 계획의 경우는 로봇에 장착된 센서들(예를 들면, 초음파, 적외선, 레이저, 카메라 등)로부터 얻어진 정보들을 활용하여 경로 계획이 이루어진다. 따라서 미지의 환경에 대하여 자세한 경로 계획하고자 할 때, 좁은 지역에 한하여 실시간으로 이루어지는 경로 계획이다. 반면 전역 경로 계획은 환경의 모델이 정확히 정의되고, 사전에 주어진 정보를 활용하여 경로 계획이 이루어진다. 전역 경로 계획은 도착점으로 향하는 수렴성을 강화하는 중요한 역할을 하며, 환경 모델이 미리 정의되어야 하기 때문에 주어진 환경, 즉 지도를 경로 계획이 가능한 형태로 표현하고 저장하는 작업이 사전에 이루어져야 한다. 여기에는 일반적으로 4가지의 형태의 표현 방법이 사용되는데, 이 중에서도 가장 널리 사용되며 효율적인 방법이 빈 공간-물체 복합 지도 표현 방법이다. 이 방법은 공간을 정사각형의 작은 요소들로 나눈 뒤, 각 요소들을 장애물과 비장애물로 표시하여 지도를 표현하는 방법이다. 따라서 이를 이용하면 출발점에서 도착점까지의 경로는 정사각형 요소들의 연속된 나열로 표현된다. 따라서 지도의 복잡도가 n개의 정사각형 요소의 수로 표현된다. $A^*$ 알고리즘, 유전자 알고리즘, 개미 군집 최적화 알고리즘 등이 이와 같은 지도 표현 방법을 이용하는 대표적인 알고리즘들이다. 하지만 빈 공간-물체 복합 지도 표현 방법을 이용한 알고리즘들로 생성된 경로는 이동시에 이동 가능한 진행의 각도가 0도, 45도, 90도등의 각도로 한정되기 때문에 생성된 경로가 부자연스러울 뿐만아니라, 지그재그 형태의 경로이다. 이는 실제의 이동 로봇에 적용하기에는 부적합한 형태의 경로이다.
본 논문에서는 이러한 기존의 개미 군집 최적화 알고리즘을 이용한 전역 경로 계획의 단점들을 보완한, 이동 로봇의 전역 경로 계획을 위한 새로운 개미 군집 최적화 알고리즘, Heterogeneous ACO (HACO) 알고리즘을 제안한다. HACO 알고리즘은 기존의 개미 군집 최적화 알고리즘 방법과는 다른 3가지 큰 차이점을 가지고 있다. 기존의 개미 군집 최적화 알고리즘의 성능을 향상하고 경로 계획에 최적화하기 위해, 개미의 이동 확률 함수 (TPF, Transition Probability Function)와 페르몬 갱신 규칙 (PUR, Pheromone Update Rule)을 수정하였고, 개미 군집 최적화 알고리즘에 사용하는 개미의 종류를 다양화하였다. 본 논문에서는 제안한 HACO 알고리즘을 구현하고, 이를 몇 가지 경로 계획 문제에 적용한다. 또한 그 성능을 기존의 개미 군집 최적화 알고리즘과 비교하여 검증하고자 한다.
