2022.10.7.(금) 공부 내용

# 정리해야하는 알고리즘

A*
Pure Pursuit
VFH(Vector Field Histogram)
Potential Field (참고 : https://pasus.tistory.com/78?category=1179984)
Visibility Graph
Voronoi Diagram
PRM(Probabilistic Roadmap Method)
RRT(Rapidly-exploring Random Tree)

 

[Book] Introduction to Autonomous Robots

4.3.2. Connecting Points to the Tree

고전적으로 새로운 포인트는 이미 트리 안에 존재하는 포인트 또는 목표점으로 연결되는데 이것은 트리 안에 존재하는 모든 점으로의 거리를 계산해야 가능하다. 그러나 이것은 가장 짧은 경로를 만들어내지는 못한다.

이것에 대해 최근에 향상된 방법으로 제시된 것이 RRT*이다. 이것은 고정된 반지름에서 d-ball(2D 지도에서, d = 2, 즉 원) 안에 있는 트리의 모든 점을 고려하여 시작까지의 전체 경로 길이를 최소화하는 점을 찾아 포인트를 연결한다. 

트리에 포인트를 추가할 때에는 자동차와 같은 로봇의 특정 운동학 부분을 고려하기에 좋다. 여기서, local planner는 트리의 각 지점에서 차량의 방향을 고려하는 적절한 궤적을 생성하는 데 사용될 수 있다.

 

4.3.3. Collision Checking

- point-in-polygon 알고리즘

2차원 좌표 내에 다각형이 존재할 때 특정 좌표가 다각형 내부에 있는지 외부에 있는지 판별해주는 알고리즘.

(즉, "다각형 내부 외부 판별 알고리즘"이다.)

 * 다각형 내부에 좌표가 존재하는지 확인하는 방법

  해당 점의 왼쪽으로 반직선을 그었을 때 (혹은 오른쪽으로 반직선을 그었을 때) 다각형과 마주치는 부분이 홀수 개이면 다각형 내부에 존재하는 것이고, 짝수 개이면 다각형 외부에 존재하는 것이다.

 

Q. 그런데 위 두 번째 사진에서 저게 마주친 것이 아닌가..????ㅠㅠ

 

- self-collision

: 로봇에 외부의 장애물로 인해 충돌이 발생하는 것이 아니라, 휴머노이드 로봇을 예로 들면, 로봇의 내부에 해당하는 각 모듈끼리 충돌이 발생하는 것.

 

- lazy collision evaluation

Collision checking은 Path Planning 문제에서 실행 시간의 최대 90%를 차지한다. 이때 계산 속도를 높이는 성공적인 방법이 바로 "lazy collision evalution"이다. 충돌 가능성이 있는 모든 포인트를 확인하는 대신, lazy collision evaluation 알고리즘은 먼저 적절한 경로를 찾는다. 그런 다음 이 경로의 모든 부분에서 충돌이 있는지 확인한다. 일부 부분에서 충돌하는 경우, 이러한 부분은 삭제되고 알고리즘은 계속 진행되지만 충돌이 없는 성공적인 경로의 부분은 유지된다.

 

참고 자료 :  [Lazy Collision Checking in Asymptotically-Optimal Motion Planning - Kris Hauser]

 

 

 

# 따로 공부한 부분 #

SLAM과 Path - Planning의 연관성을 정확히 파악해보고자..

 

ROS Navigation에서 중요한 부분은 map을 생성한 다음에 로봇의 위치를 파악하는 Localization을 해준 다음에 Path Planning을 통하여 원하는 위치를 가는 것이다. 이때 추가적으로 Transforms가 중요한데, 이것은 로봇 어디에 laser가 부착되어있는지를 의미한다. 

 

 

경로 탐색에는 Global planner 설정과 local planner 설정이 있다.

 

- Global planner 설정

ROS에서 제공되어지는 Global planner 알고리즘에는 *Navfn(Dijkstra's algorithm) , Carrot Planner가 있다.

 

- local planner 설정

local planner는 Odometry와 laser data를 계속하여 계산하고 있으면, 경로를 가는 도중에 장애물을 마주하는 경우 재계산을 통하여 경로를 다시 설정하는 것을 의미한다. 

local planner의 기본적인 알고리즘 개요는 여러 개의 경로를 만든 후 각각의 경로에 점수를 매겨, 가장 높은 점수를 가진 경로를 선택하는 것이다.

local planner 종류에는 *dwa_local_planner(제일 많이 사용), teb_local_planner(Timed Elastic Band Method), eband_local_planner(Elastic Band Method)가 있습니다.

 

따라서 간단히 설명하면 Global plan 설정은 전체적인 경로를 설정하고 길 중간중간 상황에 맞게 경로를 수정하는 것은 local planner 설정에서 담당하는 것이다. (ROS에서는 Rviz를 통하여 path에서 global planner와 local planner의 색깔을 변경하면 그 차이를 확인해볼 수 있다.)

 

- cost map

값이 있는 지도를 의미. (각 값 또는 점수를 통해 장애물의 유무를 알 수 있다.)

global cost map : 현재 감지하지 않지만 이전에 감지했던 것들을 바탕으로 만들어진 지도

local cost map : 현재 센서에서 감지되고 있는 지도

 

 

 

# 참고 자료

[Introduction to autonomous robots - Nikolaus Correll]

https://m.blog.naver.com/skwd123/221823918346

ROS Navigation in 5 Days

 

http://www.jeffreythompson.org/collision-detection/poly-point.php