Path-planning을 할 때 사용하는 알고리즘 중 하나인 개미군집에 관한 논문을 리뷰하도록 하겠습니다.
* 논문에 실린 그림을 활용하였습니다.
* Title : Ant Colony Optimization Algorithm for Robot Path Planning
* Author : Michael Brand, Michael Masuda, Nicole Wehner and Xiao-Hua Yu
* Publication : International Conference On Computer Design And Applications. 2010
* Object : Path planning is classified as an NP(Nondeterministic polynomial time) complete problem. This paper solves NP complete problem by using the ACO algorithm based on swarm intelligence.
계산 복잡도 이론에 따르면 Path-planning은 NP(Nondeterministic polynomial time) complete problem으로 분류됩니다. 풀어야 할 사이즈가 커질수록 계산하는 시간이 기하급수적으로 늘어나는 단점을 해결하기 위해서 이 논문에서는 ACO(Ant Colony Optimization) 알고리즘을 사용했습니다. ACO 알고리즘은 Swarm intelligence라는, 떼지능에 기반하여 제작된 알고리즘으로 자세한 것은 아래에서 설명드리겠습니다.
# NP(Nondeterministic polynomial time) complete problem
위의 그림 중 NP-complete는 NP집합에 속하는 결정 문제 中 가장 어려운 문제의 부분집합으로, 이에 속한 것들 중 하나라도 P에 속한다면 모든 NP 문제가 P에 속하기 때문에 P=NP의 형태로 풀리게 됩니다.
그래서 P=NP=NP-complete라는 방식으로 진행이 됩니다.
# Swarm intelligence
다른 개체와 환경에 상호작용하는 개체로 만들어진 시스템입니다. 각 개체는 아주 간단한 규칙을 따라 행동하며, 전체 규칙을 알지 못하더라도 국지적이고 어느 정도는 무작위한 상호작용을 통해 지능적으로 보이는 전체 행동을 이끌어냅니다.
Path planning은 NP complete problem으로 분류되어서 roadmap approach, cell decomposition, potential field를 계산하는 데 높은 계산비용이 필요합니다. 때문에, 동적환경에서 풀기 어렵습니다. 때문에 이 논문에서는 Swarm intelligence에 기반한 ACO 알고리즘을 사용했습니다.
# ACO 알고리즘
이 알고리즘은 실제로 개미의 행동에 영감을 받아 제작된 알고리즘으로, 실험에 사용되는 변수에 대해서 아래에 설명해드리겠습니다.
알파는 페로몬 값의 정도를 말하고, 베타는 휴리스틱 값의 정도를 말합니다. 그리고 이타는 개미 k가 노드 i에서 노드 j까지 가는 데 필요한 휴리스틱 정보를 말하는 것이고, N은 노드 i에서 이동가능한 노드들을 말합니다. 타우는 개미 k가 노드 i에서 노드 j까지 갈 때의 페로몬 레벨을 말합니다.
위의 변수들을 모두 활용하여 개미 k가 노드 i에서 노드 j로 이동할 확률 p를 구합니다.
타우의 역수를 구해 개미 k가 경로 선택할 때의 cost값으로 선정했습니다.
# 실험
map의 Starting position(왼쪽 상부)에서 Ending position(우측 하부)로 가는데 필요한 최단경로를 구하는 시뮬레이션을 진행했고, 장애물은 임의의 위치에 2개가 설치됩니다.
실험 환경은 다음과 같습니다.
1) Clean environment : 장애물이 없는 clean한 환경에서 페로몬 값을 0.1로 초기화한 후 경로 찾기
2) Dynamic environment
- Local initialization : 장애물이 있는 환경에서 페로몬 값을 절반으로 낮춘 경우에서 경로 찾기
- Global initialization : 장애물이 있는 환경에서 페로몬 값을 0.1로 초기화한 후 경로 찾기
위의 그래프를 통해서 20x20 사이즈의 map에서 Clean environment 실험을 반복할수록 실험을 반복할수록 필요한 경로 거리가 줄어드는 것을 볼 수가 있습니다.
두 개의 표를 위에서 볼 수 있는데, 위의 표는 Local initialization, 아래의 표는 Global initialization을 한 것으로, 실험을 통해 구한 최적경로의 크기는 Local initialization할 때 더 작았습니다.
또한 최적경로를 찾는데 소요되는 반복횟수 또한 Local initialization할 때 확실하게 적은 것을 알 수 있습니다.
# 결론
이 논문에선 Mobile robot의 Path planning을 위한 격자구조 맵에서 가장 짧고 충돌하지 않는 경로를 찾을 때에 효과적인 ACO 알고리즘을 설명했습니다.
EAS(Elitist Ant System), MMAS(Max-Min Ant System) 등은 ACO 알고리즘에 기반한 것입니다.
이상으로 논문리뷰 마치도록 하겠습니다!
