RHS*

개요

다이나믹한 상황에서 사용되는 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값이 작은 방향으로 이동하면 된다.