The program is written in Python using Pycharm's notebook feature. I have posted where I am stuck on this work. Please review and see where I am going wrong. Thank you.

you will be making a simple satisficing Minecraft crafting planner. Given an initial state, you will want to find a series of actions that gets you to a desired goal state. For fun, you will also use your implementations for Dijkstras and A* to show how they don't do well in a search space this large (without a lot of tweaking).

you will:

Parse and process a data file into a format that is usable in your code

make a representation of a state space such that you can check preconditions and apply effects in an efficient manner

make a method to convert the intuitive predicate based state system into a propositional system

Implement Width-Search utilizing Iterative Widening to efficiently find a plan that gets from an arbitrary state space to a desired state space

Compare Width-Search to optimal search methods such as Dijkstra's and A* to see how they compare in what they can efficiently solve

The goal of this assignment is for you to understand:

How to manipulate data (a boring, but CRUCIAL skill)

How to navigate a state space that doesn't map to standard geometry (i.e., domains outside of palt

How the pruning of a search space can result in a drastic reduction in the time spent performing the search

First we will load in crafting.json, a json file that

In [42]:

import json

from typing import NamedTuple, Dict, Tuple, Optional, Sequence, List, Set, FrozenSet

import array

import heapq

import time

import itertools

with open('Crafting.json') as f:

Crafting = json.load(f)

# List of items that can be in your inventory:

print(Crafting['Items'])

# example: ['bench', 'cart', ..., 'wood', 'wooden_axe', 'wooden_pickaxe']

# List of items needed to be in your inventory at the end of the plan:

# (okay to have more than this; some might be satisfied by initial inventory)

print(Crafting['Goal'])

# {'stone_pickaxe': 2}

# Dict of crafting recipes (each is a dict):

print(Crafting['Recipes']['craft stone_pickaxe at bench'])

# example:

# { 'Produces': {'stone_pickaxe': 1},

# 'Requires': {'bench': True},

# 'Consumes': {'cobble': 3, 'stick': 2},

# 'Time': 1

# }

['bench', 'cart', 'coal', 'cobble', 'furnace', 'ingot', 'iron_axe', 'iron_pickaxe', 'ore', 'plank', 'rail', 'stick', 'stone_axe', 'stone_pickaxe', 'wood', 'wooden_axe', 'wooden_pickaxe']

{'stone_pickaxe': 1}

{'Produces': {'stone_pickaxe': 1}, 'Requires': {'bench': True}, 'Consumes': {'cobble': 3, 'stick': 2}, 'Time': 1}

Let's reflect a little bit.

Do the recipe dictionaries in crafting.json all have the same set of keys? Print out a few to find out, or read the JSON file.

What is similar about the Initial, Goal, Produces, Consumes, and Requires schema? What is different about them?

Thinking back to your data structures class, what operations are involved in looking up a key in a dictionary data structure, and how does that compare to obtaining values from an array?

Look this up if you need to: What is the difference between a Python List of integers and a Python array.array of integers?

Let's proceed by using the same data representation for an inventory state (as in Initial), a partial inventory state (as in Goal, Produces, and Consumes), and the inventory query posed by Requires. Because the speed of the inner loop is of supreme importance in graph search, we'll want to use an array of unsigned integers data representation for each of these (this may feel like premature optimization; also try by comparing it with a simple dict-based representation). In order to go back and forth between item names and item indices, let's define a couple of global variables:

In [43]:

items_by_index = list(sorted(Crafting['Items']))

items_to_indices = {item: index for index, item in enumerate(items_by_index)}

We'll wrap our array-of-items data structure in a convenience class called State. Because we'll need to put States into closed sets, priority queues, and so on, we'll need them to be hashable, equatable, and comparable. We also will need to be adding and subtracting inventory states from each other later on, so we'll put that in there too. A skeleton of this class is provided below, with some of the data handling code given.

In [44]:

class State:

items: array.array

def __init__(self, items: Optional[Sequence[int]] = None) -> None:

if items is not None:

# Copying a state from an old state.

# This call to the array constructor creates an array of unsigned integers and initializes it from the contents of items.

self.items = array.array('I', items)

else:

self.items = array.array('I', [0 for item in items_by_index])

def __add__(self, other:'State')->'State':

s = State(self.items)

x = State(other.items)

for i,y in enumerate(items_by_index):

s.items[i] += x.items[i]

return s

def __sub__(self, other:'State')->'State':

s = State(self.items)

# TODO How do you subtract one state from another

x = State(other.items)

for i,j in enumerate(items_by_index):

s.items[i] -= x.items[i]

return s

def __ge__(self, other:'State')->bool:

s = State(self.items)

# TODO How do we know whether one state (self) contains everything that's inside of another (other)?

x = State(other.items)

for i,j in enumerate(items_by_index):

if(s.items[i] < x.items[i]):

return False

return True

def __lt__(self, other:'State')->bool:

return not (self >= other)

def __eq__(self, other:'State')->bool:

return self.items == other.items

def __hash__(self)->int:

hsh = 5381

for s in self.items:

hsh = ((hsh << 5) + hsh) + s

return hsh

def __str__(self)-> str:

out_str = []

for k,v in self.to_dict().items():

out_str.append('{}:{}'.format(k,v))

return ', '.join(out_str)

def to_dict(self) -> Dict[str, int]:

return {items_by_index[idx]: self.items[idx]

for idx in range(len(self.items))}

@classmethod

def from_dict(cls, item_dict: Dict[str, int]) -> 'State':

return cls([

item_dict.get(item, 0) for item in items_by_index

])

At this point we can already solve trivial problems:

In [45]:

# Example

initial = State.from_dict({'stone_pickaxe':1, 'ingot':2})

goal = State.from_dict({'ingot':1})

print()

print(initial)

print()

print(goal)

print()

print()

print(initial >= goal)

print(goal < initial)

print(goal >= initial)

bench:0, cart:0, coal:0, cobble:0, furnace:0, ingot:2, iron_axe:0, iron_pickaxe:0, ore:0, plank:0, rail:0, stick:0, stone_axe:0, stone_pickaxe:1, wood:0, wooden_axe:0, wooden_pickaxe:0

bench:0, cart:0, coal:0, cobble:0, furnace:0, ingot:1, iron_axe:0, iron_pickaxe:0, ore:0, plank:0, rail:0, stick:0, stone_axe:0, stone_pickaxe:0, wood:0, wooden_axe:0, wooden_pickaxe:0

True

True

False

Now that we have our state representation, we can rephrase the recipes in terms of what they need from the state.

Python has a useful datastructure -- namedtuple -- we can use for this purpose, so we'll have a namedtuple type called Recipe.

In [46]:

class Recipe(NamedTuple):

produces: State

consumes: State

requires: State

cost: int

It acts like a tuple in that its data are laid out contiguously in memory and it is immutable, but it has convenient accessors. Let's initialize a dictionary mapping names to recipes:

In [47]:

recipes: Dict[str, Recipe] = {}

for name, rule in Crafting['Recipes'].items():

recipes[name] = Recipe(

State.from_dict(rule.get('Produces', {})),

State.from_dict(rule.get('Consumes', {})),

State.from_dict({item: 1 if req else 0

for item, req in rule.get('Requires', {}).items()}),

rule['Time']

)

Now we have our state representation and our action representation for the crafting domain. Let's reflect.

What was the state representation in the path planning assignment?

What was the action representation?

How many possible actions are there in the whole domain, and how many of those are possible in a given state?

In fact, we can consider any planning problem in terms of states and a transition relation between states and those actions which are valid in that state. If we're thinking about path planning as search on the graph of possible locations (with edges given by a connectedness relation), task planning can be seen as search on the graph of possible states (with edges given by the state transition relation). Let's implement the transition relation now:

In [48]:

def preconditions_satisfied(state: State, recipe: Recipe) -> bool:

# TODO What needs to be true about state and recipe?

# Feel free to use State's >= method

consumes = recipe[1]

requires = recipe[2]

if(state >= requires and state >= consumes):

return True

return False

def apply_effects(state: State, recipe: Recipe) -> State:

#TODO What happens when a recipe is used?

produces = recipe[0]

consumes = recipe[1]

temp = state - consumes + produces

return temp

initial = State.from_dict({'stone_pickaxe':1, 'ingot':2})

print()

#Let's try using the pickaxe

if preconditions_satisfied(initial,recipes['stone_pickaxe for cobble']):

print('Stone Pickaxe',apply_effects(initial,recipes['stone_pickaxe for cobble']))

print()

if preconditions_satisfied(initial,recipes['wooden_pickaxe for cobble']):

print('Wooden Pickaxe',apply_effects(initial,recipes['wooden_pickaxe for cobble']))

Stone Pickaxe bench:0, cart:0, coal:0, cobble:1, furnace:0, ingot:2, iron_axe:0, iron_pickaxe:0, ore:0, plank:0, rail:0, stick:0, stone_axe:0, stone_pickaxe:1, wood:0, wooden_axe:0, wooden_pickaxe:0

**Planning via Graph Search**

Remember back to BFS. Consider how the one presented in class would need to change so it works on states-and-actions instead of locations-and-directions?

Let's try it:

In [55]:

def able_to_do(state:State) -> Tuple[List[State],List[str]]:

x = []

y = []

for recipe in recipes:

recipe_1 = recipes[recipe]

if(preconditions_satisfied(state,recipe_1)):

x.append(apply_effects(state,recipe_1))

y.append(recipe)

return (x,y)

test = State.from_dict({'stone_pickaxe':1, 'ingot':2})

#print(able_to_do(test))

hi

hi 2

herekkk

(419, ['craft stone_pickaxe at bench', 'wooden_pickaxe for cobble^^', 'wooden_pickaxe for coal^^', 'wooden_pickaxe for coal^*', 'wooden_pickaxe for coal^', 'craft wooden_pickaxe at bench^', 'craft bench^^^^', 'punch for wood^^^^^^^^', 'craft plank^^^^', 'punch for wood^^^^^^^', 'craft plank^^^', 'punch for wood^^^^^^', 'punch for wood^^^^^*', 'punch for wood^^^^^', 'punch for wood^^^^*', 'punch for wood^^^^', 'craft plank^^', 'punch for wood^^^', 'craft plank^', 'punch for wood^^', 'craft stick*', 'craft stick', 'craft plank', 'punch for wood', 'start'])

hi 2

herekkk

(10332, ['smelt ore in furnace', 'stone_pickaxe for cobble^^^^^^^^^^', 'stone_pickaxe for cobble^^^^^^^^^*', 'stone_pickaxe for cobble^^^^^^^^^', 'stone_pickaxe for cobble^^^^^^^^*', 'stone_pickaxe for cobble^^^^^^^^', 'stone_pickaxe for cobble^^^^^^^*', 'stone_pickaxe for cobble^^^^^^^', 'stone_pickaxe for coal^^^^^^', 'stone_pickaxe for ore^^^^^', 'stone_pickaxe for ore^^^^*', 'stone_pickaxe for ore^^^^', 'stone_pickaxe for ore^^^*', 'stone_pickaxe for ore^^^', 'stone_pickaxe for ore^^*', 'stone_pickaxe for ore^^', 'punch for wood^^', 'craft stick*', 'craft stick', 'craft plank', 'punch for wood', 'start'])

Imagine applying Dijkstra's here. How would things change? Image applying A* here. What heuristic would you want to use? Is that heuristic admissible? Is that a problem?

What's the largest planning problem (initial and goal state) you can think up which your BFS implementation can solve within 30 seconds? How many nodes does it visit and how long does it take in wall-clock time?

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.

In graph search, what is the goal of a search? How is that different from the goal of a planning problem?

In graph search, what are the preconditions for traversing an edge? How does this differ in a planning problem?

In graph search, detecting cycles is relatively cheap. Is that the case for planning problems?

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

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