# Copyright (c) 2009 Tim Freeman # # Permission is hereby granted, free of charge, to any person obtaining a copy # of this software and associated documentation files (the "Software"), to deal # in the Software without restriction, including without limitation the rights # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell # copies of the Software, and to permit persons to whom the Software is # furnished to do so, subject to the following conditions: # # The above copyright notice and this permission notice shall be included in # all copies or substantial portions of the Software. # # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN # THE SOFTWARE. # # (This is the standard MIT License, copied from # http://www.opensource.org/licenses/mit-license.php on 24 Apr 2007.) #desc Utilities to generate plans. from bits import copy_add, map_append # A "plan" is something with a step method that takes a perception as # an argument and returns a (behavior, subsequent plan) pair. # A "plan generator" is a callable that takes these keyword arguments: # perceptions -- a list of possible perceptions, # behaviors -- a list of possible behaviors, # horizon -- an integer, which is the planning horizon # and returns an iterable that's a list of plans. # one_action_plan(act) is a plan that ignores all perceptions and does # act all the time. class one_action_plan(object): __slots__=["action"] def __init__(self, action): self.action = action def step(self, perception): # No matter what we perceive, we take the specified action, # and the subsequent plan is the same as the original plan. return (self.action, self) # dict_to_plan(d) converts d to a plan. # d must be either None (in which case the plan will raise an error # when you take any steps) or a dict mapping possible perceptions to # (behavior, subsequent plan) pairs. In d, the subsequent plans are # also dict's with the same format as d. # If we step past the end (because d is None) we raise an Exception. # If a perception happens that we aren't prepared for, we raise an Exception. class dict_to_plan(object): __slots__=["d"] def __init__(self, d): assert d is None or type(d) == dict, \ "d should be a dict or None, it is %r" % (d,) self.d = d # Claim the plan has the given depth. If we want to use more # general lazily computed plans, we may not be able to easily get # the depth, and in that case assert_has_depth will do nothing. # We need it to be defined for all plans because of checks # in infer_utility. # If the plan has varying depth depending on what is perceived, # we'll get flakey results. def get_depth(self): # private method. if self.d is None: return 0 else: (behaviors, rest) = self.step(self.d.keys()[0]) return rest.get_depth() + 1 def assert_has_depth(self, desired_depth): actual_depth = self.get_depth() assert actual_depth == desired_depth, \ "Expected depth %d, actual depth was %d" % (\ desired_depth, actual_depth) def step(self, perception): if self.d is None: raise Exception("Plan is too short when reacting to perception %r" % (perception,)) else: try: (behavior, moreplan) = self.d[perception] except KeyError: raise Exception("No plan for perception %r" % (perception,)) return (behavior, dict_to_plan(moreplan)) def __str__(self): return "dict_to_plan(%r)" % (self.d,) def __repr__(self): return self.__str__() # list_to_plan(*l) converts l, which is a list of actions, to a plan. # The plan ignores the perceptions. class list_to_plan(object): __slots__=["list"] def __init__(self, *list): self.list = list def step(self, perception): # Ignore perception if len(self.list) <= 0: raise Exception("Walked off the end of the plan") else: return (self.list[0], list_to_plan(*self.list[1:])) def assert_has_depth(self, desired_depth): depth = len(self.list) assert depth == desired_depth, \ "Actual depth of %r is %r, desired depth was %r" % ( self, depth, desired_depth) def __repr__(self): return "list_to_plan(" + ",".join(map(repr, self.list)) + ")" def __cmp__(self, other): return cmp(self.list, other.list) # exhaustive simply returns a list of all possible # plans. This can easily be way too many, if there are too many # possible perceptions. # # horizon is the number of times you can successfully step any of the # resulting plans. # # Suppose: # p(n) is the number of plans of horizon n. # a is the number of possible behaviors. # per is the number of possible perceptions. # Then: # p(0) = 1. # p(n) = (a * p(n-1)) ** per. # This grows very rapidly, so a practical implementation would require a # different representation for plans. # # If there are 4 possible perceptions and 2 possible behaviors: # For horizon 1 we have 16 plans. Practical. # For horizon 2 we have 2**20 possible plans, about a million. Not possible # with my present hardware and software. # If there are 2 possible perceptions and 2 possible behaviors: # For horizon 1 we have 4 plans. # For horizon 2 we have 64 plans. def exhaustive(perceptions=None, behaviors=None, horizon=None): assert perceptions != None assert behaviors != None assert type(horizon) == int or type(horizon) == long def doit(horizon): if horizon == 0: return [None] else: behavior_plan_pairs = all_behavior_plan_pairs(horizon-1) sofar = [{}] for per in perceptions: next = [] for bp in behavior_plan_pairs: for d in sofar: next.append(copy_add(d, per, bp)) sofar = next return sofar def all_behavior_plan_pairs(horizon): rest_plans = doit(horizon) def behavior_plan_pairs(b): return [(b, p) for p in rest_plans] return map_append(behavior_plan_pairs, behaviors) return map(dict_to_plan, doit(horizon))