1 """Class for using AND-(X)OR trees to define the space of possible actions that an agent has available"""
2
3 import copy
4 from xml.dom.minidom import *
5 from PsychActions import *
6
8 """Space of possible options that an agent may have
9 Each option is assumed to be a dictionary-type object. A L{DecisionSpace} object generates all of the possible objects that can be generated by extending a given base (partially filled) object with a given key, whose value ranges over a supplied list of possible fillers.
10 @ivar base: the kernel dictionary object about which all the options are convolved
11 @ivar values: the possible options that can be used at this level of the decision hierarchy
12 @cvar branchType: label for this class of L{DecisionSpace}
13 @type branchType: string
14 @ivar illegal: options that should never be considered
15 @type illegal: strS{->}L{Action}
16 """
17
18 branchType = None
19
20 - def __init__(self,key=None,values=[],base=None):
21 """Constructor that initializes the base option and relevant key
22 @param key: the dictionary key over which this decision space generates possible fillers
23 @type key: string
24 @param base: the original dictionary object that is to be filled in (by default, a list containing a single empty L{Action} object)
25 """
26 self.key = key
27 if base:
28 self.base = base
29 else:
30 self.base = [Action()]
31 self.values = values[:]
32 self.options = []
33 self.illegal = {}
34
35 self.extras = []
36 self._generated = None
37
39 """Adds the given option directly to the space
40 @param option: the option to add to the space
41 @type option: C{L{Action}[]}
42 """
43 if not option in self.extras:
44 self.extras.append(option)
45
47 """Adds the given value to the list of possible fillers
48 @type value: C{str}
49 """
50 if not value in self.values:
51 if isinstance(value,Action):
52 raise TypeError
53 self.values.append(value)
54 self._generated = None
55
57 """Removes the given value from the list of possible fillers
58 @return: false if the value is not present; otherwise, true"""
59 try:
60 self.values.remove(value)
61 self._generated = None
62 return True
63 except ValueError:
64
65 return False
66
68 """Replaces single old value with new values
69 @param old: a single value
70 @param new: a list of values
71
72 The method continues the replacement by descending recursively
73 if there are any nested decision spaces"""
74 if self.remove(old):
75 for value in new:
76 self.append(value)
77 if isinstance(self.base,DecisionSpace):
78
79 self.base.replace(old,new)
80
82 """Accessor for the options in this space
83 @return: a list of possible options (typically, L{Action} instances)
84 """
85 if not self._generated:
86 self.generateOptions()
87 return self.options+self.extras
88
90 """Debugging method that returns true iff the given field is set"""
91 for action in self.getOptions():
92 if isinstance(action,list):
93 actionList = action
94 else:
95 actionList = [action]
96 for action in actionList:
97 if action[field]:
98 return 1
99 else:
100 return None
101
103 """Utility method that generates possible options"""
104 self.options = []
105 self._generated = 1
106
118
120 space = self.__class__(self.key,self.values,self.base)
121 space.extras = self.extras[:]
122 return space
123
125 space = self.__class__(self.key,self.values,
126 copy.deepcopy(self.base))
127 space.extras = copy.deepcopy(self.extras)
128 return space
129
131 doc = Document()
132 root = doc.createElement('decisions')
133 doc.appendChild(root)
134 if self.branchType:
135 if self.branchType:
136 root.setAttribute('branch',self.branchType)
137 if self.key:
138 root.setAttribute('key',self.key)
139
140 node = doc.createElement('values')
141 root.appendChild(node)
142 for option in self.values:
143 subNode = doc.createElement('value')
144 if isinstance(option,str):
145
146 subNode.setAttribute('value',option)
147 subNode.setAttribute('type','literal')
148 elif isinstance(option,dict):
149 if isinstance(option['value'],DecisionSpace):
150 subNode.appendChild(option['value'].__xml__().documentElement)
151 else:
152
153 subNode.setAttribute('type',option['type'])
154 subNode.setAttribute('value',option['value'])
155 else:
156 subNode.appendChild(option.__xml__().documentElement)
157 node.appendChild(subNode)
158
159 node = doc.createElement('base')
160 root.appendChild(node)
161 if isinstance(self.base,DecisionSpace):
162 node.appendChild(self.base.__xml__().documentElement)
163 else:
164 for option in self.base:
165 node.appendChild(option.__xml__().documentElement)
166
167 for option in self.extras:
168 node = doc.createElement('option')
169 root.appendChild(node)
170 for action in option:
171 node.appendChild(action.__xml__().documentElement)
172
173 for option in self.illegal.values():
174 node = doc.createElement('illegal')
175 root.appendChild(node)
176 for action in option:
177 node.appendChild(action.__xml__().documentElement)
178 return doc
179
180 - def parse(self,element):
181 assert(element.tagName == 'decisions')
182 self.key = str(element.getAttribute('key'))
183 if len(self.key) == 0:
184 self.key = None
185 child = element.firstChild
186 while child:
187 if child.nodeType == Node.ELEMENT_NODE:
188 if child.tagName == 'option':
189 actionList = []
190 subChild = child.firstChild
191 while subChild:
192 if subChild.nodeType == subChild.ELEMENT_NODE:
193 act = Action()
194 act.parse(subChild)
195 actionList.append(act)
196 subChild = subChild.nextSibling
197 self.directAdd(actionList)
198 elif child.tagName == 'illegal':
199 actionList = []
200 subChild = child.firstChild
201 while subChild:
202 if subChild.nodeType == subChild.ELEMENT_NODE:
203 act = Action()
204 act.parse(subChild)
205 actionList.append(act)
206 subChild = subChild.nextSibling
207 self.illegal[str(actionList)] = actionList
208 elif child.tagName == 'values':
209 subChild = child.firstChild
210 while subChild:
211 if subChild.nodeType == subChild.ELEMENT_NODE:
212 if subChild.hasAttribute('type'):
213
214 value = {'type':str(subChild.getAttribute('type')),
215 'value':str(subChild.getAttribute('value')),
216 }
217 elif subChild.hasAttribute('value'):
218
219 value = str(subChild.getAttribute('value'))
220 else:
221
222 grandChild = subChild.firstChild
223 while grandChild and \
224 grandChild.nodeType != Node.ELEMENT_NODE:
225 grandChild = grandChild.nextSibling
226 value = parseSpace(grandChild)
227 self.values.append(value)
228 subChild = subChild.nextSibling
229 elif child.tagName == 'base':
230 subChild = child.firstChild
231 while subChild and subChild.nodeType != Node.ELEMENT_NODE:
232 subChild = subChild.nextSibling
233 if not subChild:
234 self.base = []
235 elif subChild.tagName == 'decisions':
236 self.base = parseSpace(subChild)
237 else:
238 self.base = []
239 while subChild:
240 if subChild.nodeType == Node.ELEMENT_NODE:
241 act = Action()
242 act.parse(subChild)
243 self.base.append(act)
244 subChild = subChild.nextSibling
245 child = child.nextSibling
246
248 """Space of possible options expressed as a disjunction of all possible values
249
250 The options generated are a disjunction over the the decision spaces in the L{values} attribute.
251 @warning: Assumes that the L{values} attribute contains a list of L{DecisionSpace} instances
252 @note: Ignores the L{base} attribute
253
254 >>> space = {'type':'OR','values':[{'type':'decision','value':decisions1},{'type':'decision','value':decisions2},...,{'type':'decision','value':'decisionsn}]}
255
256 The resulting space will have the union of actions across the decision spaces, C{decisions1} to C{decisionsn}. Keep in mind that duplicates will be included!
257 """
258 branchType = 'OR'
259
261 """Utility method that generates possible options (OR assumed)
262 @note: no duplicates returned
263 """
264 options = {}
265 self.options = []
266 for value in self.values:
267 if isinstance(value,dict):
268 value = value['value']
269 if isinstance(value,DecisionSpace):
270 for option in value.getOptions():
271 key = str(option)
272 if not options.has_key(key):
273 options[key] = True
274 self.options.append(option)
275 self._generated = 1
276
278 """Space of possible options expressed as XOR tree"""
279
280 branchType = 'XOR'
281
283 """Utility method that generates possible options (XOR assumed)"""
284 self.options = []
285 for value in self.values:
286 if isinstance(self.base,DecisionSpace):
287
288 options = self.base.getOptions()
289 for option in options:
290 newOption = []
291 for item in option:
292 newItem = copy.copy(item)
293 if isinstance(value,dict):
294 newItem[self.key] = value['value']
295 else:
296 newItem[self.key] = value
297 newOption.append(newItem)
298 self.options.append(newOption)
299 else:
300
301 option = []
302 for item in self.base:
303 newItem = copy.copy(item)
304 if isinstance(value,dict):
305 newItem[self.key] = value['value']
306 else:
307 newItem[self.key] = value
308 option.append(newItem)
309 self.options.append(option)
310 self._generated = 1
311
313 """Space of possible options expressed as AND tree"""
314
315 branchType = 'AND'
316
318 """Utility method that generates possible options (AND assumed)"""
319 self.options = self.__generateAndOptions(self.values,
320 self.base.getOptions())
321 self._generated = 1
322
324 """Utility method that composes AND options with suboptions"""
325 try:
326 value = values[0]
327 except IndexError:
328 return result
329 newResult = []
330 if isinstance(value,DecisionSpace):
331 for newOption in value.getOptions():
332 for option in result:
333 newItem = copy.copy(option)
334 newItem.append(newOption)
335 newResult.append(newItem)
336 else:
337 for option in result:
338 for base in baseOptions:
339 newOption = copy.copy(option)
340 for item in base:
341 newItem = copy.copy(item)
342 if isinstance(value,dict):
343 newItem[self.key] = value['value']
344 else:
345 newItem[self.key] = value
346 newOption.append(newItem)
347 newResult.append(newOption)
348 return self.__generateAndOptions(values[1:],baseOptions,newResult)
349
350 _spacesByType = {
351 None: DecisionSpace,
352 'XOR': XORSpace,
353 'AND': AndSpace,
354 'OR': ORSpace,
355 }
356
358 """Extracts a L{DecisionSpace} instance from an XML specification. In reality, this just identifies the correct L{DecisionSpace} subclass and then invokes the appropriate I{parse} method
359 @param element: XML element (i.e., <decisions ...>...)
360 @return: L{DecisionSpace}
361 """
362 branchType = str(element.getAttribute('branch'))
363 try:
364 cls = _spacesByType[string.upper(branchType)]
365 except KeyError:
366 cls = DecisionSpace
367 space = cls()
368 space.parse(element)
369 return space
370
372 """Returns a L{DecisionSpace} object from the given dictionary specification
373
374 @param spec: The dictionary should be structured as follows:
375 - I{type}: either C{None}, 'XOR', 'OR', or 'AND',
376 - I{base}: a dictionary specification of a L{DecisionSpace} object (optional)
377 - I{key}: key argument used for constructor (defaults to C{None})
378 - I{values}: values argument use for constructor (optional)
379 @return: The L{DecisionSpace} object represented by the spec
380 @rtype: L{DecisionSpace}
381 """
382 if spec['type'] == 'action':
383
384 action = Action(spec['values'][0])
385 subspace = DecisionSpace(base=[action])
386 return subspace
387 if spec.has_key('base'):
388 base = extractSpace(spec['base'])
389 else:
390 base = None
391 try:
392 values = spec['values']
393 except KeyError:
394 values = []
395 for value in values:
396 if value['type'] == 'decision':
397 value['value'] = extractSpace(value['value'])
398 try:
399 key = spec['key']
400 except KeyError:
401 key = None
402 if base:
403 return _spacesByType[spec['type']](key,values,base)
404 else:
405 return _spacesByType[spec['type']](key,values)
406
407 if __name__ == '__main__':
408 subSpace = XORSpace('type',[{'type':'literal',
409 'value':'hold'},
410 {'type':'literal',
411 'value':'inspect'},
412 {'type':'literal',
413 'value':'pass'}])
414 print subSpace.getOptions()
415 space = AndSpace('object',['shipperA','shipperB'],subSpace)
416 print space.getOptions()
417
418 doc = space.__xml__()
419 space = XORSpace()
420 space.parse(doc.documentElement)
421 print 'XML_----------------------'
422 print space.getOptions()
423 print 'XML_----------------------'
424 parsedDict = {'type':'XOR',
425 'key':'object',
426 'values':[{'type':'generic',
427 'value':'Shipper'}],
428 'base':{'type':'XOR',
429 'key':'type',
430 'values':[{'type':'literal',
431 'value':'hold'},
432 {'type':'literal',
433 'value':'inspect'},
434 {'type':'literal',
435 'value':'pass'}]}}
436 parsedSpace = extractSpace(parsedDict)
437 print parsedSpace.getOptions()
438
439 customerDict = {'type':'XOR',
440 'key':'object',
441 'values': [{'type':'generic','value':'Shipper'}],
442 'base':{'type':'action',
443 'values':[{'type':'shipThrough'}],
444 }
445 }
446 customerSpace = extractSpace(customerDict)
447 print customerSpace.getOptions()
448
449
450 space = extractSpace({'type':'OR',
451 'values':[{'type':'decision','value':parsedDict},
452 {'type':'decision','value':customerDict},
453 ],
454 })
455 print space.getOptions()
456
457 space = parseSpace(space.__xml__().documentElement)
458 print space.getOptions()
459