모션 계획

저차원 문제는 구성 공간 위에 그리드를 오버레이하는 그리드 기반 알고리즘이나 씨프리의 모양과 연결을 계산하는 기하학적 알고리즘으로 해결할 수 있습니다.

복잡한 제약 조건 하에서 고차원 시스템에 대한 정확한 모션 계획은 계산하기가 어렵습니다. 전위 필드 알고리즘은 효율적이지만 로컬 최소값(예외는 고조파 전위 필드)에 해당합니다. 샘플링 기반 알고리즘은 로컬 최소값의 문제를 피하고 많은 문제를 매우 신속하게 해결합니다.경로가 없다는 것을 확인할 수는 없지만 더 많은 시간을 소비하면 실패 확률이 0 으로 감소합니다.

샘플링 기반 알고리즘은 현재 고차원 공간에서의 모션 계획을위한 최첨단 것으로 간주되며 수십 또는 수백 개의 차원(로봇 조작기,생물학적 분자,애니메이션 디지털 캐릭터 및 다리가있는 로봇)이있는 문제에 적용되어 왔습니다.

모션 계획 병렬 알고리즘(에이 1-에이 2)객체 조작(비행 물체를 잡기 위해).

그리드 기반 검색편집

그리드 기반 접근 방식은 구성 공간에 그리드를 오버레이하고 각 구성이 그리드 포인트로 식별된다고 가정합니다. 각 그리드 포인트에서 로봇은 인접한 그리드 포인트로 이동할 수 있습니다. 이 작업은 일련의 작업을 이산화하고 검색 알고리즘(예:*)은 처음부터 목표까지의 경로를 찾는 데 사용됩니다.

이러한 접근 방식은 그리드 해상도를 설정해야합니다. 그러나 이 알고리즘은 좁은 부분의 경로를 찾지 못할 것입니다. 또한 그리드의 포인트 수는 구성 공간 차원에서 기하 급수적으로 증가하여 고차원 문제에 적합하지 않습니다.

전통적인 그리드 기반 접근 방식은 제목 변경 사항이 주어진 기본 각도의 배수로 제한되는 경로를 생성하여 종종 차선책 경로를 만듭니다. 모든 각도 경로 계획 접근 방식은 경로를 그리드 가장자리로 제한하지 않고(짧은 경로를 찾기 위해)그리드 가장자리를 따라 정보를 전파하여(빠른 검색을 위해)짧은 경로를 찾습니다.

그리드 기반 접근 방식은 예를 들어,구성 공간에 대한 로봇의 지식이 변경되거나 구성 공간 자체가 경로를 따르는 동안 변경 될 때 반복적으로 검색해야합니다. 증분 휴리스틱 검색 알고리즘은 이전의 유사한 경로 계획 문제에 대한 경험을 사용하여 현재 검색 속도를 높여 빠르게 다시 계획합니다.

간격 기반 검색편집

이러한 접근 방식은 그리드 대신 구성 공간을 완전히 덮는 포장을 생성한다는 점을 제외하고는 그리드 기반 검색 방식과 유사합니다. 포장이 분해 두 가지로 subpavings X,X+으로 만든 상자는 X−⊂Cfree⊂X+. 설정 반전 문제를 해결하기 위해 씨 프리 금액을 특성화합니다. 따라서 간격 분석은 보장 된 인클로저를 갖기 위해 선형 부등식으로 설명 할 수없는 경우에 사용될 수 있습니다.

따라서 로봇은 엑스−에서 자유롭게 움직일 수 있고,엑스+밖으로 나갈 수 없다. 두 서브 페이브 모두에 이웃 그래프가 작성되고 경로는 다음과 같은 알고리즘을 사용하여 찾을 수 있습니다. 이 경우,그것은 또한 실행 가능하다. 하나의 초기 구성에서 목표까지의 경로가 엑스+에 존재하지 않을 때,우리는 씨 프리에 실현 가능한 경로가 존재하지 않는다는 것을 보증합니다. 그리드 기반 접근법에 관해서는,인터벌 접근 방식은 생성 될 박스의 수가 구성 공간의 차원에 대해 기하 급수적으로 증가한다는 사실로 인해 고차원 문제에 부적합하다.

오른쪽의 세 그림에 의해 2 개의 자유도를 가진 후크가 두 개의 수평 작은 세그먼트를 피하면서 왼쪽에서 오른쪽으로 이동해야하는 그림이 제공됩니다.

구간분석을 이용한 서브파이 빙을 이용한 분해는 또한 연결된 컴포넌트의 수를 세는 것과 같이 씨프리 토폴로지를 특성화하는 것을 가능하게 한다.

기하학적 알고리즘 편집

다각형 장애물 사이의 포인트 로봇

• 가시성 그래프
• 셀 분해

장애물 사이의 객체 번역

• 민코프스키 합계

건물 밖으로 나가는 길 찾기

• 가장 먼 광선 추적

현재 위치 주변의 광선 묶음이 벽에 부딪혔을 때,로봇은 문이 식별되지 않는 한 가장 긴 광선 방향으로 이동한다. 이러한 알고리즘은 건물의 비상 출구를 모델링하는 데 사용되었습니다.인공 잠재 필드 편집

한 가지 방법은 로봇의 구성을 목표에 대한 매력과 장애물로부터의 반발을 결합한 잠재적 인 분야의 지점으로 취급하는 것입니다. 결과 궤적은 경로로 출력됩니다. 이 접근 방식은 궤도가 거의 계산하지 않고 생성된다는 점에서 장점이 있습니다. 그러나 잠재적 필드의 로컬 최소값에 갇혀 경로를 찾지 못하거나 최적이 아닌 경로를 찾을 수 있습니다. 인공 전위 필드는 정전기 전위 필드(로봇을 점 전하와 같이 처리)와 유사한 연속체 방정식으로 처리 할 수 있으며 필드를 통한 움직임은 일련의 언어 규칙을 사용하여 이산 될 수 있습니다.항법 함수 또는 확률적 항법 함수는 목표 지점을 제외한 최소 지점을 갖지 않는 품질을 갖는 일종의 인공 전위 함수이다.

샘플링 기반 알고리즘 편집

샘플링 기반 알고리즘은 샘플링된 구성의 로드맵으로 구성 공간을 나타냅니다.기본 알고리즘 샘플 엔 구성 에 씨,및 유지 씨 프리 중대 사건으로 사용할 수 있습니다. 그런 다음 두 개의 이정표를 연결하는 로드맵이 구성됩니다. 다시 말하지만,충돌 감지는 씨 프리에 포함을 테스트하는 데 사용됩니다. 연결 경로를 찾기 위해 에스 과 지,로드맵에 추가됩니다. 로드맵의 경로가 에스 과 지,플래너가 성공하고 해당 경로를 반환합니다. 그렇지 않은 경우 그 이유는 결정적이지 않습니다.

이러한 알고리즘은 조합 알고리즘과는 달리 실행 시간이(명시 적으로)기하 급수적으로 차원에 의존하지 않기 때문에 고차원 구성 공간에서 잘 작동합니다. 그들은 확률 적으로 완전하며,더 많은 시간을 소비 할 때 솔루션 접근법 1 을 생성 할 확률을 의미합니다. 그러나 솔루션이 없는지 확인할 수는 없습니다.이 알고리즘이 해법을 찾을 확률은 기하 급수적으로 1 에 가깝다는 것이 입증되었습니다. “좋은”가시성을 가진 고차원 공간 또는”가난한”가시성을 가진 저차원 공간을 가질 수 있습니다. 샘플 기반 방법의 실험적 성공은 가장 일반적으로 보이는 공간이 좋은 가시성을 가지고 있음을 시사합니다.

이 기본 체계에는 많은 변형이 있습니다:

• 일반적으로 모든 쌍이 아닌 주변 마일스톤 쌍 사이의 세그먼트 만 테스트하는 것이 훨씬 빠릅니다.
• 비정규 샘플링 분포는 로드맵의 연결성을 향상시키는 영역에 더 많은 이정표를 배치하려고 시도합니다.
• 준 난수 샘플은 일반적으로 의사 난수 샘플보다 구성 공간을 더 잘 덮는 반면,최근의 일부 연구는 임의성의 근원의 효과가 샘플링 분포의 효과에 비해 미미하다고 주장한다.
• 일부 지역 제안 분포 방향 마르코프 체인 몬테 카를로 랜덤 워크를 수행하여 로컬 샘플링을 사용합니다.
• 그것은 실질적으로 곡선 눈 명소를 허용하여 주어진 문제를 해결하는 데 필요한 이정표의 수를 줄일 수 있습니다(예를 들어,두 이정표 사이의 길을 차단 장애물에 크롤링하여).
• 하나 또는 몇 개의 계획 쿼리 만 필요한 경우 전체 공간의 로드맵을 항상 구성 할 필요는 없습니다. 이 경우 트리 성장 변형은 일반적으로 더 빠릅니다(단일 쿼리 계획). 로드맵은 동일한 공간(다중 쿼리 계획)에서 많은 쿼리를 수행해야하는 경우에도 유용합니다)

• 빠르게 탐색하는 랜덤 트리
• 확률 로드맵