Search Problems
Problem solving agent가 목표로의 동작을 산출하기 위해 에이전트가 수행하는 계산 과정
Uninformed Search Methods
깊이 우선 탐색 (Depth-First Search)
너비 우선 탐색 (Breadth-First Search)
균일 비용 탐색 (Uniform-Cost Search)
Reflex Agents
-
Choose action based on current percept (현재 인식 기반 행동 선택)
-
May have memory or a model of the world’s current state
-
Do not consider the future consequences of their actions (미래 결과 고려하지 않음)
-
Consider how the world IS
Can a reflex agent be rational?
반사 에이전트는 간단한 규칙 기반 시스템으로 주어진 상황에서 즉각적인 반응을 생성하는데 중점을 둡니다. 이러한 에이전트는 현재 상황에서 가장 적합한 동작을 선택하고 실제로 많은 문제에서 효과적일 수 있습니다. 그러나 몇 가지 제약사항이 있습니다:
제한된 상황: 반사 에이전트는 현재 상황만 고려하고, 과거 또는 미래 정보를 고려하지 않습니다. 따라서 환경이 매우 동적이거나 예측이 필요한 상황에서는 한계가 있을 수 있습니다.
제한된 문제 해결 능력: 반사 에이전트는 주어진 규칙에 따라 동작하므로 문제 해결 능력이 제한됩니다. 복잡한 문제나 추론을 필요로 하는 문제에 대해서는 효과적이지 않을 수 있습니다.
환경 변화에 취약: 환경이 빠르게 변할 때, 반사 에이전트는 이러한 변화에 대응하기 어려울 수 있습니다. 새로운 규칙을 추가하거나 기존 규칙을 변경하는 작업이 필요할 수 있습니다.
따라서 반사 에이전트는 간단하고 특정한 상황에서는 합리적인 선택을 할 수 있지만, 일반적인 정의에서 보면 합리적인 에이전트라고 보기 어려울 수 있습니다. 합리성은 주어진 목표를 달성하고 최선의 결과를 얻기 위한 지능적인 판단과 추론을 요구하는 개념입니다. 이런 면에서 반사 에이전트는 더 복잡한 문제 해결 능력을 가진 합리적인 에이전트와 비교하면 상대적으로 한계가 있습니다.
Planning agents
계획 에이전트는 주어진 상황에서 최적의 행동 계획을 수립하는 데 사용되는 컴퓨터 프로그램 또는 시스템입니다. 아래에서 각 항목을 자세히 설명하겠습니다:
"What If" 질문하기:
계획 에이전트는 "만약 이렇게 행동하면 어떻게 될까?"와 같은 "what if" 질문을 제기할 수 있습니다. 이것은 가능한 행동과 그에 따른 결과를 고려함으로써 미래 상황을 시뮬레이션하는 것을 의미합니다.
행동의 가상 결과에 기반한 결정:
계획 에이전트는 다양한 행동을 시도하고, 각 행동의 가상 결과를 고려하여 최선의 선택을 내립니다. 이를 통해 미래에 발생할 수 있는 다양한 시나리오를 고려하고 최적의 행동을 결정합니다.
세계가 행동에 대한 반응을 모델화:
계획 에이전트는 세계가 어떻게 작동하는지에 대한 모델을 가져야 합니다. 이 모델은 행동이 취해질 때 세계가 어떻게 변화하는지를 설명합니다.
목표(테스트) 설정:
계획 에이전트는 달성하고자 하는 목표를 명확하게 설정해야 합니다. 이 목표를 달성하기 위한 최적의 행동 계획을 수립합니다.
세계가 어떻게 될 것인지 고려:
계획 에이전트는 현재 상황에서 어떤 행동을 취할지 결정하기 위해 세계가 어떻게 변화할 것인지 고려합니다. 이를 통해 미래의 상태를 예측하고 최적의 행동을 선택합니다.
최적 vs. 완전한 계획:
최적의 계획은 목표를 가장 효율적으로 달성하는 계획을 의미합니다. 그러나 최적의 계획을 찾는 것은 계산적으로 매우 어려울 수 있습니다. 완전한 계획은 가능한 모든 행동 시나리오를 고려하여 답을 찾는 것을 의미합니다.
계획 vs. 재계획:
계획 에이전트는 초기 계획을 세울 때와 실제 행동 중에 상황이 변경할 때 재계획을 수행할 수 있습니다. 재계획은 새로운 정보나 변화된 조건을 고려하여 행동 계획을 조정하는 것을 의미합니다.
계획 에이전트는 다양한 응용 분야에서 사용됩니다. 예를 들어 로봇 제어, 자율 주행 자동차, 게임 AI, 비즈니스 의사 결정, 및 자원 할당 등 다양한 분야에서 계획 에이전트가 활용됩니다.
Example: Traveling in Romania
• State space:
▪ Cities
• Successor function:
▪ Roads: Go to adjacent city with cost = distance
• Start state:
▪ Arad
• Goal test:
▪ Is state == Bucharest?
• Solution?
What’s in a State Space?
16
COSE361 Artificial Intelligence:
Search
The world state includes every last detail of the environment
• Problem: Pathing
▪ States: (x,y) location
▪ Actions: NSEW
▪ Successor: update
location only
▪ Goal test: is (x,y)=END
• Problem: Eat-All-Dots
▪ States: {(x,y), dot booleans}
▪ Actions: NSEW
▪ Successor: update location
and possibly a dot boolean
▪ Goal test: dots all false
State Space Sizes? • World state: ▪ Agent positions: 120 ▪ Food count: 30 ▪ Ghost positions: 12 ▪ Agent facing: NSEW • How many ▪ World states?
120x(230)x(12
2)x4
▪ States for pathing?
120
▪ States for eat
-all
-dots?
120x(230
)
Quiz: Safe Passage
• Problem: eat all dots while keeping the ghosts perma-scared
• What does the state space have to specify?
▪ (agent position, dot booleans, power pellet booleans, remaining scared time)
State Space Graphs and Search Trees
19
COSE361 Artificial Intelligence:
Search
State Space Graphs • space graph: A mathematical
representation of a search problem ▪ Nodes are (abstracted) world configurations ▪ Arcs represent successors (action results) ▪ The goal test is a set of goal nodes (maybe only
one)
• In a state space graph, each state occurs
only once!
• We can rarely build this full graph in
memory (it’s too big), but it’s a useful
idea
State Space Graphs
• space graph: A mathematical
representation of a search problem
▪ Nodes are (abstracted) world configurations
▪ Arcs represent successors (action results)
▪ The goal test is a set of goal nodes (maybe only
one)
• In a state space graph, each state occurs
only once!
• We can rarely build this full graph in
memory (it’s too big), but it’s a useful
idea
21
COSE361 Artif
