Introduction to Artificial Intelligence - Homework Assignment 01 (20pts.)

This assignment covers the following topics:

Please complete all sections. Some questions will require written answers, while others will involve coding. Be sure to run your code cells to verify your solutions.

Your team quickly arrives at central park, making sure to save all the travel reciepts so you can expense it to your Professor. If you have to miss the playoff game for this you're going to give him the worst CIF score known to man.

As you all stand around the duck pond, a detective walks up to you and introduces himself as Detective Caulfield.

You quickly slip your flask into your jacket.

"No time for questions, we need you to get to the William Theisen-Floyd Estate as soon as possible, cost is no object."

You thankfully sigh, knowing that those new congestion charges have been draining your bank account. As you start walk away and try to figure out how to get out to the estate (unfortunately the office said a blade was out of the question), you recall an algorithm that may be able to help you get to the estate! You could use a search or traversal algorithm to pick the most efficient path between the duck pond in Central Park and the Estate out on LI.

Section 1: Search Algorithms (8 pts.)

In this section, you'll need to use the map given to you by the detective to get from Central Park to the William Theisen-Floyd Estate in the Hamptons in the least amount of time possible.

Map

The map the detective gave you has a number of travel options you could use, depending on the location you're in. There's taxis of course, but you could also take the train (public transport, who knew). Additionally, several locations have outgoing flights and even ferries you could take.

Luckily, after an absolutely staggering amount of painstaking research during his winter vaction to San Juan, the detective has provided you (in minutes) geographically accurate travel times for each mode of travel between each connected location as an adjacency list.

Part 1: Uninformed Search (Djikstra's Algorithm) (5 pts.)

Thinking back to class, the first thing that comes to mind is Djikstra's algorithm. You figure that's a pretty good place to start, especially given that the map the detective gave you doesn't have any heuristic information to make use of.

In the cell below, write an implementation of Djikstra's algorithm and calculate:

import heapq
##### SETTING UP THE GRPAH #####
# The map above is translated into a directed graph, where places are nodes and possible transportation between places is edges

# Dicionary assigning a number (key) to the name of each place (value)
node_number_to_name = {
    0: 'Central Park',
    1: 'Grand Central Station',
    2: 'LGA',
    3: 'Norwalk',
    4: 'Jamaica',
    5: 'JFK',
    6: 'Bridgeport',
    7: 'BDR',
    8: 'Port Jefferson',
    9: 'Huntington',
    10: 'Massapequa',
    11: 'KISP',
    12: 'Patchogue',
    13: 'William Theisen-Floyd Estate',
}

# Adjacency List for the graph
#   Each key is a node, and the value is a dictionary of neighbors and their edge weights
#   Ex: Node: {Neighbor N: (Taxi, Train, Ferry, Flight)}

graph = {
    0: {1: (8, 22, 0, 0)},                                                             # Central Park to Grand Central (Taxi: 10 min, Train: 5 min)
    1: {2: (16, 48, 0, 0), 3: (63, 64, 0, 0), 4: (34, 43, 0, 0), 9: (61, 100, 0, 0)},  # Grand Central connections
    2: {5: (0, 0, 0, 31), 7: (0, 0, 0, 36), 11: (0, 0, 0, 35)},                        # LGA connections
    3: {6: (20, 35, 0, 0), 9: (0, 0, 26, 0)},                                          # Norwalk connections
    4: {5: (15, 23, 0, 0), 9: (47, 72, 0, 0), 10: (41, 45, 0, 0)},                     # Jamaica connections
    5: {7: (0, 0, 0, 36), 11: (0, 0, 0, 34), 13: (0, 0, 90, 0)},                       # JFK connections
    6: {8: (0, 0, 75, 0)},                                                             # Bridgeport connections
    7: {6: (10, 48, 0, 0), 11: (0, 0, 0, 33)},                                         # BDR connections
    8: {12: (28, 56, 0, 0)},                                                           # Port Jefferson connections
    9: {8: (48, 60, 0, 0)},                                                            # Huntington connections
    10: {12: (34, 52, 0, 0), 13: (0, 0, 40, 0)},                                       # Massapequa connections
    11: {12: (13, 24, 0, 0)},                                                          # KISP connections
    12: {13: (23, 47, 0, 0)},                                                          # Patchogue connections
    13: {}                                                                             # William Theisen-Floyd Estate connections
}
##### WRITE DIJKSTRAS_MULTI_MODE AND PRINT_BEST_PATH_TO_ESTATE FUNCTIONS #####
def dijkstra_multi_mode(graph, start):
    """
    Dijkstra's algorithm with support for multiple transport modes.

    Args:
    - graph: Dictionary representing the graph with multi-mode costs.
    - start: Starting node.

    Returns:
    - distances: Dictionary with the shortest distance to each node from the start.
    - paths: Dictionary with the best path to each node.
    - nodes_visited: Count of how many nodes were visited.
    - edges_evaluated: Count of how many edges were evaluated.
    """

    # TODO: Initialize priority queue to state (distance, vertex) pairs
    priority_queue = ...


    # TODO: Create and initialize a data strucutre to store the distances
    distances = ...
    distances[start] = ...

    # TODO: Create and initialize a data structure to store the best paths to each node discovered so far
    paths = ...
    paths[start] = ...

    # TODO: Initialize data structure to track visited nodes
    visited = ...

    # TODO: Initialize counters to count number of visited nodes and evaluated edges
    nodes_visited = ...
    edges_evaluated = ...

    # Traverse the graph
    while priority_queue:
        # TODO: Get the vertex with the smallest distance
        current_distance, current_vertex = ...

        # TODO: Process the current vertex


        # TODO: Expand the current vertex (check all neighbors of current vertex)
        for neighbor, costs in graph[current_vertex].items():
            # hints:
            #     Increment evaluated edge counter
            #     Find cheapest possible mode of transport
            #     Update distances data structure if there is a better path to a node discovered than the priviously recorded best path


    return distances, paths, nodes_visited, edges_evaluated

def print_best_path_to_estate(paths, graph, node_number_to_name, start, destination):
    """
    Prints the best path from the start node to the destination node with transport modes and times,
    without repeating node names.

    Args:
    - paths: Dictionary of shortest paths to each node.
    - graph: The adjacency list with costs for transport modes.
    - node_number_to_name: Dictionary mapping node numbers to their names.
    - start: The start node number.
    - destination: The destination node number.
    """
    mode_names = ["TAXI", "TRAIN", "FERRY", "FLIGHT"]

    # TODO: Get the best path from start to destination
    # hint: reference your paths dictionary using the destinatoin variable as the key, make sure to check if the path is valid)
    ...

    # TODO: Make data structure to for edges used in path, initialize data structure, track total time
    path_segments =
    path_segments.append(...)
    total_time =

    # Loop through path
    for i in range(len(path) - 1):
        # TODO: Find mode of transport used (the minimum non-zero cost)
        ...

        # Append the segment with transport mode and time
        path_segments.append(f" ---[{mode}, {time} min]--> {node_number_to_name[next_node]}")
        total_time += time

    # Join the path segments and print the result
    print(f"Best path from {node_number_to_name[start]} to {node_number_to_name[destination]}:")
    print("".join(path_segments))
    print(f"Total travel time: {total_time} minutes")
##### RUN FUNCTIONS TO FIND PATH #####
# Using the previously defined `graph`
start_node = 0  # Central Park

# Find the shortest path
distances, paths, nodes_visited, edges_evaluated = ...
print(f"Number of nodes visited: {nodes_visited}")
print(f"Number of edges evaluated: {edges_evaluated}")

# Print the best path
print_best_path_to_estate(paths, graph, node_number_to_name, start=0, destination=13)
Expected Output:

Number of nodes visited: 14

Number of edges evaluated: 25

Best path from Central Park to William Theisen-Floyd Estate:

Central Park ---[TAXI, 8 min]--> Grand Central Station ---[TAXI, 16 min]--> LGA ---[FLIGHT, 35 min]--> KISP ---[TAXI, 13 min]--> Patchogue ---[TAXI, 23 min]--> William Theisen-Floyd Estate

Total travel time: 95 minutes

Well that's a pretty good start. However as you start walking away to follow the quickest path your team found, Detective Caulfield suddenly chases you down. Wordlessly he hands you another sheet of paper.

Nervously you unfold it, hoping it's not more work but much to your relief it's actually heuristic estimates! Using this information you may be able to calculate an even better path to the estate! Heuristic estimates means that you can now use an informed search method, so you and your team bunker down in an Sbarro (best New York slice) to recalculate the best path using the A* algorithm.

Part 2: Informed Search (A*) (1 pts.)

Copy your code from above and then modify it to make use of the heuristic information provided in the table below. Calculate:

heuristics = {
    0: 90,   # Central Park
    1: 80,   # Grand Central Station
    2: 70,   # LGA
    3: 75,   # Norwalk
    4: 65,   # Jamaica
    5: 50,   # JFK
    6: 60,   # Bridgeport
    7: 55,   # BDR
    8: 45,   # Port Jefferson
    9: 60,   # Huntington
    10: 30,  # Massapequa
    11: 40,  # KISP
    12: 20,  # Patchogue
    13: 0    # William Theisen-Floyd Estate
}

import heapq

def a_star(graph, heuristics, start, destination):
    """
    A* algorithm for finding the shortest path in a graph.

    Args:
    - graph: Dictionary representing the adjacency list with travel costs for multiple modes.
    - heuristics: Dictionary of heuristic values for each node.
    - start: The starting node.
    - destination: The destination node.

    Returns:
    - path: List of nodes representing the shortest path from start to destination.
    - cost: Total travel cost of the shortest path.
    - nodes_visited: Number of nodes visited.
    - edges_evaluated: Number of edges evaluated.
    """
    # TODO: Priority queue for nodes to explore (f(n), node, g(n), path)
    priority_queue =
    heapq.heappush(____, _____)

    # Dictionary to store the best g(n) value for each node
    g_costs = {node: float('inf') for node in graph}
    g_costs[start] = 0

    # TODO: Track visited nodes and count nodes visited and edges evaluated
    visited =
    nodes_visited =
    edges_evaluated =

    while priority_queue:
        # TODO: Get the node with the smallest f(n)
        _, current_node, current_g_cost, path =

        # TODO: If the current node has already been visited, skip it


        # TODO: Mark the current node as visited, increment the visted counter


        # TODO: If we reach the destination, return the results


        # TODO: Explore neighbors
        for neighbor, costs in graph[current_node].items():
            # hints:
            #     increment evaluated edge counter
            #     fund minimum cost of all available transport modes
            #     Update g(n) and then update g_costs if the path improves the current value in g_costs for that node


    # If no path is found
    return None, float('inf'), nodes_visited, edges_evaluated

# Find the best path from Central Park (0) to William Theisen-Floyd Estate (13)
path, cost, nodes_visited, edges_evaluated = a_star(graph, heuristics, start=0, destination=13)

print(f"Number of nodes visited: {nodes_visited}")
print(f"Number of edges evaluated: {edges_evaluated}")

print_best_path_to_estate({13: path}, graph, node_number_to_name, start=0, destination=13)
Expected Output:

Number of nodes visited: 6

Number of edges evaluated: 10

Best path from Central Park to William Theisen-Floyd Estate:

Central Park ---[TAXI, 8 min]--> Grand Central Station ---[TAXI, 16 min]--> LGA ---[FLIGHT, 35 min]--> KISP ---[TAXI, 13 min]--> Patchogue ---[TAXI, 23 min]--> William Theisen-Floyd Estate

Total travel time: 95 minutes

Part 3: Were the results of the two algorithms the same or different? Why do you think this is? (2 pt.)

[ANSWER]

Problem 2: Constraint Satisfaction Problems (12 pts.)

On your way over to the estate, you read over the police report:

While the exact identities of the party-goers is currently unknown, the police do know that there were three men and three women at the party. Each has been given an alias. The suspects are three men (Colonel Mustard, Professor Plum, Mr. Green) and three women (Miss Scarlet, Mrs. Peacock, Mrs. White). Each person was in a different room (Bathroom, Dining Room, Kitchen, Living Room, Pantry, Study). A suspected weapon was found in each room (Bag, Firearm, Gas, Knife, Poison, Rope).

Armed with this knowledge, you arrive at the estate and begin methodically exploring the house. As you explore, you slowly piece together a series of clues:

  1. The woman in the kitchen was not found with the rope, knife, or bag.

  2. Miss Scarlet was either in the study or the bathroom; Professor Plum was in the other.

  3. The person with the bag, who was not Miss Scarlet nor Professor Plum, was not in the bathroom nor the dining room.

  4. The man with the rope was found in the study.

  5. The weapon in the living room was found with either Miss Scarlet or Mrs. White.

  6. The knife was not in the dining room.

  7. Mr. Green was not with the weapon found in the study nor the pantry.

  8. The firearm was in the room with Mrs. White.

  9. Mr. Theisen-Floyd was gassed in the pantry, and the suspect found in that room is the murderer.

As you ponder the clues (and the scenery, drink in hand) inspiration strikes! You recall learning another algorithm in class that could be used.

In the code cell below implement the backtracking algorithm for constraint satisfaction problems to solve the murder mystery!

from collections import deque

# Define variables
people = ["Colonel Mustard", "Professor Plum", "Mr. Green", "Miss Scarlet", "Mrs. Peacock", "Mrs. White"]
rooms = ["Bathroom", "Dining Room", "Kitchen", "Living Room", "Pantry", "Study"]
weapons = ["Bag", "Firearm", "Gas", "Knife", "Poison", "Rope"]

# Set of all assignments
assignments = []
num_checks = 0

# Define domains
domains = {
    person: set(rooms) for person in people
}
domains.update({
    room: set(weapons) for room in rooms
})

# Clues as constraints
def is_valid(assignment):
    """
    Check if the current assignment satisfies all clues.
    """
    global num_checks
    num_checks += 1

    # Extract assignments for people, rooms, and weapons
    person_to_room = {person: room for person, room, weapon in assignment}
    person_to_weapon = {person: weapon for person, room, weapon in assignment}
    room_to_weapon = {room: weapon for person, room, weapon in assignment}

    # TODO: Clue 1: The woman in the kitchen was not found with the rope, knife, or bag.
    
    
    # TODO: Clue 2: Miss Scarlet was either in the study or the bathroom; Professor Plum was in the other.
    
    
    # TODO: Clue 3: The person with the bag, who was not Miss Scarlet nor Professor Plum, was not in the bathroom nor the dining room.
    

    # TODO: Clue 4: The man with the rope was found in the study.


    # TODO: Clue 5: The weapon in the living room was found with either Miss Scarlet or Mrs. White.
    

    # TODO: Clue 6: The knife was not in the dining room.


    # TODO: Clue 7: Mr. Green was not with the weapon found in the study nor the pantry.
    

    # TODO: Clue 8: The firearm was in the room with Mrs. White.
    
    
    # TODO: Final clue: Mr. Theisen-Floyd was gassed in the pantry, and the suspect found in that room is the murderer.
    
    
    return True

# Backtracking algorithm
def backtrack(assignment):
    """
    Perform backtracking to solve the puzzle.
    """
    # TODO: Check length of assignment


    # TODO: Try all combinations of people, rooms, and weapons


    # TODO: If no combination was found that works, return none
    return None

# Find the solution (Note: my solution runs almost instantly so if yours doesn't you have a bug)
solution = backtrack(assignments)

# Print the solution
if solution:
    print("Solution found:")
    for person, room, weapon in solution:
        print(f"{person} was in the {room} with the {weapon}")
    print('Num Checks', num_checks)
else:
    print("No solution found.")
Expected Output:

Solution found:

Colonel Mustard was in the Kitchen with the Bag

Professor Plum was in the Bathroom with the Knife

Mr. Green was in the Pantry with the Gas

Miss Scarlet was in the Study with the Rope

Mrs. Peacock was in the Dining Room with the Poison

Mrs. White was in the Living Room with the Firearm

Num Checks 128561

Final Question: Based on your deductions, who was the killer?

[ANSWER]

You and your team catch the next flight back to campus feeling a little unsatisfied. Sure you know which of the aliases was likely the killer, but who are these people? You ruefully submit your report and cross your fingers that the police may be able to find some suspects based on your discovery.