AI 筆記4 - Search Agents & Problem Formulation

Goal-based （Search) agents

goal-based agent透過找到goal的state to state path，解決問題。找尋通往goal的path，可以被formalize成一個search problem。

所有可能的states(不一定能到達goal) 組成一個search space，就像下圖中所有可能抵達中心的路徑：

Search Space

search space有點類似sample space，也就是所有可能的states的集合。以8-queens來說，search space總共有64*63*... * 56種可能的8個queen放置在棋盤的方法（也就是這8個queen組成一個棋盤的screenshot state)。

goal-based agent只要找出其中一個goal state即算是solve the problem。

Solve Search Problem的步驟

1. formulate problem:

• 定義initial state為何？
• 定義所有state space ，就是initial state透過action sequence能夠抵達的其他states
• 定義action space，也就是所有的state能做的actions
• 定義transition model，也就是state A經過某個action map到哪一個state 
• 定義goal test
• 定義path cost

2. formulate goal
3. calculate solution (offline): 先算好在行動，所以基本上有environment overview
4. execute solution

8-queens Problem Formulation 範例

state：0~8個queens 在棋盤上的位置。
state space: 所有state的可能排列組合。
initial state: 這個就是0個queens的state，也就是棋盤是空的。
actions: 在棋盤空格加上一個queen
transition model: action會讓棋盤的state自然的改變
goal test: 8個queen同時在棋盤上，但是沒有任何兩子會處於可以吃掉對方的位子

Routing Problem Formulation範例

懶得打字，上圖比較快！