Machine Learning Applied To Automated Route Planning For Autonomous Vehicles

Self-driving cars have seen a rapid increase in prominence over the past few years. The technology behind these driverless vehicles relies on a combination of sensors, inertial measurement units, machine vision and wireless communications. With the development and advancement of artificial intelligence, another avenue of research has developed to optimise and enhance the capabilities of autonomous vehicles, particularly on the subject of route planning.

At its core, route planning for autonomous vehicles is a path-finding problem. Traditional algorithms which are used to solve this problem include A* and Dijkstra’s Algorithm. While these algorithms are sufficient to plan relatively simple paths, they become harder and less efficient with increasing complexity involving features such as turns, obstacles, and speed limits. In order to produce an optimal path, researchers are now turning to machine learning and artificial intelligence in order to make the most accurate predictions.

Machine learning and artificial intelligence can be used to learn from the environment and past planning decisions which generate optimal routes. One example of this is using reinforcement learning in which the self-driving car learns to identify the best possible routes by trial and error. Other more traditional machine learning techniques can also be used for adaptive navigation. Artificial Neural Networks, for example, are used to audit the driving environment and adapt plans based on the data.

In addition to machine learning methods, techniques from the field of optimisation can also be used to produce enhanced route plans. Tabu search, genetic algorithms and ant-colony optimisation can be applied to solve complex path-finding problems in order to find a global optimum.

Overall, machine learning and artificial intelligence have provided a plethora of techniques to improve route-planning strategies for autonomous vehicles. With the help of advanced data science, autonomous vehicles now have enhanced capabilities which can lead to safer and more efficient navigation.

# A* Path Finding Algorithm
import heapq

#Grid class with basic operations
class Grid(object):

    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.grid = [[0 for _ in range(width)] for _ in range(height)]

    # return node coordinates (x,y) if present else None
    def find(self, value):
        for j in range(self.height):
            for i in range(self.width):
                if self.grid[i][j] == value:
                    return (i, j)
        return None

    def get_node(self, x, y):
        return self.grid[x][y]

    def set_node(self, x, y, value):
        self.grid[x][y] = value

# find optimal route using A* algorithm
def shortest_path(start, end, grid):
    # initialise frontier with starting tuple
    frontier = []
    # loop through the grid to find all nodes
    for i in range(grid.height):
        for j in range(grid.width):
            node = grid.get_node(i, j)
            # check for the value of the node
            # and insert it into frontier
            if( node == 1 or node == -1):
                item = (node + abs(end[0]-i) + abs(end[1]-j), node, (i, j))
                heapq.heappush( frontier, item )
    # make empty list for the visited nodes
    visited = []
    while True:
        if len(frontier) == 0:
            # return failure if no route is found
            return False
        (cost, val, node) = heapq.heappop( frontier )
        # return the node if destination found
        if node == end:
            return node
        # else check the surrounding node
        if node not in visited:
            visited.append(node)
            # get the neighbouring node 
            for (i, j) in [(node[0] - 1, node[1]), (node[0] + 1, node[1]),
            (node[0], node[1] + 1), (node[0], node[1] - 1)]:
                if 0 <= i < grid.height and 0 <= j < grid.width:
                    next1 = grid.get_node(i, j)
                    if( next1 == -1 or next1 == 1 ):
                        path = (next1 + abs(end[0] - i) +
                        abs(end[1] - j), next1, (i, j))
                        heapq.heappush(frontier, path)
    return False

# main function
if __name__ == '__main__':
    # create the grid
    grid = Grid(5, 5)
    # set ceiling or roads
    grid.set_node(0, 2, 1)
    grid.set_node(1, 2, 1)
    grid.set_node(2, 2, 1)
    grid.set_node(3, 2, 1)
    grid.set_node(4, 2, 1)
    grid.set_node(4, 1, 1)
    grid.set_node(4, 0, 1)
    grid.set_node(3, 0, 1)
    grid.set_node(2, 0, 1)
    grid.set_node(1, 0, 1)
    grid.set_node(0, 0, 1)
    # set walls
    grid.set_node(2, 3, -1)
    grid.set_node(3, 3, -1)
    # set start and end points
    start = (0, 4)
    end = (4, 0)
    # perforf the A* algorithm 
    print(shortest_path(start, end, grid))