2022.10.18.(화) 공부 내용

RoadMap (RM)

RoadMap은 Q_free (free configuration space)의 모든 시작점과 목표점에 대해 경로로 연결할 수 있는 모든 곡선의 조합이다.

RoadMap Property

(q_start ∈ Q_free, q_goal ∈ Q_free, q' ∈ RM, q'' ∈ RM)

• Accessibility : q_start에서 q'까지의 경로
• Departability : q''에서 q_goal까지의 경로
• Connectivity : RoadMap에서의 q'와 q'' 사이의 경로
• One dimensional

RoadMap Path Planning

1. roadmap을 만든다.
   a) free configuration space (Q_free)에 있는 점들이 node가 된다.
   b) 두 노드에 대해 그들 사이에 free space가 존재하면 두 노드를 edge로 이어준다.
2. 출발점과 목표점을 roadmap의 q' 및 q''에 각각 연결한다.
3. roadmap에서의 q' 와 q'' 사이에 경로를 찾아 연결한다.
   결과값은 free confituration space (Q_free)의 시작점에서부터 목표점까지의 경로가 된다.

 

Voronoi Diagram

• Roadmap
• 고차원의 문제는 해결할 수 없다.

[출처 : https://www.cs.cmu.edu/~motionplanning/lecture/Chap5-RoadMap-Methods_howie.pdf]

 

Basic definition

• Single-object distance function
• Multi-object

 

Generalized Voronoi Diagram (GVD)

• 일반화된 보로노이 다이어그램
• GVD는 자유 공간의 1차원 부분 집합으로서, 가장 가까운 두 장애물에서의 거리가 동일한 (이중 등거리의) 점들의 집합이다.
• GVD를 이용한 Roadmap은 작업 공간에서 장애물과의 거리를 최대화하며, 지역적 거리 정보만을 이용해서 지도를 구성하므로 미지의 환경에서 시작하여 센서 기반 점진적 지도 구성을 수행한다.
• 변형 수축(Deformation Retract)이다.

로봇의 GVD 추종

일반적으로 GVD 상에는 시작점과 목표점이 존재하지 않는다. 따라서 경로 계획(Path Planning)은 시작점에서 GVD로 접근하는 알고리즘과 GVD를 벗어나 목표점으로 도달하는 알고리즘이 더해짐으로써 달성된다.
(즉, 일단 GVD가 구성되어야 로봇은 GVD를 사용하여 자유 공간(free space)의 경로를 계획할 수 있다.
여기서 자유공간(free space)이란 장애물이 차지하지 않은 공간을 뜻한다. 따라서 로봇은 자유 공간에서 움직이게 된다.)

 

 

 

#참고 자료

[논문][일반화된 보로노이 다이어그램을 이용한 논홀로노믹 모바일 로봇의 자율 주행 - 소명뢰, 신동익, 신규식 저자] 

 

https://slideplayer.com/slide/4463948/

The Voronoi Diagram David Johnson. Voronoi Diagram Creates a roadmap that maximizes clearance –Can be difficult to compute –

https://javalab.org/voronoi_diagram_drawing/

보로노이 다이어그램 그리는 법 - 자바실험실

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=san2sul&logNo=221073365254 

보로노이 다이어그램 만들기(학생자료)