teamwork.multiagent.pwlSimulation

16 """ 17 @ivar societyFile: the location of the L{GenericSociety<teamwork.multiagent.GenericSociety.GenericSociety>} 18 @type societyFile: str 19 """ 20

21 - def __init__(self,agents=None,observable=False):

22 """Initializes a collection to contain the given list of agents 23 @param agents: the fully-specified agents 24 @param observable: iff C{True}, agents always maintain correct beliefs about the world 25 @type observable: bool 26 @param effects: a table of features that actions affect, indexed by action, with each value being a list of keys 27 @type effects: L{Action}S{->}L{StateKey}[] 28 """ 29 self.societyFile = None 30 self.observable = observable 31 self.effects = {} 32 if agents is None: 33 MultiagentSystem.__init__(self) 34 self.state = Distribution({KeyedVector():1.}) 35 else: 36 members = [] 37 for agent in agents.members(): 38 new = PWLAgent(agent) 39 if not new.policy.rules: 40 # No policy for this agents; let's check whether 41 # somebody else computed one 42 for other in agents.members(): 43 if other.name != agent.name: 44 try: 45 belief = other.getEntity(agent.name) 46 if belief.policy.rules: 47 new.policy = belief.policy 48 break 49 except KeyError: 50 pass 51 members.append(new) 52 MultiagentSystem.__init__(self,members) 53 self.state = agents.state 54 self.initialize() 55 self.time = 0 56 self.history = {}

57

58 - def initialize(self):

59 self.effects.clear() 60 for agent in self.members(): 61 if agent.beliefs is agent.state: 62 agent.beliefs = self.state 63 agent.state = self.state 64 agent.world = self

65 ## for option in agent.actions.getOptions(): 66 ## for action in option: 67 ## self.effects[action] = [] 68 ## for other in self.members(): 69 ## for feature,table in other.dynamics.items(): 70 ## if table.has_key(action) or \ 71 ## table.has_key(action['type']): 72 ## key = StateKey({'entity':other.name, 73 ## 'feature':feature}) 74 ## self.effects[action].append(key) 75

76 - def microstep(self,turns,hypothetical=False,explain=False, 77 state=None,suggest=False):

78 """Step forward by the action of the given entities 79 @param turns: the agents to act next, each entry in the list should be a dictionary: 80 - I{name}: the name of the agent to act 81 - I{choices}: the list of possible options this agent can consider in this turn (defaults to the list of all possible actions if omitted, or if the list is empty) 82 - I{history}: a dictionary of actions already performed (defaults to the built-in history of this simulation instance) 83 @type turns: C{dict[]} 84 @param hypothetical: if C{True}, then this is only a hypothetical microstep; otherwise, it is real (default is C{False}) 85 @type hypothetical: bool 86 @param explain: if C{True}, then add an explanation to the result (default is C{False}) 87 @type explain: bool 88 @return: XML results 89 @rtype: Element 90 @param suggest: this is ignored 91 @type suggest: bool 92 """ 93 start = time.time() 94 # Generate XML explanation 95 doc = Document() 96 root = doc.createElement('step') 97 doc.appendChild(root) 98 root.setAttribute('time',str(self.time+1)) 99 root.setAttribute('hypothetical',str(hypothetical)) 100 # Cache of values 101 values = {} 102 # Build up the list of selected actions 103 actionDict = {} 104 raw = {} 105 for turn in turns: 106 name = turn['name'] 107 actor = self[name] 108 try: 109 choices = turn['choices'] 110 except KeyError: 111 choices = [] 112 if self.history is None: 113 history = None 114 else: 115 try: 116 history = turn['history'] 117 except KeyError: 118 history = copy.copy(self.history) 119 if len(choices) == 0: 120 for option in actor.actions.getOptions(): 121 choices.append(option) 122 ## if len(option) == 0: 123 ## # Doing nothing is always an option? 124 ## choices.append(option) 125 ## elif not actor.actions.illegal.has_key(str(option)): 126 ## # No deactivation of actions, so everything's possible 127 ## choices.append(option) 128 if len(choices) == 1: 129 actionDict[name] = choices[0] 130 exp = None 131 elif len(choices) > 1: 132 action,exp = actor.applyPolicy(actions=choices,history=history, 133 explain=explain,entities=self, 134 cache=values,state=state) 135 actionDict[name] = action 136 else: 137 # No actions for this actor 138 continue 139 node = doc.createElement('turn') 140 root.appendChild(node) 141 node.setAttribute('agent',name) 142 node.setAttribute('time',str(self.time+1)) 143 node.setAttribute('forced',str(len(choices) == 1)) 144 subDoc = self.explainAction(actionDict[name]) 145 node.appendChild(subDoc.documentElement) 146 if exp: 147 if explain: 148 node.appendChild(exp.documentElement) 149 raw[name] = exp 150 print 'Decision time:',time.time()-start 151 start = time.time() 152 # Update state and beliefs 153 if state is None: 154 current = None 155 else: 156 current = state[None] 157 result = {'decision': actionDict, 158 'delta': self.hypotheticalAct(actionDict,doc,current), 159 'explanation': doc, 160 'raw': raw, 161 } 162 print 'Delta time:',time.time()-start 163 if not hypothetical and sum(actionDict.values(),[]): 164 start = time.time() 165 # Update state (both objective and subjective) if real 166 # and if there's at least one action being performed 167 self.applyChanges(result['delta']) 168 # Update simulation clock 169 self.time += 1 170 if not self.history is None: 171 # Update action history 172 for option in actionDict.values(): 173 for action in option: 174 self.history[str(action)] = True 175 print 'Update time:',time.time()-start 176 return result

177

178 - def hypotheticalAct(self,actions,exp=None,state=None):

179 """ 180 Computes the scenario changes that would result from a given action 181 @param actions: dictionary of actions, where each entry is a list of L{Action<teamwork.action.PsychActions.Action>} instances, indexed by the name of the actor 182 @type actions: C{dict:str->L{Action<teamwork.action.PsychActions.Action>}[]} 183 @return: the changes that would result from I{actions} 184 - state: the change to state, in the form of a L{Distribution} over L{KeyedMatrix} (suitable to pass to L{applyChanges}) 185 - I{agent}: the change to the recursive beliefs of I{agent}, as returned by L{preComStateEstimator<teamwork.agent.RecursiveAgent.RecursiveAgent.preComStateEstimator>} 186 @rtype: C{dict} 187 @param exp: an optional partial explanation to expand upon 188 @type exp: Document 189 """ 190 if state is None: 191 state = self.state 192 # Eventual return value, storing up all the various belief 193 # deltas across the entities 194 overallDelta = {} 195 overallDelta['state'] = self.getDelta(actions,state,exp) 196 if not self.observable: 197 # Update members' subjective beliefs 198 for entity in self.members(): 199 overallDelta[entity.name] = self.getDelta(actions, 200 entity.beliefs) 201 return overallDelta

202

203 - def getState(self):

204 """ 205 @return: a dictionary of 'state' and relationships of the current simulation state 206 @rtype: dict 207 """ 208 result = {'__state':self.state} 209 for entity in self.members(): 210 result[entity.name] = entity.links 211 return result

212

213 - def getDelta(self,actions,state,exp=None):

214 """ 215 Computes the changes to the given state distribution that would result from a given action 216 @param actions: dictionary of actions, where each entry is a list of L{Action<teamwork.action.PsychActions.Action>} instances, indexed by the name of the actor 217 @type actions: C{dict:str->L{Action<teamwork.action.PsychActions.Action>}[]} 218 @param state: the initial state 219 @type state: L{Distribution}(L{KeyedMatrix}) 220 @param exp: an optional partial explanation to expand upon 221 @type exp: Document 222 """ 223 result = Distribution() 224 for vector,oProb in state.items(): 225 delta = self.applyDynamics(actions,vector,exp) 226 for matrix,nProb in delta.items(): 227 # Update probability of result 228 try: 229 result[matrix] += oProb*nProb 230 except KeyError: 231 result[matrix] = oProb*nProb 232 return result

233

234 - def applyDynamics(self,actions,state,exp=None):

235 """Compute the effect of the given actions on the given state vector 236 @param actions: the dictionary of actions 237 @type actions: strS{->}L{Action}[] 238 @type state: L{KeyedVector} 239 @rtype: dict 240 """ 241 if exp: 242 # Determine which parts of explanation we are expanding upon 243 turns = {} 244 child = exp.documentElement.firstChild 245 while child: 246 if child.nodeType == child.ELEMENT_NODE and \ 247 child.tagName == 'turn': 248 turns[str(child.getAttribute('agent'))] = child 249 child = child.nextSibling 250 result = Distribution() 251 matrix = {} 252 remaining = {} 253 for key in state.keys(): 254 if isinstance(key,StateKey): 255 remaining[key] = True 256 if self.effects: 257 # We know which state features are affected by each action 258 for option in actions.values(): 259 for action in option: 260 for key in self.effects[action]: 261 dynamics,delta = self.getEffect(action,key,state) 262 if dynamics: 263 if delta: 264 updateDelta(matrix,key,exp,turns,action, 265 vector=state,delta=delta) 266 else: 267 delta = updateDelta(matrix,key,exp,turns, 268 action,dynamics,state) 269 try: 270 del remaining[key] 271 except KeyError: 272 pass 273 else: 274 # We have to consider all possible features 275 for key in remaining.keys(): 276 for option in actions.values(): 277 for action in option: 278 dynamics,delta = self.getEffect(action,key,state) 279 if dynamics: 280 if delta: 281 delta = updateDelta(matrix,key,exp,turns, 282 action,vector=state,delta=delta) 283 else: 284 delta = updateDelta(matrix,key,exp,turns, 285 action,dynamics,state) 286 if delta: 287 # Update liking for this actor 288 for entity in self.members(): 289 link = entity.getLinkKey(entity._supportFeature, 290 action['actor']) 291 goals = entity.goals.expectation() 292 if entity.links.has_key(link) and \ 293 goals.has_key(key): 294 new = {link:KeyedVector(delta[key])} 295 new[link][key] -= 1. 296 new[link] *= goals[key] 297 new[link][link] = 1. 298 updateDelta(matrix,link,exp,turns,action, 299 vector=state,delta=new) 300 # Update other dynamic relationships 301 for entity in self.members(): 302 for link in entity.links.keys(): 303 if link['verb'] != entity._supportFeature and \ 304 link['verb'] != entity._trustFeature: 305 try: 306 option = actions[link['object']] 307 except KeyError: 308 option = [] 309 for action in option: 310 try: 311 dynamics = entity.linkDynamics[link['verb']][action['type']] 312 except KeyError: 313 dynamics = None 314 if dynamics: 315 change = dynamics.instantiateAndApply(state,entity, 316 action) 317 updateDelta(matrix,link,exp,turns,action, 318 vector=state,delta=change) 319 # Look for default dynamics 320 for key in remaining.keys(): 321 if not matrix.has_key(key): 322 entity = self[key['entity']] 323 dynamics = entity.getDynamics(Action({'type':None}), 324 key['feature']) 325 if dynamics: 326 updateDelta(matrix,key,exp,turns,None,dynamics,state) 327 result[matrix] = 1. 328 return result

329

330 - def getEffect(self,action,key,vector,instantiate=True,debug=False):

331 """Computes the effect of the given action on the given L{StateKey} 332 @return: the dynamics object, and possible a computed delta 333 """ 334 entity = self[key['entity']] 335 try: 336 # Look for instantiated dynamics 337 dynamics = entity.dynamics[key['feature']][action] 338 if debug: 339 print 'Found instantiated dynamics' 340 if isinstance(dynamics,dict): 341 # Link to other instantiated dynamics 342 if debug: 343 print 'Link to other instance' 344 entity = self[dynamics['entity']] 345 dynamics = entity.dynamics[dynamics['feature']][dynamics['action']] 346 return dynamics,None 347 except KeyError: 348 if not instantiate: 349 # Default is no effect 350 if debug: 351 print 'No instantiated dynamics' 352 return None,None 353 # Look for generic dynamics 354 try: 355 dynamics = entity.dynamics[key['feature']][action['type']] 356 except KeyError: 357 if debug: 358 print 'No generic dynamics' 359 return None,None 360 if isinstance(dynamics,str): 361 # Access link to generic dynamics 362 if debug: 363 print 'Link to other generic model' 364 dynamics = entity.society[dynamics].dynamics[key['feature']][action['type']] 365 if dynamics: 366 # Do a partial instantiation 367 if entity.name == action['actor']: 368 effectKey = 'actor' 369 elif entity.name == action['object']: 370 effectKey = 'object' 371 else: 372 effectKey = 'other' 373 try: 374 applicable = dynamics.effects[effectKey] 375 except KeyError: 376 applicable = True 377 if applicable: 378 if debug: 379 print 'Instantiating...' 380 print dynamics.getTree() 381 delta = dynamics.instantiateAndApply(vector,self[key['entity']] 382 ,action) 383 if debug: 384 print delta[key] 385 return dynamics,delta 386 return None,None

387

388 - def applyChanges(self,delta,current=None):

389 """Applies the differential changes to this set of entities""" 390 if current is None: 391 state = self.state 392 else: 393 state = current[None] 394 for key,subDelta in delta.items(): 395 if key == 'state': 396 if len(state) == 1 and len(subDelta) == 1: 397 # Update in place 398 vector = state.domain()[0] 399 delta = subDelta.domain()[0] 400 newVector = {} 401 for key,row in delta.items(): 402 newValue = 0. 403 for deltaKey,weight in row.items(): 404 if isinstance(deltaKey,LinkKey): 405 if current is None: 406 newValue += weight*self[key['subject']].links[key] 407 else: 408 newValue += weight*current[key['subject']][key] 409 elif isinstance(deltaKey,ConstantKey): 410 newValue += weight 411 elif isinstance(deltaKey,StateKey): 412 try: 413 newValue += weight*vector[deltaKey] 414 except KeyError: 415 print 'Dynamics for %s refers to nonexistent key %s' % (key,deltaKey) 416 else: 417 raise UserWarning,'Unknown delta key: %s' % \ 418 (deltaKey) 419 newVector[key] = max(min(newValue,1.),-1.) 420 # Copy new vector over 421 for key,newValue in newVector.items(): 422 if isinstance(key,StateKey): 423 try: 424 index = vector._order[key] 425 vector.getArray()[index] = newValue 426 except KeyError: 427 # New value for nonexistent state feature! Bad! 428 pass 429 elif isinstance(key,LinkKey): 430 if current is None: 431 self[key['subject']].links[key] = newValue 432 else: 433 current[key['subject']][key] = newValue 434 else: 435 print 'Unknown delta:',key,newValue 436 state.clear() 437 state[vector] = 1. 438 else: 439 state = subDelta*state 440 else: 441 # Apply changes to subjective beliefs 442 entity = self[key] 443 entity.beliefs = subDelta*entity.beliefs 444 if current is None: 445 # Reattach state (need a cleaner way of doing this) 446 for agent in self.members(): 447 agent.state = state 448 if self.observable: 449 agent.beliefs = state 450 return state

451

452 - def explainAction(self,actions):

453 doc = Document() 454 root = doc.createElement('decision') 455 doc.appendChild(root) 456 for action in actions: 457 root.appendChild(action.__xml__().documentElement) 458 return doc

459

460 - def __xml__(self,dynamics=False):

461 """ 462 @param dynamcis: if C{True}, instantiated dynamics are stored as well (default is C{False} 463 @type dynamics: bool 464 """ 465 doc = Document() 466 root = doc.createElement('multiagent') 467 root.setAttribute('type',self.__class__.__name__) 468 if self.societyFile: 469 root.setAttribute('society',self.societyFile) 470 doc.appendChild(root) 471 for agent in self.members(): 472 root.appendChild(agent.__xml__(dynamics).documentElement) 473 # Save simulation clock 474 root = doc.documentElement 475 root.setAttribute('time',str(self.time)) 476 # Save state vector 477 node = doc.createElement('state') 478 node.appendChild(self.state.__xml__().documentElement) 479 root.appendChild(node) 480 # Save action history 481 node = doc.createElement('history') 482 for action,flag in self.history.items(): 483 # Every action in the keys should have a flag of True, 484 # but why take chances? 485 if flag: 486 child = doc.createElement('action') 487 child.setAttribute('label',action) 488 node.appendChild(child) 489 root.appendChild(node) 490 return doc

491

492 - def parse(self,element,agentClass=PWLAgent,societyClass=None):

493 """ 494 @return: C{False} iff unable to load a specified society file 495 @rtype: bool 496 """ 497 self.history.clear() 498 MultiagentSystem.parse(self,element,agentClass) 499 filename = str(element.getAttribute('society')) 500 if filename: 501 self.societyFile = filename 502 # Load simulation clock 503 self.time = str(element.getAttribute('time')) 504 if self.time: 505 self.time = int(self.time) 506 else: 507 # No such attribute 508 self.time = 0 509 child = element.firstChild 510 while child: 511 if child.nodeType == child.ELEMENT_NODE: 512 if child.tagName == 'state': 513 # Load state vector 514 self.state.parse(child.firstChild,KeyedVector) 515 elif child.tagName == 'history': 516 # Load action history 517 grandchild = child.firstChild 518 while grandchild: 519 if grandchild.nodeType == grandchild.ELEMENT_NODE: 520 assert grandchild.tagName == 'action' 521 action = str(grandchild.getAttribute('label')) 522 self.history[action] = True 523 grandchild = grandchild.nextSibling 524 child = child.nextSibling 525 # If completely observable, everyone's beliefs are real state 526 if self.observable: 527 for entity in self.members(): 528 entity.beliefs = self.state 529 # Load society if available 530 if societyClass and self.societyFile: 531 society = societyClass() 532 try: 533 f = bz2.BZ2File(self.societyFile,'r') 534 data = f.read() 535 f.close() 536 except IOError: 537 return False 538 doc = parseString(data) 539 society.parse(doc.documentElement) 540 for agent in self.members(): 541 agent.society = society 542 return True

Source Code for Module teamwork.multiagent.pwlSimulation