[논문 리뷰] Path Planning for the Mobile Robot: A Review

Path planning 관련 연구를 진행하기 위해 먼저 Review 논문을 읽어보기로 했다. 해당 논문은 2018년도에 작성된 논문이며 mobile robot의 path planning 방식에 대해 설명하고 있다.

여기서 Path planning이란?

로봇과 주위 환경에 대한 정보가 주어져 있을 때,
initial state에서 final state로 가기 위한 optimal 또는 sub optimal path를 찾는 것.

이제 논문에 대해 리뷰해보기로 한다.

Abstract

---

-> 로봇의 path planning의 경우 우수하면 우수할수록, 많은 시간을 절약을 할 수 있을 뿐만 아니라 로봇의 마모와 자본투자도 줄일 수 있다. 본 논문에서는 기존의 존재하는 mobile robot의 path planning 방식을 review. 모델링, 최적화 기준, 솔루션에 대해 설명한다.
-> GA (genetic algorithm), PSO (particle swarm optimization algorithm), APF (artificial potential field), and ACO (ant colony optimization algorithm) 방식의 접근이 가장 많이 사용되고 있다.

Introduction

---

robot이 복잡한 환경에서 자율적으로 주행을 하기 위해서는 path planning은 가장 기초적인 문제 중 하나다.

path planning의 전체적인 구조 및 분류

Path planning은 주위 환경 정보를 얻을 수 있는지에 따라 크게 두가지로 나누어진다.
-> Global Path planning - planning 전에 주위 정보들을 모두 안다.
-> Local Path Planning - 주위 정보를 모른다.

Review of Global Path Planning

---

Global path planning은 다음과 같은 step을 따른다.

path planning 과정

1. Environmental modeling
   1. 알려진 지도 정보에 따라 환경 모델링을 구축하여 모바일 로봇이 작업을 수행할 수 있는 실제 환경을 지도 피쳐 정보로 변환하여 편리하게 저장.
2. Optimization Criteria
   1. 목적 함수에 따라 최적화 진행
3. Path search algorithm
   1. Path search 알고리즘은 starting 지점과 target 지점 사이의 충돌에 자유로운 path를 찾는 것이 목적인데, path length, smoothness, safety degree 등 최적 criteria에 만족해야 한다.

Environmental modeling

path planning을 하기 전에 주위 환경을 적절한 모델링을 통해서 계산 시간을 줄일 수 있어야 한다.
5가지 접근법에 대해서 설명한다.

1. Framework Space Approach 문제를 단순화하기 위해 로봇을 점으로 정하고, 주변 장애물을 축소하며, 장애물과 경계와 충돌하지 않고 장애물 공간에서 자유롭게 이동할 수 있게 한다.
   1. Visibility Graph
      

      

      1. polygon은 장애물을 나타내는 데 사용되며, 각 end point는 모든 visible 꼭지점과 연결되어 최종 맵을 형성한다. polygon의 범위에서 꼭지점은 인접한 end point에 연결되므로 로봇은 polygon 가장자리를 따라 이동할 수 있다.
      2. 2차원의 작은 환경에서는 optimal한 path를 찾을 수 있지만 time complexity가 O(N^2)이다. 문제가 복잡해질수록 visibility graph는 매우 효율이 떨어진다.
   2. Voronoi Graph
      

      

      Voronoi graph

      1. 환경의 경계를 포함하여 가장 가까운 두개 이상의 workspace boundary에서 등거리인 점의 trajectory다.
      2. vertices는 세 개 이상의 boundary에서 등거리인 점들로 형성된다.
      3. edge는 정확히 두 장벽 경계에서 등거리인 점들로 형성된다.
      4. 보로노이 그래프의 장점은 계산 속도가 빠르다는것. 단점은 더 변이적인 장소라는 것.
   3. Tangent Graph
      

      

      Tangent graph

      1. 노드는 barrier boundaries의 tangent point를 나타내고, edge는 tangent point 사이의 충돌이 없는 공통 tangent point 또는 convex boundary segments를 나타낸다.
      2. O(K^2) 메모리가 필요하며, 여기서 K는 convex segments 수를 나타낸다. 단점은 제어 과정에서 위치 오류가 발생할 경우 로봇 충돌 가능성이 매우 높다는 점이다.
2. Free Space Approach
   1. Free space approach 장애물 사이에서 얻을 수 있는 free space를 구성하는 방법이다. 충돌 없는 경로를 생성하기 위해 MAKLINK라는 새로운 graph가 구축된다. 그래프는 free convex region 사이의 common free link의 중간점을 passing point로 사용하여 구축된다. 이 점들은 노드를 나타내며, 점들 사이의 연결은 그래프에서 호를 나타낸다. 연결되는 노드와 호의 수에 대해 검색할 graphic size를 최소화함으로써 충돌 없는 경로를 검색하는 복잡성이 대폭 감소한다.
   2. 장점: 보다 유연하고 네트워크 다이어그램을 유지하기가 쉽다. 로봇의 starting point와 target point를 유연하게 변경할 수 있다.
   3. 단점: 장애물이 많은 환경에서는 이 approach는 실패할 수 있으며 최적의 경로를 확보하지 못한다.
3. Cell Decomposition Approach
   

   

   approximate cell decomposition 방식 중 하나

   1. workspace를 cell 단위로 나누는 방식이다. 이 그리드들은 연결된 그래프를 형성하고 initial 그리드에서 target 그리드까지의 경로를 탐색한다. path는 일반적으로 셀의 ordinal number로 표현된다. 방식은 크게 두가지로 나뉜다.
      1. exact cell decomposition → freespace는 겹치지 않는 n개의 단위로 나뉜다. 이 n개의 합은 원래의 자유 공간과 정확히 동일하다.
      2. approximate cell decomposition → 모든 그리드는 미리 정해진 형태(직사각형 등)로 이루어진다. 전체 환경은 여러 개의 직사각형으로 나뉜다. 직사각형에 장애물이나 경계가 포함된 경우, 4개의 작은 직사각형으로 나누고 solution boundry에 도달할 때까지 연산이 반복된다.
4. Topological Method
   1. Topological Method는 차원을 줄이는 방법이며, 고차원 기하학 공간에서의 경로 계획 문제는 저차원에서의 연결성의 판별 문제(discriminant problem of connectivity)로 변형된다.
   2. cell decomposition 방법과 비교했을 때, 이 방식은 오직 obstacle의 개수에 따라 complexity가 결정되며, 적은 model building time과 저장공간을 요구한다. 따라서 topological method는 fast path planning이 가능하다.
   3. 해당 방식은 명확한 특성과 sparse한 장애물이 있는 경우에 적절하다. 그렇지 않은 경우 naviagtion control이 어렵다. 다른 단점으로는 네트워크 구축 과정 자체가 상당히 복잡해 장애물이 증가하거나 감소할 경우 네트워크를 수정하기 어렵다.
5. Probabilistic Roadmap Method
   1. 1994년에 제시된 방법으로 랜덤 샘플을 기반으로 undirected roadmap graph를 생성한다. $R=(N,E)$ 여기서 N은 random sampling으로 얻은 노드를 의미하고 E는 노드들을 연결하는 edge를 의미한다. starting point $s$ 와 finishing point $f$가 주어질 때 해당 방식은 $s$에 직접적으로 연결되어있는 $s^{'}$과 $f$에 직접적으로 연결되어 있는 $f^{'}$을 찾는 문제가 된다.

Optimization Criteria

path planning의 optimazation criteria에 대해서 설명. 크게 세가지로 나누어진다.

1. Path Length
   

   

   Path Length

2. Smoothness → 여기서 α β 는 weighted coefficients이고 DA는 desired variable보다 큰 편향각의 수, Nf는 path segments의 총 수, Smin은 path segments의 최소 수를 나타내는 수다.
   

   

   Smoothness

3. Safety Degree
   

   

   Safety Degree

   
   d는 j번째 segment와 가장 가까운 장애물 사이의 최소 거리이고 λ는 safety degree의 threshold이다.

Path Search Algorithm

global path planning을 위한 path search 알고리즘은 크게 두가지 카테고리로 나눌 수 있다.

• Heuristic approach.
• artificial intelligence algorithm.

1. Heuristic approach.
   1. Dijkstra Algorithm
      1. shortest path를 찾는 전형적인 알고리즘. 주 특징은 starting point를 중심으로 end point까지 확장된다.
      2. 그래프의 각 edge는 두 꼭짓점에 의해 순서가 지정된 쌍으로 형성된다. edge의 cost은 weight function에 의해 결정된다. 초기에 A가 비어있고. B가 A로 이동할 때마다 선택된 점은 starting point에서 점까지의 모든 edge의 가중치의 합이 최소화되도록 한다.
      3. 알고리즘이 노드를 많이 이동하게 되므로 효율성이 높지 않다.
   2. A* Algorithm
      1. Dijkstra Algorithm에서 발전된 알고리즘.
      2. 특정 노드부터 시작하여 현재 하위 노드의 가중치가 업데이트되며, 모든 노드가 통과될 때까지 가중치가 가장 작은 하위 노드를 사용하여 현재 노드를 업데이트한다.
      3. A* 알고리즘의 핵심은 평가 함수 f(n), f(n) = g(n) + h(n)를 설정하는 것이다. 여기서 g(n)는 초기 노드에서 노드 n까지의 실제 비용을 나타내고, h(n)는 state space에서 노드 n에서 target 노드까지의 최적 경로의 추정 비용을 나타낸다.
      4. h(n)은 주로 두 노드 사이의 Euclidean distance를 사용한다.
      5. A는 shortest path searching이 항상 target point의 방향으로 진행되도록 보장한다. Dijkstra 알고리즘에 비해 A 알고리즘의 경로 검색 효율이 더 높다.
   3. D* Algorithm
      1. A는 정적환경에서 사용되는 알고리즘이며 D는 좀 더 dynamic 환경에 초점을 맞췄다.
      2. D* 알고리즘의 problem space는 series of state로 표현되며 state는 로봇 위치의 방향을 나타낸다. D* 알고리즘의 원리는 기본적으로 A* 알고리즘의 원리와 동일하다.
2. Artificial Intelligence Algorithm
   1. ANN (artificial neural network)
      1. path planning은 perceptual space에서 behavior space로의 mapping의 일종으로, artificial neural network이 mapping 관계를 표현할 수 있다.
      2. neural network는 환경 간의 constraint를 설명하는 데 사용되며, energy는 path point의 함수로 정의된다. energy의 level은 path point의 위치에 따라 달라지며 로봇은 energy가 줄어드는 방향으로 움직인다. 이렇게 얻은 총 에너지가 가장 적은 경로는 장애물은 없지만 최단 경로 또는 최적경로는 아니다.
      3. 강화학습과 ANN을 결합한 아이디어도 존재.
      4. 로봇의 work space는 무작위로 구성돼 수학적 공식으로 설명하기 어렵다. 움직이는 환경을 설명하기 위한 신경망 topology를 확립하는 것도 어렵고 복잡하고 큰 구조 때문에 신경망의 무게를 설정하는 것도 어렵다.
   2. GA (genetic algorithm)
      

      

      Genetic Algorithm의 순서도

      1. 문제의 모든 가능한 solution을 chromosomes(염색체)로 인코딩한다. 그리고 모든 염색체는 초기 population을 형성한다. 일반적으로 global path planning에 사용된다.
      2. 기본적인 연산으로는 crossover, mutation, selection으로 구성된다.
      3. 초기 population이 생성된 후, 목표에 따라 각 개인의 fitness value를 계산하고 crossover operation, mutation operation, selection operation이 fitness value에 의해 결정된다.
      4. GA의 장점은 단순하고 robust하며 강력한 search 기능과 높은 search 효율성을 가지고 있다.
      5. 단점은 조기 convergence가 일어나기 쉽다. 그리고 문제의 최적 solution에 가까워질수록 알고리즘의 수렴속도가 떨어진다.
   3. ACO (Ant colony optimization)
      

      

      1. ACO의 기본 원리는 각 개미들이 reference로 걸어온 길에 pheromone을 방출하고 먹이를 찾는 동안 다른 개미들이 방출하는 pheromone도 인지한다는 것이다. 페로몬의 작용으로 ant colony는 서로 의사소통을 하고 길을 선택할 수 있다.
      2. 경로상의 페로몬이 다른 경로의 페로몬보다 많으면 ant colony는 자발적으로 이 경로로 이동하여 이동 중에 더 많은 페로몬을 방출하여 positive feedback의 메커니즘을 형성하는 페로몬의 농도가 더 높아진다.
      3. 시간이 지나면 짧은 경로의 페로몬 농도는 점점 높아지며 이를 선택하는 개미들이 점차 증가하는 반면 다른 경로의 페로몬 농도는 점차 낮아져 없어진다. 결국 ant colony 전체가 최적의 경로로 집중된다.
      4. nest에 충분한 개미가 있는 한, 이 개미들은 장애물을 피하기 위해 nest에서 음식으로 가는 가장 짧은 길을 찾는다.
      5. ACO는 global path planning 능력뿐만 아니라 개인 간의 시너지 효과도 가지고 있다. 환경에 대한 완전한 정보를 알 수 없더라도 더 나은 길을 찾을 수 있다는 장점이 있다.
      6. 알고리즘 초기에는 수렴속도가 느리고 연산시간이 많이 걸린다.
   4. PSO (Particle swarm optimization)
      1. 새들의 군집활동의 규칙성에 영감을 받아 만들어진 알고리즘이다. 처음에는 random solution으로 시작하고 iteration을 통해 optimal solution을 찾는다. 해당 알고리즘은 fitness value를 통해 solution의 quality를 평가하며 현재 검색된 최적 값을 마지막으로 비교하여 global 최적 값을 찾는다.
      2. 이 알고리즘은 쉽게 적용이 가능하며 정확도도 높고 빠르게 수렴한다.
      3. 하지만 local optimum에 빠지기 쉽다.
   5. SA (simulated annealing)
      1. Monte-Carlo의 반복적인 솔루션 전략에 기초한 확률론적 최적화 알고리즘이다.
      2. SA는 특정 높은 초기 온도에서 시작하여 온도 parameter의 지속적인 감소와 함께 probability jump의 특징과 결합된 solution spcae에서 목적 함수의 global optimal solution을 무작위로 찾는다.
      3. 이 알고리즘은 수렴 속도가 느리고 실행 시간이 길며 성능은 초기 값에 의존한다.

Review of Local Path Planning

---

local path planning 방식은 크게 다섯가지 카테고리로 나누어진다.
→ artificial potential field method, behavior decomposition method, cased-based Learning method, rolling windows algorithm, and artificial intelligence algorithm.

1. Artificial Potential Field
   

   

   Artificial potential field

   1. 해당 알고리즘은 physics 의 potential field 개념을 이용한 알고리즘이다. 이 개념은 물체의 움직임을 두 종류의 힘의 결과로 간주한다.
   2. planning space에 있는 로봇은 target point로부터 중력을 받고 장애물에 의해 밀려난다. 두 힘의 작용에 따라 로봇은 합력인 목표 지점을 향해 움직이며, 이동 과정에서 planning space의 장애물을 효과적으로 피하고 안전하게 target에 도달할 수 있다.
   3. 장점 : 실행 및 운영이 간편, 더 안전한 경로 획득, 적은 map 정보 필요하고 computing 자원을 많이 소비하지 않는다. 좀 더 smooth한 경로를 획득할 수 있다.
   4. 단점 : 장애물을 만나기 전에 큰 충격이 발생하기 쉽다. target point 가까이에 장애물이 존재하는 경우 로봇이 target point에 도달하지 못하게 하는 반발력이 커진다. locally optimal solution에 빠지기 쉽다.
2. Behavior Decomposition Method
   1. 해당 방식은 mobile robot path planning의 새로운 trend이다.
   2. navigation 문제를 collision avoidance, tracking, target guidance 등과 같은 relatively independent navigation unit으로 세분화하는 것입니다. 이러한 behavior unit은 센서와 액추에이터가 있는 완전한 motion control unit이며 navigation이 있다. 이러한 behavior unit은 전체 navigation 작업을 완료하기 위해 서로 조정한다.
3. Cased-Based Learning Method
   1. 모바일 로봇은 path planning에 앞서 적절한 case database를 구축해야 한다. 모바일 로봇이 새로운 문제에 직면하면, 확립된 case database에서 정보를 검색한다. 검색 결과를 비교, 분석해서 새로운 문제와 가장 유사한 solution을 찾는다.
4. Rolling Windows Algorithm
   1. 해당 알고리즘은 모바일로봇이 확보한 local environment information을 활용해 'window'를 구축하고, 자체 주변정보로 'window'를 recursive하게 계산해 path planning을 진행한다. rolling calculation의 각 단계에서 heuristic 방법에 의해 sub-targets을 얻은 다음 얻은 sub-target은 현재 rolling window에서 실시간 planning을 구현한다. rolling window를 이동하면서 planning task가 완료될 때까지 얻은 정보에 의해 sub-targets이 업데이트된다.
5. Artificial Intelligence Algorithm
   1. global path planning의 내용과 같다.

Conclusions

---

path planning 문제는 모바일 로봇의 중요한 연구 분야이다. 모바일로봇의 path planning 기술이 우수하면 많은 시간을 절약할 수 있을 뿐만 아니라 모바일로봇의 마모와 자본투자도 줄일 수 있다.
본 논문에서 다양한 방법론이 검토되었다.
GA, PSO, APF, ACO가 모바일 로봇의 path planning을 해결하기 위해 가장 많이 사용되는 네 가지 접근 방식임을 보여준다.
마지막으로, 모바일 로봇의 path planning에 대한 참조를 제공할 수 있는 향후 연구에 대해 논의한다. 향후 연구는 다음을 포함해야 한다.

1. 각각의 method들은 서로 다른 용도에 적합할 수 있다. 아직 위의 사례를 모두 해결할 수 있는 범용적인 알고리즘이나 방법은 없다. artificial immune algorithm, artificial bee colony 등과 같은 새로운 path planning 방법을 연구해야 한다. 특히 2개 이상의 알고리즘을 조합하여 solution의 품질과 효율성을 높여야 한다.
2. multi-sensor 정보는 path planning에 반영되어야 한다. multi-sensor information fusion 기술은 단일 센서의 불확실성과 정보 불완전성을 극복할 수 있다. 환경과 측정된 대상을 보다 정확하고 포괄적으로 이해하고 설명할 수 있다.
3. multi-robot의 task assignment, communication cooperation 및 path planning을 연구해야 한다.
4. high dimensional environment에서의 로봇 path planning을 연구해야 한다.
5. 공중로봇과 수중 로봇에 대해서도 조사해야한다.
6. 로봇 하단 제어 및 경로 계획 알고리즘의 조합을 조사해야 한다.

---

해당 논문에서는 path planning의 전반적인 내용을 다뤘다. 따라서 각각 알고리즘에 자세한 설명은 생략되어있다. 앞으로 관심이 가는 알고리즘을 위주로 논문을 리뷰하고 구현을 진행해 볼 예정이다.

Reference

https://www.mdpi.com/2073-8994/10/10/450