[Path][Survey]A Survey on Path Planning for Mobile Robot Systems

A Survey on Path Planning for Mobile Robot Systems | IEEE Conference Publication | IEEE Xplore

A Survey on Path Planning for Mobile Robot Systems

 

 

open-loop path

• 사전에 미리 계산된 경로나 궤적을 의미. 
  즉, 로봇이나 이동체가 실행중에 sensor로부터의 피드백 없이, 처음에 정해진 경로를 그래도 따라가도록 하는 방식 

 

closed-loop path

• Lavelle와 Lindemann은 open-loop가 가지는 피드백 부재로 인한 취약점을 보완하고자, 센서나 상태 측정을 가지고 실시간으로 경로 오차을 보정할수있는 closed-loop feedback law를 제안함,
• 즉, 미리 계산된 경로만 따르는 것이 아닌, 실제로 이동중인 로봇이 자신의 상태를 지속적으로 모니터링 하면서, 경로 이탈과 같은 예상치 못한 상황에 대응할수있게 제어 입력을 조장하는 방식이다.

 

opposite angle-based

• 로봇이나 이동체의 제어에서, 어떤 기준으로부터 발생하는 각도 오차의 반대 방향을 이용해서 제어 입력을 산출하는 방법을 의미
• 즉, 로봇이; 특정 방향으로 부터 벗어났을때 그 반대 방향의 정보를 활용해서 자동으로 보정하는 방법이다.

 

 

0. abstact

• 지난 30년간, robot vehicles 분야에서 많은 흥미로우면서 빠르게 진보하였다. 로봇 청소기나 인사로봇 같은 다양한 타입의 로봇들은 우리 삶의 엽에서 자주 접할수있다. 
  • 해당 로봇들의 핵심 부분중 하나는 path planning이다. 이는 시작점에서 도착지점까지 빠르고 안전한 경로를 찾는것이다.
• 본 논문은 앞에서 말한 path planning분야에 대해서 연구하고 싶은 학자들의 편의를 위해서, 이와 관련 주제에 대해서 리뷰를 할것이다.
  • 본 논문에서는 robot vehcles의 기술 중 하나인 path planning을 3가지의 카테고리로 나누어 설명하였다. ( 전통적인 접근법 , 지능 기반 접근법 , 그리고 그외의 것들... )
    • 모바일 로봇의 path planning에 대한 메인 주제에 대해서 말한 다음에는 futrue research의 방향에 대해서 논의하였다.

 

1. Introduction

• 과학기술은 모바일 로봇의 개발을 가능하게 하였으며, 현재는 널리 다양하게 사용되고 있다.
  • 모바일로봇은 과학기술의 발전으로 인해서 의료,엔터테이먼트,군용,제조 등 다양하면서도 중대한 분야에서 점차 사용되고 있다.
    • 이때 로봇의 path planning의 기술적인 도전과제는 '불확실하고 복잡한 환경'을 어떻게 다루냐이다.
  • 목표는 '어떠한 충돌'없이 효율적이면서 정밀한 경로를 식별하는 것이다.
• 복잡하고 불확실한 환경에서, 뛰어난 성능을 보여주는 path planning의 접근법은 다음과 같다.
  ===> 모바일 로봇에게 맞는 효율적인 경로를 빈번히 발생시킬수 있어야한다.
  • 모바일 로봇들을 위하여 제안되었던 방법들은 그들의 작업 환경과 그에 따른 mission losses를 개선하는데 목표를 두었다.
• 떠오르는 research주제로는, route mapping이 중요한 모듈로 떠오른다. ( 이는 자율주행 분야 내에서 ... )
• 많은 학자들은 로봇의 path planning에 대해서 survey하였다. 하지만, 연구들을 분류하면서 이들은 좀 더 포괄적이면서 더 확장시켰어야 했다. 이와는 대조적으로 본 논문에서는 현존하는 path planning들의 특징들도 분석하였다. 
  우리는 가장 최신의 다양한 path planning 기술들에 대해서 소개하고, 미래 예측을 위해서 가능한 전망도 제시할거다.

 

• 1장인 introduction을 제외하고 남은 부분은 다음과 같이 소개할것이다.
  • 2~4장은 로봇의 route mapping에 대해서 3가지(전통적인 방법 , 지능 기반 , 다른 접근법들)로 나누어서 설명한다.
  • 5장은 모바일 로봇의 몇몇 제안과 나아갈 방향에 대해서 제시하고자 한다.

 

 

2. Classical Approaches

• 전통적인 접근법은 오랫동안 연구되었다.
• 이 방법의 특징은 간단한 구조이면서 구현이 쉽다. 하지만 만들어진 장애물이 존재하는 환경이 필요하며, 하나의 명백한 한계점은 다양한 환경에 적용하는것이 어렵다는 것이다.
  • 그래도 전통적인 접근법은 능동적으로 솔루션에 다가갈수있다.
  • 전통적은 방법에는 위에 그림에서 볼수 있둣이 CD ,  APF , PRM , RRT , DP , SA , bug approach등이 존재한다.

2-1. CD Approach

• CD 접근법은 workspace를 작은 부분으로 분할한다. 이러한 segments은 무방향 connect graph의 정점이 된다.
• 장애물이 존재하는 grid기반의 환경에서는 로봇은 오직 unmarked된 셀로만 이동이 가능하며 장애물을 피하면서 안전하고 효율적으로 가야한다.
  • Lindemann은 3가지의 혁신적인 접근법을 제안하였는데, 이는 CD를 사용하는 자율주행 로봇을 위한 segmented linear path를 만들어 내였다. 그리고 3가지의 standard optimization problems을 다항식 시간안에 해결하였으며, 제안된 방법들이 다른 방법들보다 효과적임을 입증했다.
  • open-loop path의 건고하지 않은 취약점으로 인해서 Lavelle와 Lindemann은 새로운 closed-loop feedback law를 제안하였다. ( 이는 system이 상태 공간 안에 존재하는 어떠한 지점이는 도달이 가능하게 하였다. )
  • Jung은 곡선 장애물에서의 route mapping문제를 해결하기 위해서, opposite angle-based exact cell decomposiotion과 douglas-peucker appproximation을 조합하였다. Expanded Douglas–Peucker Polygonal Approximation and Opposite Angle-Based Exact Cell Decomposition for Path Planning with Curvilinear Obstacles
  • 같은 때에 Liu는 complete coverage 알고리즘 기반으로 Boustrophedon CD방법으로 성능 향상을 입증했다. 

 

2-2. PRM Approach

• 출발지에서 목적지까지 곧바로 가는 경로를 정할때에는, PRM이 많이 사용된다. 선택된 경로는 자유공간에서 확률적으로 랜덤한 points만들어낸다. ( 이때는 수학적기법 사용 )
• collision-check줄여서 성능 향상을 시키기 위해서 lazy-prm구조가 제안되었다.
• path planning에서 좁은 복도와 공간 config는 어려운 도전과제이다.
  • Chai[14]는 particle swarm optimization과 RPM을 조합하여 새로운 방법을 제안하였다. 이러한 제안된 접근법은 route mapping이 좁은 복도와 샘플링 위치 활용에서의 성공 가능성을 높혀주었다.

 

2-3. AFP Approach

• 해당되는 방법은 potential field기반의 방법이다. 이는 인공적인 중력장으로 안전하고 매끄러운 경로를 만들어낸다.
• 자율주행 차량을 위한 route mapping에서는 운전자의 운전 스타일을 고려하여 지역 경로 mapping알고리즘이 도입되었다.
• 다중 로봇 환경에서는 지역 경로 계획 모델이 변형된 APF기법을 사용하였다. 이를 통해서 로봇들은 환경을 효율적이고 안전하게 탐색하면서 편대를 유지하고 장애물과 다른 로봇과의 충돌을 피할수있게 되었다.
• 최근에는 강화학습과 접목된 Q-APF알고리즘이 제안되었다.

 

2-4. a star Approach

• a*알고리즘에 대해서 알아보기전에, 다익스트에 대해서 먼저 알아보자. 다익스트라는 출발점에서 목적지까지 지속적으로 확장해 나아가는 것이 가능한 알고리즘이다. 이때 목적지로 뻗어 나아갈때, 출발점에서 가장 가까운 노드를 선택하면서 나아간다. 이러한 방법이 업그레이드 된 것이 A*알고리즘이다.
• A*는 휴리스틱 기반의 path planning기법이다. ( 이는 확실한 평가 지표(경로에 대한)를 이용하여 구현한다. )
• Yoon은 'grid map'과 '2개의 실시간 휴리스틱'을 조합하여 효율적으로 반복하여 접근하는 방법을 제안하였다.
  • ( 여기서 사용한 2개의 휴리스틱 함수는 '운동학과 크기를 고려한 함수' 와 '자율주행의 collsion-free constrains'이다. )
• Zhong[22]은 모바일 로봇이 운영되는 환경은 계속해서 바뀐다고 하였다. 그래서 새로운 hybrid 방법을 제안했는데 이는 a*와 adaptive window approach를 결합한 방식이다
• a*는 안전하면서도 계산 비용이 효율적이다.

 

2-5. RRT Approach

• RRT는 샘플링 기반이며, 이는 단계마다 랜덤한 point를 발생시키면서 점점 목표 지점에 가까워지는 방식을 취한다.
• Zhang[24]은 동적인 환경에서 충돌이 없는 경로를 얻기 위해서, RRT접근법으로 predictive route mapping을 제안하였다.
  • 이 알고리즘은 자유 주행하는 로봇의 속도와 동적인 장애물에 따라서 basic motion을 예측한다.
• 같은 때에 Qi는 multi-objective dynamic RRT알고리즘을 제안하였다.
  • 수정된 RRT알고리즘은 initail path를 얻는데 사용되었다. 게다가 state tree structure를 생성하였다.

 

 

2-6. DP Approach

• DP의 메인 아이디어는 큰 문제를 작은 문제들로 나누어서 가장 빠른 경로를 찾아내는 것이다.
  • 가장 중요한 단계에서는 node에 넘버링하기와 최적의 솔루션을 찾는것을 포함한다.
  • 이 방법의 장점은 능동적으로 계산하는 것이 가능하다.  
  • path planning단계에서는, DP를 통하여 여러 장벽이나 장애물들의 위치를 알수있다. 이로 인해서 안전하고 유동적인 경로를 선택하는 것이 가능하다.
    하지만, 이 방법은 최적의 값에 가까워질수 있으나 차원수가 높아지면 digit curve가 나타날것이다.
• 결과적으로 Hu는 rote mapping방법을 제안하였다. 해당 방법은 MPADP 방법을 사용한다. 이 방법은 control policy와 cost function approxunatuin을 조합하여 사용된다.

 

 

2-7. SA approach

• SA알고리즘은 greedy 알고리즘의 일부이다. ( 이는 local optimal을 피할수있음 )
• SA의 핵심 아이디어는 현재보다 더 나쁜 랜덤한 값을 얻을때, 알고리즘은 즉시 버리는 것이 아니라, 확률적으로 받아드린다.
• 성공적으로 plan인 유전자 알고리즘을 사용하는 방법이다.
• global optimum문제는 존재하는 local search와 SA 처리과정을 대신 사용하여 해경하였다.
• 모두가 잘 알겠지만, 로봇에게는 신속하고 정확한 경로를 발견하는 것이 이상적이다.
• Zhang과 Lu는 SA-PSO알고리즘을 제안하였다. 이는 PSO알고리즘을 사용하는 SA와 파라미터를 조절하여 돌연변이 particles을 만들어내는 2가지의 조합이다.

 

 

 

2-8. Bug Approach 

• bug방법에서는, 로봇은 출발점에서 목적지까지 선을 따라서 걷는다. 하지만 만약에 장애물을 발견한다면, 로봇은 장애물의 주변을 따라 이동하면서, 목표지점과 가장 가까운 장애물 위의 한 점을 판단한다. 
• 가장 가까운 지점에서 출발하며, 로봇은 반복적으로 목표에 도달해 나아간다.  
• 알려진 환경과 안할려진 환경에서 나아갈 궤적을 결정하기 위해서, Nguyen은 improved K-Bug method를 제안하였다. 이는 가장자리를 도는 fuzzy logic이 적용된 방법이다.
• 장애물을 피하는 문제를 목표로 해서, Kong은 no-target bug method를 개발하였는데, 이는 mobile robot이 목표를 향해서 이동하게 해준다. ( 장애물을 피하면서 )
  • 같은 때에, bug-like method improved with fuzzy criteria라는 정적인 장애물인 경우에서 사용할수 있는 방법이 제안되었다.

 

2-9. 정리

• 지금까지 2-1부터하여 2-8까지를 보면 전통적인 방법은 구현하기가 쉬워 보이며, 구조도 간단해보인다.
  하지만 전통적인 방법에는 아래와 같은 문제가 존재한다.
  • 1. 대부분의 전통적인 알고리즘은 더 나은 path를 만들어 내기 위해서 환경 정보와 모델 환경을 알아야한다.
  • 2. 실행이 가능한 경로를 얻는다고 해도, 아마 효율적이지 않을 것이며, multi-objective제약을 확립하기 어렵다.
  • 3. 실시간 배포에는 환경에 대해서 예측할 수가 없어서 실현하기가 어렵다.
  • ==> 로봇이 더욱 복잡한 환경에서 작동하기에는, 전통적인 방법에는 제한이 있다.
• 미래에는, 지능기반의 multi-robot의 협동이 hot research topic이 될것이다. 챕터 3에서는 이러한 방법에 대해서 알아본다.

 

3. Intelligent Approaches

• 과학 기술의 발전으로, 지능기반 접근법도 mobile-robot에서 흔히 볼 수 있게 되었다.
• 전통적인 접근법과 비교하였을때,  이 방법은 잘 알려지지 않고 동적인 환경에서 더 나은 성능을 보여준다.
  • 더 구체적으로는, 지능기반의 방법은 다양한 제약조건 아래에서 best path를 찾을수있다.
• 최근에 지능 기반 접근법은 fuzzy logic , neural network , genetic algorithm , particle swarm optimization , colony optimization , bacterial foraging optimization과 같은 방법이 robot navigation에 널리 사용된다.

 

3-1. Fuzzy Logic Algorithm

• fuzzy logic control은 컴퓨터 분야에서 'fuzzy set theory'와 'fuzzy logic reasoning'을 사용하는 기술이다.
• 1965년에 fuzzy set은 Zadeh에 의해서 제안되었으며, mobile robot의 path planning에 널리 사용되고 있다.
• 잘 모르는 환경에 대해서 로봇이 안전하게 이동할 수 있게 하기 위해서, Abiyev[35]은 거리와 장애물과의 거리 각을 이용하여, 이를 중요한 파라미터로 사용하였으며, 이는 fuzzy 지식 기반의 robot navigation을  개발하였다.
• 같은 때에 Chang[36]은 충돌 없이 group of robot을 navigating하는 fuzzy logic controllers를 제안하였다. 

 

3-2. Neual Network Algorithm

• 인공 신경방은 1940년대에 나타났다. 이는 각각의 많은 수의 뉴런은 연결마다 가중치를 다르게 가지고 있다.
  • 이는 3차원에서의 robot route mapping을 해결하였다. DNN을 사용한 샘플링 기반의 route planning frame-work는 Wang에 의해서 제안되었다.
    • 이는 3D path planning의 몇몇 예시를 가지고 훈련 시켰으며, 이는 앞으로의 지역에서 path가 가능한지 아닌지 예측할 수 있게 해주었다.
  • 카메라의 마스킹에 대한 속도를 증가 시키기 위해서 Shirbandi는 CNN을 사용하여 장애물을 피하게 하였다. ( 이는 monocular camera를 사용함. ) 

 

3-3. Genetic Algorithm

• 유전자 알고리즘은 최근들어서 집중 받고 있다. 고전적인 방법과 최적화 방법과 비교 하였을때, 유전자 알고리즘은 principles of organic selection을 사용하는 강력한 방법이다. 
  이는 각각의 가능한 해들은 gene형태로 되어 있으며, 각각의 객체군들은 반복적으로 selection,crossover,mutation이 가능하다. 
• vehicle-like robots과 같은 비선형 vehicles에 한하여, Vieira[42]는 궤적 planning기술을 제안하였다.
  • multi-locomotion robot은 다양한 형태에 대해서 적응할 수 있는 것이 도전과제이다.
• path planning에서 4가지의 최적화 목표는 'power consumption' , 'time consumption' , 'path length' , 'smoothness'이다.
  • Suresh[44]는 multi-objective genetic 알고리즘으로 위에서 말한 path planning의 문제점을 해결하였다.
• 최적의 길을 찾기 위헤서는 5가지의 기준이 받아들여진다. 'incorporation security' , 'range' , 'smothness' ,'length of travel' , 'path devoid of collisions'

 

3-4. Swarm Intelligent and Bionic Approaches

• 해당 때지능 방법은 주로 새,벌레,박테리아 같은 곳에서 영감받은 방법이다. 이는 생명체들이 음식을 찾기 위해서 협동적으로 행동한다. 각각의 그룹의 인원은 경로를 탐색할때 자신이나 그룹의 다른 인원의 경험을 사용한다. 그러므로, 음식을 좀 더 효율적인 방법으로 찾는게 가능하다. 이 방법은 집단 행동을 가진 동물들의 집관을 모방한 것 이며, 때지능이나 생물적 방법이라고도 부른다.

 

3-5. Particle Swarm Optimization

• PSO는 때지능의 종류중 하나이며, 새가 먹이를 찾는 방법에서 발견하였다.
• 이 알고리즘은, 새들은 하나의 particle이며, 이들은 쉽게 서로 정보를 교환할 수 있다.
  • 모든 particle은 좋은 정보는 유지한다.
• PSO기반의 trajectory planner는 full coverage optimum route를 많은 aerail vechicles들에게 분산시켜준다.

 

3-6. Ant colony Optimization

3-7. Bacterial Foraging Optimization

 

4. Other Approaches

• 위에서 소개한 방법 이외에도, 우리의 요구사항에 맞는 방법들이 존재한다. 
  연구자들은 다른 분야의 기술과 결합해서 path planning에 대해서 더 나은 성능을 보여준 방법들이 존재한다.
• Fareh[55]는 실행 가능한 path를 결정하는 계산 속도를 줄이기 위해서 vision기반의 path planning 기술을 제안했다.
  • 제안되었던 기술은, 새로운 접근법이였으며, 잘알려진 a*,CD,PRM과 같이 사용하여 속도를 향상시켰다.
• Xing은 robot route planner를 제안하였는데, 이는 seeker optimization 알고리즘과 advantage actor-critic 알고리즘을 결합한 방법이다.
  • 이 접근 법은 global, local route planner를 통합것이며 강화학습 기반의 path planning이다.