전역 경로 계획 global path planning

휴리스틱 heuristic

• 목표 지점까지의 거리를 예측하는 방법
• 휴리스틱 함수는 알고리즘의 효율성을 결정한다
• ex)
  • 맨헤튼 거리, 유클리드 거리 등이 존재

 

가중치 그래프 weighted graph

• 각 엣지에 가중치가 할당된 그래프이다.
• 가중치는 거리,시간,비용 등의 특정 기준으로 측정
  • 경로의 효율성을 평가하는데 주로 사용

 

휴리스틱 최적화 heuristic optimization

• 휴리스틱을 최적화하여 탐색 시간을 줄이는 방법
• 잘 설계된 휴리스틱은 목표까지의 경로를 효율적으로 탐색하게 한다.

 

탐색 공간 search space

• 경로 탐색 시 고려해야 하는 모든 가능한 경로의 집합
• 전역 경로 계획에서 탐색 공간을 줄이는 것은 알고리즘의 속도를 높이는 핵심 요소이다.

 

 

전역 경로 계획

• 출발지에서 목적지까지의 최적 경로를 찾는데 사용
• 전체 환경 정보를 알고 있어야 한다.
• 환경이 정적일때 유리
• 알고리즘 선택시 고려사항
  • 환경의 복잡성
    • 환경이 단순하고 정적이면 플로이드 워셜이 좋으나, 복잡하다면 a-star나 다익스트라가 더 적합
  • 계산 자원의 제약
    • 환경이 크면서 자원이 한정되어 있다면, 휴리스틱을 이용한 알고리즘이 유리
  • 장애물의 유무 및 위치 변화
    
    • 전역 경로 계획은 주로 고정된 장애물이 있는 환경에서 유리

 

다익스트라 알고리즘

• 모든 경로의 가중치를 고려하여 가장 짧은 경로를 찾는 알고리즘
• 모든 노드를 탐색하니 최적의 해를 보장
• 시간 복잡도가 node수의 제곱이라서 노드가 많이질수록 느려짐

 

A-star 알고리즘

• 휴리스틱을 사용하여 경로를 탐색하는 알고리즘.
• 다익스트라보다 효율적.
• 휴리스틱 함수를 통해서 탐색을 최적화해서 시간을 단축함.
  • 단, 휴리스틱 함수가 잘못 설계되면, 최적 경로를 찾는데 어려움 발생 

 

D-star 알고리즘

• 기본적으로 A-star와 유사하지만, 경로 중간에 새로운 장애물 등장과 같은 변화에 따라서 경로를 재계산 할 수 있는 알고리즘이다.
• 장점
  • 환경이 변화는 상황에서도 경로를 유연하게 수정 가능 

 

플로이드 워셜 알고리즘

• 모든 노드 쌍 간의 최단 경로를 찾는데 사용하는 알고리즘
• 그래프 내 모든 경로를 계산하니, 정적인 환경에서 가능한 모든 경로를 미리 계산하는 경우 유리
• 모든 노드 쌍에 대해서 최단 경로를 찾으니, 특정 경로에 대한 계산이 빠름
  • 단, 시간복잡도가 노드수의 세제곱이다.

 

벨만 포드 알고리즘

• 가중치가 음수인 경우에도 사용할 수 있으나, 다익스라에 비해서 느리다.

 

샘플링 기반 알고리즘

• RRT ( Rapidly-exploring Random Tree )
  • 무작위 샘플링을 통해서 공간을 빠르게 탐색하며 트리를 확장함
  • 고차원 공간에서도 효과적이며 빠르게 경로 탐색이 가능. 하지만 찾은 경로가 최적이 아닐수있음 
• PRM ( probabilistic Roadmap )
  • 미리 환경 내에서 다수의 랜덤 샘플 포인트를 생성하고, 이를 연결해서 그래프를 구성후, 그래프 탐색기법으로 경로를 찾는다.
  • 복잡한 환경에서도 안정적으로 작동하나, 사전 샘플링이 필요하며, 환경이 자주 바뀌면 재계산이 필요.