Path planning method and system

Abstract

The invention provides a method for planning a path in an urban road traffic network. The method comprises the steps of dividing a region to be searched, which is determined according to a start point and a final point, into multiple sub regions according to a given road network density; then mapping the multiple sub regions into one-dimensional discrete points, and forming a Voronoi graph based on the discrete points; determining an adjacency relation between every two of all the sub regions according to the Voronoi graph, and judging the connectivity between every two adjacent sub regions; constructing a new road network according to a set of the selected adjacent sub regions which are communicated, and searching an optimal path between the start point and the final point in the new constructed road network. According to the method, the construction time of a road network topological structure is shortened; furthermore, the search range of the path is narrowed, the search time is shortened and the search efficiency is improved.

Description

technical field [0001] The invention belongs to the field of intelligent road traffic, in particular to a method for path planning in intelligent traffic. Background technique [0002] Path planning is the most basic application in intelligent transportation, that is, to select the shortest path from the current point to the target point as the travel route for travelers in the urban road traffic network. Urban road traffic network (referred to as road network for short) is usually represented by an undirected graph with weights. Among them, intersections in the road network are regarded as vertices of the undirected graph, and paths in the road network are edges in the undirected graph. The classic methods for solving the shortest path in a graph include methods such as Dijkstra, Folyd, and A*. However, these classic shortest path algorithms generally have problems such as high computational complexity and excessive storage consumption when dealing with large-scale road n...

AI Technical Summary

Problems solved by technology

The problem with this method is that as the number of network layers constructed increases, the time consumption and storage space required for preprocessing will also increase, and it does not solve the problem of large-scale road networks.

This scheme has fast response time and high accuracy for low-density object query time, but the processing efficiency for high-density objects is significantly reduced, and multiple queries need to be executed to query the k-nearest neighbors of an object

Images