Planning Algorithms - Discrete Feasible Planning 문제 정의

아래 내용은 Steven M. LaValle 교수님의 Planning Algorithms를 요약한 내용입니다. 또한, 일부 내용에는 개인적인 의견이 포함될 수도 있습니다.

여러가지 제약 조건을 만족하면서 Planning 문제를 해결한다는건 여간 어려운 일이 아닙니다. 따라서 이번 챕터에서는 조금 더 간단한 형태로 폼을 바꾼 뒤 풀어보는 방법을 찾아봅시다.

사실 대부분의 경우에서는 state space가 한정적이기 때문에 간단한 형태로 풀어보는 것도 의미가 있습니다.

어떤걸 단순화 할 것 인가?

• 어떠한 geometry model이나 differential equation이 필요 없음.
• 통계학같은 복잡함을 피하기 이해서 uncertainty(불확실성)을 고려하지 않음.
• 모든 모델들은 완전히 알려져있고 예측 가능함.

Introduction to Discrete Feasible Planning

Problem Formulation

discrete feasible planning 모델은 state-space에서 정의됩니다. 가장 기본이 되는 아이디어는 world에서 각각 구분되는 situation을 $state$, $x$ 라고 칭합니다. 또한 모든 가능한 state들의 집합을 $\textit{state space}$, $X$라고 칭합니다. discrete planning에서는 이 집합이 셀 수 있는 집합이어야 합니다. 여기서 중요한 점은 이 state space는 꼭 관련있는 정보들만 있어야 합니다. 관련없는 정보가 state안에 포함된다면 이는 문제 해결을 어렵게 만듭니다. 하지만 이 $X$는 특정 작업을 해결하기 위할만큼 충분한 데이터를 담아야 합니다.

world는 $actions, u$를 도입함으로써 변경될 수 있습니다. 즉, current state $x$에 특정 action $u$를 적용하면 새로운 new state $x$가 나오는 함수가 존재하고 이를 $\textit{state transition function}, f$라고 칭합니다. 이는 아래처럼 쓰일 수 있습니다.

$x' = f(x, u).$

여기서 action space를 정의해볼껀데 특정 state $x$에 대해서 $U(x)$를 action space라고 정의합니다. 이는 $x$에 적용가능한 모든 action들에 집합이라고 칭할 수 있습니다. 여기서 중요한 점은 두 개의 특정 state $x$, $x'$이 존재할 때 이들의 action 집합 $U(x), U(x')$은 꼭 완전히 분리되지 않을 수 있습니다. 즉, 서로 겹치는 값들이 있을 수도 있고 없을 수도 있다는 것이죠. 따라서 모든 state들에 대한 action 집합은 아래처럼 표현됩니다.

$U = \bigcup_{x\in U}{U(x)}.$

planning problem의 일부로써 goal states들은 $X_G \subset X$를 만족하고 initial state $x_I \in X$를 만족해야 합니다. (여기서 goal states는 하나의 원소만 있을 수 있고 여러 개의 원소를 가질 수 있다는 것으로 이해했습니다.)

즉, 위의 내용들을 종합해서 Discrete Feasible Planning 문제는 아래와 같이 정의됩니다.

1. 비어있지 않은 $\textit{state space X}$가 있고 이 집합은 finite(유한)하거나 countably infinite (셀 수 있을만큼 무한)한 state들의 집합이다.
2. 각 state $x \in X$마다, 유한한 action space $U(x)$가 존재한다.
3. State transition function $f$는 state를 모든 $x \in X$와 모든 $u \in U(x)$에 대해서 새로운 state를 생성하는 함수이다 ($f(x, u) \in X$). 즉, $x' = f(x, u)$로 쓰일 수 있다.
4. initial state $x_I \in X$이고 goal set $X_G \subset X$이다.

여기서 위 수식을 이해하기 쉽게 하기위해서 위의 그림처럼 directed state transition graph로 표현해 볼 수 있다. 정점들의 집합은 state space $X$로 표현되고 오직 $u \in U(x)$가 존재할 때만 (필요충분조건) $x \in X$로부터 시작되는 directed edge는 $x' \in X$로 이어진다. 그리고 initial state와 goal set은 그래프안에 특정 정점들로 정해질 수 있다.

Examples of Discrete Planning

Moving on a 2D Grid

자 이제 Discrete Planning의 예시를 생각해봅시다. robot이 Figure 2.1처럼 격자에서 움직이고 $(i, j)$로 이루어진 정수형 좌표를 가지고 있다고 생각해보면 로봇은 discrete step을 4개의 방향 (위, 아래 오른쪽, 왼쪽)에서 선택할 수 있고, 이는 하나의 좌표의 값을 올리거나 내리는 것으로 해석될 수 있습니다. (위의 그림에서 한칸씩 이동하는 것을 생각해보세요.)

여기서 위의 정리한 식과 비교해보면 $X$는 모든 정수 쌍 $(i, j), \text{in which}\ i,j \in \mathbb{Z}$의 집합이라고 볼 수 있고 $U$는 $U = \{(0, 1), (0, -1), (1, 0), (-1, 0)\}$으로 정의될 수 있다. 여기서 모든 state $x \in X$에 대해서 $U(x) = U$라고 정의하면 state transition equation은 $f(x, u) = x + u$ 형태로 정의될 수 있고 state와 action은 2차원 벡터들로 정의할 수 있습니다. 예를 들어서 $x = (3, 4)$이고 $u = (0, 1)$이면 $f(x, u) = (3, 5)$이고 이는 y 좌표로 한칸 이동했음을 의미합니다. 편의를 위해서 시작 좌표 $x_I = (0, 0)$이라고 칭하고 $X_G = \{(100, 100)\}$이라고 할 때 (0, 0)에서 (100, 100)으로 가는 sequence of action을 찾는 건 쉬울 것 입니다.

이 문제를 더 흥미롭게 만들기 위해서 우리는 위의 사각형 타일을 지워서 로봇들이 피해야 하는 좌표로도 만들 수 있습니다. 여기서 지운다는 의미는 그에 해당하는 정점들과 연관된 간선들을 state transition graph에서 삭제한다는 의미와 동일하겠지요. 여기서 가장 밖에 위치한 정점들에 울타리를 설치해서 $X$를 유한하게 만들면 매우 복잡한 미로를 만들 수도 있습니다.

Rubik's Cube Puzzle

많은 퍼즐들은 discrete planning problem들로 정의될 수 잇습니다. 예를 들어서 $3 \times 3 \times 3$ 의 작은 큐브가 있다고 생각해봅시다. 여기서의 action은 $3 \times 3$의 평면을 90도 회전하는 것으로 볼 수 있습니다. 만약 정말 많은 action들을 시도해본다면 언젠가는 색깔이 맞는 형상을 볼 수 있겠죠. 여기서의 state space는 configuration(큐브의 구성)들의 집합이 되고 각 state는 12개의 가능한 액션들이 있겠죠 (위 아래 90도 6개, 왼쪽 오른쪽 90도 6개).여기서의 planning 문제는 주어진 큐브 구성에서 모든 색깔이 동일해지는 state까지 가기위한 sequence of actions를 찾는 문제입니다.

여기서 한가지 강조할 점은 이해를 위해서 state transition graph라는 걸 소개했지만 실제로는 state transition graph를 명시적으로 표현해서 사용하는 경우는 잘 없습니다. Figure 2.1을 보면 매우 적은 정보많으로도 무한한 크기의 그래프를 표현할 수 있습니다. 따라서 전체적으로 state transition graph를 만드는것이 아닌 이걸 만들 수 있는 model을 정의하는게 훨씬 효율적이라고 볼 수 있습니다.