Technical Independent Study
The decision-making algorithm with LED guidence system
Target
The ultimate goal of our system is to find the most comfortable path for people, taking into account distance and crowding, thus providing a better subway experience for the user.
Method
In order to better count the paths, we convert the structure of the subway stations into a directed connectivity graph for better path planning
In our algorithm both distance and crowd situation will contribute to the value function. Thus we can find a most comfortable path for the user.
The Value Function
After a reacher we found that People care about distance and crowding in roughly equal measure，so finally our function is shown as below:
Comfort = 0.5*Distance/Expected Distance + 0.5*Crowd Density/Expected Crowd Density
To find the most comfortable path, I chose the algorithm Dijkstra
Which can find the most shortest path to each of other points from the start point.
Dijkstra
1 / Initialize
Start by assigning a tentative distance value to every node in the graph. Set it to zero for the initial node and infinity for all other nodes.
2 / Mark
Mark the initial node as the "current" node, and set all other nodes as "unvisited".
3 / Current Node
For the current node, consider all its unvisited neighbors and calculate their tentative distances through the current node. If this tentative distance is shorter than the neighbor's current tentative distance, update the neighbor's tentative distance.
4 / Visited
Mark the current node as "visited" so that it will not be checked again.
5 / Select
Select the unvisited node with the smallest tentative distance as the new "current" node.
6 / Repeat
Repeat steps 3-5 until you have visited all nodes. The algorithm terminates when the destination node has been visited. At this point, the shortest path has been found.
Animation
Guidance Strategy For LED
Green
More comfortable roads recommended for people to walk on
Red
Uncomfortable path, not recommended for walking