Ethical Framework & Weighting

Intro

This poster is dedicated to the design and justifications behind my route planning algorithm. The purpose of this algorithm is to plan a route through a city while minimising risk in an automated vehicle.

My Ethical Framework

There are two major factors we need to consider while designing our route planning algorithm. The first is the risk posed to other road users and pedestrians and the total distance of the route. To make sure that both parties are considered, I will be using utilitarianism as my ethical framework. Utilitarianism aims to maximise the overall happiness and well-being of all parties affected by an action or decision. For example, we would route the car around highly populated areas to minimise the risk posed to others while also minimising the distance of the route to maximise the happiness of our passengers.

Applying Utilitarianism

When we apply utilitarianism to our route planning algorithm we assign a weight to each road depending on the risk level of that area. For example, in the diagram below, we can assign a road weight in a range from zero to one where zero is the safest and one has the most risk. This scale allows is to numerically represent the potential harm we can cause to others and allow us to minimise it.

Balancing Safety and Distance

The balance between safety and distance can be challenging to predict as it is all down to probability. In our case, we do not know the safety and reliability of the car, so I will be making a variety of weightings that the manufacture can select from. To see the weightings I have created, choose one from the "Presets" section on the right.

Algorithm Design & Navigation

Graph Theory

To navigate the city we will be using graph theory for our calculations. Graph theory is a mathematical structure comprising points called nodes and links between them called edges. In our scenario, a junction in the city would be a node, and the roads connecting them would be edges. Each edge (road) will have a calculated weight based on the area that borders it and the length of the road. The most optimal route will be a list of nodes that have the lowest total weight.

Calculating Edge Weights

To calculate the edge weights we take two factors into consideration, the length of the edge and the areas bordering that edge. The weights of these areas are pre-determined using our ethical framework of choice. To calculate the total weight of the edge, we will multiply all the weights by the length of the edge and sum them together. If there are two areas bordering a single edge, then we will take the average of the two and add that to the total weight. The below pseudocode shows how we calculate the total weight of an edge.

                    
INPUT areas   # list of areas bordering this edge
INPUT length  # the length of this edge
INPUT weights # the current weights of the algorithm (blue, green, red, length)

SET cost TO weigth["length"] * length
SET areaCosts TO 0
FOR area IN areas
    SET areaCosts TO areaCosts + length * weights[area]
ENDFOR
IF areas.length > 1
    SET areaCosts TO areaCosts / areas.length
ENDIF
SET cost TO cost + areaCosts

OUTPUT cost # the final cost of this edge
                    
                

Navigating The Graph

To navigate the graph I have chosen to use the A* algorithm. A* uses a heuristic function to make the most optimistic estimate of the distance between the current node and the goal node. It then uses this heuristic to prioritise the nodes that are closer to the goal node, meaning that it does not need to iterate over every node in the graph. My heuristic function simply returns the straight line distance between the two nodes with no extra modifiers, such as areas or zones. I chose this algorithm because it is much more efficient than other algorithms such as Dijkstra's algorithm. Dijkstra's needs to iterate over every node in the graph, making it far less efficient for larger cities and routes. The code for this part of the algorithm can be found here.