Systems and methods for route planning on topographical map using vehicle motion
The present disclosure may provide a method for route planning. The method may include obtaining a start location and a destination of a target vehicle. The method may also include obtaining a map of a target region including the start location and the destination. The map may include node information of each of a plurality of nodes. Further, the method may include obtaining motion status information associated with one or more vehicles other than the target vehicle in the target region. The method may further include determining a target route of the target vehicle based at least in part on the start location, the destination, the motion status information associated with the one or more vehicles, and the map.
1. A system for route planning, comprising:
at least one storage device including a set of instructions; and
at least one processor in communication with the at least one storage device, wherein when executing the set of instructions, the at least one processor is configured to cause the system to:
obtain a start location and a destination of a target vehicle;
obtain a map of a target region including the start location and the destination, the map including node information of each of a plurality of nodes;
obtain motion status information associated with one or more vehicles other than the target vehicle in the target region; and
determine a target route of the target vehicle based at least in part on the start location, the destination, the motion status information associated with the one or more vehicles, and the map;
wherein to determine the target route of the target vehicle based at least in part on the start location, the destination, the motion status information associated with the one or more vehicles, and the map, the at least one processor is configured to cause the system to:
identify one or more static vehicles from the one or more vehicles based on the motion status information;
for each of the one or more static vehicles, determine a preset region including one or more nodes associated with the static vehicle;
for each of the one or more nodes associated with the static vehicle, modify the node information of the node by designating the node as a barrier;
identify one or more moving vehicles from the one or more vehicles based on the motion status information;
for each of the one or more moving vehicles, determine one or more nodes associated with a predetermined route corresponding to the moving vehicle;
for each of the one or more nodes associated with the moving vehicle, modify the node information of the node by assigning a weight value larger than a predetermined threshold to the node;
determine the target map based on the map, the modified node information of the one or more nodes associated with each of the one or more static vehicles, and the modified node information of the one or more nodes associated with each of the one or more moving vehicles;
determine a start node from the plurality of nodes based on the start location in the target map;
determine a destination node from the plurality of nodes based on the destination in the target map; and
determine the target route of the target vehicle based on a plurality of costs associated with a plurality of target nodes between the start node and the destination node, wherein each cost associated with each target node of the plurality of target nodes is a sum of a first cost from the start node to the target node and a second cost from the target node to the destination node, the first cost is determined according to formula (1) below:
g ( n )=cost( n )+ g ( n pre )+ dis ( n pre ,n )+angle( n pre ,n ) (1)
where cost(n) refers to a weight value of the target node, g(n pre ) refers to a cost of a parent node of the target node, dis(n pre , n) refers to a cost from the parent node of the target node to the target node, and angle(n pre , n) refers to a turn cost from the parent node of the target node to the target node, and
the second cost is determined according to formula (2) below:
h ( n )=| x s 0 −x n |+|y s 0 −y n | (2)
where x s 0 and y s 0 refer to an X-coordinate and a Y-coordinate of the destination node respectively and x n and y n refer to an X-coordinate and a Y-coordinate of the target node respectively.
2. The system of claim 1 , wherein the node information of each of the plurality of nodes includes at least one of a location of the node, a barcode of the node, a coordinate of the node, a passability of the node, a turn capability of the node, a count of adjacent nodes, or a connectivity of the node to the adjacent nodes.
3. The system of claim 1 , wherein, for each of the one or more nodes associated with the static vehicle, to modify the node information of the node, the at least one processor is directed to:
assign a weight value larger than a predetermined threshold to the node, and
designate the node as a node incapable of a turn left or a turn right at the node.
4. The system of claim 1 , wherein the at least one processor is configured to cause the system further to:
determine a candidate map based on the map and the modified node information of the one or more nodes associated with each of the one or more static vehicles; and
determine a candidate route of the target vehicle based on the candidate map, the start location, and the destination;
determine whether the candidate route at least partially overlaps with at least part of at least one predetermined route that has not been passed, the at least one predetermined route corresponding to at least one moving vehicle of the one or more vehicles; and
in response to a determination that the candidate route does not overlap with the at least one predetermined route that has not been passed, designate the candidate route as the target route of the target vehicle.
5. The system of claim 4 , wherein the at least one processor is configured to cause the system further to:
in response to a determination that the candidate route at least partially overlaps with the at least part of the at least one predetermined route that has not been passed, for each of the one or more nodes associated with the static vehicle, modify the node information of the node;
identify one or more moving vehicles from the one or more vehicles based on the motion status information;
for each of the one or more moving vehicles, determine one or more nodes associated with a predetermined route corresponding to the moving vehicle;
for each of the one or more nodes associated with the moving vehicle, modify the node information of the node;
determine a second candidate map based on the map, the modified node information of the one or more nodes associated with each of the one or more static vehicles, and the modified node information of the one or more nodes associated with each of the one or more moving vehicles; and
determine a second candidate route of the target vehicle based on the second candidate map, the start location, and the destination.
6. A method implemented on a computing device including at least one processor, at least one storage medium, and a communication platform connected to a network, the method comprising:
obtaining a start location and a destination of a target vehicle;
obtaining a map of a target region including the start location and the destination, the map including node information of each of a plurality of nodes;
obtaining motion status information associated with one or more vehicles other than the target vehicle in the target region; and
determining a target route of the target vehicle based at least in part on the start location, the destination, the motion status information associated with the one or more vehicles, and the map;
wherein the determining the target route of the target vehicle based at least in part on the start location, the destination, the motion status information associated with the one or more vehicles, and the map includes:
identifying one or more static vehicles from the one or more vehicles based on the motion status information;
for each of the one or more static vehicles, determining a preset region including one or more nodes associated with the static vehicle;
for each of the one or more nodes associated with the static vehicle, modifying the node information of the node by designating the node as a barrier;
identifying one or more moving vehicles from the one or more vehicles based on the motion status information;
for each of the one or more moving vehicles, determining one or more nodes associated with a predetermined route corresponding to the moving vehicle;
for each of the one or more nodes associated with the moving vehicle, modifying the node information of the node by assigning a weight value larger than a predetermined threshold to the node;
determining the target map based on the map, the modified node information of the one or more nodes associated with each of the one or more static vehicles, and the modified node information of the one or more nodes associated with each of the one or more moving vehicles;
determining a start node from the plurality of nodes based on the start location in the target map;
determining a destination node from the plurality of nodes based on the destination in the target map; and
determining the target route of the target vehicle based on a plurality of costs associated with a plurality of target nodes between the start node and the destination node, wherein each cost associated with each target node of the plurality of target nodes is a sum of a first cost from the start node to the target node and a second cost from the target node to the destination node, the first cost is determined according to formula (1) below:
g ( n )=cost( n )+ g ( n pre )+ dis ( n pre ,n )+angle( n pre ,n ) (1)
where cost(n) refers to a weight value of the target node, g(n pre ) refers to a cost of a parent node of the target node, dis(n pre , n) refers to a cost from the parent node of the target node to the target node, and angle(n pre , n) refers to a turn cost from the parent node of the target node to the target node, and
the second cost is determined according to formula (2) below:
h ( n )=| x s 0 −x n |+|y s 0 −y n | (2)
where x s 0 and y s 0 refer to an X-coordinate and a Y-coordinate of the destination node respectively and x n and y n refer to an X-coordinate and a Y-coordinate of the target node respectively.
7. The method of claim 6 , wherein for each of the one or more nodes associated with the static vehicle, the modifying the node information of the node includes:
assigning a weight value larger than a predetermined threshold to the node, and designating the node as a node incapable of a turn left or a turn right at the node.
8. The method of claim 6 , further comprising:
determining a candidate map based on the map and the modified node information of the one or more nodes associated with each of the one or more static vehicles; and
determining a candidate route of the target vehicle based on the candidate map, the start location, and the destination;
determining whether the candidate route at least partially overlaps with at least part of at least one predetermined route that has not been passed, the at least one predetermined route corresponding to at least one moving vehicle of the one or more vehicles; and
in response to a determination that the candidate route does not overlap with the at least one predetermined route that has not been passed, designating the candidate route as the target route of the target vehicle.
9. The method of claim 8 , further comprising:
in response to a determination that the candidate route at least partially overlaps with the at least part of the at least one predetermined route that has not been passed, for each of the one or more nodes associated with the static vehicle, modifying the node information of the node;
identifying one or more moving vehicles from the one or more vehicles based on the motion status information;
for each of the one or more moving vehicles, determining one or more nodes associated with a predetermined route corresponding to the moving vehicle;
for each of the one or more nodes associated with the moving vehicle, modifying the node information of the node;
determining a second candidate map based on the map, the modified node information of the one or more nodes associated with each of the one or more static vehicles, and the modified node information of the one or more nodes associated with each of the one or more moving vehicles; and
determining a second candidate route of the target vehicle based on the second candidate map, the start location, and the destination.
10. The method of claim 6 , wherein the node information of each of the plurality of nodes includes at least one of a location of the node, a barcode of the node, a coordinate of the node, a passability of the node, a turn capability of the node, a count of adjacent nodes, or a connectivity of the node to the adjacent nodes.
11. A non-transitory computer readable medium, comprising executable instructions that, when executed by at least one processor, direct the at least one processor to perform a method, the method comprising:
obtaining a start location and a destination of a target vehicle;
obtaining a map of a target region including the start location and the destination, the map including node information of each of a plurality of nodes;
obtaining motion status information associated with one or more vehicles other than the target vehicle in the target region; and
determining a target route of the target vehicle based at least in part on the start location, the destination, the motion status information associated with the one or more vehicles, and the map, wherein the determining the target route of the target vehicle based at least in part on the start location, the destination, the motion status information associated with the one or more vehicles, and the map includes:
identifying one or more static vehicles from the one or more vehicles based on the motion status information;
for each of the one or more static vehicles, determining a preset region including one or more nodes associated with the static vehicle;
for each of the one or more nodes associated with the static vehicle, modifying the node information of the node by designating the node as a barrier;
identifying one or more moving vehicles from the one or more vehicles based on the motion status information;
for each of the one or more moving vehicles, determining one or more nodes associated with a predetermined route corresponding to the moving vehicle;
for each of the one or more nodes associated with the moving vehicle, modifying the node information of the node by assigning a weight value larger than a predetermined threshold to the node;
determining the target map based on the map, the modified node information of the one or more nodes associated with each of the one or more static vehicles, and the modified node information of the one or more nodes associated with each of the one or more moving vehicles;
determining a start node from the plurality of nodes based on the start location in the target map;
determining a destination node from the plurality of nodes based on the destination in the target map; and
determining the target route of the target vehicle based on a plurality of costs associated with a plurality of target nodes between the start node and the destination node, wherein each cost associated with each target node of the plurality of target nodes is a sum of a first cost from the start node to the target node and a second cost from the target node to the destination node, the first cost is determined according to formula (1) below:
g ( n )=cost( n )+ g ( n pre )+ dis ( n pre ,n )+angle( n pre ,n ) (1)
where cost(n) refers to a weight value of the target node, g(n pre ) refers to a cost of a parent node of the target node, dis(n pre , n) refers to a cost from the parent node of the target node to the target node, and angle(n pre , n) refers to a turn cost from the parent node of the target node to the target node, and
the second cost is determined according to formula (2) below:
h ( n )=| x s 0 −x n |+|y s 0 −y n | (2)
where x s 0 and y s 0 refer to an X-coordinate and a Y-coordinate of the destination node respectively and x n and y n refer to an X-coordinate and a Y-coordinate of the target node respectively.
12. The non-transitory computer readable medium of claim 11 , wherein, for each of the one or more nodes associated with the static vehicle, the modifying the node information of the node includes:
assigning a weight value larger than a predetermined threshold to the node, and
designating the node as a node incapable of a turn left or a turn right at the node.
13. The non-transitory computer readable medium of claim 11 , the method further comprising:
determining a candidate map based on the map and the modified node information of the one or more nodes associated with each of the one or more static vehicles; and
determining a candidate route of the target vehicle based on the candidate map, the start location, and the destination;
determining whether the candidate route at least partially overlaps with at least part of at least one predetermined route that has not been passed, the at least one predetermined route corresponding to at least one moving vehicle of the one or more vehicles; and
in response to a determination that the candidate route does not overlap with the at least one predetermined route that has not been passed, designating the candidate route as the target route of the target vehicle.
14. The non-transitory computer readable medium of claim 13 , the method further comprising:
in response to a determination that the candidate route at least partially overlaps with the at least part of the at least one predetermined route that has not been passed, for each of the one or more nodes associated with the static vehicle, modifying the node information of the node;
identifying one or more moving vehicles from the one or more vehicles based on the motion status information;
for each of the one or more moving vehicles, determining one or more nodes associated with a predetermined route corresponding to the moving vehicle;
for each of the one or more nodes associated with the moving vehicle, modifying the node information of the node;
determining a second candidate map based on the map, the modified node information of the one or more nodes associated with each of the one or more static vehicles, and the modified node information of the one or more nodes associated with each of the one or more moving vehicles; and
determining a second candidate route of the target vehicle based on the second candidate map, the start location, and the destination.