[ Algorithm ] Maze problem - Using Online DFS Search

Question: 
在 AI 的範疇中, 當你的問題的 State space 是未知, 且每個 State 可以執行的 actions 也只有到那個 State 時才可以知道時, 這意味著你無法像 offline search 的問題一樣在正式開始解問題前先進行沙盤推演 (建立 search tree), 然後套用 search algorithm (DFS, BFS, A* etc) 找到最佳路徑. 而這類只能走一步算一步的問題我們歸類為 online search problem. 底下是更多有關 online search problem 的描述: 

Offline search algorithms compute a complete solution before setting foot in the real world and then execute the solution. In contrast, an online search agentinterleaves computation and action: first it takes an action, then it observes the environment and computes the next action. Online search is a good idea in dynamic or semidynamic domains - domains where there is a penalty for sitting around and computing too long. Online search is also helpful in nondeterministic domains because it allows the agent to focus its computational efforts on the contingencies that actually arise rather than those that might happen but probably won't. Of course, there is a tradeoff: the more an agent plans ahead, the less often it will find itself up the creek without a paddle.

當假設我們的問題是 deterministic 且 fully observable environment, 底下的訊息是已知: 
- ACTIONS(s) 

Which returns a list of actions allowed in state s.

- The step-cost function c(s,a,s') 

Note that this cannot be used until the agent knows the s' is the outcome.

- GOAL-TEST(s) 

Used to verify the goal state.

說到這裡我們可以發現 Maze(迷宮) 是不是很像一個 Online search 的的問題, 首先我們對迷宮一無所知 (Unknown state space), 走進去才知道每一步可以走的下一步有哪些 (Action(s) is known only for current state and passed states). 而底下我們要介紹 Online DFS Search 來解 Maze 問題. 考慮我們有下面的 Maze: 
 

Online DFS Agent: 
底下是 Online DFS Search 的 pseudo code, 該函數透過傳入一個當前的 State 來返回下一個可能的 Action. 並請把已經走過的 State 放到 unbacktracked 的堆疊中, 當走到死胡同時 (Dead end), 就把上一個 State 取回來 (Pop out unbacktracked) 並繼續該 State 尚未執行過的 Action(s). 而 untried 可以把它想成一個 Map 對應每個 State 與它尚未執行過的 Actions; 而 result 則是用來記錄走過的路徑: 
 

Coding and definition: 
在解任何 Search problem 之前要先定義幾個東西, 首先是 State Representation: 

這邊用 tuple (x,y) 來代表當前的位置或是 State. 在上面的 Maze 的問題中, Initial State 即是 (0,0); 而 Goal state 是 (4,3).

再來是 Actions: 

因為我們是二維的 Maze, 所以 Actions list 包含: UP,DOWN,LEFT,RIGHT 與 STOP. 通常走到 Goal state 或是沒路可以走時就返回 STOP.

接著是 Cost 的定義: 

這邊沒有做 Optimal 的需求, 所以就定義每 take 一個 Action 就 Cost unit 1.

最後剩下的就是 Coding 了... 首先我使用類別 Maze 來代表迷宮. 在建構子中傳入迷宮的長相 (int[][] mb), Initial State s 與 Goal state g: 

view plaincopy to clipboardprint?

1. package c4.maze;  
2.   
3. import java.util.LinkedList;  
4. import java.util.Queue;  
5.   
6. public class Maze {  
7.     public int[][] mazeBody; // 0 is obstacle, 1 is road  
8.     public State curState=null;  
9.     public State goalState=null;  
10.       
11.     public Maze(int[][] mb, State s, State g){this.mazeBody=mb; this.curState=s; this.goalState=g;}  
12.       
13.     public boolean move(){return false;}  
14.     public boolean goalTest(){return curState.equals(goalState);}  
15.     public boolean goalTest(State s){ return s.equals(goalState);}  
16.       
17.     public State result(Action a)  
18.     {  
19.         if(a.equals(Action.RIGHT)) curState.x++;  
20.         else if(a.equals(Action.LEFT)) curState.x--;  
21.         else if(a.equals(Action.UP)) curState.y++;  
22.         else if(a.equals(Action.DOWN)) curState.y--;  
23.         return curState;  
24.     }  
25.       
26.     public State result(State s, Action a)  
27.     {  
28.         State nextState = s.cloneself();  
29.         if(a.equals(Action.RIGHT)) nextState.x++;  
30.         else if(a.equals(Action.LEFT)) nextState.x--;  
31.         else if(a.equals(Action.UP)) nextState.y++;  
32.         else if(a.equals(Action.DOWN)) nextState.y--;  
33.         return nextState;  
34.     }  
35.       
36.     public Queue actions()  
37.     {  
38.         return actions(curState);  
39.     }  
40.       
41.     public Queue actions(State state)  
42.     {  
43.         Queue actions = new LinkedList();  
44.         int moveRight = state.x+1;  
45.         int moveLeft = state.x-1;  
46.         int moveDown = state.y-1;  
47.         int moveUp = state.y+1;  
48.         if(moveRight0) actions.add(Action.RIGHT);  
49.         if(moveLeft>=0 && mazeBody[moveLeft][state.y]>0) actions.add(Action.LEFT);  
50.         if(moveDown>=0 && mazeBody[state.x][moveDown]>0) actions.add(Action.DOWN);  
51.         if(moveUp0].length && mazeBody[state.x][moveUp]>0) actions.add(Action.UP);  
52.         System.out.printf("\t[Test] %s has %d actions...\n", state, actions.size());  
53.         return actions;  
54.     }  
55.       
56.     /** 
57.      * BD : Skip action which will lead you back to original state. 
58.      * @param src 
59.      * @param state 
60.      * @return 
61.      */  
62.     public Queue actions(Action prvAct, State state)  
63.     {  
64.         Queue actions = new LinkedList();  
65.         int moveRight = state.x+1;  
66.         int moveLeft = state.x-1;  
67.         int moveDown = state.y-1;  
68.         int moveUp = state.y+1;  
69.         if(moveUp0].length &&   
70.            mazeBody[state.x][moveUp]>0 &&   
71.            !Action.DOWN.equals(prvAct)) actions.add(Action.UP);  
72.         if(moveDown>=0 &&   
73.            mazeBody[state.x][moveDown]>0 &&   
74.            !Action.UP.equals(prvAct)) actions.add(Action.DOWN);  
75.         if(moveRight
76.            mazeBody[moveRight][state.y]>0 &&   
77.            !Action.LEFT.equals(prvAct)) actions.add(Action.RIGHT);  
78.         if(moveLeft>=0 &&   
79.            mazeBody[moveLeft][state.y]>0 &&   
80.            !Action.RIGHT.equals(prvAct)) actions.add(Action.LEFT);  
81.               
82.         System.out.printf("\t[Test] %s has %d actions...\n", state, actions.size());  
83.         return actions;  
84.     }  
85.       
86.     @Override  
87.     public String toString()  
88.     {  
89.         StringBuffer strBuf = new StringBuffer("");  
90.         for(int j=mazeBody[0].length-1; j>=0; j--)  
91.         {  
92.             for(int i=0; i
93.             {  
94.                 if(i==curState.x && j==curState.y) strBuf.append("S");  
95.                 else if(i==goalState.x && j==goalState.y) strBuf.append("G");  
96.                 else if(mazeBody[i][j]>0) strBuf.append("R");  
97.                 else strBuf.append("#");                  
98.             }  
99.             strBuf.append("\r\n");  
100.         }  
101.         return strBuf.toString();  
102.     }  
103. }  

這邊要特別說明的是函數 result(State s, Action a). 參數 s 是指當前的 State; 而參數 a 則是上一個 State 執行該 Action 來到當前的 State; 而返回的是當前的 State 可以執行的 Action(s), 從代碼中可以發現我把 Action 回將當前 State 帶回前一個 State 從返回可執行 Action 中移除, 為的是避免 loop 的發生. 接著是類別 State: 用來代表當前的狀態: 

view plaincopy to clipboardprint?

1. package c4.maze;  
2.   
3. public class State {  
4.     public int x=-1;  
5.     public int y=-1;  
6.       
7.       
8.     public State(int x, int y){this.x = x; this.y = y;}  
9.       
10.     @Override  
11.     public boolean equals(Object o)  
12.     {  
13.         if(o!=null && o instanceof State)  
14.         {  
15.             State s = (State)o;  
16.             if(s.x == x && s.y == y) return true;  
17.         }  
18.         return false;  
19.     }  
20.       
21.       
22.       
23.     public State cloneself(){return new State(x,y);}  
24.       
25.     @Override  
26.     public String toString()  
27.     {  
28.         return String.format("(%d,%d)", x,y);  
29.     }  
30. }  

接著還有列舉 Action, 用來表示移動的方向或是終止條件: 

view plaincopy to clipboardprint?

1. package c4.maze;  
2.   
3. public enum Action {  
4.     DOWN,UP,LEFT,RIGHT,STOP;  
5.       
6.     public Action Reverse()  
7.     {  
8.         if(this.equals(DOWN)) return UP;  
9.         else if(this.equals(UP)) return DOWN;  
10.         else if(this.equals(LEFT)) return RIGHT;  
11.         else if(this.equals(RIGHT)) return LEFT;  
12.         return null;  
13.     }  
14.       
15.     @Override  
16.     public String toString()  
17.     {  
18.         if(this.equals(DOWN)) return "Move Down";  
19.         else if(this.equals(UP)) return "Move Up";  
20.         else if(this.equals(LEFT)) return "Move Left";  
21.         else if(this.equals(RIGHT)) return "Move Right";  
22.         else if(this.equals(STOP)) return "Stop";  
23.         return "Unknown";  
24.     }  
25. }  

最後是 Online DFS Search 的實作, 使用類別 ODFSAgent 代表: 

view plaincopy to clipboardprint?

1. package c4.maze;  
2.   
3. import java.util.HashMap;  
4. import java.util.Queue;  
5. import java.util.Stack;  
6.   
7. /** 
8. * BD : Online DFS Agents 
9. * @author John 
10. * 
11. */  
12. public class ODFSAgent {  
13.     private Maze maze;  
14.     private State s=null;   // Previous state  
15.     private Action a=null;  // Previous action  
16.     private HashMap> untried= new HashMap>();  
17.     private Stack unbacktracked = new Stack();  
18.     private HashMap result = new HashMap();  
19.   
20.     public ODFSAgent(Maze m){maze = m;}  
21.       
22.       
23.     public Action odfs(State cs)  
24.     {  
25.         if(maze.goalTest()) return Action.STOP;  
26.         if(!untried.containsKey(cs)) untried.put(cs.x*100+cs.y, maze.actions(a, cs));  
27.         if(s!=null)  
28.         {  
29.             result.put(String.format("%s:%s", s,a), cs);  
30.             //cs = maze.result(s, a);  
31.             unbacktracked.add(s);  
32.         }  
33.         if(untried.get(cs.x*100+cs.y).isEmpty())  
34.         {  
35.             if(unbacktracked.isEmpty()) return Action.STOP;  
36.             else a = a.Reverse();             
37.         }  
38.         else  
39.         {  
40.             a = untried.get(cs.x*100+cs.y).poll();  
41.             System.out.printf("\t[Test] %s->%s\n", cs, a);  
42.         }  
43.         s = cs;  
44.         return a;  
45.     }  
46.       
47.     public void run() throws Exception  
48.     {  
49.         State is = maze.curState;  
50.         Action a = null;  
51.         do  
52.         {  
53.             a = odfs(is);           // Retrieve action based on current state  
54.             System.out.printf("\t[Info] %s...\n", a);             
55.             is = maze.result(a);    // Execute action and get result state.  
56.             System.out.printf("\t[Info] Maze:\n%s\n", maze);  
57.             Thread.sleep(1000);  
58.         }while(!a.equals(Action.STOP));  
59.     }  
60.       
61.     /** 
62.      * @param args 
63.      */  
64.     public static void main(String[] args) throws Exception{  
65.         State cs = new State(0,0);  
66.         State gs = new State(4,3);  
67.         int mb[][] = {{1,1,0,1},{1,0,0,1},{1,1,1,1},{1,0,0,0},{1,1,1,1}};  
68.         Maze maze = new Maze(mb, cs, gs);  
69.         System.out.printf("\t[Info] Maze:\n%s\n", maze);  
70.         ODFSAgent odfsAgent = new ODFSAgent(maze);  
71.         odfsAgent.run();  
72.     }  
73. }  

執行結果如下: 

...略...
[Test] (4,2) has 1 actions...
[Test] (4,2)->Move Up
[Info] Move Up...
[Info] Maze:
RRR#S
##R#R
R#R#R
RRRRR

[Info] Stop...
[Info] Maze:
RRR#S
##R#R
R#R#R
RRRRR

完整代碼可以在 這裡 下載.