Optimal Route Planning

Determining optimal routes in road networks from a given source to a given target location is a problem frequently addressed in everyday life. Typically, frames from a video camera are used to train a deep convolutional neural network which can then be used to predict the correct steering control. We will now look at how an autonomous vehicle can travel from its current location to a given destination or a goal location.

Route planning is used to decide the route to take from one place to another. Consider the problem that you need to go from your house to your school. Here, your house and school become the source and the destination, respectively. The output of the route-planning algorithm is the route to take, which enlists all the roads and intersections to take to reach the destination from the source.

To have a high-level representation of the road network suitable for our route planner, we will represent cities as vertices (or nodes) and the connecting roads as edges to have a road network graph. With a road network graph, just as any other graph, most of the graph-based shortest path algorithms (like A* and Dijkstra’s) can then be used to find a path from the current location to the destination. The road network graph for most cities in the UK is well known. The transportation authority maintains a road network graph which is also maintained by numerous services like Google Maps.

Dijkstra’s Algorithm

The road network graph consists of every intersection of multiple roads as the vertex and all roads as the edges. All two-way roads, in which one can travel in both directions, can be represented as undirected edges, whereas all one-ways are directed edges. The number of lanes, the speed limits etc. can also be stored on the edges. The weight of the edge is taken as the length of the road (if minimizing distance) or the length of the road divided by the maximum speed (if minimizing travel time). This converts the problem into a standard graph search problem. Dijkstra’s algorithm is a common search algorithm for graphs which gives the shortest path from the source to the destination when all the edges are nonnegative, an assumption which is true for our road network graph.

Dijkstra’s algorithm considers the distance (using predefined metrics) between one vertex to each other in a graph. The Classic Algorithm A* extends these calculations with supplementary information and a greedy strategy to improve its results.

Metaheuristics

Metaheuristic methods have been used successfully in the computation of the shortest path in a graph. The solutions yield very slow query times when realistic road networks are used as inputs, and this fact hampers their usage in real-time or interactive applications. On the other hand, applying aggressive heuristics does not always provide accurate results. The source and the destination may not be pre-existing vertices in the road network graph and, hence, these are added as additional vertices at the query time and all intersections to which they connect are added as edges. If a road is blocked, the corresponding edges are removed.

Assumptions of Routing Algorithms

While working in this layer of abstraction, numerous assumptions are made. The most important assumption usually made is that no other vehicle occupies the road, in which case the vehicle can travel with the maximum permissible speed. In addition, it is assumed that different lanes have the same distances which are the average length of the road. Roundabout distance may be ignored or may be taken as a constant. Naïve methods also do not consider the time wasted in traffic congestion and traffic lights. Hence, the computations are not accurate and are made from a variety of assumptions; however, the assumptions enable decision making in small computation time while operating at a higher degree of abstraction.

Many routing algorithms can make assumptions about the repeated traffic trends to get a better indication of the expected traffic congestion and operating speed, and thus more reasonable assumptions of travel time and route selection. Similarly, many algorithms can simulate the motion of other vehicles to get an indicative measure of the traffic congestion and accordingly select the route. Many other algorithms navigate vehicles such that congestion never happens. The number of assumptions made in planning a route on a more realistic road network determines the complexity of the algorithm used.