CN106875090B - A Multi-robot Distributed Task Allocation Formation Method Oriented to Dynamic Tasks - Google Patents
A Multi-robot Distributed Task Allocation Formation Method Oriented to Dynamic TasksDownload PDFInfo
- Publication number
- CN106875090B CN106875090BCN201710015070.8ACN201710015070ACN106875090BCN 106875090 BCN106875090 BCN 106875090BCN 201710015070 ACN201710015070 ACN 201710015070ACN 106875090 BCN106875090 BCN 106875090B
- Authority
- CN
- China
- Prior art keywords
- task
- robot
- auction
- point
- task point
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
- G06Q10/063—Operations research, analysis or management
- G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
- G—PHYSICS
- G05—CONTROLLING; REGULATING
- G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
- G05D1/02—Control of position or course in two dimensions
- G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
- G05D1/0287—Control of position or course in two dimensions specially adapted to land vehicles involving a plurality of land vehicles, e.g. fleet or convoy travelling
- G05D1/0289—Control of position or course in two dimensions specially adapted to land vehicles involving a plurality of land vehicles, e.g. fleet or convoy travelling with means for avoiding collisions between vehicles
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
- G06Q10/047—Optimisation of routes or paths, e.g. travelling salesman problem
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
- G06Q10/063—Operations research, analysis or management
- G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
- G06Q10/06312—Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling
Landscapes
- Business, Economics & Management (AREA)
- Human Resources & Organizations (AREA)
- Engineering & Computer Science (AREA)
- Strategic Management (AREA)
- Economics (AREA)
- Entrepreneurship & Innovation (AREA)
- General Physics & Mathematics (AREA)
- Physics & Mathematics (AREA)
- Operations Research (AREA)
- Development Economics (AREA)
- Game Theory and Decision Science (AREA)
- Quality & Reliability (AREA)
- Tourism & Hospitality (AREA)
- Theoretical Computer Science (AREA)
- General Business, Economics & Management (AREA)
- Marketing (AREA)
- Educational Administration (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Aviation & Aerospace Engineering (AREA)
- Automation & Control Theory (AREA)
- Manipulator (AREA)
- Feedback Control In General (AREA)
Abstract
Translated fromChinese
Description
Technical Field
The invention relates to the technical field of robot intelligent auction algorithms, in particular to a dynamic task-oriented multi-robot distributed task allocation forming method.
Background
With the deep knowledge of people on artificial intelligence and complex systems, the robot system has good application prospects in the fields of buildings, military, fire fighting, industrial production and the like. However, in the current multi-robot system, the number of tasks is large, the information contained in the task points is complex, the number of the participating robots is large, and the calculation cost of the global search algorithm is exponentially increased, so that the global search algorithm is difficult to find the optimal solution of the task allocation problem within the specified time. Therefore, the global search algorithm is not suitable for solving the large-scale multi-agent dynamic task allocation problem. In large-scale systems, task allocation must meet real-time requirements, and tends to obtain a "good" solution within a specified time, which is not necessarily the optimal solution. Therefore, the method has important significance for the research of the multi-robot dynamic task allocation problem with time constraint.
Most of the current task allocation adopts an auction algorithm, the traditional auction algorithm is static in terms of tasks, and a one-time auction algorithm is adopted. However, in the case of a large number of task points and dynamic changes, the method has a great defect, cannot perform scheduling more times, cannot meet the real-time requirement, and cannot obtain an ideal effect.
Disclosure of Invention
The present invention provides a dynamic task oriented multi-robot distributed task allocation formation method that overcomes or at least partially solves the above-mentioned problems by solving the problems of multiple dynamic tasks in an environment through cooperative cooperation between robots based on an improved auction algorithm and in conjunction with a-star algorithm path optimization.
In order to achieve the above object, the present invention provides a dynamic task-oriented multi-robot distributed task allocation forming method, which comprises:
s1: according to the information in the environment map, the factors and difficulties which need to be considered in the task allocation problem are cleared;
s2: when a task occurs, a task allocation scheme is generated based on a multi-stage auction algorithm, and the robot executes the task according to the task allocation scheme.
Further, the step S1 includes:
s11: a target environment map is given, and a plurality of robots with task execution capacity, task points with attributes changing along with time and a plurality of obstacles are distributed on the map;
s12: according to the state change of the task points, the factors and difficulties needing to be considered for cleaning task distribution
Further, in step S11, the environment is a robot work environment, a rectangular coordinate system is established for a given environment map, the coordinate system uses the x axis to the right as a positive direction and the y axis to the positive direction, the work environment is divided into a plurality of grids, and N (N belongs to Z) is spatially distributed on the environment map+) Task point, M (M belongs to Z)+) Individual robot and B (B ∈ Z)+) And determining coordinates of the robot, the task and the obstacle, respectively.
Where the task is denoted by the letter j, where j equals 1,2, …, N, the task approximates a point on the map. The robot is denoted by the letter i, where i ═ 1,2, …, M. The obstacle is denoted by the letter B, where B is 1,2, …, B.
The coordinates of the task point on the map are
Wherein j is 1,2, …, N; the coordinates of the robot on the map are
Wherein i is 1,2 … M; the coordinates of the obstacle on the map are
Where k is 1,2, …, B.
The distance formula between the task point and the robot is as follows:
suppose that the j coordinate of the task point and the j' coordinate of the task point are respectively
The distance between the two is expressed as:
further, in step S12, the state quantity of the task point j (j ═ 1,2, …, N) at time (t +1) changes exponentially with time, and the state quantity of the task point j (j ═ 1,2, …, N) is expressed as:
in the formula:
Sj(t+1)，Sj(t) task point state quantities of task j (j ═ 1,2, …, N) at stages (t +1) and t, respectively;
αjthe state change rate of the jth task point;
βiexecution capabilities of robot i and βi＞0；
The time difference between t and (t + 1);
the task quantity threshold value is set, whether the task is finished or not is judged, and when s is reached, the task quantity threshold value is setj(t) < ε, this indicates that the task is complete.
This is a task state distributed dynamic task allocation problem. The state change of the task point is in a continuous exponential function form (equation three). The task volume is time-distributed and is affected by how many robots are performing the task (the sum of the performance capabilities of the agent).
The completion time of task point j (j ═ 1,2, …, N) is inversely proportional to the sum of the performance capabilities acting on task point j. The execution capacity of m robots for executing the target task j at the stage t and
then, it indicates that the m robots cannot complete the task point, sj(t) exhibits an ascending trend; when in use
Then m robots are shown to be able to complete the task point, sj(t) shows a tendency to decline.
Further, in step S12, the system task assignment needs to consider factors including task point attribute parameters and robot attribute parameters.
Attribute parameter of task point j (j is 1,2, … N)The number of the components comprises: task quantity (i.e. state value) S of task pointj(t) indicating the task amount of the task point at time t, wherein j is 1,2, …, N, and when t is 0, indicating the initial amount S of the task pointj(0) Duty point change rate αj(ii) a The task points j are distributed in space, and the positions of the task points j on the environment map
The attribute parameters of the robot i (i ═ 1,2, …, M) include: velocity v of movementiThe length of the path taken by the robot i in unit time, and a robot capability value βi(ii) a The position of the robot on the environment map
With the increase of the number of target task points and robots, the difficulty of task allocation problem increases rapidly, and the importance degree and the state change rate of each target task point, the cost and the execution capacity of each intelligent agent when executing tasks are all factors to be considered.
Assuming that the robot that is heading for the jth task point does not go to other task points until the next phase of solution generation, for a given M (M ∈ Z)+) Personal robot, N (N is belonged to Z)+) A task point, which is shared by multiple auctions
A distribution scheme having a complexity of
In step S2, the method further includes:
s21: when a task is detected, selecting a robot closest to a task point as a proxy robot; if the robot closest to the plurality of task points is the same robot i (i is 1,2, …, M), the system selects the robot i of the task point closest to the origin of the rectangular coordinate system from the plurality of task points as the proxy robot;
s22: the agent robot issues auction information to the auction robots within the communication radius to wait for feedback;
s23: the auction robot receiving the auction information selects the task point with the highest profit to bid according to the profit function of the auction robot;
s24: the agent robot collects the bidding information, selects the winning robot according to a preset rule and informs the winning robot to execute the task;
s25: and selecting the nearest task point for the auction robots not winning the bid and the robots in the communication blind areas.
Further, in step S2, when detecting that the task point and the idle robot without targets have been completed, the idle robot is re-auctioned, so that the idle robot obtains a new task point again, thereby obtaining a new allocation scheme, and the auction is stopped until all task points in the environment are executed.
The target-oriented task of the invention is dynamically changed along with time, and the task points are distributed on the completed time point, namely the task points are inconsistent on the executed time.
If a traditional auction algorithm flow is used, after an allocation scheme is generated, a dynamic target task is executed according to the scheme, and it is difficult to adapt to the dynamic change and real-time requirements of the target task.
The improved auction algorithm can track the state change of the task points in real time, once the task points are finished, the robot without targets can exist, and the algorithm can redistribute the task points, so that a new distribution scheme is obtained.
Further, in step S22, the agent robot is responsible for issuing auction information to the auction robots within the communication radius, and waits for feedback; the agent robot of each task point j (j is 1,2, …, N) grasps the relevant auction information of the task point j, and the message includes: the position of the task point j, the change rate of the task point j, the state quantity of the task point j and the number s of suitable robots needed by the task point j. The state quantities of the task points change exponentially with time.
Number of suitable robots s required for task point jjIs defined as: suppose there are w robots such that
And is
The optimal number s of robots needed by the task point j takes the following values:
w≤sjw +2 ≤ (four type)
The robots i (i is 1,2, …, M) all have corresponding communication radiuses ri(the communication radius of the robot can be set to be different values), and the agent robot is responsible for issuing auction information to the auction robots within the communication radius.
Further, in step S23, the auction robot that has received z (0 ≦ z ≦ N) pieces of proxy robot auction information balances the information with the following balance criteria: the auction robot analyzes the z auction information issued by the agent robot, the traditional auction algorithm is improved, a dynamic economic benefit function is introduced, and the robot i calculates the income value E after executing a certain task point jij(EijReal number) and selects the most profitable task point to bid. The dynamic revenue function used is:
Eij＝g(k1,Sj(t),αj,βi,n)-h(k2,dij) (formula five)
In the formula:
g, the robot i obtains benefits after executing the task point j and is an exponential function;
h is the cost consumed by the robot i to execute the task point j;
k1, k2 variable weight parameters, which can be set to their respective values under different circumstances;
dijthe path length between the robot i and the task point j is long;
in the above formula, k1 and SjThe product of (t) is the scaling factor of an exponential function, αj,βiN is the relation between the three
Forming an index in the index function, n representing the number of robots that are executing the task point j (when t is 0, the task point is not executed by a robot, and n is 0);
h is dijFunction, given the parameter k2, the value of h is given by dijAnd (6) determining.
Each robot has a corresponding execution capacity value β for a given environment mapi(i ═ 1,2, …, M), the ability value of this robot i is a constant, and the execution ability values between robots may be set to be different.
Further, in step S24, after receiving the bidding information of the auction robots, the agent robot analyzes the information, selects the auction robot that wins the bid according to the target with the greatest overall benefit, and notifies all the bidding auction robot results.
Further, in step S25, the robots in the communication blind areas in the map (there may be robots that cannot receive the auction information issued by the agent robot due to the limitation of the communication radius in the environment map) and the auction robots that have not bid themselves to execute the task points closest to the robots.
Further, in step S24, the agent robot may select the auction robot that wins the bid according to a predetermined rule, where the specific content is:
proxy robot acceptance n for task point jjBid message of each auction robot if nj＞sjThen sort by profit size, choose top ranked(s)j-1) one auction robot acts as a middling robot and informs all bidding auction robots if nj＜sjThen n isjAll the auction robots are the middle-standard robots.
Further, in the step S24, in the process of the robot traveling, the path is optimized through the a-star algorithm, so as to reasonably avoid collision with other robots and obstacles, and search out the optimal collision-free path for the robot to reach the corresponding task point.
And generating a task allocation scheme, starting to execute the target task point by the robot according to the allocated scheme, displaying the position of the robot in real time in the forward target task process by the robot, and searching the optimal collision-free path through an A-star algorithm.
In the searching process of the A-star algorithm, a method for searching the extended space node by a cost function is adopted, and the general form of the cost function is as follows:
(i) g (i) + h (i) (formula six)
In the formula:
(i) a valuation function of node i from the initial node to the target node;
g (i) the actual cost from the initial node to node i in the state space;
h (i) estimated cost of best path from node i to the target node.
The optimal collision-free path is searched through an A-star algorithm, the robot can reasonably avoid obstacles and cannot meet the obstacles in the traveling process, and the A-star is an effective method for solving the shortest path, so that the real-time and environment adaptability efficiency of path planning is improved.
The robot follows the following rules throughout the execution:
a) the optimal number of robots required for task point j is sj；
b) The robot which is going to the jth task point does not go to other task points before the scheme of the next stage is generated;
c) the robot cannot go to the executed task point;
d) the agent robot selects the auction robot for winning the bid according to a rule established in advance;
e) the auction robot which does not bid or the communication blind area robot (the robot which can not receive the auction information sent by the agent robot in the communication radius) can execute the nearest task point;
f) the agent robot executes the task point of the self agent.
Through the technical scheme, a set of complete execution scheme is finally generated, and the time required for completing all task points is obtained. The time required to complete all task points is the time at which the last task point was executed.
Based on the technical scheme, the multi-stage auction algorithm facing the dynamic tasks is provided, the problem of dynamic task allocation in the environment is solved, the given task is solved by one-time allocation adopted by the traditional auction algorithm, and the expected effect cannot be achieved due to the fact that the dynamic tasks are limited greatly. Through the realization of multiple auctions, the aim of time optimization is fulfilled, the resources of the robot are utilized to the greatest extent, the method is simulated on VC + + and Csharp platforms, and a large number of experimental simulation test results show that the improved auction algorithm can better solve dynamic tasks in the environment compared with the traditional auction algorithm, meets the real-time requirement through multiple distribution, and can provide an approximate optimal solution.
Drawings
FIG. 1 is a diagram of an environment model according to an embodiment of the present invention.
Figure 2 is a flow diagram of a multi-stage auction algorithm according to an embodiment of the present invention.
Fig. 3 is a flow diagram of proxy robot work according to an embodiment of the present invention.
Fig. 4 is a flowchart of the operation of the auction robot according to the embodiment of the present invention.
Fig. 5 is a simulation diagram of a conventional auction algorithm (single-stage auction algorithm) according to an embodiment of the present invention.
Fig. 6 is a simulation diagram of an improved auction algorithm (multi-stage auction algorithm) according to an embodiment of the present invention.
FIG. 7 is a graph comparing time consumption of a multi-stage auction algorithm with a single-stage auction algorithm according to an embodiment of the present invention.
Detailed Description
The following detailed description of embodiments of the present invention is provided in connection with the accompanying drawings and examples. The following examples are intended to illustrate the invention but are not intended to limit the scope of the invention.
The invention provides an improved auction algorithm and a method for solving the problem of a plurality of dynamic tasks in the environment through cooperative cooperation between robots in combination with A-star algorithm path optimization.
The multi-stage auction algorithm is improved on the basis of the traditional auction algorithm, and corresponding rules and dynamic profit functions are added. The traditional auction algorithm is suitable for solving the distribution problem of static target tasks, the value of the target tasks and the execution cost of the robots are respectively measured through benefit and cost parameters, the auction algorithm of the target tasks to the robots is designed, a distribution scheme is generated, and the whole system only carries out auction once.
The robot collaborative cooperation is embodied as follows: when the robot detects that a task point occurs, the agent robot issues auction information to the auction robot, and the auction robot balances and bids according to the received information; the agent robot selects an allocation scheme according to the feedback information and a preset rule, the robot sends the known information to the robot in the communication radius of the robot in the process of executing the task, resource sharing is achieved, once the task points are completed, the idle robot obtains target task points through re-auction to assist other robots to execute the task points until all the task points are completed.
According to an embodiment of the present application, as shown in fig. 1, the environment model diagram of the present invention includes the following steps:
firstly, a rectangular coordinate system is established for a target map, the target map is divided into a plurality of map blocks with the same size, and the length and the width of each map block are equal.
Secondly, in the embodiment of the present invention, given that the length and width of the target map are all 300 units, the map contains 89401 map blocks.
Given an environment map, M (M E Z) can be set specifically+) Personal robot, N (N is belonged to Z)+) A task point, and B (B ∈ Z)+) An obstacle.
And calculating and storing the distance between the task points (formula two) and the distance between the task points and the robot (formula one).
Finally, the study objective of the invention was analyzed: aiming at a plurality of robots with certain task execution capacity, a plurality of tasks with the attributes changing along with time are given, a multi-robot dynamic task allocation strategy is established, the completion time of all tasks is optimized, and the completion time of the last task can be used for measurement.
When M (0 ≦ M) robots act on task point j (j ≦ 1,2, …, N), the task state quantity formula for task point j at (t +1) (t ≧ 0) is:
as shown in FIG. 2, the multi-stage auction algorithm employed in the present invention is a flow chart, detailed as follows:
in S201, when a task occurs, a proxy robot for each task point is determined, and a robot closest to the task point j is selected as a proxy robot for the task point j.
The workflow of the agent robot is shown with reference to fig. 3, and is detailed as follows:
after receiving the message of the monitoring system, the robot i (i is 1,2, …, M) closest to the task point j (j is 1,2, …, N) is the proxy robot of the task point, the robot i first knows the task specific information of the task point j and sorts the task specific information, mainly calculates the optimal number s of robots required for completing the task j and obtains the change rate α of the task pointjThe task state quantity of the task point, the geographic position of the task point and the like. And then sending auction information to the auction robots within the communication radius to wait for feedback. And the auction robots receiving the auction information select the task points with the highest profit to bid according to the profit functions of the auction robots, the agent robot selects the auction robots winning the bid with the highest overall benefit as the target, and notifies all the bidding auction robots. And if the number n of the landmark robots reaches the condition that n is larger than s, selecting s robots with top profit ranks, and reselecting the task points closest to the landmark robots.
In S203, the auction robot workflow refers to fig. 4, which is detailed as follows:
if the auction robot is not selected as the agent robot, the auction robot is automatically converted into the auction robot, and the agent robot firstly issues auction information to the auction robots within the communication radius to wait for feedback. The auction robot receiving the auction information selects the task point with the highest profit to bid according to the profit function of the auction robot, and the agent robot collects the bid information and selects the auction robot winning the bid with the highest overall benefit of the system as the target. And if the auction robot successfully wins the bid, starting to execute the task, and if the auction robot fails to win the bid, selecting to execute the nearest task point. And if the task point is completed, the idle robots are redistributed according to the current situation until the task is completed.
And generating a distribution scheme, starting to execute a task, optimizing the path by the robot through an A-Star algorithm in the process of traveling, reasonably avoiding collision with other robots and obstacles, and searching out the optimal collision-free path for the robot to reach a corresponding task point.
Once there are completed task points, there will be untargeted idle robots, and the system will re-auction them, resulting in a new allocation scheme until all task points in the environment are completed.
The robots cooperatively perform the task test.
The above-mentioned method of the improved auction algorithm (multi-stage auction algorithm) has M robots, N task points, and B obstacles. In that
(m is the number of robots performing task point j). In order to test the improvement of the auction algorithm in performing the dynamic task, the test was performed using a map having a length and a width of 300 grids, comparing the effects of the single-stage auction algorithm and the multi-stage auction algorithm.
Fig. 5 and fig. 6 are both test examples, in which the thick black small circle is a proxy robot, and therobot 3 is a communication blind area robot, specifically as follows:
fig. 5 is a simulation diagram of a test single-stage auction algorithm, whererobots auction robots robot 3 selects thetask point 1 with the closest execution distance for the robot with the communication blind area (which is not in the communication radius range of the proxy robot and cannot accept auction information issued by the proxy robot), the robot starts to execute the target task point after the task allocation scheme is generated, the auction is not carried out in the execution process, and once the task point is executed, the idle robot does not assist other robots to execute the unfinished task point.
Fig. 6 is a simulation diagram of a certain testing multi-stage auction algorithm, in which the initial allocation method is the same as the single-stage auction algorithm allocation method, and the multi-stage auction algorithm is characterized in that once there is a completed task point, there are targets-free robots, and the algorithm reallocates them, in the diagram, thetask point 1 is executed first, and the algorithm reallocates therobots
In order to verify the efficiency of the improved auction algorithm, 8 sets of test data were selected, the communication radius was set to 200 units, k1 is 1, k2 is 0.0025; the statistical results are shown in table 1.
Table 1 is a statistical table of test times
The simulation result is drawn into a line graph, as shown in fig. 7, the comparison result is carried out, after corresponding rules and dynamic revenue functions are introduced for the dynamic tasks, the overall effect of the robot for executing the dynamic tasks is greatly improved, and the effectiveness of the robot for the dynamic tasks adopting the improved multi-stage auction algorithm is proved through simulation tests.
Finally, the method of the present application is only a preferred embodiment and is not intended to limit the scope of the present invention. Any modification, equivalent replacement, or improvement made within the spirit and principle of the present invention should be included in the protection scope of the present invention.
Claims (9)
Translated fromChinese
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710015070.8ACN106875090B (en) | 2017-01-09 | 2017-01-09 | A Multi-robot Distributed Task Allocation Formation Method Oriented to Dynamic Tasks |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710015070.8ACN106875090B (en) | 2017-01-09 | 2017-01-09 | A Multi-robot Distributed Task Allocation Formation Method Oriented to Dynamic Tasks |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN106875090A CN106875090A (en) | 2017-06-20 |
| CN106875090Btrue CN106875090B (en) | 2020-05-08 |
Family
ID=59165639
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201710015070.8AActiveCN106875090B (en) | 2017-01-09 | 2017-01-09 | A Multi-robot Distributed Task Allocation Formation Method Oriented to Dynamic Tasks |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN106875090B (en) |
Families Citing this family (39)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109426560A (en)* | 2017-08-28 | 2019-03-05 | 杭州海康机器人技术有限公司 | Method for allocating tasks, device and computer readable storage medium |
| CN109426884B (en)* | 2017-08-28 | 2022-02-11 | 杭州海康机器人技术有限公司 | Distribution scheme determination method, device and computer readable storage medium |
| CN107657364A (en)* | 2017-09-06 | 2018-02-02 | 中南大学 | A kind of overloading AGV tasks towards tobacco plant material transportation distribute forming method |
| CN107479403A (en)* | 2017-09-14 | 2017-12-15 | 长春北方化工灌装设备股份有限公司 | Annular RGV semi-matter simulating systems based on virtual reality and run dispatching algorithm without sky |
| CN108009012B (en)* | 2017-12-14 | 2021-12-14 | 中南大学 | A multi-agent dynamic task assignment method based on task model |
| CN108416488B (en)* | 2017-12-21 | 2022-05-03 | 中南大学 | A dynamic task-oriented task assignment method for multi-intelligent robots |
| DE102017223717B4 (en)* | 2017-12-22 | 2019-07-18 | Robert Bosch Gmbh | Method for operating a robot in a multi-agent system, robot and multi-agent system |
| CN110309993B (en)* | 2018-03-27 | 2022-04-05 | 杭州海康机器人技术有限公司 | AGV task allocation method and device for automatic guided transport vehicle |
| DE102018207539A1 (en)* | 2018-05-15 | 2019-11-21 | Robert Bosch Gmbh | Method for operating a robot in a multi-agent system, robot and multi-agent system |
| CN108985580B (en)* | 2018-06-16 | 2022-09-02 | 齐齐哈尔大学 | Multi-robot disaster search and rescue task allocation method based on improved BP neural network |
| CN110618689B (en)* | 2018-06-20 | 2022-04-26 | 陕西师范大学 | A Negotiation and Cooperation Modeling Method for Multi-UUV System Based on Contract Net under Constrained Conditions |
| CN108873907A (en)* | 2018-07-11 | 2018-11-23 | 山东大学 | The cooperative control method of how incomplete humanoid robot patrol escort mission based on vector field |
| EP3605399A1 (en)* | 2018-07-31 | 2020-02-05 | Tata Consultancy Services Limited | Systems and methods for semantic knowledge based dynamic utility calculation |
| CN109254581B (en)* | 2018-08-10 | 2021-07-02 | 合肥哈工库讯智能科技有限公司 | AGV dolly intelligent operation regulation and control system based on running state analysis |
| CN109447471B (en)* | 2018-10-30 | 2021-03-23 | 北京理工大学 | Multi-robot multi-region collaborative search task allocation method |
| CN109919431B (en)* | 2019-01-28 | 2023-04-07 | 重庆邮电大学 | Heterogeneous multi-robot task allocation method based on auction algorithm |
| CN109886574B (en)* | 2019-02-20 | 2023-02-14 | 哈尔滨工程大学 | Multi-robot task allocation method based on improved threshold method |
| CN110046795B (en)* | 2019-03-01 | 2021-11-05 | 斯坦德机器人（深圳）有限公司 | Robot task assignment method and device |
| CN110162043B (en)* | 2019-05-17 | 2020-10-09 | 北京航空航天大学 | A cluster task assignment and control method under the constraint of simultaneous arrival of multiple target points |
| CN110362105B (en)* | 2019-06-17 | 2022-07-19 | 广州大学 | Sensor network wireless charging method based on multiple UAVs |
| CN110456633B (en)* | 2019-06-29 | 2022-06-14 | 西南电子技术研究所（中国电子科技集团公司第十研究所） | Airborne multi-platform distributed task allocation method |
| CN112184400B (en)* | 2019-07-03 | 2024-04-02 | 中南大学 | Heterogeneous multi-agent multi-stage distributed auction algorithm based on local information |
| CN112181608B (en)* | 2019-07-03 | 2023-10-31 | 中南大学 | A distributed allocation method for multi-point dynamic assembly tasks based on local information |
| CN110727272B (en)* | 2019-11-11 | 2023-04-18 | 广州赛特智能科技有限公司 | Path planning and scheduling system and method for multiple robots |
| CN112859887B (en)* | 2019-11-28 | 2022-06-14 | 中国科学院沈阳自动化研究所 | Multi-underwater robot autonomous task allocation method based on space-based center |
| CN111027875B (en)* | 2019-12-17 | 2023-09-26 | 鲁东大学 | A multi-robot task allocation method for intelligent warehousing based on adaptive task pool |
| CN111208815B (en)* | 2019-12-24 | 2023-03-31 | 浙江华睿科技股份有限公司 | Method for distributing a plurality of handling tasks to a plurality of automated guided vehicles and related device |
| CN111489049B (en)* | 2020-03-03 | 2022-07-05 | 北京理工大学 | A multi-agent distributed task assignment method |
| CN111461488B (en)* | 2020-03-03 | 2022-03-11 | 北京理工大学 | Multi-robot distributed collaborative task assignment method for workshop handling problem |
| US11440193B2 (en) | 2020-03-30 | 2022-09-13 | Wipro Limited | Method, device, and system for managing collaboration amongst robots |
| CN111680836B (en)* | 2020-06-06 | 2023-05-02 | 杭州电子科技大学 | A Distributed Multi-robot System Task Allocation Method for ST-SR Problems |
| CN111798097B (en)* | 2020-06-06 | 2024-04-09 | 浙江科钛机器人股份有限公司 | Autonomous mobile robot task allocation processing method based on market mechanism |
| CN112070383B (en)* | 2020-08-31 | 2022-04-12 | 北京理工大学 | Dynamic task-oriented multi-agent distributed task allocation method |
| CN114330978B (en)* | 2021-11-11 | 2022-08-09 | 深圳大学 | Air-ground robot task dynamic allocation method, storage medium and terminal equipment |
| US20230306334A1 (en)* | 2022-03-22 | 2023-09-28 | Rapyuta Robotics Co., Ltd. | Task assignment in autonomous mobile devices |
| CN115464645A (en)* | 2022-09-13 | 2022-12-13 | 达闼机器人股份有限公司 | Task execution method, device, equipment and storage medium |
| CN115903898B (en)* | 2022-11-17 | 2023-12-29 | 新疆送变电有限公司 | Unmanned aerial vehicle flight control method and device, electronic equipment and storage medium |
| CN116245257B (en)* | 2023-05-06 | 2023-09-12 | 季华实验室 | A multi-robot scheduling method and device |
| CN118952198B (en)* | 2024-08-13 | 2025-05-27 | 北京积加科技有限公司 | Robot control method, device, electronic device and computer readable medium |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8726278B1 (en)* | 2004-07-21 | 2014-05-13 | The Mathworks, Inc. | Methods and system for registering callbacks and distributing tasks to technical computing works |
| CN106155802A (en)* | 2015-03-30 | 2016-11-23 | 阿里巴巴集团控股有限公司 | Method for scheduling task, device and control node |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7584123B1 (en)* | 2004-04-06 | 2009-09-01 | Ticketmaster | Systems for dynamically allocating finite or unique resources |
| CN104166750B (en)* | 2014-06-18 | 2017-07-11 | 南京邮电大学 | Robocup based on weighting synergetic rescues collaboration method |
| CN105843227B (en)* | 2016-04-15 | 2018-10-23 | 上海大学 | A kind of multi-robot Cooperation of task based access control closeness dynamic adjustment surrounds and seize method for allocating tasks |
- 2017
- 2017-01-09CNCN201710015070.8Apatent/CN106875090B/enactiveActive
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8726278B1 (en)* | 2004-07-21 | 2014-05-13 | The Mathworks, Inc. | Methods and system for registering callbacks and distributing tasks to technical computing works |
| CN106155802A (en)* | 2015-03-30 | 2016-11-23 | 阿里巴巴集团控股有限公司 | Method for scheduling task, device and control node |
Non-Patent Citations (2)
| Title |
|---|
| Analysis of Dynamic Task Allocation in Multi-Robot Systems;Kristina Lerman 等;《International Journal of Robotics Research》;20060331;第25卷(第3期);第225-241页* |
| 知识化制造环境下的任务分配与动态控制策略;董昊;《中国博士学位论文全文数据库 工程科技Ⅱ辑》;20070815;第2007年卷(第2期);第C029-7页* |
Also Published As
| Publication number | Publication date |
|---|---|
| CN106875090A (en) | 2017-06-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN106875090B (en) | A Multi-robot Distributed Task Allocation Formation Method Oriented to Dynamic Tasks | |
| Liu et al. | Multi-agent reinforcement learning-based coordinated dynamic task allocation for heterogenous UAVs | |
| CN107168054B (en) | Multi-robot task allocation and path planning method | |
| Zhao et al. | A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario | |
| Shang et al. | A multi-population cooperative coevolutionary algorithm for multi-objective capacitated arc routing problem | |
| CN104408518B (en) | Based on the neural network learning optimization method of particle swarm optimization algorithm | |
| CN107657364A (en) | A kind of overloading AGV tasks towards tobacco plant material transportation distribute forming method | |
| CN103401939A (en) | Load balancing method adopting mixing scheduling strategy | |
| CN111798097B (en) | Autonomous mobile robot task allocation processing method based on market mechanism | |
| CN110717684B (en) | Task allocation method based on task allocation coordination strategy and particle swarm optimization | |
| CN110286588A (en) | An assembly line rebalancing optimization method considering energy consumption | |
| CN113033970A (en) | AUV cluster layered distribution method for large-scale tasks | |
| CN105373692B (en) | Cockpit man-machine function allocation method based on section Two-tuple Linguistic Information Processing | |
| CN110390490A (en) | Profit-based task allocation method for spatial crowdsourcing | |
| Miao et al. | A novel multimodal multi-objective optimization algorithm for multi-robot task allocation | |
| CN117592751A (en) | Task matching and allocation method for air-ground unmanned systems based on improved auction mechanism and pigeon swarm evolutionary algorithm | |
| CN112734127A (en) | Multi-AUV task allocation method based on dynamic ant colony labor division model | |
| Bekker | Applying the cross-entropy method in multi-objective optimisation of dynamic stochastic systems | |
| Gaggero et al. | When time matters: Predictive mission planning in cyber-physical scenarios | |
| CN108769105A (en) | A kind of scheduling system of knowledge services multi-task scheduling optimization method and its structure under cloud environment | |
| CN116089083A (en) | Multi-target data center resource scheduling method | |
| CN107329826A (en) | A kind of heuristic fusion resource dynamic dispatching algorithm based on Cloudsim platforms | |
| Wang | Intelligent warehouse multi-robot scheduling system based on improved A* algorithm | |
| CN117932934A (en) | A situation-based dynamic evaluation method for unmanned swarm collaboration effectiveness | |
| Bi et al. | Dynamic Weighted and Heat-map Integrated Scalable Information Path-planning Algorithm. |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |