그리드 환경에서 휴리스틱 검색 알고리즘의 성능 지표

3 실험 환경 및 성능 지표

휴리스틱 검색 알고리즘은 시작 위치와 목표 위치가 주어지면 최적의 경로를 결정하므로 로봇 경로 찾기와 같은 분야에서 중요한 역할을 합니다. 그리드 기반 환경은 자율 항법 및 로봇공학과 같이 이러한 알고리즘을 구현할 수 있는 실제 환경 시나리오를 표현하는 데 일반적으로 사용됩니다[6]. 본 연구에서는 잘 알려진 휴리스틱 검색 알고리즘인 D*, D* Lite, LPA*, LRTA*, RTAA*, ARA*를 다양한 그리드 환경에서 종합적으로 분석합니다. 우리는 유클리드 거리 휴리스틱을 사용하여 알고리즘 검색을 안내하고 장애물 밀도 및 그리드 크기와 같은 몇 가지 그리드 특성이 알고리즘 성능에 미치는 영향을 평가합니다.

우리 연구에서는 연구 커뮤니티의 경로 계획 작업에 일반적으로 사용되는 것 외에도 단순성과 제어 용이성으로 인해 그리드 기반 환경을 사용합니다. 그리드는 횡단 가능한 상태를 나타내는 흰색 셀로 구성되는 반면, 검은색 셀은 횡단 불가능한 장애물을 나타냅니다. 시뮬레이션의 에이전트는 8개 방향으로 이동할 수 있으며 비용은 수평 및 수직 이동의 경우 1, 대각선 이동의 경우 √2입니다. 우리는 무작위로 생성된 그리드 환경과 개인화된 그리드 환경이라는 두 가지 유형의 그리드 환경을 사용했습니다.

무작위로 생성된 그리드 기반 환경: 그리드는 세 가지 매개변수로 특징지어집니다.

그리드 크기(NxN), 장애물 밀도, 시작 상태와 목표 상태 사이의 거리. 검색 알고리즘 성능에 대한 각 매개변수의 영향을 조사하기 위해 다른 매개변수는 일정하게 유지하면서 각 매개변수를 독립적으로 변경했습니다. 변형에는 그리드 크기의 변화, 시작부터 목표까지의 거리의 변화, 장애물 밀도의 변화가 포함되었습니다. 변형의 각 그리드에 대해 동일한 그리드 매개변수의 무작위 인스턴스 10개를 생성했습니다(예: 장애물 밀도가 0.25이고 크기가 300x300이며 시작에서 목표까지의 거리가 140인 그리드에는 무작위로 생성된 10개의 인스턴스가 있습니다).

개인화된 그리드 환경: 보다 구체적인 시나리오를 시뮬레이션하도록 설계되었습니다. 이러한 그리드는 고정된 크기(71x31 단위)와 시작 및 목표 상태 모두에 대해 고정된 위치를 가지며 장애물 구성에 따라 두 부분으로 나뉩니다.

• 수평 벽 구성: 이 실험에서는 그리드 길이 10단위마다 그리드 너비의 절반인 수평 벽을 추가합니다. 새로 생성된 그리드에 두 가지 방향으로 벽을 추가했습니다. 한 번은 왼쪽에서 오른쪽으로, 한 번은 오른쪽에서 왼쪽으로 추가했습니다.

• 수평 벽 길이 구성: 여기서는 내부에 배치할 수 있는 가능한 모든 벽을 추가합니다.

그리드 길이를 지정하고 새 그리드를 생성할 때마다 모든 벽 길이를 2단위씩 늘립니다.

우리는 철저한 분석을 제공하기 위해 이 두 가지 서로 다른 환경을 채택했으며, 두 가지 다른 방해 시나리오가 있는 경우 검색 알고리즘의 성능에 대한 미묘한 통찰력을 밝히려고 노력했습니다. 첫 번째에서는 장애물이 그리드 내에서 무작위로 흩어져 있는 반면, 두 번째에서는 벽과 같은 구조물이 연결된 장애물 덩어리로 나타납니다.

실험에 사용된 다양한 검색 알고리즘의 성능을 평가하기 위해 다음 측정항목을 선택했습니다.

• 경로 비용: 메트릭은 시작부터 목표 상태까지 경로 길이 또는 실행된 작업 수를 측정합니다. 이는 솔루션의 품질을 나타냅니다.

• 메모리 소비: 알고리즘이 솔루션을 찾는 데 필요한 메모리 양을 측정합니다. 알고리즘의 확장성을 확인하는 것과 관련이 있으며 (KB) 단위로 측정됩니다.

• 해결 시간: 알고리즘이 해결 방법을 찾는 데 걸리는 총 시간(ms)을 밀리초(ms) 단위로 나타냅니다.

우리는 250GB RAM을 탑재하고 Ubuntu Linux 22.04를 실행하는 3.30GHz 27 Intel i9 코어에서 실험을 수행했습니다. 다음 설정 사용: 모든 알고리즘은 유클리드 거리를 휴리스틱 함수로 사용했습니다. LRTA* 및 RTAA*의 경우 각 반복마다 확장된 노드 수를 250으로 설정했습니다. ARA* 알고리즘은 휴리스틱을 위해 2.5의 가중치로 실행되었습니다. 무작위성을 설명하고 결과의 신뢰성을 보장하기 위해 각 그리드에서 각 알고리즘을 100번 실행했습니다.