code

2017年1月25日 星期三

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範例

懶得打字,上圖比較快!




沒有留言:

張貼留言