상태 공간

State space
Vacuum World, 유한 상태 공간의 최단 경로 문제

상태 공간은 시스템의 [1]가능한 모든 구성의 집합입니다.그것은 주어진 시스템의 행동에 대한 추론에 유용한 추상화이며 인공지능과 게임 이론 분야에서 널리 사용된다.

예를 들어 장난감 문제인 Vacuum World는 진공과 오물이 존재할 수 있는 제한된 구성 세트가 있는 분리된 유한 상태 공간을 가지고 있습니다.상태가[2] 1에서 시작하여 시간에 따라 증가하는 자연수인 "카운터" 시스템은 무한 이산 상태 공간을 가집니다.비감쇠[3] 진자의 각도 위치는 연속(따라서 무한) 상태 공간입니다.

정의.

동적계 이론에서 함수 θ에 의해 정의된 이산계 상태 공간은 동적계의 각 가능한 상태가 a에서 b까지의 [4]방향 가장자리를 갖는 정점으로 표현되는 방향 그래프로 모델링할 수 있다.이를 상태 다이어그램이라고 합니다.

함수 θ에 의해 정의되는 연속 동적 계통의 경우, 해당 계통의 상태 공간은 θ의 화상이다.

상태 공간은 컴퓨터 과학에서 기계의 단순한 모델로서 유용합니다.공식적으로 상태 공간은 태플 [N, A, S, G]로 정의할 수 있습니다.

  • N은 일련의 상태입니다.
  • A는 상태를 연결하는 호 세트입니다.
  • S는 시작 상태를 포함하는 N의 비어 있지 않은 하위 집합입니다.
  • G는 목표 상태를 포함하는 N의 비어 있지 않은 부분 집합입니다.

특성.

abcdefgh
8
Chessboard480.svg
f8 white queen
d7 white queen
g6 white queen
a5 white queen
h4 white queen
b3 white queen
e2 white queen
c1 white queen
8
77
66
55
44
33
22
11
abcdefgh
8개의 퀸 퍼즐 상태 공간의 유효한 상태

상태 공간에는 몇 가지 공통 속성이 있습니다.

예를 들어 Vacuum World의 분기 계수는 4입니다. 진공 청소기는 이동 후 인접한 4개의 정사각형 중 1개로 끝납니다(같은 정사각형에 머물거나 대각선으로 이동할 수 없다고 가정).Vacuum World의 호는 인접한 모든 사각형에서 도달할 수 있기 때문에 양방향이며 상태 공간은 4개의 인접한 사각형 사이를 이동함으로써 루프에 진입할 수 있기 때문에 트리가 아닙니다.

상태 공간은 무한 또는 유한할 수 있으며 이산 또는 연속일 수 있습니다.

크기

특정 시스템의 상태 공간 크기는 가능한 [3]공간 구성 수입니다.

유한

상태 공간의 크기가 유한한 경우 상태 공간의 크기를 계산하는 것은 조합상의 문제입니다.[5]예를 들어, 8개의 여왕 퍼즐에서는 8개의 조각을 8x8 체스판에 놓는 모든 방법을 세어 상태 공간을 계산할 수 있습니다.이는 64개 세트에서 교체 없이 8개 위치를 선택하는 것과 같습니다.

이는 여왕의 법적 구성 수인 92보다 훨씬 많은 것입니다.많은 게임에서 유효 상태 공간은 도달 가능 상태 또는 법적 상태에 비해 작습니다.이 속성은 체스에서도 관찰됩니다. 체스에서는 유효 상태 공간이 게임 법적 움직임에 의해 도달할 수 있는 위치 집합입니다.이것은 사용 가능한 체스 피스 조합을 보드 위에 직접 배치함으로써 얻을 수 있는 일련의 위치보다 훨씬 작습니다.

인피니트

모든 연속 상태 공간은 대응하는 연속 함수에 의해 설명될 수 있으므로 [3]무한합니다.이산 상태 공간에는 시간 의존형 "카운터"[2] 시스템의 상태 공간 등의 무한 크기도 있을 수 있습니다.이는 라인 내의 고객 수를 정의하는 큐잉 이론의 시스템과 유사하며 상태 공간 {0, 1, 2, 3, ...}을 가질 수 있습니다.

탐색

주요 기사: 상태 공간 검색

상태 공간 탐색은 목표 상태를 찾기 위해 가능한 상태를 열거하는 프로세스입니다.예를 들어, 팩맨의 상태 공간은 모든 음식 알갱이를 먹을 때마다 목표 상태를 포함하고 팩맨을 보드 [6]주위로 이동시킴으로써 탐색됩니다.

검색 상태

탐색 상태는 상태 공간에서의 세계 상태를 압축하여 나타낸 것으로 탐색에 이용된다.상태 공간이 공간을 탐색하는 데 필요한 것보다 더 많은 정보를 인코딩하기 때문에 검색 상태가 사용됩니다.각 세계 상태를 탐색에 필요한 정보로만 압축하면 [6]검색 상태의 수를 줄임으로써 효율성이 향상됩니다.예를 들어, Pacman 공간의 상태에는 Pacman이 향하고 있는 방향(위, 아래, 왼쪽 또는 오른쪽)에 대한 정보가 포함됩니다.Pacman에서 방향을 변경하는 데 비용이 들지 않기 때문에 Pacman의 검색 상태는 이 정보를 포함하지 않고 Pacman이 마주할 수 있는 각 방향에 대해 1개씩 검색 공간의 크기를 4배 줄일 수 있습니다.

방법들

표준 검색 알고리즘은 이산 상태 공간을 탐색하는 데 효과적입니다.다음 알고리즘은 상태 [6][7]공간을 검색할 때 완전성과 최적성을 모두 보여 줍니다.

이러한 방법은 연속된 상태 공간을 탐색하는 것으로 자연스럽게 확장되지 않습니다.주어진 목표 상태를 찾기 위해 연속 상태 공간을 탐색하는 것은 항상 가능하지 않은 임의의 연속 함수를 최적화하는 것과 같습니다. 수학적 최적화를 참조하십시오.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Nykamp, Duane. "State space definition". Math Insights. Retrieved 17 November 2019.
  2. ^ a b Papernick, Norman. "Infinite States and Infinite State Transitions". Carnegie Mellon University. Retrieved 12 November 2019.
  3. ^ a b c Nykamp, Duane. "The idea of a dynamical system". Math Insights. Retrieved 12 November 2019.
  4. ^ Laubenbacher, R. Pareigis, B. (2001). "Equivalence Relations on Finite Dynamical Systems" (PDF). Advances in Applied Mathematics. 26 (3): 237–251. doi:10.1006/aama.2000.0717.
  5. ^ Zhang, Weixong (1999). State-space search: algorithms, complexity, extensions, and applications. Springer. ISBN 978-0-387-98832-0.
  6. ^ a b c Abbeel, Pieter. "Lecture 2: Uninformed Search". UC Berkeley CS188 Intro to AI. Retrieved 30 October 2019.
  7. ^ Abbeel, Pieter. "Lecture 3: Informed Search". UC Berkeley CS188 Intro to AI. Retrieved 12 November 2019.