CN115083139A - Multi-vehicle scheduling method - Google Patents

Abstract

A multi-vehicle scheduling method includes the steps of constructing a layout map of vehicles and a closed space according to parameter information of current vehicles and layout information of parking environments, designing priority rules, calculating priorities of the vehicles according to the rules, and selecting the vehicles needing to be taken out of a warehouse. Planning a collision-free path which accords with kinematic constraint of each vehicle by adopting a punitive mixed A-algorithm; and according to the vehicle priority, sequentially adopting an s-t diagram strategy to obtain the conflict-free tracks of the multiple vehicles in space-time, and finishing the dispatching of the multiple vehicles for going out of the garage. The invention plans the path of the vehicle, and configures the speed by using the S-T chart strategy, thereby avoiding other vehicles, completing the integral dispatching of a plurality of vehicles and realizing the high-efficiency delivery without collision.

Description

Multi-vehicle scheduling method

technical field

The invention relates to a technology in the field of multi-vehicle control, in particular to a multi-vehicle scheduling method based on a penalized hybrid A ^* algorithm and an ST graph strategy.

Background technique

The existing multi-vehicle scheduling problems can be divided into two aspects: single-vehicle routing and multi-vehicle scheduling. The path planning problem can be described as: under the premise that the environment is known or partially known, given the starting point and the target end point, find a collision-free shortest path from the starting point to the end point. Multi-vehicle scheduling is designed to solve the situation that multiple vehicles move and interfere with each other when they leave the warehouse at the same time, ensure that all vehicles leave the warehouse in an orderly and rapid manner, reduce the total time of leaving the warehouse, and improve efficiency. In the current scheduling method, the path planning often does not meet the kinematic characteristics of the vehicle, or there is a phenomenon that the path is not smooth and reasonable enough, and the scheduling of multiple vehicles is not fast enough.

SUMMARY OF THE INVENTION

Aiming at the above-mentioned shortcomings of the prior art, the present invention proposes a multi-vehicle scheduling method. By planning the path of the vehicle, and then using the S-T graph strategy to configure the speed, avoid other vehicles, complete the overall scheduling of multiple vehicles, and achieve no Collision and efficient delivery.

The present invention is achieved through the following technical solutions:

The invention relates to a multi-vehicle scheduling method based on a penalized hybrid A ^* algorithm and an ST map strategy. According to the parameter information of the current vehicle and the layout information of the parking environment, the layout map of the vehicle and the confined space is constructed, and the priority rules are designed according to The rules calculate the priority of each vehicle and select the vehicle that needs to be out of the warehouse. The penalized hybrid A ^* algorithm is used to plan a collision-free path for each vehicle that conforms to the kinematic constraints; according to the vehicle priority, the st graph strategy is used in turn to obtain a multi-vehicle trajectories without conflicts in space and time. Library scheduling.

The present invention relates to a system for implementing the above method, comprising: a priority calculation unit, a path planning unit and a speed planning unit, wherein: the priority calculation unit is connected with the path planning unit and transmits vehicle priority information and information of vehicles that need to leave the warehouse , the path planning unit is connected with the speed planning unit and transmits the path information of the vehicle.

technical effect

The invention as a whole solves the defects of the prior art that the planned running path of the vehicle is not smooth enough and the speed is switched too frequently during the running process. Compared with the prior art, the present invention uses the improved A ^* algorithm and ST map to plan the speed of the vehicle, ensuring that the vehicle can reduce the switching of the driving state without affecting the overall time, and is more suitable for the actual situation, without causing Physically unrealizable speed planning improves the overall multi-vehicle outbound speed.

Description of drawings

Fig. 1 is the schematic flow chart of the present invention;

Fig. 2 is the layout map of the multi-vehicle of the embodiment;

Fig. 3 is the schematic diagram of the S-T diagram of the embodiment;

4 is a schematic diagram of a single vehicle path planning according to an embodiment;

FIG. 5 is a schematic diagram of a speed configuration using an S-T diagram according to an embodiment.

Detailed ways

As shown in FIG. 1 , the present embodiment relates to a multi-vehicle scheduling method based on a penalized hybrid A ^* algorithm and an ST graph strategy, which specifically includes:

Step S1: Collect the parameter information of the current vehicle and the layout information of the parking environment, and construct a layout map of the vehicle and the confined space.

As shown in Figure 2, the map of this embodiment has a length and width of 54m and 24m respectively. There are 6 vehicles parked in the map space. The vehicles are represented by rectangles, and other obstacles are represented by the smallest polygon that can contain obstacles. To represent: use a rectangle with a length of 10m and a width of 3.5m to represent the vehicle, number the vehicles from top to bottom and from left to right as A, B, C, D, E, F, and the confined space has only one single exit .

Step S2: Design a corresponding priority rule according to the task requirements, the parking position of the vehicle, and the performance of the vehicle, calculate the priority of each vehicle according to the rule, and select the vehicle that needs to be out of the warehouse.

In this embodiment, the task requirement refers to: four vehicles are out of the warehouse.

The parking positions of the vehicles refer to: the vehicles are arranged in parallel with the front of the vehicles outward, as shown in FIG. 2 , the distances of the vehicles relative to a single exit are different.

The performance of the vehicle includes: vehicle maintenance, equipment assembly, and mileage.

The principle of the design is to meet the requirements of the task and the number of vehicles with good state and performance will leave the garage as soon as possible, that is, the overall vehicle exit time is the smallest, and the obtained priority rule is: E _i =b ₁ P _i +b ₂ C _i , where: E _i is the final comprehensive index of each vehicle, C _i is the performance index of the vehicle, obtained according to the comprehensive evaluation of the performance of the vehicle, and the position index of the vehicle is based on P _i =(|x _i (t _fi )-x _i (0)|+|y _i (t _fi )-y _i (0)|)/2 is obtained, where: |x _i (t _fi )-x _i (0)|, |y _i (t _fi )- y _i (0)| is the distance between the midpoint of the rear wheel axle of each vehicle relative to the midpoint of the exit, and b ₁ and b ₂ are weight coefficients, representing the trade-off between vehicle performance and vehicle position.

In this embodiment, the starting and ending positions and performance indices of the six vehicles are shown in Table 1:

Table 1 Vehicle parameter table

The weight coefficients are set as b ₁ =0.4, b ₂ =0.6, the comprehensive index of each vehicle in the vehicle is obtained, and the four vehicles A, E, C and F with the highest comprehensive index are selected to leave the warehouse, and their priority is designated. level, as shown in Table 2:

Table 2 Vehicle comprehensive index and priority

Step S3: Using the penalized hybrid A ^* algorithm, plan a collision-free path for each vehicle that meets the kinematic constraints, that is, meets the requirements of the position and attitude angle of the end point.

|a_i(t)|≤a_maxi，|ν_i(t)|≤ν_maxi，|ω_i(t)|≤ω_maxi，其中：(x_i(t),y_i(t))为t时刻车辆的后轮轴中点坐标，θ_i(t)为车辆在XOY坐标系中的姿态角，ν_i(t)和a_i(t)分别为车辆的沿身体纵轴的速度以及加速度，

为车辆前轮偏转角，以逆时针为正方向，对应地，ω_i(t)为前轮偏转角速度，L为前后轮轴距。The kinematic constraints described include:

|a _i (t)|≤a _maxi , |ν _i (t)|≤ν _maxi , |ω _i (t)|≤ω _maxi , where: (x _i (t),y _i (t)) is t The coordinates of the midpoint of the rear wheel axle of the vehicle at the moment, θ _i (t) is the attitude angle of the vehicle in the XOY coordinate system, ν _i (t) and a _i (t) are the speed and acceleration of the vehicle along the longitudinal axis of the body, respectively,

is the deflection angle of the front wheel of the vehicle, with counterclockwise as the positive direction, correspondingly, ω _i (t) is the deflection angular velocity of the front wheel, and L is the wheelbase of the front and rear wheels.

Said meeting the requirements of the position and attitude angle of the end point means: satisfying ( _xi (t _fi ), _yi (t _fi ), θ _i (t _fi ))=(x ^* , y ^* , θ ^* ).

The penalized hybrid A ^* algorithm specifically includes:

Step S3-1: The map constructed in step S1 is discretized, and the initial pose of the vehicle to be planned at this time is added to the open list as an initial node, and the heuristic value of the current node is calculated.

The discretization process refers to dividing the map x and y directions and the angle θ of the longitudinal axis of the vehicle at minute intervals Δx, Δy and Δθ, respectively, so that the map is transformed into a plurality of discrete nodes.

The open list refers to: a list used to store the nodes that have been explored on the map

The lower priority vehicle is regarded as a static obstacle, and the path planning of the vehicle cannot reach the node occupied by the obstacle.

The calculation of the heuristic value specifically includes: N _child .f=N _child .g+N _child .h, N _child g=N _current g+length+penalty, N _child .h=|N _child .SS _end |, where: the heuristic value f is composed of the g function value and the h function value, the h function value is only the distance between the s value of the node and the end point s value; the g function value is the total path length from the starting point to the current node, N _current g is the value of the g function _of the parent node, length is the length from the parent node to the child node, and the penalty value penalty is the penalty for reversing during the ST graph path search process.

Step S3-2: Select the node with the smallest heuristic value from the open list as the current node and remove it from the open list and add it to the close list. When the current node at this time is the target node, go to step S3-5, otherwise continue to step S3- 3;

Step S3-3: Use the Reeds-Shepp curve to generate a shortest path from the current node to the target node that conforms to the kinematic constraints. When the Reeds-Shepp curve can just avoid all obstacles, go to step S3-5; otherwise, continue According to the preset node expansion method, the current node is expanded into 6 child nodes.

The Reeds-Shepp curve refers to: summarizing the arrangement and combination of all arcs and straight line segments into 48 types, according to which the connection of any starting and ending point poses on the plane can be realized, and guaranteed in the sense of vehicle kinematics. Shortest, but does not guarantee obstacle avoidance requirements.

The preset node expansion mode refers to: corresponding to two moving directions of forward and backward and three steering directions of left turn, right turn, and straight travel during the movement of the vehicle, a total of 6 driving states, corresponding to 6 expansion nodes.

Step S3-4: When the expanded child node collides with the obstacle, that is, it overlaps with the node occupied by the obstacle or the child node is already in the close table, the child node is ignored; when the child node is not in the open table, the open table is added. Table, calculate and record the heuristic value of the child node and the parent node; when the extended child node is already in the open table, compare the heuristic value of the node in the original open table, if the current heuristic value is smaller, then update the node, Then go to step S3-2.

Step S3-5: The path search is successful, and a collision-free path is output.

As shown in Figure 4, after searching for the target pose node, by taking the parent nodes one by one, the path planning from the starting point to the end point that satisfies the kinematic constraints of the vehicle is obtained backtracking.

Step S4: After completing the path planning, according to the priority of the vehicles, the s-t graph strategy is used to obtain the trajectories of multiple vehicles without conflict in space and time, and the scheduling of multiple vehicles out of the warehouse is completed, which specifically includes:

Step S4-1: For the vehicle with the current speed to be planned, according to the collision-free path obtained in step S3, the vehicle with higher priority is regarded as a moving obstacle, and the path and time are discretized in combination with other moving obstacles to obtain ST diagram, where S is the predetermined path planned by the vehicle in step S3, and this path is discretized with a small mileage interval Δs, the same T is the travel time of the vehicle, and this time is discretized with a small time interval Δt to obtain ST grid diagram with T as the horizontal axis and S as the vertical axis. The trajectory of the vehicle with higher priority starts from time t=0 to the final time t=t _end , every small time interval Δt, to determine whether the position of the vehicle with higher priority at this time is the same as the position of the currently planned vehicle When the overlap occurs, the overlapped moment and the corresponding driving distance s are combined into coordinates (s, t), and marked in the ST map, indicating that other vehicles occupy this section of the path at this moment.

Step S4-2: First create an open list and a close list, and add the origin (0, 0) in the S-T graph to the open list.

Step S4-3: Extract the node with the smallest heuristic value at this time from the open list of the improved A ^* algorithm, select the node with the smallest heuristic value from the open list as the current node, remove it from the open list, and add it to the close list. If S=S _end of the node, go to step S4-6, otherwise continue to step S4-4;

Step S4-4: Expand the current node according to the improved node expansion method, expand 3 sub-nodes and calculate the corresponding heuristic value: Compared with the eight-neighbor expansion method of the ordinary A ^* algorithm, due to the characteristic that time cannot be reversed and the driving speed is not It can tend to infinity, and select the upper right, right and lower right neighborhoods to expand the child nodes, corresponding to the actual driving situation of forwarding, parking, and reversing.

Step S4-5: For each child node, if it already exists in the close table or belongs to the obstacle node in the S-T graph, the child node is ignored; when the child node is not in the open table, it is added to the open table and records the information of the child node. The heuristic value and the parent node; when the extended child node is already in the open table, compare the heuristic value of the node in the original open table, and update the node when the current heuristic value is smaller. Continue to iterate and go to step S4-3.

Step S4-6: The path search in the S-T graph is successful, and the speed is configured for the vehicle according to the searched path in the S-T graph.

As shown in FIG. 5 , the speed configuration is planned for the vehicle by using the S-T diagram, and the vehicle can travel to the end point without collision by traveling along the path planned in step S3 according to the result of the speed configuration.

After a specific practical experiment, according to the parking situation of the vehicle shown in Figure 2, the above method is run with the parameters in Table 1. Under the condition of ensuring the overall time, the vehicle path is smoother, and the number of switching times of the vehicle's driving state can be reduced by half, and No reversing behavior occurs.

Compared with the prior art, the method considers the kinematic constraints of the vehicle, and can also complete the path planning for vehicles with non-holonomic constraints, and the path is smooth, and reversing and steering behaviors do not occur frequently. Considering the pose requirements of the vehicle, it is more reasonable to plan a path that meets the vehicle's outgoing pose requirements. The speed configuration of the vehicle can reduce braking and reversing behaviors while ensuring the minimum overall time.

The above-mentioned specific implementation can be partially adjusted by those skilled in the art in different ways without departing from the principle and purpose of the present invention. The protection scope of the present invention is subject to the claims and is not limited by the above-mentioned specific implementation. Each implementation within the scope is bound by the present invention.

Claims (9)

1. A multi-vehicle scheduling method based on a punishment type mixed A-algorithm and an S-T map strategy is characterized in that a layout map of vehicles and a closed space is constructed according to parameter information of current vehicles and layout information of parking environments, priority rules are designed, the priority of each vehicle is calculated according to the rules, vehicles needing to be delivered out of a warehouse are selected, and a collision-free path which accords with kinematic constraints of each vehicle is planned by adopting the punishment type mixed A-algorithm; and according to the vehicle priority, sequentially adopting an s-t diagram strategy to obtain the conflict-free tracks of the multiple vehicles in space-time, and finishing the dispatching of the multiple vehicles for going out of the garage.

2. The multi-vehicle scheduling method based on the penalty hybrid a-algorithm and S-T graph strategy according to claim 1, which specifically comprises:

step S1: acquiring parameter information of a current vehicle and layout information of a parking environment, and constructing a layout map of the vehicle and a closed space;

step S2: designing a corresponding priority rule according to the task requirement, the parking position of the vehicle and the performance of the vehicle, calculating the priority of each vehicle according to the rule, and selecting the vehicle needing to be taken out of the warehouse;

step S3: a punishment type mixed A-x algorithm is adopted to plan a collision-free path which accords with kinematic constraint of each vehicle, namely the requirements of the position and the attitude angle of a terminal point are met;

step S4: after the path planning is finished, sequentially adopting an s-t diagram strategy to obtain the conflict-free tracks of a plurality of vehicles in space and time according to the vehicle priority, and finishing the dispatching of a plurality of vehicles to leave the garage.

3. The method of claim 1, wherein the parking position is selected from the group consisting of: the vehicle heads are arranged in parallel outwards, as shown in fig. 2, the distances of the vehicles relative to a single outlet are different; the performance of the vehicle comprises: maintenance condition of the vehicle, equipment assembly condition, and mileage;

the design principle is that vehicles with good state performance meeting the task requirement number are driven out of the garage as soon as possible, namely the overall vehicle out-of-garage time is the minimum, and the obtained priority rule is as follows: e _i ＝b ₁ P _i +b ₂ C _i Wherein: e _i Is the final composite index, C, of each vehicle _i The position index of the vehicle is obtained according to P by comprehensively evaluating the performance of the vehicle _i ＝(|x _i (t _fi )-x _i (0)|+|y _i (t _fi )-y _i (0) I))/2, wherein: | x _i (t _fi )-x _i (0)|、|y _i (t _fi )-y _i (0) L is the distance of the midpoint of the rear axle of each vehicle relative to the exit midpoint, b ₁ ，b ₂ Is a weight coefficient representing a tradeoff between vehicle performance and vehicle position.

4. A method for multi-vehicle scheduling based on a penalized hybrid a-x algorithm and S-T graph strategy according to claim 1 or 2, wherein said kinematic constraints comprise:

|a _i (t)|≤a _maxi ，|ν _i (t)|≤ν _maxi ，|ω _i (t)|≤ω _maxi wherein: (x) _i (t)，y _i (t)) is the midpoint coordinate of the rear axle of the vehicle at time t, θ _i (t) is the attitude angle of the vehicle in the XOY coordinate system, v _i (t) and a _i (t) speed of the vehicle along the longitudinal axis of the body and the sumThe speed of the motor is controlled by the speed of the motor,

for the front wheel yaw angle of the vehicle, in the positive counter-clockwise direction, correspondingly, ω _i (t) is the front wheel deflection angle speed, L is the front and rear wheel wheelbase;

the requirement for meeting the position and attitude angle of the terminal point is as follows: satisfies (x) _i (t _fi )，y _i (t _fi )，θ _i (t _fi ))＝(x*，y*，θ*)。

5. The method for dispatching multiple vehicles based on penalty hybrid a-algorithm and S-T graph strategy according to any one of claims 1 to 4, wherein the penalty hybrid a-algorithm specifically comprises:

step S3-1: discretizing the map constructed in the step S1, adding the initial pose of the vehicle to be planned as an initial node into an open list, and calculating the heuristic value of the current node;

step S3-2: selecting the node with the minimum heuristic value from the open list as a current node, removing the open list, adding a close list, and when the current node is a target node, turning to the step S3-5, otherwise, continuing to the step S3-3;

step S3-3: generating a shortest path which accords with the kinematic constraint and is from the current node to the target node by using the Reeds-Shepp curve, and turning to the step S3-5 when the Reeds-Shepp curve can just avoid all barriers; otherwise, continuing to expand the current node into 6 child nodes according to a preset node expansion mode;

step S3-4: when the expanded child node collides with the obstacle, namely the expanded child node is overlapped with the node occupied by the obstacle or the child node is already in a close table, ignoring the child node; when the child node is not in the open table, adding the open table, and calculating and recording the heuristic value and the father node of the child node; when the extended child node is already in the open table, comparing the heuristic value of the node in the original open table, if the current heuristic value is smaller, updating the node, and then going to step S3-2;

step S3-5: and (5) successfully searching the path and outputting a collision-free path.

6. The method of claim 5, wherein the discretization process is selected from the group consisting of: dividing the map in the x direction and the y direction and the angle theta of the longitudinal axis direction of the vehicle at intervals of delta x, delta y and delta theta respectively, and converting the map into a plurality of discrete nodes; the lower priority vehicles are considered static obstacles and the path plan of the vehicle may not reach the nodes occupied by the obstacles.

7. The method of claim 5, wherein the heuristic value calculation specifically comprises: n is a radical of _child· f＝N _child· g+N _child· h，N _child· g＝N _current· g+length+penalty，N _child· h＝|N _child· S-S _end L, wherein: the heuristic value f consists of a g function value and an h function value, and the h function value is only the distance between the s value of the node and the s value of the terminal point; the function value of g is the total path length from the starting point to the current node, N _current· g is a g function value of a father node, length is the length from the father node to a child node, and penalty value penalty is the penalty of reversing in the S-T graph path searching process.

8. The method for multi-vehicle scheduling based on the penalty hybrid a-algorithm and S-T graph strategy according to claim 5, wherein the step 4 specifically comprises:

step S4-1: regarding the vehicle with the current speed to be planned, according to the collision-free path obtained in the step S3, regarding the vehicle with higher priority as a moving obstacle, and combining other moving obstacles to discretize the path and time to obtain an S-T diagram, wherein S is the determined path planned by the vehicle step S3, the path is discretized by a minute mileage interval Δ S, the same T is the vehicle travel time, the time is discretized by a minute time interval Δ T to obtain the path with T as the horizontal axis, and S is the horizontal axisAn S-T grid plot of the vertical axis; starting the track of the vehicle with higher priority from the time t equal to 0 to the final time t equal to t _end Judging whether the position of the vehicle with high priority at the moment is overlapped with the position of the vehicle planned at present or not at a tiny time interval delta T, combining the overlapped moment and the corresponding driving mileage S into a coordinate (S, T) when the overlapping occurs, and marking the coordinate (S, T) in an S-T diagram to indicate that other vehicles occupy the path at the moment;

step S4-2: firstly, creating an open list and a close list, and adding an origin (0, 0) in an S-T diagram into the open list;

step S4-3: extracting the node with the minimum heuristic value at the moment from an open list of the improved A-star algorithm, selecting the node with the minimum heuristic value from the open list as the current node, removing the open list, adding a close list, and adding S-S of the current node at the moment _end Go to step S4-6, otherwise continue to step S4-4;

step S4-4: expanding the current node according to an improved node expansion mode, expanding 3 child nodes and calculating corresponding heuristic values: compared with an eight-neighborhood expansion mode of a common A-star algorithm, due to the characteristic that time cannot be backed off and the driving speed cannot tend to infinity, three neighborhoods of the upper right, the upper right and the lower right are selected to expand child nodes, and the child nodes correspond to forward driving, parking and backing in the actual driving condition;

step S4-5: for each child node, when the child node exists in a close table or belongs to an obstacle node in an S-T graph, the child node is ignored; when the child node is not in the open table, adding the open table, and recording the heuristic value and the father node of the child node; when the expansion child node is already in the open table, comparing the heuristic value of the node in the original open table, and when the current heuristic value is smaller, updating the node; continuing iteration, and turning to the step S4-3;

step S4-6: and successfully searching the path in the S-T diagram, and configuring the speed for the vehicle according to the path searched in the S-T diagram.

9. A system for implementing the method of any preceding claim, comprising: priority computational element, route planning unit and speed planning unit, wherein: the priority calculating unit is connected with the path planning unit and transmits vehicle priority information and information of vehicles needing to go out of the garage, and the path planning unit is connected with the speed planning unit and transmits the path information of the vehicles.

Images