정의
로봇 자신과 다른 모든 물체와 로봇의 위치를 지정할 수 있는 데이터 구조
이점
플래너가 차원 수를 잘 줄일 수 있다.
예시
물체가 있는 위치를 잘 표현하려면 6 Dof가 필요하다. 사용자는 기존 프레임에서 (x, y, z) 좌표로 객체의 위치를 지정할 수 있지만 물체도 앞면, 뒷면, 바닥의 3차원으로 되어 있다. 따라서 앞면이 어디를 향하는지, 기울었는지, 똑바로 서있는지, 엎어져있는지를 나타내려면 추가로 3 자유도가 더 필요하다. (이를 오일러 각, 피치, 요, 롤 로 표현)
경로 플래닝에 해당되는 모바일 지상 로봇에 필요한 자유도는 6보다 작다. (로봇과 모든 물체가 바닥에 있으면 높이 좌표(z)를 제거할 수 있다. 하지만 수중로봇이나 공중에 떠 있는 로봇에 경우 z좌표가 필요하다.)
이와 마찬가지로 오일러 각도 항상 필요하지 않다. 로봇이 하려고 하는 것이 장애물 주변 경로에 대한 계획을 세우는 거라면 로봇이 어느 쪽을 향하고 있던 상관이 없다. 그러나 행성 탐사선이나, 앞에 놓인 언덕의 기울기는 바위가 많은 험난한 지형에서 미션을 수행하는데 매우 중요할 수 있다.
표현 방법
1. 메도우 맵
구동방식
프리 스페이스를 볼록 다각형(컨벡스)로 변환한다. 폴리곤은 로봇이 이동할 안전한 영역을 가리킨다.
컨벡스는 로봇이 둘레에서 시작해 둘레의 다른 점을 향해 직선으로 이동하면 폴리곤 밖으로 나가지 않는다는 중요한 성질을 가진다.
=> 결국 이는 경로 플래닝에서 어떤 폴리곤들을 순서대로 통과하는 게 가장 효율적인지를 결정하는 문제가 된다.
흥미로운 피처의 쌍 사이에 라인 세그먼트가 있다고 생각해서 컨벡스 폴리곤을 구성한다. (ex. 실내 지도에서 모퉁이, 출입구, 물체 경계선 등)
이를 통해 컨백스 폴리곤의 프리 스페이스를 분할하는 라인 세그먼트의 조합을 결정할 수 있다.
단점
- 일부 선분은 다른 폴리곤에 연결돼 있지 않으므로 알고리즘의 범위를 넘어선다.
- 선분들의 길이가 일정하지 않다. -> 폴리곤을 가르 지르는 전체 경로의 길이에 차이가 있을 수 있다.
👨🏫 솔루션 : 다른 폴리곤과 경계를 이루는 각 라인 세그먼트의 중간 지점을 찾는 것이다. 이러한 중간점 각각은 노드가 되고, 중간점 사이에 에지를 그리면 무방향 그래프가 만들어진다. 이를 바탕으로 경로를 지정한다.
2. 보로노이 그래프 (GVG)
메도우 맵과 달리 로봇이 새로운 환경에 진입할 때 GVG가 만들어지며, 위상학적 맵을 만든다.
보로노이 엣지가 모든 점에서 거리가 같은 라인을 생성하는 것이다.
에지는 주요 통행로 역할을 한다. 또한 GVG 곡선 에지는 그래프 이론이나 알고리즘에서 문제가 되지 않는다
이점
로봇이 보로노이 엣지를 따라가면 공간의 중앙을 유지하기 때문에 모델링 된 장애물과 충돌하지 않는다.
=> 메도우 맵처럼 장애물 경계를 확장할 필요가 없다.
3. 규칙적인 그래프 (그리드)
월드 공간에 2D 데카르트 그리드를 그린다.
그리드 요소에 포함한 영역에 물체가 있는 경우, 해당 요소는 점유 중으로 표시된다.
그리드 각 요소의 중심은 노드가 될 수 있고 따라서 그리드를 고도로 연결된 그래프로 변환할 수 있다.
노드 간에 연결선을 대각선으로 그릴 수 있는지 여부에 따라 4 연결형 또는 8 연결형 그리드로 구분한다.
단점
디지털화 바이어스라는 개념이 쓰이는데, 이는 물체가 그리드 요소의 가장 작은 부분에 놓이더라도 해당 요소 전체가 점유 중이라고 표시되는 것이다.
=> 공간 낭비도 심해지고 물체들도 불균형(삐죽삐죽)한 모양을 가지게 된다.
👨🏫 솔루션 : 낭비되는 공간을 줄이고자 실내용 규칙적인 그리드를 4~6인치의 세밀한 그리드로 분할해서 사용하는 경우가 많다.
😢 해상도가 높아지면서 경로 플래닝 알고리즘은 고려해야 할 노드가 엄청나게 많아지고 저장 비용이 높아진다.