JPS 알고리즘 - 그래프에 방향성이라는 조건을 추가하니 더 최적화가 되네요?

안녕하세요. 오늘은 Jump Point Search(JPS) 알고리즘을 공부하려고 합니다.

• HARABOR, Daniel; GRASTIEN, Alban. Online graph pruning for pathfinding on grid maps. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2011. p. 1114-1119.
• node pruning 기법으로 훌륭한 성과를 낸 논문입니다!

 
2011년에 소개된 알고리즘인데 A* 알고리즘에서 노드 탐색 부분을 최적화하여 엄청난 성능 향상을 얻어낸 알고리즘이더라고요!

벤치마크에서 JPS가 압도적으로 뛰어난 성능을 보여줍니다!

어떻게 노드 탐색 부분을 최적화 했는지 자세히 알아볼까요?

---

1. A* 알고리즘과 JPS 알고리즘의 차이점

A* 알고리즘과 JPS 알고리즘의 가장 큰 차이점은 방향성을 고려하여 OPEN 리스트에 추가되는 노드의 수를 감소시킨 것입니다.

방향성을 어떻게 고려했는지 간단하게 살펴보고, 알고리즘의 동작 방식을 구체적으로 살펴보도록 하겠습니다.
 

2. 방향성 - 선택한 것에 대해서 끝장을 본다.

앞서 언급한 방향성부터 설명드리겠습니다.

예시 1

예시 1의 노드 4이 OPEN 리스트에 추가되어 있다고 가정해봅시다.
그러면 노드 4이 목적지인지 확인하고 다음으로 확인할 노드들을 OPEN 리스트에 추가하겠죠?
 
A* 알고리즘이었다면 노드 1, 노드 5, 노드 7을 OPEN 리스트에 추가하고 각각의 노드들에 대해서 탐색을 진행할 것입니다.
 
하지만 JPS 알고리즘은 다릅니다.
노드 5로 가는 오른쪽으로 뻗어나가는 경우를 선택했다면 노드 5를 바로 OPEN 리스트에 추가하지 않고 점프하여 다음 노드 6을 확인합니다.
노드를 바로 OPEN 리스트에 추가하지 않고 한번 결정된 방향으로 점프하면서 나아갑니다.
 
JPS 알고리즘에서는 이런 방식으로 방향성이 고려됩니다.
 

3. 알고리즘 동작 방식

2. 방향성의 마지막에서 "노드를 바로 OPEN 리스트에 추가하지 않고 한번 결정된 방향으로 점프하면서"라고 두루뭉실하게 설명을 드렸습니다.
조금 더 구체적으로 설명을 드리면 다음 조건들 중 하나를 만족할 때까지 결정된 방향으로 나아갑니다.

1. 해당 방향으로 나아갔을 때, 지도를 벗어나거나 장애물이 있을 때
2. 목적지 노드일 때
3. 노드와 연결된 노드들 중에 forced 노드가 있는 경우
4. (대각선 방향으로 이동 중인 경우) 대각선 방향을 분해한 방향 중에 조건 2, 3을 만족하는 노드가 있는 경우

1을 제외하고는 해당 노드들이 jump point가 되고, jump point들은 OPEN 리스트에 추가됩니다.
 
조건 3의 forced 노드가 무엇인지 그리고 조건 4에 대해서 부연 설명을 드리겠습니다.
 

3.1. forced 노드란

노드 x와 연결된 노드들을 n라고 하고 x에 오기 전 노드를 p라고 할 때, 다음 조건들을 만족하는 노드 n을 forced 노드라고 합니다.

1. n이 노드 x의 natural neighbor이 아니다.
   • 노드 x와 연결된 노드들 중 p에서 출발하여 x를 경유해서 노드 n으로 가는 경로 길이가 p에서 출발하여 x를 경유하지 않고 노드 n으로 가는 경로 길이보다 길거나 같은 노드들을 natural neighbor이라고 합니다.
   • 대각선 이동의 경우, 대소 비교 조건이 "긴"으로 바뀝니다.
2. p부터 시작해서 x를 거쳐서 노드 n을 가는 것보다 x를 거치지 않고 노드 n을 가는 것이 더 길다.

 
백문이 불여일견! forced 노드를 직접 찾아보면서 이해해보도록 하겠습니다.

예시 2

예시 2에서 노드 4를 거쳐서 노드 5에 온 상황(오른쪽 방향으로 이동)을 가정해보겠습니다.
그러면 p는 노드 4가 되고 x는 5가 됩니다.
 
조건 1을 적용하기 위해서 노드 5의 natural neighbor 들을 찾아보겠습니다.

• 노드 5에 연결된 노드들은 1, 3, 4, 6, 7, 8, 9가 있습니다.
• 노드 4에서 노드 5로 가는 것은 대각선 이동이 아니기 때문에 노드 5를 경유했을 때의 경로 길이가 더 길거나 같은 경우를 찾아보겠습니다.
  • 주황색으로 마킹된 노드들이 natural neighbor들입니다.

도착 노드	노드 5를 경유했을 때의 경로 길이	노드 5를 경유하지 않았을 때의 경로 길이
1	2.414 ( 4 - 5 - 1 )	1 ( 4 - 1 )
3	2.414 ( 4 - 5 - 3 )	3.828 ( 4 - 8 - 6 - 3 )
4	2 ( 4 - 5 - 4 )	0 ( 4 )
6	2 ( 4 - 5 - 6 )	2.828 ( 4 - 8 - 6 )
7	2.414 ( 4 - 5 - 7 )	1 (4 - 7 )
8	2 ( 4 - 5 - 8 )	1.414 ( 4 - 8 )
9	2.414 ( 4 - 5 - 9 )	2.414 ( 4 - 8 - 9 )

노드 3과 노드 6이 forced 노드이기 때문에 노드 5는 jump point로 OPEN 리스트에 추가됩니다.
 

3.2. 대각선 방향을 분해한 방향 중에 조건 2, 3을 만족하는 경우

"대각선 방향을 분해한 방향"은 다음과 같습니다.

• 오른쪽+위 대각선 방향을 분해하면 오른쪽 방향과 윗 방향입니다.
• 오른쪽+아래 대각선 방향을 분해하면 오른쪽 방향과 아래 방향입니다.
• 왼쪽+위 대각선 방향을 분해하면 왼쪽 방향과 윗 방향입니다.
• 왼쪽+아래 대각선 방향을 분해하면 왼쪽 방향과 아래 방향입니다.

이제 "대각선 방향을 분해한 방향 중에 조건 2, 3을 만족하는 경우"가 어떤 것인지 예시로 살펴볼까요?

예시 3

 
예시 3에서 노드 9를 거쳐서 노드 6으로 온 상황(오른쪽+위 대각선 방향으로 이동)을 가정하겠습니다.
 
오른쪽+위 대각선 방향을 분해하면 오른쪽 방향과 윗 방향입니다.

• 윗방향에는 길이 더 없으므로 오른쪽 방향만 고려하겠습니다.

 
노드 6의 오른쪽 방향으로는 노드 7, 노드 8이 있습니다.
노드 7은 forced 노드가 아닙니다.

• 노드 9에서 노드 6을 거치든 거치지 않든 경로 길이가 2.414입니다.

노드 8은 forced 노드입니다.

• 노드 6에서 노드 7을 거치면 경로 길이가 2, 노드 7을 거치지 않으면 2.828입니다.

노드 8이 forced 노드이기 때문에 노드 6은 jump point로 OPEN 리스트에 추가됩니다.

---

JPS 알고리즘은 어떠셨나요?
저는 처음에 이해하기 어려웠는데 계속 보다보니 결국에는 이해가 되네요 ㅜㅠ
 
저는 노드 탐색을 최적화 하는 점이 아주 흥미로웠습니다!
그래프에 방향성이라는 조건이 추가되어야 해서 격자 지도라는 조건이 생겼지만 그렇게 큰 제약조건은 아닌 것 같더라고요.
 
JPS 알고리즘을 "더" 최적화 한 연구들도 있는데 다음에 공부해봐야겠습니다!
설명이 부족한 부분이나 잘못된 부분 알려주시면 최대한 보완하도록 하겠습니다 :)