Can you show me how to use iterative widening on a python project. The project i
ID: 3751814 • Letter: C
Question
Can you show me how to use iterative widening on a python project. The project is minecraft themed, and therefore movements and objects are based off it. Below I posted questions and answers I have so far. Please see comments marked TODO, I need help implementing those. Thanks.
Think about a recipe like making a stone pickaxe. Every possible planning state either satisfies its preconditions or doesn't. If this recipe were the only action, we could formulate the problem as a domain with just three abstract states---one without a pickaxe and without the needed supplies, one without a pickaxe and with the needed supplies, and one with a pickaxe (and it doesn't matter what else is in the state).
If we had a domain with just two recipes (punch for wood and wood planks), what would be the abstract states in the sense used above?
We can automate the intuition of (15) by transforming our states into combinations of propositions A proposition here is a logical fact entailed by the state; for example I have at least one piece of wood, I have at least two pieces of wood, I have at least one plank, and so on. Note that if we have two pieces of wood then we necessarily have one piece of wood as well! Iterated Widening is a planning algorithm which works by abstracting away differences between states and discarding states which are too similar to states which have been seen already in this iteration. Two states are similar if they share some number of propositions in common---so if the width measure is one, then when we have seen one state where we have at least one stick we subsequently ignore every other state we might find later with one or more sticks (we'll relax this a little to say "any sufficiently different state is worth exploring"---so if it has at least a few propositions that are unique with respect to all seen combinations of a given width, we will consider it). To regain completeness---to always find a solution if one exists---the size of the combinations of items considered in this similarity computation is gradually increased until a solution is found.
Now we will define a Proposition of the form I have at least N of item INDEX
Then we will define a function that takes in a state and propositionalizes it. E.g.
If we have: items_by_index = ['wood', 'cobble', 'bench'] and our current state is: {'wood':5, 'bench':1}
then propositionalized version should be a set of: Proposition(1,5), Proposition(1,4), Proposition(1,3), Proposition(1,2), Proposition(1,1), Proposition(3,1)
i.e. we have at least 1,2,3,4, and 5 pieces of wood, and at least 1 bench.
In [ ]:
class Proposition(NamedTuple):
item: int
at_least: int
def state_propositions(state: State) -> Set[Proposition]:
propositions: Set[Proposition] = set()
# TODO Do something for each item in state. Output all propositions entailed by the state's contents
state_array = state.items
items_by_index
for index in range(len(items_by_index)):
if(state_array[index] > 0):
for at_least in range(state_array[index]):
temp_tuple = Proposition(index,at_least+1)
#print(temp_tuple)
propositions.add(temp_tuple)
return propositions
Now let's get the propositions from the recipes
In [ ]:
def recipe_to_propositions(recipe: Recipe) -> Set[Proposition]:
propositions: Set[Proposition] = set()
# TODO Do something with recipe.consumes, recipe.produces, and recipe.requires.
# Emit, for this recipe, all the propositions entailed by the postconditions
#and the _minimal_ set of propositions required for the preconditions
#(i.e., don't need to output wood >= 2, wood >= 1, wood >= 0 if the recipe needs 2 wood.)
consumes = recipe[1]
requires = recipe[2]
what_you_need = consumes+requires
propositions = state_propositions(what_you_need)
#print(propositions)
return propositions
recipe_propositions = set()
for r in recipes:
recipe_propositions |= recipe_to_propositions(recipes[r])
#print(recipe_propositions)
Explanation / Answer
class Proposition(NamedTuple):
item: int
at_least: int
def state_propositions(state: State) -> Set[Proposition]:
propositions: Set[Proposition] = set()
for i in range(len (state.items)) :
for k in range(1,state.items[i]+1):
propositions.add(Proposition(i,k))
return propositions
def recipe_to_propositions(recipe: Recipe) -> Set[Proposition]:
propositions: Set[Proposition] = set()
# G. Do something with recipe.consumes, recipe.produces, and recipe.requires.
# Emit, for this recipe, all the propositions entailed by the preconditions and the _minimal_ set of propositions embodied in the preconditions (i.e., don't need to output wood >= 2, wood >= 1, wood >= 0 if the recipe creates 2 wood.)
r = state_propositions(recipe.requires)
p = state_propositions(recipe.produces)
c = state_propositions(recipe.consumes)
propositions |= r
propositions |= c
propositions |= p
return propositions
def preconditions_satisfied(state: State, recipe: Recipe) -> bool:
if ( state >= recipe.requires and state >= recipe.consumes) :
return True
return False
def apply_effects(state: State, recipe: Recipe) -> State:
# E. How do you make a new state out of a state and a recipe?
# Note, DO NOT change state in-place!
newstate = state - recipe.consumes + recipe.produces
return newstate
def see_state(state:State, combinations:List[Set[Proposition]], seen_combinations:Set[FrozenSet[Proposition]]) -> bool:
any_new = False
state_props = state_propositions(state)
for combo in combinations:
if combo in seen_combinations:
continue
if(state_props.issuperset(combo)) :
seen_combinations.add(combo)
any_new = True
return any_new
recipe_propositions = set()
for r in recipes.values():
recipe_propositions |= recipe_to_propositions(r)
def plan_dijkstra(initial: State, goal: State, limit:int) -> Tuple[int, int, Optional[List[str]]]:
start_time = time.time()
open_list: List[Tuple[int, State,str]] = [(0, initial, "")]
best_costs: Dict[State, Tuple[int, str,State]] = {initial:(0, "",initial)}
visit_count = 0
found = False
while open_list:
# Dijkstra's search uses the priority queue data structure
cost, curstate , gotfrom = heapq.heappop(open_list)
#print("cost=",cost,"curstate=",curstate,"from=",gotfrom)
if(curstate >= goal):
x,rname,z = best_costs.get(curstate)
print ("found it!! Number of visited nodes=" ,visit_count , "state=",curstate,"goal=",goal,"by=",rname)
found = True;
break;
visit_count += 1
if(visit_count > limit) :
print("too many iterations , current state=",curstate)
break
for candidaterecipename in recipes:
if (preconditions_satisfied(curstate,recipes[candidaterecipename])) == False:
continue
candidatestate = apply_effects(curstate,recipes[candidaterecipename])
if(candidatestate in best_costs):
#print("found=" , neighbor)
candidatestate_cost,rname,fromstate = best_costs.get(candidatestate)
if(candidatestate_cost > cost + recipes[candidaterecipename].cost) :
#print("update cost for ", neighbor ,"newcost", cost + neighbor_cost)
best_costs[candidatestate] = (cost + recipes[candidaterecipename].cost , gotfrom, curstate )
heapq.heappush (open_list, (cost + recipes[candidaterecipename].cost, candidatestate, candidaterecipename ) )
else:
#print(neighbor ,"newcost", cost + neighbor_cost)
best_costs[candidatestate] = (cost + recipes[candidaterecipename].cost , gotfrom,curstate )
heapq.heappush (open_list, (cost + recipes[candidaterecipename].cost, candidatestate, candidaterecipename ) )
if(found == False) :
return (visit_count, -1, None)
state = curstate
bestcost,dummy1,dummy2 = best_costs.get(state)
retpath: List[str] = []
while(1):
cost,rname,fromstate = best_costs.get(state)
if(rname == "") :
break;
retpath.insert(0,rname)
state = fromstate
print("plan_dijkstra visited=",visit_count,"best_cost=",bestcost,"retpath=",retpath)
return (visit_count, bestcost, retpath)
def plan_width(initial: State, goal: State, WMax: int) -> Tuple[int, int, Optional[List[str]]]:
all_propositions = recipe_propositions | state_propositions(initial) | state_propositions(goal)
all_combinations: List[FrozenSet[Proposition]] = []
for W in range(1, WMax + 1):
start_time = time.time()
visit_count = 0
# Calculate all combinations of propositions at size W and add to all_combinations
all_combinations += [frozenset(props) for props in itertools.combinations(all_propositions, W)]
# Sanity check that this is 6279 for W=3, for example
print("W=",W,"Combination count=",len(all_combinations))
# Track, for each combination (by index), whether we have seen this combination before (0 for no, >0 for yes)
seen_combinations: Set[FrozenSet[Proposition]] = set()
open_list: List[Tuple[int, State,str]] = [(0, initial, "")]
best_costs: Dict[State, Tuple[int, str,State]] = {initial:(0, "",initial)}
found = False
while open_list:
# Dijkstra's search uses the priority queue data structure
cost, curstate , gotfrom = heapq.heappop(open_list)
#print("cost=",cost,"curstate=",curstate,"from=",gotfrom)
if(curstate >= goal):
x,rname,z = best_costs.get(curstate)
print ("found it!! Number of visited nodes=" ,visit_count , "state=",curstate,"goal=",goal,"by=",rname)
found = True;
break;
visit_count += 1
for candidaterecipename in recipes:
if (preconditions_satisfied(curstate,recipes[candidaterecipename])) == False:
continue
candidatestate = apply_effects(curstate,recipes[candidaterecipename])
IsAddingValue = see_state(candidatestate,all_combinations,seen_combinations)
if(IsAddingValue == False):
continue
if(candidatestate in best_costs):
#print("found=" , neighbor)
candidatestate_cost,rname,fromstate = best_costs.get(candidatestate)
if(candidatestate_cost > cost + recipes[candidaterecipename].cost) :
#print("update cost for ", neighbor ,"newcost", cost + neighbor_cost)
best_costs[candidatestate] = (cost + recipes[candidaterecipename].cost , gotfrom, curstate )
heapq.heappush (open_list, (cost + recipes[candidaterecipename].cost, candidatestate, candidaterecipename ) )
else:
#print(neighbor ,"newcost", cost + neighbor_cost)
best_costs[candidatestate] = (cost + recipes[candidaterecipename].cost , gotfrom,curstate )
heapq.heappush (open_list, (cost + recipes[candidaterecipename].cost, candidatestate, candidaterecipename ) )
if(found == False) :
continue
state = curstate
bestcost,dummy1,dummy2 = best_costs.get(state)
retpath: List[str] = []
while(1):
cost,rname,fromstate = best_costs.get(state)
if(rname == "") :
break;
retpath.insert(0,rname)
state = fromstate
print("plan_width: visited=",visit_count,"best_cost=",bestcost,"retpath=",retpath)
return (visit_count, bestcost, retpath)
return visit_count, -1, None
#print(items_to_indices)
#print(Crafting['Items'])
#print(Crafting['Goal'])
#print(Crafting['Recipes']['craft stone_pickaxe at bench'])
# Example
initial = State.from_dict({'stone_pickaxe':1, 'ingot':2})
goal = State.from_dict({'ingot':1})
assert(initial >= goal)
#print("initial",initial)
#print("goal",goal)
#all = initial + goal
#print("all",initial + goal)
#print(plan_dijkstra(State.from_dict({'wood':1}),State.from_dict({'iron_pickaxe':1}),200000))
print(plan_width(State.from_dict({'wood':1}),State.from_dict({'iron_pickaxe':1}),4))
'''
#print(plan_dijkstra(State.from_dict({}),
State.from_dict({'stone_pickaxe':1}),
200000))
#print(plan_dijkstra(State.from_dict({'bench':1,'stone_pickaxe':1}),
State.from_dict({'ingot':1}),
200000))
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.