Path Planning, Guidance, Navigation, Control 알고리즘

Path Planning, Guidance, Navigation, Control Algorithm Technical Review

 

Path Planning 알고리즘은 로봇공학, 자율주행차, 드론 및 기계공학 분야에서 중요한 역할을 담당합니다 [1]. 이 알고리즘은 로봇이나 자율주행차가 지정된 목표지점까지 안전하고 효율적으로 이동할 수 있도록 경로를 계획하는 기술입니다 [1]. Path Planning의 목적은 목표지점까지 이동하는 경로를 계획하는 과정으로, 운전자 없이 스스로 이동해야 하는 자율 시스템에서 매우 중요한 기술입니다 [1]. 이러한 알고리즘은 최적의 경로를 계획하여 목표지점까지 안전하고 빠르게 이동하는 것을 목표로 합니다 [1].

 

경로계획 알고리즘은 로봇이 충돌하지 않는 여러 경로 중에서 임무에 맞게 최적의 경로를 선택하는 과정입니다 [4]. 이 과정은 환경 인식 정보를 바탕으로 충돌이 없는 공간을 탐색해 그래프(Graph)를 구축하고, 그래프를 목표에 맞게 평가하는 두 단계로 추상화할 수 있습니다 [4]. 충돌을 피하기 위한 그래프를 구축하기 위해서는 충돌 감지 알고리즘이 필요하며, 임무에 따라 최적의 경로를 선택할 수 있도록 비용 함수나 이득 함수를 적절하게 설계해야 합니다 [4].

 

경로계획은 모션 플래닝(Motion Planning)이라는 고차원 공간에서 로봇의 움직임을 계획하는 기술로 확장될 수 있습니다 [4]. 이는 2차원 및 3차원 유클리드 공간(Euclidean Space)을 넘어서 드론의 회전 운동이나 로봇 팔 관절의 움직임을 포함한 고차원 상태 공간(Configuration Space)에서의 경로를 계획합니다 [4].

 

충돌 감지 알고리즘의 발전 방향

 

충돌 감지 알고리즘은 자율주행 차량 및 로봇 시스템의 필수 요소로, 작업 중 장애물과의 충돌을 방지하기 위해 환경을 지속적으로 인식하고 분석하는 역할을 수행합니다. 이러한 알고리즘의 혁신은 로봇의 안전성 및 작업 효율성을 크게 향상시키는 주요한 방향으로 자리잡고 있습니다. 최근에는 센서 융합 기술이 발전함에 따라 다양한 센서(예: 카메라, 레이다, LiDAR)의 데이터를 통합하여 보다 정확한 충돌 감지와 회피가 가능해졌습니다. 예를 들어, 라이다 센서는 주변 환경을 3차원으로 인식하여 정밀한 장애물 감지를 수행하지만, 날씨나 조명 상태에 따라 노이즈가 발생할 수 있습니다. 이를 보완하기 위해 YOLO와 같은 딥러닝 기반의 객체 인식 기술이 사용되며, 이는 고차원 데이터의 해석 능력을 극대화하는 데 기여하고 있습니다 [12].

 

또한, 실시간 반응성을 보장하기 위해 강화학습 기반의 예측 모델과 적응형 MPC(Model Predictive Control) 기술을 포함한 복합 시스템이 개발되고 있습니다. 이러한 시스템은 예기치 않은 장애물 또는 변화하는 환경에 즉각적으로 반응하여 경로를 수정할 수 있는 능력을 부여합니다 [12]. 이러한 알고리즘들은 충돌 경고 및 회피 기능을 통합하여 자율주행차가 복잡한 환경에서도 안전하게 작동할 수 있도록 합니다.

 

앞으로의 연구 방향은 더욱 발전된 인공지능 기술과 초정밀 센서 기술의 융합을 통해 충돌 감지 알고리즘의 성능을 극대화하고, 자율주행 시스템이 자연스러운 방식으로 주변을 인식하고 반응할 수 있도록 하는 것입니다. 특히, 다수의 로봇이 협력하여 충돌을 피하고 임무를 수행할 수 있도록 하는 다중 에이전트 시스템의 발전이 강조되고 있습니다 [4]. 이와 같은 기술들은 자율주행차량, 드론 등 다양한 분야에서의 실용적인 응용 가능성을 열어나가고 있으며, 궁극적으로는 인간의 간섭 없이도 복잡한 환경에서 안전하게 작업할 수 있는 시스템을 구축하는 데 기여할 것입니다.

 

경로계획 알고리즘의 실제 적용 사례

 

경로계획 알고리즘은 자율주행차, 로봇공학, 드론 및 다양한 분야에서 실질적으로 널리 활용되고 있습니다. 특히, 최근의 연구들은 다중 임무를 수행하는 자율 시스템에서의 경로계획의 효과성을 높이기 위한 다양한 접근 방식을 개발하고 있습니다. 예를 들어, 스위스 취리히 연방 공과대학에서 개발한 Receding Horizon Next-Best-View(정보 제공형 탐사 경로계획) 알고리즘은 소형 드론이 미지의 공간을 탐사하는 과정에서 새로운 환경 정보를 실시간으로 업데이트하며 최적의 탐사 경로를 계획합니다. 이 알고리즘은 드론이 주변 환경 정보를 3차원 지도 형태로 표현하고, 관측하지 못한 공간으로의 비행을 통해 탐사를 실시하도록 설계되었습니다 [4].

 

또한, 미국 네바다 대학교와 스위스 취리히 연방 공과대학의 연구진에 의한 지하 탐사를 위한 경로계획 알고리즘은 4족 보행 로봇과 드론이 협력하여 복잡한 지하 환경을 효율적으로 탐사하는 시스템을 개발하였습니다. 이 시스템은 지역계획과 전역계획을 포함한 계층적 구조로 설계되어 있어, 각 로봇이 자신이 위치한 지역 내에서 신속하게 경로를 계획하고, 필요시 전역계획을 통해 임무를 완료하는 데 도움이 됩니다 [4].

 

무인비행체 탐사 분야에서도 경계 기반 탐사 경로계획 알고리즘이 주목받고 있습니다. 홍콩 과기대학의 Aerial Robotics Group에서 개발한 이 알고리즘은 탐사 경계 정보를 활용하여 탐사지역을 효과적으로 관리하고, 드론이 서로 간섭하지 않도록 경로를 최적화하여 넓은 영역을 고르게 탐사하는 데 중점을 두고 있습니다 [4]. 이러한 알고리즘들은 단일 드론 대신 다수의 드론을 이용해 부담을 분담하고, 각 드론의 효율성을 극대화하는 기술적 접근으로 평가받고 있습니다.

 

이렇듯, 경로계획 알고리즘은 다양한 실용적 응용 사례에서 그 효과가 입증되었으며, 자율주행 및 드론 기술의 발전에 필수적인 역할을 수행하고 있습니다. 이러한 연구들은 실제 환경에서의 안전성 및 효율성 향상을 위해 지속적으로 이루어지고 있으며, 향후 더욱 발전된 알고리즘의 출현이 기대됩니다 [4].

 

고차원 모션 플래닝의 도전 과제

 

고차원 모션 플래닝에서는 로봇이나 자율주행 시스템이 고차원 상태 공간에서 최적의 경로를 찾아내는 과정에서 여러 도전 과제가 발생합니다. 특히 로봇의 움직임을 고차원에서 계획하는 것은 간단한 2D 또는 3D 경로 계획보다 계산량이 급격히 증가하며, 장애물 회피와 같은 실시간 반응성을 요구합니다. 이와 관련하여 고차원 상태 공간에서의 경로 계획은 장애물 회피, 스스로의 동작 제한, 경로 최적화와 같은 다양한 요소를 고려해야 합니다. 

 

먼저, 고차원 상태 공간에서의 경로 계획은 각 차원에서의 변수가 서로 영향을 미치기 때문에 복잡한 계층적 구조를 필요로 하며, 이에 따라 충분한 계산 자원과 시간이 요구됩니다 [2]. 예를 들어, 드론의 경우 비행 속도, 고도, 회전 각도 등의 여러 변수를 동시에 고려해야 하므로 더 복잡한 알고리즘이 필요하게 됩니다. 이 과정에서 알고리즘은 하나의 최적 경로를 신속하게 업데이트할 수 있어야 하며, 이는 GPS 또는 IMU와 같은 센서를 통해 실시간으로 주변 정보를 수집하고 판단하는 능력을 필수적으로 요구합니다 [2][16]. 

 

또한, 고차원 경로 계획의 효율성을 저해하는 요소는 많이 존재합니다. 예를 들어, 드론과 같은 비행체는 다양한 장애물과 동적으로 변하는 환경에 대응해야 하기 때문에, 경로를 변경하면서도 안정성을 확보하기 위해 다양한 제어 기술이 필요합니다 [4]. 최근 연구에서는 적응형 MPC와 같은 제어 알고리즘을 통해 이러한 모델을 제어하고, 동시에 고차원 경로를 효율적으로 탐색하는 방법에 대한 관심이 커지고 있습니다. 이 방식은 행동 계획의 복잡성을 줄이고, 목표 달성을 위한 경로를 안정적으로 생성할 수 있는 접근으로 평가되고 있습니다 [3][4].

 

결론적으로, 고차원 모션 플래닝에서는 계산 효율성, 실시간 반응성, 그리고 다양한 환경적 요소에 대한 적응력 모두 중요하며, 이는 자율주행 시스템의 성능을 좌우하는 핵심 요소로 작용합니다. 이를 해결하기 위한 지속적인 알고리즘의 발전과 연구가 필요합니다 [3].

 

Path Planning 알고리즘의 주요 종류

 

Path Planning 알고리즘에는 다양한 종류가 있습니다. 대표적인 알고리즘으로는 Random Sampling-Based Algorithm, Probabilistic Roadmap Algorithm, Potential Field Algorithm, A* Algorithm, Dijkstra Algorithm, RRT Algorithm 등이 있습니다 [1].

 

Potential Field Algorithm은 목표 지점과 현재 위치 사이의 장력과 마찰력을 이용하여 로봇의 이동 경로를 계획합니다 [1]. 이 알고리즘은 시작 지점부터 목표 지점까지 이동 경로를 계획하기 위해 인력(Attractive Force)과 척력(Repulsive Force)이라는 두 가지 요소를 에너지로 정의합니다 [4]. 인력은 목표 지점이 물체를 끌어당기는 힘으로 작용하며 목적지를 향하는 경로를 유도합니다 [4]. 반면에, 척력은 장애물이 주변을 밀어내는 힘으로써 로봇이 장애물을 회피하도록 유도합니다 [4]. 이 방법은 다른 알고리즘에 비해 계산량이 비교적 적어 빠르게 경로를 계획할 수 있지만, 복잡한 환경에서는 최종 목적지까지 이동하지 못하고 한 지점에서 맴도는 문제가 발생할 수 있습니다 [4].

 

Dijkstra Algorithm은 너비 우선 탐색 알고리즘을 이용하여 최단 경로를 계산하는 알고리즘입니다 [1]. 이 알고리즘은 그래프의 시작 노드(Node)에서 모든 노드까지의 최단 경로를 검색하는 알고리즘입니다 [4]. 경로계획 그래프를 형성한 후 각 목적지로 이동할 수 있는 다양한 경로를 비교함으로써 최적의 경로를 선택할 수 있습니다 [4]. 하지만 그래프의 모든 경로를 검색하는 특징으로 인해 최종 목적지가 이미 결정된 상황에서 다른 노드까지 최단 경로를 계획하는 불필요한 계산을 포함합니다 [4].

 

A* Algorithm은 휴리스틱 함수를 이용하여 경로를 계획하는 알고리즘입니다 [1]. 이 알고리즘은 Dijkstra 알고리즘의 단점을 극복하고자, 목표 노드까지의 최단 경로를 적은 계산량으로 계산하도록 설계되었습니다 [4]. 목표 지점까지의 이동 비용을 휴리스틱 비용(Heuristic Cost)으로 정의하며, 값을 정확하게 추정할수록 불필요한 탐색 없이 빠르게 최단 경로를 계획할 수 있습니다 [4]. A* 알고리즘의 휴리스틱 비용으로 격자 간 유클리드 거리(Euclidean Distance)를 사용함으로써 빠르게 최단 거리의 경로를 찾습니다 [4].

 

RRT(Rapidly-exploring Random Tree) Algorithm은 로봇이나 차량의 이동 경로를 무작위로 트리 구조로 만들어가면서 최적 경로를 탐색하는 알고리즘입니다 [1]. 이 알고리즘은 샘플링 방식을 사용하여 환경을 트리 구조로 탐색하고 확장합니다 [4]. RRT는 PRM과 비교할 때 그래프 구축과 경로 검색이 더 빠르지만, 무작위성 샘플링을 통한 확장 방식 때문에 실행마다 다른 경로를 생성할 수 있습니다 [4]. 또한, 많은 샘플링을 수행하더라도 항상 최적의 경로를 제공하는 것은 아닙니다 [4].

 

각 알고리즘의 성능 비교 분석

 

Path Planning과 Guidance 알고리즘의 성능 비교는 자율주행 시스템의 효과성 및 효율성을 이해하는 데 필수적인 요소입니다. 독립적인 작업을 수행하는 SAPF(Single Agent Path Finding)와 여러 에이전트 간 상호작용을 고려하는 MAPF(Multi Agent Path Finding)는 각기 다른 특성과 성능을 가집니다. SAPF 알고리즘은 안정적이고 이해하기 쉬운 경로 탐색을 제공하며, A*, Dijkstra와 같은 고전적인 접근 방식을 사용하여 하나의 에이전트에 대한 최단 경로를 탐색합니다. 이들 알고리즘은 일반적으로 낮은 계산 비용으로 높은 정확성을 제공하지만, 환경이 복잡해질 경우 성능이 저하될 수 있습니다 [2].

 

반면에 MAPF는 여러 에이전트가 함께 존재하는 환경에서 최적의 경로를 생성하기 위한 접근 방식으로, 각 에이전트 간의 충돌을 방지하기 위한 복잡한 조정 작업이 포함됩니다. 이러한 과정에서 각 에이전트는 SAPF 알고리즘을 기반으로 최적의 단일 경로를 계산한 뒤, 서로의 경로가 겹치지 않도록 재조정합니다. 이로 인해 MAPF는 계산 비용이 더 높고 복잡해지지만, 다중 에이전트 환경에서도 충돌 없이 효율적으로 동작할 수 있는 강점을 가지고 있습니다 [2].

 

Path Planning 알고리즘의 성능을 비교할 때, 알고리즘별로 데이터 처리 속도와 정확성을 측정하는 것이 중요합니다. A* 알고리즘은 휴리스틱 비용을 기반으로 경로를 보다 효율적으로 탐색할 수 있도록 설계되어, 계산 시간은 상대적으로 짧으나, 특정 상황에서는 비효율적인 경로를 초래할 수 있습니다 [1]. Dijkstra 알고리즘은 모든 가능한 경로를 탐색하므로 정확도는 높지만, 계산 비용이 많아 복잡한 환경에서는 비효율적일 수 있습니다 [4].

 

그 외에도 RRT(Rapidly-exploring Random Tree) 알고리즘은 실시간 경로 탐색에 유리하지만, 경로의 최적성은 보장되지 않으며, 무작위 샘플링에 의해 결과가 크게 달라질 수 있습니다 [1]. 이러한 다양한 알고리즘들의 성능 비교는 특정 사용 사례, 환경적 요인, 자원 제약 등을 고려하여 수행되어야 하며, 각 알고리즘의 장단점을 명확히 이해하는 것이 중요합니다.

 

알고리즘 선택 시 고려해야 할 요소

 

Path Planning 알고리즘을 선택할 때는 여러 가지 요소를 종합적으로 고려해야 합니다. 각 알고리즘은 특정 환경과 요구사항에 적합한 장단점이 존재하기 때문에, 목적에 맞는 알고리즘을 선정하는 것이 매우 중요합니다. 다음은 알고리즘 선택 시 고려해야 할 주요 요소들입니다:

 

- 환경 복잡성: 알고리즘은 장애물이나 복잡한 환경에서 얼마나 잘 작동할 수 있는지를 고려해야 합니다. 예를 들어, RRT(무작위 탐색 트리) 알고리즘은 복잡한 환경에서 유연하게 대처할 수 있지만, 항상 최적의 경로를 제공하지는 않으며, 다양한 환경에서의 성능 검증이 필요합니다 [1] . 

 

- 경로 계획의 정확도: 정확성이 중요한 경우, A* 알고리즘이 선호됩니다. 이 알고리즘은 높은 정확성으로 최단 경로를 계산할 수 있지만, 계산 비용이 더 높을 수 있다는 단점이 있습니다 [1] . 

 

- 계산 비용: 경로 계획을 수행하는 데 드는 시간과 자원은 중요한 요소입니다. Dijkstra 알고리즘은 높은 정확성 대신 상대적으로 높은 계산 비용을 요구합니다. 따라서, 계산 속도가 중요한 경우에는 경량화를 고려해야 합니다 [1] .

 

- 다중 에이전트 환경: 다중 에이전트 환경에서는 MAPF(Multi-Agent Path Finding) 알고리즘과 같이 에이전트 간의 충돌을 방지하면서 경로를 최적화할 수 있는 알고리즘을 선택하는 것이 필수적입니다. 각 에이전트가 개별적으로 최적 경로를 계산한 후 충돌을 피하는 전략이 필요합니다 [2] .

 

- 재사용 가능성과 상호작용: 특정 환경에서 이미 구축된 경로계획 그래프가 재사용될 수 있다면, PRM(확률적 로드맵) 같은 샘플링 기반 알고리즘이 유리할 수 있습니다. 이러한 방식은 매번 환경을 새로 구성하는 것보다 수행 시간과 자원을 절약할 수 있습니다 .

 

각각의 알고리즘은 특정한 해결책을 제시할 수 있으므로, 최종적으로 알고리즘 선택은 예상되는 상황, 환경상의 장애물, 제외해야 할 비용, 그리고 알고리즘이 해결해야 할 문제의 특성에 따라 결정되어야 합니다 [1] . 이와 같은 요소들을 종합적으로 고려해 적절한 알고리즘을 선택함으로써, Path Planning 분야에서의 효과적이고 안정적인 작업 수행이 가능합니다.

 

최신 알고리즘의 발전 동향

 

Path Planning 분야에서 최신 알고리즘은 지속적으로 진화하고 있으며, 다양한 기법들이 개발되고 있습니다. 최근의 연구들은 기존의 알고리즘을 개선하고 새로운 접근 방식을 도입하여 로봇의 경로 계획 효과성을 높이고 있습니다. 예를 들어, Instruction-Guided Probabilistic Roadmap (IG-PRM) 알고리즘은 자연어 지시사항을 활용하여 로봇의 경로 계획을 수행하는 혁신적인 방식입니다. IG-PRM은 대규모 언어 모델을 사용하여 사용자의 지시를 임베딩 벡터로 변환하고, 이를 기반으로 점유 맵에서 지시 기반 비용 맵을 예측합니다. 이 맵을 바탕으로 표준 최단 경로 탐색 알고리즘을 사용하여 경로를 찾습니다 [3].

 

또한, Bidirectional Guidance Informed Trees (BIGIT*)라는 새로운 비대칭 최적 샘플링 기반 경로 계획 알고리즘이 제안되어 주목받고 있습니다. 이 알고리즘은 중간 만남 전략과 게으른 경로 탐색 전략을 결합하여, 효율적으로 비방향성을 유지하면서 최적 경로를 탐색할 수 있게 설계되었습니다. 시뮬레이션 결과, BIGIT*는 기존 알고리즘보다 초기 솔루션 발견 속도와 최적 솔루션 수렴 속도가 개선된 것으로 나타났습니다 [13].

 

마지막으로, 무인비행체의 경로계획 기술 동향을 살펴보면, 최근에는 다수 드론을 활용한 탐사 경로계획 알고리즘이 활발히 연구되고 있습니다. 단일 드론이 수행하는 탐사 임무의 한계를 극복하기 위해, 여러 드론이 서로 간섭하지 않도록 구역을 분할하여 효율적으로 탐사하는 방식이 주목받고 있습니다. 예를 들어, 수목이 우거진 환경에서 ETRI 자율비행연구실은 Graph-based Exploration Planner 기술을 기반으로 탐사 경로를 생성하여 높은 효율로 임무를 수행하고 있습니다 [4].

 

이러한 최신 기술들은 자율주행차량, 드론 및 로봇 등 다양한 분야에서의 경로 계획의 정확성과 효율성을 극대화하고 있으며, 지속적인 연구 개발이 가치 있는 성과를 내고 있습니다. 다양한 환경과 조건에서 로봇의 경로 계획을 용이하게 하는 알고리즘들이 더욱 중요해질 것으로 예상됩니다.

 

SAPF와 MAPF의 구분과 역할

 

Path Finding 알고리즘은 크게 두 가지로 분류됩니다. SAPF(Single Agent Path Finding)와 MAPF(Multi Agent Path Finding)입니다 [2]. SAPF는 우리가 흔히 접하는 가장 기본적인 알고리즘들로, A*, BFS, Dijkstra 등이 포함됩니다 [2]. 이러한 알고리즘들은 맵(미로) 격자가 있고 Queue로 길을 찾아 목표 지점으로 가는 역할을 합니다 [2]. 보통 한 가지의 Agent만 가지고 알고리즘을 개발하고 최단 경로를 도출합니다 [2].

 

반면, MAPF(Multi Agent Path Finding)는 하나의 맵에서 SAPF를 사용하는 주체가 많은 경우를 말합니다 [2]. Multi Agent라고 해서 특별한 알고리즘이 있는 것은 아니며, SAPF의 알고리즘을 사용하여 Single Agent의 최적 경로를 생성한 후, 또 다른 Agent의 최적 경로를 생성하여 최종적으로 Multi Agent 경로를 생성합니다 [2]. 이 과정에서 각 Agent간 충돌을 방지하는 방법 중 한 가지를 택하여 사용합니다 [2].

 

Continuous 도메인과 Discrete 도메인

 

Path Planning 알고리즘에서 시간 도메인은 크게 Continuous Time과 Discrete Time으로 나눌 수 있습니다 [2]. CCBS(Continuous Conflict Based Search)는 CBS(Conflict Based Search)를 RealTime(ContinuousTime) 도메인으로 풀어낸 것입니다 [2]. 충돌은 동일한 공간/시간에서 발생하는데, 시간 도메인에 따라 충돌의 정의가 달라집니다 [2].

 

Discrete Time에서는 한 번에 한 격자만 이동하므로 정확히 같은 시간, 같은 공간에 있을 때만 충돌로 간주합니다 [2]. 이는 몸체가 충돌하는 경우에 해당합니다 [2]. 반면, Continuous Time에서는 연속적이므로 격자간 이동하는 도중에도 충돌이 발생할 수 있습니다 [2]. 이는 모서리로 충돌하는 경우에 해당합니다 [2].

 

최신 Path Planning 기술: IG-PRM

 

최근 Path Planning 분야에서는 인간이 제공하는 자연어 지시사항을 기반으로 로봇의 경로 계획을 수행하는 혁신적인 데이터 기반 경로 계획 알고리즘인 Instruction-Guided Probabilistic Roadmap(IG-PRM)이 제안되었습니다 [3]. IG-PRM은 기존의 모바일 로봇 내비게이션 기술을 개선하기 위해 설계되었으며, 사용자(로봇 운영자)가 "더 넓은 경로를 선택하라"거나 "작은 장애물에 주의하라"와 같은 자연어 지시를 통해 로봇의 행동 제약을 명시할 수 있도록 합니다 [3].

 

IG-PRM의 핵심 아이디어는 대규모 언어 모델(LLM)을 사용하여 이러한 지시를 임베딩 벡터로 변환하고, 이를 활용하여 점유 맵(occupancy maps)에서 지시 기반 비용 맵(instruction-guided cost maps)을 예측하는 것입니다 [3]. 이 과정을 통해 구성된 비용 맵을 바탕으로 로드맵을 구축하고, 이후 표준 최단 경로 탐색 알고리즘을 사용해 지시 기반 경로를 찾습니다 [3].

 

IG-PRM은 두 개의 주요 모듈로 구성됩니다: 지시 임베딩 모듈과 맵 인코딩 모듈입니다 [3]. 지시 임베딩 모듈은 자연어 지시를 고정 크기 벡터 임베딩으로 변환하는 역할을 하며, 맵 인코딩 모듈은 점유 맵과 지시 임베딩을 결합하여 같은 크기의 비용 맵을 생성합니다 [3]. 이렇게 생성된 비용 맵을 사용하여 PRM의 노드 샘플링 및 엣지 확장 절차를 수행하여 지시 기반 로드맵을 구축합니다 [3].

 

Guidance 알고리즘의 정의와 역할

 

Guidance 알고리즘은 경로 추종 알고리즘의 일종으로, 로봇을 현재 위치에서 전방의 목표지점까지 도달하도록 조향각을 계산합니다 [7]. Pure Pursuit과 같은 Guidance 알고리즘은 로봇이 전방의 한 목표지점을 끊임없이 쫓는 방식으로 작동합니다 [7]. 이러한 알고리즘은 기하학적 관계를 이용하여 로봇이 목표 지점에 도달할 수 있도록 필요한 조향각을 계산합니다 [7].

 

Guidance 알고리즘에서 중요한 파라미터 중 하나는 LookAheadDistance입니다 [7]. 이는 다음 목표지점이 배치되는 거리를 결정하며, 로봇이 조향각을 계산하기 위해 현재 위치에서 앞으로의 경로상에 있는 목표지점 중 얼마나 멀리 있는 목표지점을 봐야하는지를 결정합니다 [7]. LookAheadDistance의 설정에 따라 로봇의 경로 추종 방식이 달라질 수 있습니다 [7].

 

만약 LookAheadDistance를 작게 설정하면 로봇이 경로로 빠르게 되돌아오지만, 경로를 초과하여 진동할 수 있습니다 [7]. 반대로, LookAheadDistance를 길게 설정하면 경로를 따라 부드럽게 주행하지만, 코너에서 더 큰 곡률이 발생할 수 있으며, 경로 추종 성능이 저하될 수 있습니다 [7].

 

Navigation 알고리즘의 원리와 종류

 

Navigation(네비게이션)은 로봇이 목표 지점까지 안전하게 이동할 수 있도록 경로를 계획하고 이를 따라가게 만드는 기술입니다 [9]. 이는 로봇의 위치 추정(Localization), 지도 생성(Mapping), 경로 계획(Path Planning)을 포함하며, 다양한 센서 데이터와 알고리즘을 통해 이루어집니다 [9]. Path Planning은 로봇이 목표 지점까지 이동할 수 있도록 최적의 경로를 찾는 알고리즘으로, 이 과정에서는 장애물 회피와 같은 조건을 고려해서 가능한 경로 중 가장 효율적이고 안전한 경로를 선택하게 됩니다 [9].

 

Navigation 알고리즘은 크게 Global Path Planning과 Local Path Planning으로 나눌 수 있습니다 [9]. Global Path Planning은 전체 환경에 대한 정보를 바탕으로 목표 지점까지의 경로를 계산하는 방식입니다 [9]. 반면, Local Path Planning은 실시간으로 변화하는 환경을 고려하여 장애물 회피와 같은 세부적인 경로를 계획하는 방식입니다 [9].

 

A* 알고리즘은 가장 널리 사용되는 전역 경로 계획 알고리즘 중 하나입니다 [9]. 이 알고리즘은 휴리스틱 함수(Heuristic Function)를 사용하여, 시작 지점에서 목표 지점까지의 최단 경로를 탐색합니다 [9]. 이 과정에서 f(n) = g(n) + h(n) 방식으로 탐색을 최적화하여 목표 지점까지의 경로만 빠르게 탐색합니다 [9]. g(n)은 시작점에서 현재 노드 n까지 실제로 소요된 비용이며, h(n)은 현재 노드 n에서 목표 노드까지 도달할 것으로 예상되는 비용입니다 [9].

 

Dijkstra 알고리즘은 A*와 유사하지만, 휴리스틱 함수를 사용하지 않고 모든 가능한 경로를 탐색하여 가장 짧은 경로를 찾는 방식입니다 [9]. RRT 알고리즘은 확률적 경로 계획 방식으로, 복잡한 환경에서 빠르게 경로를 탐색하는 데 유리한 알고리즘입니다 [9].

 

Local Navigation과 Dynamic Window Approach

 

Local Navigation에서는 DWA(Dynamic Window Approach)와 DWB(Dynamic Window Approach의 발전형)가 많이 사용됩니다 [9]. DWA는 로봇의 속도와 회전을 고려하여, 주어진 시간 내에 이동할 수 있는 최적의 경로를 계산합니다 [9]. DWB 역시 DWA와 같이 로봇의 속도와 회전, 가속도 제한을 고려하여 단기간 실행 가능한 속도 명령의 집합을 산출합니다 [9]. 다만 DWA와 달리 DWB는 후보 경로 생성과 비용 평가 과정을 더욱 모듈화하여 분리한 점이 특징입니다 [9].

 

Control 알고리즘의 정의와 종류

 

제어 알고리즘(Control Algorithms)은 로봇의 센서 입력을 바탕으로, 액추에이터를 제어하여 원하는 동작을 수행하도록 하는 기술입니다 [11]. 로봇 제어 알고리즘은 크게 두 가지로 나눌 수 있습니다: 피드백 제어(Feedback Control)와 피드포워드 제어(Feedforward Control)입니다 [11].

 

피드백 제어는 로봇의 현재 상태를 지속적으로 모니터링하여 원하는 상태로 유지하는 방법입니다 [11]. 일반적인 피드백 제어 알고리즘으로는 PID(비례-적분-미분) 제어가 있습니다 [11]. 피드포워드 제어는 예상되는 입력이나 외부 자극에 기반하여 로봇의 동작을 사전에 조절하는 방법입니다 [11]. 이는 예측 가능한 상황에서 유용하게 사용됩니다 [11].

 

PID 제어는 로봇 제어에서 가장 널리 사용되는 알고리즘 중 하나입니다 [11]. PID는 비례(Proportional), 적분(Integral), 미분(Derivative) 제어의 세 가지 요소를 조합하여 로봇의 동작을 조절합니다 [11]. 비례 제어(P)는 현재 상태와 목표 상태 간의 차이를 줄이기 위해 비례적으로 반응합니다 [11]. 적분 제어(I)는 시간에 따라 누적된 오차를 보정합니다 [11]. 미분 제어(D)는 오차의 변화율에 반응하여 시스템의 반응 속도를 조절합니다 [11].

 

자율주행을 위한 통합적 제어 알고리즘

 

자율주행 시스템에서 제어 알고리즘은 차량의 AI가 내린 결정을 물리적 행동으로 변환하는 역할을 합니다 [10]. 이러한 알고리즘은 차량의 가속, 제동, 조향 및 기타 제어 시스템을 관리하여 선택한 동작 과정을 실행합니다 [10]. 제어 알고리즘은 정밀도와 타이밍이 매우 중요합니다 [10]. 이는 차량이 환경을 통해 안전하게 이동하고, 충돌을 피하고, 올바른 차선을 유지하고, 주변 환경의 동적 변화에 적절하게 대응하도록 보장합니다 [10].

 

자율주행 알고리즘은 크게 인지(Perception), 판단(Planning & Decision), 제어(Control)의 세 부분으로 나뉩니다 [10]. 인지는 자율주행차의 감각 시스템 역할을 하며, 차량은 라이다, 레이다, 카메라, 열화상 카메라, 초음파 센서 등 수많은 센서를 통해 주변 환경으로 부터 방대한 양의 실시간 데이터를 수집합니다 [10]. 판단은 인지를 통해 수집된 정보를 바탕으로 분석하고 의사 결정을 내리는 과정을 의미합니다 [10]. 제어는 이러한 결정을 물리적 행동으로 변환하여 실제 움직임을 만들어내는 역할을 합니다 [10].

 

자율주행을 위한 최신 알고리즘 연구

 

완전한 자율주행을 구현하기 위한 최신 연구에서는, 자율주행의 서브 시스템 중 핵심 기술인 센싱, 인지, 판단, 그리고 제어 부분에 대한 통합적인 접근이 이루어지고 있습니다 [12]. 자율주행 차량은 주변 환경을 센싱하기 위해 카메라, 라이다, 레이다와 같은 다양한 센서들을 사용합니다 [12]. 이러한 단일 센서들이 가진 문제점을 해결하기 위해 Late Fusion 방식의 센서 융합이 제안되었습니다 [12].

 

센싱 이후 인지 영역에서는 차량의 위치를 파악하고 객체를 인식하고 추적하는 역할을 합니다 [12]. 객체 인식에는 YOLO v4와 같은 딥러닝 기반 알고리즘이 사용되고, 다중 객체 추적에는 GNN JPDA와 같은 알고리즘이 사용됩니다 [12]. 차량의 현재 위치 파악을 위해서는 GPS/IMU와 카메라를 융합한 방법이 사용됩니다 [12].

 

판단 부분에서는 동작예측, 경로계획, 모션계획이 수행됩니다 [12]. 순환 신경망을 사용해서 객체의 동작을 예측하고, 경로계획으로는 D*Lite와 같은 알고리즘을 사용합니다 [12]. 생성한 경로의 궤적을 따라가기 위해서 프레네-세레 공식(Frenet-Serret formulas)을 적용하고, 종방향과 횡방향 계획을 통해 모션 계획을 수행합니다 [12].

 

제어 부분에서는 강화학습 기반의 DQN을 이용해서 전방 장애물과의 충돌과 회피의 의사결정을 수행합니다 [12]. 회피의 결정이 나면 적응형 MPC(Model Predictive Control)를 이용해서 차량을 제어합니다 [12]. 이러한 통합적인 접근은 자율주행 차량의 개발뿐만 아니라 선박과 철도, 비행체 등 다양한 무인 분야에 응용이 가능합니다 [12].

 

무인비행체를 위한 경로계획 연구 동향

 

최근의 무인비행체 경로계획 기술은 할당된 영역을 빠짐없이 관측하는 "탐사(Exploration)"를 목적으로 활발히 연구되고 있습니다 [4]. 이 탐사 기술은 무인비행체가 조난자를 수색하거나 정찰하는 임무에 적용될 수 있습니다 [4]. 주요 연구 사례 중 하나는 스위스 취리히 연방 공과대학의 Receding Horizon Next-Best-View 탐사 경로계획 알고리즘으로, 소형 드론이 미지의 공간을 탐사하는 과정에서 새로운 환경 정보를 업데이트하면서도 순간마다 최적의 탐사 경로를 계획합니다 [4].

 

미국 네바다 리노 대학과 스위스 취리히 연방 공과대학의 공동 연구진은 지하 탐사에 특화된 경로계획 알고리즘을 개발했습니다 [4]. 이 시스템은 4족 보행 로봇과 드론을 모두 사용하여 탐사 임무를 수행하며, 계층적 구조인 지역계획(Local Planning)과 전역계획(Global Planning)으로 나누어 동작합니다 [4].

 

홍콩 과기대학의 Aerial Robotics Group 연구진은 드론의 빠른 탐색 임무를 위한 새로운 탐사 경계 기반의 경로계획 알고리즘을 개발했습니다 [4]. 이 알고리즘은 경계 정보 구조(Frontier Information Structure)를 사용하여 탐사 경계를 효과적으로 관리하도록 설계되었습니다 [4]. 또한, 계층적 방법을 사용함으로써 최적의 탐사 경로를 생성합니다 [4].

 

다수 드론을 활용한 탐사 경로계획 연구도 진행되고 있습니다 [4]. 단일 드론이 넓은 공간에서 탐사 임무를 수행하면 경로계획 계산의 효율과 계획 경로의 질이 감소하는 문제를 해결하기 위해, 다수의 드론이 서로 중복되지 않는 영역을 탐사하는 방법이 연구되고 있습니다 [4].

 

한국전자통신연구원(ETRI) 자율비행연구실에서는 수목이 우거진 숲속 환경에서의 무인 탐사 및 수색 임무용 드론의 자율비행 기술을 연구하고 있습니다 [4]. 이 연구에서는 Graph-based Exploration Planner 기술을 기반으로 하는 탐사 경로계획 알고리즘을 사용하여, 넓은 탐사 공간에서 지역 및 전역계획으로 구성된 계층적 경로계획 정책을 활용하여 높은 효율로 탐사 경로를 생성합니다 [4].

 

Path Planning과 Guidance 알고리즘의 상호작용

 

Path Planning 알고리즘과 Guidance 알고리즘은 자율주행 시스템에서 상호작용하여 목표 지점까지의 안전하고 효율적인 이동을 가능하게 합니다. 최근에는 Bidirectional Guidance Informed Trees (BIGIT*)라는 새로운 비대칭적 최적 샘플링 기반 경로 계획 알고리즘이 제안되었습니다 [13]. BIGIT*는 비방향성 휴리스틱 탐색의 중간 만남 특성을 극대화하고, 새로운 게으른 전략과 일관된 비용 검색을 결합하여 비표면적인 랜덤 기하 그래프(RGG) 위에 묘사된 초기 비방향 모션 트리를 구성합니다 [13].

 

BIGIT*의 핵심은 다음과 같은 세 가지 주요 구성 요소로 나뉘어집니다: 1) 비대칭적 중간 만남 전략, 2) 게으른 경로 탐색 전략, 3) 단위 비용 검색과 휴리스틱 업데이트입니다 [13]. 비대칭적 중간 만남 전략은 스타트 상태와 목표 상태에서 동시에 탐색을 수행하여 두 트리가 만나는 최적의 경로를 찾습니다 [13]. 게으른 경로 탐색 전략은 초기 샘플링 단계에서 각 엣지의 충돌 검사를 완전하게 수행하지 않고, 교차 상태가 감지되면 해당 엣지에 대해 희소하게 충돌 검사를 수행합니다 [13]. 단위 비용 검색과 휴리스틱 업데이트는 발견된 후보 경로에 대해 발전적인 비용을 업데이트하기 위해 단위 비용 검색을 사용하여 탐색의 정확도를 높입니다 [13].

 

BIGIT*는 다양한 환경에서 기존의 샘플링 기반 경로 계획 알고리즘과 비교하여 성능이 효과적으로 개선됨을 보였습니다 [13]. 시뮬레이션 및 실제 드론 비행 경로 계획 작업을 통해 신뢰성을 입증하였으며, 모든 실험에서 초기 솔루션 발견과 최적 솔루션 수렴 속도가 증가한 결과를 보였습니다 [13].

 

결론 및 전망

 

Path Planning, Guidance, Navigation, Control 알고리즘은 자율주행 시스템의 핵심 요소로, 각각의 알고리즘이 유기적으로 상호작용하여 안전하고 효율적인 이동을 가능하게 합니다. 이러한 알고리즘은 로봇공학, 자율주행차, 드론 등 다양한 분야에서 활용되고 있으며, 최근에는 인공지능, 딥러닝 등의 기술과 결합하여 더욱 발전하고 있습니다.

 

향후에는 더욱 발전된 알고리즘과 인공지능(AI) 기술을 통해 실시간으로 환경을 인식하고 더 복잡한 경로를 계획할 수 있는 로봇 네비게이션 시스템이 등장할 것으로 기대됩니다 [9]. 온디바이스 AI 기술이 발전하는 등의 변화가 있다면 더 많은 선택지가 생길 것입니다 [9]. 이러한 발전은 자율주행 차량, 로봇, 드론 등 다양한 분야에서 활용될 것이며, 인간의 삶을 더욱 편리하고 안전하게 만들어줄 것입니다.

 

─────────────────────────────────────────────────────────

 

참고문헌

 

[1] [2208.10172] Algorithms of Real-Time Navigation and Control of ... (2022). https://arxiv.org/abs/2208.10172

[2] A New Guidance Algorithm Against High-Speed Maneuvering Target. (n.d.). https://www.kci.go.kr/kciportal/ci/sereArticleSearch/ciSereArtiView.kci?sereArticleSearchBean.artiId=ART002766432

[3] Adaptive End-to-End Architecture for Autonomous Spacecraft ... (n.d.). https://arc.aiaa.org/doi/pdfplus/10.2514/6.2024-0430

[4] AHP Hybrid Path Planning Method. (n.d.). http://journal.ksmpe.or.kr/journal/article.php?code=91513

[5] [Algorithm][Path Planning] MAPF? CCBS? 등 개념 / 종류 정리. (2024). https://aronglife.tistory.com/entry/AlgorithmPath-Planning-MAPF-CCBS-%EB%93%B1-%EA%B0%9C%EB%85%90-%EC%A2%85%EB%A5%98-%EC%A0%95%EB%A6%AC

[6] Algorithms of Real-Time Navigation and Control of Autonomous ... (2022). https://www.researchgate.net/publication/362858671_Algorithms_of_Real-Time_Navigation_and_Control_of_Autonomous_Unmanned_Vehicles

[7] Analysis of Navigation Algorithms for a Fleet of Mobile Robots by ... (2023). https://link.springer.com/chapter/10.1007/978-3-031-38563-6_60

[8] Cooperative Path Planning of Unmanned Aerial Vehicles - 국내도서. (n.d.). https://product.kyobobook.co.kr/detail/S000009418761

[9] KAIST 무인시스템 및 제어 연구실. (2014). https://unmanned.kaist.ac.kr/

[10] Navigation과 Path Planning - velog. (2025). https://velog.io/@dbwls/Navigation%EA%B3%BC-Path-Planning

[11] Neural Combinatorial Optimization in ICML 2021 - LG AI연구원. (2021). https://www.lgresearch.ai/blog/view?seq=156&page=1&pageSize=12

[12] Optimal Path Planning Algorithm for Visiting Multiple Mission Points ... (n.d.). http://www.koreascience.or.kr/article/JAKO201915540966222.page

[13] Optimal Route Guidance Algorithm using Lidar Sensor. (2021). https://koreascience.kr/article/CFKO202132348476221.page

[14] Optimization-Based Path Planning and Control for Autonomous ... (n.d.). https://repository.hanyang.ac.kr/handle/20.500.11754/167972

[15] Path Planning - MATLAB & Simulink - 매스웍스. (n.d.). https://kr.mathworks.com/discovery/path-planning.html

[16] Path Planning - 홀로쓰는 나의일지 - 티스토리. (2023). https://sofee.tistory.com/33

[17] Path Planning Basics: Dijkstra Algorithm. (2022). https://soohwan-justin.tistory.com/73

[18] [PDF] Proposal of Algorithms for Navigation and Obstacles Avoidance of ... (n.d.). https://arxiv.org/pdf/1611.09436

[19] [PDF] 로봇주행 기술 및 표준화 동향 - 한국전자통신연구원. (n.d.). https://ettrends.etri.re.kr/ettrends/downloadPdf.do?paperno=0905001676

[20] [PDF] 자율주행자동차, 딥러닝 기술을 탑재하다 도심 싱크홀 공포, IoT로 예방. (2017). https://kist.re.kr/_attach/kist/file/2023/12/peBzUDxeOtjDwlvhaVJMzMlrgM.pdf

[21] [PDF] 적응 알고리즘을 통한 가변 시스템의 진동 제어. (n.d.). https://www.ksae.org/func/download_journal.php?path=L2hvbWUvdmlydHVhbC9rc2FlL2h0ZG9jcy91cGxvYWQvam91cm5hbC9BYnN0cmFjdF8xNTY1Nzg4MzQwXzc2NTQucGRm&filename=S1NBRUpTQ18yMDA5MDUxNV8yNS0yNi5wZGY=&bsid=6288

[22] [Robotics] Potential Field Method - gyeongtiger 님의 블로그 - 티스토리. (2024). https://gyeongtiger.tistory.com/17

[23] The Rise of Autonomous Robots: AI-Driven Navigation and Control. (2025). https://www.researchgate.net/publication/387743724_The_Rise_of_Autonomous_Robots_AI-Driven_Navigation_and_Control

[24] 경로계획 알고리즘 - 그래프, 구분, 용도, Flood Fill - velog. (2023). https://velog.io/@jm7029/%EA%B2%BD%EB%A1%9C%EA%B3%84%ED%9A%8D-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%EB%B6%84

[25] 내비게이션 “경로 재탐색” 자주 하면 오히려 늦게 간다? - 한겨레. (2015). https://www.hani.co.kr/arti/science/science_general/715465.html

[26] 네비게이션의 원리가 무엇일까? : 네이버 블로그. (2024). https://blog.naver.com/bella00217/223697351305?viewType=pc

[27] [논문 리뷰] Asymptotically Optimal Sampling-Based Path Planning ... (2025). https://www.themoonlight.io/ko/review/asymptotically-optimal-sampling-based-path-planning-using-bidirectional-guidance-heuristic

[28] [논문 리뷰] Path Planning for the Mobile Robot: A Review. (2021). https://voilier-bsc.tistory.com/15

[29] [논문 리뷰] Path Planning using Instruction-Guided Probabilistic ... (2025). https://www.themoonlight.io/ko/review/path-planning-using-instruction-guided-probabilistic-roadmaps

[30] [논문리뷰] Classifier-Free Diffusion Guidance - 전생했더니 인공지능 ... (2023). https://kimjy99.github.io/%EB%85%BC%EB%AC%B8%EB%A6%AC%EB%B7%B0/cfdg/

[31] [논문]자율주행을 위한 센서 융합 및 딥러닝 기반의 주행 제어 알고리즘. (2024). https://scienceon.kisti.re.kr/srch/selectPORSrchArticle.do?cn=DIKO0015751694

[32] 로봇 경로 설정에 대한 이야기. (2023). https://yujinrobot.com/resource/blog/robotic-path-planning-explained

[33] 로봇 제어 알고리즘 - 신석구 - 티스토리. (2024). https://afwqegwagesafte.tistory.com/12

[34] 로봇 제어 알고리즘 설계 및 개발 - wntdev - 티스토리. (2024). https://wntdev.tistory.com/198

[35] 모델예측제어 및 강화학습의 기술 동향 - 전기의세계 - DBpia. (2021). https://www.dbpia.co.kr/journal/articleDetail?nodeId=NODE10599353

[36] 무인 자율 주행을 위한 Path-planning & Vehicle Control 기술 | DBpia. (n.d.). https://www.dbpia.co.kr/journal/articleDetail?nodeId=NODE02359019

[37] 무인비행체 경로계획 기술 동향. (2024). https://ettrends.etri.re.kr/ettrends/209/0905209002/

[38] 빅데이터 등 첨단 기술 집약체, 내비게이션 작동 원리는? - 한국일보. (2016). https://www.hankookilbo.com/News/Read/201611050421476822

[39] [오토저널] 자율주행자동차의 주행 알고리즘 개발을 위한 조향 구동 ... (2021). https://dpg.danawa.com/news/view?boardSeq=60&listSeq=4714810

[40] [자동차 공학] Pure Pursuit - 네이버 블로그. (2021). https://m.blog.naver.com/rich0812/222592223219

[41] [자료 구조] 최단 거리 알고리즘 정리 (다익스트라, 벨만 포드, 플로이드 ... (2022). https://roytravel.tistory.com/340

[42] [자율주행] Path Planning 알고리즘 종류와 특성 - Monglory - 티스토리. (2023). https://monglory.tistory.com/18

[43] 자율주행 인지, 판단, 제어 알고리즘의 중요한 역할 - 디바인테크놀로지. (2023). https://divinetechnology.tistory.com/65

[44] 최적 경로 계획을 위한 RRT*-Smart 알고리즘의 개선과 2, 3차원 환경 ... (n.d.). https://www.jksaa.org/archive/view_article?pid=jksaa-27-2-1

[45] 출판물 - 한국자동차공학회. (2000). https://ksae.org/journal_list/search_index.php?mode=view&page_mode=all&sid=52157&keyfield=&keyword=&page=237&kwon_title=JUVDJUI2JTk4JUVBJUIzJTg0JUVEJTk1JTk5JUVDJTg4JUEwJUVCJThDJTgwJUVEJTlBJThD

[46] [항공우주] Guidance, Navigation, and Control (GNC)란 무엇인가. (2023). https://normal-engineer.tistory.com/433