Untitled diff
建立於 差異永不過期
Policy Iteration
Value Iteration
public boolean performReachabilityFrom(State si){
public boolean performReachabilityFrom(State si){
HashableState sih = this.stateHash(si);
HashableState sih = this.stateHash(si);
//if this is not a new state and we are not required to perform a new reachability analysis, then this method does not need to do anything.
//if this is not a new state and we are not required to perform a new reachability analysis, then this method does not need to do anything.
if(valueFunction.containsKey(sih) && this.foundReachableStates){
if(valueFunction.containsKey(sih) && this.foundReachableStates){
return false; //no need for additional reachability testing
return false; //no need for additional reachability testing
}
}
DPrint.cl(this.debugCode, "Starting reachability analysis");
DPrint.cl(this.debugCode, "Starting reachability analysis");
//add to the open list
//add to the open list
LinkedList <HashableState> openList = new LinkedList<HashableState>();
LinkedList <HashableState> openList = new LinkedList<HashableState>();
Set <HashableState> openedSet = new HashSet<HashableState>();
Set <HashableState> openedSet = new HashSet<HashableState>();
openList.offer(sih);
openList.offer(sih);
openedSet.add(sih);
openedSet.add(sih);
while(!openList.isEmpty()){
while(!openList.isEmpty()){
HashableState sh = openList.poll();
HashableState sh = openList.poll();
//skip this if it's already been expanded
//skip this if it's already been expanded
if(valueFunction.containsKey(sh)){
if(valueFunction.containsKey(sh)){
continue;
continue;
}
}
//do not need to expand from terminal states
//do not need to expand from terminal states if set to prune
if(model.terminal(sh.s())){
if(this.model.terminal(sh.s()) && stopReachabilityFromTerminalStates){
continue;
continue;
}
}
valueFunction.put(sh, valueInitializer.value(sh.s()));
this.valueFunction.put(sh, this.valueInitializer.value(sh.s()));
List<Action> actions = this.applicableActions(sh.s());
List<Action> actions = this.applicableActions(sh.s());
for(Action a : actions){
for(Action a : actions){
List<TransitionProb> tps = ((FullModel)model).transitions(sh.s(), a);
List<TransitionProb> tps = ((FullModel)model).transitions(sh.s(), a);
for(TransitionProb tp : tps){
for(TransitionProb tp : tps){
HashableState tsh = this.stateHash(tp.eo.op);
HashableState tsh = this.stateHash(tp.eo.op);
if(!openedSet.contains(tsh) && !valueFunction.containsKey(tsh)){
if(!openedSet.contains(tsh) && !valueFunction.containsKey(tsh)){
openedSet.add(tsh);
openedSet.add(tsh);
openList.offer(tsh);
openList.offer(tsh);
}
}
}
}
}
}
}
}
DPrint.cl(this.debugCode, "Finished reachability analysis; # states: " + valueFunction.size());
DPrint.cl(this.debugCode, "Finished reachability analysis; # states: " + valueFunction.size());
this.foundReachableStates = true;
this.foundReachableStates = true;
this.hasRunVI = false;
return true;
return true;
}
}