제어 공학 기초: 경로 계획 — A*, 다익스트라, RRT, RRT*, PRM

Contents — find the section you need

로봇을 출발점에서 목표 지점까지 이동시키는 것은 직선 경로로 이동하는 것과는 거리가 멉니다. 효율적인 경로 계획은 벽, 통로 폭, 로봇의 발자국, 회전 제한, 위치 추정 불확실성, 오래된 지도, 움직이는 사람, 정지 거리 등을 모두 고려해야 합니다. 경로 계획은 어디로 갈지 선택하고, 궤적 생성 및 제어는 동적인 환경 속에서 해당 경로를 어떻게 따라갈지 결정합니다. 안전한 스택은 이러한 책임들을 명확하게 구분하면서도 각자의 한계를 공유합니다.

이 입문서에서는 그리드 다익스트라 알고리즘과 A 알고리즘을 연속 공간 RRT, RRT, PRM 알고리즘과 비교합니다. 또한 장애물 확장, 휴리스틱, 샘플링, 복잡도, SLAM/Nav2 통합, 구현 검증, 독립적인 안전 동작에 대해 설명합니다. 관련 내용은 Visual SLAM Primer, ROS 2 Primer, Sensor Fusion Primer를 참조하십시오.

실질적인 결론

다익스트라 알고리즘은 음수가 아닌 가중 그래프에서 최단 경로를 보장하지만, 목표 경로와 무관한 방향으로 확장하는 경향이 있습니다. A* 알고리즘은 허용 가능한 휴리스틱을 사용하여 최적의 경로를 유지하면서 확장 방향을 결정합니다.
RRT는 고차원 연속 공간에서 실행 가능한 경로를 빠르게 찾는 경향이 있습니다. RRT*는 샘플 수가 증가함에 따라 최적 경로에 근접하지만, 이웃 노드 및 재배선 비용이 추가됩니다. PRM은 충분히 정적인 공간에서 여러 쿼리에 걸쳐 로드맵 구축 비용을 분산합니다.
확장되지 않은 지도에서 최단 경로는 로봇이 반경, 위치 오차 및 정지 거리를 고려했을 때 충돌 경로가 될 수 있습니다.
반환된 경로는 안전성을 보장하지 않습니다. 지도 최신성, 지역 감지, 추적 오차, 동적 장애물, 재계획 지연 시간 및 비상 정지는 각각 개별적으로 고려해야 합니다.

알고리즘 선택 전 자유 공간 정의

상태 공간을 $\mathcal X$ , 장애물 공간을 $\mathcal X_{obs}$ , 자유 공간을 $\mathcal X_{free}=\mathcal X\setminus\mathcal X_{obs}$ 라고 하자. 경로 $\sigma:[0,1]\to\mathcal X_{free}$ 은 $x_s$ 와 $x_g$ 를 연결하며, 장애물은 $\sigma(0)=x_s,\sigma(1)=x_g$ 이다. 2D 공간에서 점 로봇은 $x=(x,y)$ 을 사용하고, 차량은 여기에 방향( $\theta$ ), 속도, 조향을 추가하며, 매니퓰레이터는 모든 관절 각도를 포함한다. 상태를 단순화하면 탐색 비용이 줄어들지만, 하류 차량이 실현할 수 없는 곡선이 생성될 수 있다.

장애물 확장 알고리즘은 장애물을 확장하여 유한 로봇을 점 탐색으로 전환한다. 여기서 $r_{loc}$ 는 불특정한 평균 오차가 아니라, 정의된 신뢰 수준에 따라 선택된 반경과 같은 명시된 불확실성 항이어야 한다. 개념적인 최소값은 다음과 같습니다.

r_{inflate}=r_{robot}+r_{loc}+r_{safe}

여기서 $r_{robot}$ 은 물체 반경이고, 위치 불확실성은 앞의 항으로 나타내며, $r_{safe}$ 는 추적/정지 여유입니다. 실제 여유는 지도 해상도, 센서 사각지대, 접근하는 물체의 속도, 제동 능력에 따라 달라집니다. 여유가 너무 작으면 충돌이 발생하고, 너무 크면 통과가 불가능하다고 판단합니다.

다이어그램: Duskcoil, 측정된 것이 아닌 개념도. 셀 크기와 팽창률은 실제 로봇의 발자국, 불확실성 및 작동 범위에서 도출해야 합니다.

그리드 탐색: 다익스트라 및 A*

음수가 아닌 에지 비용 $c(u,v)\ge0$ 을 갖는 그래프 $G=(V,E)$ 에 대해 다익스트라 알고리즘은 알려진 시작 비용이 가장 낮은 미정착 노드를 반복적으로 찾습니다. $g(n)$ 의 복잡도로 이웃 노드와의 관계를 완화합니다. 일단 안정화되면 $g$ 값이 최단이 됩니다. 이진 힙을 사용하는 경우 대표적인 복잡도는 $O((|V|+|E|)\log|V|)$ 입니다. 이는 최단 그래프 거리를 보장하지만, 목표에 대한 정보가 없으면 경로가 크게 확장되는 경향이 있습니다.

A* 알고리즘은 노드를 다음과 같이 정렬합니다.

f(n)=g(n)+h(n)

여기서 $h(n)$ 은 남은 비용의 하한입니다. 허용 가능한 휴리스틱은 실제 남은 비용을 과대평가하지 않으므로 A*는 최적해로 남습니다. 맨해튼 거리는 4-연결 그리드에 적합하고, 유클리드 거리 또는 체비셰프 관련 거리는 8-연결 그리드에 적합할 수 있습니다. 일관된 휴리스틱은 또한 $h(n)\le c(n,n')+h(n')$ 을 만족하고 재확장을 줄입니다.

가중 A*는 최적성을 희생하면서 실행 가능한 경로를 더 빠르게 찾기 위해 휴리스틱의 복잡도를 $w>1$ 만큼 높입니다. 이는 건전한 방법이 될 수 있습니다. 명시적인 경우 운영상의 트레이드를 고려합니다. 에지 비용은 길이뿐만 아니라 장애물 위험 증가, 여유 공간, 회전, 에너지 또는 지형과 같은 요소를 인코딩할 수 있습니다. 따라서 출력은 최소 정의된 비용이며, 반드시 최소 기하학적 길이일 필요는 없습니다.

연속 및 고차원 공간: RRT, RRT*, PRM

정밀 그리드는 6관절 로봇 팔 구성 공간 또는 차량 자세 공간에서 급격히 증가합니다. RRT는 자유 공간에서 $x_{rand}$ 을 샘플링하고, 가장 가까운 트리 노드 $x_{near}$ 을 찾은 다음, 해당 노드 방향으로 제한된 거리를 이동하고 충돌 검사를 수행한 후 $x_{new}$ 을 추가합니다. RRT는 확률적으로 완전합니다. 충분한 샘플이 있으면 실행 가능한 경로가 존재할 때 경로를 찾을 확률이 1에 가까워집니다. 하지만 첫 번째 경로가 가장 짧다는 것을 보장하지는 않습니다.

RRT*는 인근 정점 중에서 가장 비용이 적은 부모 노드를 선택하고, 더 저렴한 경우 새로운 정점을 통해 이웃 노드를 재배선합니다. RRT는 유한 시간 최적이 아니라 점근적으로 최적입니다. 이웃 노드 탐색, 충돌 검사 및 재배선에 시간이 소요됩니다. 컴퓨팅 자원을 소비하십시오. "최적"을 약속하기보다는 운영 마감일에 맞춰 품질을 측정하십시오.

PRM은 자유로운 구성을 샘플링하고 인접한 충돌 없는 쌍을 연결하여 재사용 가능한 로드맵을 생성합니다. 전처리 비용을 분산할 수 있기 때문에 정적인 공장이나 반복적인 로봇 팔 쿼리 환경에서 유용합니다. 동적 장애물은 에지를 무효화합니다. 좁은 통로는 균일 샘플링이 어렵기 때문에 장애물 경계, 경로 편향 또는 작업 정보 기반 샘플링이 필요할 수 있습니다.

다이어그램: Duskcoil, 간소화된 버전. 샘플링, 충돌 검사 및 연결성은 성능 측정 또는 최종 생산 경로가 아닙니다.

방법	공간/대표 비용	결과 속성	적합성 우수	주요 실패 모드
다익스트라	그래프, $O((V+E)\log V)$	최단 비음수 비용 경로	휴리스틱 없음, 전체 비용 필드	목표에서 멀어지는 방향으로 확장
A*	그래프; 최악의 경우 비교 가능	허용 가능한 $h$ 을 사용한 최단 경로	단일 그리드 쿼리	$h$ 과대평가, 낮은 비용
RRT	연속적; 샘플 의존적	확률적으로 완전함	빠르고 실행 가능한 고차원 경로	좁은 통로, 대략적인 충돌 검사
RRT*	연속적; 재배선 오버헤드	점근적으로 최적	시간이 남을 때까지 개선	마감 시간/실행 시간
PRM	전처리 및 쿼리	샘플링 조건을 사용한 확률적으로 완전함	정적 반복 쿼리	동적 공간의 오래된 에지

SLAM, Nav2 및 로컬 계획

SLAM은 지도와 자세 추정치를 제공하지만, 계획자는 타임스탬프에 맞춰 정렬된 변환과 명확한 점유/비용 의미를 필요로 합니다. 루프 폐쇄 또는 재위치화는 지도 프레임의 자세를 변경할 수 있으며, 이전 경로를 계속 따라가는 것은 위험할 수 있습니다. 불확실성, 위치 재설정 및 지도 업데이트 이벤트를 재계획 규칙에 반영해야 합니다. Visual SLAM Primer를 참조하십시오.

Nav2와 유사한 ROS 2 아키텍처에서 전역 비용 지도와 계획자는 대규모 경로를 선택하고, 지역 비용 지도와 제어기는 주변 장애물과 속도를 처리합니다. 전역 A* 알고리즘은 통로를 선택할 수 있으며, 지역 레이어는 사람을 만나면 양보하거나, 정지하거나, 우회해야 합니다. 순수하게 지역적인 레이어는 막다른 길에 갇힐 수 있습니다. 계획자, 제어기, 복구, 지도 업데이트 속도, 마감 시간 및 우선순위를 명시적으로 정의해야 합니다. ROS 2 입문에 설명된 ROS 2 전송은 실시간 또는 안전을 보장하지 않습니다.

배포 전에 페이로드, 센서 시야각, 최대 속도/감속, 위치 오차 및 지도 해상도를 포함한 크기를 측정하십시오. 좁은 통로에서 실제 여유 공간을 테스트하십시오. 계획된 경로가 연속적인 움직임 및 운동학적 특성을 고려하여 충돌 검사를 수행하십시오. 그리드 경로는 차동 구동 장치, 차량 또는 로봇 팔이 할 수 없는 방식으로 셀 사이에서 회전할 수 있습니다.

동적 장애물의 경우, 감지 최신성, 상대 속도, 제동 거리 및 재계획 시간을 측정하십시오. 계획자가 늦었다고 해서 계속 이동하지 마십시오. 알 수 없는 사람, 구멍, 투명한 장애물 및 센서 오류는 안전 상황으로 간주하고 자동으로 셀을 비우지 마십시오. 경로가 없거나, 로컬 경로가 안전하지 않거나, 공분산이 너무 크거나, 지도가 오래되었거나, 추적 오차가 허용 범위를 초과하는 경우 속도를 줄이거나, 정지하거나, 인계하십시오. 비상 정지는 계획자 출력과 관계없이 작동해야 합니다.

구현 체크리스트 및 안전성

상태 공간, 풋프린트, 프레임, 지도 해상도 및 알 수 없는 셀의 의미를 정의합니다.
위치 오차, 속도 및 정지 거리를 고려하여 모델을 확장하고, 실제 좁은 통로에서 테스트합니다.
휴리스틱의 허용 가능성을 검증하거나, 의도적으로 완화된 보장 조건을 문서화합니다.
충돌 검사 해결 방법, 난수 생성기, 마감 시간 및 샘플링 계획기의 해답 없음 동작을 기록합니다.
재위치 추정, 지도 변경, 센서 오류, 동적 장애물 및 통신 지연을 고려합니다.
경로 없음, 오래된 지도 및 추적 편차 이벤트에 대해 안전한 정지 및 진단 가능한 로그 경로를 검증합니다.

참고 자료

이해도 점검

차량이 장애물이 없는 모든 경로를 따라갈 수 있습니까?

차량의 이동 범위와 회전 제약 조건이 중요합니다. 특정 지점으로 가는 경로가 차량에게 반드시 가능한 것은 아닙니다.

Try it in the browser

Lab Change the conditions in a browser experimentNav2는 경로는 있지만 움직이지 않습니다: 진단 워크플로

제어 공학 기초: 경로 계획 — A, 다익스트라, RRT, RRT, PRM