로봇 경로 계획에서 A*·RRT·PRM을 고르는 기준

경로는 탐색 대상이 아니라 제약을 만족해야 하는 결과다

경로 계획은 시작 상태에서 목표 상태까지 충돌 없이 이동할 수 있는 경로를 상태공간에서 찾는 문제다. 로봇과 자율주행 시스템에서는 단순한 최단거리만으로 충분하지 않다. 환경 표현, 구성공간(C-space), 길이·위험·에너지 비용 함수, 동역학·가속·곡률 제약, 충돌 검사 모듈이 함께 경로의 성립 여부를 결정한다.

A* Search는 격자나 그래프 지도에서 휴리스틱을 사용해 최적 경로를 탐색한다. RRT/RRT*는 샘플링으로 탐색 트리를 확장하므로 연속 공간과 동역학 제약을 다루기 쉽다. PRM은 자유공간을 샘플링해 로드맵을 만들고, 이후 다중 쿼리에 경로를 빠르게 응답하는 방식이다.

지도와 제약이 A*의 탐색 범위를 정한다

A*는 우선순위 큐인 Open list와 방문 집합을 관리하면서 g(n), h(n), f(n) 비용을 기준으로 탐색한다. 허용적(admissible)이고 일관적(consistent)인 휴리스틱을 적용하면 최적 경로를 보장하며, 격자 기반 비용지도와 결합할 때 안정적으로 사용할 수 있다.

실시간성이나 근사 최적화가 필요할 때는 가중치 A*(WA*)와 Anytime Repairing A*(ARA*)로 확장할 수 있다. 다만 상태공간 차원이 커지면 탐색 공간도 급격히 증가하며, 협소 통로나 고해상도 지도에서는 비용이 커진다.

RRT 계열은 연속 공간에서 먼저 해를 찾는다

RRT/RRT*는 무작위 샘플, 근접 노드 탐색, 스티어링(steer) 함수, 충돌 검사를 바탕으로 트리를 늘려 간다. 고차원 또는 비선형 제약이 있는 환경에서 초기 해를 빠르게 찾는 데 유리하다.

RRT는 재배선(rewire)을 통해 발견한 경로를 개선하며 점근적 최적화를 보장한다. 샘플 수, 확장 스텝, goal bias, Informed RRT는 수렴 속도를 조정하는 요소다. 대신 결과는 확률적이어서 시드와 파라미터의 영향을 받으며, 장애물이 밀집한 곳에서는 충돌 검사가 병목이 될 수 있다.

PRM은 로드맵을 만들어 반복 질의에 대응한다

PRM은 자유공간 샘플을 뽑고 k-최근접 연결을 수행해 로드맵을 구성한다. 연결에는 직선 또는 곡률 제한을 따르는 로컬 플래너를 쓴다. 오프라인에서 로드맵을 만든 뒤 온라인 질의에 응답하므로, 같은 환경에서 여러 출발점과 목적지를 처리하는 상황에 적합하다.

협소 통로는 PRM이 취약한 영역이다. 가변 반경 r(n), 가중 연결, 가이드 샘플을 적용해 이를 보완할 수 있다. 로드맵 품질은 결과에도 직접 영향을 주며, 오프라인 구축 시간과 메모리도 고려해야 한다.

충돌 검사와 비용 모델은 모든 계획기의 공통 경로다

충돌 검사는 BVH, Voxel, Signed Distance Field(SDF)를 기반으로 수행할 수 있다. 캐싱과 증분 업데이트는 검사 지연을 줄이는 수단이다.

비용 모델은 길이, 곡률, 위험, 에너지를 가중 합산해 경로의 우선순위를 정한다. 다목표 비용을 함께 쓸 때는 정규화와 스케일링 정책이 필요하다. 지도는 Occupancy Grid, ESDF/TSDF, 폴리곤 맵, 레인-센트릭 HD Map 중 환경에 맞는 형태를 선택한다. 상태공간 역시 SE(2)/SE(3), 조인트공간, 시간 확장 공간(ST-Graph)으로 정의하며 해상도와 차원성에 따른 복잡도를 관리해야 한다.

계획기 선택부터 재시도까지의 흐름

입력에는 격자·메시·ESDF 형태의 맵, 차륜형·드론·매니퓰레이터 로봇 모델, 시작점과 목표점, 속도·곡률·동역학 제약, 시간 제한이 포함된다. 이후 알고리즘을 선택하고 탐색 또는 샘플링, 충돌 검사, 비용 평가, 경로 평활화와 재최적화를 거친다. 결과물은 웨이포인트나 스플라인 경로, 누적 비용, 성공·실패 상태, 재시도 정책으로 구성된다.

⤢✕

알고리즘별 운영 특성 비교

기준	A*	RRT/RRT*	PRM
성능	격자 지도에서 짧은 경로, 휴리스틱 품질에 민감	초기 해 빠름, RRT* 수렴에 시간 소요	오프라인 구축 후 온라인 질의 저지연
확장성	차원 증가 시 급격한 상태 폭발	고차원·비선형 제약에서 유리	고차원에서도 로드맵 재사용 효율
일관성	결정론적, 동일 입력 시 동일 결과	확률적, 시드·파라미터에 영향	확률적, 로드맵 품질에 영향
안정성	협소 통로·고해상도에서 비용 증가	장애물 밀집 시 충돌 검사 병목	협소 통로 처리 취약, 매개변수 의존
운영 편의	설정 단순, 비용지도 필요	파라미터 다수, 튜닝 필요	오프라인 시간·메모리 요구, 재사용 용이

로봇 형태에 따라 달라지는 조합

실내 이동 로봇(AMR/AGV)에는 비용지도(costmap)와 A* 글로벌 계획기를 두고, Trajectory rollout/TEB 기반 로컬 스무딩을 결합할 수 있다. 인플레이션 레이어를 포함한 장애물 업데이트를 반영하면서 재계획 주기는 5~10 Hz로 운영한다.

자율주행 차량은 레인·커넥터 기반의 PRM 또는 하이브리드 그래프를 사전에 구축해 전역 경로 질의에 사용한다. 지역 구간은 RRT*/Model Predictive Control와 결합하고 곡률·가속 제약을 포함한다.

드론과 멀티로터는 3D ESDF와 Informed RRT*로 초기 경로를 생성한 뒤 B-spline 또는 최적화로 평활화한다. 최대 속도와 가속을 기준으로 동역학 적합성을 확인하고 충돌 여유거리를 유지한다.

고자유도 매니퓰레이터에는 C-space PRM과 FCL/SDFormat 충돌 검사를 조합할 수 있다. 오프라인 로드맵을 재사용하고, 협소 통로에는 가이드 샘플링과 작업공간 힌트를 적용한다.

전역에는 PRM, 지역 재계획에는 RRT*, 비용지도 기반 백업에는 A*를 두는 하이브리드 구성도 가능하다. 이 경우 폴백 순서와 타임아웃을 정하고, 파라미터 스윕을 자동화한다.

Informed 샘플링과 휴리스틱 개선은 환경과 맵 복잡도에 따라 계획 시간을 3060% 줄일 수 있다. 하이브리드 구성은 장애물 밀집 구간의 성공률을 1025%p 높일 수 있으며, 평활화와 재최적화를 적용하면 최적 대비 비용 오차를 515% 수준으로 유지할 수 있다. PRM 로드맵을 재사용하면 다중 쿼리 처리량이 310배 증가하고 CPU 사용량의 예측 가능성이 향상된다. SDF 기반 여유거리 관리는 근접 충돌 이벤트를 20~40% 줄이는 데 활용할 수 있다.