방법론
이 절에서는 계획기에서 로봇의 움직임, 환경, 공분산 제약을 어떻게 모델링하는지 설명합니다. 또한 A*의 이산화된 노드에 대해 연속시간 종속 시스템으로 EKF를 구현하는 방법을 다룹니다.
불확실성 측정 지표
위치추정 불확실성을 정량화할 때는 EKF 공분산에서 도출한 스칼라 지표를 사용할 수 있습니다. 여기서는 위치 공분산의 대각합을 사용합니다.
공분산 행렬은 대칭이며 양의 준정부호이므로 대각합을 사용합니다. 따라서 모든 대각 원소가 음이 아닌 값을 가지며, 그 결과 양의 스칼라 값을 얻습니다.
불확실성 제약은 다음과 같습니다.
위치 공분산의 대각합은 사용자가 지정한 임계값 미만이어야 합니다.
이 제약을 위반하는 두 노드 사이의 모든 궤적 구간은 실행 불가능한 것으로 간주합니다.
불확실성을 고려한 간선 평가
알고리즘 1을 사용해 구간을 생성한 뒤, 알고리즘 2에 요약된 불확실성 검사 함수를 사용해 각 후보 경로 구간을 평가합니다. 로봇의 움직임과 EKF 전파를 동시에 시뮬레이션하고, 실행 전반에 걸쳐 불확실성 지표를 모니터링합니다. 제약을 충족하지 못하는 노드는 제외됩니다.
이론적 분석
이 절에서는 제안하는 불확실성 제약 A* 계획기의 최적성에 관한 이론적 보장을 제시합니다. 이 문제는 간선의 유효성을 EKF 공분산 한계로 엄격하게 결정하는 그래프 탐색 문제로 정식화됩니다.
그래프 정식화
간선 비용은 당근 추종 제어기가 생성하는 궤적의 호 길이입니다.
실험 및 결과
이 절에서는 GPS 신호가 차단된 환경에서 제안된 불확실성 제약 계획기를 평가한 시뮬레이션 결과를 제시합니다. 실험을 통해 위치추정 불확실성에 상한을 적용하는 것이 다양한 계획기의 경로 실행 가능성, 추정 정확도, 경로 품질에 어떤 영향을 미치는지 살펴봅니다.
랜드마크 밀도의 영향
장애물 밀도와 불확실성 임계값을 고정하고 랜드마크 비율을 변경해 랜드마크 밀도의 영향을 평가합니다. 각 조건에서 모든 계획기의 성공한 실행을 대상으로 성공률, 경로 길이, 계산 시간을 평균값으로 보고합니다. 장애물 밀도와 불확실성 임계값의 영향을 평가할 때도 같은 절차를 사용합니다.
경로 길이 측면에서 A는 모든 랜드마크 밀도에서 일관되게 가장 짧은 경로를 생성합니다. 경로 길이는 유클리드 하한에 가깝게 유지되며, 이는 허용 가능한 휴리스틱이 보장하는 최적성을 반영합니다. PRM과 RRT는 무작위 탐색과 최적이 아닌 로드맵 연결성 때문에 눈에 띄게 더 긴 경로를 생성합니다. 랜드마크 밀도가 증가하면 모든 계획기에서 경로 길이의 변동성이 감소하지만, 이동 거리 면에서는 A*가 여전히 가장 효율적입니다.
전반적으로 A의 계산 시간이 가장 짧고, 그다음은 PRM, RRT 순입니다. 랜드마크 밀도가 증가하면 모든 계획기에서 계산 시간이 늘어납니다.
장애물 밀도의 영향
모든 장애물 밀도에서 A는 일관되게 가장 짧은 경로를 생성하며, 복잡한 환경에서도 최적성 보장이 유효함을 보여줍니다. PRM과 RRT는 무작위 샘플링으로 인한 우회와 제한적인 국소 연결성 때문에 더 긴 경로를 생성합니다. 장애물 밀도가 증가하면 모든 계획기에서 경로 길이가 약간 늘어나지만, 상대적인 순서는 달라지지 않습니다.
모든 장애물 밀도에서 A의 계산 시간이 가장 짧고, 그다음은 PRM, RRT 순입니다. 이는 샘플링 기반 계획기가 복잡한 환경에서 더 많은 노드를 확장해야 하기 때문입니다.
불확실성 임계값의 영향
랜드마크 밀도를 10%, 장애물 밀도를 5%로 고정하고 불확실성 임계값을 평가합니다.
결론
이 논문은 추측 항법으로 위치추정 불확실성이 커지는 GPS 신호 차단 환경에서의 경로 계획을 제시합니다. 불확실성 제약 A*는 최적성 보장을 유지하며 불확실성 제약을 만족하는 모든 실행 가능 궤적 가운데 최단 경로를 찾고, 전반적으로 짧은 계산 시간도 보입니다.
실험 결과, 기하학적으로 최적인 경로가 불확실성 제약 아래에서는 유효하지 않은 경우가 많지만, 이 방법은 랜드마크가 밀집한 구역을 통과하는 실행 가능한 우회 경로를 성공적으로 찾아냅니다. 그러나 이 접근법은 환경과 랜드마크 위치를 알고 있다고 가정하며, 실제 GPS 신호 차단 상황에서는 이러한 가정이 항상 성립하지 않을 수 있습니다. 향후 연구에서는 이러한 가정을 완화하고, 동적 장애물을 처리하며, 불확실성이 있는 다중 로봇 내비게이션을 위한 에이전트 간 신념 필터를 탐구할 예정입니다.
자주 묻는 질문
계획기는 위치추정 불확실성을 어떻게 측정하나요? EKF에서 도출한 위치 공분산의 대각합을 사용합니다.
궤적 구간은 언제 실행 불가능한 것으로 간주되나요? 두 노드 사이에서 사용자가 지정한 불확실성 임계값을 위반하면 해당 구간은 실행 불가능합니다.
간선 비용은 어떻게 정의하나요? 당근 추종 제어기가 생성하는 궤적의 호 길이입니다.
이 접근법은 어떤 가정을 두나요? 환경과 랜드마크 위치를 알고 있다고 가정합니다.