CN-116796913-B - Multi-vehicle path planning optimization method based on conflict

Abstract

The invention discloses a multi-vehicle path planning optimization method based on conflict, which is characterized in that before a vehicle moves, search expectations are relaxed, a feasible path set is generated, continuous optimization is carried out on the feasible path set, and the optimization is carried out continuously until the vehicle moves. The invention can effectively avoid two problems in the prior art, and has the characteristics of wide adaptability and high retrieval efficiency.

Inventors

• WANG XIAOJIN
• JIN XIN
• CHEN BO

Assignees

• 上海振华重工(集团)股份有限公司

Dates

Publication Date

20260512

Application Date

20221229

Claims (3)

1. 1. A multi-vehicle path planning optimization method based on conflict is characterized by comprising the following steps: before the vehicle moves, the search expectations are relaxed, a feasible path set is generated, continuous optimization is carried out on the feasible path set, continuous optimization is carried out to the running stage of the vehicle, The generating a set of possible paths further comprises: s1, generating a space shortest path for each vehicle independently, and then estimating time windows of all nodes of the space shortest path; S2, adding the next path into the space-time conflict graph according to the priority, and constructing time constraint according to a first-come first-go mode when two vehicles pass through the same node; s3, judging whether the step S2 is feasible or not, if yes, ending, otherwise, entering the step S4; S4, canceling a path of the newly added vehicle and adding the newly added vehicle to the list to be re-planned; S5, judging whether a path which is not added with the conflict exists, if yes, returning to the step S2, and if no, entering the step S6; S6, carrying out feasible path planning on each vehicle to be re-planned, In the step S1, the single vehicle feasible path planning further includes: s101, packing a directed connected graph G formed by a starting point and other paths and a conflict tree into a search node, and storing the search node to a weight priority list open_list by taking the current shortest path as weight; s102, judging whether a weight priority list open_list is empty, if so, indicating that a path does not exist, ending, and if not, entering a step S103; S103, selecting an optimal searching node in a weight priority list open_list, taking a path node C in the optimal searching node, and inquiring a shortest path R2 formed by C to a terminal point; s104, attempting to add the shortest path R2 to the directed communication graph G; S105, judging whether a strong communication component exists, if so, entering a step S106, otherwise, combining a shortest path R1 from a starting point to a path node C and R2 formed from the path node C to an end point into an optimal path, and adding the optimal path into a directed communication graph G to generate a new directed communication graph G; s106, judging whether a subsequent space node N of the path node C is taken, if so, entering a step S107, and if not, storing the current search node into a searched list close_list; S107, checking whether the searched list close_list exists, if so, entering a step S108, and if not, returning to the step S106; s108, continuously judging whether a weight priority list open_list exists, if so, loosening the repeated node, returning to the step S106, and if not, entering the step S109; S109, the path from the starting point to the subsequent space node N is R1, and the path is tried to be added into a directed communication graph G; s110, judging whether a strong communication component exists, if so, adding the vehicles associated with the strong communication component into a driving tree, and if not, entering a step S111; S111, judging whether a driving vehicle without a path exists, if yes, entering a step S112, if not, forming a new search node by a new subsequent space node N, a directed communication graph G and a driving tree, calculating weights by the shortest path of the subsequent space node N, adding a weight priority list open_list, and returning to the step S106; s112, adding the non-path vehicle into the driving tree; S113, judging whether the driving tree has ring conflict, if so, returning to the step S106, and if not, entering into the step S114; S114, the driven vehicles recursively use the path planning method to avoid; S115, judging whether the avoidance is successful, if so, entering a step S116, and if not, returning to the step S106; S116, calculating avoidance cost, packing a new path directed communication graph G and a driving tree into a new search node, calculating weight by using the shortest path of a subsequent space node N and the avoidance cost, and adding a weight priority list open_list.
2. 2. The collision-based multi-vehicle path planning optimization method of claim 1, wherein the relaxing search expectations further comprises: And (3) searching from the end point to the start point by using a Dijkstra algorithm, recording the distance from each node to the end point and the relation between the nodes and the father node, and directly inquiring the shortest path from any node to the end point during subsequent searching.
3. 3. The method according to claim 1, wherein in step S6, if the current path of the vehicle is different from the expected shortest path, the following steps are performed: s601, dividing a feasible path set into fixed time_step on a time dimension, so as to form a discretized space-time three-dimensional diagram; S602, judging whether a path needing to be optimized exists, if yes, entering a step S603, and if no, ending; s603, selecting any vehicle needing to be optimized; S604, planning paths on a space-time three-dimensional map on the premise of not changing space-time paths of other vehicles; s605, judging whether a better path exists, if so, updating the path, and if not, returning to the step S602.

Description

Multi-vehicle path planning optimization method based on conflict Technical Field The invention relates to automatic warehouse and logistics park technologies, in particular to a multi-vehicle path planning optimization method based on conflict. Background The automatic warehouse and logistics park refer to application scenes in which automatic conveying equipment such as Automatic Guided Vehicles (AGVs), automatic forklifts and other automatic equipment are adopted to carry in a fixed space. In order to ensure the safety and high efficiency of multi-vehicle operation in the same space, planning paths of vehicles in time and space in advance is an important problem to be solved. As shown in fig. 1, a typical multi-vehicle warehouse scenario is shown, in which the gray area in fig. 1 is an unviewable area, the white area is a passable area, the circle represents a vehicle starting position, the five-pointed star represents a target position, the number represents a vehicle number, and the line between circles and the five-pointed star represents a planned vehicle driving path. At least one lattice is required to be exclusive when a vehicle runs through a white lattice on a route, so that a space-time conflict is defined when two or more vehicles need to occupy the same lattice at the same time. At this point, the problem translates into how to plan a reasonable path for each vehicle so that all vehicles have no space-time conflicts and can take the least time. The optimal path planning problem of multiple vehicles is the NP problem in theory, and the optimal solution does not exist. What is sought in the industry is how to find near optimal solutions under industry constraints. The current mainstream practice is as follows: 1) A single vehicle path planning algorithm with a time window (representing Dijkstra, a and related variations thereof) is used for each vehicle to plan a space-time shortest path. The method is relatively simple and high in speed, the conflict problem with other vehicles is solved by using a time window, but the consideration factor is relatively coarse, the possible complex problem among multiple vehicles is usually solved by adopting greedy algorithm ideas such as priority setting, planning sequence and the like, and the comprehensive efficiency is not high, so that some redundant operations around a way are often performed for a small avoidance; 2) In recent years, a method for planning multiple paths together, namely, when vehicles plan paths, simultaneously considering possible changes of other vehicle paths, and searching for a better combination in the process of multiple-vehicle game. A typical example of such a method is a collision-based path planning method (CBS), which is based on the idea of paying attention to collisions between vehicles (two or more vehicles pass through the same area at the same time), and sequentially processing the collisions in time series. When each conflict is processed, each party trying to avoid the conflict in time and space by adopting path planning based on a time window, each avoiding generates a new situation, and each situation is scored according to the number of conflicts required to be processed subsequently, so that the number of conflicts is reduced through iteration, the conflicts are converged in the future direction, and finally, a path completely free of conflicts is found. The method can find a better comprehensive approximate optimal path, but has two defects that the searching efficiency is low due to too many similar situations (typical cases are as shown in fig. 2, the situations of the same type are too many), and the conflict resolution cost cannot be distinguished, namely, the embarrassing situation that the cost for resolving the residual conflict is too great due to the previous decision, although the number of the conflicts is reduced, is caused (as shown in fig. 3, the first vehicle 1 can solve the conflicts a and b with the minimum cost, but the problem is caused to solve the problem that c is extremely great). Although some improved methods based on a priori knowledge have been proposed, they are limited to either a certain application scenario or limited in effectiveness. Disclosure of Invention Aiming at the defects in the prior art, the invention aims to provide a multi-vehicle path planning optimization method based on conflict, which can effectively avoid two problems in the prior art and has the characteristics of wide adaptability and high retrieval efficiency. In order to achieve the above purpose, the invention adopts the following technical scheme: a multi-vehicle path planning optimization method based on conflict comprises the following steps: Before the vehicle moves, the search expectations are relaxed, a feasible path set is generated, continuous optimization is carried out on the feasible path set, and the feasible path set is continuously optimized to a vehicle operation stage. Preferably, the relaxed