위험 민감한 점진적 샘플링을 통한 강력한 확률적 최단 경로 계획

지난 마일 자율 배송 및 공급망 관리와 같은 고위험 산업에서 확률적 최단 경로(SSP) 문제의 보편성 덕분에, 성공적인 작업 완료를 보장하면서 위험한 결과를 완화하는 데 있어 강력한 계획 알고리즘이 필수적입니다. SSP 문제를 해결하기 위한 주류 기회 제약 점진적 샘플링 기술은 지나치게 보수적인 경향이 있으며 일반적으로 바람직하지 않은 꼬리 이벤트의 가능성을 고려하지 않습니다. 우리는 최소 조건부 가치-위험(CVaR)을 가진 경로 세그먼트에 따라 노드를 선택하는 점근적으로 최적화된 급속 탐색 랜덤 트리(RRT*) 계획 알고리즘에서 영감을 받아 위험 인식 대안을 제안합니다. 우리의 동기는 CVaR 위험 척도의 단계적 일관성과 SSP 문제의 최적 부분 구조에 있습니다. 따라서 각 샘플링 반복에서 CVaR에 대한 최적화를 수행하는 것은 샘플 크기의 한계에서 최적 경로로 이어집니다. 우리는 장애물과 확률적 경로 세그먼트 길이가 있는 2차원 그리드 세계에서 수치적 경로 계획 실험을 통해 우리의 접근 방식을 검증합니다. 우리의 시뮬레이션 결과는 트리 성장 과정에 위험을 통합하는 것이 노이즈 매개변수의 변동에 대해 길이가 크게 덜 민감한 경로를 생성하며, 즉 환경 불확실성에 대해 더욱 강력한 경로를 생성함을 보여줍니다. 알고리즘 분석은 기본 RRT* 절차와 유사한 조회 시간 및 메모리 공간 복잡성을 드러내며, 처리 시간이 약간 증가할 뿐입니다. 이 증가는 현저히 낮은 노이즈 민감도와 감소된 플래너 실패율로 상쇄됩니다.