Artificial Intelligence

**Planning with Iterated Widening**

Let's compare against a dedicated planning algorithm, rather than applying graph search naively. Planning domains have some significant differences from general graph search problems---let's reflect on what they might be. 11. In graph search, what is the goal of a search? How is that different from the goal of a planning problem? 12. In graph search, what are the preconditions for traversing an edge? How does this differ in a planning problem? 13. In graph search, detecting cycles is relatively cheap. Is that the case for planning problems? 14. Is there more than one type of "cycle" in our crafting planning problem?

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). 15. 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.

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 return propositions

Now let's get the propositions from the recipes

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.) return propositions recipe_propositions = set() for r in recipes: recipe_propositions |= recipe_to_propositions(recipes[r])