Artificial Intelligence

The outer loop of iterative widening gradually increases the bound $W$ up to a given $WMax$. The inner loop has the same skeleton as a standard graph search, with the exception that non-novel states are immediately thrown away. For now, implement iterative widening's inner loop using breadth-first search.

Your search should return the sequence of actions required to reach a goal condition from an initial condition, along with the cost of that plan. You also may want to print output describing how many nodes are visited and how much time has been taken for each value of $W$.

Iterated Widening is a pruning technique that admits a lot of different search techniques: Try it with: * Depth-First Search * Try changing the order of the recipes * the default order * randomly shuffled * sorted from lowest to highest cost * highest to lowest cost * Breadth-First Search

GIVEN:

import random def width_search(initial: State, goal: State, WMax: int) -> Tuple[int, Optional[List[str]]]: start_time = time.time() all_propositions = recipe_propositions | state_propositions(initial) | state_propositions(goal) all_combinations: List[FrozenSet[Proposition]] = [] # Increase W up to WMax for W in range(1, WMax + 1): visited = 0 # Calculate all combinations of propositions at size W and add to all_combination all_combinations += [frozenset(props) for props in itertools.combinations(all_propositions, W)] 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() # Initialize seen_combinations see_state(initial, all_combinations, seen_combinations) open_list: List[Tuple[int, State]] = [(0, initial)] best_costs: Dict[State, int] = {initial: 0} best_from: Dict[State, List[str]] = {initial: []} while open_list: visited += 1 # TODO This should look like your graph search, except... # Call see_state on newly expanded states to update seen_combinations and use its return value to decide whether to add this state to the open list (is that the only thing that determines whether it should go on the open list?) return visited, -1, None