저자:  (1) Aya Kherrour, 트렌토 대학교 정보 공학 및 컴퓨터 과학과;  (2) Marco Robol, 트렌토 대학교 정보 공학 및 컴퓨터 과학과;  (3) Marco Roveri, 트렌토 대학교 정보 공학 및 컴퓨터 과학과;  (4) Paolo Giorgini, 트렌토 대학교 정보 공학 및 컴퓨터 과학과.  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번 실행했습니다.  이 문서는 CC 4.0 라이선스에 따라   있습니다. arxiv에서 볼 수

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

EScholar Technologies

EScholar

이 오디오는 이야기의 원래 언어로 제작되었습니다!

너무 오래; 읽다

Boost your HackerNoon story @ $159.99! 🚀

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

About Author

코멘트

태그 걸기

이 기사는 다음에서 발표되었습니다.

Related Stories

Floki의 Valhalla가 인도 스리랑카 투어의 보조 후원자로 합류

HackerNoon 글쓰기 대회에서 우승하고 싶으신가요? #crypto-api 대회 우승자들이 추천하는 내용은 다음과 같습니다.

Claude Sonnet 3.5 시스템 프롬프트 유출: 법의학적 분석

Crypto Growth: 효과적인 사용자 페르소나 만들기

Floki의 Valhalla가 인도 스리랑카 투어의 보조 후원자로 합류

HackerNoon 글쓰기 대회에서 우승하고 싶으신가요? #crypto-api 대회 우승자들이 추천하는 내용은 다음과 같습니다.

Claude Sonnet 3.5 시스템 프롬프트 유출: 법의학적 분석

Crypto Growth: 효과적인 사용자 페르소나 만들기

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps