We developed an Android App, “BeatRush”, as our solution to the problem of Rush Hour.
The BeatRush App System has the following components:
- A* Engine
- Android Application
The system uses the following input:
- Pittsburgh city OSM XML data
- User input – Destination location, current location (obtained from User’s phone GPS), times of arrival and departure, time-windows around these mentioned times.
We use the A* algorithm along with backtracking, for searching the best path from source to destination. We want to find the path that takes the minimum time.
- Let f(x) be the time function that we want to minimize using A*.
f(x) = g(x) + h(x), whereg(x) = distance(A,B)/TrafficSpeed(A,B) and the heuristic
h(x) = distance(B, GoalNode)/SpeedLimit
distance(A,B) = the great circle distance between point A and the neighbor point B,
TrafficSpeed(A,B) = speed of traffic between points A and B, obtained from Here Traffic API.
SpeedLimit is in kmph, and is obtained from the OSM database.
The great circle distance is the shortest distance between two points on the surface of a sphere.
It is given by the following formula:
where Φ1, 𝝺1 and Φ2, 𝝺2 are the latitude and longitude of points 1 and 2 and ΔΦ and Δ𝝺 are their absolute differences. Δ𝞼 is the central angle between them.
- We start searching for the path at the start of the departure window. This is important because we will need the approximate traffic data at that particular time, which we solicit from the API. We keep searching for a path which starts in the user’s departure window and ends within the user’s arrival window. We have a lookup table, which has the traffic information for the whole day, at one minute intervals. We will need this to get the traffic information at different points in time.
- h(x) is admissible as the great circle distance (analogous to Euclidean distance) will always be smaller than actual path distance and the speed limit will always be greater than the actual speed of the vehicle.
- As mentioned above, we sometimes ran into dead-ends while searching for the best path. In such cases, we backtrack on the path which has been searched until then, until we are able to provide an alternate path to search on. Sometimes, the dead-ends are too far along a way, and backtracking will take a lot of time. Case in point – by mistake the search got onto a railway track, and the dead-end was encountered a long way away from the beginning of that track, where we could have gone on an alternate route. Backtracking took a lot of time, time we could have saved. In such cases, we tag the beginning node of the railway track with some tag. Then while searching for the path, we check for this tag and don’t go there if this tag is present.
What if we could fight the terrible traffic we all have to encounter during rush hour? What if there was a better way to move and travel that can make our time more efficient?
Traffic is an issue that has been impacting society for a long time now. Rush hour is a part of the day during which traffic congestion on roads and crowding on public transport is at its highest. Rush hour is a phenomenon that usually happens twice a day – once in the morning and once in the evening, the times during which people commute the most. We propose a solution to the problem of Rush Hour by suggesting the most time-efficient route for the user to take between two locations.
Artificial intelligent agents in the direct control class usually focus on managing estimation of traffic in a particular road network for controlling traffic lights, analyzing the traffic demand for a particular route, and on qualitative predictions of route demands (rush hour) and bottlenecks that could form. On the other hand, the indirect control class agents usually focus on climate predictions and using the direct control agents information to alert the drivers.