KR-20260061495-A - Obstacle avoiding A-Star route search method using midpoint

Abstract

본 발명은 자율주행 시스템에서 에이스타 알고리즘을 이용한 장애물 회피 경로 탐색 방법을 개선하기 위해 제안되었다. 본 발명은 이러한 문제를 해결하기 위해 중간 지점을 도입한 장애물 회피 경로 탐색 방법을 제안한다. 기존의 에이스타 알고리즘을 개선하여 경로 상에 장애물이 있을 경우, 중간 지점을 설정하여 장애물을 회피하는 방식이다. 중간 지점은 탐색 범위 내에서 휴리스틱 값이 가장 낮은 노드로 선정되며, 경로 탐색 과정 중 환경이 변화할 경우 실시간으로 갱신될 수 있다. 특히 장애물이 경로에 위치할 경우 해당 구간의 휴리스틱 값을 높게 설정하여 우회 경로를 유도함으로써 경로 탐색의 정확성과 효율성을 동시에 확보한다. 본 발명의 방법은 중간 지점을 경유함으로써 장애물을 회피하는 동시에 최적 경로를 유지할 수 있도록 돕는다. 이를 통해 탐색 공간이 넓고 환경이 동적으로 변화하는 자율주행 상황에서도 효율적인 경로 탐색이 가능하며, 기존의 알고리즘보다 단순하면서도 효과적으로 장애물을 회피할 수 있다.

Inventors

• 김주현

Assignees

• 김주현

Dates

Publication Date

20260506

Application Date

20241027

Claims (1)

1. 장애물 회피를 위한 경로 탐색 방법에 있어서, 중간 지점을 활용하여 경로 탐색 알고리즘을 두 번 이상 사용하는 경로 탐색 방법.

Description

중간 지점을 활용한 장애물 회피 에이스타 경로 탐색 방법{Obstacle avoiding A-Star route search method using midpoint} 본 발명은 중간 지점을 활용한 에이스타 최단 경로 탐색 알고리즘 기반의 장애물 회피 경로 탐색 방법에 관한 것이다. 자율주행 시스템에서는 출발지에서 목표 지점까지의 최적 경로를 찾기 위해 다양한 경로 탐색 알고리즘이 사용된다. 대표적인 경로 탐색 알고리즘으로는 다익스트라(Dijkstra) 알고리즘과 에이스타 알고리즘이 있다. 다익스트라 알고리즘은 출발지부터 목표 지점까지 가능한 모든 경로를 탐색하여 최적 경로를 보장하지만, 탐색해야 하는 노드가 많아질수록 계산량이 급격히 증가하여 비효율적일 수 있다. 반면 A 알고리즘은 목표 지점까지의 예상 비용을 휴리스틱 함수로 반영하여 효율적으로 탐색하며, 자동차 내비게이션과 같은 응용 분야에서 널리 사용되고 있다. 기존 연구에 따르면 장애물의 분포와 복잡도를 반영하지 않는 경로 탐색 방식은 현실적인 환경에서 한계가 있을 수 있다. 특히 복잡한 장애물이 존재하는 상황에서는 다익스트라 및 에이스타 알고리즘의 성능이 저하될 수 있다. 이를 보완하기 위해 HPA (Hierarchical Pathfinding A)** 알고리즘이 제안되었는데, 이는 경로 탐색 공간을 블록 단위로 분할하여 탐색 효율을 높이는 방식이다. 하지만 블록의 크기에 따라 경로의 정확도가 저하되거나, 전처리 과정과 온라인 탐색 과정이 복잡해지는 문제가 존재한다. 자율주행 자동차는 이동 중 주변 환경이 실시간으로 변하기 때문에 기존의 알고리즘만으로는 충분한 경로 탐색 성능을 제공하기 어렵다. 따라서 인식된 장애물의 범위를 동적으로 반영하여 경로를 실시간으로 수정할 수 있는 탐색 알고리즘이 필요하다. 예를 들어, 목표 지점까지의 직선 경로상에 장애물이 있으면, 직선의 기울기를 점차 변경하며 장애물을 피할 수 있는 경로를 찾아야 한다. 또한 경로를 탐색할 때 중간 노드(t1, t2 등)를 설정하여 여러 경유지를 거치는 방식이 최적 경로를 보장할 수 있다. 이러한 방식은 장애물과의 거리와 분포를 휴리스틱 함수로 반영함으로써 경로 탐색의 효율성과 정확성을 동시에 높인다. 본 발명은 기존의 경로 탐색 알고리즘이 가진 한계를 극복하기 위해 장애물 인식을 기반으로 한 동적 경로 탐색 알고리즘을 제안한다. 이는 실시간으로 인식된 장애물 정보를 반영하여 탐색 경로를 수정하며 경로 탐색 효율을 극대화한다. 도 1은 경로 탐색 방법의 흐름도이다. 본 발명을 첨부된 도면을 참조하여 상세히 설명하면 다음과 같다. 도 1은 경로 탐색 방법의 흐름도로 알고리즘의 순서를 나타낸다. 먼저 입력값 받기(101)에서 입력값은 플랫폼의 탐색 범위내의 데이터를 의미한다. 데이터를 바탕으로 지도를 구성하고 주변 지형을 파악하여 장애물의 감지할 있다. 지도를 구성하면 장애물과 목표 지점의 상대적인 위치를 구체화한다. 또한 지도를 구성함으로써 지형을 그리드로 나누고 각각의 노드로 여길 수 있다. 탐색 범위 내의 노드 휴리스틱 함수 계산(102)은 탐색 범위내의 모든 노드의 휴리스틱 함수를 계산함을 의미한다. 이후 휴리스틱 함수가 가장 작은 노드를 중간 지점으로 저장(103)한다. 해당 중간 지점을 목표 지점으로 하여 근접한 노드의 휴리스틱 함수를 계산(104)한다. 마찬가지로 휴리스틱 함수가 가장 작은 곳으로 이동(105)한다. 이동할 때는 탐지 범위가 달라짐에 따라 중간지점이 변할 수 있다. 따라서 목표지점 도착 여부(106)를 살피고 위 순서를 도착(107)할 때까지 반복한다.