- Published on
Novel Path Clearance Algorithm
In early 2022, I was deeply concerned about the inefficiencies in the response times of emergency service providers, which led me to invent the Path Clearance Algorithm. The novel Path Clearance Algorithm helps realize the project Save A Life Maps (SAL Maps) in targeting and notifying users along the path of an incoming Emergency Service Provider (ESP), urging them to make way. This reduces the overall transit time of the ESP thus significantly increasing the efficiency and success rates of emergency services in reaching the users in need and connecting them with the targeted hospitals.
Algorithm
The proposed Novel Path Clearance Algorithm enables the users in transit along the path of an incoming ESP to get notified to make way ahead of time and provide a clear path. The algorithm is detailed below:
Firstly, the entire route of the ESP is divided into an array of waypoints derived from the Polyline Object using the Google Maps API.
An optimum radius, R1, is chosen based on the minimum distance between a pair of consecutive waypoints from the array initialized in step 1 as shown in Figure 1.1.
Figure 1.1: Dividing the Polyline Object into an array of Waypoints, determining the radius, and selecting the next two immediate Waypoints that the ESP will travel through.
The algorithm considers the current location of the ESP and determines the immediate next two waypoints that the ESP will travel through as highlighted in green in Fig 1.1.
Based on the two waypoints and the calculated path-dependent radius, R1, the algorithm generates circular areas around each of the selected waypoints as depicted in Figure 1.2.
Figure 1.2: Generation of circular areas around the two selected Waypoints using radius R1.
Another Radius, R2, is calculated based upon the chosen radius to generate a concentric circle within the first circular area. The second radius is slightly lesser than the first radius i.e., R2<R1 as depicted in Figure 1.3.
Figure 1.3: Generation of circular areas around the two selected Waypoints using radius R2.
A function is used to process the current location of the user in transit, determining whether they are located within the circular area generated around the two waypoints, with R1 serving as the radius.
When the user is within the annular region, the first notification is sent to alert the user to prepare to clear the path for the incoming ESP.
The second notification is dispatched when the user is within the inner circular area, i.e., the region generated using R2 as the radius, to indicate that they should finally begin to make way and clear the path for the incoming ESP. Figure 1.4 depicts a user getting notified about an incoming emergency service.
Figure 1.4: The ambulance is about to traverse through a Waypoint. The car in red does not intersect with the area generated using R1 and hence does not receive the notification. The car in yellow receives the first notification to get ready to make way and as it moves further as depicted in green, it receives the second notification to finally make way for the incoming ambulance.
This algorithm provides a sophisticated means of notifying users to clear the path for an incoming ESP, thus minimizing the time taken for the ESP to reach its destination.
Edge Cases Covered
SAL Maps is enabled by the innovative Path Clearance Algorithm, which has been designed to cater to various edge cases to ensure the successful implementation of its mission. These edge cases comprise the Two Way Street Edge Case, Notifying the Users Ahead of the Ambulance, Threshold Edge Case, and Crossroads Edge Case.
Two Way Street Edge Case
When it comes to the Two Way Street Edge Case, SAL maps employs a sophisticated algorithm to ensure that cars intersecting with the area of the upcoming ambulance waypoint receive proper notifications. However, not every car will receive a notification. Instead, only the green car depicted in Figure 2.1, which is moving along the direction of the incoming ambulance, will be notified to get ready and finally make way. This is achieved by analyzing the next waypoint of the cars and checking if their paths are aligned in the same direction as that of the ambulance. This approach is necessary to prevent excessive notifications from cluttering the user’s screen and potentially causing confusion.
Figure 2.1: Two Way Street Edge Case.
By considering the direction of the incoming ambulance, the algorithm ensures that notifications are only sent to relevant parties, reducing the likelihood of accidents and increasing overall safety. The algorithm’s ability to analyze the direction of vehicles is especially vital in cases where multiple vehicles are approaching the same waypoint. By only notifying vehicles moving in the same direction as the ambulance, the algorithm avoids overburdening drivers with unnecessary alerts, thus promoting a safe and efficient environment for everyone on the road.
Notifying the Users Ahead of the ESP
To ensure the smooth flow of traffic behind an ambulance, SAL Maps does not send notifications to users in transit behind the ambulance. This is achieved by excluding the live location of the ambulance in radius generation. Instead, the next two waypoints of the ambulance are used to create the radius, allowing only vehicles ahead of the ambulance to receive a notification to make way for it. As depicted in Figure 2.2, the green car receives a notification while the red car does not receive a notification to make way for the incoming ambulance.
Figure 2.2: Notifying only those users in transit that are ahead of the ESP. By considering only the next two waypoints of the ambulance, the system reduces the likelihood of generating false alarms for users traveling behind the ambulance, which can cause unnecessary panic and confusion. This way, the system ensures that users behind the ambulance can continue their journey without any interruption, while the vehicles ahead make way for the ambulance to pass through.
Threshold Edge Case
At the outset of dispatching an ambulance, an estimated time of arrival (ETA) is calculated. A threshold of 5 minutes is considered, after which, if the ambulance does not arrive, another ambulance is dispatched to the user in need in parallel. If the first ambulance arrives before the second ambulance, the second ambulance is notified and canceled and vice versa. This redundancy mechanism ensures that timely medical assistance is provided to the user in need, while also optimizing the utilization of resources.
Crossroads Edge Case
In the Crossroads Edge Case, when the ambulance approaches a crossroad, multiple vehicles from different directions might need to be notified to make way. To handle this situation, the algorithm considers the next two waypoints of each vehicle and checks if they intersect with the ambulance’s path. Only the vehicles who’s next two waypoints intersect with the ambulance’s path are notified to make way.
The Crossroads Edge Case is just one example of how the novel path clearance algorithm developed by SAL Maps takes into account various edge cases to provide efficient and effective emergency services. By considering the location and direction of the incoming ambulance as well as the location and path of other vehicles on the road, the algorithm ensures that only the necessary notifications are sent, reducing unnecessary distractions for drivers and improving response times for emergency services.