[AI/Concepts] Agent and Search

에이전트

첫주차에서 다뤘던 개념인 에이전트에 대해 살펴보자.

• 에이전트는 액추에이터와 센서를 통해 환경에 맞춰 행동을 한다.
  • 에이전트 함수는 모든 상황에서 에이전트가 무엇을 할지를 설명합니다.
    • 지각 기록을 사용할수도 안할 수도 있다.
  • 에이전트 프로그램(Agent Program)은 에이전트 함수를 물리적 구조(Architecture) 위에서 구현하여 실제로 동작하게 한다.
• 성과 측정은 환경의 상태 변화를 평가하는 데 사용됩니다.
• 완벽한 합리적인 에이전트는 기대되는 성과를 최대화합니다.

어떻게 하면 에이전트를 효과적으로 설계할 수 있을까?

 

일단 PEAS 프레임워크를 이용하면 에이전트를 설계 기준을 명확히 할 수 있다.

• Performance : 에이전트의 성공을 평가하는 기준 (예: 안전성, 시간, 수익성)
• Environment : 에이전트가 동작하는 주변 조건 (예: 도로, 보행자)
• Actuators : 에이전트가 환경에 영향을 미치는 수단 (예: 조향 장치, 브레이크)
• Sensor : 에이전트가 환경을 인식하는 수단 (예: 카메라, GPS)

 

에이전트는 Enviorment와 상호작용하기 때문에 작업 환경을 명확히 정의 해야 한다. 이를 위해 작업 환경의 특성을 분류해보자.

1. 완전 관찰 가능(Fully Observable) vs. 부분 관찰 가능(Partially Observable)
   • 완전 관찰 가능: 에이전트가 환경의 모든 상태를 완전히 인식할 수 있음.
   • 부분 관찰 가능: 에이전트가 환경의 일부만 인식할 수 있음. 예를 들어, 차량의 전방 카메라로 모든 것을 판단해야 하는 경우.
2. 결정론적(Deterministic) vs. 확률적(Stochastic)
   • 결정론적: 행동의 결과가 확실함. 체스에서 말의 이동이 이에 해당.
   • 확률적: 행동의 결과에 불확실성이 존재함. 예를 들어, 주사위 게임에서 결과가 랜덤하게 결정됨.
3. 에피소드형(Episodic) vs. 연속형(Sequential)
   • 에피소드형: 각 행동이 독립적이며, 과거의 행동이 현재에 영향을 미치지 않음.
   • 연속형: 과거의 행동이 현재와 미래의 행동에 영향을 미침.
4. 정적(Static) vs. 동적(Dynamic)
   • 정적: 환경이 에이전트의 행동과 무관하게 변하지 않음.
   • 동적: 환경이 에이전트의 행동에 따라 변함.
5. 이산(Discrete) vs. 연속(Continuous)
   • 이산: 상태와 행동이 명확히 구분됨. 체스의 각 칸 이동 등이 이에 해당.
   • 연속: 상태와 행동이 연속적인 값을 가짐. 예를 들어, 자동차의 위치와 속도는 연속적임.
6. 단일 에이전트(Single-Agent) vs. 다중 에이전트(Multi-Agent)
   • 단일 에이전트: 한 명의 에이전트만 환경과 상호작용.
   • 다중 에이전트: 여러 에이전트가 동시에 환경과 상호작용.

 

이러한 환경의 복잡성과 특성에 따라 적합한 에이전트 유형을 선택해야 한다.

 

가장 기본적인 에이전트는 테이블 기반 에이전트인데, 모든 상태를 테이블에 기록해놓는게 사실 매우 비효율적이고 실용적이지 않다. AI의 주요 도전 과제는 심플하게 문제 정의를 하는게 key challenge다.

 

이렇게 해서 나온게 아래 나와있는 에이전트 유형이다.

1. 단순 반사형 에이전트(Simple Reflex Agents)
   • 현재의 지각에만 기반하여 행동을 선택하고, 과거의 지각 기록을 무시합니다.
   • 예: 간단한 룰에 따라 행동하는 진공 청소기.
2. ⠀모델 기반 반사형 에이전트(Model-Based Reflex Agents)
   • 일부 내부 상태를 유지하여, 과거의 지각을 반영합니다.
   • 예: 장애물을 피하기 위해 과거의 정보를 활용하는 로봇.
3. ⠀목표 기반 에이전트(Goal-Based Agents)
   • 특정 목표를 달성하기 위해 행동을 선택합니다.
   • 예: 목적지까지의 최적 경로를 찾는 내비게이션 시스템.
4. ⠀기타 다양한 유형
   • 학습 기반 에이전트(Learning Agents) 등.

 

에이전트 유형을 정했다면, 이제 에이전트가 문제를 해결하는 과정에 대해 살펴보자.

문제 해결 에이전트는 문제 해결을 위해 다음과 같은 과정을 거친다.

1. 목표 설정 (Goal Formulation)
   • 에이전트의 목표를 명확히 정의하여 행동 범위를 제한합니다.
2. 문제 설정 (Problem Formulation)
   • 문제를 해결하기 위해 고려해야 할 행동과 상태를 결정합니다.
3. 탐색 (Search)
   • 상태 공간(State Space)에서 목표 상태로 가는 행동 순서를 찾습니다.
4. 실행 (Execution)
   • 탐색을 통해 얻은 솔루션을 하나씩 실행합니다.

결국 문제 해결은 탐색을 통해 이루어지며, 이는 상태 공간에서 목표 상태로 가는 경로(행동의 순서)를 찾는 것이다.

 

⠀탐색 문제(Search Problems)는 다음의 요소로 구성됩니다:

• 상태(State): 에이전트와 환경의 구성 상태.
• 초기 상태(Initial State): 에이전트가 시작하는 상태.
• 행동(Actions): 상태에서 선택할 수 있는 행동들.
• 전이 모델(Transition Model): 행동을 수행했을 때 상태가 어떻게 변화하는지.
• 목표 테스트(Goal Test): 주어진 상태가 목표 상태인지 판단하는 방법.
• 경로 비용(Path Cost): 초기 상태에서 목표 상태로 가는 경로의 총 비용.

이를 토대로 탐색 전략을 살펴보자

 

1. 정보가 없는 탐색 전략 (Uninformed Search Strategies)
사전 정보 없이 정해진 순서에 따라 탐색을 수행하는 전략입니다.

• 너비 우선 탐색(Breadth-First Search, BFS)
  • 완전성: 예. 모든 가능한 상태를 탐색.
  • 최적성: 예. 가장 낮은 경로 비용을 보장.
  • 단점: 공간 복잡성이 높아 메모리 사용량이 큼.
• 깊이 우선 탐색(Depth-First Search, DFS)
  • 완전성: 아니오. 무한 깊이에서 실패할 수 있음.
  • 최적성: 아니오.
  • 장점: 메모리 사용량이 적음.
• 깊이 제한 탐색(Depth-Limited Search)
  • DFS의 한계를 보완하기 위해 깊이에 제한을 둔 탐색.
• 반복 깊이 탐색(Iterative-Deepening Search)
  • BFS와 DFS의 장점을 결합한 탐색 전략.
    무한 루프에 빠질 수 있는 가능성을 방지하기 위해 탐색된 노드 집합(Explored Set)을 유지하는 것이 중요하다.

 

2. 정보 기반 탐색 전략 (Informed Search Strategies)

각 노드에 대해 평가 함수(Heuristic Function)를 사용하여 더 바람직한 노드를 우선적으로 탐색합니다. 휴리스틱 함수는 최단 경로 비용을 추정한다.

• 탐욕 탐색(Greedy Search)
  • 목표 상태에 가장 가까워 보이는 노드를 우선적으로 탐색. (lowest h(n))
  • 완전성: 아니오. 반복 루프에 빠질 수 있음.
  • 최적성: 아니오.
• A* 탐색(A* Search)
  • 평가 함수 f(n) = g(n) + h(n)를 사용하여 현재까지의 실제 비용(g(n))과 목표 상태까지의 예상 비용(h(n))을 합산.
  • 완전성: 예. 적절한 휴리스틱을 사용할 경우.
  • 최적성: 예. 허용 가능한 휴리스틱을 사용할 경우.
  • 장점: 최적 경로를 보장하면서도 효율적으로 탐색.