CN102156660A

CN102156660A - Method for distributing tasks based on two-layer decomposition in multiagent system

Info

Publication number: CN102156660A
Application number: CN2011100907744A
Authority: CN
Inventors: 蒋玉俊; 孟海战; 徐媛; 周伟
Original assignee: Southeast University
Current assignee: Southeast University
Priority date: 2011-04-12
Filing date: 2011-04-12
Publication date: 2011-08-17

Abstract

In the task assignment method based on double-layer decomposition in the multi-agent system, the structure between the agents in the multi-agent system is a federated structure, that is, the system is composed of mesons and execution subjects, where the mesons are the subjects used to accept tasks ;Task assignment is as follows: after the intermediary accepts the task, it analyzes the associated structure of the task, decomposes the task at the first level according to a certain resource threshold, and decomposes the task into several closely related subtask group modules; then , each subject in the system feeds back subject information to the meson. The feedback information includes the subject’s resource and capability information and the result information of the subject’s processing task. The meson decomposes the task group according to the obtained information and assigns the task Solve for each subject. The execution time of the task can be effectively reduced, and the execution time of the task is close to the shortest execution time under the limitation of the execution capability of the multi-agent system.

Description

The method for allocating tasks that decomposes based on bilayer in the multiagent system

Technical field

The present invention relates to (Multi-Agents System) a kind of optimization method for allocating tasks that decomposes based on bilayer in the multiagent system, specifically be to utilize neutretto (Mediator) task to be carried out bilayer decomposition distribution according to the relational structure of task and the ability and the resource of main body (Agent), and then reduce the task execution time of multiagent system effectively, improve and carry out efficient.

Background technology

In the multiagent system, traditional Task Distribution Study on Problems mainly is with the subproblem after decomposing, and distributes to relatively independent main body according to certain rule and method, by finishing the work sharing out the work and help one another between the main body.Research contents comprises conflict how to avoid between the multiagent, reduce communication cost, improve aspects such as system's parallel processing capability, and model by improving these aspects and algorithm are realized the Task Distribution scheme optimized.But the distribution of task is inseparable with decomposing, and decomposition is the prerequisite of distributing, and different task decomposing schemes are to the Task Distribution important influence.Therefore, with the decomposition of task and distribution combine study Task Distribution more can the optimized distribution method, improve task executions efficient.

Find Yichuan Jiang﹠amp through retrieval to existing document; Jiuchuan Jiang is published in " IEEE Transactions On Parallel And Distributed Systems, VOL.20, No.5 (May 2009) " paper " Contextual Resource Negotiation-Based Task Allocation and Load Balancing in Complex Software Systems " in (IEEE parallel with distributed system journal the 20 volume fifth phase) Task Distribution and the load balancing of sight resource negotiation (in the complicated software system based on), this article has proposed a kind of Task Distribution scheme based on main body (Agent) sight resource, when Task Distribution, not only consider resource and ability that main body self is had, consider that also main body associated therewith is the resource and the ability of the main body in its sight environment, its process is before the Task Distribution, at first detect the resource and the ability of main body, the resource of main body and ability can not satisfy mission requirements, detect the resource and the ability of related with it main body, the task that is incorporated into is handled in the main body array, until satisfying mission requirements, carry out Task Distribution according to the resource and the ability of main body group in the sight environment then; Simultaneously, overweight for fear of the main body load with high sight resource and ability, this paper proposes after the main body of the type obtains certain task, and its sight resource and ability can be cut down, and satisfy the load balancing requirement during Task Distribution to greatest extent.Also find James Guo Ming Fu﹠amp by retrieval; Tirthankar Bandyopadhyay ﹠amp; Marcelo H. Ang Jr is published in " 2009 IEEE International Conference on Robotics and Automation (May 12-17,2009) " paper " Local Voronoi Decomposition for Multi-Agent Task Allocation " (the local Thiessen polygon decomposition algorithm in the multiagent Task Distribution) in (2009 IEEE robots and robotization international conference), this article proposes the decomposition algorithm that a kind of local message according to main body is determined the Thiessen polygon zone of main body, the approaching as theoretic optimal solution of its optimization degree in search problem.

Yet, though above-mentioned paper all provides the optimisation strategy that is used for that task is decomposed or distributes, not with the decomposition of task with distribute the optimization process scheme that combines the task of research.Promptly most at present researchs relevant for Task Distribution are confined to the distribution of task or decompose single aspect, and the research of decomposition being included in the Task Distribution strategy does not also have concrete research approach.

Summary of the invention

Technical matters:The objective of the invention is at above-mentioned the deficiencies in the prior art, a kind of method for allocating tasks that decomposes based on bilayer in the multiagent system is proposed, in the method, version in the multiagent system between the main body is the federal style structure, be that system is made of neutretto and executive agent, this characteristic feature of an invention is that the decomposition of task and distribution are combined as the optimization of probing into the Task Distribution strategy, avoids studying respectively the deficiency of decomposing and dividing timing to occur.

Technical scheme:The present invention is achieved through the following technical solutions, and this method may further comprise the steps:

Step 1, after task was accepted by neutretto, neutretto at first traveled through the relational structure of task, writes down required resource in each subtask and the association between the subtask, relational structure according to the subtask is decomposed into a series of subtasks module with task, finishes first floor task and decomposes; By the adjustment of resource threshold in the module of control subtask, the size of control subtask module;

Step 2, main body in the system is to neutretto feedback resource and ability information separately, the type of the abstract subtask that can handle for main body and each are handled the number of subtask constantly, the subtask result that neutretto was once handled each main body has record, evaluation as this main body sincerity degree, the sincere degree that has according to the feedback information and the neutretto of main body decomposes task, take all factors into consideration the be untreated load balancing of subtask module and the subtask module that is about to be assigned with of each main body simultaneously, finish the sublevel task and decompose.

In the step 1, described resource threshold is by being assigned to total the resource kind and the quantity of the subtask in the module, and promptly how many subtask module resources comes the control module size, rather than comes the control module size with the quantity of subtask in the module.

In the step 2, described load balancing is that certain finishes last neutretto constantly when the load of assessment main body, not only consider untreated load on the main body, also consider to be about to be assigned to of the load of the subtask modular belt of main body to main body, take all factors into consideration the load of each two aspect of main body, can carry out the main body of this subtask module for the overall load minimum following subtask module assignment constantly.

The decomposition of sublevel task is to carry out on the basis that first floor task is decomposed, and according to main body resource in the multiagent system and ability the subtask module that does not satisfy the task solving requirement is decomposed once more in sublevel decomposes.

So-called neutretto is meant the coordination main body that is used to handle each main body association in decomposition;

The resource that so-called subtask is required is meant kind and the quantity of finishing the subtask resource requirement,

The subtask is finished in expression

Need k resource

;

Association between the so-called subtask is meant the preceding sequence task and the follow-up task of the subtask that is traveled through, and preceding sequence task refers to the subtask, upper strata with the subtask direct correlation, and follow-up task refers to the lower floor subtask related with the subtask;

So-called resource threshold is meant the maximum number of all resources in the subtask module that is decomposed.Go control module size Billy more to help objective judgement with contained resource sum in the module and be used for the processing module task executions time with subtask number control module size in the module;

The concrete technical scheme of this step is: after task was accepted by neutretto, neutretto traveled through the task relational structure, and traversing result is recorded in two-dimensional array

, wherein

,

Be respectively applied for and deposit the subtask

Preceding sequence task and follow-up task, Deposit and handle the subtask

Required resource is carried out the first floor according to the result of traversal to task and is decomposed, and the condition that is used to control decomposing module is: The subtask Arbitrary before sequence task Number

The number of resources of subtask module Limit threshold value greater than module

The process flow diagram of decomposition algorithm as shown in Figure 3.

After the relational structure of neutretto by task decomposes the task first floor, original task is decomposed into several degrees of association subtask module more closely, multiagent system is when handling these modules, can reduce the degree of association effectively is assigned to the communication that produces when different main body is handled and expends in the subtask closely, especially when the task scale was huger, the minimizing that communication expends was more obvious.

The concrete method of step 2 is as follows:

Have individual

The multiagent system of individual executive agent is handled to be had

Type

The ancestral task that individual subtask constitutes, ancestral task is broken down into after step 1 is decomposed

Individual sub-task module,

The execution time of type subtask is

The executive capability of single main body is that the maximum number of energy subtasking in the unit interval is

, wherein,

Expression can be carried out

Of type subtask

Individual main body;

In the module of subtask

Total number of type subtask is used

The expression (r=1,2,, m;

=1,2,,

).So, the multiagent system required maximum execution time of finishing the work is

, promptly

Total number of every type of subtask multiply by the summation of the unit execution time of carrying out the type subtask divided by system to total executive capability of this kind task in the individual sub-task module, in the case

Individual sub-task module can not be by the multiagent system parallel processing; Multiagent system the shortest required execution time of finishing the work is

, at this moment

Individual sub-task module is handled by multiagent system simultaneously, and the execution time of general assignment is the execution time of the longest subtask module of required time; In view of the executive capability of each main body in the multiagent system, the actual general assignment execution time falls between, and the target of this invention is to make the execution time of general assignment farthest approaching under multiagent system executive capability restrictive condition

Each main body of task is in the load of moment t , wherein

Be last one not being performed of the task that constantly is assigned on the main body A,

For distributing to the subtask of this main body; The result of each main body subtasking of neutretto record promptly can think sincere reliable in the successful execution subtask as the sincere degree of each main body, and it is non-honest reliable to execute the task, and the sincere degree of each main body is

, the sincerity degree increases 1 when main body completes successfully a subtask, otherwise subtracts 1, thinks that when sincere degree is lower than 0 this main body do not have sincere degree, and neutretto is not distributed to body tasks.During original state, the sincere degree and the load of each main body are 0, neutretto distributes according to the resource and the ability antithetical phrase task module of main body, and at first the unique task of the executive agent of antithetical phrase task module or subtask is distributed, to not unique the distributing to of executive agent

Less relatively trusted main body, this moment

Be 0; First moment executed the task after the end, each main body is to the load and the execution result of neutretto feedback oneself in the system, the neutretto basis load and the execution result of each main body is this moment distributed to next task constantly of each main body, assigns the task to the main body that satisfies following three conditions:

Condition one: Minimum main body, wherein,

For the moment finishes also untreated subtask on the main body,

Be the subtask that to distribute;

Condition two: communication expends less, and same main body is distributed in the subtask in the module of promptly same subtask, if do not satisfy, the subtask module is decomposed again, distributes according to condition one;

Condition three: sincere degree is higher, satisfy condition one and the basis of condition two on distribute to the higher main body of sincere degree;

The process flow diagram of decomposition algorithm as shown in Figure 4.

On the basis of above-mentioned two-layer decomposition, draw the method for allocating tasks that decomposes based on bilayer, its process flow diagram is as shown in Figure 5.

According to the method for allocating tasks of this invention,, can reduce the untight subtask of the degree of association effectively and be assigned to the different communication that main body caused and expend by the decomposition of the first floor based on the task relational structure; Simultaneously, this is invented each and carries out the load evaluate that finishes constantly by the task of distributing and being about to be assigned with is brought each main body, under the prerequisite of efficiently executing the task, reduced task execution time effectively, thereby made execution time of general assignment approach the shortest execution time under the multiagent system executive capability restrictive condition.

Beneficial effect:Neutretto is the main body that is used to receive an assignment.In the task assigning process, be not only the prioritization scheme research of decomposed task being carried out Task Distribution, and the decomposition of task is considered in the Task Distribution process.The neutretto that receives an assignment in the system at first carries out the first floor according to the relational structure between the task to task and decomposes, and degree of association subtask relatively closely combines, and can reduce expending of the communication resource in the task processes so effectively; Secondly, the feedback information of each main body in the neutretto evaluation system, information comprises the task of the resource of main body and ability, main body carrying and to execute the task result's record of each main body, according to the feedback information of main body, the first floor is decomposed obtaining of task decompose.Wherein, the result that each main body is executed the task is for fear of not being assigned to task time and again by the resource of feedback and the main body of ability successful execution task as a factor of sublevel decomposition.

1, decompose by the first floor based on the task relational structure, the communication that has reduced effectively in the task assigning process expends, and especially effect is more obvious when the task scale is bigger;

The method of the calculating main body load that 2, on the basis of foundation main body resource and ability, proposes, this method is considered the executive capability of the existing task of main body and task to be allocated and main body, reduced the execution time of general assignment effectively, made actual execution time effectively approach the shortest execution time under the multiagent system executive capability restriction;

Description of drawings

Fig. 1 is the structure connection of subtask in the ancestral task and the example displayed map of resource requirement type;

Fig. 2 is the task processing power figure of main body in the multiagent system;

Fig. 3 is based on the first floor task decomposition process figure of subtask relational structure in the ancestral task;

Fig. 4 is based on the sublevel task decomposition process figure of execution environment;

Fig. 5 is based on the double-deck method for allocating tasks process flow diagram that decomposes;

Fig. 6 is the flowchart of the distribution method of decomposing based on bilayer among the embodiment;

The processing power of A2, A3 is respectively 1,1,2; Terminal task is meant the subtask of follow-up task at task relational structure noon among Fig. 3, With

Represent the contained total resource number of task in j sub-task module and this module respectively.

Embodiment

Below in conjunction with accompanying drawing embodiments of the invention are elaborated: present embodiment is being to implement under the prerequisite with the technical solution of the present invention; detailed embodiment and concrete operating process have been provided; but present embodiment is a simple case of the present invention to be used, and protection scope of the present invention is not limited to following embodiment.

Under the prerequisite that does not influence explanation content of the present invention, the main body in task and the multiagent system is done following simplification and setting:

(1) is used to control the resource threshold of subtask block size

=10, the scale of different tasks according to task changed;

(2) do not consider the difference of subtask type in an embodiment, the execution time of subtask is all identical, promptly is provided with

(3) ability of main body processing subtask is respectively in the system ,

, i.e. the maximum subtask number that can handle constantly in unit of main body;

(4) each main body can both be finished subtask module or the subtask that is assigned to, promptly

All constantly increase;

Above-mentioned setting does not influence summary of the invention, just more clearly sets forth the part simplification of doing in order to invent when the small-scale task is handled, when foundation the present invention handles actual task,

,

Character according to task itself is provided with, and

Handle the execution result information of feeding back behind the subtask according to main body, the sincere degree that changes each main body get final product ( Finish a subtask smoothly

) increase 1, otherwise subtract 1).

Step 1, the neutretto in Fig. 2 multiagent at first travels through task, determines the preceding sequence task and the follow-up task of each subtask, is respectively

,

,

,

,

,

,

,

By

For Can judge

Be terminal task, then will

Terminal task compose to , because

Be 1, promptly

(

) preceding sequence task have only

, will Be included into module

, because of

Non-powder task, and =4, i.e. subtask module In the subtask contain the resource sum, satisfy

So, will Tax is given , continuing the first floor and decompose, circulation is divided into task four sub-task modules at last successively, is respectively

,

,

,

, finished the decomposition of first floor task.The task of the first floor that the present invention is undertaken by the relational structure between the subtask is decomposed and has been reduced the subtask that is associated effectively be assigned to the very big communication cost of bringing when different subjects goes to carry out in the task assigning process, and what show in extensive task processes is apparent in view.

Step 2, what the task decomposition of the first floor was played in the process of whole Task Distribution is filtration, and the degree of association is filtered together the subtask more closely, expends thereby reduce communication effectively in the Task Distribution implementation.On the basis that the first floor decomposes, decompose once more according to the demand resource of task and the execution environment of multiagent system, the process flow diagram of decomposition as shown in Figure 4, detailed process is as follows:

In view of the difference of not considering the subtask type among the embodiment, the execution time of subtask all is provided with

, so,

Can be reduced to

Neutretto traversal main information at first distributes executive agent to have only one subtask, will

Affiliated subtask module

Distribute to main body

, the antithetical phrase task module travels through then, can handle

Main body have

, can handle Be main body

, can handle

Be main body

, can handle

Be main body

, calculate each main body this moment

, handle The time main body

Be respectively

, Distribute to Less

, at this moment With

Be respectively 1 and 2, and

Be zero, therefore will

Distribute to

(distribute to

Less main body), finish the Task Distribution in first moment, allocation result is shown in Fig. 6 (a), and multiagent system begins to carry out each subtask module; After constantly finishing, execution result information is fed back to neutretto, neutretto distributes the task of being untreated according to feedback information, by feedback information, to each main body

Estimate with sincere degree (executive agent of subtask is credible all the time),

, the subtask module assignment is given

Fig. 6 (a) is theoretic OPTIMAL TASK allocative decision, and Fig. 6 (b) is the Task Distribution result of the multiagent system under this invention, and as seen in this small-scale Task Distribution embodiment, the present invention can find the optimal distributing scheme of task effectively.

Yet, this invention is not limited to this embodiment, in large-scale Task Distribution process, the present invention carries out the load evaluate that finishes constantly by the task of distributing and being about to be assigned with is brought each main body at each, under the prerequisite of efficiently executing the task, reduced task execution time effectively, thereby made execution time of general assignment approach the shortest execution time under the multiagent system executive capability restrictive condition.

Task Distribution according to the present invention carries out can reduce the task executions time effectively, makes task executions the shortest execution time under multiagent system executive capability restrictive condition around, has improved task executions efficient largely; Simultaneously, in extensive task was handled, by the decomposition based on relational structure, the communication that can reduce effectively between each main body Processing tasks process expended.

Claims

1. a task assignment method based on double-layer decomposition in a multi-agent system, characterized in that the method comprises the following two steps:

Step 1: After the task is accepted by meson, meson first traverses the association structure of the task, records the resources required by each subtask and the association between subtasks, and decomposes the task into a series of subtasks according to the association structure of subtasks module to complete the task decomposition of the first layer; by controlling the adjustment of the resource threshold in the subtask module, the size of the subtask module is controlled;

Step 2. The subjects in the system feed back their resource and capability information to the meson, which is abstracted into the types of subtasks that the subject can handle and the number of subtasks that can be processed at each moment. The result has a record, as the evaluation of the integrity of the subject, the task is decomposed according to the feedback information of the subject and the integrity of the intermediary, and at the same time, the load balance of the unprocessed subtask modules of each subject and the subtask modules to be assigned is comprehensively considered. , to complete the sub-level task decomposition.

2. the method for assigning tasks based on double-layer decomposition in the multi-agent system according to claim 1, characterized in that in step 1, the resource threshold has been assigned to the total resource types and quantities of the subtasks in the module , that is, how much subtask module resources control the module size, instead of using the number of subtasks in the module to control the module size.

3. the task distribution method based on double-layer decomposition in the multi-agent system according to claim 1 is characterized in that in the step 2, the load balancing is that when the end meson evaluates the load of the main body at the end of a certain moment, not only The unprocessed load on the main body also considers the load brought to the main body by the subtask modules that will be assigned to the main body, comprehensively considers the loads of the two aspects of each main body, and assigns the subtask module at the next moment to the subtask module that can execute the subtask with the smallest overall load. The body of the task module.

4. the task distribution method based on double-layer decomposition in the multi-agent system according to claim 1, it is characterized in that, the sub-level task decomposition is carried out on the basis of the first-level task decomposition, in the sub-level decomposition according to the multi-subject The main resources and capabilities in the system decompose the subtask modules that do not meet the requirements of task solving.