[인공지능] 인공지능 문제 정의

탐색 (Search)

 

방대한 데이터에서 목적에 맞는 데이터를 찾아내기 위한 과정

 

• 하노이 타워
• 경로 찾기
• 8-puzzle
• 틱택토
• ...

하노이 타워 경로 찾기

8-puzzle tic tac toe

 

에이전트 (agent)

 

특정 환경 (environment) 내에 위치하여, 설계된 목적 (objectives) 을 만족 시키기 위하여, 자율적 (autonomous) 으로 유연하게 (flexible) 행동할 능력이 있는 컴퓨터 시스템

 

인공지능에서의 문제 풀이의 주체

 

지능형 에이전트는 센서로부터 인지된 주변 환경을 인지 (Perception) 하고 효과기 (actuator) 를 통해 외부환경에 적절한 행동을 취할 수 있는 로봇 / 기계 / 소프트웨어

 

에이전트의 종류

• Rational Agents (Rule base)
  • "Do right thing."
  • 그냥 옳은 행동만을 하는 에이전트
• Simple Reflex Agents (Rule base)
  • 당장의 정해진 규칙에 의해서 행동, 경험을 활용하지 않음
  • 단순 반응 에이전트
• Model based Relfex Agents
  • 특정 상황에서 수행되는 행동의 영향력을 이해하고 환경을 모델링
  • 환경을 모델링하여 그 모델에 맞춰서 행동하는 에이전트
• Goal based Agents
  • 행동을 실행하기 이전에 목적에 부합하는지를 고려하는 에이전트
  • 결과 위주
• Utility based Agents
  • 과정을 중시할 수 있는, 즉 효율성을 추구하는 에이전트
  • 과정 위주

Q. 8-puzzle에서 에이전트의 개수는 몇일까?

A. 1

 

Q. 틱택토에서 에이전트의 개수는 몇일까?

A. 2

 

상태 (State)

 

시스템이나 환경의 조건이나 상황

• 다양한 형태의 자료구조 (symbol string, vector, 2-D array, tree, list) 를 사용하여 문제의 상태를 표현할 수 있습니다.

초기 상태

• 시스템이나 환경에서 에이전트가 시작하는 상태

목표 상태

• 시스템이나 환경에서 에이전트가 찾고자 하는 최종적인 상태

 

행동 (Actions)

 

특정 상태에서 취할 수 있는 모든 동작

 

함수 Actions(s)는 상태 s에서 취할 수 있는 모든 동작들의 집합을 반환

Actions()

 

그렇다면 상태와 행동을 어떻게 연결시킬 수 있을까?

 

연산자 (operator)

 

상태 간의 전이를 정의하는 모델

• 임의 상태에서 임의 행동을 했을 때 어떤 상태에 도달하는지를 나타내는 모델

함수 Result(s, a)는 상태 s에서 행동 a를 취했을 때 전이된 상태를 반환

Result()

 

연산자를 통해 에이전트는 어떤 상태들에 도달할 수 있을까?

 

상태 공간 (state space)

 

초기 상태와 목표 상태를 포함하여 임의의 상태로부터 연산자를 통해 생성 가능한 모든 상태들의 집합

 

Q. 하노이 타워 환경에서 에이전트가 도달할 수 있는 상태의 개수는?

A: (규칙 상관하지 않을 때) 3^3 = 27

 

상태 공간의 구성 요소

• 상태 묘사 형태: 행동 적용이 용이한 상태 묘사 방식을 선택
  • 큰 원판부터 작은 원판까지의 위치를 list로 표현
• 초기 상태와 목표 상태, 연산자에 대한 묘사
• 행동의 종류

 

상태 공간의 표현을 더 간소화 할 수 있을까?

abstracting the Tower of Hanoi

 

상태 공간의 간소화

 

그래프 (graph) 표현

• 노드 (node)
  • 특정 상태를 표현
• 엣지 (edge)
  • 특정 행동을 표현

 

상태 공간 탐색

• 상태 공간에서의 문제 풀이는 초기 상태에서 시작하여 목표 상태에 도달할 수 있는 일련의 행동들을 찾는 것
• 그래프에서 이에 대응하는 경로를 찾는 문제와 동일

 

탐색 종료 판단

 

주어진 상태가 종료 상태인지 확인

• 종료 상태는 목표 상태가 될 수 있고 아닐 수도 있다.
• 예: 틱택토

종료 상태

 

에이전트가 목표 상태에 도달할 수 있는 여러 방법들 중 어떤 방법이 가장 좋은 방법인가?

 

경로 비용 (path cost)

 

초기 상태에서 목표 상태로 가는 행동들의 비용

• 거리가 가장 짧은 경로를 추천

 

탐색 문제

 

인공지능에서의 문제

• 초기 상태, 목표 상태 및 연산자로 기술 가능해야 됨
• 초기 상태에 연산자를 적용하여 그 상태를 변화시키는 상태 공간 탐색에 의해 목표 상태를 발견하는 과정

탐색 (search)

• 시행착오적 (trial and error) 방법에 의한 문제 해결 방법
• 수많은 해 (solution) 들이 놓인 공간에서, 이중 하나의 해를 찾음으로써 문제를 푸는 방법

 

예제

• 선교사 식인종 문제
• 외판원 문제