JPS(Jump Point Search) 알고리즘

Path Planning

JPS(Jump Point Search) 알고리즘

ABOUT-D 2025. 3. 14. 16:53

Reference

[1] Online Graph Pruning for Pathfinding on Grid Maps (2011 Proceedings of the AAAI conference on artificial intelligence)

[2] Improving Jump Point Search (2014 Proceedings of the International Conference on Automated Planning and Scheduling)

Related Work

그리드 맵에서 경로 탐색 문제를 풀 때, 대칭 경로가 많아 탐색 공간이 커지는 문제가 있다. 기존 해결책들로는

Dead-end heuristic(2006), Swamps(2010) : 그리드 맵을 인접한 지역의 series로 분해하고, 이를 이용해 탐색이 불필요한 지역을 식별한다. 이는 탐색이 불필요한 지역을 사전 제거할 수 있지만, 탐색 공간을 완전히 줄여주지는 못한다.
dead and reducdant cell 식별(2010) : 학습 기반 휴리스틱 탐색의 맥락에서 개발되었다. 반복적 심화 알고리즘을 여러번 실행한 후에야 탐색 속도를 높일 수 있으며, 추가적인 메모리 사용이 필요하다.
Fast expansion (2009) : 최적의 A* 알고리즘을 가속화한다. open list에서 best node보다 더 좋은 후속 노드를 발견하면, 불필요한 open list operation을 피한다. 이는 jump point와 비슷하지만, jump point는 확장 가능한 대규모 노드 집합을 식별하여 완전히 건너뛸 수 있다는 점에서 다르다.
HPA*(2004) : 최적성(optimality)이 요구되지 않는 경우이는 계층적 경로 탐색 방법이 만연히 사용된다. 보통 탐색 공간을 훨씬 더 작은 근사치로 분할하여 성능을 개선한다(주로 오프라인) . 빠르고 메모리 효율적이지만 최적은 아니다(suboptimal).

JPS (Jump Point Search)

1. 환경 및 표기법

우리는 undirected uniform-cost 그리드 맵을 다룬다. 각 노드는 8개 이하의 이웃을 가지고, 이동 가능(traversable)하거나 아닌 두 가지 경우만 존재한다. 이동 가능한 노드에서 이웃 노드로의 직선 이동(수직 또는 수평)의 비용은 1이고, 대각선 이동의 비용은 $\sqrt{2}$이다. 이동 불가능한(장애물) 노드를 포함한 이동은 허용되지 않는다.

$\vec{d}$ : 여덟가지 가능한 이동 방향 중 하나 (위, 아래, 왼쪽 오른쪽 등)
$y+k \vec{d}$ : 노드 $x$에서 $\vec{d}$ 방향으로 $k$ 단위 이동을 통해 $y$에 도달할 수 있다.
$d$가 대각선 이동이면, $d$에 대해 45도 각도로 이동하는 두 직선 이동을 $d_1$과 $d_2$로 표기한다.
경로 $\pi = <n_0, n_1, ...,n_k>$ : 노드 $n_0$에서 시작해 $n_k$에서 끝나는 cycle-free ordered walk
setminus 연산자 ($\pi \setminus x$) : 제외된 노드 $x$는 경로에서 나타나지 않는다.
$len(\pi)$ : 경로의 길이
$dist(n_0,n_k)$ 그리드에서 두 노드 간의 거리

2. JPS (Jump Point Search)

A* 알고리즘은 대칭적인 경로를 여러 번 평가하는 비효율성이 있다. JPS는 A* 알고리즘에 간단한 가지치기 규칙(pruning rule)을 추가하여, 불필요한 노드를 건너뛰며 중요한 노드(점프 포인트)만 선택적으로 확장한다. 이를 통해 추가적인 메모리 사용 없이 더 빠르게 최적의 경로를 찾을 수 있다.

3. 점프 포인트 (Jump points)

점프 포인트란?

특정 조건을 만족하는 중요한 노드
일반적으로 경로에서 방향이 바귀는 지점 또는 탐색할 가치가 있는 지점
중간 노드를 확장하지 않고, 한 번에 점프하여 중요한 노드로 이동

Fig. 1. (a) 직선과 (b) 대각선 점프 포인트 예시. 점선은 막다른 길(dead end)에 도달한 중간 노드 평가 시퀀스이다.

Fig. 1(a)에서, 부모 노드가 $p(x)$인 노드 $x$로 탐색이 확장되고 있다. $p(x)$에서 $x$로의 탐험 방향은 오른쪽을 향한 직선 이동이다. $x$를 확장할때, 회색으로 표시된 이웃을 평가하는 것은 별 의미가 없다. 왜냐하면 이러한 이동에 의한 경로는 $x$ 없이 $p(x)$를 포함하는 대체 경로보다 더 나을 수 없기 때문이다. 따라서 $x$의 유일한 non-dominated 이웃은 오른쪽 노드이다. JPS는 A* 알고리즘에서처럼 이 이웃을 생성하고 open list에 추가하는 것이 아닌, $y$ 같은 노드($z$와 같은 최소 하나의 non-dominated 이웃을 가진 노드)를 마주하기 전까지는 오른쪽으로 계속 이동하도록 한다. 만약 $y$(점프 포인트)와 같은 노드를 마주하면 이를 $x$의 후속 노드(successor)로 생성하고 $g-value$ $g(y)=g(x) + dist(x,y)$를 할당한다. 또는, 장애물에 도달하면 이 방향으로의 추가적인 탐색은 무의미하다는 결론을 내린다.

Non-dominated node
특정 탐색 경로에서 다른 경로보다 더 나은(짧거나 효율적인) 대체 경로가 존재하지 않는 노드.
해당 노드로 이동하는 것이 탐색 최적성(optimlaity) 유지에 필요하다.

Definition 1. Jump points

노드 $y$는 노드 $x$에서 출발하여 방향 $\vec{d}$로 향하는 점프 포인트이다.

이때 $y$는 $y=x+k \vec{d}$인 값 $k$를 최소화하고 아래 조건 중 하나를 만족해야 한다.

1. 노드 $y$는 목표 노드이다.

2. 노드 $y$는 평가가 forced인 이웃을 하나 이상 가진다.

3. $\vec{d}$는 대각선 이동이고, 조건 1 또는 조건 2에 따라 $y$에서 $z$가 점프 포인트인 방향 $\vec{d}_i \in {\vec{d}_1, \vec{d}_2}$로 $k_i \in \boldsymbol{N}$만큼 떨어진 노드 $z=y+k_i \vec{d}_i$가 존재한다.

Fig. 1(b)는 조건 3에 의해 식별된 점프 포인트의 예시이다. $x$에서 시작하여 노드 $y$를 만날때까지 대각선으로 탐색한다. $y$에서 $k_i=2$ 수평 이동으로 노드 $z$에 도달할 수 있다. 따라서 $z$는 조건 2에 의해 $y$의 점프 포인트 후속 노드이다. 그리고 이를 통해 $y$가 $x$의 점프 포인트 후속 노드임을 알 수 있다.

4. 이웃 가지치기 규칙 (Neighbour Pruning Rules)

각 노드가 생성될지 건너뛸지를 정의하기 위해 가지치기 규칙을 정의한다. 그리드에서, 어떤 노드 $x$의 인접한 노드 집합 $neighbours(x)$ 중에서 목표 최적성을 위해 평가될 필요가 없는 노드 $n$을 찾아야 한다. 이를 위해 두 경로 $\pi$(노드 $p(x)$에서 출발하여 $x$를 방문하고 $n$에서 종료)와 $\pi '$(노드 $p(x)$에서 출발하여 $x$를 방문하지 않고 $n$에서 종료)의 길이를 비교한다. 추가적으로, $\pi$ 또는 $\pi '$에 포함된 각 노드는 $neighbours(x)$에 속해야 한다.

부모 노드 $p(x)$에서 $x$로의 전환이 직선 이동인지 대각선 이동인지에 따라 두 가지 경우를 고려해야 한다. 이때, 만약 $x$가 시작 노드라면 $p(x)$는 null이고 가지치기할 게 없다.

직선 이동인 경우

다음 dominance constraint eq. (1)를 따르는 모든 노드 $n \in neighbours(x)$를 가지치기한다. Fig. 2(a)의 예시에서, $p(x)=4$이고 $n=5$를 제외한 모든 이웃을 가지치기한다.

$$
\operatorname{len}(\langle p(x), \ldots, n\rangle \backslash x) \leq \operatorname{len}(\langle p(x), x, n\rangle) \tag{1}
$$

대각선 이동인 경우

직선 이동에 대한 가지치기 규칙과 비슷한데, $x$를 제외한 경로는 엄격히 dominant 해야한다는 것만 다르다. Fig. 2(c)의 예시에서, $p(x)=6$이고 $n=2,3,5$를 제외한 모든 노드를 가지치기 한다.

$$
\operatorname{len}(\langle p(x), \ldots, n\rangle \backslash x)<\operatorname{len}(\langle p(x), x, n\rangle) \tag{2}
$$

$neighbours(x)$가 장애물을 포함하지 않고 있다고 가정하면, 직선 또는 대각선 가지치기 적용 후 남은 노드들을 $x$의 natural neighbors라고 부른다. 이는 Fig. 2(a)와 2(c)에서 흰색 노드에 해당한다. $neighbours(x)$가 장애물을 포함하면, 무든 non-natural neighbors를 가지치기 할 수 없을 수 있다. 이 경우 각 이웃에 대한 평가가 forced(강제)된다고 한다.

Definition 2. 다음과 같은 경우 노드 $n \in neighbours(x)$는 forced.

1. $n$이 $x$의 natural neighbour이 아니다.

2. $\operatorname{len}(\langle p(x), x, n\rangle)<\operatorname{len}(\langle p(x), \ldots, n\rangle \backslash x)$

Fig. 2(b)은 $n=3$의 평가가 forced일때 직선 이동의 예시이다. Fig. 2(d)는 비슷하게, $n=1$의 평가가 forced일때 대각선 이동을 포함한 예시이다.

Fig. 2. 직선 또는 대각선 이동을 통해 부모 노드 $p(x)$를 통해 노드 $x$에 도착한 몇 가지 경우. $x$로 확장되었을 때 모든 회색 노드들을 가지치기(prune)할 수 있다.

5. 알고리즘

점프 포인트 후속 노드를 식별하는 과정은 Algorithm 1에 나와있다.

line2 : 현재 노드 $x$에 인접한 이웃집합을 가지치기하여 pruned set을 얻는다.

line3-5 : 각 이웃 $n$을 $x$의 후속 노드 집합에 추가하는 대신, $x$에 대해 $n$과 같은 방대 방향이지만 더 멀리 있는 노드로 "점프"로의 상대적인 방향 가진 노드로 "점프"한다. 예를 들어, edge $(x,n)$가 $x$에서 오른쪽으로 탐사하는 직선 이동으로 구성되어 있으면, $x$의 바로 오른쪽에 있는 노드들 중에서 점프 포인트를 찾는다. 그러한 노드를 찾으면 $n$ 대신 해당 점프 포인트를 후속 노드로 추가한다. 점프 포인트를 찾지 못하면, 아무것도 추가하지 않는다.

line 6 : 이 과정을 이웃 집합이 고갈되어 $x$의 후속 집합을 return 할 때까지 계속한다.

개별 점프 포인트 후속 노드를 식별하기 위해 Algorithm 2를 적용한다.

Require : 초기 노드 $x$, 탐사 방향 $\vec{d}$, 시작 노드 $s$, 목표 노드 $g$

line1 : 알고리즘은 $\vec{d$} 방향으로 이동하여 $x$에 점프 포인트 후속 노드가 있는지 확인하기 위해 시도한다.

line5, 7, 11 : 그리고 그 위치의 노드 $n$이 Definition 1을 만족하는지 테스트한다. 만약 그렇다면, $n$을 점프 포인트로 할당하고 return 한다.

line12 : $n$이 점프 포인트가 아니면 알고리즘은 방향 $\vec{d}$과 새로운 초기 노드 $n$에 대해 반복한다.

line3 : 장애물을 만나거나 더 이상의 진행이 불가능하면 멈춘다.

line9-11 : 각 대각선 단계 전에 알고리즘은 직선 점프 포인트를 찾지 못해야 한다. 이는 Definition2의 세 번째 조건에 해당하고 최적성을 보호하기 위해 필수적이다.

6. 최적성 (Optimality)

여기서는, 그리드 맵의 각 최적 길이 경로에 대해 점프 포인트 노드만을 확장하여 찾을 수 있는 같은 길이 경로가 존재함을 증명한다(Theorem 1). 즉, 이제 "점핑" 노드가 탐색의 최적성에 아무런 영향이 없음을 증명한다.

각 최적 경로에 대해 대칭적인 대안(symmetric alternative)를 식별하고, 이를 연속적인 segment로 분할한다. 그후 이 경로를 따른 터닝 포인트(turning point)가 또한 점프 포인트임을 증명한다.

Definition 3. 터닝 포인트(turning point)는 이전 노드 $n_{i-1}$에서 $n_i$로의 탐사 방향이 $n_i$에서 다음 노드 $n_{i+1}$로의 탐사 방향과 다른 경로 상의 모든 노드 $n_i$이다. 즉, 방향이 바뀌는 지점이다.

Fig. 3은 최적 경로 상에서 마주할 수 있는 세 가지 종류의 종류의 터닝 포인트를 나타낸다. 직선-직선과 같은 다른 종류의 터닝 포인트 종류들은 suboptimal이고 이미 가지치기 되었으므로 여기서는 고려하지 않는다. 이제 diagonal-first라고 부르는 특정 최적 길이 대칭 경로를 따라 나타나는 점프 포인트와 터닝 포인트 간의 등가 관계를 찾는다.

Fig. 3. 최적 터닝 포인트의 종류. (a) 대각선-대각선 (b) 직선-대각선 (c) 대각선-직선

Definition 4. 포인트 $\pi$가 대각선-직선 터닝 포인트 $<n_{k-1}, n_{k}', n_{k-1}>$ 로 대체 가능한 직선-대각선 터닝 포인트 $<n_{k-1}, n_k, n_{k+1}>$($\pi$의 길이는 같음)을 포함하지 않으면, $\pi$는 diagonal-first이다.

임의의 최적 길이 경로 $\pi$가 주어졌을 때, Algorithm 3을 $\pi$에 적용하여 항상 대칭 diagonal-first 경로 $\pi '$를 유도할 수 있다. 이때, 이는 단지 개념적 장치일 뿐임을 유의하자.

Lemma 1. 최적 dianonal-first 경로 $\pi '$에 따른 각 터닝 포인트는 또한 점프 포인트이다.

Proof) $n_k$는 $\pi '$에 따른 임의의 터닝 포인트 노드라고 하자. Fig. 3에 나오는 세 가지 경우를 고려한다.

대각선-대각선 : $\pi '$가 최적이므로, 우회를 강제하는, $n_k$와 $n_{k-1}$ 모두에 인접한 장애물이 있어야 한다. 장애물이 없으면 $\operatorname{dist}\left(n_{k-1}, n_{k+1}\right)<\operatorname{dist}\left(n_{k-1}, n_k\right)+ \operatorname{dist}\left(n_{k}, n_{k+1}\right) $이고, 이는 $\pi '$가 최적이라는 사실과 모순이다. 따라서 $n_{k+1}$은 $n_k$의 forced neighbour이다. 이는 Definition 2의 두 번째 조건을 만족하고, $n_k$는 점프 포인트이다.

직선-대각선 : 이 경우 $n_k$에 인접한 장애물이 있어야 한다. 이게 참이 아니라면 $n_k$는 대각선-직선 터닝 포인트로 대체될 수 있어 $\pi '$가 diagonal-first라는 사실과 모순된다. $\pi '$ 가 diagonal-first라는 것이 보장되므로 $n_{k+1}$은 $n_k$의 forced neighbour이다. 이는 Definition 2의 두 번째 조건을 만족하고, 따라서 $n_k$는 점프 포인트이다.

대각선- 직선 : 이 경우는 $n_k$에서 직선 이동만을 통해 목표에 도달 가능한지 또는 $\pi '$이 추가적인 터닝 포인트를 가지는지에 따라 두 가지 가능성이 있다. 만약 직선 이동만을 통해 목표에 도달할 수 있다면, $n_k$는 Definition 2의 세 번째 조건을 만족하는 점프 포인트 후속 노드가 있고, 따라서 $n_k$는 점프 포인트이다. $n_k$ 뒤에 다른 터닝 포인트 $n_l$이 있다면, $n_l$은 직선-대각선 이어야 하고, 해당 경우에 대한 주장에 따라 이 또한 점프 포인트이다. 따라서 $n_k$는 Definition 2의 세 번째 조건을 만족하는 점프 포인트 후속 노드를 가지고, 따라서 $n_k$는 점프 포인트이다.

Theorem 1. 점프 포인트 가지치기(pruning)를 통한 탐색은 언제나 최적 솔루션을 반환한다.

Proof) $pi$를 그리드 상의 두 노드 사이에서 임의로 선택된 최적 경로라고 하자. 그리고 $\pi '$는 $\pi$에 Algorithm 3을 적용하여 유도한 diagonal-first symmetric equivalent이다. 이제 점프 포인트 가지치기로 탐사할 때 $\pi '$에 포함된 모든 터닝 포인트가 최적으로 확장됨을 보인다.

$\pi ^{\prime} $를 인접한 세그멘트들의 시리즈로 나눈다. ( $\pi^\prime = \pi_0^{\prime}+\pi_1^{\prime}+\ldots+\pi_n^{\prime}$ ) 각 $\pi_i^{\prime}=\left\langle n_0, n_1, \ldots, n_{k-1}, n_k\right\rangle$는 모든 이동이 동일한 방향으로 이동하는 하위 경로이다. 이때 시작 노드와 목적 노드를 제외한, 세그먼트의 시작과 끝에 있는 모든 노드는 전환점임을 유의하자.

$\pi_i^{\prime}$는 한 방향(직선 또는 대각선)으로만 구성되어 있으므로 Algorithm 2를 이용해 각 세그먼트의 시작 노드 $n_0 \in \pi_i^{\prime}$에서 끝 노드 $n_k \in \pi_i^{\prime} $로 점프할 수 있다. 중간 확장이 발생할 수 있지만, $n_0$에서 $n_k$로 최적으로 도달함은 보장된다. $n_0$와 $n_k$ 모두 점프 포인트로 식별되고 따라서 반드시 확장된다. Lemma 1에 따르면 $\pi ^{\prime} $를 따라 각 터닝 포인트는 역시 점프 포인트이고, 따라서 모든 터닝 포인트는 탐색 중에 확장되어야 한다. 오직 시작과 목표 노드만 남는다. 시작 노드는 각 탐색의 시작에 반드시 확장되고, 목표 노드는 정의에 따라 점프 포인트이다. 따라서 둘 모두 확장된다.

Experiments

네 가지 벤치마크에 대해 평가

Adaptive Depth : 100x100 사이의 12가지 map
Baldur's Gate : 120 maps
Dragon Age : 실제적인 벤치마크
Rooms : 256x256 사이즈의 300가지 map

Metric (둘 다 높을수록 좋은 값)

탐색 시간 가속화(search time sppedup) : 2.0이면 두 배로 빠르다는 의미
- Fig. 4에서 jump point pruning이 모든 벤치마크에서 Swamps보다 탐색 시간을 확실히 개선한다.
- 일부 경우, HPA*보다도 빠르며, 특히 작은 맵에서 유리하다
노드 확장 가속화(node expansion sppedup) : 2.0이면 노드 수의 절반이 확장되었음을 의미
- 표 1에서도 확장된 노드의 전체 수에 대한 개선을 보인다.

Swamps : 목표에 도달하는 것과 관련이 없는 맵 영역을 식별하는 데 효과적이지만, 남아 있는 영역은 탐색하는 데 여전히 상당한 노력이 필요하다. 점프 포인트는 Swamps에서는 확장된 많은 노드를 무시할 수 있음을 보인다. 두 가지 아이디어가 상호 보완적인 것처럼 보여 쉽게 결합할 수도 있다. 먼저 Swamps 기반 분해를 적용하여 현재 탐색과 관련이 없는 영역을 가지치기 한다. 그런 다음 점프 포인트를 사용하여 맵의 나머지 부분을 탐색한다.

HPA* : 메모리 오버헤드가 허용 가능하고 최적성이 중요하지 않은 경우 여전히 유리할 수 있다. Future work로, 점프 포인트 제거를 사용해 HPA*의 속도를 높일 수 있다.

[2] 에서의 JPS 정리

JPS의 두 가지 주요 규칙

Pruning rules : 불필요한 노드는 탐색하지 않도록 제거
Jumping rules : 유효한 후보 점프 포인트 찾아 빠른 이동 및 연산량 감소

Pruning Rules

부모 노드 $p$를 통해 현재 노드 $x$에 도착했을 때, 다음 조건에 해당하는 $x$의 이웃 노드 $n$을 탐색에서 제외한다.

경로 $\pi=<p,x,n>$보다 더 짧은 경로 $\pi'=<p,y,n>$ 또는 단순히 $\pi'=<p,n>$가 존재한다.
경로 $\pi=<p,x,n>$와 같은 길이지만 먼저 대각선 이동을 더 빨리 포함하는 경로 $\pi'=<p,y,n>$가 존재한다.

Fig.1에서,

회색(제거된 노드), 흰색(남아있는 이웃). 장애물이 있으면 리스트가 변경될 수 있다.
FIg. 1(a) : 직선 이동 시 하나의 natural 이웃만 유지
Fig. 1(c) : 대각선 이동 시 세 개의 natural 이웃 유지
Fig. 1(b), (d) : 장애물로 인해 forced 이웃 추가
natural 이웃 : 기존 탐색경로에서 자연스럽게 연결되는 이웃
forced 이웃 : 장애물이나 차단된 경로로 인해 강제로 탐색해야 하는 이웃

Fig. 1. (a)와 같이 p에서 x로 직선으로 이동하면 오직 하나의 natural 이웃만 남는다. (c)와 같이 p에서 x로 대각선으로 움직이면, 세 개의 natural 이웃이 남는다. (a)와 (c)에서 장애물이 x에 인접해있으면 일부 이웃은 (b)와 (d 같이 force 이웃이 된다.

Jumping Rules

JPS는 현재 노드 $x$의 각 forced 이웃과 natural 이웃에 대해 단순히 반복적인 “점핑” 과정을 적용한다. 이를 통해 각 이웃 $n$을 대체 가능한 후속 노드 $n'$로 대체한다.

점프를 통해 A* 오픈 리스트에 노드들을 넣지 않고도 맵을 빠르게 이동할 수 있다. 이는 수행할 operation의 수를 줄이고 리스트의 노드 수도 줄여 각 list operation의 비용을 낮춘다.

JPS에서 노드를 가지치기하는 것은 완전히 온라인임을 유의하자. 전처리 과정이 없으므로 메모리 overhead가 없다.