CN117268412A

CN117268412A - Path planning method, device, equipment, storage medium and vehicle

Info

Publication number: CN117268412A
Application number: CN202210678916.7A
Authority: CN
Inventors: 刘国亮; 湛逸飞
Original assignee: Beijing Co Wheels Technology Co Ltd
Current assignee: Beijing Co Wheels Technology Co Ltd
Priority date: 2022-06-15
Filing date: 2022-06-15
Publication date: 2023-12-22

Abstract

The present disclosure relates to a path planning method, apparatus, device, storage medium, and vehicle, the method comprising: acquiring road network information in a preset area; determining a plurality of path points in the preset area based on the road network information; planning a plurality of paths in the preset area according to the plurality of path points; and determining a test path with the shortest running time of the vehicle according to the paths. The method and the device rapidly and accurately plan the path with the shortest running time in the preset area according to the path planning algorithm through the road network information to support the task of automatic driving simulation test.

Description

Path planning method, device, equipment, storage medium and vehicle

Technical Field

The disclosure relates to the field of computer technology, and in particular, to a path planning method, a device, equipment, a storage medium and a vehicle.

Background

The automatic driving simulation test is to digitize an application scene of automatic driving in a mathematical modeling mode, establish a system model which is as close to the real world as possible, and further simulate the running process of the vehicle on a pre-planned good test route, thereby carrying out test verification on the automatic driving system of the vehicle.

In the existing automatic driving simulation test process, the planning of a test route is mainly finished by manpower, and the defects of low effective rate, unreasonable route planning and the like are overcome.

Therefore, how to plan the test path with the shortest driving time is a problem to be solved.

Disclosure of Invention

In order to solve the above technical problems or at least partially solve the above technical problems, the present disclosure provides a path planning method, apparatus, device, storage medium and vehicle, so as to improve the efficiency and quality of path planning in an autopilot simulation test task.

In a first aspect, an embodiment of the present disclosure provides a path planning method, including:

acquiring road network information in a preset area;

determining a plurality of path points in the preset area based on the road network information;

planning a plurality of paths in the preset area according to the plurality of path points;

and determining a test path with the shortest running time of the vehicle according to the paths.

In a second aspect, an embodiment of the present disclosure provides a path planning apparatus, including:

the acquisition module is used for acquiring road network information in a preset area;

the first determining module is used for determining a plurality of path points in the preset area based on the road network information;

the planning module is used for planning a plurality of paths in the preset area according to the plurality of path points;

and the second determining module is used for determining a test path with the shortest running time of the vehicle according to the paths.

In a third aspect, an embodiment of the present disclosure provides an electronic device, including:

a memory;

a processor; and

a computer program;

wherein the computer program is stored in the memory and configured to be executed by the processor to implement the method according to the first aspect.

In a fourth aspect, embodiments of the present disclosure provide a computer-readable storage medium having stored thereon a computer program for execution by a processor to implement the method of the first aspect.

In a fifth aspect, embodiments of the present disclosure also provide a computer program product comprising a computer program or instructions which, when executed by a processor, implement the method of the first aspect.

In a sixth aspect, embodiments of the present disclosure further provide a vehicle including a path planning apparatus according to the second aspect.

The path planning method, the device, the equipment, the storage medium and the vehicle provided by the embodiment of the disclosure determine the range of path planning by acquiring the road network information in the preset area; determining a plurality of path points in a preset area according to road network information, and providing a data base for subsequent path planning; according to the method, a plurality of paths in a preset area are planned according to a plurality of path points, so that a test path with the shortest running time is determined from the paths, the path with the shortest running time in the preset area can be planned rapidly and accurately according to a path planning algorithm, and the task of automatic driving simulation test is supported by the path with the shortest running time.

Drawings

The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate embodiments consistent with the disclosure and together with the description, serve to explain the principles of the disclosure.

In order to more clearly illustrate the embodiments of the present disclosure or the solutions in the prior art, the drawings that are required for the description of the embodiments or the prior art will be briefly described below, and it will be obvious to those skilled in the art that other drawings can be obtained from these drawings without inventive effort.

Fig. 1 is a flowchart of a path planning method provided in an embodiment of the present disclosure;

fig. 2 is a schematic diagram of a preset area network according to an embodiment of the present disclosure;

fig. 3 is a flowchart of a path planning method provided in an embodiment of the present disclosure;

fig. 4 is a schematic diagram of a preset area network according to an embodiment of the present disclosure;

FIG. 5 is a flow chart of a path planning method according to another embodiment of the present disclosure;

fig. 6 is a schematic structural diagram of a path planning apparatus according to an embodiment of the present disclosure;

fig. 7 is a schematic structural diagram of an electronic device according to an embodiment of the disclosure.

Detailed Description

In order that the above objects, features and advantages of the present disclosure may be more clearly understood, a further description of aspects of the present disclosure will be provided below. It should be noted that, without conflict, the embodiments of the present disclosure and features in the embodiments may be combined with each other.

In the following description, numerous specific details are set forth in order to provide a thorough understanding of the present disclosure, but the present disclosure may be practiced otherwise than as described herein; it will be apparent that the embodiments in the specification are only some, but not all, embodiments of the disclosure.

The embodiments of the present disclosure provide a path planning method, which is described below with reference to specific embodiments.

Fig. 1 is a flowchart of a path planning method according to an embodiment of the present disclosure. The method can be executed by a path planning device, the path planning device can be implemented in a software and/or hardware mode, the path planning device can be configured in electronic equipment, such as a server or a terminal, wherein the terminal specifically comprises any equipment with a data processing function, such as a smart phone, a palm computer, a tablet computer, a notebook computer, an integrated machine and the like. In addition, the method can be applied to application scenes of path planning. It can be appreciated that the path planning method provided by the embodiment of the present disclosure may also be applied in other scenarios.

The following describes a path planning method shown in fig. 1, which includes the following specific steps:

s101, obtaining road network information in a preset area.

Road network (road network) refers to a road system composed of various roads interconnected and interlaced into a mesh distribution in a certain area. The highway network is composed of all levels of highways. Urban road networks, which consist of various roads in urban areas. Urban road networks include free-form and hybrid. The free type is formed along with rivers and coasts according to the topography, such as a road network of Qingdao city in China. The hybrid is a hybrid of several forms, such as the road network of washington, U.S.

Longitude and latitude are coordinate systems composed of longitude and latitude, are spherical coordinate systems which define the space on the earth by utilizing the spherical surface of a three-dimensional space, and can mark any position on the earth. The weft and the warp are auxiliary lines which are assumed by human beings for measuring convenience, and are defined as tracks formed by the rotation of a certain point on the surface of the earth along with the earth. Any one weft is round and is parallel to each other. The length of the weft is the circumference of the equator multiplied by the cosine of the latitude of the weft, so that the equator is longest, the longer the weft is from the equator, the shorter the circumference is, and the two poles are contracted to 0. From the equator north and south, each of which is 90 °, referred to as north latitude and south latitude, denoted by "N" and "S", respectively. Longitude is divided into east and west, north and south, latitude is divided into north and south, and east and west.

And the terminal selects a corresponding preset area from the map according to the appointed longitude and latitude data, and acquires road network information in the preset area. Specifically, a plurality of position points corresponding to the longitude and latitude data can be determined according to the plurality of groups of longitude and latitude data, and a space polygon is established according to the plurality of position points, wherein an area surrounded by the space polygon is a preset area.

S102, determining a plurality of path points in the preset area based on the road network information.

As shown in fig. 2, the preset area is 20, and the road network information of the preset area 20 includes related information of all roads in the preset area, where the road network information of each road includes a plurality of continuous points forming the road. A plurality of intricate roads are arranged in the preset area, each road is composed of a plurality of continuous points, and the terminal can determine a plurality of path points in the preset area according to the plurality of continuous points.

S103, planning a plurality of paths in the preset area according to the plurality of path points.

The Dijkstra algorithm was proposed by the netherlands computer scientist diecktra in 1959 and is therefore also called diecktra algorithm. The shortest path algorithm from one vertex to the rest vertices solves the shortest path problem in the weighted graph. The dijkstra algorithm is mainly characterized by starting from a starting point, adopting a greedy algorithm strategy, traversing each time to the adjacent nodes of the vertex which is nearest to the starting point and is not visited until the vertex is extended to the end point.

The navigation engine is used as a piece of software and service, supports multiple applications such as hybrid navigation, big data intelligent dynamic path planning, high-precision hybrid positioning based on multiple sensors, natural guiding voice broadcasting, voice control and voice intelligent searching based on artificial intelligence technology, navigation data increment updating and daily updating, and the like, and is important for the existing manual driving or automatic auxiliary driving.

The terminal builds a navigation engine by using Dijkstra algorithm based on a road network of a preset area and a plurality of path points. The terminal plans a plurality of paths in the preset area through the navigation engine and the plurality of path points in the preset area. Specifically, the terminal can obtain all paths which can pass between any two path points in the preset area, including the length of the paths, the width of the paths, the distribution condition of traffic lights on the paths and the like.

For example, the terminal acquires all passable paths from the path point 21 to the path point 23 in the preset area 20, including a path from the point 21 to the point 22 and a path from the point 21 to the point 24, the point 25 and the point 26 to the point 23. It is to be understood that the path from the point 21 to the point 23 is not limited to the above-mentioned 2 paths, but includes other paths from the point 21 to the point 23, and this embodiment is not specifically described, and will be described later by taking the above-mentioned 2 paths as examples. The terminal can determine the width of a planned path and a plurality of lanes on the path according to the navigation engine, the width of the lanes is generally 3.75m-4.0m, and the number of lanes on the road surface depends on the road grade and the road design age; the length of the path; traffic light distribution conditions on the path, etc.

S104, determining a test path with the shortest running time of the vehicle according to the paths.

The terminal screens out a test path meeting a preset condition from the paths which can pass through the plurality of paths according to the planning, wherein the preset condition is that the running time of the vehicle is shortest, namely, the test path with the shortest running time of the vehicle is determined in the plurality of paths, and the terminal comprises a path 1, a point 21, a point 22 and a point 23, a path 2, a point 21, a point 24, a point 25, a point 26 and a point 23.

Optionally, the congestion condition of the road, the traffic light setting condition on the road, the accident condition of the vehicle on the road, the peak time condition of the vehicle running on the road, and the like all affect the determination of the test path with the shortest running time.

The method and the device for path planning determine the range of path planning by acquiring the road network information in the preset area; determining a plurality of path points in a preset area according to road network information, and providing a data base for subsequent path planning; according to the method, a plurality of paths in a preset area are planned according to a plurality of path points, so that a test path with the shortest running time is determined from the paths, the path with the shortest running time in the preset area can be planned rapidly and accurately according to a path planning algorithm, and the task of automatic driving simulation test is supported by the path with the shortest running time.

Fig. 3 is a flowchart of a path planning method according to an embodiment of the present disclosure. As shown in fig. 3, the method comprises the following steps:

s301, obtaining road network information in a preset area.

The implementation principle and the specific method of S301 and S101 are identical, and are not repeated here.

S302, determining a plurality of road network points in the preset area based on the road network information.

And determining a plurality of road network points in a preset area according to the road network information. Specifically, the road network comprises a plurality of roads, and each road is composed of a plurality of road points. I.e. a road is made up of a set of numerous road points on the road.

S303, removing repeated road points at the road junction to obtain a plurality of path points in the preset area.

Overlapping road points exist at the junction of different roads, and the overlapping road points respectively belong to the different roads. Taking two road intersection as an example, two overlapped road points exist in the two road intersection, and the two road points respectively belong to the two roads which are intersected with each other, namely each road is provided with one overlapped road point, and the positions of the two overlapped road points are the same, and commonly include an intersection, a T-shaped intersection and the like. And de-duplicating the repeated road points in all the road points in the preset area, namely removing the repeated road points at the road junction, wherein the rest road points are path points in the preset area. As shown in fig. 4, there are at least two overlapped road points at positions other than the points 40, 41, 42, 43, 44 and 45, which respectively belong to different roads, and the repeated road points are removed, so that only one road point at the same position is used as a path point.

S304, sorting the plurality of path points, and determining the starting point of the test path based on the sorting result.

Specifically, determining a datum point on the boundary of the preset area, and calculating distances between the plurality of path points and the datum point respectively; and determining a path point closest to the datum point as a starting point of the test path.

A point on the boundary of the preset area is selected as a reference point, for example, a point with the smallest longitude and latitude on the boundary of the preset area (i.e. the southeast angle of the preset area) is selected as a reference point, and the actual distance between each path point and the reference point is calculated. And sorting the plurality of path points according to the actual distances from small to large, and selecting the path point with the smallest actual distance from the reference point in the plurality of path points as the starting point of the test path planning. The actual distance between the path point and the reference point is the geographic distance between the path point and the reference point, and is not the euclidean distance. It may be understood that, in the embodiment of the present disclosure, a point with the smallest longitude and latitude on the boundary of the preset area (i.e. the southeast angle of the preset area) is selected as the reference point, and a path point with the smallest actual distance from the reference point is selected as the starting point of the test path planning, which is only an example, and in actual situations, different reference points may be selected according to specific requirements and corresponding ranking rules may be determined.

For example, as shown in fig. 4, the southeast corner of the preset area is used as a reference point, and the actual distance between the point 40 and the reference point is the smallest, that is, the point 40 is used as a starting point.

Alternatively, the start point of the test path may also be determined in the following manner. The selected preset area is taken as basic data, the southeast angular position is taken as a reference point, the selected preset area is divided according to a preset distance to generate grid data, the preset distance can be 1km x 1km, other distances can be also used, and the embodiment is not particularly limited. The method comprises the steps of mapping the space positions of a plurality of path points into grids, screening out grid combinations containing the path points, deleting other grids which do not contain the path points, wherein the other grids and the grids containing the path points have no space relation, and the path points in the obtained grid combinations are the sampled path points. The path point contained in the last grid is selected as the starting point for the test path plan.

S305, determining any one of the path points except the starting point as the end point of the test path.

Any one of the plurality of path points other than the start point is determined as the end point of the test path.

For example, as shown in fig. 4, the path points such as point 41, point 42, point 43, etc. may be used as the end points of the test path. The point 43 is exemplified as an end point.

Alternatively, the end point of the test path may also be determined in the following manner. One of the path points is randomly selected as an end point of the test path in a grid containing a plurality of path points.

S306, planning a plurality of paths in the preset area based on the starting point and the ending point.

The terminal builds a navigation engine by using Dijkstra algorithm based on a road network of a preset area and a plurality of path points. The terminal plans a plurality of paths in the preset area according to the road network information, the starting point and the end point of the preset area and a plurality of path points in the preset area. Specifically, the terminal can obtain all paths which can pass between any two path points in the preset area, including the length of the paths, the width of the paths, the distribution condition of traffic lights on the paths and the like.

Optionally, starting from the starting point, searching all paths containing the starting point according to the road network running direction and the precursor successor relation of the road network, searching all successor paths of the paths containing the starting point, if the paths containing the starting point have a plurality of successor paths, respectively selecting a plurality of successor paths to insert the rear part of the paths containing the starting point and the paths containing the starting point into a plurality of path groups, using the serial numbers of the successor paths as the successor serial numbers of the path groups, continuing searching the successor paths, and repeating the process to obtain a plurality of path group data; starting from the end point, searching all paths containing the end point according to the road network running direction and the precursor successor relation of the road network, searching all precursor paths of the paths containing the end point, if the paths containing the end point have a plurality of successor paths, respectively selecting a plurality of precursor paths to insert the front part of the paths containing the end point and the paths containing the key points into a plurality of path groups, combining the numbers of the precursor paths as the numbers of the path groups, continuously searching the precursor paths, and repeating the process to obtain a plurality of path group data; repeating the steps until the two path groups have intersection; and merging the two groups of paths according to the precursor successor relationship of the path groups, finding all path combinations from the starting point to the end point, and determining a plurality of paths in a preset area.

For example, when the start point is point 40 and the end point is point 43, the planned path may be a plurality of paths 40-41-42-43, 40-44-45-43, 40-44-42-43, and so on.

S307, determining a test path with the shortest running time of the vehicle according to the paths.

Specifically, according to the paths, determining road conditions of the paths; respectively determining the running time of the vehicle on the multiple paths according to the road conditions of the multiple paths; and determining a test path with the shortest running time of the vehicle according to the running time of the vehicle on the paths.

Optionally, according to the distances of the paths and the specified running speed of each path, calculating the time required for passing through the paths, and selecting one path combination with the shortest time as the test path with the shortest running time of the vehicle.

Determining road conditions of the multiple paths according to the planned paths, wherein the road conditions comprise road congestion, traffic light setting conditions on the roads, road bending degree and the like; according to the road conditions of the multiple roads, determining the running speed of the vehicle according to the usual running speed of the vehicle, the congestion condition of the road and the speed limit condition of the road, so as to respectively determine the running time of the vehicle on the multiple paths; and determining a test path with the shortest running time when the vehicle is in disorder according to the running time of the vehicle on the plurality of paths.

For example, a plurality of planned paths 40-41-42-43, 40-44-45-43 and 40-44-42-43 are taken as examples, the number of red road lamps of the paths 40-41-42-43 is large, the number of lanes of the paths 40-44-45-43 is small, traffic jam is easy to occur, and the number of red road lamps of the paths 40-44-42-43 is small and the road is smooth compared with the two paths. The running path lengths of the three roads are the same, and the average running speed of the vehicle on the three roads is determined according to the road speed limit condition and the road congestion condition at the same time, so that the running time on each road is obtained according to the distance and the speed of the vehicle. The travel time of the vehicles on each road is ordered, and the test path with the shortest travel time of the vehicles, namely the path 40-44-42-43, is obtained.

The method and the device for path planning determine the range of path planning by acquiring the road network information in the preset area; determining a plurality of road points in the preset area based on the road network information, removing repeated road points at the road junction to obtain a plurality of path points in the preset area, sequencing the plurality of path points, and determining the starting point of the test path based on the sequencing result; determining any one point except the starting point in the path points as an end point of the test path, planning a plurality of paths in the preset area based on the starting point and the end point, and providing a data base for subsequent path planning; and determining road conditions of the multiple paths according to the multiple paths, respectively determining running time of the vehicle on the multiple paths according to the road conditions of the multiple paths, and determining a test path with the shortest running time of the vehicle according to the running time of the vehicle on the multiple paths. The method can rapidly and accurately plan the test path which meets the requirements in the preset area according to the preset effect and acquire the corresponding test path data set, for example, the path with the shortest running time in the preset area can be rapidly and accurately planned according to the path planning algorithm, and the task of automatic driving simulation test is supported by the path with the shortest running time, so that the unreasonability of manually planning the path is avoided, and the efficiency and quality of path planning are improved.

On the basis of the above embodiment, the method further includes: removing other path points in the plurality of paths from the plurality of path points, the other path points being path points in the plurality of paths other than the start point and the end point; sequencing the rest path points, and re-determining the starting point and the end point of the path; and planning a plurality of paths in the preset area based on the redetermined starting point and the redetermined ending point.

After determining the paths, removing the path points except the two path points of the starting point and the end point from the paths so as to avoid repeated planning of the same path. And re-ordering the rest path points, and re-determining the starting point and the end point according to the re-ordering result.

Optionally, in the step, a path point closest to the reference point is determined as a first start point, another path point is randomly selected as a first end point, after a corresponding plurality of first paths are determined, all path points except the first start point and the end point included in the plurality of first paths are removed from the plurality of initially obtained path points, and the next start point is continuously selected according to the distance between the path point and the reference point, namely, the path point closest to the reference point is determined as a second start point. If the path point that is the second closest to the reference point has been removed, then the path point that is the third closest to the reference point is continued to be selected as the second starting point, and so on, until a point that has not been removed is determined as the second starting point. And repeatedly executing the steps until all the path points in the plurality of path points are traversed, and finally obtaining a test path data set corresponding to the preset area.

For example, as shown in fig. 2, if in the process of path planning, the starting point is determined to be point 21, the end point is determined to be point 22, the test path is finally determined to be path 24, after the path points and the related road network information thereof included in the path 24 are stored in the test path data set, the path points except for the starting point 21 and the end point 22 in the path points included in the path 24 are removed from the plurality of path points, and the starting point and the end point are reselected to perform corresponding path planning; as shown in fig. 4, if the starting point is determined to be the point 40 and the end point is determined to be the point 43 in the process of one path planning, when the test path is finally determined to be the path 40-44-42-43, after the path points and the related road network information contained in the path 40-44-42-43 are stored in the test path data set, the path points except the starting point 40 and the end point 43 in the path points contained in the path 40-44-42-43 are removed from the plurality of path points, and the starting point and the end point are reselected to perform corresponding path planning.

Embodiments of the present disclosure provide for removing other path points in the plurality of paths from the plurality of path points, the other path points being path points in the plurality of paths other than the start point and the end point; sequencing the rest path points, and re-determining a starting point and an ending point; based on the redetermined starting point and end point, planning a plurality of paths in the preset area, excluding the path points of the planned paths, avoiding repeated planning of the same paths, saving operation resources, improving the path planning efficiency, ensuring that all possible paths in the preset area can be planned by traversing all path points, further selecting the test path which meets the requirements most, namely the test path with the shortest running time, and ensuring the comprehensiveness and accuracy of path planning.

Fig. 5 is a flowchart of a path planning method according to another embodiment of the present disclosure. As shown in fig. 5, the method comprises the following steps:

s501, obtaining road network information in a preset area.

The implementation principles and specific methods of S501 and S101 are identical, and are not repeated here.

S502, determining a plurality of road network points in the preset area based on the road network information.

The implementation principles and specific methods of S502 and S302 are identical, and are not repeated here.

S503, removing repeated road points at the road junction to obtain a path point set in the preset area.

The road network comprises a plurality of roads, and each road consists of a plurality of road points. At the junction of different roads, there may be two overlapped road network points, where the two road network points respectively belong to two different roads that are intersected with each other, but the positions of the two road network points are the same, and if there are multiple repeated points at the same position during path planning, the subsequent path planning may be affected, for example, two identical paths may be planned based on the two road network points that are repeated at the junction of the roads. And the rest road points are taken as the path points in the preset area, and the path points form a path point set.

S504, determining a starting point and an ending point based on the path point set.

Selecting a path point which accords with a preset rule from the path point set as a starting point, and selecting any point except the starting point as an end point. Wherein, a point on the boundary of the preset area can be selected as a reference point, and the actual distance between each path point and the reference point is calculated. And sorting the plurality of path points according to the actual distances from small to large, and selecting the path point with the smallest actual distance from the reference point in the plurality of path points as the starting point of the test path planning.

S505, planning a plurality of paths in the preset area based on the starting point and the ending point.

And constructing a navigation engine by using a Dijkstra algorithm based on the road network information of the preset area and a plurality of path points in the preset area. And randomly selecting any path point except the starting point from a plurality of path points as an end point of path planning. Based on the determined starting point and the determined end point, a navigation engine can be used for planning all trafficable paths between the starting point and the end point in a preset area. And further planning a plurality of paths in the preset area.

S506, determining a test path with the shortest running time of the vehicle according to the paths.

The implementation principles and specific methods of S506 and S307 are identical, and will not be repeated here.

S507, removing other path points in the paths from a path point set, wherein the other path points are path points except the starting point and the ending point in the paths.

After determining the paths, removing the path points except the two path points of the starting point and the end point from the paths so as to avoid repeated planning of the same path.

S508, judging whether the number of the path points in the path point set is larger than a preset value. If yes, executing S504; if not, S509 is performed.

And repeating the steps S504-S506 until the number of the rest path points in the path point set is less than or equal to a preset threshold value. In some embodiments, the preset value may be 2, and when the number of the path points in the path point set is not greater than two, it represents that all the path points in the path point set have been traversed, and at this time, all the test paths in the preset area have been planned, and the remaining two path points in the path point set are the start point and the end point of the test path when the last path is planned.

S509, ending.

According to the embodiment of the disclosure, the path in the preset area is rapidly and accurately planned based on the road network information according to the path planning algorithm to support the task of automatic driving simulation test, compared with manual planning, the method and the device have the advantages of being more reasonable in planning speed and improving the efficiency and flexibility of path planning.

Fig. 6 is a schematic structural diagram of a path planning apparatus according to an embodiment of the present disclosure. The path planning device may be a terminal as described in the above embodiments, or the path planning device may be a part or component in the terminal. The path planning apparatus provided in the embodiment of the present disclosure may execute the processing flow provided in the embodiment of the path planning method, as shown in fig. 6, where the path planning apparatus 60 includes: an acquisition module 61, a first determination module 62, a planning module 63, a second determination module 64; the acquiring module 61 is configured to acquire road network information in a preset area; a first determining module 62, configured to determine a plurality of path points in the preset area based on the road network information; a planning module 63, configured to plan a plurality of paths in the preset area according to the plurality of path points; the second determining module 64 is configured to determine, according to the multiple paths, a test path with a shortest running time of the vehicle.

Optionally, the first determining module 62 is further configured to determine a plurality of road network points in the preset area based on the road network information; and removing repeated road points at the road junction to obtain a plurality of path points in the preset area.

Optionally, the planning module 63 is further configured to sort the plurality of path points, and determine a start point of the test path based on a sorting result; determining any one of the plurality of path points except the starting point as an end point of the test path; and planning a plurality of paths in the preset area based on the starting point and the ending point.

Optionally, the planning module 63 is further configured to determine a reference point on the preset area boundary, and calculate distances between the plurality of path points and the reference point respectively; and determining a path point closest to the datum point as a starting point of the test path.

Optionally, the planning module 63 is further configured to remove other path points in the plurality of paths from the plurality of path points, where the other path points are path points in the plurality of paths except the start point and the end point; sequencing the rest path points, and re-determining the starting point and the end point of the path; and planning a plurality of paths in the preset area based on the redetermined starting point and the redetermined ending point.

Optionally, the second determining module 64 is further configured to determine road conditions of the multiple paths according to the multiple paths; respectively determining the running time of the vehicle on the multiple paths according to the road conditions of the multiple paths; and determining a test path with the shortest running time of the vehicle according to the running time of the vehicle on the paths.

The path planning apparatus of the embodiment shown in fig. 6 may be used to implement the technical solution of the above-mentioned method embodiment, and its implementation principle and technical effects are similar, and will not be described herein again.

Fig. 7 is a schematic structural diagram of an electronic device according to an embodiment of the disclosure. The electronic device may be a terminal as described in the above embodiments. The electronic device provided in the embodiment of the present disclosure may execute the processing flow provided in the path planning method embodiment, as shown in fig. 7, where the electronic device 70 includes: memory 71, processor 72, computer programs and communication interface 73; wherein the computer program is stored in the memory 71 and configured to be executed by the processor 72 for performing the path planning method as described above.

In addition, the embodiment of the present disclosure also provides a computer-readable storage medium having stored thereon a computer program that is executed by a processor to implement the path planning method described in the above embodiment.

Furthermore, the disclosed embodiments also provide a computer program product comprising a computer program or instructions which, when executed by a processor, implements a path planning method as described above.

In addition, the embodiment of the disclosure also provides a vehicle, which comprises the obstacle point cloud data processing device.

It should be noted that the computer readable medium described in the present disclosure may be a computer readable signal medium or a computer readable storage medium, or any combination of the two. The computer readable storage medium can be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or a combination of any of the foregoing. More specific examples of the computer-readable storage medium may include, but are not limited to: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a Random Access Memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this disclosure, a computer-readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device. In the present disclosure, however, the computer-readable signal medium may include a data signal propagated in baseband or as part of a carrier wave, with the computer-readable program code embodied therein. Such a propagated data signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, or any suitable combination of the foregoing. A computer readable signal medium may also be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device. Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to: electrical wires, fiber optic cables, RF (radio frequency), and the like, or any suitable combination of the foregoing.

In some implementations, the clients, servers may communicate using any currently known or future developed network protocol, such as HTTP (HyperText Transfer Protocol ), and may be interconnected with any form or medium of digital data communication (e.g., a communication network). Examples of communication networks include a local area network ("LAN"), a wide area network ("WAN"), the internet (e.g., the internet), and peer-to-peer networks (e.g., ad hoc peer-to-peer networks), as well as any currently known or future developed networks.

The computer readable medium may be contained in the electronic device; or may exist alone without being incorporated into the electronic device.

The computer readable medium carries one or more programs which, when executed by the electronic device, cause the electronic device to:

acquiring road network information in a preset area;

In addition, the electronic device may also perform other steps in the path planning method as described above.

Computer program code for carrying out operations of the present disclosure may be written in one or more programming languages, including, but not limited to, an object oriented programming language such as Java, smalltalk, C ++ and conventional procedural programming languages, such as the "C" programming language or similar programming languages. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the case of a remote computer, the remote computer may be connected to the user's computer through any kind of network, including a Local Area Network (LAN) or a Wide Area Network (WAN), or may be connected to an external computer (for example, through the Internet using an Internet service provider).

The flowcharts and block diagrams in the figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present disclosure. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems which perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.

The units involved in the embodiments of the present disclosure may be implemented by means of software, or may be implemented by means of hardware. Wherein the names of the units do not constitute a limitation of the units themselves in some cases.

The functions described above herein may be performed, at least in part, by one or more hardware logic components. For example, without limitation, exemplary types of hardware logic components that may be used include: a Field Programmable Gate Array (FPGA), an Application Specific Integrated Circuit (ASIC), an Application Specific Standard Product (ASSP), a system on a chip (SOC), a Complex Programmable Logic Device (CPLD), and the like.

In the context of this disclosure, a machine-readable medium may be a tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device. The machine-readable medium may be a machine-readable signal medium or a machine-readable storage medium. The machine-readable medium may include, but is not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples of a machine-readable storage medium would include an electrical connection based on one or more wires, a portable computer diskette, a hard disk, a Random Access Memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing.

It should be noted that in this document, relational terms such as "first" and "second" and the like are used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. Moreover, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, an element defined by the phrase "comprising one … …" does not exclude the presence of other like elements in a process, method, article, or apparatus that comprises the element.

The foregoing is merely a specific embodiment of the disclosure to enable one skilled in the art to understand or practice the disclosure. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the disclosure. Thus, the present disclosure is not intended to be limited to the embodiments shown and described herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

Claims

1. A method of path planning, the method comprising:

acquiring road network information in a preset area;

2. The method of claim 1, wherein the determining a plurality of waypoints within the preset area based on the road network information comprises:

determining a plurality of road network points in the preset area based on the road network information;

and removing repeated road points at the road junction to obtain a plurality of path points in the preset area.

3. The method of claim 1, wherein planning a plurality of paths within the predetermined area based on the plurality of path points comprises:

sorting the plurality of path points, and determining the starting point of the test path based on the sorting result;

determining any one of the plurality of path points except the starting point as an end point of the test path;

and planning a plurality of paths in the preset area based on the starting point and the ending point.

4. A method according to claim 3, wherein said sorting the plurality of path points, determining the start of the test path based on the sorting result, comprises:

determining a datum point on the preset area boundary, and calculating distances between the plurality of path points and the datum point respectively;

and determining a path point closest to the datum point as a starting point of the test path.

5. A method according to claim 3, characterized in that the method further comprises:

removing other path points in the plurality of paths from the plurality of path points, the other path points being path points in the plurality of paths other than the start point and the end point;

sequencing the rest path points, and re-determining the starting point and the end point of the path;

and planning a plurality of paths in the preset area based on the redetermined starting point and the redetermined ending point.

6. The method of claim 1, wherein determining a test path with a shortest vehicle travel time based on the plurality of paths comprises:

determining road conditions of the multiple paths according to the multiple paths;

respectively determining the running time of the vehicle on the multiple paths according to the road conditions of the multiple paths;

and determining a test path with the shortest running time of the vehicle according to the running time of the vehicle on the paths.

7. A path planning apparatus, the apparatus comprising:

8. An electronic device, comprising:

a memory;

a processor; and

a computer program;

wherein the computer program is stored in the memory and configured to be executed by the processor to implement the method of any one of claims 1-6.

9. A computer readable storage medium, on which a computer program is stored, which computer program, when being executed by a processor, implements the method according to any of claims 1-6.

10. A vehicle, comprising: a path planning apparatus according to claim 8.