Source Code for Module teamwork.state.States

  1   ########################################################################### 
  2   # 11/5/2001: David V. Pynadath (pynadath@isi.edu) 
  3   # 
  4   # StateSpace: generic state space class for representing a set of states, 
  5   #      where each state is a combination of feature-value pairs.  Useful 
  6   #      mainly as a skeleton class, since by itself, it enumerates all 
  7   #      possible combinations of feature-value pairs, regardless of actual 
  8   #      reachability. 
  9   # 
 10   # EnumeratedSubspace: more practical state space class that generates only  
 11   #      reachable subset of the overall state space. 
 12   #  
 13   ########################################################################### 
 14   
 15  import copy 
 16  from types import * 
 17  # 
 18  # Very general, but very weak state space class, defines some basic 
 19  # methods, and is useful for state spaces where all combinations of 
 20  # attribute values are possible and reachable 
 21  # 
 22 -class StateSpace: 
 23      version = 1.0 
 24      # Takes an optional list of features, where each feature is a tuple (name,  
 25      # values), with "name" being a string giving the name of the feature, and 
 26      # "values" is a list of strings, with each string being the name of a 
 27      # possible value for this feature. 
 28 -    def __init__(self,featureList=[]): 
 29          self.features = {} 
 30          self.size = 1 
 31          for feature in featureList: 
 32              self.features[feature[0]] = feature[1] 
 33              self.size = self.size * len(feature[1]) 
 34   
 35      # Adds an additional feature to the space, named after the string 
 36      # "featureName" and with possible values taken from the list 
 37      # "featureSpace" 
 38 -    def addFeature(self,featureName,featureSpace): 
 39          self.features[featureName] = featureSpace 
 40          self.size = self.size*len(featureSpace) 
 41   
 42      # Useful for iterating through state space, since it (along with 
 43      # getNextState) provides a java Enumeration-type functionality 
 44 -    def getFirstState(self): 
 45          state = {'_index':{}} 
 46          for feature in self.features.keys(): 
 47              state['_index'][feature] = 0 
 48              state[feature] = self.features[feature][0] 
 49          return state 
 50   
 51      # Useful for iterating through state space, since it (along with 
 52      # getFirstState) provides a java Enumeration-type functionality.  Returns 
 53      # None when there are no more states left. 
 54 -    def getNextState(self,oldState,parent=None): 
 55          keys = self.features.keys() 
 56          state = copy.deepcopy(oldState) 
 57          changedFlag = None 
 58          for feature in keys: 
 59              state['_index'][feature] = state['_index'][feature] + 1 
 60              if state['_index'][feature] >= len(self.features[feature]): 
 61                  state['_index'][feature] = 0 
 62              state[feature] = \ 
 63                             self.features[feature][state['_index'][feature]] 
 64              if state['_index'][feature] > 0: 
 65                  changedFlag = 1 
 66                  break 
 67          if changedFlag: 
 68              return state 
 69          else: 
 70              return None 
 71   
 72      # Returns a unique integer ID corresponding to a state 
 73 -    def state2index(self,state): 
 74          index = 0 
 75          keys = copy.deepcopy(self.features.keys()) 
 76          keys.reverse() 
 77          for feature in keys: 
 78              index = (index*len(self.features[feature])) + \ 
 79                      state['_index'][feature] 
 80          return index 
 81   
 82      # Returns the unique state corresponding to an integer ID 
 83 -    def index2state(self,index): 
 84          total = index 
 85          state = {'_index':{}} 
 86          for feature in self.features.keys(): 
 87              value = total - (total/len(self.features[feature])*\ 
 88                               len(self.features[feature])) 
 89              state['_index'][feature] = value 
 90              state[feature] = self.features[feature][value] 
 91              total = (total/len(self.features[feature])*\ 
 92                       len(self.features[feature])) 
 93          return state 
 94   
 95      # Generates a unique ID for the state, returns nothing 
 96 -    def createIndex(self,state): 
 97          state['_index'] = {} 
 98          for feature in self.features.keys(): 
 99              try: 
100                  state['_index'][feature] = self.features[feature].\ 
101                                             index(state[feature]) 
102              except ValueError: 
103                  print 'Feature:',feature,'does not contain:',state[feature] 
104   
105      # Returns a dictionary version of the provided state with various 
106      # bookkeeping fields removed.  Useful for pretty printing of states. 
107 -    def state2dict(self,state): 
108          dict = copy.copy(state) 
109          for key in dict.keys()[:]: 
110              if key[0] == '_': 
111                  del dict[key] 
112          return dict 
113   
114      # Utility method for taking a dictionary of state feature values and 
115      # returning the specific state object stored in the state space. 
116 -    def dict2state(self,state): 
117          return self.index2state(self.state2index(state)) 
118   
119 -    def printStates(self): 
120          state = self.getFirstState() 
121          while state: 
122              print self.state2dict(state) 
123              state = self.getNextState(state) 
124   
125  # 
126  # Compact, dynamically generated version of the state space class 
127  # 
128 -class EnumeratedSubspace(StateSpace): 
129      version = 1.0 
130      # states: instance of StateSpace, used to specify the features of 
131      #         interest, as well as all possible values for those features 
132      # generators: a dictionary, with keys corresponding to the names of 
133      #         features in the state space, and the entry for each key being a 
134      #         function that takes, as input, an original state and an action 
135      #         and returns, as output, a list of possible values for the given 
136      #         feature over all possible destination states 
137      # actions: a list of strings, with each string being the name of a 
138      #         possible action (corresponding to the action argument to the 
139      #         generator functions) 
140      # initialStates: an optional list of start states 
141      # RETURNS: a subset of the overall StateSpace instance.  This subset 
142      #         contains only those states reachable from the specified 
143      #         initial states, according to the generator functions and set of 
144      #         all possible actions 
145 -    def __init__(self,states,generators,actions,initialStates=None, 
146                   debug=0): 
147          self.features = states.features 
148          self.featureKeys = self.features.keys() 
149          if initialStates: 
150              self.states = initialStates[:] 
151          else: 
152              self.states = [states.getFirstState()] 
153          self.children = [] 
154          self.parents = [] 
155          self.indices = {} 
156          self.__initializeIndex(self.indices,0) 
157          for curState in range(len(self.states)): 
158              realState = states.state2dict(self.states[curState]) 
159              self.__addIndex(realState,curState) 
160   
161          curState = 0 
162          maxChildren = 0 
163          while curState < len(self.states): 
164              if debug > 1: 
165                  print self.state2dict(self.index2state(curState)) 
166              self.children.append({}) 
167              while len(self.parents) <= curState: 
168                  self.parents.append({}) 
169              # Determine set of applicable actions in this state 
170              if generators.has_key('Action'): 
171                  actionSet = generators['Action'](self.states[curState]) 
172              else: 
173                  actionSet = actions 
174              for action in actionSet: 
175                  self.children[curState][action] = [] 
176                  successors = {} 
177                  # Determine all possible successor states, given the 
178                  # particular action to be taken 
179                  for feature in self.featureKeys: 
180                      successors[feature] = [] 
181                      possibleSuccessors = generators[feature]\ 
182                                           (self.states[curState],action) 
183                      for successor in possibleSuccessors: 
184                          if not successor in successors[feature]: 
185                              successors[feature].append(successor) 
186                  # Create set of possible states out of combinations of 
187                  # possible successor feature values 
188                  successorStates = [{}] 
189                  for feature in self.features.keys(): 
190                      self.__generateStates(generators,curState,action, 
191                                           feature,successorStates) 
192                  # Add successors to state space (unless already present) 
193                  for nextState in successorStates: 
194                      # Create state index for quick access 
195                      nextIndex = self.state2index(nextState) 
196                      if nextIndex < 0: 
197                          # State doesn't exist yet, so add it to state space 
198                          # now. 
199                          nextIndex = len(self.states) 
200                          self.__addIndex(nextState,nextIndex) 
201                          self.states.append(nextState) 
202                      # Enumerate state as possible successor 
203                      self.children[curState][action].append(nextIndex) 
204                      # Enumerate current state as possible parent of successor 
205                      while len(self.parents) <= nextIndex: 
206                          self.parents.append({}) 
207                      if not self.parents[nextIndex].has_key(action): 
208                          self.parents[nextIndex][action] = [] 
209                      self.parents[nextIndex][action].append(curState) 
210                  # Update record of maximum branching factor 
211                  if len(self.children[curState][action]) > maxChildren: 
212                      maxChildren = len(self.children[curState][action]) 
213              curState = curState + 1 
214          # Create position index within each state 
215          for curState in range(len(self.states)): 
216              self.states[curState]['_position'] = curState 
217          self.size = len(self.states) 
218          if debug: 
219              print 'State space:',self.size,'states' 
220              print 'Max successors:',maxChildren 
221   
222 -    def __initializeIndex(self,indices,position): 
223          if position < len(self.featureKeys): 
224              for value in self.features[self.featureKeys[position]]: 
225                  if position + 1 < len(self.featureKeys): 
226                      indices[value] = {} 
227                  else: 
228                      indices[value] = -1 
229                  self.__initializeIndex(indices[value],position+1) 
230   
231 -    def __generateStates(self,generators,state,action,feature,stateList): 
232              # Determine whether we've already processed this feature 
233              try: 
234                  if stateList[0].has_key(feature): 
235                      # This feature has already been processed 
236                      done = 1 
237                  else: 
238                      done = None 
239              except IndexError: 
240                  done = None 
241              if not done: 
242                  # Process this feature 
243                  successors = {} 
244                  # Determine all possible successor states, given the 
245                  # particular action to be taken 
246                  successors = [] 
247                  possibleSuccessors = generators[feature]\ 
248                                       (self.states[state],action) 
249                  try: 
250                      substate = possibleSuccessors[0] 
251                      if type(substate) is DictType: 
252                          #  Joint generator for multiple features 
253                          successors = possibleSuccessors 
254                      else: 
255                          # Independent generator for this feature only 
256                          for successor in possibleSuccessors: 
257                              substate = {feature:successor} 
258                              if not substate in successors: 
259                                  successors.append(substate) 
260                  except IndexError: 
261                      pass 
262                  # Compose new successors with current list of partial 
263                  # states 
264                  originalStates = stateList[:] 
265                  for orig in originalStates: 
266                      stateList.remove(orig) 
267                      for substate in successors: 
268                          for key in substate.keys(): 
269                              orig[key] = substate[key] 
270                          stateList.append(copy.copy(orig)) 
271   
272 -    def ___generateStatesOld(self,featureVals,features,index,stateList): 
273          if index < len(features): 
274              originalStates = stateList[:] 
275              for state in originalStates: 
276                  stateList.remove(state) 
277                  for value in featureVals[features[index]]: 
278                      state[features[index]] = value 
279                      stateList.append(copy.copy(state)) 
280              self.___generateStatesOld(featureVals,features,index+1,stateList) 
281   
282      # Returns a first state from the state space.  This is useful for 
283      # iterating through the state space.  If the optional parent argument is 
284      # provided, it returns the first destination state immediately reachable 
285      # from the parent.  The return value is consistent across multiple calls 
286      # with the same argument. 
287 -    def getFirstState(self,parent=None): 
288          if parent: 
289              children = self.children[parent['_position']] 
290              state = self.states[children[0]] 
291              if not state.has_key('_'+`parent['_position']`): 
292                  state['_'+`parent['_position']`] = 0 
293              return state 
294          else: 
295              return self.states[0] 
296   
297      # Returns the next state in a sequence throughout the state space.  This 
298      # is useful for iterating through the state space.  oldState is the 
299      # previous state in this sequence.  The sequence is consistent across 
300      # multiple calls. 
301 -    def getNextState(self,oldState,parent=None): 
302          if parent: 
303              children = self.children[parent['_position']] 
304              key = '_'+`parent['_position']` 
305              if oldState[key] < len(children)-1: 
306                  state = self.states[children[oldState[key]+1]] 
307                  if not state.has_key(key): 
308                      state[key] = oldState[key]+1 
309                  return state 
310              else: 
311                  return None 
312          elif oldState['_position'] < len(self.states)-1: 
313              return self.states[oldState['_position']+1] 
314          else: 
315              return None 
316   
317      # Remove any children that have a zero probability with respect to the 
318      # given distribution. 
319 -    def pruneChildren(self,probFun,threshold=0.000001): 
320          maxChildren = 0 
321          for origState in self.states: 
322              orig = self.state2index(origState) 
323              for action in self.children[orig].keys(): 
324                  for dest in self.children[orig][action][:]: 
325                      destState = self.index2state(dest) 
326                      self.state2dict(destState) 
327                      if probFun(origState,destState,action) < threshold: 
328                          self.parents[dest][action].remove(orig) 
329                          self.children[orig][action].remove(dest) 
330                  if len(self.children[orig][action]) > maxChildren: 
331                      maxChildren = len(self.children[orig][action]) 
332   
333 -    def __addIndex(self,state,position): 
334          index = self.indices 
335          for feature in self.featureKeys: 
336              if type(index[state[feature]]) is IntType: 
337                  index[state[feature]] = position 
338              else: 
339                  index = index[state[feature]] 
340   
341      # Utility method for taking a symbolic state representation and returning 
342      # a unique numeric ID for the state 
343 -    def state2index(self,state): 
344          if state.has_key('_position'): 
345              return state['_position'] 
346          else: 
347              index = self.indices 
348              for feature in self.featureKeys: 
349                  if index.has_key(state[feature]): 
350                      index = index[state[feature]] 
351                  else: 
352                      print 'Unable to find index for state:',state 
353                      print 'Failed on feature value:',state[feature] 
354                      print 'Valid feature values:',index.keys() 
355                      return -1 
356              state['_position'] = index 
357              return index 
358   
359      # Utility method for taking a numeric state ID and returning a symbolic 
360      # state representation 
361 -    def index2state(self,index): 
362          try: 
363              return self.states[index] 
364          except IndexError: 
365              print 'Illegal index:',index 
366              return None 
367   
368 -    def dict2state(self,state): 
369          try: 
370              del state['_position'] 
371          except KeyError: 
372              pass 
373          return StateSpace.dict2state(self,state) 
374