Integration of Traffic Information into the Path Planning among Moving Obstacles

Abstract

This paper investigates the integration of traffic information (TI) into the routing in the presence of moving obstacles. When traffic accidents occur, the incidents could generate different kinds of hazards (e.g., toxic plumes), which make certain parts of the road network inaccessible. On the other hand, the first responders, who are responsible for management of the traffic incidents, need to be fast and safely guided to the incident place. To support navigation in the traffic network affected by moving obstacles, in this paper, we provide a spatio-temporal data model to structure the information of traffic conditions that is essential for the routing, and present an extended path planning algorithm, named MOAAstar–TI (Moving Obstacle Avoiding A* using Traffic Information), to generate routes avoiding the obstacles. A speed adjustment factor is introduced in the developed routing algorithm, allowing integration of both the information of vehicles and traffic situations to generate routes avoiding the moving obstacles caused by the incidents. We applied our system to a set of navigation scenarios. The application results show the potentials of our system in future application in real life.

1. Introduction

Incident management (IM) is defined as the “entirety of measures that are intended to clear the road for traffic as quickly as possible after an incident has happened, ensure safety for emergency services and road users, and control the damage” [1]. IM plays an important role in maintaining the safety of road networks and in handling incidents, and it involves different organizations (e.g., police and fire brigades) that are responsible for a set of measures, such as clearing blocks and rescuing victims. For these organizations, an important issue is determining the best driving route to the incident scene [2].

During the management of incidents, there is a need for supporting first responders in navigating among moving obstacles. For example, toxic plumes can be created and block roads in the event of an accident with a truck carrying chemicals. In such cases, the first responders should be guided to avoid the obstacles caused by the hazards and to safely reach the location where the incident occurred. In the car navigation industry, many commercial route guidance systems (e.g., Tom-Tom, INRIX, Google, and Garmin) have been developed, and some of these systems are even able to incorporate traffic information to suggest an alternative route. Nevertheless, these systems do not consider the dynamics of hazards caused by the incidents, and thus cannot provide routing services among moving obstacles. In academia, navigation during disasters has attracted considerable attention [3,4,5,6], and in more recent studies, some researchers have investigated the use of hazard models to support navigation in the presence of hazards. By using the fire model, Wang et al. [7] extend the A* algorithm to calculate routes that avoid fires. Mioc et al. [8] employ a hydrological model for the prediction of floods, and they study the calculation of evacuation routes, taking the water depths and vehicle types into account. Considering that blocked roads can be used when the obstacles move, Visser [9] and Wang and Zlatanova [10] introduce the waiting option to avoid moving obstacles such as plumes. However, the aforementioned path planners do not take the traffic conditions into account; thus, they cannot be directly applied to road networks with large traffic flows.

Timely and accurate information plays a crucial role in the information chain between all the incident management emergency services. In many studies, problems related to information (sharing), communication, and coordination have been identified as the main bottlenecks for effective cooperation between emergency services (e.g., [11,12]). The lack of a real-time assessment of the mobility consequences of an incident, as well as of its wider consequences for the surrounding area, in terms of security and safety hampers the ability of the decision makers to effectively respond to an incident and to manage its consequences.

Table 1. Information categories for traffic incident management (extracted from [2]).

Incident Information	Surrounding Environment	Organization Information
• location • type of incident • number of vehicles • number of casualties • status of casualties • dangerous goods • plumes • cargo information	• environmental damage • infrastructure damage • status of blocked roads/lanes • best driving route to incident • traffic jams • alternative driving routes • road works • special events • weather information	• location of fieldworkers of other organizations • allocation of resources of other organizations • status information of all fieldworkers

summarizes three different information categories needed for IM: information about the incident, information of the surrounding environment, and organization information. To conduct the IM process in an effective and efficient manner, the need for real-time (spatial) information and supporting information systems is large. Well-established communication and information technology and clear organizational responsibilities among emergency services are the most important issues for IM. In fact, they are a prerequisite for the effective application of IM. The ‘situation’ interface and the ‘control’ interface in a traffic management centre are the two main domains where information systems play a crucial role. The situation interfaces of the traffic management system for monitoring consist of induction loops, cameras, and human observers. For the traffic measure support, the road authorities use variable message signs, speed limit signs, ramp metering and peak/plus lanes, and special measures for IM. Peak/plus lanes are additional traffic lanes that can be opened to traffic if the demand so requires. When closed, the lanes are for the exclusive use of the emergency services [13]. In responding to incidents that involve chemicals or dangerous substances, a high level of preparedness and precise real-time knowledge of the impact are required; thus, innovative technologies and a better information infrastructure supporting the incident management are necessary.

An important class of information needed for routing among moving obstacles is the information of traffic situations in road networks. Various situations, such as car crashes, congestion and large traffic flows, could occur in the road network, which would slow the movement of vehicles or even cause blockages of roads. Moreover, vehicle speed plays an important role in avoiding moving obstacles in environments affected by hazards. With different speeds, people may need different routes to avoid or pass through the obstacles [7]. Because vehicle speed is largely dependent on traffic, the route guidance system should consider not only the status of roads influenced by moving obstacles but also the traffic conditions. This is particularly important for navigating the responders who have to proceed to destinations in the least amount of time to perform their rescue operations.

Travel time is one of critical indicators reflecting the traffic situation. This indicator has been widely used in traffic management systems and in route guidance systems. An important issue concerning the travel time is its predictions. Considerable research efforts have been devoted to this direction, and various methods and technologies have been applied for predicting the travel time in freeways or motorways, such as neural networks [14,15,16], Kalman filter [17,18], and support vector regression [19,20]. Because incidents can cause disturbances in traffic flows [21], special attention has been devoted to taking the information of incidents into account in the prediction of the travel time. Fei et al. [22] develop a Bayesian inference-based dynamic linear model to predict short-term freeway travel time. They also propose an adaptive-control-based framework to capture the travel time fluctuations during non-recurrent congestion caused by unforeseen events (incidents and accidents). Based on the work of [22], an extended model is presented in [23], using a hidden Markov model to capture the probabilistic nature of travel time delays associated with congestion. Li and Chen [24] construct a prediction model, integrating three data mining techniques, namely, K-means, decision tree, and neural network, to forecast the travel time of a freeway with non-recurrent congestion. For navigation among moving obstacles, not only the predicted information of the moving obstacles but also the forecasted information of travel time are needed. The above studies provide a set of promising solutions to the prediction of travel time during incidents, which would be useful for path planning in the presence of moving obstacles.

In this paper, we address the issue of integrating traffic information into navigation for first responders to avoid moving obstacles caused by incidents. A spatial data model is adapted from [7] to structure both the real-time and predicted information of traffic conditions in the road network. Based on the work of [25], we present an extended A* algorithm that can work with both the information of the availabilities and the traffic information of roads, and apply it to generate obstacle-avoiding routes in a traffic network. The remainder of this paper is structured as follows. In Section 2, we illustrate our system architecture, which combines the hazard simulation system and the traffic prediction system to support routing in the presence of moving obstacles. Section 3 presents the proposed spatial data model. In Section 4, we describe the modifications of the routing algorithm in great details. In Section 5, we apply the proposed data model and the developed algorithm to a set of scenarios and present the application results. This paper concludes with some discussions and suggestions for future research in Section 6.

2. System Framework

Figure 1 shows the framework that we design for integrating traffic information into the routing. This framework combines agent technology, a geo-database, hazard simulations, and the travel time prediction system. In the Netherlands, the real-time traffic information can be collected from various types of traffic measuring devices (e.g., loop detectors and video cameras) and smartphone apps such as WAZE [26]. When incidents occur, they also provide live traffic data of transportation networks affected by hazards. The real-time traffic information is delivered through public and private sectors, such as Rijkswaterstaat (Dutch Ministry of Infrastructure and the Environment) and ANWB (The Royal Dutch Touring Club), and is stored in the traffic database. This information is fed into the travel time prediction system to predict the travel times of the transportation networks in the near future. Sensor data about hazards are gathered from the field and are used to drive the hazard simulation systems. The hazard models generate predictions of the movement of moving obstacles. Within this framework, we apply the agent technology to process and analyse the data from the hazard models, and we employ a geo-database to store the data that are essential for routing. 2D and 3D GIS data are structured and stored in the geo-database systems together with GPS data from the field. Various types of agents are developed to transform the data from different sources into standard GIS format and to derive the spatio-temporal information of the road network (e.g., when and which roads will be affected by moving obstacles). Using the information of moving obstacles and traffic conditions, the routing algorithms calculate the feasible routes, which are suggested to responders to use to reach their destinations while avoiding moving obstacles.

3. Geo-Database Design

In this study, we extend the data model presented in [7] to store the information of traffic situations. Figure 2 shows the logical class diagram of our data model. The data regarding the traffic incidents, responders, and road network are coloured in yellow, light grey, and light green, respectively. The newly defined datatypes are coloured in light blue. The class RealIncident is used to store the information of real incidents. This class is linked with two classes that predict the effect of the incidents: (1) HazardSimulationEvent, which describes hazard simulations; and (2) TrafficSimulationEvent, which simulates traffic flows during incidents. We derive the information of the availability of roads from hazard simulation results, using the spatial intersection operation [7]. To facilitate this, we divide a big road network into smaller RoadNetworks. Each RoadNetwork is composed of RoadSegments, which include different types of roads that can be accessed by relief vehicles, such as city streets, highways, and secondary roads. In the extended model, we attach new attributes travel_time_list and travel_speed_list to each RoadSegment to respectively store the travel time and the travel speed that change over time. In this study, we divide the timeline into small time periods, and create two new data types: TT_Of_TimePeriod and TS_Of_TimePeriod. TT_Of_TimePeriod stores the travel time corresponding to the time period [start_time, end_time], and TS_Of_TimePeriod records the travel speed of the time period [start_time, end_time]. Note that, in this paper, we assume that both the real-time and predicted travel time information of roads over these time periods are available and updated by external software or systems. The travel speed of each road segment is derived based on the corresponding travel time and the length of the road, i.e., $travel\_speed=length/travel\_time$. To store the information of time periods when the RoadSegment and RoadJunction are blocked by moving obstacles, the attribute affected_time_list is used, which is composed of a list of AffectedTimePeriod. The class Vehicle stores the information of vehicles and is associated with Route. A Route is composed of a set of RoadSegments. Because there is a many-to-many association between RoadSegment and Route, a class named RoadSegment_to_Route is used to represent this relationship. As discussed in [10], in some situations, such as plumes, the responders can wait for a short amount of time to avoid the moving obstacles. Therefore, the information of waiting options is also structured in the data model. In our research, we assume that the waiting options are allowed at the source node of road segments. Every waiting option is indicated by a pair of attributes: beginWaitingTime (the time when the waiting starts) and endWaitingTime (the time when the waiting ends).

4. Routing Algorithm

In this study, we aim to provide the fastest routes that avoid moving obstacles caused by incidents, and we address the issues of integrating traffic information (TI) into the routing for first responders. To calculate obstacle-avoiding routes in the traffic network, we design and develop a moving obstacle-avoiding A* (MOAAstar) algorithm based on the algorithm presented in [25]. This algorithm is named MOAAstar–TI. In MOAAstar–TI, the parameter $speed$ of vehicles is removed, and we build a new function that uses the real-time and predicted speeds of roads to estimate the arrival time of nodes. During emergencies, normal cars are supposed to make place for vehicles of the emergency services. Moreover, the first responders can use sirens or the shoulders of roads in emergency situations. This allows relief vehicles to move faster than the average speeds of normal vehicles. Therefore, in the algorithm, we introduce a speed adjustment factor α to represent the extent to which the vehicle can move faster than the average speed. In this paper, the speed adjustment factor α is defined by the ratio of the real-time speed of the vehicle to the predicted average speed of traffic flows. This factor enables the algorithm to adjust the speed of the vehicle for each road to give customized routes, taking into account both the traffic flows and the status of the rescue vehicle. We assume that the road network is represented by a graph G consisting of a finite set of nodes N and edges E. The edge between two nodes x and y is denoted by $xy$. The length of edge $xy$ is denoted by $w_{xy}$. Based on the concept of safe intervals [27,28], the affected_time_list that stores the affected time of road segments and junctions is converted into a set of open intervals, $S_e=(p_1,...,p_j,...,p_J$), where $p_j=[t_{oj}^x,t_{cj}^x]$ is the jth interval of node x, $t_{oj}$ is the start time of $p_j$, and $t_{cj}$ is the ending time of $p_j$. In the algorithm, each state s is defined by its node x and an open interval associated with this node $(x,p_j)$.

4.1. Algorithm Description

Figure 3 shows the main structure of the MOAAstar–TI algorithm. Following the basic principle of the classical A* algorithm, the developed algorithm selects the state (s) with the lowest cost, expands it to generate its successors and uses them to update the $openSet$. In the generation of successors (Figure 4), the algorithm first derives the earliest $start\_time$ (line 8, Figure 4), and then it estimates the possible arrival time to the next node y via edge $xy$. In this paper, we introduce a new function $Estimate\_arrival\_time(start\_time,xy)$ (line 9, indicated in green in Figure 4) that can use the travel speeds of edges to estimate the arrival time to node y from node x. Figure 5 shows the steps of the estimation function. The vehicle starts moving given the $start\_time$. The travel speed $T{S}_l$ of the edge is extracted from the TT_Of_TimePeriod corresponding to the interval l. From line 5 to line 10 (Figure 5), the function calculates how far the vehicle can travel along edge $xy$ with the speed during interval l, i.e., ($travel\_end\_t$ - $travel\_start\_t)\times \alpha \times {TS}_l$. If there is still some distance to travel along edge $xy$, the function calculates the remaining distance and the speed of the next time interval ($l+1$) will be used. The function repeats the same steps until node y is reached within a certain interval, and returns the estimated arrival time ($EAT$). If the vehicle can safely travel through edge $xy$ before the edge is closed and the $arrival\_time$ is found to be within an safe interval of node y, then the algorithm will create a new state $s^{\prime }$ (line 13, Figure 4). The created state $s^{\prime }$ will simply be ignored if it already existed in the $closeSet$. Otherwise, it will be used to update the $openSet$.

4.2. Time Complexity Analysis

In this section, we estimate the time complexity of our algorithm MOAAstar–TI, assuming the heuristic function $h\left(n\right)=0$ (the worst case). Basically, the algorithm MOAAstar–TI can be divided into four main parts: (1) extracting the state with the min value in the open set (line 7, Figure 3); (2) estimating the arrival time from one node of an edge to the other (line 9, Figure 4); (3) generating a new state associated with a node (line 11–16, Figure 4); and (4) inserting a new state and updating the open set (line 20–29, Figure 4). Let $\left|T\right|$ be the max number of open intervals that are associated with nodes and edges, and let $\left|L\right|$ be the number of time intervals that the predicted speeds are within. As each state of a node corresponds to an open interval, the total number of states is $\left|T\right|·\left|N\right|$. With a binary min-heap, each extraction operation of the state with the min value takes time $O\left(lg\right(\left|T\right|·\left|N\right|\left)\right)$ and there are at most $\left|T\right|·\left|N\right|$ such operations. Thus, the total time for calling Part 1 is $O\left(\right|T\left|·\right|N\left|·lg\right(\left|T\right|·\left|N\right|\left)\right)$. To generate new states, we examine every edge leaving from a certain node and every associated interval in the function $updateOpenSet\left(s\right)$. In the function $Estimate\_arrival\_time(start\_time,xy)$, the $while$ loop iterates at most $\left|L\right|$ times to perform the calculation of the remaining distance along the edge, each taking $O\left(1\right)$ time. Therefore, the function takes a computational complexity of $O\left(\right|L\left|\right)$. As we obtain the estimated arrival time, we iterate over max $\left|T\right|$ open intervals to generate a new state, and insert it to the open set (costing $O\left(lg\right(\left|T\right|·\left|N\right|\left)\right)$ time). Because there are at most $\left|T\right|·\left|E\right|$ edge examinations, the running time of calling Part 2, Part 3 and Part 4 is $O\left(\right|T\left|·\right|E\left|·\right(\left|L\right|+\left|T\right|+lg\left(\right|T\left|·\right|N\left|\right))$. To sum up, the total running time of the algorithm is $O\left(\right|T\left|·\right|E\left|·\right(\left|L\right|+\left|T\right|+lg\left(\right|T\left|·\right|N\left|\right))+|T\left|·\right|N\left|·lg\right(\left|T\right|·\left|N\right|\left)\right)$ or $O\left(\right(\left|E\right|+\left|N\right|\left)·lg\right(\left|N\right|)+|E|+|N\left|\right)$ if $\left|T\right|$ and $\left|L\right|$ are regarded as constant coefficients.

5. Case Study

To utilize the traffic information for routing among moving obstacles, we have adapted the multi-agent-based navigation system developed in a previous study [29], integrating the extended A* algorithm MOAAstar–TI (presented in Section 4). The proposed spatial data model has been realized in the relational database PostgreSQL with the PostGIS extension [30]. We applied our system to a set of navigation scenarios, considering a case of plumes that affected the city of Arnhem in the Netherlands. We created a set of moving obstacles to simulate the movement of plumes. The road network dataset of Arnhem was used in the experiments. This network consists of 13,336 road segments and 11,712 junctions. To test the proposed algorithm with traffic information, in this study, we built a traffic simulator, which provides predicted information on the travel times and travel speeds of the road network. The traffic simulator uses the normal speed of cars (60 km/h) as the mean speed, and generates the speeds of roads from time t = 0 min to time t = 60 min (the time interval = 1 min), following the normal distribution. Figure 6 shows snapshots of the movement of obstacles and traffic flows. Based on the simulated travel speeds, the navigation system applies the proposed MOAAstar–TI algorithm to calculate the routes, and it displays the calculated results to users through a 2D viewer, which is built based on OpenStreetMap.

5.1. Scenario 1

Figure 7 depicts three routes calculated for three vehicles (V1, V2 and V3) by our system. In

Table 2. Calculated results of scenario 1.

Vehicle ID	Distance (km)	Total Waiting Time (min)	Actual Travel Time (min)
V1	15.1	0.0	17.3
V2	13.6	0.0	20.8
V3	12.6	0.0	19.5

Notes: $\left(1\right)$ V1, V2 and V3 have the same source and the same destination; $\left(2\right)$ The route of V1 is calculated by the algorithm MOAAstar–TI given α = 1; $\left(3\right)$ The route of V2 is calculated by the algorithm MOAAstar-II given a speed of 60 km/h; $\left(4\right)$ The route of V3 is calculated by the algorithm MOAAstar-II given a speed of 100 km/h; $\left(5\right)$ The actual travel time of V2 and R3 are estimated using the traffic information.

, we present the calculated results, comparing the results calculated using our MOAAstar–TI algorithm and the results computed using the MOAAstar-II algorithm presented in [25]. We assume that all the three vehicles have to move from the blue point to the green point. From Figure 8, we can see that the relief vehicle V1 (α = 1) that follows the average speed of traffic flows can change its speed along its route. As shown in the table, the travel distances of the routes calculated by the MOAAstar-II algorithm for Vehicles V2 and V3 are shorter than the route of V1 calculated by MOAAstar–TI, but it takes more time for the response vehicles to arrive at the destination due to the lack of consideration of the traffic flows. Note that, because the moving speed of the relief vehicles can be significantly reduced by the traffic flows, without considering the traffic conditions, the responders could be affected by the hazards during their movement, or may have no safe routes towards the destination.

5.2. Scenario 2

In this scenario, we show the impact of the speed adjustment factor (α) on the route calculation.

Table 3. Calculated results of scenario 2.

Vehicle ID	Distance (km)	Total Waiting Time (min)	Total Travel Time (min)
V1	23.6	0.6	29.0
V2	23.5	1.6	27.3
V3	15.8	2.0	16.9

Notes: $\left(1\right)$ The route of V1 is calculated by the algorithm MOAAstar–TI given α = 1; $\left(2\right)$ The route of V2 is calculated by the algorithm MOAAstar–TI given α = 1.3; $\left(3\right)$ The route of V3 is calculated by the algorithm MOAAstar–TI given α = 1.6.

shows the route results calculated by MOAAstar–TI for three vehicles (V1, V2 and V3). Three values of the speed adjustment factor are set for the involved vehicles, i.e., $\alpha =1,1.3,1.6$. The higher α is, the faster the vehicle can move relative to the average speed of traffic flows. As we can see from the table, our algorithm generates three different routes for the vehicles, and different waiting times are used for the vehicles to avoid the moving obstacle. Figure 9 shows the calculated routes as well as the movements of the vehicles along their routes. Although there is a slight difference between the route of V1 ($\alpha =1$) and the route of V2 ($\alpha =1.3$), vehicle V3 with $\alpha =1.6$ can travel a clearly different route that allows it to take the least amount of travel time to reach the destination. Using the speed adjustment factor, our algorithm can include the information of real situations of vehicles into the routing and generates obstacle-avoiding routes customized for responders, which would facilitate their response to major traffic incidents.

6. Conclusions

This paper investigates the integration of traffic information into path planning in the presence of moving obstacles. We adapted our previous data model from [7], introducing new data types and attributes to structure the information of traffic and waiting options to avoid moving obstacles. A variant of the moving obstacle-avoiding A* algorithm, MOAAstar–TI, has been developed to address both the real-time and predicted travel speed of roads, and it was tested with synthetic data of traffic flows in a real network. The testing results in the context of toxic plumes show the importance of traffic information in the generation of routes that avoid such plumes. Note that our approach is general and not limited to the case of plumes. It can also be applied to other types of hazards, such as fires and floods.

Despite the potential of our approach, some practical issues still need to be mentioned and addressed. First, currently there is not a direct connection between our system and a travel time prediction system that can be driven by real-time traffic information. In this paper, we assume that the data of traffic flows are obtained and provided by an external traffic simulation system; second, in this study, it is assumed that the data of travel times of the entire road network are available. Nevertheless, due to the lack of road monitoring devices, some roads may have no historic or real-time data regarding traffic flows. In this case, the vehicle speed is still needed and integrated into the path planning process; third, due to the time limitation in incident response, the calculation time of the algorithm is a critical factor in the evaluation of the system, and it may vary with different road networks. Thus, more tests would be needed to evaluate the performance of our algorithm on different road networks. Finally, our system is based on a central server, which is used to maintain all the data essential for routing and provides the route calculation service for the vehicles in the field. This approach highly depends on the availability of the communication network. Investigating the role of the communication network in the routing is beyond the scope of this paper.

In future work, we would like to use a plume model (e.g., [31]) to test our system, and combine it with a travel time prediction system to forecast the traffic flows in the case of toxic plumes. Because uncertainties could be involved in the results from the prediction system and can influence travellers’ behavior [32], it is also necessary to investigate the routing with uncertain travel times. One of the possible solutions is to introduce another factor that can be adjusted based on the uncertainties of the predicted speed and be added into the estimation of traveling time of roads. Furthermore, we will study the navigation aid for ordinary road users during traffic incident management. On one hand, major incidents (e.g., with dangerous substances) on or near a highway have a direct impact on the safety of the people passing close to the incident location or living in the surrounding area. The incidents can also cause traffic disorder, which could influence the movement of vehicles on the roads. On the other hand, the traffic management center can directly take effective traffic measures, for example, blocking certain roads. This information can be distributed by traffic information services to provide precise travel information to road users, and can even be integrated into route navigation systems to provide alternative driving routes to the vehicles on the highway. This information can also be shared with citizens living next to the highway to provide evacuation routes on their smartphones. Moreover, some special navigation cases should be considered in future research. For instance, during the management of an incident, responders may have to go to a certain point that is exactly located inside the hazards. This situation can be more complex if more responders and more dynamic destinations are involved [33]. New approaches would be needed to address these navigation problems.