## 2012年10月21日 星期日

### [ Algorithm ] Maze problem - Using Online DFS Search

Question:

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.

- 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.

Online DFS Agent:

Coding and definition:

1. package c4.maze;
2.
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;
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 &&
72.         if(moveDown>=0 &&
73.            mazeBody[state.x][moveDown]>0 &&
75.         if(moveRight
76.            mazeBody[moveRight][state.y]>0 &&
78.         if(moveLeft>=0 &&
79.            mazeBody[moveLeft][state.y]>0 &&
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. }

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. }

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. }

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);
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);
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

## 關於我自己

Where there is a will, there is a way!