Dynamic Guidance of an Autonomous Vehicle with Spatio-Temporal GIS

Abstract

Most of computer-vision systems for vehicle guidance are tuned for highway scenarios. Developing autonomous or driver-assistance systems for complex urban traffic pose new algorithmic and system architecture challenges. This paper introduces a novel system that uses Spatio-Temporal GIS principles and a new traffic determination algorithm. The prototype system can be used as a part of autonomous vehicles controlling structure with analytical capabilities. For these purposes, predicting vehicle motion is done through trajectories. The trajectories are generated using spatial and aspatial information in GIS environment. Then, vehicle is navigated by GPS and a fuzzy logic map matching is used to locate the vehicle position on the map. Traffic congestion algorithm, which passed through 82.5% of evaluations cases successfully, is performed by vehicle’s velocity in the third step. Finally, heuristic real-time route finding algorithm is used for dynamic updating of planned vehicle trajectory. Furthermore, the system is open so that further extensions such as controlling autonomous vehicle for avoiding or leaving the banned regions are possible.

1 Introduction

From a research point of view, autonomous vehicles for urban environment are viewed as mobile robots which execute the task of displacing efficiently and guiding themselves through the streets [1]. The modern robotic paradigm indicates that robots have to execute five basic tasks: perceiving environment, deciding reactions, guiding dynamically and planning route, implementing a service layer for managing the fleet of vehicles and responding user’s requests and finally realizing them [1].

All mentioned tasks are interested subjects for active research. Traffic detection, route planning and dynamic guidance, which can be considered as parts of these tasks are under investigation in the followings. Many researchers have studied on recent cases to improve quality and capabilities of the tasks [2,3,4,5,6].

Nevertheless, majority of the above mentioned researches are single purposed, because they can just operate based on one proposed case. Hence, they are not cost effective for guiding autonomous vehicle(s) which need multiple applications and analysis in real-time. In addition, most of them use prevalent tools for detecting congestion and guiding vehicles that will cause affinity of autonomous vehicles to various tools.

For solving the mentioned challenges, it is necessary to find an algorithm for detecting congestion, which act without using conventional tools (such as surveillance cameras). In addition, a system that can be equipped with analytical capability and customization is required. GIS (Geospatial Information System) can provide these abilities [7, 8]. Then can be used for our purpose. With respect to variation of autonomous vehicle temporally & spatially, Spatio-Temporal GIS can provide our requirement.

This paper presents the steps for developing a system for guiding autonomous driving vehicles. This will be done by proposing a new algorithm for automatic vehicle detection in traffic congestion (without using conventional tools such as video camera) and Spatio-Temporal GIS (STGIS) capabilities for going out of congestion.

2 System Design and Implementation

The proposed system can be used as a part of the control structure of an autonomous vehicle, which moves in urban environments and has the ability of guiding vehicle. Figure 1 presents the system flowchart.

Fig. 1.

Flow chart of the system

2.1 Preparing Spatial and Attribute Information

Various analyses can be carried out in Spatio-Temporal GIS. These analyses should be operated on accurate and up-to-date information. The primitive spatial information used in this research, was digital maps (1:1000) of Tehran covering vicinity of Vanak square which produced by Tehran Municipality.

The reference ellipsoid of these maps was WGS84 with UTM projection system. These maps were controlled for some errors such as (overshoot, undershoot, spike, switchback …) to be ready for GIS analysis. Attribute information such as streets names, delay time, passing time, were also linked to the spatial information.

2.2 Integrating of GPS and STGIS

Recently, GPS (Global Positioning System) technologies are increasingly used in various applications of transportation planning and operation [9]. In order to track the autonomous vehicles, latitude, longitude and time, which are obtained by GPS, will be needed. These data will be stored in Spatio-Temporal Database (STDB).

STDB uses four-generation systems to retrieve, manipulate, represent and store spatially and temporally referenced data [10]. The third one is suitable for this study and has been used to handle data in database. Figure 2 represents a schematic view of this concept.

Fig. 2.

Spatio-temporal database

In this study, the data is collected with the period of five second (Our GPS up-date rate). The first record of database is processed and information fields of latitude, longitude and time are populated. At this time, a point with the same coordinates will be shown as a graphical object of autonomous vehicle in STGIS. Other records are handled based on the above figure.

2.3 Map Matching Process

The proposed system must correct the positional errors introduced by GPS receiver and recognize the streets from other features in the map and be able to apply map matching process. The basic idea of conventional map matching is comparing the vehicle’s trajectory against known streets close to the previous matched position. The street whose shape most closely resembles the current trajectory and previously matched street is selected as the one on which the vehicle is apparently travelling [11].

However, when a map matching based vehicle is travelling in a city area, there may be many streets patterns matching the trajectory reported by the positioning sensors at any given moment. It may be difficult to distinguish precisely on which particular street the vehicle is travelling.

Rather, the system may conclude that the vehicle is “more likely” to be on certain streets and “less likely” to be on some other streets. Therefore, techniques for dealing with qualitative terms such as likeliness are required in the map matching process. Fuzzy logic can be used as an effective method dealing with this task. Zhao (1997) has introduced an efficient algorithm for handling fuzzy logic map matching which has been applied in the system (see appendix) [11].

2.4 Detecting Congestion

Traffic engineering activities usually use wide variety of information and parameters [12]. Our new method has been proposed for modelling and detecting congestion without considering most of these criteria. It is clear that when a vehicle is located in congestion, its velocity will be reduced proportional to the congestion volume. If the vehicle is located in congestion, it can be said that the velocity of vehicle in particular time will be less than a threshold. Of course, for evaluating this hypothetical suggestion different statistical measurements and observations based on street speed limit, date time and the average velocity of vehicle with respect to congestion volume are required.

Accordingly, the congestion volume was measured for some streets near Vanak square in the September of 2006. In the streets which critical velocity was 50 km/h, the velocity average was measured 23.8 km/h. This measurement has been done during a week (excluding holidays) repeatedly between 7:30 to 9:00 AM and 6:00 to 7:30 PM (the rush hour periods). With respect to the results, following constraints were defined for detecting traffic and guiding vehicle (following thresholds are subjective and varies according to the normal traffic pattern).

• If the velocity is in the range of 20–23.8 km/h, congestion will be smooth and fluent, so vehicle can continue moving along the predefined path.

• If the velocity is in the range of 10–20 km/h, congestion is not so heavy and vehicle can leave the path or continue moving.

• If the velocity is less than 10 km/h, congestion is heavy and the vehicle should be guided to evacuate the traffic.

For this purpose, forty vehicles were recorded in three sequentially five seconds. These observations were categorized in three groups (see Fig. 3).

Fig. 3.

Examination of the explained method for detecting traffic with forty vehicles

The first vertical bar contains thirty-three vehicles, which situated in heavy congestion. Second part includes five vehicles, which put in middle congestion and the last one is consisted of two vehicles, which located in smooth congestion.

For two recent groups reducing velocity maybe originated from another reasons such as pedestrian or drivers offends. Thus, it is concluded that these conditions are correct for 82.5% of observations in the case study.

2.5 Analytical Modeling with STGIS

STGIS is able to apply changes occurred in time to the model and update it. Based on updated model, various analyses such as finding the nearest facility (for example; gas station) with respect to the vehicle’s movement can be done.

In this research, When a vehicle is located in congestion, STGIS can find the nearest available node or junction to the vehicle’s position. Then, new path to destination node will be found based on minimum time or distance and the vehicle will be able to change its predefined trajectory.

Since the number of nodes in urban environment is huge, real-time route finding may not be done effectively. Therefore, it is better to consider a heuristic programming to enhance route finding efficiency.

There are different heuristic and probabilistic methods. In recent study, two heuristic shortest path algorithms, which run fastest on real road networks, have been considered. These two algorithms are graph growth algorithm implemented with two queues (TQQ) and Dijkstra algorithm implemented with double buckets (DKD) [13]. These algorithms have been introduced in Pallottino 1984 and Ahuja et al. 1993 respectively [14].

The processing time of these mentioned algorithms and some others were evaluated using real road networks. The algorithms were implemented using various nodes. Table 1 shows execution time of the algorithms.

Table 1. Execution times of algorithms with one to one condition

Table 1 concludes that when the number of nodes is more than 2000, DKD has better performance than others do. Therefore, this algorithm used for real-time route finding.

In order to implement the algorithm in STGIS environment, some of effective parameters in urban traffic such as volume of traffic congestion, intersection and passing delay and type of streets (e.g., major, local and Collector) which are essential for time based route finding were simulated. Based on these parameters, route-finding algorithm was performed for changing the predefined path of autonomous vehicle (Figs. 4 and 5).

Fig. 4.

Shortest path finding using minimum time

Fig. 5.

Shortest path finding using minimum distance and detecting congestion

3 Conclusion

Autonomous vehicles, also called mobile robots and robotic vehicles, for use in urban environments are in their early stage of development. This paper concentrated on developing a system to be used as a part of controlling structure in urban autonomous vehicles. The proposed system has two contributions. The first is automatic recognition of location for autonomous vehicles in traffic jam and the second is introducing Spatio-Temporal GIS (STGIS) functionality for Dynamic guidance of the vehicles and going out of congestion.

Using the traffic determination algorithm will cause freedom from using conventional tools (such as surveillance cameras). In addition, using STGIS that is equipped with analytical capability will provide more facilities for guiding vehicles. For example with STGIS, further extensions such as controlling autonomous vehicle for avoiding or leaving the banned regions are doable. So using STGIS in the control structure of an autonomous vehicle can improve the efficiency.

The future researches can concentrate on:

• Evaluation of presented method to detect traffic congestion in different conditions for testing suitability according to the normal traffic pattern.

• Defining constraints to detect automatic congestion using fuzzy logic method.

Using other Spatio-Temporal functions such as not entering to inclusion and exclusion zones or finding the nearest facility to the vehicles position.

Appendix

See (Fig. 6).

Fig. 6.

The fuzzy logic map-matching algorithm and its rules [11]

Rule 1:

If Δheading is small

THEN resemblance of the route is high.

Where “Δheading” is defined as the difference between the direction of the street segment and the heading of the vehicle.

Rule 2:

IF Δheading is almost 180° AND heading error is zero

THEN possibility of U-turn is high.

Where AND is a minimal operator.

Rule 3.1:

IF Δdistance is large

THEN necessity to retrieve successive segment is high.

Rule 3.2:

IF Δheading is large and heading error is zero

THEN necessity to retrieve successive segments is high.

Where Δdistance is defined as the difference between the segment length and distance which vehicle has traveled on that particular segment.

Rule 4:

IF the heading errors and the root mean square errors for the vehicle’s speed are small

THEN the motion is steady.

Rule 5:

IF the truth value of the previous candidate street pattern is high AND IF the truth value of the current candidate street pattern is high

THEN the truth value of the correspondence is high.

Rule 6.1:

IF the difference between the distances traveled along the current candidate street and the length of the candidate street is small AND IF the difference between the vehicle heading and direction of successive street is small

THEN the truth value for the successive street is high.

Rule 6.2:

IF the truth value of the candidate street is high AND IF the truth value for the successive street is high

THEN the combined truth value of the moving vehicle on the street is high.

Rule 6.3:

IF no street pattern similar to the path of travel can be found with given distance

THEN the vehicle is on-street.

Rule 7:

IF there is more than one street pattern within a given distance to the current vehicle motion

THEN the vehicle is on-street.

Rule 8.1:

IF Δheading is small AND Δdistance is small

THEN resemblance of this segment is high.

Rule 8.2:

IF resemblance of this segment is high AND resemblance path is high

THEN resemblance of the whole path is high.