Solving Problems by Searching

Introduction

  • 皆下來將談論 Goal-based agent 的一種型態 : Problem-solving agent

  • 而環境也會設定在一般的 PEAS

    • 也就是 actions 永遠為 fixed sequence

Problem-Solving Agents

  • Problem-Solving agent 被設計為 "Formulate, search, execute"

  • Search : 找出一系列 actions 來完成 goal

    • Search algorithm 會把 problem 當成 input，然後 output 出 solution

  • Execution : 執行由這些 solution 產生的 actions

Formulation

Formulate 也是一大關鍵，要能夠把問題很好的呈現出來

一個問題可以用五大元件表達 :

  • Initial state

    • State 的最初狀態

  • Actions

    • 可以實現的所有動作

  • Transition model

    • 每個動作的描述與結果 (做了某 action 會發生什麼)

  • Goal test

    • 查看 State 是否為 Goal state

  • Path cost

    • 計算每個動作的成本

  • Solution = 一系列的 actions 讓我們從 init state 走到 goal state

  • Solution quality = 由 past cost function 來計算

Example

Find path to a destination

  • init: 起始位子

  • action: 可以往哪幾個節點走

  • transition model: 往 X 走之後會發生什麼 ?

  • goal test: 是否到了終點

  • path cost: 每個節點的距離

8-puzzle problem

  • 要讓左邊的棋盤變成右邊的棋盤

    • state: 每個回合棋盤的樣子

    • init: 棋盤的起始樣子

    • action: 空格往哪個方向移動

    • transition model: 移動完後新的棋盤長什麼樣子

    • goal test: 棋盤是否已經變成終點的樣子了

    • path cost: 每次移動 cost 1

8-queens problem

  • 要讓棋盤上的八個 queen 不會互相攻擊 (同一列、行、斜線都會攻擊)

    • state: 任何 8 個 queen 在棋盤的樣子

    • init: 每有任何 queen 在棋盤

    • action: 加入 queen 到棋盤

    • transition model: 加入後新的棋盤的樣子

    • goal test: 測試 8 個 queen 沒有互相攻擊

Real world problem

  • Touring problem

  • TSP

  • VLSI layout

  • Robot navigation

Infrastructure for Searching Algorithms

  • 我們用樹的運作來定義一個 search algorithm

    • 其中 branches 是 actions

    • 而 nodes 是 states

  • 而每個 node (n) 有幾個屬性 :

    • n.state

    • n.parent

    • n.action

    • n.path-cost

  • 我們也可以透過幾個尺度來測量 searching algorithm 的好壞 :

    • Completeness : 一定能找到一個解嗎

    • Optimality : 是否找到最佳解

    • Time complexity : 多久找到解

    • Space complexity : 花多少 memory 才找到解

而 Searching algorithm 可以分為 uninformed 以及 informed

Uninformed Search Strategies

  • 又稱 blind search

  • 每個 state 之後生成新的 states

  • 並且利用 goal test 來驗證新的 state 是否為 goal state

  • 他不會知道 non-goal state 彼此間到底誰好

  • 如果知道的話就是 informed search (heuristic search)

Breadth-first search (BFS)

  1. expand root node

  2. expand all its successors

  3. then their successors

  • 考慮每個節點都有 b 個 successors

  • 受到深度 (depth) 影響非常大

  • 第一層要跑 b 個 nodes, 下一層要跑 b^2 個 nodes, 再下一層 b^3 ...

  • 他的複雜度為

    b+b2+b3+⋯+bd=O(bd)b+b^2+b^3+\cdots+b^d = \mathcal{O}(b^d)

Uniform-cost search

  1. expand 會優先選擇 lowest path cost 的 node

    • 由 priority queue 來實作

  2. 接著會對該 node 進行 goal test

    • test 是為了避免有更好的 path 可以走

  3. 通常可以得到 optimal solution

  4. 因為不受 depth 影響而是考慮 path cost

  5. 複雜度為

    O(b1+⌊C∗/ϵ⌋)\mathcal{O}(b^{1+\left \lfloor C*/\epsilon \right \rfloor})

  6. 若所有的 path cost 都一樣，那就會像 BFS

舉個例子 :

  1. 走到 S

    • 此時 queue = [S], 並且找到 RV[80], E[99]

  2. 我們選擇 RV

    • 此時 queue = [S, RV], 並且找到 E[99], P[80+97]

  3. 我們選擇 E

    • 此時 queue = [S, RV, E], 並且找到 P[80+97], B[99+211]

  4. 我們選擇 P

    • 此時 queue = [S, RV, E, P], 並且更新 B，因為 B[80+97+101] 小於 B[99+211]

  5. 我們選擇 B

    • 此時找到終點 B 為 S -> RV -> P -> B [80+97+101]

Depth-first search (DFS)

  • expand 同一條路徑 (frontier) 上直到找到最深 (deepest) 的 node

  • 時間複雜度為 (m 有可能遠大於 d)

    O(bm)∣m=maximum depth of any node\mathcal{O}(b^m) \mid m = \text{maximum depth of any node}

  • DFS 一次只需儲存同一條路上的點，空間複雜度為

    O(bm)\mathcal{O}(bm)

Depth-limited search

  • 在 DFS 基礎上加入 limit (ℓ)

  • Incompleteness

  • Nonoptimal

  • 這個 limit 可以由有 domain-knowledge 的人來設計

Iterative deepening DFS

  • 逐步增加 limit 直到找到 goal 為止

  • 有 DFS 省空間的好處、也有 BFS completeness 的好處

  • 通常用於 search space 很大時，或是 solution 是 unknown 的

  • 看起來很浪費 Time complexity ，但其實 bound 在 最後一層

Bidirectional search

  • 同時從終點及起點開始演算法

  • 若在中間點交集，代表找到最佳解

  • Motivation 是

    bd/2+bd/2<bdb^{d/2}+b^{d/2} < b^d

  • 但如何從背後 search 回來是一大難題

  • path-finding & 8-puzzle 還可以實作

  • 但 8-queen 這類題目是無法實作的

Informed (Heuristic) Search Strategies

  • Infromed search 會加入一些 domain-knowledge 進來

    • 可以幫助 algorithm 更快解出 solution

  • 代表的算法為 best-first search

    • 藉由 evaluation function f(n) 來算出下一個 node

      • f(n) 會透過 search strategy 來挑選

    • 大部分的 search algorithm 會有 heuristic function h(n)

      • h(n) 通常評估從 node n 到 goal state 的 cheapest path cost 為何

    • 有可能 f > h , 也有可能 f = h

Greedy best-first search

  • 以 path-finding 為例，直線最接近終點的 node 應該可以更快找到 solution

  • 所以 h(n) = n 到終點的直線距離 (domain knowledge)

  • 而 path-finding 的 h(n) = f(n)

  • 因為會直接使用 h(n) 尋找下一個最接近終點的 node

    • 所以 search cost is minimal

    • 但不見得是 optimal

    • 也像 DFS 一樣是 incomplete

  • 更好的 heuristic 可以讓算法效率更高

A* Search

  • 最有名的 best-first search

  • 他會把 path cost g(n) 和 heuristic h(n) 結合在一起

    f(n)=g(n)+h(n)f(n) = g(n) + h(n)

  • 要求 h(n) 能夠符合 admissibility

    • admissibility 代表永遠不會 overestimate cost to goal

      • Straight line distance 就有符合 admissibility

  • 要求 consistency

    • n 的 goal cost 永遠不會大於他的 successor n'

      h(n)≤c(n,a,n′)+h(n′)h(n) \le c(n,a,n') + h(n')

  • 用 path-finding 舉例 :

    • heuristic = straight line distance

    • path cost = to next city distance

PreviousIntelligent AgentsNextBeyond Classical Search

Last updated