Distributed blackboard decision-making framework for collaborative planning based on nested genetic algorithm

School of Electronics and Information,Northwestern Polytechnical University,Xi’an 710129,China

Distributed blackboard decision-making framework for collaborative planning based on nested genetic algorithm

Yaozhong Zhang*,Lei Zhang,and Zhiqiang Du

School of Electronics and Information,Northwestern Polytechnical University,Xi’an 710129,China

A distributed blackboard decision-making framework for collaborative planning based on nested genetic algorithm(NGA) is proposed.By using blackboard-based communication paradigm and shared data structure,multiple decision-makers(DMs)can collaboratively solve the tasks-platforms allocation scheduling problems dynamically through the coordinator.This methodology combined with NGA maximizes tasks execution accuracy, also minimizes the weighted total workload of the DM which is measured in terms of intra-DM and inter-DM coordination.The intra-DM employs an optimization-based scheduling algorithm to match the tasks-platforms assignment request with its own platforms.The inter-DM coordinates the exchange of collaborative request information and platforms among DMs using the blackboard architecture.The numerical result shows that the proposed blackboard DM framework based on NGA can obtain a near-optimal solution for the tasks-platforms collaborative planning problem. The assignment of platforms-tasks and the patterns of coordination can achieve a nice trade-off between intra-DM and inter-DM coordination workload.

distributed collaborative planning,blackboard,decision maker(DM),nested genetic algorithm(NGA).

1.Introduction

In the past decade,decision-making problems(e.g.tasksplatforms assignment problem)have obtained attention of manyresearchers[1–5].Theyhave broughtforwardmany good solutions include branch-and-bound,dynamic programming(DP),dynamic list scheduling(DLS),and local search techniques,e.g.pair-wise exchange(PWE)[6,7], but with the rapidly development of military science and technology,especially the information warfare battlefield the current solution cannot meet the demand for dynamic collaborative decisions[3,5].Now the dynamic tasks decision-makingproblem has becoming a hot issue for the researchers[8–12].The new concept not only emphasizes onstandardizedprocessesandmethods,centralizedassessmentandguidance,butalso onnetworkeddistributedplanning capabilities,and decentralized execution for assessing,planning and executing missions across a range of military operations.Since many real-world systems are distributed,using a distributed architecture is a natural and practical approach[1,3].The most important and signifi cant aspect in a distributed architecture is the coordination and communication among various elements in the network.And the Blackboard architectures are very suitable for this distributed system to achieve a common goal[13–15].

In order to study the coordination behavior among DMs and to mimic the collaborative planning processes in decision-making,we have developed a distributed blackboard decision-making framework for collaborative planning that dynamicallyallocates tasks-platformsscheduling (TPS)to accomplish mission objectives.This methodology combined with nested genetic algorithm(NGA)to maximize tasks execution accuracy,also minimize the weighted total workload of the DM,which measured in terms of intra-DM and inter-DM coordination workloads. The intra-DM employs an optimization-based scheduling algorithm to match the tasks-platforms assignment request with its own platforms.The inter-DM coordinates the exchange of collaborative request information and platforms among DMs using the blackboard architecture.

As we know,the problemof TPS is typicallyNP-hardin its general form[1,3,4,16,17].The commonly used methodsincludebranch-and-bound,DP,DLS,localsearchtechniques,group technology,and heuristic algorithm,genetic algorithm(GA)[8,10–12,18,19].Among these methods, the DLS method find the asset-task allocation and mission schedule by sequentially assigning tasks to assets until task set is exhausted.The group technology using an optimization-basedschedulingandM-bestassetallocationalgorithm is used to generate asset packages by matching the task requirements and asset capabilities.The GA utilizes stochastic search techniques based on the mechanism of natural selection and genetics.Many works have established that GA is one of the most widely used approaches for solving the clustering problems with various objectives and constraints.

In recent years,a number of researchers combined GA with stochastic local search or other techniques to increase the efficien y of GA by reducing their search space.Some authors also employed double-loop or NGA approaches to solve the problem[20,21].At the same time,blackboard architectures are used to integrate multiple heterogeneous sources of knowledge.It can be used in solving complex problems in a wide variety of domains and provides encapsulation of knowledge from the various independent knowledge sources participating in the coordination process[22].Thus in this paper,we combine the blackboard architectures and NGA to provide a distributed decisionmaking framework for the TPS problem.

2.Blackboard decision-making framework

2.1Definition

(i)DM

A DM can be considered as a combat unit that has the ability of information collection,processing,decisionmaking and operational capabilities that can control the necessary resources to execute tasks[23].The functional model of DM is shown in Fig.1.

Fig.1 Functional model of DM

(ii)Blackboard

The blackboard is an asynchronous entity for information collection and processing.It is a central information repositoryenablingcoordinationbetweenDMs.To participate in the coordination process,the DMs share information throughthe global workspaceand respondto the timebased trigger mechanism of the blackboard[12,24].

(iii)Coordinator

A coordinator is a software agent with information processing and decision-making abilities that can control the shared assets to execute mission tasks and enable collaboration and negotiation among peer DMs.The coordinator plays the role of an agent who supervises and manages the blackboard,and allocates shareable assets to those tasks listed on the blackboard.The coordinator allocates assets to tasks based on the allocation’s impact on the entire mission plan.

(iv)Task

A task,which is derivedfrommission decomposition,is an activity that requires relevant resources provided by the DM’s assets.The tasks are carried out by a DM or a group of DMs under certain mission objectives.

(v)Asset

An asset is a physical entity with given resource capabilities and is used to process tasks.In this paper an asset referres to a platform.

2.2Blackboard decision-making architecture

Blackboard is used to exchange platforms and tasks information,at the same time it can be used to trigger signal for collaborative planning request for platforms.The blackboard decision-making architecture let the DMs collaborate with each other to accomplish tasks by computing in parallel and distributed,and also can manage the communicationand knowledgeconversionbetween DMs.This architecture is applied to distribute planning and collaborative process.The architecture is depicted as Fig.2.

Fig.2 Blackboard decision-making architecture

2.3Blackboard decision-making process

The coordinator decomposes the mission into tasks,andassignsthetaskstoDMs.TheneachDMupdatestheblackboard with the task information and dynamic task status. The blackboard allows the collaborating DMs to access the task information and status received from individual DMs based on a time-based trigger mechanism and allows DMs to updatethe shareableplatformsinformationandthe platforms status on the blackboard.The blackboard also triggersthe coordinationprocessby allowingthe coordinator to access the received tasks and platforms information. The coordinator starts the collaborative task planning process using NGA,after assigningthe platformto the coordinatedtasks,then modifie the platformstatus if neededand updates the corresponding DMs and broadcasts the taskplatform schedule[25,26].The coordinator then updates the task status on the blackboard based on the schedule.

The blackboard decision-making process is shown in Fig.3.

Fig.3 Blackboard decision-making process

3.Mathematical model

Here we give a modifie mathematical model that is given in[3].In order to formulate the problem mathematically, the following notations are introduced.

M:Total number of DMs;

L:Total number of the resource types;

Nt:Total number of tasks;

Np:Total number of platforms;

Ti:Indicate taski(i=1,2,...,Nt);

Pj:Indicate platformj(j=1,2,...,Np);

TD:Task-DM assignment matrix if taskiis assigned to DMm,TD(i,m)=1, else,TD(i,m)=0;

PD:Platform-DM assignment matrix if platformjis assignedto DMm,PD(j,m)=1,elsePD(j,m)=0;

TP:Task-platform assignment matrix if platformjis assigned to taski,TP(i,j)=1, elseTP(i,j)=0;

rt(i,l):Task-resource requirement matrix;

rp(j,l):Platform-resource capability matrix;

(xT(i),yT(i)):Location ofTi;

V(j):Velocity of platformj.

3.1 Intra-DM workload

SupposeT?mis the tasks set assigned toDMm,P?mis the platforms set assigned toDMm.The intra-DM platform for performingTi(Ti∈T?m)is

(i)Geographical location center ofDMm

(ii)Distance betweenPjandTjinsideDMm

(iii)Accumulated transfer delay for executingTiinsideDMm

(iv)Accumulated accuracy for executing tasks insideDMm

The remaining resourceslrequest forTiwhen performingand the total satisfie resourceslrequest before

Total number of resources to performTifor the platforms insideDMmis

The satisfaction degree of the platform resourcesltoTiinsideDMmis

Thus we can defin the task execute accuracy(TEA)for intra-DM as

(v)Taskaccuracysignificanc(TAS)forintra-DMis define as

whereρ1is the TAS index(TASI)for intra-DM workload. Then we can get the intra-DM workload forDMmas

3.2Collaborative workload of inter-DM

IfTicannot be completely performed byDMm,thenTineed to be collaborative by inter-DM through the blackboard.Here we defin the platform transfer timet(i)and inter-DM platform set

(ii)The transfer time delay forTiinter-DM is

(iii)The task accuracy of taskTican be updated as

Total inter-DM residual resource request is

The remaining resourceslrequest forTiperformingPjcan be updated asand the total satisfie resourceslrequest beforePjcan be updated as

The actual executed resourceslrequest whenTiis performed in inter-DM is

(iv)TAS for inter-DM can be define as

whereρ2is the TASI for inter-DM workload.

(v)The inter-DM workload forDMmis

3.3System total workload ofDMm

So far,we can defin the formula of system total workload forDMmas

whereWIntrais the intra-DM coordination workload ofDMm,WInteris theinter-DMcoordinationworkload,andαis the weight assigned to the intra-DM workload.

Our objection is minimizing the total workload of the system,so we seek to minimizethe root meansquare value of the system workload,which is given by

4.NGA solution

The problem formulated above is a combinatorial optimization problem and is generally nondeterministic polynomial time NP-hard.Therefore,in order to avoid falling into local minima,we employ the NGA to solve the taskplatform schedule problem.The NGA consists of two loops,namely:the outer-loop GA(OLG)and the innerloop GA(ILG).

(i)OLG

The OLG seeks to fin an optimal or near-optimal task-platform schedule,such that both the intra-DM and inter-DM workloads are minimized.For this task-platform schedule problem,in the representation of a chromosome, an integer alphabet{1,2,...,M}is employed,also the task and platform should be considered simultaneously. Therefore,the representation is given by a 1×(Np+Nt) vector.In order to avoid the optimal chromosome was destroyed in the process of genetic evolution,we select the method of multi-parameter cross coding[27–29].For an eight tasks and seven platforms problem,the chromosome is coding as

(ii)ILG

The ILG is responsible for findin the platform-task assignment and evaluating intra-DM and inter-DM workloads,given the task-platform schedule provided by the OLG.

We use a binary chromosome contains genes.Each gene stands for the assignment status of platform to task [30,31].If its value is“1,”it indicates that the platform has been allocated to the task.For example,for the eight tasksandsevenplatformsproblem,thechromosometaking the form{TP(1,1),TP(1,2),TP(1,3),...,TP(2,1),TP(2,2),...,TP(7,8)}indicates the platform–task assignment.

The fl w chart of the NGA in our research is shown in Fig.4.

5.Performance measures

There are many indexes to evaluate the task-platform schedule problem.Here we defin the task execution efficien y to evaluate the performance of our solution.

TheplatformtransfertimefortaskTiperformedbyplatformPjis

Fig.4 Flow chart of NGA algorithm

In order to simplify the question,we ignored the task executive time and only considered the platform transfer time.Thus the time needed to complete the task depends on the maximum platform transfer time.

Therefor the maximum platform transfer time for taskTiis

Here we use the ratio of actual resources used to total resources needed to indicate the task execution ratio.Thus the task execution ratio is

The task execution efficien y is define by

6.Simulation and results

In the scenarioconsideredhere,thereare eight tasks,seven platforms and four DMs.The following are some asset constraints:(i)One platform can only be assigned to one task at any given time;(ii)The platform once committed to a task remains with that task until the task is finished Table 1 shows the initial parameters for our scenario.

Table 1 Initial parameters

As we know,in the total workloads formulaαis the weight assigned to the intra-DM workload.Because the inter-DMworkloadis morecostlythantheintra-DMworkload,so the value ofαshould be less than 0.5.In the simulation,we can adjust the workloads between intra-DM and inter-DM by selecting differentαvalue.The smaller ofα, the more tend for the task to be performed by intra-DM and vice versa.We compare the optimal solution value by using differentαin the simulation.The result is shown in Fig.5.

Fig.5 Evolution curve of NGA with differentα

Table 2 Task execution efficienc

In the simulation,we change the value ofαfrom 0.001 to 0.9 to test its influenc on the performance of NGA. From Table 2,we note that whenα=0.1 the algorithm achieves the best result.This implies that,whenα=0.1 the system workload is much better balanced among the DMsthanthatwhenαequalsothervalues.Ifαis toosmall (e.g.0.001),the task-platform schedule tends to produce less numberof DMs in order to reduce the inter-DM workload;ifαis large(e.g.0.9),the minimization of inter-DM coordination workload is not guaranteed.Thus in order to get a reasonably balanced workload results we chooseα=0.1 in our simulation to generate the optimal solution. The simulation result is shown in Table 3.

Table 3 Task-platform assignment solution

We can see from the solution that tasks(T2,T3,T5,T6,T7)can be performedby the DM self.While the tasks(T1,T4,T8)cannot be performed by the DM itself,they need to request coordinationwith other DMs.The task-platform assignment is a feasible optimal solution.

7.Conclusions

In this paper,we propose a distributed blackboard decision-making framework for collaborative planning based on NGA.First we construct the task-platform allocation decision-making framework based on blackboard mechanism.The blackboardarchitecturecan makethe collaborate process among DMs convenient and efficient In order to balance the intra-DM and inter-DM coordination workloads,we adopt the NGA to obtain a near-optimal solution for this special two loop questions.We can influ ence the solution by using differentαvalues.The numerical result shows that the proposed distribute blackboardDM frameworkbasedon NGA approachcan obtaina nearoptimal solution for the task-platform collaborative planning problem.Whenα=0.1,the assignment of taskplatform and the patterns of coordination can achieve a nice trade-off between intra-DM and inter-DM coordination workload.

[1]S.Mandal,H.Xu,D.L.Kleinman.Agent-based distributed framework for collaborative planning.Proc.of the IEEE Aerospace Conference,2010:1–11.

[2]F.L.Yu,F.Tu,K.R.Pattipati.Integration of a holonic controlarchitecture andmulti-objectiveevolutionary algorithm for fl xible distributed scheduling.IEEE Trans.on Systems,2008, 38(5):1001–1017.

[3]J.L.Posadas.Agent-based distributed architecture for mobile robot control.Engineering Applications of Artificia Intelligence,2008,21(6):805–823.

[4]M.S.Vassiliou.The evolution towards decentralized C2.Proc. of the 15th International Command and Control Research Technology Symposium,2010:22–24.

[5]M.Indiramma,K.R.Anandakumar.Collaborative decision making framework for multi-agent system.Proc.of the International Conference on Computer and Communication Engineering,2008:1140–1146.

[6]C.Meirina,G.M.Levchuk,K.R.Pattipati.A multi-agent decision framework for DDD-III environment.Proc.of the 8th International Command and Control Research Technology Symposium,2003.

[7]T.L.James,E.C.Brown,K.B.Keeling.A hybrid grouping genetic algorithm for the cell formation problem.Computers&Operations Research,2007,34(7):2059–2079.

[8]H.Bui,X.Han,S.Mandal,et al.Optimization-based decision support algorithms for ateam-in-the loopplanning experiment.Proc.of the IEEE International Conference on Systems,Man and Cybernetics,2009:4684–4689.

[9]X.Han,S.Mandal,K.R.Pattipati.An optimization-based distributed planning algorithm:a blackboard-based collaborative framework.IEEE Trans.on Systems,Man,and Cybernetics, 2014,44(6):673–686.

[10]Y.Y.Sun.Research on multi-agent intelligent decision support system based on blackboard.Advances in Automation and Robotics,2011,122(1):197–206.

[11]S.W.Brett.Distributed algorithms for resource allocation problems.Proc.of the 17th International Command and Control Research Technology Symposium,2012.

[12]F.Rossi,M.Pavone.On the fundamental limitations of performance for distributed decision-making in robotic networks.Proc.of the 53th IEEE Conference on Decision and Control, 2014.

[13]E.Elbeltagia,T.Hegazyb,D.Grierson.Comparison among fve evolutionary-based optimization algorithms.Advanced Engineering Informatics,2005,19(1):43–53.

[14]Y.P.Wang,X.Y.Li,J.Tian.Blackboard mechanism based genetic algorithm for dynamic deployment of mobile sensor networks.Proc.of the International Conference on Electronic&Mechanical Engineering and Information Technology,2011: 2796–2799.

[15]G.Shroff,S.Sharma,P.Agarwal,et al.A blackboard architecture for data-intensive information fusion using localitysensitive hashing.Proc.of the 14th International Conference on Information Fusion,2011:1–8.

[16]S.Y.Tu,A.H.Sayed.Distributed decision-making over adaptive networks.IEEE Trans.on Signal Processing,2014,62(5): 1054–1069.

[17]M.P.Behbahni,S.Khaddaj,I.Choudhury.A novel distributed multidimensional management approach for modeling proactive decision making.Proc.of the 12th International Symposium on Distributed Computing and Applications to Business, Engineering&Science,2013:181–185.

[18]K.Choudhary,G.N.Purohit.A multi-objective optimization algorithm for uniformly distributed generation of test cases.Proc.of the International Conference on Computing for Sustainable Global Development,2014:455–457.

[19]S.H.Huang,P.C.Lin,H.I.Chan.A nested genetic optimization algorithm for the capacitated facility location problem.Proc.of the International Conference on Industrial Engineering and Engineering Management,2010:2105–2109.

[20]L.H.Tang,C.Zhu,W.M.Zhang,et al.Robust mission planning based on nested genetic algorithm.Proc.of the 4th International Workshop on Advanced Computational Intelligence, 2011:45–49.

[21]F.L.Yu,F.Tu,K.R.Pattipati.A novel congruent organizational design methodology using group technology and a nested genetic algorithm.IEEE Trans.on Systems,2006, 36(1):5–18.

[22]X.Han,S.Mandal.An optimization-based multi-levelasset allocation model for collaborative planning.Proc.of the 16th International Command and Control Research Technology Symposium,2011.

[23]S.A.Petersen,P.Sriram,J.Krogstie,et al.A collaborative planning,information and decision support system.IFIP Advances in Information and Communication Technology,2013, 408(1):295–302.

[24]S.Acharya,A.Dutta.Coordination ontology for multi agent based distributed decision making.Proc.of the 2nd IEEE International Conference on Parallel Distributed and Grid Computing,2012:508–514.

[25]D.Scheidt,K.Schultz.On optimizing command and control structures.Proc.of the 16th International Command and Control Research Technology Symposium,2011.

[26]M.Gaha,M.Gagnon,F.Sirois.A modern blackboard system.Proc.of the IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology,2011: 163–166.

[27]M.Gen,A.Syarif.Hybrid genetic algorithm for multi-time period production/distribution planning.Computer and Industrial Engineering,2005,48(4):799–809.

[28]K.Yasuda,L.Hu,Y.Yin.A grouping genetic algorithm for the multi-objective cell formation problem.International Journal of Production Research,2005,43(4):829–853.

[29]T.Tunnukij,C.Hicks.An enhanced grouping genetic algorithm for solving the cell formation problem.International Journal of Production Research,2009,47(7):1989–2007.

[30]I.Mahdavi,M.M.Paydar,M.Solimanpur,et al.Genetic algorithm approach for solving a cell formation problem in cellular manufacturing.Expert Systems withApplications,2009,36(3): 6598–6604.

[31]C.Feng,L.Liu,S.Burns.Using genetic algorithms to solve construction time-cost trade-off problems.Journal of Computing in Civil Engineering,1997,11(3):184–189.

Biographies

Yaozhong Zhangwas born in 1974. He received his Ph.D.degree in system engineering from Northwestern Polytechnical University, Xi’an,China,in 2006.Now he is an associate professor at School of Electronics and Information in Northwestern Polytechnical University.His research interests include modeling,simulation and effectiveness evaluation of complex systems, decision-making,command and control system.

E-mail:zhang y z@nwpu.edu.cn

Lei Zhangwas born in 1992.She received her B.E.degree in Department of Electronic Information Science and Technology from Northwest University,Xi’an,China,in 2013.Now she is a postgraduate in Department of Electronic Information from Northwestern Polytechnical University.Her current research interests include theories and methods of cooperative control for multiple UAVs, complex system modeling.

E-mail:973028876@qq.com

Zhiqiang Duwas born in 1983.He received his B.E.degree in Naval Aeronautical Engineering Institute,Yantai,China,in 2006.In 2014,he received his M.S.degree in the School of Electronic and Information,Northwestern Polytechnical University. Now he is an engineer in Unit 92768 of the PLA and his research concern is C4ISR.

E-mail:xiaobaofadai@163.com

10.1109/JSEE.2015.00136

Manuscript received Augst 27,2014.

*Corresponding author.

This work was supported by the National Aerospace Science Foundation of China(20138053038)and the Graduate Starting Seed Fund of Northwestern Polytechnical University(Z2015111).