MP2: Wi-Fi Fingerprints

ECE/CS 434 | MP2: Wi-Fi Fingerprints


Objective
In this MP, you will:

Implement a localization algorithm based on Wi-Fi fingerprints.
Experiment with clustering algorithms such as KNN.
Apply appropriate optimizations to improve localization accuracy.
Imports & Setup
The following code cell, when run, imports the libraries you might need for this MP. Feel free to delete or import other commonly used libraries. If Gradescope reports an error and you believe it is due to an unsupported import, check with the TA to see if it could be added.

import numpy as np
import pandas as pd
from sklearn.neighbors import KDTree
from statistics import mean 
import math
Problem Description
There is a room with 3 Wi-Fi access points (their locations are known). You are given the RSSI measurements from all 3 access points (APs) at  N  unique locations in the room, as well as the phone’s orientation when the measurement was taken. Let’s call this the “offline phase”, and call the collected data "fingerprints". In the “online phase”, a user in the room walks along a straight line. Given the RSSI measurements collected by this user’s smartphone and the Wi-Fi fingerprints collected during the off-line phase, your task is to find the beginning and end locations of this user’s walk.

offline.csv contains data for the off-line phase and has 5 columns: (x, y, alpha, SSID, RSSI).

1-walk-*.csv contain data collected during the on-line phase and has 3 columns: (SSID, Time, RSSI)

ap_locations_1.csv contains the coordinates of each AP. This data is only needed if you want to implement optional optimizations. The reference implementation did not use this data.

Notes
Refer to groundtruth.png for a visual of the setting.
alpha is provided in degrees.
RSSI is provided in decibels.
SSID provides the unique identifier for each AP.
Your Implementation
Implement your localization algorithm in the function wifi_localization(online_file, offline_file, ap_locations). Do NOT change its function signature. You are, however, free to define and use helper functions.

# This function takes three arguments: 
#    online_file  (string) - name of data file for online phase
#    offline_file (string) - name of data file for offline phase
#    ap_locations (string) - name of data file for access point locations (optional optimization, reference implementation did not use this)
# It returns a list with two tuple values corresponding to the start and end coordinates of the walk

def wifi_localization(online_file, offline_file, ap_locations):
    # feel free to replace/modify the next two lines
    fingerprints = pd.read_csv(online_file)
    walk = pd.read_csv(offline_file)
    
    return [(0., 0.), (0., 0.)] # Your return value should be in this format: [(x_start, y_start), (x_end, y_end)]
Running and Testing
The code below runs and evaluates your localization algorithm on the two datasets provided. We will use this same function estimate_grade(loc, gt) to grade your MP on the two provided datasets and on additional (hidden) datasets.

if __name__ == '__main__':
    def estimate_grade(calculated, expected):
        X = 0
        Y = 1
        S = 0
        E = 1
        calculated = np.array(calculated)
        expected = np.array(expected)

        # 1. Calculate deviation of walking direction from ground truth
        def get_deviation(calculated, expected):
            calculated = np.array(calculated[E] - calculated[S])
            expected = np.array(expected[E] - expected[S])
            with np.errstate(divide='ignore', invalid='ignore'): 
                dot_prod = np.dot(calculated, expected) / np.linalg.norm(calculated) / np.linalg.norm(expected)
                deviation = np.nan_to_num(np.degrees(np.arccos(dot_prod)), nan=90)
                return deviation if deviation <= 90 else abs(deviation - 180)

        delta_theta = get_deviation(calculated, expected)

        # You will receive full points if deviation <= 30 degrees. 
        # You will receive 0 points if deviation >= 60 degrees.
        # Points for deviation between 30 and 60 degrees will be scaled proportionally.
        theta_score = 1 if(delta_theta <= 30) else max((1 - abs(delta_theta - 30)/30), 0)

        # 2. Calculating absolute distance between calculated and expected S/E coordinates.
        dist_errors = expected - calculated
        s_dist = np.linalg.norm(dist_errors[S], ord=2)
        e_dist = np.linalg.norm(dist_errors[E], ord=2)

        # You will receive full points if error <= 0.5 units. 
        # You will receive 0 points if error >= 3 units.
        # Points for error between 0.5 and 3 units will be scaled proportionally.
        s_score = 1 if(abs(s_dist) <= 0.5) else max(1 - abs(s_dist - 0.5)/2.5, 0)
        e_score = 1 if(abs(e_dist) <= 0.5) else max(1 - abs(e_dist - 0.5)/2.5, 0)
        dist_score = (s_score + e_score) / 2

        return theta_score * 0.8 + dist_score * 0.2

    student_out_1 = wifi_localization("1-walk-1.csv", "offline.csv", "ap_locations_1.csv")
    expected_1 = [(0., 2.5),(3.5, 2.5)]
    grade_1 = estimate_grade(student_out_1, expected_1)

    student_out_2 = wifi_localization("1-walk-2.csv", "offline.csv", "ap_locations_1.csv")
    expected_2 = [(0., 0.),(3., 3.)]
    grade_2 = estimate_grade(student_out_2, expected_2)

    from IPython.display import display, Markdown
    display(Markdown("""
|  Dataset  |  Expected Output |     Your Output |                  Grade |
|:---------:|-----------------:|----------------:|-----------------------:|
|     1     |     {expected_1} | {student_out_1} |        {grade_1:2.2f}% |
|     2     |     {expected_2} | {student_out_2} |        {grade_2:2.2f}% |
|   Hidden  |              ??? |             ??? | Graded upon Submission | 
|   Hidden  |              ??? |             ??? | Graded upon Submission | 
""".format(
        expected_1=expected_1,
        student_out_1=student_out_1,
        grade_1=(grade_1 * 100),
        expected_2=expected_2,
        student_out_2=student_out_2,
        grade_2=(grade_2 * 100),
    )))
Rubric
You will be graded on the two walks provided to you (5 points each) and two additional walks under a different setting (15 points each). Make sure you are not over-fitting to the provided data. We will use the same code from the Running and Testing section above to grade all 4 traces of data. In plain English, you will be graded on two error metrics:

(80%) How much your walking direction deviates from ground truth. You will receive full points if deviation ≤ 30 degrees, and 0 points if deviation ≥ 60 degrees. Points for deviation between 30 and 60 degrees will be scaled proportionally.
(20%) How much your start and end coordinates deviate from ground truth. You will receive full points if error ≤ 0.5 units. You will receive 0 points if error ≥ 3. Points for error between 0.5 and 3 units will be scaled proportionally.
Submission Guidlines
This Jupyter notebook is the only file you need to submit on Gradescope. If you are working in a pair, make sure your partner is correctly added on Gradescope and that both of your names are filled in at the top of this file.

Make sure any code you added to this notebook, except for import statements, is either in a function or guarded by __main__(which won't be run by the autograder). Gradescope will give you immediate feedback using the provided test cases. It is your responsibility to check the output before the deadline to ensure your submission runs with the autograder.