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同時在棋盤上,但是沒有任何兩子會處於可以吃掉對方的位子
沒有留言:
張貼留言