CN-121303489-B - Scheduling method for solving multi-unmanned platform in multi-task frequent mode

CN121303489BCN 121303489 BCN121303489 BCN 121303489BCN-121303489-B

Abstract

The invention relates to a scheduling method for solving a multi-unmanned platform in a multi-task frequent mode, and belongs to the technical field of path planning. The method comprises the steps of distributing new tasks received by polling to unmanned platforms, calculating Manhattan distances required by the unmanned platforms distributed with the new tasks and/or planned to finish corresponding tasks, determining the priority of each unmanned platform based on the Manhattan distances and the running speeds of the unmanned platforms, and carrying out path planning for each unmanned platform according to the priority in sequence, wherein obstacle information is obtained based on running paths of the tasks in progress and the tasks in planning, whether a path scheme of one node in the path planning to reach a next adjacent node has a conflict is determined based on the obstacle information, and the next arrival node is determined from the adjacent nodes without the conflict. The method realizes the sub-optimal solution in a short time, and solves the problems of high algorithm time cost and high priority sensitivity in the prior art.

Inventors

YUAN QINGXIN
DONG YANPENG
QI XIANYU
WANG XIAOJUN

Assignees

北京机械设备研究所

Dates

Publication Date: 20260508
Application Date: 20240708

Claims (8)

1. The scheduling method for solving the problem of multiple unmanned platforms in a multi-task frequent mode is characterized by comprising the following steps: Distributing the new task received by polling to the unmanned platform; Calculating Manhattan distance required by each unmanned platform allocated with a new task and/or planned to finish a corresponding task, and determining the priority of each unmanned platform based on the Manhattan distance and the running speed of the unmanned platform; The path planning for one unmanned platform comprises obtaining barrier information based on the running path of the task in progress and the planned non-progress task, determining whether the path scheme of one node in the path planning reaching the next adjacent node has conflict or not based on the barrier information, and determining the next reaching node from the adjacent nodes without conflict; The obstacle information comprises a time point and a node of departure of the unmanned platform, a time point and a node of arrival at a terminal point, a running track, nodes of a path and time of arrival at each node of the path; The step of determining whether the point conflict exists in the path scheme from one node to the next adjacent node in the path plan based on the obstacle information comprises the following steps: Acquiring a distance between one node and a next adjacent node in a path scheme of the unmanned platform and an operation speed, acceleration and deceleration in a data matrix of the unmanned platform to obtain an operation time period, wherein the distance is obtained by a map distance matrix; acquiring unmanned platforms with running tracks in the obstacle information in the time period by utilizing the departure time point, the arrival time point and the arrival time of each node of the route of each unmanned platform in the obstacle information; Calculating the distance between the unmanned platform and the central point of the unmanned platform with the running track in the obstacle information for each time point in the time period, wherein the distance is obtained by using the nodes of the unmanned platform starting, the nodes reaching the end point, the running track and the nodes of the path in the obstacle information in the time period; calculating the sum of the longest distance values of the two unmanned platforms by utilizing the longest distance value from the center point of the unmanned platform to the edge of the unmanned platform in the unmanned platform data matrix; when the center point distance is less than or equal to the sum of the longest distance values, a point conflict is considered to exist; determining whether an edge conflict exists in a path scheme from one node to a next adjacent node in the path plan based on the obstacle information, wherein the method comprises the following steps: acquiring a road on which the unmanned platform runs from one node to the next node according to a path scheme and a running time period for running the road, wherein the running time period is obtained by the distance between a starting node and a stopping node and the running speed, acceleration and deceleration of the unmanned platform; acquiring unmanned platforms with running tracks in the obstacle information in the time period by utilizing the departure time point, the arrival time point and the arrival time of each node of the route of each unmanned platform in the obstacle information; Obtaining a road travelled by the unmanned platform in the obstacle information by using nodes of the unmanned platform in the time period, nodes reaching the terminal, running tracks and nodes of the path in the obstacle information; Judging whether the unmanned platform enters the same road in the opposite direction in the time period and the unmanned platform in the obstacle information, and if so, considering that the side conflict exists.
2. The method for scheduling multiple unmanned platforms in a multitasking mode according to claim 1, wherein the calculating the manhattan distance required for each unmanned platform assigned with a new task and/or planned to have no tasks to perform a corresponding task comprises: updating the state of each unmanned platform as the initial state of the current path planning; And obtaining the Manhattan distance required by each unmanned platform to complete the task based on the node of the initial state of each unmanned platform and the assigned task.
3. The method for scheduling multiple unmanned platforms in a multi-task concurrency mode according to claim 2, wherein updating the state of the unmanned platform as the initial state of the current path planning comprises: Acquiring a node and a time point of an unmanned platform which is used as an initial state of the unmanned platform after the current task is completed, wherein the node and the time point are used as the initial state of the unmanned platform which bears a new task and/or is planned to be not used for carrying out the task and is executing the task; and acquiring the node of the unmanned platform which does not perform the task when the system receives the new task as the initial state of the platform.
4. A method of scheduling a multi-unmanned platform in a multi-tasking mode according to claim 2 or 3, wherein the manhattan distance is obtained by: Wherein, the Representing the value of the manhattan distance, Representing the coordinates of the node where the initial state of the unmanned platform is located, Representing the unmanned platform The coordinates of the start points of the individual tasks, Representing the unmanned platform The coordinates of the end points of the individual tasks, Representing the total number of tasks for the unmanned platform.
5. The method for scheduling multiple unmanned aerial vehicles in the multi-task concurrency mode according to claim 1, wherein determining the priority of each unmanned aerial vehicle based on the Manhattan distance and the operation speed of the unmanned aerial vehicle comprises estimating task completion time by using the Manhattan distance and the operation speed in the unmanned aerial vehicle data matrix, and determining the priority of the unmanned aerial vehicle according to the task completion time.
6. The method for scheduling multiple unmanned platforms in a multi-task frequent pattern according to any one of claims 1 and 5, wherein a map and an unmanned platform which need to be operated by a task are modeled in advance to obtain a distance matrix of the map and an unmanned platform data matrix, wherein the distance matrix comprises distances among nodes, and the unmanned platform data matrix comprises the serial number, the running speed, the acceleration and the deceleration of the unmanned platform and the longest distance value from the central point of the unmanned platform to the edge of the platform.
7. The scheduling method for resolving a multi-unmanned platform in a multi-tasking mode according to claim 1, wherein the determining the next node from the neighboring nodes where no conflict exists comprises: calculating cost values of all adjacent nodes without conflict; and selecting a point with the minimum cost value as a next node, wherein the cost value represents the sum of the path length from the starting point to the node and the estimated path length from the node to the end point.
8. The scheduling method for solving the problem of multiple unmanned platforms in a multi-tasking mode according to claim 1, wherein the allocating the new task received by the poll to the unmanned platform comprises: The method comprises the steps of arranging newly received tasks according to a time sequence of receiving, distributing the tasks by utilizing a FIFO principle, counting the load condition of each unmanned platform, sequentially distributing the tasks to the unmanned platform with the smallest load, and distributing the unmanned platform with the smallest number if a plurality of unmanned platforms with the smallest load exist at the same time.

Description

Scheduling method for solving multi-unmanned platform in multi-task frequent mode Technical Field The invention relates to the technical field of path planning, in particular to a scheduling method for solving a multi-unmanned platform in a multi-task frequent mode. Background With the rapid development of low cost sensors and computing devices, more and more manufacturing application scenarios can support concurrent control of unmanned platforms such as large-scale mobile robots, unmanned vehicles, and the like. The application scene of the large-scale unmanned platform often provides higher requirements for task dispatch flexibility, system structure robustness, planning effectiveness and the like of a dispatching system. The existing method for solving the scheduling problem of the multi-unmanned platform is mainly developed based on two algorithms, wherein one algorithm uses an upper-layer searching operator, once collision and conflict exist in the current planning scheme, a lower-layer planner is triggered to conduct re-planning until the upper-layer searching operator detects that no collision and conflict occur, and the method requires high calculation time cost. Another algorithm is a lot of saving in calculation time cost, but due to the characteristic of sequential planning, this method has high sensitivity to priority. Disclosure of Invention In view of the above analysis, the present invention aims to provide a scheduling method for solving the problem of high time cost and high priority sensitivity of the existing scheduling method. The embodiment of the invention provides a scheduling method for solving a multi-unmanned platform in a multi-task frequent mode, which comprises the following steps: Distributing the new task received by polling to the unmanned platform; Calculating Manhattan distance required by each unmanned platform allocated with a new task and/or planned to finish a corresponding task, and determining the priority of each unmanned platform based on the Manhattan distance and the running speed of the unmanned platform; And carrying out path planning on each unmanned platform according to the priority, wherein the path planning on one unmanned platform comprises the steps of obtaining barrier information based on the running path of the task in progress and the planned non-task in progress, determining whether a path scheme of one node in the path planning reaching a next adjacent node has conflict or not based on the barrier information, and determining the next reaching node from the adjacent nodes without the conflict. Based on a further improvement of the above method, calculating manhattan distances required by each unmanned platform assigned with new tasks and/or planned to not perform tasks to complete the respective tasks, comprises: updating the state of each unmanned platform as the initial state of the current path planning; And obtaining the Manhattan distance required by each unmanned platform to complete the task based on the node of the initial state of each unmanned platform and the assigned task. Based on the further improvement of the method, updating the state of the unmanned platform as the initial state of the current path planning comprises the following steps: Acquiring a node and a time point of an unmanned platform which is used as an initial state of the unmanned platform after the current task is completed, wherein the node and the time point are used as the initial state of the unmanned platform which bears a new task and/or is planned to be not used for carrying out the task and is executing the task; and acquiring the node of the unmanned platform which does not perform the task when the system receives the new task as the initial state of the platform. Based on a further improvement of the above method, the manhattan distance is obtained by: Wherein d Manhattan represents a Manhattan distance value, (x c,yc) represents coordinates of a node where an initial state of the unmanned platform is located, (x io,yio) represents coordinates of a start point of an ith task of the unmanned platform, (x id,yid) represents coordinates of a destination point of the ith task of the unmanned platform, and tasknum represents a total number of tasks of the unmanned platform. Based on the further improvement of the method, determining the priority of each unmanned platform based on the Manhattan distance and the running speed of the unmanned platform comprises estimating task completion time by using the Manhattan distance and the running speed in the unmanned platform data matrix, and determining the priority of the unmanned platform from high to low according to the task completion time. Based on further improvement of the method, the obstacle information comprises a time point and a node of departure of the unmanned platform, a time point and a node of arrival at an end point, a running track, a node of a path and a time of arrival at each node of the path. Base