공부공간/Robot Navigation (4) 썸네일형 리스트형 [로봇내비게이션 강의정리] Voronoi Voronoi 개념 맵에 점이 여러개 찍혀있을 때, 그 점에 가장 가까운 영역들은 그 점의 영역이라고 보는 방법이다. 이 때, General Voronoi Diagram은 다음을 말한다. F13은 장애물 1과3 사이의 보로노이 경계선을 의미하고 S13은 그 경계선을 직선으로 무한히 이은 선을 말한다. 이 때, F들의 모든 집합을 GVD라고 한다. Voronoi를 어떻게 path planning에 활용할 것인가 장애물을 한 점으로 근사했을 때, 위 그림에서 점을 장애물이라고 보자. 이 때, 점 주변의 영역은 장애물 주변의 영역이 되는것이고, 다시말해 영역과 영역사이 경계선은 장애물들로 부터 가장 먼 경로가 된다. 따라서 이 경계선을 따라서 로봇을 움직이면 로봇은 가장 안전한 path planning을 할 .. [로봇내비게이션 강의정리] V-graph(Visibility) Roadmap-based method 선들의 연결로 path를 완성하는 알고리즘 Visibility graph, Voronoi Diagram Visibility Graph란? "보이는" 꼭지점(노드)들을 연결하는 graph를 말한다. v-graph를 만드는법 : 안보이는 점은 잇지 말고 보이는 점만 잇는다.(간단) v-graph를 만드는 의사코드는 다음과 같다. QInit, QGoal에서 Q(q)가 의미하는 바 : configuration을 의미하는 약어이다. 2줄에 segment는 노드와 노드를 연결하는 선을 의미. edge또한 선을 의미한다. u,v는 각각 노드를 의미한다. ==> 위 의사코드를 간단히 정리하자면 1. 만약 선분이 장애물의 한 변을 이루는 선분이면 ok, 선분이 장애물과 안 부딫히면 .. [로봇내비게이션 강의정리] Shortest path Algorithm 다익스트라 알고리즘 다익스트라 알고리즘은 각 노드에서 모든 노드로 가는 최단경로를 알 수 있는 알고리즘이다.(계산을 통해서) 1) A노드를 방문하면 A의 이웃노드들 업데이트( O~B, O~C ) 2) 업데이트 후 이웃 노드들까지 가는 비용을 원래 알던 값과 비교하여 priority queue에 push한다. 3) priority queue에서 pop하고, pop된 노드는 src노드에서 해당 노드까지 최단경로가 확정된 것이다. 이 상태에서 다시 1번으로 돌아가 반복한다. 의사코드는 다음과 같다. 목적지가 주어지지 않고 모든 노드에 대해서 비용을 다 계산하는 케이스. 여기서 while문 안에 있는 u는 priority queue에서 pop해서 나온 노드를 말한다. 여기서 if dist[u] = infinit.. [로봇내비게이션 강의정리] Map representation 개념정리 테이블 Metric navigation 맵의 모든 장애물의 좌표를 정확한 좌표로써 나타내고 메모리에 저장하는 방식. Topological navigation 노드와 링크로 맵을 구성. 노드와 링크간의 거리정보, 맵정보를 다 저장한다. 맵의 메모리는 metric 방식에 비해 상당히 줄어든다. Hybrid navigation metric, topological방식의 각각의 장점을 모아서 맵을 표현한 방식이다. node-link로 맵을 표현하다가 필요할 때마다 Metric navigation 방식을 가져와서 사용하는 식. closed-world assumption 맵의 장애물들을 최대한 간단히 나타내서 맵을 구성하는 메모리를 줄이는 방식. 맵을 선으로 표현한다. 맵을 grid기반 맵으로 나타냈을 때,.. 이전 1 다음
