[인공지능] Chapter 2. Search

Agent

• Reflex agents
  • Current percept 기반 행동
  • 행동의 결과를 고려하지 않음
  • Consider how the world IS
• Planning agents
  • 행동의 결과를 고려
  • Consider how the world WOULD BE

Search Problems

• Consist of
  • A state space
    • 모든 가능한 상태들의 집합
  • A successor function
    • 현재 상태를 기반으로 다음 상태 및 비용을 연산하는 함수
  • A start state
    • 초기상태
  • A goal test
    • 주어진 상태가 목적 상태인지 확인하는 함수
• Solution
  • start state를 goal state로 바꾸는 sequence of actions

 

State space Graphs

• A mathmatical representation ofa search problem
  • Nodes: (abstracted) world configurations
  • Arcs: successors (action result)
  • The goal test: a set of goal nodes
• 각각의 상태는 오로지 한 번 나타남
• full 그래프를 그리기 힘들지만, 그리면 useful

 

Search Trees

• A ‘what if’ tree of plans and their outcoms
• The start state is the root node
• Children: successors
• Nodes show states, but correspond to PLANS that achieve those states
• 대부분의 경우, 전체 트리를 실제로 그릴 수 없다.

• Searching with a Search Tree
  • Expand out potential plans (nodes)
  • Maintain a fringe of partial plans under consideration
  • Try to expand as few tree nodes as possible

 

SSG ↔ ST

• ST에서 각각의 노드는 SSG에서 an entire PATH를 의미
• 필요에 따라 그래프를 그리지만, 가능한 적게 그리는 것이 좋다
• Size
  • SSG < ST
  • Lots of repeated structure in the search tree

General tree search

• Important ideas
  • Fringe
  • Expansion
  • Exploration strategy
• Main question
  • Which fringe nodes to explore?

Uninformed search

• Depth-first search (DFS)
• Breadth-first search (BFS)
• Uniform cost search (UCS)

Depth-First Serch

• Strategy
  • expand a deepest node first
• Implementation
  • Fringe is a LIFO stack
• Complete
  • Guaranteed to find a solution if one exists?
• Optimal
  • Guaranteed to find the least cost path?
• What nodes DFS expand?
  • Some left prefix of the tree
  • Could process the wole tree
• How much space does the fringe take?
  • Only has siblings on path or roots
• Is it complete?
  • the tiers could bo infinite, so only if we prevent cycles
• Is it optimal?
  • No
  • it finds the ‘leftmost’solution, regardless of depth or cost

Breadth-First Search

• Strategy
  • 가장 얕은 노드부터 expand
• Implementation
  • Fringe is a FIFO queue
• What nodes does BFS expand?
  • Processes all nodes above shallowest solution
  • Let depth of shallowest solution be s
  • Search takes time O(bs)
• How much space does the fringe takes?
  • Has roughly the last tier
• Is it complete?
  • s must be finite if a solution exists, so yes!
• Is it optimal?
  • Only if costs are all 1 (more on costs later)

Iterative Deepening

• Idea
  • DFS’s space advantage + BFS’s time advantage
  • Run a DFS with dept limit 1→ (If no solution) Run DFS with depth limit 3 …
  • → (If no solution) Run DFS with depth limit 2
• Isn’t that wastefully redundant?
  • Generally most work happens in the lowest level searched, so not so bad

Cost-Sensitive Search

BFS finds the shortest path in terms of number of actions. It does not find the least-cost path. We will now cover a similar algorithm which finds the least-cost path

Uniform Cost Search

• Strategy
  • expand a cheapest node first
  • Fringe is priority queue (priority: cumulative cost)
• What nodes does UCS expand?
  • Processes all nodes with cost less than cheapest solution
  • If that solution costs C* and arc cost at lest E then the ‘effective depth’ is roughly C*/e
• How much space does the fringe take
  • Has roughly the last tier
• Is it complete?
  • Assuming best solution has a finite cost and minimum arc cost is positive, yes!
• Is it optimal
  • Yes!

<DFS, BFS, UCS 비교>

	DFS	BFS	UCS
strategy	expand a deepest node first	가장 얕은 노드부터 expand	• expand a cheapest node first • Fringe is priority queue (priority: cumulative cost)
implementation	Fringe is a LIFO stack	Fringe is a FIFO queue
expand nodes	• Some left prefix of the tree • Could process the wole tree	• Processes all nodes above shallowest solution • Let depth of shallowest solution be s • Search takes time O(bs)	• Processes all nodes with cost less than cheapest solution • If that solution costs C* and arc cost at lest E then the ‘effective depth’ is roughly C*/e
complete	the tiers could bo infinite, so only if we prevent cycles	s must be finite if a solution exists, so yes!	Assuming best solution has a finite cost and minimum arc cost is positive, yes!
optimal	• No • it finds the ‘leftmost’solution, regardless of depth or cost	Only if costs are all 1 (more on costs later)	Yes!
issues			UCS explores increasing cost contours
pros			complete and optimal
cons			• explores optins in every direction • No information about goal location