확률론적 로드맵
Probabilistic roadmap확률론적 로드맵[1] 플래너는 로봇의 모션 계획 알고리즘으로 로봇의 출발 구성과 목표 구성 사이의 경로를 결정하는 문제를 해결하면서도 충돌을 피한다.
PRM의 기본 아이디어는 로봇의 구성 공간에서 무작위 샘플을 채취해 여유 공간에 있는지 테스트한 후 로컬 플래너를 사용하여 이러한 구성을 다른 인근 구성에 연결하려고 시도하는 것이다.시작 및 목표 구성이 추가되며, 그래프 검색 알고리즘이 결과 그래프에 적용되어 시작과 목표 구성 사이의 경로를 결정한다.
확률론적 로드맵 설계자는 시공 단계와 질의 단계의 두 단계로 구성된다.건설 단계에서는 환경에서 할 수 있는 동작에 근접한 로드맵(그래프)이 구축된다.첫째, 임의의 구성이 생성된다.그리고 나서, 그것은 일반적으로 가장 가까운 이웃들 또는 미리 정해진 거리보다 작은 모든 이웃들 중 하나인 몇몇 이웃들과 연결된다.Roadmap이 충분히 밀도가 높을 때까지 그래프에 구성과 연결이 추가된다.쿼리 단계에서 시작 및 목표 구성은 그래프에 연결되며, 경로는 Dijkstra의 최단 경로 쿼리에 의해 얻는다.
PRM은 자유공간의 형상에 있어 비교적 약한 특정 조건을 감안할 때 확률적으로 완전하다. 즉, 샘플링된 점의 수가 경계 없이 증가함에 따라 알고리즘이 0에 근접할 경우 경로를 찾지 못할 확률이다.수렴 속도는 여유 공간의 특정 가시성 특성에 따라 달라지며, 가시성은 로컬 플래너에 의해 결정된다.대략, 각 점들이 공간의 큰 부분을 "보기" 할 수 있고, 또한 공간의 각 부분 집합의 큰 부분이 그것의 보완물의 큰 부분을 "보기"할 수 있다면, 설계자는 빠르게 경로를 찾을 것이다.
PRM 방법의 발명은 리디아 E. 카브라키에게 인정된다.[2][3]기본 PRM 방식에는 여러 가지 변형들이 있는데, 상당히 정교하게, 샘플링 전략과 연결 전략을 변화시켜 더 빠른 성능을 달성한다.예: 참조Geraerts & Overmars(2002년).[4]
참조
- ^ Kavraki, L. E.; Svestka, P.; Latombe, J.-C.; Overmars, M. H. (1996), "Probabilistic roadmaps for path planning in high-dimensional configuration spaces", IEEE Transactions on Robotics and Automation, 12 (4): 566–580, doi:10.1109/70.508439, hdl:1874/17328.
- ^ Erbland, Kate (2013-10-14). "Dr. Lydia E. Kavraki: A Woman Making Robots Work". Mental Floss. Retrieved 2019-10-07.
{{cite web}}: CS1 maint : url-status (링크) - ^ "Lydia E. Kavraki named 2017-2018 ACM Athena Lecturer". www.acm.org. Retrieved 2019-10-07.
- ^ Geraerts, R.; Overmars, M. H. (2002), "A comparative study of probabilistic roadmap planners", Proc. Workshop on the Algorithmic Foundations of Robotics (WAFR'02) (PDF), pp. 43–57.
