Ahn9807: 새 문서: 분류: 경로 탐색 가운데 == 개요 == 다이나믹한 상황에서 사용되는 D*알고리즘의 간편한 버전이다. 시작점에서 끝점까지의 Path를 계산한다. 각각의 노드에 Consistency check을 하여서 그러한 Consistency가 깨지는 부분에서 Path를 업데이트하게 된다. : $rhs(n)=min_{n\in near \ by \ cells} (c(n,c') + g(n'))$ 로 정의되는 rhs값과 현재 cell의 g값이 일치...

2023-02-25T10:46:21Z

새 문서: 분류: 경로 탐색 섬네일|가운데 == 개요 == 다이나믹한 상황에서 사용되는 D*알고리즘의 간편한 버전이다. 시작점에서 끝점까지의 Path를 계산한다. 각각의 노드에 Consistency check을 하여서 그러한 Consistency가 깨지는 부분에서 Path를 업데이트하게 된다. :<math>rhs(n)=min_{n\in near \ by \ cells} (c(n,c') + g(n'))</math> 로 정의되는 rhs값과 현재 cell의 g값이 일치...

새 문서

[[분류: 경로 탐색]]

[[파일:RHS*.png|섬네일|가운데]]
== 개요 ==
다이나믹한 상황에서 사용되는 [[D*]]알고리즘의 간편한 버전이다. 시작점에서 끝점까지의 Path를 계산한다. 각각의 노드에 Consistency check을 하여서 그러한 Consistency가 깨지는 부분에서 Path를 업데이트하게 된다.

:<math>rhs(n)=min_{n\in near \ by \ cells} (c(n,c') + g(n'))</math>
로 정의되는 rhs값과 현재 cell의 g값이 일치하면 consistency라고 하고 아니면 inconsistency라고 한다. 여기서 g는 현재 노드에서 goal까지의 최소 거리이다. rhs를 풀어서 설명하면 현재 노드 근처의 노드의 g값 + 1 중 제일 작은 값이다. (c값은 1로 표현되는 거리라고 가정할 경우)

== 알고리즘 ==
우선 모든 노드와 Goal까지의 Shortest Path값을 저장한다. 만약 rhs consistency가 깨지면 현재 노드들에 어떠한 변화가 생긴것으로 새로히 Path를 계산해야 한다. 그후 연결되어 있는 모든 노드들의 consistency가 일치할 때까지 업데이트를 수행해준다. 그 다음 연결되는 노드들의 g값이 작은 방향으로 이동하면 된다.

RHS* - 편집 역사