CN118070993A

CN118070993A - Task allocation method for multiple target points and multiple executors

Info

Publication number: CN118070993A
Application number: CN202410365087.6A
Authority: CN
Inventors: 尹泉; 徐舷哲
Original assignee: Huazhong University of Science and Technology
Current assignee: Huazhong University of Science and Technology
Priority date: 2024-03-28
Filing date: 2024-03-28
Publication date: 2024-05-24

Abstract

The invention discloses a task allocation method for multiple target points and multiple executors, belonging to the field of path planning, comprising the following steps: establishing an undirected graph of a space where a task is located, initializing an empty node list, inserting the node list after initializing a root node, and then executing: (S1) searching a node with the minimum total cost from the node list, removing the node from the node list, checking whether path conflict exists in the node, and if so, turning to the step (S2); otherwise, go to step (S3); (S2) creating a new node, taking the union of the path constraint set of the current node and the path constraint set for solving the path conflict as the path constraint set of the new node, adding the new node into a node list after other elements of the new node are determined, and then turning to the step (S1); (S3) outputting the task allocation scheme in the current node and the shortest path when each executing body executes the allocated task. The invention can effectively determine the optimal task allocation scheme and the path planning scheme of the multi-target point multi-executor.

Description

Task allocation method for multiple target points and multiple executors

Technical Field

The invention belongs to the field of path planning, and in particular relates to a task allocation method for multiple target points and multiple executors.

Background

In the context of automated warehouse systems, traffic management, automatic aircraft traction, video games, etc., problems are involved in assigning a plurality of tasks to a plurality of task executives, wherein in the assigning process, it is desirable to target cost minimization, determine for each executor the shortest path that can move from a start point to an end point when executing the assigned task, and ensure that the executives cannot collide with each other during movement. For example, in an automated warehousing system, there are multiple warehouse robots, each of which needs to pick up one inventory pod from a storage location and transport it to one or more storage locations. This class of problems can be abstracted as a multi-agent path planning problem (MAPF). The multi-agent path planning algorithm is well studied in the fields of artificial intelligence and robots. The optimization solution to the MAPF problem has proven to be NP-hard, i.e., there is no guarantee that the optimal solution will be found in polynomial time. Many scholars have studied the MAPF problem in recent years, where a conflict-based search algorithm (CBS) is an advanced algorithm that can find the optimal solution for MAPF.

There are many variations of the MAPF problem that currently take into account both the task allocation problem and the path planning problem with the task allocation multi-agent path planning problem (TAPF). In TAPF problem, the agent is divided into multiple teams, each team is assigned as many single target tasks as agents and a collision-free path is planned for the agent. One special case of TAPF problem is that there is only one team, called anonymous MAPF problem. The anonymous MAPF problem can be solved by a CBS-TA algorithm, which expands the search tree of the CBS to a search forest, each tree corresponds to different allocations, and an optimal solution is found in the search forest by specifying a search rule.

The multi-target multi-agent path planning problem with task allocation (MG-TAPF) is a variation of the TAPF problem, where each task consists of multiple sequential target points (i.e., target locations). The MG-TAPF problem calculates a one-to-one assignment of tasks to each agent and plans a collision-free path for the agent from the current location to a series of target locations for its task assignments such that the sum of the task completion times for each agent is minimized.

Aiming at the task allocation problem of multiple target points and multiple executives, the existing method is often solved by expanding a search tree to a method for searching a forest, the method is only suitable for small-scale scenes with fewer task executives, and when the task executives are more, the problem that a search space explodes and an optimal solution can not be solved possibly exists. The task allocation problem of the multi-target point multi-executor is decomposed into the problem of the single-target point single-executor, and then the solution is carried out.

Disclosure of Invention

Aiming at the defects and improvement demands of the prior art, the invention provides a task allocation method of multiple target points and multiple executors, which aims at determining an optimal task allocation scheme and a corresponding task execution path aiming at the tasks of the multiple target points and the multiple executors, effectively realizing the minimization of the task completion time cost and being not limited by the task scale.

In order to achieve the above object, according to one aspect of the present invention, there is provided a task allocation method for allocating m tasks to m execution bodies, each task including a plurality of target positions, each execution body having a separate starting point, the execution bodies being sequentially moved from the starting point to each target position in the task when executing the task, m being a positive integer greater than 1; the task allocation method of the multi-target point multi-execution body comprises the following steps:

Initializing: establishing an undirected graph of a space where a task is located, initializing an empty node list, and initializing a path constraint set of a root node to be empty; the undirected graph takes the position which can pass through the space where the task is located and is free of an obstacle as an apex, and if a passable channel exists between the two positions, an edge exists between the two corresponding apexes; the node elements include: path constraint set, shortest path set, cost matrix, task allocation scheme, and total cost;

the bottom layer searching step: solving a shortest path set meeting the path constraint set in the directed graph; determining the path cost of each executing body for executing each task according to the shortest path combination to obtain a cost matrix; determining a task allocation scheme according to the cost matrix; determining a total cost required for executing a task according to the task allocation scheme and the cost matrix;

planning: determining a root node element through the bottom layer searching step and adding the root node into a node list, and then executing the following steps:

(S1) searching a node with the minimum total cost from the node list, removing the node from the node list, checking whether path conflict exists in the node, and if so, turning to the step (S2); otherwise, go to step (S3);

(S2) creating a new node, taking the union of the path constraint set of the current node and the path constraint set for solving the path conflict as the path constraint set of the new node, adding the new node into a node list after determining elements of the new node through a bottom layer searching step, and then turning to the step (S1);

(S3) outputting the task allocation scheme in the current node and the shortest path adopted by each executing body when executing the allocated task.

Further, if the path conflict is vertex conflict < a _i,a_j, u, t >, then two new nodes N1 and N2 are created in step (S2), and the path constraint sets N1.Constraints and N1.Constraints are respectively:

N1.constraints←N.constraints∪<a_i,u,t>

N2.constraints←N.constraints∪<a_j,u,t＞

Wherein vertex conflicts < a _i,a_j, u, t > indicate that executives a _i and a _j will conflict at vertex u at time t; n represents the current node, N.constraints represents the path constraint set of the current node; the path constraints < a _i, u, t > indicate that the executive a _i is not allowed to move to vertex u at time t, and the path constraints < a _j, u, t > indicate that the executive a _j is not allowed to move to vertex u at time t.

Further, if the path conflict is an edge object conflict < a _i,a_j, u, v, t >, then two new nodes N1 and N2 are created in step (S2), and the path constraint sets N1.Constraints and N1.Constraints are respectively:

N1.constraints←N.constraints∪<a_i,u,v,t>

N2.constraints←N.constraints∪<a_j,u,v,t>

Wherein, edge object conflicts < a _i,a_j, u, v, t > indicate that executors a _i and a _j will conflict at edge < u, v > at time t; n represents the current node, N.constraints represents the path constraint set of the current node; the path constraints < a _i, u, v, t > indicate that the executive a _i is not allowed to pass the edge < u, v > at time t, and the path constraints < a _j, u, v, t > indicate that the executive a _j is not allowed to pass the edge < u, v > at time t.

Further, in the bottom layer searching step, a shortest path set meeting the path constraint set is solved in the directed graph by adopting an MLA algorithm.

Further, in the bottom layer searching step, a dynamic Hungary algorithm is adopted to determine a task allocation scheme according to the cost matrix.

Further, in step (S1), a CBS-TA algorithm is used to find a node with the smallest total cost from the node list.

Further, in step (S1), before searching the node with the minimum total cost from the node list, the method further includes:

if the node list is empty, judging that the task has no feasible solution, and returning to failure.

According to still another aspect of the present invention, there is provided a computer readable storage medium, including a stored computer program, which when executed by a processor, controls a device in which the computer readable storage medium is located to execute the task allocation method for multiple target points and multiple executives provided by the present invention.

In general, through the above technical solutions conceived by the present invention, the following beneficial effects can be obtained:

(1) The task allocation method of the multi-target point multi-executor realizes a layered task allocation method, specifically, along with the continuous execution of searching, a binary search tree is constructed, each node corresponds to a possible task allocation method, and corresponds to a path constraint set, a shortest path set, a cost matrix and total cost, each node is stored in a node list, and each node with the minimum total cost is searched from the constructed binary tree nodes and removed from the node list, so that high-level searching is realized; for the searched nodes, path conflict detection is carried out on the searched nodes, when the path conflict is detected, new nodes are generated according to the need of eliminating the path conflict and added into a node list, and therefore bottom-layer search is completed; the high-level searching and the bottom-level searching are combined, and finally, the optimal task allocation scheme can be searched. The invention only needs to search for one search tree, can effectively avoid the problem of search space explosion, and simultaneously fully considers the constraint relation in the multi-target point multi-executor task through path conflict detection and path constraint set perfection, thereby ensuring that the solved solution is the optimal solution.

(2) In the preferred scheme of the invention, when the bottom layer search is carried out, the shortest path set meeting the path constraint set is solved in the directed graph by adopting an MLA algorithm, and the shortest path set meeting the requirement can be effectively found.

(3) In the invention, for a newly built node, only a single row of matrix elements in the cost matrix can be changed, while other matrix elements are unchanged.

(4) In the preferred scheme of the invention, the node with the minimum total cost in the node list is searched by using the CBS-TA algorithm in the high-level search, so that the repeated searching nodes are greatly reduced, and the searching efficiency can be remarkably improved.

Drawings

FIG. 1 is a schematic diagram of a multi-target multi-executable task according to an embodiment of the present invention;

FIG. 2 is a flowchart of a task allocation method for multiple target points and multiple executors according to an embodiment of the present invention;

Fig. 3 is a schematic diagram of a search process according to an embodiment of the present invention.

Detailed Description

The present invention will be described in further detail with reference to the drawings and examples, in order to make the objects, technical solutions and advantages of the present invention more apparent. It should be understood that the specific embodiments described herein are for purposes of illustration only and are not intended to limit the scope of the invention. In addition, the technical features of the embodiments of the present invention described below may be combined with each other as long as they do not collide with each other.

In the present invention, the terms "first," "second," and the like in the description and in the drawings, if any, are used for distinguishing between similar objects and not necessarily for describing a particular sequential or chronological order.

In order to make the technical scheme of the invention clearer, before explaining the technical scheme of the invention in detail, the task allocation problem of the multi-target point multi-execution body related to the invention is explained as follows:

In the task allocation problem of multiple target points and multiple executives, { a ₁,a₂,...,a_m } represents m agents in the system. Taking an automatic advantage system as an example, one task execution body is a warehouse robot.

In order to plan a moving path of each task executing body when executing a task, the invention establishes a corresponding undirected graph G= (V, E) aiming at a space where the task is located, wherein V epsilon V represents vertexes in the undirected graph, and E epsilon E represents edges between two vertexes. The undirected graph established by the invention takes the position which can pass through and has no barrier in the space where the task is located as the vertex, and if a passable channel exists between the two positions, an edge exists between the two corresponding vertexes. Taking an automatic warehouse system as an example, the space where the task is located is a warehouse, a plurality of shelves and manual sorting tables are placed in the warehouse, and other spaces are channels where an executive body can move. Modeling the warehouse space by using a grid map or a topological map, wherein the vertex represents a position which can be occupied by an executive body, and the edge represents a unit path which can be passed by an adjacent position.

Each agent a _i has a separate starting point s _i e V, and each task executor can move from one vertex to another per unit time through an edge, or can stay at the original vertex.

The task set to be allocated is { g ₁,g₂,...g_m }, where each task gj is composed of Kj target points g _j＝<g_j[1],...,g_j[K_j ] >, each target point corresponds to a vertex in the undirected graph, and each agent can execute a task.

Using pi _i (t) to denote the position of the executive ai at time t, pi _i＝<π_i(0),...,π_i(T_i),π_i(T_i +1),..> to denote the path of agent a _i, the following points need to be met:

(1) The path is sent out from the starting point of the execution body, namely pi _i(0)＝s_i; (2) At each unit time, the agent moves along the edge to the next vertex, i.e., pi _i(t+1)∈V|(π_i(t),π_i (t+1))ee, or stays at the current location, i.e., pi _i(t)＝π_i (t+1); (3) The execution body sequentially accesses the target points in the task in sequence and finally stays at the last target point.

The goal of the TAPF problem is to minimize the sum of each executable path, i.e., minimize the task completion time cost, expressed asT _i represents the time for agent a _i to reach the last vertex of the task.

For convenience of description, in the following embodiment, a scenario including two tasks g ₁ and g ₂, and two task executors a ₁ and a ₂ shown in fig. 1 is exemplified. In fig. 1, the blank positions are positions where a task can pass through and is free of obstacles, S1 and S2 respectively represent the start point of a ₁、a₂, g ₁＝<g_a[1],g_a [2] represents two target points of task g ₁, and g ₂＝<g_b[1],g_b [2] represents two target points of task g ₂.

The following are examples.

Example 1:

A task allocation method for multiple target points and multiple executors. As shown in fig. 1 and fig. 2, the task scenario corresponding to the present embodiment provides a task allocation method for multiple target points and multiple executors, which includes:

In this embodiment, each node may be expressed as: h= (c, Ω, pi _ta,M_c). Where c represents the assembly of all executives satisfying the current path constraint set, Ω represents the path constraint set, pi represents the shortest path set of the agent satisfying the constraint Ω, pi _ta represents the task allocation scheme, and M _c represents the cost matrix of the current node. The cost matrix M _c is an M x M-dimensional matrix in which each matrix element stores the path cost that the agent a _i needs to move to complete task g _j. Each node stores a possible allocation scheme and associated path planning information.

The planning step of this embodiment initializes the first task allocation scheme by creating a root node. Because it is the root node, path collisions are ignored. In the TAPF problem, the mission allocation scheme needs to be planned first, and then the shortest path of each agent needs to be calculated. As an alternative implementation manner, in this embodiment, the task allocation scheme of the root node is calculated according to the cost matrix M _c and the hungarian algorithm, and once the task allocation scheme is determined, each agent may search for the shortest path to find possible path conflicts.

In this embodiment, a ₁ executes g ₁,a₂ executes g ₂ as the task allocation scheme of the root node.

Optionally, in this embodiment, in the bottom layer searching step, an MLA algorithm is used to solve a shortest path set that satisfies a path constraint set in the directed graph. The MLA algorithm can complete path collision detection while searching for the shortest path.

After the root node is created, the root node is inserted into the node list, and the optimal solution can be searched, and the node with the minimum cost is searched from the node list each time and is removed from the node list. Checking whether path conflict exists in the path, if the path conflict does not exist, returning the allocation scheme corresponding to the node as an optimal scheme; if a path conflict exists, additional path constraints are determined based on the path conflict. Alternatively, in the present embodiment, the first occurring path conflict is selected as the path conflict to be resolved. The element pi of the current node contains the current path planning of each executive, all paths are searched from the moment 0, and when the path conflict occurs, the check is stopped, and the found conflict is returned.

The path conflict may be a vertex conflict or an edge object conflict. Vertex conflicts may be expressed as < a _i,a_j, u, t >, meaning that executives a _i and a _j will collide at vertex u at time t; edge object conflicts may be expressed as < a _i,a_j, u, v, t >, meaning that executives a _i and a _j would conflict at edge < u, v > at time t; a _i and a _j represent two different executives, and u and v represent two vertices in the undirected graph.

If the path conflict is vertex conflict < a _i,a_j, u, t >, then two new nodes N1 and N2 are created in step (S2), and the path constraint sets N1.Constraints and N1.Constraints are respectively:

N1.constraints←N.constraints∪<a_i,u,t>

N2.constraints←N.constraints∪<a_j,u,t>

Wherein, N represents the current node, N.constraints represents the path constraint set of the current node; the path constraints < a _i, u, t > indicate that the executive a _i is not allowed to move to vertex u at time t, and the path constraints < a _j, u, t > indicate that the executive a _j is not allowed to move to vertex u at time t;

If the path conflict is an edge object conflict < a _i,a_j, u, v, t >, two new nodes N1 and N2 are created in step (S2), and the path constraint sets N1.Constraints and N1.Constraints are respectively:

N1.constraints←N.constraints∪<a_i,u,v,t>

N2.constraints←N.constraints∪<a_j,u,v,t>

Where the path constraint < a _i, u, v, t > indicates that the executive a _i is not allowed to pass the edge < u, v > at time t, and the path constraint < a _j, u, v, t > indicates that the executive a _j is not allowed to pass the edge < u, v > at time t.

In this embodiment, after the root node is fetched from the node list, it is checked that there is a vertex conflict < a ₁,a₂, B2,1> between a ₁、a₂, that is, at time 1, the executing bodies a ₁ and a ₂ will conflict at the location B2. For two agents a ₁ and a ₂ that collide, the present embodiment creates two new nodes N1 and N2, whose path constraint sets N1.Constraints and N1.Constraints are respectively:

N1.constraints←N.constraints∪<a₁,B2,1>

N2.constraints←N.constraints∪<a₂,B2,1>

Wherein, N represents the current node, namely the root node, N.constraints represents the path constraint set of the current node, namely the empty set; path constraints < a ₁, B2,1> indicate that executable a ₁ is not allowed to move to vertex B2 at time 1, and path constraints < a ₂, B2,1> indicate that executable a ₂ is not allowed to move to vertex B2 at time 1.

According to the new path constraint, performing bottom-layer search on the execution bodies with conflicts by using an MLA algorithm to find the shortest path;

In the bottom layer search, the agent needs to sequentially reach the target points in the task and meet the path constraint set, and the MLA algorithm can find the shortest path meeting the requirement. The MLA algorithm is an improved algorithm of the Space-TimeA algorithm, and the next target point is distinguished by adding labels to different target points, and the algorithm is mainly to calculate h-value as follows:

where dist (s _i,g_i 0) represents the distance of the current position to the next target point, Representing the distance between the remaining target points.

Path update cost matrix using MLA search, the agent that re-plans the path uses new path cost, and the path cost of other agents is unchanged.

The new cost matrix is used to calculate the tasking scheme. The general method is to recalculate by using the Hungary algorithm, but as only a single row of matrix elements are changed and other matrix elements are unchanged, the Hungary algorithm is directly used, so that the cost is large. As a preferred embodiment, the task allocation scheme is determined by using a dynamic hungarian algorithm for the new node established, and only the task allocation scheme of the changed agent is repeatedly calculated, and the task allocation schemes of other agents are unchanged.

In an embodiment, the cost of executing body a ₁ to execute tasks g ₁ and g ₂ is 5, and the cost of executing body a ₂ to execute tasks g ₁ and g ₂ is 5, so the task allocation scheme is unchanged.

And after the created new nodes N1 and N2 are inserted into the node list, performing high-level searching again, and taking out the node with the minimum total cost from the node list to judge whether collision exists. Optionally, in this embodiment, when performing a higher-level search to determine a node with the smallest total cost in the node list, a CBS-TA algorithm is used.

As shown in fig. 3, the present embodiment takes out the node N2 from the node list, and the node N2 has a conflict, so the solution of N2 is returned as the optimal solution, and the shortest path that each executing body follows when executing the assigned task when assigning the task according to the determined task assignment scheme can be determined according to the shortest path set of the node N2.

In other embodiments of the present invention, a situation may occur in which no node that does not have a path conflict is obtained until the node list is empty, at which time it is determined that the task has no feasible solution, and failure is returned.

As shown in fig. 3, in the searching process, a binary search tree is constructed, and each node corresponds to a possible task allocation method, so that compared with searching forest, the problem of search space explosion can be effectively avoided.

In general, the invention provides a task allocation method for multiple target points and multiple executors, which is a hierarchical search method, wherein in the high-level search, a CBS-TA algorithm is used for searching all possible tasks to be allocated to the task executors, and in the low-level search, an MLA algorithm is used for searching the shortest collision-free path, so that the search efficiency can be obviously improved under the condition of ensuring the optimal solution. The task allocation method effectively solves the problems that the existing task allocation method with multiple target points and multiple executors has search space explosion or cannot obtain the optimal solution.

Example 2:

A computer readable storage medium, comprising a stored computer program, which when executed by a processor, controls a device in which the computer readable storage medium is located to execute the task allocation method for multiple target points and multiple executors provided in the above embodiment 1.

It will be readily appreciated by those skilled in the art that the foregoing description is merely a preferred embodiment of the invention and is not intended to limit the invention, but any modifications, equivalents, improvements or alternatives falling within the spirit and principles of the invention are intended to be included within the scope of the invention.

Claims

1. The task allocation method of the multi-target point multi-executor is used for allocating m tasks to m executors, each task comprises a plurality of target positions, each executor is provided with a single starting point, when the executor executes the task, the executors need to sequentially move to each target position in the task from the starting point, and m is a positive integer greater than 1; the task allocation method for the multi-target point multi-executable is characterized by comprising the following steps:

Initializing: establishing an undirected graph of a space where a task is located, initializing an empty node list, and initializing a path constraint set of a root node to be empty; the undirected graph takes the position which can pass through in the space where the task is located and is free of an obstacle as an apex, and if a passable channel exists between the two positions, an edge exists between the two corresponding apexes; the node elements include: path constraint set, shortest path set, cost matrix, task allocation scheme, and total cost;

Planning: determining a root node element through the bottom layer searching step and adding the root node into the node list, and then executing the following steps:

(S1) searching a node with the minimum total cost from the node list, removing the node from the node list, checking whether path conflict exists in the node list, and if so, turning to the step (S2); otherwise, go to step (S3);

(S2) creating a new node, taking the union of the path constraint set of the current node and the path constraint set for solving the path conflict as the path constraint set of the new node, adding the new node into the node list after determining the element of the new node through the bottom layer searching step, and then turning to the step (S1);

2. The method of task allocation for multiple target points and multiple executors according to claim 1, wherein if the path collision is vertex collision < a _i,a_j, u, t >, then two new nodes N1 and N2 are created in the step (S2), and path constraint sets N1.Constraints and N1.Constraints are respectively:

N1.constraints←N.constraints∪<a_i,u,t>

N2.constraints←N.constraints∪<a_j,u,t>

3. The method of task allocation for multiple target points and multiple executors according to claim 1, wherein if the path conflict is an edge object conflict < a _i,a_j, u, v, t >, then two new nodes N1 and N2 are created in the step (S2), and path constraint sets N1.Constraints and N1.Constraints are respectively:

N1.constraints←N.constraints∪<a_i,u,v,t>

N2.constraints←N.constraints∪<a_j,u,v,t>

4. A method for task allocation of multiple target points and multiple executors according to any one of claims 1-3, wherein in the bottom layer searching step, a MLA algorithm is adopted to solve a shortest path set satisfying a path constraint set in a directed graph.

5. A multi-target point polytype task allocation method according to any one of claims 1-3, wherein in the bottom layer searching step, a dynamic hungarian algorithm is adopted to determine a task allocation scheme according to the cost matrix.

6. A multi-target multi-executable task allocation method according to any one of claims 1 to 3, wherein in said step (S1), a CBS-TA algorithm is used to find a node with the smallest total cost from said list of nodes.

7. A multi-target multi-executable task allocation method according to any one of claims 1 to 3, wherein said step (S1) further comprises, before searching for a node having the smallest total cost from said node list:

8. A computer readable storage medium comprising a stored computer program which, when executed by a processor, controls a device in which the computer readable storage medium is located to perform the multi-target multi-executable task allocation method according to any one of claims 1 to 7.