CN114659533A - Path planning method for multi-task conflict detection and resolution in emergency rescue scenarios - Google Patents

Abstract

The invention discloses a path planning method for multi-task conflict detection and resolution in an emergency rescue scenario. The invention improves the Dijkstra algorithm, comprehensively considers multiple factors such as road occupancy, intersection occupancy, fleet priority, etc., solves the problem of conflict resolution when the Dijkstra algorithm is used for navigation planning in multi-echelon cooperative transportation, and can be applied to emergency rescue and coordinated transportation. Scenes.

Description

Path planning method for multi-task conflict detection and resolution in emergency rescue scenarios

technical field

The invention relates to the technical field of path planning, in particular to a path planning method for multi-task conflict detection and resolution in an emergency rescue scenario.

Background technique

The information construction of emergency rescue forces has always been an important part of the construction of the national network information system. In recent years, extreme severe weather and natural disasters have occurred frequently, and the tasks undertaken by the national rescue forces have become increasingly arduous. Some rescue operations have a long time span, a wide range of operations, and many rescue elements involved, which put forward new requirements for the rapid response capability of rescue forces. Through comprehensive research and analysis of road section resource occupancy, time cost, and congestion elements of travel routes, flexible priority rules are formulated, conflict detection and resolution for multi-task routes are realized, and multi-task emergency rescue plans are generated, which can improve the scientific nature of the task planning process of rescue forces. It can provide effective support for the rapid deployment of emergency rescue operations.

Most of the existing literatures on conflict detection and resolution algorithms start with the construction of complex STN networks, and consider the influence information of multiple dimensions such as time, space, and resources to deal with complex traffic scenarios, such as "Research and Implementation of Conflict Detection and Resolution Algorithms", "STN-based planning execution process time conflict detection and resolution", which also includes "unsignaled intersection conflict detection and resolution algorithm research" combined with GPS positioning technology, such methods are not only difficult to construct, but also due to the addition of satellite heights The performance sensor device greatly increases the input cost. Based on the above shortcomings, this paper starts from the route navigation level, analyzes the task requirements of the journey, and borrows the process of the traditional graph theory algorithm Dijkstra to improve, and then solve the problem of conflict resolution. Some existing improvements to Dijkstra's algorithm, such as "A Port Logistics Scheduling Method Based on Dijkstra's Algorithm", are complex system construction for port logistics scheduling tasks, and combined with Dijkstra to solve the routing problem on scheduling, but not The conflict situation of multi-task coordination during travel is not considered, and "Research on the planning of container port truck dispatching yard based on Dijkstra algorithm" is also similar to the above situation. Other conflict scenarios such as "Parking AGV path planning based on improved Dijkstra algorithm" will be stored The vehicle weight value is set as the distance, and the vehicle weight value is set as the time to introduce the time window, and the parking path problem is solved in stages. However, because the parking task does not have the priority nature of the emergency rescue task, this method cannot handle many tasks in an emergency scenario. The tasks are complex and coordinated, and the rescue convoy is not suitable for emergency rescue mission scenarios because it has a longer driving length than ordinary vehicles, occupies a high degree of intersection, and has more complex rules for entering intersection nodes. In addition, there are improvements and optimizations for the storage structure and efficiency of the Dijkstra algorithm itself.

SUMMARY OF THE INVENTION

In view of this, the present invention provides a path planning method for multi-task conflict detection and resolution in an emergency rescue scenario, which solves the problem of conflict resolution when using Dijkstra algorithm for navigation planning in multi-echelon cooperative transportation.

The path planning method for multi-task conflict detection and resolution in an emergency rescue scenario of the present invention includes:

Step 1: Taking the steerable intersections in the area as nodes and roads as edges, construct a directed weighted graph G(V, E) of the road network in the area, where V is the set of nodes in the road network, and E is the The set of directed edges in the road network; the weight of edge E includes dynamic weight E.length, E.value and static weight E.val; where E.val is the time for the current fleet to be planned to pass edge E under ideal conditions ;

Step 2, considering the conflict between the fleet to be planned and the planned fleet, update the G(V,E) data:

S21, extract the unmarked node Vmin with the smallest value in the set V, and obtain its adjacent points according to G(V, E), and the adjacent points are not marked; wherein the value is the current fleet to be planned to reach this point The time of the node; the value of the starting node of the path is initialized to 0; the value of other nodes is initialized to infinity; if the nodes in the set V have been marked, go to step 3;

S22, select the untraversed point Vtt in the adjacent nodes of Vmin, and update the weight Ett.length of the edge Ett between the nodes Vmin and Vtt:

1) Determine whether the edge Ett between the node Vmin and the node Vtt is occupied by other planned fleets, if not, set Ett.value=Ett.val, Ett.length=Ett.value+fleet.length/velocity ; Execute 2); wherein, fleet.length is the length of the fleet to be planned; velocity is the average speed of the fleet to be planned;

Otherwise, let Ett.value=Vmin.end-Vmin.value+Ett.val, Ett.length=Vmin.end-Vmin.value+Ett.value+fleet.length/velocity; execute 2);

2) Judge whether the convoy to be planned conflicts with the planned convoy when it reaches the node Vtt; if it does not conflict, set Ett.length=Ett.value, and execute S23; if there is a conflict, go to 3); the conflict is It means that the time period of the two teams passing through the node Vtt overlaps;

3) Determine whether the to-be-planned fleet arrives at the node Vtt first: if the to-be-planned fleet arrives first, and the priority of the to-be-planned fleet is greater than or equal to the planned fleet, set Ett.length=Ett.value, execute S23, and notify the The conflict has been planned to re-plan the fleet; if the to-be-planned fleet arrives first, but the priority of the to-be-planned fleet is lower than that of the planned fleet, execute 4);

If it arrives after the planned fleet, but the priority of the planned fleet is greater than the planned fleet, set Ett.length=Ett.value, execute S23, and notify the planned fleet to re-plan; if it arrives after the planned fleet, and wait for If the priority of the planned fleet is not greater than the planned fleet, then judge whether the next node of the planned fleet is Vmin, if so, set Ett.length=Vmin.end-Vmin.value+Ett.val, and execute S23; otherwise, set Ett.length=end-Vmin.value, execute S23;

4) Determine whether the next node of the planned fleet is Vmin, if not, set Ett.length=end-Vmin.value, and execute S23; if so, set Ett.length=Vmin.end-Vmin.value+Ett .val, execute S23;

S23, calculate Vtt.value'=Vmin.value+Ett.length; if Vtt.value' is less than the value of the node Vtt, update Vtt.value=Vtt.value', and record Vmin into the backtracking vector res;

S24, judge whether the adjacent points of Vmin have all been traversed, if not all traversed, then return to S22; if all have been traversed, then mark the current node Vmin, and return to S21;

Step 3: Backtrack the res vector from the end point of the path forward to obtain the shortest path.

Preferably, in the described S22, the mode of judging whether the edge Ett of the node Vmin and the node Vtt is occupied by other planned teams is:

Set the state in the parameters of edge Ett to store the occupied time of the planned fleet on edge Ett, that is [Vmin.start,Vtt.end] or [Vtt.start,Vmin.end]; The start time of the planned convoy passing through the node Vmin, Vtt.end is the end time of the convoy leaving the node Vtt; Vtt.start is the start time of the planned convoy passing the node Vtt, and Vmin.end is the time when the convoy left the node Vmin. End Time;

Then, if the Vmin.value of the fleet to be planned is within the time period stored in the state, it means that the table Ett has been occupied, otherwise, it means that it is not occupied.

Preferably, in the described S22, when it is judged that the fleet to be planned arrives at the node Vtt, whether it is in conflict with the planned fleet is:

If the fleet to be planned satisfies: Vmin.value+Ett.value>Vtt.end or Vmin.value+Ett.length<Vtt.start, there is no conflict, otherwise it is a conflict; among them, Vtt.end is the planned fleet passing through the node The start time of Vtt, Vtt.start is the start time of the planned fleet passing through the node Vtt.

Preferably, in the S22, the method of judging whether the fleet to be planned reaches the node Vtt first is: if the fleet to be planned satisfies: Vmin.value+Ett.value<Vtt.start and Vtt.start<Vmin.value+Ett .length, it means that the planned echelon arrives at Vtt first; among them, Vtt.start means the start time of the planned fleet passing through this node; otherwise, the planned fleet arrives at the node Vtt.

Preferably, in the step 2, a set U and a set S are constructed, the set U is initialized as a set V, and the set S is an empty set; Vmin is selected from the set U and moved into the set S; Vmin and its adjacent points are merged into the temporary set. In the set Vtemp, merge the edges of the fleet to be planned from Vmin to each node in the set Vtemp into the temporary set Etemp;

Select the node Vtt from the temporary set Vtemp, calculate the weight Ett.length of the edge Ett between the node Vmin and Vtt, and update the value of the node Vtt in Vtemp to the value: Vtt.value=Vmin.value+Ett.length;

Traverse all the nodes in the set Vtemp; if the value of the node in the set Vtemp is less than the value of the same node in the set U, then update the value of the node in the set U to the value in the set Vtemp;

Empty the collection Vtemp, Etemp;

Reselect Vmin from the set U and move it into the set S, and repeat the above operations until the set U is an empty set, and perform step 3.

Preferably, the Vtt.length is revised according to road traffic conditions, road surface material and gradient.

Beneficial effects:

1) The present invention takes into account the fact that in the actual logistics and transportation scenario, the implementation of multiple fleets in the moving scheme will often cause congestion problems, and improves the Dijkstra algorithm, comprehensively considering road occupation, intersection occupation, fleet priority and other factors, It solves the problem of conflict resolution when using Dijkstra algorithm for navigation planning in multi-echelon collaborative transportation, and can be applied to emergency rescue coordinated transportation scenarios.

2) The present invention solves the path planning problem from the perspective of theoretical conflict with the historical task path and makes an early response or response, so it is not necessary to introduce expensive GIS, GPS technology, etc. in the preliminary planning stage, and the cost is greatly reduced. And it can be updated and adjusted for the priority of historical tasks, which is more flexible.

3) This scheme has certain scalability, which is convenient for subsequent improvement. For example, when the convoy passes through roads with different traffic conditions, different pavement materials, and different slopes, the time and cost spent are not the same. In this scheme, the weight change can be considered in advance by introducing road data with these influencing factors. And it can also be adjusted according to the needs of some special models. This greatly improves the flexibility and expandability of the program.

Description of drawings

Fig. 1 is a flow chart of the present invention.

FIG. 2 is a flow chart of updating Ett.length and Vtt.value of the present invention.

Figure 3 is a directed road graph, in which letters represent intersection nodes, the line segment between the letters represents the road segment between two intersections, and the number above it represents the time passing through this road segment.

As shown in Fig. 3(a), the original shortest path from A to F is A->B->C->F, and the time is 27, which is less than 30 for the other one. But if there are other teams occupying C port time 10 at this time, then the cost from C to F will change from 10 to 20 (as shown in Figure 3(b)). However, the traditional algorithm does not do this cost calculation considering the influence of other teams, so the shortest path is still calculated as A->B->C->F.

After calculation by the method of the present invention, the shortest path finally obtained is A->D->E->F, and the time is 30, which is less than the other 37.

Detailed ways

The present invention will be described in detail below with reference to the accompanying drawings and embodiments.

The invention provides a path planning method for multi-task conflict detection and resolution in an emergency rescue scene. Based on the theoretical basis of the traditional Dijkstra algorithm, the graph theory principle is borrowed, and the time of nodes and edges is increased on the basis of the original weighted graph. Attribute, when modeling, the road segment can be regarded as an edge, and the intersection can be regarded as a node, and in the process of graph search, the focus is placed on the time attribute of each node and edge, considering the time and priority, This enables the transport fleet to achieve the function of avoiding congestion with the existing fleet of transport tasks when using the algorithm for path planning.

Compared with the navigation implementation based on the Dijkstra algorithm, this scheme no longer ignores the current calculated fleet length and the existing historical fleet length and travel route, and regards the process of passing a node or an edge in the directed graph as a The time window of the attribute, once it conflicts with the planned path, the priority will be judged, and the resources of the intersection and road section will be allocated to the task fleet with a higher task level first. If the priority of the current task is higher, the actual search will be performed. The weight is not modified. If the priority is lower or the same level when it conflicts with other tasks at this point, the weight of the current search will be changed accordingly according to the time attribute, so that the team task will take into account during the operation of the algorithm. To meet the task requirements of congestion avoidance, a convoy route is finally planned that takes into account the cost of congestion time.

The flow chart of the method of the present invention is shown in Figure 1, which specifically includes:

1) Construct the road model of a certain area: take the steerable intersections in the area as nodes and the roads as the edges to construct the road network G(V, E) in the area; where V is the set of nodes in the road network , E is the set of directed edges in the road network, and G(V, E) is a directed weighted graph;

Wherein, the structural design of the edge and node in this embodiment is as follows:

The edge E structure is:

edge id value Snode Enode state* length val

edge is the name of the edge; id is the index of the edge; value is the road weight considering the influence of edge occupancy; Snode and Enode are the start and end points of the edge respectively; state* represents whether the current road segment is occupied by other teams, in the form of a linked list, If it is occupied, read the occupied time; length is the dynamic weight of this edge, that is, the weight of the fleet passing by is considered; val is the static weight of this edge, which is the ideal time for the current fleet to be planned to pass this edge.

The structure of node V is:

node id start* end* next* value

node is the name of the node; id is the index of the node, start* represents the start time of other teams passing through this node, in the form of a linked list; end* represents the end time of the other teams leaving this node, in the form of a linked list; next* It represents the next node of other teams, in the form of a linked list; value represents the start time of the current team to be planned to reach this node, and the initial value is infinity.

2) Initialization, the process is as follows:

2.1) Initialize the current time t0: set the initial path time t in the model to 0;

2.2) Initialize the backtracking vector res to save the shortest path result;

2.3) Initialize the node set S, which represents the set of nodes that have found the shortest path at the current moment, let S=ф;

2.4) Initialize the node set U, which represents the set of nodes with the shortest path not calculated at the current moment; let U=V.

3) If U=ф, go to step 14); otherwise, go to step 4);

4) Select the node Vmin with the smallest value in the set U, and move it into the set S; wherein, the value of the starting point V0 of the path planning is 0, and the value of other nodes is infinite;

5) According to the road network G(V, E), search the adjacent points of the node Vmin in the set U, and merge the node Vmin and its adjacent points into the temporary set Vtemp;

6) According to the road network G(V, E), construct a temporary set Etemp, and store the edges of the fleet to be planned from Vmin to each node in the set Vtemp;

7) arbitrarily select an untraversed element Vtt from the set Vtemp;

8) Determine the state of the element Vtt:

8.1) Read the start attribute Vtt.start and end attribute Vtt.end on it;

8.2) Read the directed edge Ett.val of Vmin-Vtt in the Etemp set;

8.3) Ett.val is the ideal passing time regardless of echelon length and edge occupation;

Ett.value is the time it takes for the head of the team to reach Vtt after the entire echelon is required to wait for the road section to be occupied;

Ett.length is the time it takes for the tail of the team to leave Vtt after the entire echelon is required to wait for the road section to be occupied;

When assigning values to the latter two, first make a logical judgment, which is divided into two cases:

If the road segment is not occupied by other echelons:

Then Ett.value=Ett.val,

Ett.length=Ett.value+fleet.length/velocity;

Among them, fleet.length is the length of the fleet; velocity is the average speed of the fleet; execute 8.4);

Otherwise: Ett.value=Vmin.end-Vmin.value+Ett.val,

Ett.length=Vmin.end-Vmin.value+Ett.value+fleet.length/velocity;

implement 8.4);

Among them, you can judge whether the road section is occupied according to the "state" of the road section: the state stores the time period when other planned fleets are occupied between the two intersections Vmin and Vtt. For example, fleet a will reach Vmin first, and then After Vtt, the occupied time period stored in the state is [Vmin.start,Vtt.end];

Another situation is that the team a will reach Vtt first, and then pass through Vmin, then the time period stored in the state is [Vtt.start, Vmin.end];

As long as Vmin.value is within this interval, it is considered that the road segment Ett is occupied when the planned fleet reaches Vmin.

That is, if the time Vmin.value when the planned fleet reaches Vmin satisfies: the starting point of the state storage period < Vmin.value < the end point of the state storage period, it means that Ett is occupied.

The reason why the storage method is adopted is because: if the algorithm is running, it will waste a lot of time to determine whether Vtt first or Vmin first, so it is better to access this information at the beginning of storage, so that although the storage space is reduced. increase, but the algorithm program will no longer make the logical judgment of who comes first here, which will greatly improve the performance.

8.4) Determine whether the convoy to be planned conflicts with other planned convoys at the node Vtt, and the conflict is that the two convoys pass through the node Vtt at the same time:

If Vmin.value+Ett.value>Vtt.end or Vmin.value+Ett.length<Vtt.start, it means that the to-be-planned fleet will arrive earlier or later than other planned fleets, and there will be no conflict with them, so that Ett. length=Ett.value, go to step 10); otherwise, a conflict occurs, go to step 9);

9) According to the actual conflict time, update the Etemp state:

9.1) If Vmin.value+Ett.value<Vtt.start and Vtt.start<Vmin.value+Ett.length, it means that the planned echelon will reach Vtt first, and there will be a conflict with the warehoused echelon a at this point. When the priority of the two tasks can be judged, if the priority of the task of the echelon to be planned is higher than or equal to a, the echelon to be planned can take the lead in occupying the Vtt point, read the coordinates of a, re-plan the route for a, and make Ett. length=Ett.value, go to step 10); if the priority of the current task is less than the priority of a, then when calculating Vtt, a will take priority over it, the current task should plan the waiting time, and determine that a reaches Vtt after the next node, if the next node of echelon a on Vtt is not Vmin, go to 9.2); otherwise, next node = Vmin, which means that echelon a is given priority to pass this intersection, and a will also have a task conflict with the planning echelon, Ett .length=Vmin.end-Vmin.value+Ett.val, go to step 10).

If start<Vmin.value+Ett.value<Vtt.end, it means that the planned echelon will arrive at Vtt after the planned echelon meeting, and the echelon a will arrive first. It is assumed that the task priority of the planned echelon is not higher than that of the a echelon, and the echelon a is on the Vtt The next node is not Vmin, and still go to 9.2 without changing the route of echelon a). If the next node = Vmin, it means that echelon a will also conflict with the current task after passing through the intersection, so The waiting time will be lengthened, Ett.length=Vmin.end-Vmin.value+Ett.val, go to step 10);

If the task priority of the echelon to be planned is higher than the echelon a, the current echelon is given priority to occupy the Vtt point, and the route is re-planned for a, Ett.length=Ett.value, enter step 10);

9.2) Update Ett.length=end-Vmin.value, enter step 10);

10) Update the state of Vtt in Vtemp: Vtt.value=Vmin.value+Ett.length;

11) judge whether Vtemp is fully traversed, if not, return to step 7), if all traversal is completed then jump to step 12);

12) Update set U according to set Vtemp: If the value of a node t in set U is greater than the value of node t in Vtemp at this time, update t.value in U to the value of node t in Vtemp, which also means that The shortest distance precursor node to t is Vmin, Vmin is recorded in the backtracking vector res, the set Vtemp and Etemp are cleared, and step 13) is performed; otherwise, the node t in U is not updated, and step 13) is performed;

13) Go back to step 3).

14) Backtrack the res vector from the end point forward to get the shortest path. For example, to reach the end point F in Figure 3, read from the res vector that the precursor of F is point E, the precursor of point E is point D, and the precursor of point D is point A, then the final shortest path is A->D ->E->F.

To sum up, the above are only preferred embodiments of the present invention, and are not intended to limit the protection scope of the present invention. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention shall be included within the protection scope of the present invention.

Claims (6)

1. a path planning method for multi-task conflict detection and resolution under an emergency rescue scenario, characterized in that, comprising: Step 1: Taking the steerable intersections in the area as nodes and roads as edges, construct a directed weighted graph G(V, E) of the road network in the area, where V is the set of nodes in the road network, and E is the The set of directed edges in the road network; the weight of edge E includes dynamic weight E.length, E.value and static weight E.val; where E.val is the time for the current fleet to be planned to pass edge E under ideal conditions ; Step 2, considering the conflict between the fleet to be planned and the planned fleet, update the G(V,E) data: S21, extract the unmarked node Vmin with the smallest value in the set V, and obtain its adjacent points according to G(V, E), and the adjacent points are not marked; where the value is the current fleet to be planned to reach this point The time of the node; the value of the starting node of the path is initialized to 0; the value of other nodes is initialized to infinity; if the nodes in the set V have been marked, go to step 3; S22, select the untraversed point Vtt in the adjacent nodes of Vmin, and update the weight Ett.length of the edge Ett between the nodes Vmin and Vtt: 1) Determine whether the edge Ett between the node Vmin and the node Vtt is occupied by other planned fleets, if not, set Ett.value=Ett.val, Ett.length=Ett.value+fleet.length/velocity ; Execute 2); wherein, fleet.length is the length of the fleet to be planned; velocity is the average speed of the fleet to be planned; Otherwise, let Ett.value=Vmin.end-Vmin.value+Ett.val, Ett.length=Vmin.end-Vmin.value+Ett.value+fleet.length/velocity; execute 2); 2) Judging whether the convoy to be planned conflicts with the planned convoy when it reaches the node Vtt; if there is no conflict, set Ett.length=Ett.value, and execute S23; if there is a conflict, go to 3); the conflict is It means that the time period of the two teams passing through the node Vtt overlaps; 3) Determine whether the to-be-planned fleet arrives at the node Vtt first: if the to-be-planned fleet arrives first, and the priority of the to-be-planned fleet is greater than or equal to the planned fleet, set Ett.length=Ett.value, execute S23, and notify the The conflict has been planned to re-plan the fleet; if the to-be-planned fleet arrives first, but the priority of the to-be-planned fleet is lower than that of the planned fleet, execute 4); If it arrives after the planned fleet, but the priority of the planned fleet is greater than the planned fleet, set Ett.length=Ett.value, execute S23, and notify the planned fleet to re-plan; if it arrives after the planned fleet, and wait for If the priority of the planned fleet is not greater than the planned fleet, then judge whether the next node of the planned fleet is Vmin, if so, set Ett.length=Vmin.end-Vmin.value+Ett.val, and execute S23; otherwise, set Ett.length=end-Vmin.value, execute S23; 4) Determine whether the next node of the planned fleet is Vmin, if not, set Ett.length=end-Vmin.value, and execute S23; if so, set Ett.length=Vmin.end-Vmin.value+Ett .val, execute S23; S23, calculate Vtt.value'=Vmin.value+Ett.length; if Vtt.value' is less than the value of the node Vtt, then update Vtt.value=Vtt.value', and record Vmin in the backtracking vector res; S24, judge whether the adjacent points of Vmin have all been traversed, and if not all of them have been traversed, then return to S22; if all have been traversed, mark the current node Vmin, and return to S21; Step 3: Backtrack the res vector from the end point of the path forward to obtain the shortest path. 2. The path planning method for multi-task conflict detection and resolution under the emergency rescue scene as claimed in claim 1, wherein in the described S22, it is judged whether the edge Ett of the node Vmin and the node Vtt is by other planned motorcades. The way it is occupied is: Set the state in the parameters of edge Ett to store the occupied time of the planned fleet on edge Ett, that is [Vmin.start,Vtt.end] or [Vtt.start,Vmin.end]; The start time of the planned convoy passing through the node Vmin, Vtt.end is the end time of the convoy leaving the node Vtt; Vtt.start is the start time of the planned convoy passing the node Vtt, and Vmin.end is the time when the convoy left the node Vmin. End Time; Then, if the Vmin.value of the fleet to be planned is within the time period stored in the state, it means that the table Ett has been occupied; otherwise, it is not occupied. 3. The path planning method for multi-task conflict detection and resolution under the emergency rescue scene as claimed in claim 1, characterized in that, in the S22, when it is judged that the convoy to be planned arrives at the node Vtt, whether it is in conflict with the planned convoy The way is: If the fleet to be planned satisfies: Vmin.value+Ett.value>Vtt.end or Vmin.value+Ett.length<Vtt.start, there is no conflict, otherwise it is a conflict; among them, Vtt.end is the planned fleet passing through the node The start time of Vtt, Vtt.start is the start time of the planned fleet passing through the node Vtt. 4. the path planning method of multi-task conflict detection and resolution under the emergency rescue scene as claimed in claim 1, it is characterized in that, in S22, the mode that judges whether the convoy to be planned arrives at node Vtt first is: if the convoy to be planned meets the : Vmin.value+Ett.value<Vtt.start and Vtt.start<Vmin.value+Ett.length, it means that the planned echelon reaches Vtt first; among them, Vtt.start means that the planned fleet passes through this node Start time; otherwise, it will arrive at node Vtt after planning the fleet. 5. The path planning method for multi-task conflict detection and resolution in an emergency rescue scenario as claimed in claim 1, wherein in the step 2, a set U and a set S are constructed, and the initialization set U is a set V, and a set S is an empty set; select Vmin from set U and move it into set S; merge Vmin and its adjacent points into the temporary set Vtemp, and merge the edges of the fleet to be planned from Vmin to each node in the set Vtemp into the temporary set Etemp; Select the node Vtt from the temporary set Vtemp, calculate the weight Ett.length of the edge Ett between the node Vmin and Vtt, and update the value of the node Vtt in Vtemp to the value: Vtt.value=Vmin.value+Ett.length; Traverse all the nodes in the set Vtemp; if the value of the node in the set Vtemp is less than the value of the same node in the set U, then update the value of the node in the set U to the value in the set Vtemp; Empty the collection Vtemp, Etemp; Reselect Vmin from the set U and move it into the set S, and repeat the above operations until the set U is an empty set, and then go to step 3. 6 . The path planning method for multi-task conflict detection and resolution in an emergency rescue scenario according to claim 1 , wherein the Vtt.length is revised according to road traffic conditions, road surface material and gradient. 7 .

Images