2012年10月22日 星期一

[ Algorithm ] Maze problem - Using Online LRTA*

Question: 
考慮我們有下面的 Maze: 
 

目的是從 Initial State S 走道 Goal State G. 在 Maze problem - Using Online DFS Search 我們已經知道這是一個 Online Search Problem. 因此底下要介紹另一個 Online local search 的演算法 LRGA*: 透過更新 H(s) 來學習並找到通往 Goal State 的路徑. 

LRTA* : 
LRTA* 指的是 Learning Real-Time A* 的縮寫, 它跟 A* 一樣都有個 H(s) (對比 A* 的 h(s)), 不一樣的是這個 H(s) 會隨著 State 的 transition 自己更新: 
1. 當某個 State s 走到下個 State s', 且 s' 沒有出現過在 H(s') 時, 則使用 A* 的 h(s').
2. 當某個 State s 走到下個 State s' 時 (H(s') 須為已知!), 則原先的 H(s) 會被更新成 c(s,a,s')+H(s')
3. c(s,a,s') 指的是 State s take action a 到下個 State s' 所花的 cost.
4. 在每次的 State transition 會先從當前 State 挑選未執行過 action
5. 在每次的 State transition, 如果當前 State 可以執行的 actions 都執行過, 則選擇下一個 State s' 有最小的 H(s')

該演算法的 Pseudo code 如下: 
 

看完說明與 Pseudo code 還有有點昏? 我也是 ><", 接著來看範例. 考慮有 State transition 與 對應 H(S) mapping 如下 (深色的圓 是 current state): 
 

每個圓圈內的數字是該 State 對應的 H(s), 而目前的 State 是在從左邊數過來第 3 個圓圈. 
- (a)->(b) 
在 (a) 時, 往右邊的 State 移動會有最小的 H(s')=2. 故往右邊移動並更新 H(s)=c(s,move right,s') + H(s')=1+2=3

- (b)->(c) 
在 (b) 時, 往左邊的 State 移動會有最小的 H(s')=3. 故往左邊移動並更新 H(s)=c(s,move left,s') + H(s')=1+3=4

- (c)->(d) 
在 (c) 時, 往右邊的 State 移動會有最小的 H(s')=4. 故往右邊移動並更新 H(s)=c(s,move left,s') + H(s')=1+4=5

- (d)->(e) 
在 (d) 時, 往右邊的 State 移動會有最小的 H(s')=4. 故往右邊移動並更新 H(s)=c(s,move left,s') + H(s')=1+4=5

如此原先在 (a) 的 State 透過 update H(s) 便從原先的 local minimum 脫離而朝 global minimum 移動. 

Coding and definition: 
詳細的 State Representation 與 Actions 定義可以參考 Maze problem - Using Online DFS Search, 而對應 LRTA* 的實作我使用類別 LRTAAgent 來當作解 maze problem 的 Agent: 
  1. package c4.maze;  
  2.   
  3. import java.util.HashMap;  
  4. import java.util.Iterator;  
  5. import java.util.Map.Entry;  
  6. import java.util.Queue;  
  7.   
  8. /** 
  9. * BD: Learning in Real Time A* Search Agent 
  10. *     http://localhost/JJWiki/Wiki.jsp?page=Beyond%20Classical%20Search#section-Beyond+Classical+Search-OnlineLocalSearch 
  11. * @author John 
  12. * 
  13. */  
  14. public class LRTAAgent {  
  15.     public boolean                  useUncertainOptimal = false;  
  16.     public boolean                  debug = false;  
  17.     private Maze                    maze;  
  18.     private State                   s=null;                                 // Previous state  
  19.     private Action                  a=null;                                 // Previous action  
  20.     private HashMap     result = new HashMap();     // a table, indexed by state and action.  
  21.     private HashMap    H = new HashMap();         // a table of cost estimates indexed by state.  
  22.   
  23.     public static class AState{  
  24.         public State st;  
  25.         public Action act;  
  26.         public AState(State s, Action a){this.st =s; this.act=a;}  
  27.           
  28.         @Override  
  29.         public boolean equals(Object o)  
  30.         {  
  31.             if(o!=null && o instanceof AState)  
  32.             {  
  33.                 AState as = (AState)o;  
  34.                 if(st.equals(as.st) && act.equals(as.act)) return true;  
  35.             }                 
  36.             return false;  
  37.         }  
  38.           
  39.         @Override  
  40.         public int hashCode()  
  41.         {  
  42.             return st.x*100+st.y+act.hashCode();  
  43.         }  
  44.     }  
  45.       
  46.     public LRTAAgent(Maze m){maze = m;}  
  47.       
  48.     public void printf(String fmt, Object ...args)  
  49.     {  
  50.         if(debug) System.out.printf(fmt, args);  
  51.     }  
  52.       
  53.     /** 
  54.      * BD: Use distance in straight line as h(s) 
  55.      * @param s 
  56.      * @param g 
  57.      * @return 
  58.      */  
  59.     public double h(State s, State g)  
  60.     {  
  61.         double dist = Math.pow((double)(g.x-s.x), 2)+ Math.pow((double)(g.y-s.y), 2);  
  62.         //System.out.printf("\t[Test] sd=%.01f for %s to %s...\n", Math.sqrt(dist), s, g);  
  63.         return Math.sqrt(dist);  
  64.     }  
  65.       
  66.     /** 
  67.      * BD : Always return 1; 
  68.      * @param s 
  69.      * @param g 
  70.      * @return 
  71.      */  
  72.     public double h1(State s, State g)  
  73.     {  
  74.         return 1;  
  75.     }  
  76.       
  77.     /** 
  78.      * BD: LRTA*-COST(s,a,s',H) 
  79.      * @param ps 
  80.      * @param a 
  81.      * @param cs 
  82.      * @return 
  83.      */  
  84.     public double lrtaCost(State ps, Action a, State cs)  
  85.     {         
  86.         Double i = cs!=null?H.get(cs.toString()):null;  
  87.           
  88.         if(i==null)   
  89.         {  
  90.             printf("\t[Test] %s take %s to be unknown! Using heruistic...\n", ps, a);  
  91.             return h1(ps, maze.goalState);  
  92.         }  
  93.         else   
  94.         {  
  95.             if(Action.STOP.equals(a))  
  96.             {  
  97.                 printf("\t[Test] lrtaCost[%s, %s, %s]=%.1f(%.1f)...\n", ps, a, cs, i, i);  
  98.                 return 0+i; // Stop take no action and has cost=0;  
  99.             }  
  100.             else  
  101.             {  
  102.                 printf("\t[Test] lrtaCost[%s, %s, %s]=%.1f(%.1f)...\n", ps, a, cs, i+1, i);  
  103.                 return 1+i;  // Here c(s,a,s')=1. Every action take unit cost=1.  
  104.             }  
  105.         }  
  106.     }  
  107.       
  108.     public void showResult()  
  109.     {  
  110.         Iterator> iter = result.entrySet().iterator();  
  111.         while(iter.hasNext())  
  112.         {  
  113.             Entry e = iter.next();  
  114.             System.out.printf("\t[Result] %s->%s\n", e.getKey(), e.getValue());  
  115.         }  
  116.     }  
  117.       
  118.     public void showH()  
  119.     {  
  120.         Iterator> iter = H.entrySet().iterator();  
  121.         while(iter.hasNext())             
  122.         {  
  123.             Entry e = iter.next();  
  124.             System.out.printf("\t[H] %s->%.1f\n", e.getKey(), e.getValue());  
  125.         }  
  126.     }  
  127.       
  128.     /** 
  129.      * BD: Learning in Real Time A* 
  130.      * @param s 
  131.      * @return 
  132.      */  
  133.     public Action lrta(State cs)  
  134.     {  
  135.         if(debug)   
  136.         {  
  137.             showResult();  
  138.             showH();  
  139.         }  
  140.           
  141.         if(maze.goalTest()) return Action.STOP;  
  142.         if(!H.containsKey(cs.toString())) H.put(cs.toString(), h1(cs, maze.goalState));  
  143.         if(s!=null)  
  144.         {  
  145.             // Update result table.  
  146.             printf("\t[Test] Update result: %s take %s to %s...\n", s, a, cs);  
  147.             result.put(String.format("%s_%s", s,a), cs.cloneself());  
  148.             printf("\t[Test] Update result: %s take %s to %s...\n", cs, a.Reverse(), s);  
  149.             result.put(String.format("%s_%s", cs, a.Reverse()), s.cloneself());  
  150.             printf("\t[Test] Update %s to have cost=%.01f...\n", s, lrtaCost(s, a, cs));  
  151.               
  152.             // Update estimated cost for previous state.  
  153.             H.put(s.toString(), lrtaCost(s, a, cs));   
  154.         }  
  155.         Queue queue = maze.actions(cs);  
  156.         double minCost = Integer.MAX_VALUE, tmpCost=0;  
  157.         while(!queue.isEmpty())  
  158.         {  
  159.             Action na = queue.poll();  
  160.             State ns = result.get(String.format("%s_%s", cs, na));  
  161.             if(useUncertainOptimal && ns==null)  
  162.             {  
  163.                 printf("\t[Test] Uncertainity take lead on action=%s...\n", na);  
  164.                 a = na;               
  165.                 break;  
  166.             }  
  167.             else if((tmpCost=lrtaCost(cs, na, ns)) < minCost)  
  168.             {  
  169.                 printf("\t[Test] Take %s from %s to %s have cost=%.01f...\n", na, cs, ns, tmpCost);  
  170.                 minCost = tmpCost;  
  171.                 a = na;  
  172.             }  
  173.         }  
  174.         s = cs.cloneself();  
  175.         return a;  
  176.     }  
  177.       
  178.     public void run() throws Exception  
  179.     {  
  180.         State is = maze.curState;  
  181.         Action a = null;  
  182.         do  
  183.         {  
  184.             a = lrta(is);           // Retrieve action based on current state  
  185.             System.out.printf("\t[Info] %s...\n", a);             
  186.             is = maze.result(a);    // Execute action and get result state.  
  187.             System.out.printf("\t[Info] Maze:\n%s\n", maze);  
  188.             Thread.sleep(1000);  
  189.         }while(!a.equals(Action.STOP));  
  190.     }  
  191.       
  192.     public static void main(String[] args) throws Exception{  
  193.         State cs = new State(0,0); // Initial state  
  194.         State gs = new State(4,3); // Goal state  
  195.         int mb[][] = {{1,1,0,1},{1,0,0,1},{1,1,1,1},{1,0,0,0},{1,1,1,1}};  
  196.         Maze maze = new Maze(mb, cs, gs);  
  197.         //System.out.printf("\t[Info] Maze:\n%s\n", maze);  
  198.         LRTAAgent lrtaAgent = new LRTAAgent(maze);  
  199.         lrtaAgent.useUncertainOptimal = false;  // Using uncertainty optimal approach  
  200.         lrtaAgent.debug = true// Debug use. Print more message.  
  201.         lrtaAgent.run();  
  202.     }  
  203. }  
執行結果如下: 
[Test] (0,0) has 2 actions...
[Info] Move Right...
[Info] Maze:
RRR#G
##R#R
R#R#R
RSRRR
...(略)...
[Test] (4,2) has 2 actions...
[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

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

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...