# Multiagent Task Planning Based on Distributed Resource Scheduling under Command and Control Structure

Authors: Jie Zhang; Gang Wang; Yafei Song; Fangzheng Zhao; Siyuan Wang
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

For task planning of the command and control structure, the existing algorithms exhibit low efficiency and poor replanning quality under abnormal conditions. Given the requirements of the current accusation architecture, a distributed command and control structure model is built in this paper based on multiagents, which exploits the superiority of multiagents in achieving complex tasks. The concept of MultiAgent-HTN is proposed based on the framework. The original hierarchical task network planning algorithm is optimized, the multiagent collaboration framework is redefined, and the coordination mechanism of local conflict is developed. With the classical resource scheduling problem as the experimental background, the proposed algorithm compared with the classical HTN algorithm is drawn. According to the experimental results, the proposed algorithm exhibits higher quality and higher efficiency than the existing algorithm and the space anomaly is significant in the course of processing. The planning is more efficient and the time is more complicated and superior in solving the same problem, and the algorithm exhibits good convergence and adaptability. In the conclusion, it is proved that the distributed command and control structure proposed in this paper exhibits high practicability in relevant fields and can solve the problem of distributed command and control structure in a multiagent scenario.


---

## Body

## 1. Introduction

Nowadays, there are many methods for optimization of distributed programming, which are mainly divided into three types: numerical analysis method, heuristic algorithm, and hybrid algorithm. At present, the common numerical analysis methods include linear programming method, nonlinear programming method, branch exchange method, branch demarcation method, enumeration method, dynamic programming method, stochastic programming method, and fuzzy programming method [1]. The principle of numerical analysis method is relatively simple, and it has a high operability [2]. However, for the complicated distributed resource planning problem, it is impossible to obtain the satisfactory optimal solution by using only the numerical analysis method. At present, the common heuristic algorithms that scholars at home and abroad use to study the optimal solution of distributed resource planning include genetic algorithm, particle swarm algorithm, tabu search algorithm, ant colony algorithm, and immune clone algorithm. The heuristic algorithm can get the optimal solution to some extent, but in many cases, it cannot get an optimal solution, for example, when the genetic algorithm is calculated, all the alternatives are listed as a set, and then each scheme in the set is analysed, and the optimal solution is obtained through many operations, but the algorithm is prone to fall into prematurity and long-time operation of CPU. The particle swarm optimization (PSO) algorithm and genetic algorithm have similar characteristics to some extent, which is to find the set of all the options and then analyze and calculate each scheme to find the optimal solution. However, compared with the genetic algorithm, it is simpler, accurate, faster, and easier to implement to converge. In order to overcome the drawbacks of heuristic algorithm, to deal with the problem of complex distributed programming constraint model and to find the best solution, a hybrid algorithm is proposed. In the face of emergencies, a quick and effective command and control structure is indispensable. Feasible command and control structure is capable of generating the highest quality decision scheme at the fastest speed in the effective time and timely handle the temporal exception in the execution process of the scheme to ensure the smooth execution of the decision scheme. The multiagent technology [3], originated in the 1980s, has been widely used and become a hot topic in the field of distributed artificial intelligence. Distributed multiagent system shows its superiority and efficiency in dealing with complex tasks. The formation of alliance is the foundation of all the activities for alliance. As a hot research object, the construction of alliance [4] is an important research content. Therefore, how to form a balanced alliance and to make it develop in an expected direction has become one of the main issues in the artificial intelligence research.For the particularity of the emergency response, the accusation architecture is characterized by large scale, hierarchical decision-making, complex cooperative relationship, and robust spatio-temporal constraint as well as complex external situation [5].


### 1.1. Large Scale

There are considerable participating units involved in emergency response, with considerable tasks to be completed [6], numerous types, and plenty of resources to rely on. The relationship and element connotation of the mentioned problems should be considered when making a decision plan, thus leading to a large scale of command and control.


### 1.2. Hierarchical Decision-Making

Under complex requirements for solution, i.e., input complex tasks, the task is decomposed layer by layer, several simple tasks are decomposed, and the task is processed according to the concept of multiagent system. Following this principle, the decision-making process requires certain empirical knowledge and rules [7].


### 1.3. Complex Cooperative Relationship

In the execution of the decision scheme, there are complex dependencies and time-space constraints among agents, and there also exist resource and time constraints between agents and tasks [8].


### 1.4. Robust Spatio-Temporal Constraint [9]

The longer the time consumption, the more serious the loss of people’s property will be. Accordingly, the constraint on the generation time of task processing scheme is extremely robust, requiring the generation of high-quality decision-making tasks in a short time.


### 1.5. Complex External Situation

In the execution of the decision scheme, the change trend of the external situation environment cannot be predicted. Environmental factors affect the implementation result of the decision scheme, thus easily leading to the unenforceability of the scheme. Thus, the generation of decision plans is required to be consistent with the change of external situation.In brief, the generation of decision-making schemes for complex task planning has led to great difficulty. Conventional mathematical modelling is not suitable for solving such problems for its slow solution speed, complex cooperative relationship, and spatio-temporal state constraints. Besides, conventional mathematical modelling schemes are usually used for solving static problems, and in the case of dynamic problems, it is necessary to remodel once the problems change [10]. Accordingly, the conventional modelling method has some limitations and cannot fit the solution of such problems [11].HTN (Hierarchical Task Network) planning is one of the most commonly used intelligent planning methods in the field of multiagent [12]. The basic process is to decompose complex tasks until they can be split into directly executable atomic-level tasks. After the decomposed tasks are achieved, task allocation is performed, and finally a decision scheme is yielded [13]. The HTN algorithm has the following advantages in solving such problems. First, the scheme is yielded quickly and can solve complex problems with robust constraints. Second, the existing empirical knowledge can be fully exploited. The HTN can efficiently use the existing method set and empirical knowledge to express various constraints to enhance the decision-making efficiency and improve the quality of the decision-making scheme. The HTN has been extensively used in robotics, feature modelling, emergency response decision-making, etc. The above discussion suggests that the HTN exhibits a good adaptability to the solution of the decision-making scheme of emergency problems [13]. Moreover, targeted optimization is conducted in this paper based on the HTN to solve the decision-making generation problem of distributed accusation architecture.In brief, the major contributions of this paper are as follows:(i)
A novel expression form, MultiAgent-HTN, is proposed, which expands the conventional HTN methods to express the time preference of the HTN. Preference information is expressed by preference function, which can express continuous preference.(ii)
The heuristic search algorithm is used to guide the planning direction in the MultiAgent-HTN, and three definitions of horizontal consistency are proposed to estimate the quality of the MultiAgent-HTN, which acts as heuristic information to assess the quality of operators or methods. Heuristic searches select appropriate operators or methods based on their ranks.


## 1.1. Large Scale

There are considerable participating units involved in emergency response, with considerable tasks to be completed [6], numerous types, and plenty of resources to rely on. The relationship and element connotation of the mentioned problems should be considered when making a decision plan, thus leading to a large scale of command and control.


## 1.2. Hierarchical Decision-Making

Under complex requirements for solution, i.e., input complex tasks, the task is decomposed layer by layer, several simple tasks are decomposed, and the task is processed according to the concept of multiagent system. Following this principle, the decision-making process requires certain empirical knowledge and rules [7].


## 1.3. Complex Cooperative Relationship

In the execution of the decision scheme, there are complex dependencies and time-space constraints among agents, and there also exist resource and time constraints between agents and tasks [8].


## 1.4. Robust Spatio-Temporal Constraint [9]

The longer the time consumption, the more serious the loss of people’s property will be. Accordingly, the constraint on the generation time of task processing scheme is extremely robust, requiring the generation of high-quality decision-making tasks in a short time.


## 1.5. Complex External Situation

In the execution of the decision scheme, the change trend of the external situation environment cannot be predicted. Environmental factors affect the implementation result of the decision scheme, thus easily leading to the unenforceability of the scheme. Thus, the generation of decision plans is required to be consistent with the change of external situation.In brief, the generation of decision-making schemes for complex task planning has led to great difficulty. Conventional mathematical modelling is not suitable for solving such problems for its slow solution speed, complex cooperative relationship, and spatio-temporal state constraints. Besides, conventional mathematical modelling schemes are usually used for solving static problems, and in the case of dynamic problems, it is necessary to remodel once the problems change [10]. Accordingly, the conventional modelling method has some limitations and cannot fit the solution of such problems [11].HTN (Hierarchical Task Network) planning is one of the most commonly used intelligent planning methods in the field of multiagent [12]. The basic process is to decompose complex tasks until they can be split into directly executable atomic-level tasks. After the decomposed tasks are achieved, task allocation is performed, and finally a decision scheme is yielded [13]. The HTN algorithm has the following advantages in solving such problems. First, the scheme is yielded quickly and can solve complex problems with robust constraints. Second, the existing empirical knowledge can be fully exploited. The HTN can efficiently use the existing method set and empirical knowledge to express various constraints to enhance the decision-making efficiency and improve the quality of the decision-making scheme. The HTN has been extensively used in robotics, feature modelling, emergency response decision-making, etc. The above discussion suggests that the HTN exhibits a good adaptability to the solution of the decision-making scheme of emergency problems [13]. Moreover, targeted optimization is conducted in this paper based on the HTN to solve the decision-making generation problem of distributed accusation architecture.In brief, the major contributions of this paper are as follows:(i)
A novel expression form, MultiAgent-HTN, is proposed, which expands the conventional HTN methods to express the time preference of the HTN. Preference information is expressed by preference function, which can express continuous preference.(ii)
The heuristic search algorithm is used to guide the planning direction in the MultiAgent-HTN, and three definitions of horizontal consistency are proposed to estimate the quality of the MultiAgent-HTN, which acts as heuristic information to assess the quality of operators or methods. Heuristic searches select appropriate operators or methods based on their ranks.


## 2. Related Research

In the field of emergency problem solving network analysis, based on enhancing the efficiency of decision-making schemes, researchers analysed them from different perspectives. Jackson et al. built FMECAN (Failure Mode Effects and Criticality Analysis Network) as the program analysis model to achieve the input and output ratios of different failure models. This built network significantly enhanced the reliability of the decision-making program generation system and up-regulated the resource allocation rate [14]. Pratyszek and Karagiannis modelled the decision-making scheme for local conflicts by building failure nodes into failure trees [15]. Moreover, Xiuhua et al. established vague meanings for grouping functions. To formulate the rule of conditioned, research on distributed decision is of great significance [16]. For multiagent systems with actuator faults, Xiuhua et al. proposed a novel design method of distributed intermediate observer, capable of simultaneously estimating the state and fault of the system. This proposed method was applied in systems with strictly positive and real conditions and unsatisfied observer matching conditions [16]. Given the Cyber Physical Systems (CPSs) with nonlinear coupling characteristics in attack, Ao presented a distributed safety measurement preselector to ensure that the state of the system was accurately estimated in a preset limited time. This researcher also developed a distributed finite time safety control algorithm to ensure that the system can track a given signal in a limited time [17]. Based on the environmental and situational awareness of the motion control system and the existing research results worldwide, Jian et al. highlighted the existing challenges and future research directions [18]. In another work, Fan et al. proposed a compound distributed inclusive control algorithm and a compound distributed integral sliding mode control protocol based on nonlinear integral sliding mode control and disturbance observer, respectively [19]. Dong et al. designed the event-triggering control mechanism based on the consistency of the third-order discrete multiagent system of event-triggering control. They provided the determination conditions for the event-triggering controller to exclude zeno-like behaviour [20]. For the linear heterogeneous multiagent system, a state and output feedback collaborative controller was designed, capable of effectively reducing the network communication load and the number of controller updates and achieving the multiagent system’s asymptotic tracking and interference suppression to the external system [21]. If the directed graph was strongly connected, Dongyue and Jie designed a distributed algorithm based on the disturbance observer to reach the consistency of the linear multiagent system with unknown disturbance [22]. Furthermore, Shiming et al. presented a novel event-triggered consistency control protocol with the state predictor. They demonstrated that the proposed event-triggered control strategy is capable of effectively achieving the average consistency under the combined connected topology using Lyapunov stability theory and algebraic graph [23]. The method to combine the average dwell time and the joint switching signal was employed to deal with the system instability caused by the delay of switching between the controller and the system mode. A switching control strategy based on output feedback was formulated [24]. Moreover, based on the universal consistency protocol of multiagent, Jun and Guoping developed the position time-varying consistency protocol of planar nonintegrity multiagent, which can effectively solve the general time-varying formation of the planar nonintegrity multiagent system [25]. Phuong et al. [26] proposed two methods to solve the problem following the d-relaxed priority rule. In this paper, the formulation construction exact solution proposed in the mathematical literature is improved. The metaheuristic approach based on the iterative local search framework also found approximate solutions the problem operator introduction. However, the major drawback of this method is that it cannot find the best solution and provide a solution that is stable and runs reasonably on a large instance.In the field of command and control structure modelling, Haoran, a domestic scholar, studied and designed the command information system. He proposed a command information system architecture based on the mobile cloud mode, which significantly optimized the utilization of computing resources of the command information system and further enhanced the realization efficiency of command and control [27]. Liping et al. proposed a preference vector guided coevolutionary algorithm for Many-Objective Optimization and compared ASF-PICEA-g with g-NSGA-II and r-NSGA-II on WFG and DTLZ benchmark test functions based on 3 to 20 dimension. The experimental results showed that ASF-PICEA-g exhibited good performance and better stability, and the obtained solution set had better convergence and distribution than other algorithms [28]. Furthermore, Jin introduced service-oriented thinking into the architecture design of the command and control information system, thus enhancing the information processing capacity of the command and control information system [29]. Hongming et al. proposed the C/S and B/S hybrid architecture, and then the system was separated from the business logic through the data access layer, so the database was completely transparent to the user. By running the RunProxy to connect the client and server, the security of the server was significantly improved [30]. Based on the hierarchical hierarchy and OODA control loop, He et al. proposed a four-layer command and control structure for the unmanned combat system based on cognition, ensuring the unity of command, the flexibility of control, and the scalability of the system [31]. Furthermore, Minglei proposed a temporal HTN planner TPHTN (time preference HTN) to process time constraints with preferences [32]. The planner expressed the time preference information using STNP (simple time network with preference) and expressed the time preference information in the planning domain knowledge by extending the operators and methods. In the planning process, TPHTN propagated STNP from top to bottom and three definitions of horizontal consistency were proposed to estimate the quality of STNP. Besides, a new heuristic search was designed to select appropriate operators or methods and corresponding STNP according to the quality. Lastly, TPHTN generated a plan that meets the decision maker’s preference when the planning terminates. Besides such benefits of this method, it neither expressed continuous preference nor used the heuristic search algorithm to guide the planning direction. Given the above information, it is speculated that the conventional modelling method is not suitable for the current command and control structure modelling requirements.In brief, this study proposes a new method MultiAgent-HTN based on the architecture, which can solve these problems well. Based on the current command and control domain requirements, a multiagent-based distributed command and control model architecture is built, the HTN algorithm is optimized, and the resource scheduling problem is taken as the experimental background. The algorithm in this paper is to be compared with the original HTN algorithm, TPHTN algorithm, FHTN algorithm, etc. The results of comparative experiments reveal that the proposed algorithm exhibits certain superiority and high convergence in solving problems for distributed cooperative task planning.


## 3. Design of Distributed Command and Control Structure Model Based on MultiAgent

According to the modelling requirement of command and control decision-making function, the agent structure block diagram of command and control model can be obtained as shown in the following Figure1:Figure 1
Block diagram of the command and control agent.The distributed command and control model [33] aims to optimize the utilization of alleged resources, deal with local contradictions in the command and control process, and reduce the complexity of the model structure while the mission requirements are satisfied. The following variables are defined based on the input task’s timing constraints, resource requirements, and other constraints. dim denotes the allocation variable of the command and control resource, tijm the resource transfer variable, oij the timing variable, K and N are the numbers of the resource planning of each party, respectively, assumed internal collaboration function In and external collaboration function En as the objective function, and Y is the time required for the completion of the input task. The purpose is to ensure that the objective function values of In and En are the minimum, thus making internal collaboration and external collaboration the least complex. The problem is expressed as follows:(1)s.t.∑i=0ntijm−dim=0;i=1,…,N;m=1,…,K∑i=0ntjim−dim=0;i=1,…,N;m=1,…,K∑i=0nti0m=∑j=0ntojm=1si−sj+tijm∗pijqm+oij∗T≤oij∗T−timei;i,j=1,…,N;m=1,…,K∑m=1Krml∗dim≥Ril;i=1,…,N;l=1,…,Nsi−Y≤−ti,i=1,…,N0≤Y≤Tsi≥0tijk∈0,1dik∈0,1.Then, the relevant mathematical description of the command and control model is the mixed element linear programming problem, i.e., the search problem of state space. Clustering analysis is conducted on the input tasks. Different tasks are assigned to different agents in accordance with the clustering results, and then the workload of agents is minimized. The following variables are defined:WI denotes the cooperation threshold within agents, WK is the cooperation threshold outside agents, the minimum load is set to minCw, and M and N are the value parameters of search space and the range of their values are 1,D:(2)s.t.∑m=1Dtmj=1ynmi≥dji∗xmj;m,n=1,…,D;i=1,…,N;j=1,…,Kynmi≥dji∗xnj;m,n=1,…,D;i=1,…,N;j=1,…,KCw≥WI∗∑m=1Dtnj+WK∗∑m=1,m≠nD∑i=1Nynmi;n=1,…,Dxnj,xmj∈0,1.Complex task processing determines the external collaboration threshold of the command and control centre. To deal with the collaboration among agents’ internal decision-making, the maximum external collaboration threshold between agents should be determined and the indirect collaboration threshold in command and control structure should be minimized, which is defined asminWmax. Define eij as direct connection variable, zijk as indirect connection variable, the internal collaboration function In represents the quantitative expression of the cooperative ability of each member within the unit, and external collaboration function En represents the quantitative expression of the cooperative ability and the cooperative efficiency among the units as follows:(3)s.t.∑i,j=1Deij=D−1;j=1,…,K∑j=0Dej0=0,∑j=0Deji=1;i=1,…,Dlj≥lj+1+eij−1D+1;i,j=1,…,Deij+eji+∑i=1nzijk≥dij;i,j=1,…,Deik+eki+ejk+ekj≥2∗zijk;i,j,k=1,…,DWmax≥WI+In+WE∗En+∑i<jzijncij;n=1,…,Deij∈0,1zijk∈0,1.


## 4. Optimization of Distributed Cooperative Task Planning Algorithms Based on HTN

In the process of command and control decision-making, the situation information of each agent cannot be fully shared, so agents should plan to maximize their own interests according to the local situation they have mastered. Given the above content, to avoid the interaction between agents, eliminate local conflicts or enhance resource utilization, the distributed cooperative task should be planned [34] to ensure the completion of the global task and the maximization of overall interests. For this end, this chapter primarily describes the cooperative relationship between distributed multiagents in the decision-making of command and control. Taking the task planning as the background, the multiagent cooperative mode and relationship network of command and control decision-making link are built.


### 4.1. Description of Basic HTN Algorithms

The HTN decision system has been extensively used in the planning system of AI field. The HTN represents the change of state following the concept of atomic operators, and a group of atomic operators represents a state. The basic principle of the HTN aims to generate a range of instruction actions based on a target or task and input the given problem domain or task (e.g., the initial test state of the process), and the state is the sequence of the ordered unfinished task set.


### 4.2. Parameter Definition

Definition 1.
HTN is expressed as a six-tupleU,I,C,A,T,Nwith extended presequence language. In the six-tuple, U denotes variable set, I constant set, C logical consistent set, A agent’s task action set, T task set, and N task identifier set. These sets are independent of each other.Definition 2.
State refers to the basic state list of agent, i.e., the atomic state list. If the value is not 0, the state will be true; otherwise, it will be 0.Definition 3.
Agent’s task action isAgent.fx1,x2,…,xk, where f∈F,x1,x2,…,xk is the action item. The prerequisites and prediction results should be declared.Definition 4.
The complex task isftx1,x2,…,xk.


### 4.3. Constraints

#### 4.3.1. Variable Constraint

(4)
v
1
=
c
v
1
=
v
2
,where v1,v2∈V denotes a variable identifier and c∈C c a constant identifier.


#### 4.3.2. Sequential Constraint

(5)
n
<
n
′
,where n,n′∈N. “<” denotes the logical sequential operator, i.e., the task content of n must be completed before the decision instruction of n′ task is generated.


#### 4.3.3. State Constraint

(6)
n
,
l
l
,
n
n
,
l
,
n
′
,
n and l are, respectively, the numbers of two agents performing tasks. n,l=1 indicates that l is executed after n; l,n=1 indicates that n is executed after l; and n,l,n′=1 indicates that l is executed between n and n′.


### 4.4. Analysis of Algorithm Flow

The HTN planning is instantiated and analysed, which is detailed as follows Algorithm1:Algorithm 1:HTN algorithm Pseudo Code.
(1)
HTNs,U,C,O,M
(2)
ifU,C can be shown to have no solution
(3)
Then return failure
(4)
else ifU is primitive then
(5)
ifU,C has a solution then
(6)
nondeterministically letπ be any such solution
(7)
returnπ
(8)
else return failure
(9)
else
(10)
choose a nonprimitive task nodeu∈U
(11)
active⟵m∈Mtaskmis unifiable withtu
(12)
ifactive≠∅ then
(13)
nondeterministically choose anym∈active
(14)
σ⟵ an mgu for m and tu that renames all variables of m
(15)
U′,C′⟵δσU,C,σu,σm
(16)
U′,C′ ⟵ apply-critic U′,C′
(17)
return HTNs,U′,C′,O,M
(18)
else return failureThe algorithm exhibits good convergence. As the iteration proceeds, the quality of the decision scheme generated by the algorithm becomes increasingly higher. The specific convergence function is presented as follows:The aim of the experiment is to prove that the algorithm has good convergence. In Figure2, the horizontal axis is the number of iterations and the vertical axis is the value of error loss. According to the simulation, the number of iterations is taken as the reference object and the error loss value as the criterion of convergence. The experimental results show that the error loss value decreases with the increase of iteration times, so the algorithm has good convergence.Figure 2
Function convergence curve.


### 4.5. Multiagent Distributed Collaboration Framework Based on HTN

Usually, in a centralized environment, the collaboration framework of MultiAgent-HTN (MultiAgent-Hierarchical Task Network Planning, MA-HTN) is to establish a decision-making centre, control the overall situation, and deduce and solve the scheme.However, in the actual command and control process, the overall situation sharing is difficult to achieve, and the security of a single decision-making centre cannot be ensured. Once the centre is destroyed, it loses the initiative of war. Thus, distributed MA-HTN exhibits higher superiority. Each agent deduces the scheme internally and does not share the relevant information with each other in the process of scheme deduction. Moreover, each agent should cooperate with the scheme that has dependency or mutually exclusive relationship to solve local conflicts to build a task planning collaboration network and maximize the overall interests. The cooperative task planning process framework of distributed MA-HTN is illustrated in Figure3.Figure 3
Distributed mission planning process for distributed MA-HTN.The cooperative task planning of distributed MA-HTN is based on the modification of the decision-making scheme. Cooperative relationship adjustment mechanism is introduced to integrate the process of decision-making adjustment and modification. Thus, the cooperative relationship control of decision-making actions is achieved in the planning process. The algorithm flow follows the original HTN planning framework and intermediate steps (e.g., potential cooperative relationship detection and situational information sharing) are added. The potential cooperative relationship detection is employed to detect whether there is a potential dependency or contradiction between the decision instruction of the agent and the decision instruction generated by other agents. After the potential cooperative relationship is confirmed, the situation interaction module releases its own situation information and cooperative relationship information to other agents and then receives information from other agent nodes. According to the collaboration detection, the specific collaboration relationship is determined according to the results of situation information interaction, and the specific collaboration relationship is processed through the coordination relationship adjustment mechanism to maximize the overall interests of each agent. The algorithm flow not only applies to the planning of cooperative relationships between any two independent agents, but also to cooperative planning among multiple agents.On the one hand, the distributed MA-HTN cooperative task planning process integrates the collaboration mechanism into the HTN, thus formulating and collaborating the decision-making instructions simultaneously. Accordingly, a decision-making scheme compatible with other agents can be yielded in one time. On the other hand, the confirmed cooperative relationship can be identified and processed as soon as possible. The original decision-making scheme is modified, which reduces the invalid decision-making actions of the adjusted decision-making instructions, and even may not need to make corresponding decisions at all. In brief, compared with the algorithm flow framework for conventional multiagent collaboration, this algorithm shows a higher advantage in reducing the global decision generation time and enhancing the collaboration efficiency. The specific algorithm flow is illustrated as follows Algorithm2.Algorithm 2:MultiAgent-HTN algorithm flow in distributed environment.
(1)
Procedure MA-HTNs,T,D
(2)
sets, initial state
(3)
setT, initial task set
(4)
setD, domain
(5)
initial operatorActionID=0
(6)
setP= the empty plan
(7)
T
0
⟵
t
belongs to
T
:
no other task in
T
is constrained to precede
t
(8)
loop
(9)
ifT is empty then return P
(10)
nondeterministically choose anyt in T0
(11)
ift is a primitive task then
(12)
choose a ground instancea for t with the smallest cost among the available resources
(13)
ActionID=ActionID+1
(14)
opmessagea=ID,Resourceuseda,sta,eta,costa
(15)
sendlist⟵opmessagea
(16)
sendopmessagea to the other planners
(17)
ifreceivelist≠∅:
(18)
ResourceID=Resourceuseda
(19)
conflict actionsa′⟵a′belongs to theextopmessagesofreceivelist:
(20)
hasResourcea′=ResourceusedIDand has the smalleststa′
(21)
and durationst,etis overlapped with durationst′,et′, then
(22)
ifst<st′
(23)
delete the restextopmessage in receivelist
(24)
Resourcestater=i,Resourcestr=st,Resourceetr=et
(25)
deleteT in T0 and add a into P
(26)
else ifst>st′
(27)
deleteopmessagea in sendlist
(28)
Resourcestater=i′,Resourcestr=st′,Resourceetr=et′
(29)
Backtrack
(30)
else deleteT in T0 and add a into P
(31)
ift is a nonprimitive task then
(32)
choose a method to decomposet into subtasks t1,t2,…,tn
(33)
deleteT in T0 and add t1,t2,…,tn into T0
(34)
if receiving a newopmessagea′ in receivelist of a′ and sendlist
(35)
ResourceID=Resourceuseda′
(36)
conflict actionsa′belongs to theextopmessagesofreceivelist:
(37)
hasResourceuseda=ResourceID,and has the smalleststa
(38)
and durationst,etis overlapped with durationst′,et′,then
(39)
ifst′<st
(40)
delete the restopmessage in sendlist
(41)
Resourcestater=i′,Resourcestr=st′,Resourceetr=et′
(42)
Backtrack to task node at actiona
(43)
else ifst′>st
(44)
deleteextopmessagea′ in receivelist
(45)
Resourcestater=i,Resourcestr=st,Resourceetr=et
(46)
deleteT in T0 and add a into P
(47)
repeat
(48)
end MA-HTN


### 4.6. Coordination Mechanism of Local Conflicts

For the contradiction of local conflicts between various agents, a corresponding cooperation mechanism should be adopted for processing. Decker uses GPGP to deal with the coordination of resource conflicts. However, the coordination mechanism employed in this paper consists of one party that keeps the original decision-making plan unchanged and the other party that modifies the original decision-making plan. In Figure4, there is a local conflict between Action.A1 and Action.B1 and between Agent.A and Agent.B. Action.A1 remains unchanged. Agent.B modifies Action.B1 and abandons Task.B1. Task.B is split into subtasks Task.B1 and Task.B2, and Action.B3 is selected to avoid the conflict. Since local conflicts belong to different agents, they may have different generation time. In the process of the agent’s cooperative planning, potential conflict contradictions are detected earlier, and according to the collaborative mechanism, the decision-making modification of which party should be made is determined. The party of the invalid adjustment decision scheme can continue to yield the decision-making instructions, and the party that needs adjustment receives the conflicting task nodes and makes the modification for the original task, which deletes the task node in the conflict section or replaces the conflicting task content to adjust the plan. Lastly, the sent or received conflict information is updated. The coordination chart of agent decision-making action conflict relationship is presented as follows.Figure 4
Agent conflict coordination mechanism.The Task.A of Agent.A can be decomposed into Action.A1 and Action.A2 of decision-making action, and the relationship between them is “and” in logical relation. Task.B of Agent.B can be decomposed into subtasks Task.B1 and Task.B2, and the relationship between them is “or” in logical relationship. The subtask Task.B1 can be further decomposed into decision-making actions Action.B1 and Action.B2. There is a conflict between Action.A2 and Action.B1, i.e., the execution of A2 will lead to unsmooth execution of B1.Based on this conflict coordination mechanism, a coordination mechanism is designed for reusable resource conflicts and consumptive resource conflicts.The reusable resource conflict coordination mechanism can be used by multiple decision-making agents simultaneously to generate repeated resource conflicts. For these resource conflicts, the tasks exhibiting higher priority are reserved and the tasks with lower priorities are coordinated based on determining the priority of the input tasks. The task priority criteria are the following three points. First, tasks that use resources earlier prioritize to ensure that the total global task time is the minimum. Second, tasks with higher overall interests have higher priority. Lastly, in the case of similar overall interests, the lower resource consumption exhibits higher priority.The resource consuming conflict coordination mechanism, i.e., part of the consumed resources can be used by multiple agents simultaneously, whereas the number of resources is insufficient. In this case, the resource consuming conflict coordination mechanism is employed to process conflicts. Based on judging the priority of the input task, the agent with high priority is guaranteed to complete the input task in priority to avoid multiple conflicts and lead to great loss of overall interests.


## 4.1. Description of Basic HTN Algorithms

The HTN decision system has been extensively used in the planning system of AI field. The HTN represents the change of state following the concept of atomic operators, and a group of atomic operators represents a state. The basic principle of the HTN aims to generate a range of instruction actions based on a target or task and input the given problem domain or task (e.g., the initial test state of the process), and the state is the sequence of the ordered unfinished task set.


## 4.2. Parameter Definition

Definition 1.
HTN is expressed as a six-tupleU,I,C,A,T,Nwith extended presequence language. In the six-tuple, U denotes variable set, I constant set, C logical consistent set, A agent’s task action set, T task set, and N task identifier set. These sets are independent of each other.Definition 2.
State refers to the basic state list of agent, i.e., the atomic state list. If the value is not 0, the state will be true; otherwise, it will be 0.Definition 3.
Agent’s task action isAgent.fx1,x2,…,xk, where f∈F,x1,x2,…,xk is the action item. The prerequisites and prediction results should be declared.Definition 4.
The complex task isftx1,x2,…,xk.


## 4.3. Constraints

### 4.3.1. Variable Constraint

(4)
v
1
=
c
v
1
=
v
2
,where v1,v2∈V denotes a variable identifier and c∈C c a constant identifier.


### 4.3.2. Sequential Constraint

(5)
n
<
n
′
,where n,n′∈N. “<” denotes the logical sequential operator, i.e., the task content of n must be completed before the decision instruction of n′ task is generated.


### 4.3.3. State Constraint

(6)
n
,
l
l
,
n
n
,
l
,
n
′
,
n and l are, respectively, the numbers of two agents performing tasks. n,l=1 indicates that l is executed after n; l,n=1 indicates that n is executed after l; and n,l,n′=1 indicates that l is executed between n and n′.


## 4.3.1. Variable Constraint

(4)
v
1
=
c
v
1
=
v
2
,where v1,v2∈V denotes a variable identifier and c∈C c a constant identifier.


## 4.3.2. Sequential Constraint

(5)
n
<
n
′
,where n,n′∈N. “<” denotes the logical sequential operator, i.e., the task content of n must be completed before the decision instruction of n′ task is generated.


## 4.3.3. State Constraint

(6)
n
,
l
l
,
n
n
,
l
,
n
′
,
n and l are, respectively, the numbers of two agents performing tasks. n,l=1 indicates that l is executed after n; l,n=1 indicates that n is executed after l; and n,l,n′=1 indicates that l is executed between n and n′.


## 4.4. Analysis of Algorithm Flow

The HTN planning is instantiated and analysed, which is detailed as follows Algorithm1:Algorithm 1:HTN algorithm Pseudo Code.
(1)
HTNs,U,C,O,M
(2)
ifU,C can be shown to have no solution
(3)
Then return failure
(4)
else ifU is primitive then
(5)
ifU,C has a solution then
(6)
nondeterministically letπ be any such solution
(7)
returnπ
(8)
else return failure
(9)
else
(10)
choose a nonprimitive task nodeu∈U
(11)
active⟵m∈Mtaskmis unifiable withtu
(12)
ifactive≠∅ then
(13)
nondeterministically choose anym∈active
(14)
σ⟵ an mgu for m and tu that renames all variables of m
(15)
U′,C′⟵δσU,C,σu,σm
(16)
U′,C′ ⟵ apply-critic U′,C′
(17)
return HTNs,U′,C′,O,M
(18)
else return failureThe algorithm exhibits good convergence. As the iteration proceeds, the quality of the decision scheme generated by the algorithm becomes increasingly higher. The specific convergence function is presented as follows:The aim of the experiment is to prove that the algorithm has good convergence. In Figure2, the horizontal axis is the number of iterations and the vertical axis is the value of error loss. According to the simulation, the number of iterations is taken as the reference object and the error loss value as the criterion of convergence. The experimental results show that the error loss value decreases with the increase of iteration times, so the algorithm has good convergence.Figure 2
Function convergence curve.


## 4.5. Multiagent Distributed Collaboration Framework Based on HTN

Usually, in a centralized environment, the collaboration framework of MultiAgent-HTN (MultiAgent-Hierarchical Task Network Planning, MA-HTN) is to establish a decision-making centre, control the overall situation, and deduce and solve the scheme.However, in the actual command and control process, the overall situation sharing is difficult to achieve, and the security of a single decision-making centre cannot be ensured. Once the centre is destroyed, it loses the initiative of war. Thus, distributed MA-HTN exhibits higher superiority. Each agent deduces the scheme internally and does not share the relevant information with each other in the process of scheme deduction. Moreover, each agent should cooperate with the scheme that has dependency or mutually exclusive relationship to solve local conflicts to build a task planning collaboration network and maximize the overall interests. The cooperative task planning process framework of distributed MA-HTN is illustrated in Figure3.Figure 3
Distributed mission planning process for distributed MA-HTN.The cooperative task planning of distributed MA-HTN is based on the modification of the decision-making scheme. Cooperative relationship adjustment mechanism is introduced to integrate the process of decision-making adjustment and modification. Thus, the cooperative relationship control of decision-making actions is achieved in the planning process. The algorithm flow follows the original HTN planning framework and intermediate steps (e.g., potential cooperative relationship detection and situational information sharing) are added. The potential cooperative relationship detection is employed to detect whether there is a potential dependency or contradiction between the decision instruction of the agent and the decision instruction generated by other agents. After the potential cooperative relationship is confirmed, the situation interaction module releases its own situation information and cooperative relationship information to other agents and then receives information from other agent nodes. According to the collaboration detection, the specific collaboration relationship is determined according to the results of situation information interaction, and the specific collaboration relationship is processed through the coordination relationship adjustment mechanism to maximize the overall interests of each agent. The algorithm flow not only applies to the planning of cooperative relationships between any two independent agents, but also to cooperative planning among multiple agents.On the one hand, the distributed MA-HTN cooperative task planning process integrates the collaboration mechanism into the HTN, thus formulating and collaborating the decision-making instructions simultaneously. Accordingly, a decision-making scheme compatible with other agents can be yielded in one time. On the other hand, the confirmed cooperative relationship can be identified and processed as soon as possible. The original decision-making scheme is modified, which reduces the invalid decision-making actions of the adjusted decision-making instructions, and even may not need to make corresponding decisions at all. In brief, compared with the algorithm flow framework for conventional multiagent collaboration, this algorithm shows a higher advantage in reducing the global decision generation time and enhancing the collaboration efficiency. The specific algorithm flow is illustrated as follows Algorithm2.Algorithm 2:MultiAgent-HTN algorithm flow in distributed environment.
(1)
Procedure MA-HTNs,T,D
(2)
sets, initial state
(3)
setT, initial task set
(4)
setD, domain
(5)
initial operatorActionID=0
(6)
setP= the empty plan
(7)
T
0
⟵
t
belongs to
T
:
no other task in
T
is constrained to precede
t
(8)
loop
(9)
ifT is empty then return P
(10)
nondeterministically choose anyt in T0
(11)
ift is a primitive task then
(12)
choose a ground instancea for t with the smallest cost among the available resources
(13)
ActionID=ActionID+1
(14)
opmessagea=ID,Resourceuseda,sta,eta,costa
(15)
sendlist⟵opmessagea
(16)
sendopmessagea to the other planners
(17)
ifreceivelist≠∅:
(18)
ResourceID=Resourceuseda
(19)
conflict actionsa′⟵a′belongs to theextopmessagesofreceivelist:
(20)
hasResourcea′=ResourceusedIDand has the smalleststa′
(21)
and durationst,etis overlapped with durationst′,et′, then
(22)
ifst<st′
(23)
delete the restextopmessage in receivelist
(24)
Resourcestater=i,Resourcestr=st,Resourceetr=et
(25)
deleteT in T0 and add a into P
(26)
else ifst>st′
(27)
deleteopmessagea in sendlist
(28)
Resourcestater=i′,Resourcestr=st′,Resourceetr=et′
(29)
Backtrack
(30)
else deleteT in T0 and add a into P
(31)
ift is a nonprimitive task then
(32)
choose a method to decomposet into subtasks t1,t2,…,tn
(33)
deleteT in T0 and add t1,t2,…,tn into T0
(34)
if receiving a newopmessagea′ in receivelist of a′ and sendlist
(35)
ResourceID=Resourceuseda′
(36)
conflict actionsa′belongs to theextopmessagesofreceivelist:
(37)
hasResourceuseda=ResourceID,and has the smalleststa
(38)
and durationst,etis overlapped with durationst′,et′,then
(39)
ifst′<st
(40)
delete the restopmessage in sendlist
(41)
Resourcestater=i′,Resourcestr=st′,Resourceetr=et′
(42)
Backtrack to task node at actiona
(43)
else ifst′>st
(44)
deleteextopmessagea′ in receivelist
(45)
Resourcestater=i,Resourcestr=st,Resourceetr=et
(46)
deleteT in T0 and add a into P
(47)
repeat
(48)
end MA-HTN


## 4.6. Coordination Mechanism of Local Conflicts

For the contradiction of local conflicts between various agents, a corresponding cooperation mechanism should be adopted for processing. Decker uses GPGP to deal with the coordination of resource conflicts. However, the coordination mechanism employed in this paper consists of one party that keeps the original decision-making plan unchanged and the other party that modifies the original decision-making plan. In Figure4, there is a local conflict between Action.A1 and Action.B1 and between Agent.A and Agent.B. Action.A1 remains unchanged. Agent.B modifies Action.B1 and abandons Task.B1. Task.B is split into subtasks Task.B1 and Task.B2, and Action.B3 is selected to avoid the conflict. Since local conflicts belong to different agents, they may have different generation time. In the process of the agent’s cooperative planning, potential conflict contradictions are detected earlier, and according to the collaborative mechanism, the decision-making modification of which party should be made is determined. The party of the invalid adjustment decision scheme can continue to yield the decision-making instructions, and the party that needs adjustment receives the conflicting task nodes and makes the modification for the original task, which deletes the task node in the conflict section or replaces the conflicting task content to adjust the plan. Lastly, the sent or received conflict information is updated. The coordination chart of agent decision-making action conflict relationship is presented as follows.Figure 4
Agent conflict coordination mechanism.The Task.A of Agent.A can be decomposed into Action.A1 and Action.A2 of decision-making action, and the relationship between them is “and” in logical relation. Task.B of Agent.B can be decomposed into subtasks Task.B1 and Task.B2, and the relationship between them is “or” in logical relationship. The subtask Task.B1 can be further decomposed into decision-making actions Action.B1 and Action.B2. There is a conflict between Action.A2 and Action.B1, i.e., the execution of A2 will lead to unsmooth execution of B1.Based on this conflict coordination mechanism, a coordination mechanism is designed for reusable resource conflicts and consumptive resource conflicts.The reusable resource conflict coordination mechanism can be used by multiple decision-making agents simultaneously to generate repeated resource conflicts. For these resource conflicts, the tasks exhibiting higher priority are reserved and the tasks with lower priorities are coordinated based on determining the priority of the input tasks. The task priority criteria are the following three points. First, tasks that use resources earlier prioritize to ensure that the total global task time is the minimum. Second, tasks with higher overall interests have higher priority. Lastly, in the case of similar overall interests, the lower resource consumption exhibits higher priority.The resource consuming conflict coordination mechanism, i.e., part of the consumed resources can be used by multiple agents simultaneously, whereas the number of resources is insufficient. In this case, the resource consuming conflict coordination mechanism is employed to process conflicts. Based on judging the priority of the input task, the agent with high priority is guaranteed to complete the input task in priority to avoid multiple conflicts and lead to great loss of overall interests.


## 5. Experimental Analysis

### 5.1. Problem Description

Resource scheduling in distributed command and control structure has always been one of the key issues in the field. Resource scheduling is a typical decision-making problem in the process of command and control. In the command process, many resources should be transported from resource storage to material demand in limited time. This problem is a complex decision-making problem. It involves numerous resource scheduling sites and resources. Both spatio-temporal constraints and numerical logic reasoning should be considered in the solution process. Besides, on the premise of meeting the requirements, high-quality and fast solutions should be generated.SupposeP1,P2,andP3 are resource demand points. Q1,Q2,andQ3 are resource storage points, which store Q q1,q2,q3,q4,andq5 resource types, respectively. Locations O1,O2,O3,O4,andO5 are the transfer centres for resource scheduling. Assume that seven transport teams can be used to solve the problem and the initial location of all transport teams is in the resource storage point and the transfer centre of resource scheduling. The transport capacity of each transport team should not exceed the transport limit of the team. The maximum speed and minimum speed of the team are defined as S_max and S_min, respectively. The specific information of the transport team is listed in Table 1.Table 1
Basic information of the resource dispatching transport team.
Number
Transport team
Transportation resource category
Transport limit
S
_
max
S
_
min
1
Team
1
O
1
,
O
2
500
50
75
2
Team
2
O
1
,
O
2
400
45
65
3
Team
3
O
3
,
O
4
500
45
70
4
Team
4
O
3
,
O
4
350
35
50
5
Team
5
O
4
400
30
60
6
Team
6
O
2
,
O
4
300
30
55
7
Team
7
O
1
,
O
2
,
O
3
,
O
4
300
45
65It is assumed that the temporal constraints for each transport team per transport are as follows:(7)Tmin≤End−Start≤Tmax;Tmin,0.5,Tmin+Tmax2,1,0.2∗Tmin+0.8∗Tmax,1,Tmax,0.5Tmin<0.5,Tmax>0.5Tmin+Tmax2<1;0.2∗Tmin+0.8∗Tmax>1,where Tmin denotes the time required for the transport team to transport resources at the minimum speed and Tmax is the time required for the transport team to transport resources at the maximum speed. Decision-making principle requires the resources to be transported from the resource storage place as soon as possible. At the same time, the required resources can reach the resource demand point as possible without considering the accidents in the transport process.To test the performance of Multiagents HTN, eight resource scheduling problems were designed. This is the initial state of the problem and the temporal constraints are more different. The specific information is listed in Table2.Table 2
Detailed plan of resource scheduling.
Number
Initial state
Temporal constraint
Problem
_
1
r
e
s
o
u
r
c
e
_
n
e
e
d
A
1
p
1
300
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
200
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
Problem
_
2
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
300
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
500
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
Problem_
3
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
200
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
300
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
500
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
Problem_
4
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
300
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
400
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
700
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
e
n
d
.1
≤
4
0,0
,
2,2
,
3,2
,
4,3
Problem
_
5
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
300
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
700
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
100
e
n
d
.1
≤
4
0,0
,
1,1
,
3,1
,
5,1
e
n
d
.1
≤
4
0,0
,
4,3
,
5,2
,
7,1
e
n
d
.1
≤
4
0,0
,
3,2
,
4,1
,
5,4
e
n
d
.1
≤
4
0,0
,
1,4
,
5,2
,
6,3
e
n
d
.1
≤
4
0,0
,
2,1
,
4,2
,
6,3
Problem_
6
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
300
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
500
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
500
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
700
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
e
n
d
.1
≤
4
0,0
,
1,3
,
3,1
,
5,7
e
n
d
.1
≤
4
0,0
,
3,7
,
7,8
,
2,5
e
n
d
.1
≤
4
0,0
,
3,2
,
5,3
,
6,5
e
n
d
.1
≤
4
0,0
,
4,4
,
5,3
,
5,1
Problem_
7
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
100
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
300
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
700
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
900
e
n
d
.1
≤
4
0,0
,
4,3
,
6,3
,
4,7
e
n
d
.1
≤
4
0,0
,
6,4
,
4,6
,
7,3
e
n
d
.1
≤
4
0,0
,
4,5
,
3,4
,
4,1
e
n
d
.1
≤
4
0,0
,
5,3
,
3,1
,
6,4
e
n
d
.1
≤
4
0,0
,
6,2
,
4,7
,
4,1
e
n
d
.1
≤
4
0,0
,
7,1
,
3,6
,
4,4
Problem_
8
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
200
e
n
d
.1
≤
4
0,0
,
3,1
,
2,2
,
5,5
e
n
d
.1
≤
4
0,0
,
3,3
,
3,2
,
4,1


### 5.2. Analysis of Experimental Results

In this paper, MultiAgent-HTN, TPHTN [35], and F-HTN algorithms are compared and analysed. The TPHTN algorithm exhibiting better temporal preference has been extensively applied practically. F-HTN is a dynamic task hierarchical planner with good dynamic replanning capability and is a fast HTN algorithm, which is optimized on the original HTN algorithm model to enhance the iteration rate of the algorithm. The advantage is the output rate of the final scheme is accelerated, but the defect is that the generated scheme may fall into the local optimal, resulting in the loss of global revenue. Thus, this paper takes the above algorithm as the comparison method.


#### 5.2.1. Quality Comparison of Generating Schemes

This paper compares the quality of the generating schemes of MultiAgent-HTN and TPHTN algorithm and solves the above algorithms, respectively. The quality comparison diagram of the generating schemes is given as follows.The preference degree is one of the important evaluation indexes for the quality of the generated scheme. The higher the preference degree is, the higher the quality of the final generated scheme will be. It can be found from Figure5 that both algorithms can solve the problem with relatively high quality, but MultiAgent-HTN has a better generation scheme than TPHTN. For some complex problems, e.g., Problem_6 and Problem_7, the quality of TPHTN generated solutions is obviously not as good as that of MultiAgent-HTN. The reason is that TPHTN adopts a rule-based planning method to quickly generate the solution. However, when the problem is complicated, the exponential growth of the rules that should be dealt with leads to the insufficient quality of the generating scheme. MultiAgent-HTN adopts a heuristic search strategy based on depth-first, so it is more prominent in solving complex problems.Figure 5
Initial state collection of resource scheduling planning.


#### 5.2.2. Efficiency Comparison of Generation Schemes

The generation solution requires not only a high-quality solution but also a sufficient efficiency. Excessive decision-making time often significantly affects the outcome of the decision. The efficiency of the scheme generation of MultiAgent-HTN and TPHTN is compared. The efficiency comparison of generating schemes is presented below.The comparison of the results of the above figure suggests that in general, the generation time of MultiAgent-HTN and TPHTN is approximately the same, but by combining Figures5 and 6, it can be concluded that the generation scheme of MultiAgent-HTN has relatively high quality. In solving complex problems, MultiAgent-HTN requires more time to generate decision-making solutions. Because of the small time difference, it is almost negligible. In conclusion, MultiAgent-HTN exhibits higher scheme generation efficiency than TPHTN.Figure 6
Comparison of the generation efficiency of MultiAgent-HTN and TPHTN schemes.


#### 5.2.3. Comparisons of Replanning Numbers

After a decision plan is generated, when a scenario is faced during the execution of the scenario, there are usually two solutions for that case. First, the decision plan should be revised. When the decision plan encounters an abnormality in the execution, the decision plan is adjusted following the determined decision modification rule. When the adjustment still encounters a tense anomaly, the replanning of the decision-making scheme is conducted. Second, the temporal exception handling is performed according to the temporal constraints. The replanning rate is obtained by dividing the average number of replanning times by the number of occurrences of the temporal anomaly. 4 out of the 8 questions above are selected as the subject. Among them, Problem_8 is simple. Problem_2 and Problem_5 are more complex issues. Problem_7 is complex. The specific experimental results are presented as follows.The results of Figures7–10 suggest that with the rise in abnormal frequency in the execution of decision-making schemes. The replanning rate basically shows an increasing trend. But there are also unexpected situations, which occur because the quality of the decision-making plan is contingent. In the same scenario, the rescheduling rate of MultiAgent-HTN is the lowest and that of F-HTN is the highest for the rescheduling of four problems. When the problem is too complicated or the solution space is too large, F-HTN and TPHTN may not be able to solve and will fall into deadlock. MultiAgent-HTN uses repair local decision-making scheme when the decision-making scheme needs to be replanned. Accordingly, the efficiency of reprogramming is much higher than those of the other two algorithms.Figure 7
Problem_2 comparison of resource replanning times.Figure 8
Problem_5 resource replanning comparison.Figure 9
Problem_7 resource replanning comparison.Figure 10
Problem_8 comparison of resource replanning times.


#### 5.2.4. Comparisons of Algorithmic Complexity

In the same scenario, the framework of this algorithm is compared with F-HTN and TPHTN algorithms. The results are listed in Tables3 and 4 below.Table 3
Algorithmic iteration efficiency comparison.
Algorithm
Limited time (s)
Number of iterations
Average objective function value
Algorithm in this paper
1
50
7.215
5
300
6.813
10
1000
6.126
HTN
1
50
11.215
5
300
10.813
10
1000
10.126
F-HTN
1
50
9.165
5
300
9.133
10
1000
8.562
TPHTN
1
50
9.935
5
300
9.423
10
1000
9.024Table 4
Algorithmic iteration efficiency comparison.
Algorithm
Time complexity
Space complexity
Sample data volume
Algorithm in this paper
O
1
O
m
5000
O
1
O
m
50000
O
1
O
m
1000000
HTN
O
n
2
O
m
n
5000
O
1
O
m
50000
O
1
O
m
1000000
F-HTN
O
n
2
O
m
n
5000
O
log
2
n
O
m
50000
O
n
2
O
m
1000000
TPHTN
O
log
2
n
O
m
n
5000
O
n
2
O
m
n
50000
O
1
O
m
1000000The experimental data suggest that the algorithm in this paper analyses the function value and its time-space complexity under the same number of iterations. It is found that the algorithm is capable of achieving lower objective function value, and it exhibits better convergence and adaptability.


## 5.1. Problem Description

Resource scheduling in distributed command and control structure has always been one of the key issues in the field. Resource scheduling is a typical decision-making problem in the process of command and control. In the command process, many resources should be transported from resource storage to material demand in limited time. This problem is a complex decision-making problem. It involves numerous resource scheduling sites and resources. Both spatio-temporal constraints and numerical logic reasoning should be considered in the solution process. Besides, on the premise of meeting the requirements, high-quality and fast solutions should be generated.SupposeP1,P2,andP3 are resource demand points. Q1,Q2,andQ3 are resource storage points, which store Q q1,q2,q3,q4,andq5 resource types, respectively. Locations O1,O2,O3,O4,andO5 are the transfer centres for resource scheduling. Assume that seven transport teams can be used to solve the problem and the initial location of all transport teams is in the resource storage point and the transfer centre of resource scheduling. The transport capacity of each transport team should not exceed the transport limit of the team. The maximum speed and minimum speed of the team are defined as S_max and S_min, respectively. The specific information of the transport team is listed in Table 1.Table 1
Basic information of the resource dispatching transport team.
Number
Transport team
Transportation resource category
Transport limit
S
_
max
S
_
min
1
Team
1
O
1
,
O
2
500
50
75
2
Team
2
O
1
,
O
2
400
45
65
3
Team
3
O
3
,
O
4
500
45
70
4
Team
4
O
3
,
O
4
350
35
50
5
Team
5
O
4
400
30
60
6
Team
6
O
2
,
O
4
300
30
55
7
Team
7
O
1
,
O
2
,
O
3
,
O
4
300
45
65It is assumed that the temporal constraints for each transport team per transport are as follows:(7)Tmin≤End−Start≤Tmax;Tmin,0.5,Tmin+Tmax2,1,0.2∗Tmin+0.8∗Tmax,1,Tmax,0.5Tmin<0.5,Tmax>0.5Tmin+Tmax2<1;0.2∗Tmin+0.8∗Tmax>1,where Tmin denotes the time required for the transport team to transport resources at the minimum speed and Tmax is the time required for the transport team to transport resources at the maximum speed. Decision-making principle requires the resources to be transported from the resource storage place as soon as possible. At the same time, the required resources can reach the resource demand point as possible without considering the accidents in the transport process.To test the performance of Multiagents HTN, eight resource scheduling problems were designed. This is the initial state of the problem and the temporal constraints are more different. The specific information is listed in Table2.Table 2
Detailed plan of resource scheduling.
Number
Initial state
Temporal constraint
Problem
_
1
r
e
s
o
u
r
c
e
_
n
e
e
d
A
1
p
1
300
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
200
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
Problem
_
2
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
300
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
500
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
Problem_
3
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
200
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
300
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
500
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
Problem_
4
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
300
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
400
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
700
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
e
n
d
.1
≤
4
0,0
,
2,2
,
3,2
,
4,3
Problem
_
5
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
300
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
700
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
100
e
n
d
.1
≤
4
0,0
,
1,1
,
3,1
,
5,1
e
n
d
.1
≤
4
0,0
,
4,3
,
5,2
,
7,1
e
n
d
.1
≤
4
0,0
,
3,2
,
4,1
,
5,4
e
n
d
.1
≤
4
0,0
,
1,4
,
5,2
,
6,3
e
n
d
.1
≤
4
0,0
,
2,1
,
4,2
,
6,3
Problem_
6
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
300
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
500
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
500
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
700
e
n
d
.1
≤
4
0,0
,
2,1
,
3,1
,
4,1
e
n
d
.1
≤
4
0,0
,
1,3
,
3,1
,
5,7
e
n
d
.1
≤
4
0,0
,
3,7
,
7,8
,
2,5
e
n
d
.1
≤
4
0,0
,
3,2
,
5,3
,
6,5
e
n
d
.1
≤
4
0,0
,
4,4
,
5,3
,
5,1
Problem_
7
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
100
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
300
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
700
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
900
e
n
d
.1
≤
4
0,0
,
4,3
,
6,3
,
4,7
e
n
d
.1
≤
4
0,0
,
6,4
,
4,6
,
7,3
e
n
d
.1
≤
4
0,0
,
4,5
,
3,4
,
4,1
e
n
d
.1
≤
4
0,0
,
5,3
,
3,1
,
6,4
e
n
d
.1
≤
4
0,0
,
6,2
,
4,7
,
4,1
e
n
d
.1
≤
4
0,0
,
7,1
,
3,6
,
4,4
Problem_
8
r
e
s
o
u
r
c
e
_
n
e
e
d
A
3
p
2
200
e
n
d
.1
≤
4
0,0
,
3,1
,
2,2
,
5,5
e
n
d
.1
≤
4
0,0
,
3,3
,
3,2
,
4,1


## 5.2. Analysis of Experimental Results

In this paper, MultiAgent-HTN, TPHTN [35], and F-HTN algorithms are compared and analysed. The TPHTN algorithm exhibiting better temporal preference has been extensively applied practically. F-HTN is a dynamic task hierarchical planner with good dynamic replanning capability and is a fast HTN algorithm, which is optimized on the original HTN algorithm model to enhance the iteration rate of the algorithm. The advantage is the output rate of the final scheme is accelerated, but the defect is that the generated scheme may fall into the local optimal, resulting in the loss of global revenue. Thus, this paper takes the above algorithm as the comparison method.


### 5.2.1. Quality Comparison of Generating Schemes

This paper compares the quality of the generating schemes of MultiAgent-HTN and TPHTN algorithm and solves the above algorithms, respectively. The quality comparison diagram of the generating schemes is given as follows.The preference degree is one of the important evaluation indexes for the quality of the generated scheme. The higher the preference degree is, the higher the quality of the final generated scheme will be. It can be found from Figure5 that both algorithms can solve the problem with relatively high quality, but MultiAgent-HTN has a better generation scheme than TPHTN. For some complex problems, e.g., Problem_6 and Problem_7, the quality of TPHTN generated solutions is obviously not as good as that of MultiAgent-HTN. The reason is that TPHTN adopts a rule-based planning method to quickly generate the solution. However, when the problem is complicated, the exponential growth of the rules that should be dealt with leads to the insufficient quality of the generating scheme. MultiAgent-HTN adopts a heuristic search strategy based on depth-first, so it is more prominent in solving complex problems.Figure 5
Initial state collection of resource scheduling planning.


### 5.2.2. Efficiency Comparison of Generation Schemes

The generation solution requires not only a high-quality solution but also a sufficient efficiency. Excessive decision-making time often significantly affects the outcome of the decision. The efficiency of the scheme generation of MultiAgent-HTN and TPHTN is compared. The efficiency comparison of generating schemes is presented below.The comparison of the results of the above figure suggests that in general, the generation time of MultiAgent-HTN and TPHTN is approximately the same, but by combining Figures5 and 6, it can be concluded that the generation scheme of MultiAgent-HTN has relatively high quality. In solving complex problems, MultiAgent-HTN requires more time to generate decision-making solutions. Because of the small time difference, it is almost negligible. In conclusion, MultiAgent-HTN exhibits higher scheme generation efficiency than TPHTN.Figure 6
Comparison of the generation efficiency of MultiAgent-HTN and TPHTN schemes.


### 5.2.3. Comparisons of Replanning Numbers

After a decision plan is generated, when a scenario is faced during the execution of the scenario, there are usually two solutions for that case. First, the decision plan should be revised. When the decision plan encounters an abnormality in the execution, the decision plan is adjusted following the determined decision modification rule. When the adjustment still encounters a tense anomaly, the replanning of the decision-making scheme is conducted. Second, the temporal exception handling is performed according to the temporal constraints. The replanning rate is obtained by dividing the average number of replanning times by the number of occurrences of the temporal anomaly. 4 out of the 8 questions above are selected as the subject. Among them, Problem_8 is simple. Problem_2 and Problem_5 are more complex issues. Problem_7 is complex. The specific experimental results are presented as follows.The results of Figures7–10 suggest that with the rise in abnormal frequency in the execution of decision-making schemes. The replanning rate basically shows an increasing trend. But there are also unexpected situations, which occur because the quality of the decision-making plan is contingent. In the same scenario, the rescheduling rate of MultiAgent-HTN is the lowest and that of F-HTN is the highest for the rescheduling of four problems. When the problem is too complicated or the solution space is too large, F-HTN and TPHTN may not be able to solve and will fall into deadlock. MultiAgent-HTN uses repair local decision-making scheme when the decision-making scheme needs to be replanned. Accordingly, the efficiency of reprogramming is much higher than those of the other two algorithms.Figure 7
Problem_2 comparison of resource replanning times.Figure 8
Problem_5 resource replanning comparison.Figure 9
Problem_7 resource replanning comparison.Figure 10
Problem_8 comparison of resource replanning times.


### 5.2.4. Comparisons of Algorithmic Complexity

In the same scenario, the framework of this algorithm is compared with F-HTN and TPHTN algorithms. The results are listed in Tables3 and 4 below.Table 3
Algorithmic iteration efficiency comparison.
Algorithm
Limited time (s)
Number of iterations
Average objective function value
Algorithm in this paper
1
50
7.215
5
300
6.813
10
1000
6.126
HTN
1
50
11.215
5
300
10.813
10
1000
10.126
F-HTN
1
50
9.165
5
300
9.133
10
1000
8.562
TPHTN
1
50
9.935
5
300
9.423
10
1000
9.024Table 4
Algorithmic iteration efficiency comparison.
Algorithm
Time complexity
Space complexity
Sample data volume
Algorithm in this paper
O
1
O
m
5000
O
1
O
m
50000
O
1
O
m
1000000
HTN
O
n
2
O
m
n
5000
O
1
O
m
50000
O
1
O
m
1000000
F-HTN
O
n
2
O
m
n
5000
O
log
2
n
O
m
50000
O
n
2
O
m
1000000
TPHTN
O
log
2
n
O
m
n
5000
O
n
2
O
m
n
50000
O
1
O
m
1000000The experimental data suggest that the algorithm in this paper analyses the function value and its time-space complexity under the same number of iterations. It is found that the algorithm is capable of achieving lower objective function value, and it exhibits better convergence and adaptability.


## 5.2.1. Quality Comparison of Generating Schemes

This paper compares the quality of the generating schemes of MultiAgent-HTN and TPHTN algorithm and solves the above algorithms, respectively. The quality comparison diagram of the generating schemes is given as follows.The preference degree is one of the important evaluation indexes for the quality of the generated scheme. The higher the preference degree is, the higher the quality of the final generated scheme will be. It can be found from Figure5 that both algorithms can solve the problem with relatively high quality, but MultiAgent-HTN has a better generation scheme than TPHTN. For some complex problems, e.g., Problem_6 and Problem_7, the quality of TPHTN generated solutions is obviously not as good as that of MultiAgent-HTN. The reason is that TPHTN adopts a rule-based planning method to quickly generate the solution. However, when the problem is complicated, the exponential growth of the rules that should be dealt with leads to the insufficient quality of the generating scheme. MultiAgent-HTN adopts a heuristic search strategy based on depth-first, so it is more prominent in solving complex problems.Figure 5
Initial state collection of resource scheduling planning.


## 5.2.2. Efficiency Comparison of Generation Schemes

The generation solution requires not only a high-quality solution but also a sufficient efficiency. Excessive decision-making time often significantly affects the outcome of the decision. The efficiency of the scheme generation of MultiAgent-HTN and TPHTN is compared. The efficiency comparison of generating schemes is presented below.The comparison of the results of the above figure suggests that in general, the generation time of MultiAgent-HTN and TPHTN is approximately the same, but by combining Figures5 and 6, it can be concluded that the generation scheme of MultiAgent-HTN has relatively high quality. In solving complex problems, MultiAgent-HTN requires more time to generate decision-making solutions. Because of the small time difference, it is almost negligible. In conclusion, MultiAgent-HTN exhibits higher scheme generation efficiency than TPHTN.Figure 6
Comparison of the generation efficiency of MultiAgent-HTN and TPHTN schemes.


## 5.2.3. Comparisons of Replanning Numbers

After a decision plan is generated, when a scenario is faced during the execution of the scenario, there are usually two solutions for that case. First, the decision plan should be revised. When the decision plan encounters an abnormality in the execution, the decision plan is adjusted following the determined decision modification rule. When the adjustment still encounters a tense anomaly, the replanning of the decision-making scheme is conducted. Second, the temporal exception handling is performed according to the temporal constraints. The replanning rate is obtained by dividing the average number of replanning times by the number of occurrences of the temporal anomaly. 4 out of the 8 questions above are selected as the subject. Among them, Problem_8 is simple. Problem_2 and Problem_5 are more complex issues. Problem_7 is complex. The specific experimental results are presented as follows.The results of Figures7–10 suggest that with the rise in abnormal frequency in the execution of decision-making schemes. The replanning rate basically shows an increasing trend. But there are also unexpected situations, which occur because the quality of the decision-making plan is contingent. In the same scenario, the rescheduling rate of MultiAgent-HTN is the lowest and that of F-HTN is the highest for the rescheduling of four problems. When the problem is too complicated or the solution space is too large, F-HTN and TPHTN may not be able to solve and will fall into deadlock. MultiAgent-HTN uses repair local decision-making scheme when the decision-making scheme needs to be replanned. Accordingly, the efficiency of reprogramming is much higher than those of the other two algorithms.Figure 7
Problem_2 comparison of resource replanning times.Figure 8
Problem_5 resource replanning comparison.Figure 9
Problem_7 resource replanning comparison.Figure 10
Problem_8 comparison of resource replanning times.


## 5.2.4. Comparisons of Algorithmic Complexity

In the same scenario, the framework of this algorithm is compared with F-HTN and TPHTN algorithms. The results are listed in Tables3 and 4 below.Table 3
Algorithmic iteration efficiency comparison.
Algorithm
Limited time (s)
Number of iterations
Average objective function value
Algorithm in this paper
1
50
7.215
5
300
6.813
10
1000
6.126
HTN
1
50
11.215
5
300
10.813
10
1000
10.126
F-HTN
1
50
9.165
5
300
9.133
10
1000
8.562
TPHTN
1
50
9.935
5
300
9.423
10
1000
9.024Table 4
Algorithmic iteration efficiency comparison.
Algorithm
Time complexity
Space complexity
Sample data volume
Algorithm in this paper
O
1
O
m
5000
O
1
O
m
50000
O
1
O
m
1000000
HTN
O
n
2
O
m
n
5000
O
1
O
m
50000
O
1
O
m
1000000
F-HTN
O
n
2
O
m
n
5000
O
log
2
n
O
m
50000
O
n
2
O
m
1000000
TPHTN
O
log
2
n
O
m
n
5000
O
n
2
O
m
n
50000
O
1
O
m
1000000The experimental data suggest that the algorithm in this paper analyses the function value and its time-space complexity under the same number of iterations. It is found that the algorithm is capable of achieving lower objective function value, and it exhibits better convergence and adaptability.


## 6. Conclusions

With the frequent occurrence of local disputes and emergencies, a growing number of scholars worldwide pay attention to the generation of decision-making schemes for emergency response to real events. The basic aim of the decision-making scheme is to fulfill the tactical objectives of the complete scheme that is to minimize the casualties and property losses as much as possible. Moreover, the generation time of the scheme should be shortened to a great extent and the local disputes should be coordinated quickly and efficiently after the implementation of the scheme. As one of the efficient intelligent planning algorithms, HTN exhibits good adaptability and high efficiency in solving such problems, which is the basis of the algorithm framework proposed in this paper.In this paper, a distributed command and control structure model based on multiagent is constructed to meet the demand of current command and control structure. The problem of large amount of data and complex situation environment of emergency events is solved using the high collaboration efficiency of multiagent and the superiority of solving complex problems. Based on the HTN algorithm, an algorithm framework of MultiAgent-HTN is proposed and the algorithm is simulated and compared comprehensively. The results of experiments reveal that the algorithm exhibits high practicability and research value in solving complex problems with large amount of data and complex situation. Besides, it also exhibits high adaptability and superior self-cooperation ability. Furthermore, the future research direction of this paper involves optimizing the exact method by adding effective inequalities to solve more instances in the branching and cutting framework. Community based on larger metaheuristic large neighbourhood search (LNS) may be considered a good candidate approximation method. Moreover, the capacity version of the problem is also a noteworthy topic for future study.



---

*Source: 4259649-2019-11-06.xml*