Sage Journals: Discover world-class research

Abstract

The multi-autonomous underwater vehicles (Multi-AUVs) cluster is an important means to solve the marine tasks effectively. The heterogeneous Multi-AUVs are constrained by cooperative relationship, and a model of multi-autonomous underwater vehicles role-based collaborative task planning is proposed. The Multi-AUVs are set to different roles depending on the functional properties. To analyze the accountability of each role, and to ensure the reliability, the desired behavior and the estimate state of each role are described in the model. Task allocation needs to be implemented dynamically in path planning, for the existing of the cooperative relationships and the demand of tasks changes. Role-based task assessment and allocation methods are proposed to achieve dynamic adjustment of roles according to task requirements. Due to poor underwater communication conditions, the implicit coordination framework is implied to the coordinate information interaction to compensate the large delays in underwater communications and the reliance between Multi-AUVs. To adapt to the implicit collaborative framework and poor communication conditions, a variable communication radius (contract network) is proposed. The simulation result shows that the proposed method has well performance.

Keywords

Multi-autonomous underwater vehicles collaborative task planning role modeling implicit coordination variable communication radius contract network

Introduction

Autonomous underwater vehicle (AUV) is a highly integrated underwater intelligent vehicle which can perform complex marine tasks by carrying various sensors and special equipment. By programming, the AUV can autonomously perform complex marine tasks without humans. Due to the demands of special tasks, the size of AUV should not be too large, which requires us to design micro AUV. The problem with micro AUV, however, is that they have limited space, the sensors and other functional modules they carry. Therefore, heterogeneous Multi-AUVs are applied to the actual scenario. The efficient and reliable tasks execution can be realized through reasonable measurement and configuration of its strategy.^1,2 The collaborative task planning problem of Multi-AUVs is an non-deterministic polynomial-hard problem with time-sequence logical constraints. In this article, a role-based task planning method is proposed. According to tasks requirements, the Multi-AUVs will be given different roles, to make the task collection be decomposed into multiple subtasks of the same attributes. The method can reduce with the size of the temporal logic programming problem, and shorten the planning time.

The main marine tasks that the Multi-AUVs can perform are hydrological monitoring, military confrontation, and underwater operations.³ The tasks set can be divided into different task subsets according to different sensors required, and these subsets are the basis for assigning roles to AUV. The functional modules loaded by heterogeneous AUV are different, so the types of tasks performed are subject to the functional modules. In this article, a functional hierarchy is proposed based on the types of tasks performed by AUV and the time–space constrained task execution strategy. To achieve high task execution efficiency, the parallel management method is adopted for AUV by referring to the research methods of multiple agents. Each same constructed AUV can be identified as a role with unique advantages for performing a given task.⁴

The role-based AUV classification method is adopted to make AUV change from passive receiving instruction information to active analyzing of other collaborative AUV status in the process of task execution, to achieve the reliability of collaboration under poor communication conditions and unknown environment. It is also the guiding ideology of parallel management. Partially observable Markov decision-making process (POMDP) method applied in parallel role model is appropriate.⁵

A contract network algorithm with variable communication radius (VCR) is proposed, which can effectively solve the problem of cooperative control in weak communication environment, reduce communication range and communication bandwidth; and at the same time, a Multi-AUVs tasks execution scheme that can meet the task demand is presented.

The rest of this article is as follows. Second section presents the collaborative task planning modeling and the implicit collaborative framework. In the third section, the Multi-AUVs role assignment and task assignment is provided. The simulation and experimental is shown in fourth section and we conclude this article in the last section.

Collaborative task planning modeling

Role description

The structure of parallel management is the same as that of AUV distributed structure. Due to communication restrictions, it is commonly used to find a distributed structure (master–slave structure) of AUV as the main AUV, but this will make the AUV limited.⁶ The application of implicit cooperation can make the decentralized AUV structure have the same synergistic effect as the master–slave structure, which means reflected in the improvement of freedom and intelligence.

As shown in Figure 1, heterogeneous Multi-AUVs clusters are divided into different roles according to their respective functions. For a given task, the task can be performed by $n_{i}$ different roles which played by corresponding Multi-AUVs. When $n_{i} > 1$ , a cooperative role group composed of Multi-AUVs can be described by quaternions $< POMDP, P I, E, K >$ . POMDP is defined by $< S, A, Z, T, O, R, B, γ >$ , where a finite set of actions $a \in A_{r}$ is defined corresponding to the rights attached to the role. The responsibility of each role r is represented by a reward function $R_{i}^{r} (s_{i}, a_{i})$ , where $i \in 1, ..., n$ identifies AUV perform it and $s_{i}$ refers to the state of ${AUV}_{i}$ . The objective of the cooperative role group represented with a reward function depending on joint states and joint actions, and definite as the addition of the local rewards for each AUV

R (s, a) = \sum_{i = 1}^{n} R_{i}^{r_{i}} (s_{i}, a_{i})

Figure 1.

AUV and role relational topology. AUV: autonomous underwater vehicle.

A belief function $b \in B$ is maintained as the probability distribution of states. The objective is to determine the policy $π (b) = a$ that maximizes the expected cumulative reward

V^{t} (b) = r (b, π (b)) + γ \sum_{z \in Z} p (z | a, b) V^{t - 1} (b_{a}^{z})

where $r (b_{t}, π (b_{t})) = \sum_{s \in S} R (s, π (b_{t})) b_{t} (s)$ is the expected immediate reward and $z \in Z$ refers to the possible observation. To ensure that the sum is finite when $T \to \infty$ , rewards are weighted by a discount factor γ (0,1).⁷

To predict the behavior of a role, the AUV, which is both the role holder and the planner of the action, must know the policy functions of all roles.⁸ A set of policy functions $P I = {π_{r 1}, π_{r 2}, ..., π_{r n}}$ indicates the policies of all roles.

When AUV performs the next action, it needs to combine the policy with the current belief. The belief states of other roles need to be updated by the prediction function. By observing the actual actions of the teammates’ roles after the execution of the actions, Bayes estimates that the updates can be made

\bar{b^{'}} (s^{'}) = \frac{1}{η} O (z, a_{i}, s^{'}) \sum_{s \in S} T (s^{'}, a_{i}, s) \bar{b} (s)

E'_{r} (\bar{b'}) = η E_{r} (\bar{b})

where $T (s', a_{i}, s)$ represents the probability of executing action $a_{i}$ in state s and moving to state $s^{'}$ and $O (z, a_{i}, s^{'})$ represents the probability of observing z when executing action $a_{i}$ and reaching state $s^{'}$ . And the normalization constant is

η = p (z | \tilde{b}, a) = \sum_{s \in S'} O (z, a, s') \sum_{s \in S} T (s', a, s) \tilde{b} (s)

The parameter z is the actual observation of the other roles, thence every possible observation $z \in Z$ should be traversed. As a result, one estimated belief state reproduces multiples after the iteration.

To get the only state of belief, k describes a set of critical actions that lead the process of tasks. The performer of the critical actions is the AUV that takes the role of path planner, denoted by ${role}_{pp}$ . Once an action $a \in k$ is found or believed performed, other teammates will translate both its belief state and the predicted belief of other members into the predicted belief state of ${role}_{pp}$ with the largest probability

b = \underset{\tilde{b}}{argmax} [E_{{role}_{pp}} (\tilde{b})]

{\tilde{b}}_{other} = \underset{\tilde{b}}{argmax} [E_{{role}_{pp}} (\tilde{b})]

This function ensures the accuracy of the prediction while promoting the task. And from above, get the following equation

V^{t} (b) = max_{r_{i}, a_{i} \in A_{r_{i}}} [\sum_{s \in S} \sum_{i = 1}^{n} R_{i}^{r_{i}} (s_{i}, a_{i}) b (s) + γ \sum_{z \in Z} p (z | a, b) V^{t - 1} (b_{b}^{a})]

Implicit coordination modeling

When Multi-AUVs perform tasks, due to the influence of environmental uncertainty and limited communication interaction, the intelligence degree of collaboration between AUVs plays an important role in the completion of collaborative tasks. For specific tasks, the functional requirements for AUV are different. Therefore, it is necessary to divide AUV with specific functions to achieve the reliability of AUV collaboration under unknown environment and poor communication conditions.^9
–11

By using POMDP to analyze inaccurate observation information and uncertain execution effect, the role model of Multi-AUVs was established. Because of the role assignment, Multi-AUVs can solidify several behaviors in each role’s knowledge base, thereby reducing the amount of data generated by adopting a fixed communication format.^12,13

To realize AUV cooperation under poor communication conditions, it is assumed that AUV broadcasts a clue c ∈ C_a to other members after performing an action a. The non-empty C_a is all possible clue of a. The implicit coordination framework is shown in Figure 2.

Figure 2.

The implicit coordination framework.

From the role model, we can get the policy $π_{t}$ of ${role}_{t}$ , the historical clue series ${c_{0}, c_{1}, ... c_{n - 1}}$ of ${role}_{t}$ obtained by observation, and the initial belief state ${role}_{t}$ of $b_{0}$ . To solve the further action $a_{n}$ of ${role}_{t}$ and its probability distribution, the algorithm estimates the current belief state of ${role}_{t}$ by Bayes estimation, and inputs it into $π_{i}$ to calculate the prediction of further action. After obtaining the clues of actual action through observation, the deviation of prediction is corrected by filtering the prediction set and the clues of actual action. After the prediction of the belief state and the prediction of the further actions of the teammates, the implicit coordination is realized by converting the belief state into the prediction belief of the leading role.

The prediction function is used to predict the further action from the prediction set of belief state. It can make decision by each belief state $\tilde{b_{i}} \in \tilde{E_{i}}$ , then votes on each possible further action with probability of $\tilde{b_{i}}$ . The action with the highest probability becomes the prediction outcome. This process can be expressed as follows

\tilde{a_{i}} = \underset{a}{argmax} \sum_{\tilde{b_{i}} \in \tilde{E_{i}}, π_{t} (\tilde{b_{i}}) = a} p (\tilde{b_{i}})

Consider a simple model with two states $s_{1}$ and $s_{2}$ . Assume that $b_{1}$ and $b_{2}$ are two belief states in $\tilde{E}$ with the probability $p_{1}$ and $p_{2}$ . Each possible further action is compared with probability, the only thing to do is comparing $p_{1}$ and $p_{2}$ to select the most likely further action between $a_{1}$ and $a_{2}$ .

To further explain the model, specific objects are proposed. During the execution of a series of tasks, three roles may be used, such as path planning role, function execution role, and communication and computing role. Each role has several states of its own, such as movement and cessation. When the path planning role arrives at the designated location, it will stop moving, so that other roles will start to perform topographic scanning and detection when they find that the path planning role has stopped moving.^14
–16

Task description

Marine tasks are classified by corresponding Multi-AUVs sensor modules, and the tasks set and Multi-AUVs collection must describe these attributions. To fully describe the Multi-AUVs task assignment, the Multi-AUVs cooperative task allocation can be described with multi-tuple

{R, T, F, E, C}

In equation (10), the Multi-AUVs roles collection is $R = {R_{1}, R_{2}, \dots R_{n}}$ and $R_{i}$ is a role group composed of the heterogeneous Multi-AUVs that can perform a kind of task. The tasks set is $T = {T_{1}, T_{2}, \dots T_{n}}$ , and each subtask $T_{j}$ can be performed by a group of roles and tasks marked with the same class of symbols can be performed by a set of roles $R_{i}$ . $F$ represents the set of objective functions. $E$ represents the underwater environment. $C$ is the set of constrains.^17

–21

As shown in Figure 3, there are six groups of roles and different types of tasks in the environment. Each group of Multi-AUVs must perform one kind of task sequence. The objective functions of AUV execution are the shortest time, which is also the shortest path when there is no current information in the task environment $E$ .

Figure 3.

Task description.

Assuming that there are n groups of roles in the area to carry out the marine tasks, m targets need to be allocated, then the target distribution matrix $Q^{m \times n}$ is

Q_{i j} = {\begin{matrix} 1 T_{j} is assigned to R_{i} \\ 0 T_{j} is nοt assigned to R_{i} \end{matrix}

In equation (11), $i = 1, 2 \dots, n$ , $j = 1, 2 \dots, m$ . The subset of tasks meets $T = \cap_{j = 1}^{n} T_{j},$ $T_{j} \cap T_{l} = \emptyset,$ $\forall j, l \in (1, 2, \dots, n)$ . To achieve reasonable allocation, task allocation should meet the following constraints

\begin{matrix} \sum_{i = 1}^{m} Q_{i j} \leq m_{max} \\ \sum_{j = 1}^{n} Q_{i j} \leq n_{max} \\ seq (T_{i}, T_{j}) > 0 \end{matrix}

In equation (12), $m_{max}$ represents the number of tasks assigned to role group and $n_{max}$ is the maximum amount of tasks assigned by role group. $seq (T_{i}, T_{j}) > 0$ indicates that the tasks sequence has certain timing constrains between tasks.

Multi-AUVs role assignment and task planning

Role assignment

As shown in second section, tasks and role groups are one-to-one correspondence, and role groups contain at least one heterogeneous AUV. Therefore, to simplify the problem, the role assignment problem is simplified to the matching problem of the role group and the same attribute task. According to the requirements of tasks for AUV function modules, specific AUV is assigned to different roles, and AUV resource constraints and task attribute constraints are considered in the allocation process. Meanwhile, equations (7) and (8) are adopted in the role group to allocate the role and obtain the best expected cumulative reward. Since this article mainly introduces the cooperative task assignment problem, the traditional Hungarian algorithm can be adopted for the role pre-assignment problem.²²

Task planning algorithm

Collaborative task planning is usually divided into task allocation and path planning problems. In this article, the methods of dealing with the task allocation problem is as follows: instead of assigning each AUV to the role group, the heterogeneous AUV with the cooperative relation can form the cooperative relation, and then solve each specific task. For the path planning problem, it can be seen from the modeling in the second section that an AUV is required to assume the role of the path planner. Therefore, collaborative path planning becomes a Multi-AUVs task traversal problem. The objective function of path planning in this article adopts the strategy of shortest path, and the objective function is also the shortest time if the underwater water flow environment is not considered.

For the task planning problem, the contract network is used to optimize the solution. The role group will bid value as the control variable for negotiation and competition and determine the distribution of tasks. Due to the limitation of underwater communication conditions, the VCR contract network algorithm is adopted for tenderers to send bidding signals to tenderers within a certain communication radius (actual space distance). If no suitable tenderers are found, the communication radius will be extended. The flowchart of VCR contract network algorithm is shown in Figure 4.

Task announcement stage: For a new target, if the current role group is unable to complete the task, the tenderer role group will inform the bidders to participate in the bid. The bidding stage is based on the communication mechanism. The tenderer sets the communication radius and issues the bidding information to the role group within the communication radius.

Bidding stage: When the role group within the communication radius of the tenderer receives the bidding information, it evaluates the change in the effectiveness of the target after the execution of the contract according to the requirements of the contract and its own status and sends the calculated results to the tenderer. When the bidder finds that the role group within the current communication radius cannot give a high-performance change value, the communication radius will be enlarged and the bidding information will be sent to the role group that has not made the bidding.

Awarding stage: The task is assigned to the winning bidder when the role group within the current communication radius of the tenderer can give a higher performance value.

Monitoring stage: The successful bidder role group and the tenderer role group have no opinion on the proposed contract. A commitment monitor relationship is formed and the implementation of the tasks enters the schedule. Bidding is completed, and the task will be executed successfully.

Figure 4.

Block diagram of VCR contract network algorithm. VCR: variable communication radius.

When the task assignment is completed, the role group forms a formation to perform the corresponding task sequence. The path planning ${AUV}_{pp}$ will be guided by the relevant path planning algorithm and obstacle avoidance algorithm to the task location. When the path planning ${AUV}_{pp}$ reaches the task location, the other AUVs in the role group perform their respective tasks. In the role group, the implicit cooperative algorithm is used to observe the actions of each role, to realize the state estimation of each AUV in the role group.

To highlight the problems studied, the shortest path algorithm is adopted to realize the path planning of multi-role groups. A feasible path planning algorithm can be seen in the article.²³ Without considering the effect of obstacles and ocean current in the underwater environment, the shortest path will be the broken line connection of the task location in the task sequence.

Simulation and experimental

In this article, the simulation environment is a three-dimensional (3-D) underwater environment of 1000 × 1000 × 2 (km). To facilitate observation, the 3-D space is projected into the two-dimensional space, where role group 1, 3, 6 can perform task type 1, and role group 2, 4, 5 can perform task type 2. Task types are distinguished by triangular and square in Figure 5.

Figure 5.

Comparison of task planning using two contract networks.

As shown in Figure 5, the task planning results of the traditional contract network and the VCR contract network are, respectively, used.

In the traditional contract network task planning results, the global execution efficiency of tasks is high, and each role group can perform corresponding tasks. However, it is obvious to pursue the global task load rate and role groups are more inclined to make tasks uniformly executed, resulting in serious bending of a single role group in path planning.

It can be seen from the VCR contract network simulation results: Tasks are all nearby principles, so that qualified role groups can perform corresponding tasks, which can not only meet the requirements of weak communication conditions but also realize shorter paths. From the VCR contract network simulation results, it can also be seen that role group 1 does not need to perform tasks, thus saving AUV equipment resources.

The Multi-AUV task allocation method based on role groups enables the AUV group to have strong task execution capability, which is more reliable than the single AUV task sequence. The task path length of each role group based on the VCR contract network and the traditional contract network is shown in Table 1.

Table 1.

The path length of two contract network algorithms (units: kilometer).

Role group	Traditional contract network	VCR contract network
1	1397.6	0
2	1517.3	904.2
3	973.2	973.2
4	891.2	891.2
5	1246.2	843.5
6	940.4	1670
Sum	6965.9	5282.1

VCR: variable communication radius.

It can be seen from Table 1 that the path length of the traditional contract network algorithm increases because of global bidding, while the overall path length of the contract network algorithm with VCR decreases because of adopting the principle of proximity.

At the same time, the method of VCR is well adapted to the underwater poor communication environment. When using the VCR contract network algorithm, the total path of a certain role group may be too long, but the above path scheme meets the needs of energy or path length during the bidding process of the contract network. If the global load rate needs to be balanced, improvements can be made during the modeling process. For example, when a first-level contract network can meet the tender requirements, it needs to be compared with the role groups within the second-level communication radius. To some extent, this approach can balance the communication and load rate requirements.

Conclusions

In this article, the implicit collaboration of role mechanism is adopted to make Multi-AUVs work effectively under the condition of poor communication. At the same time, a role-based task planning method was designed, which greatly increased the reliability of Multi-AUVs task execution. Contract network algorithm based on VCR also has good application characteristics for poor communication environment. And the overall path length of the contract network algorithm with VCR decreases because of adopting the principle of proximity. This article focuses on solving the cooperative control problem of collaborative task planning under the condition of poor communication with the function-centered role mechanism. The future will be considered how to solve the key AUV fault task re-planning method within the role group.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by the National Natural Science Foundation of China subsidization project (51579047), the Natural Science Foundation of Heilongjiang Province (QC2017048), the Natural Science Foundation of Harbin (2016RAQXJ077), and the Fundamental Research Funds for the Central Universities (HEUCF180407).

ORCID iD

Lei Zhang

References

Zhang

Yang

. Multi-AUV autonomous task planning based on the scroll time domain quantum bee colony optimization algorithm in uncertain environment. Plos One 2017; 12(11): 1–14.

Zhu

Huang

Yang

. Dynamic task assignment and path planning of multi-AUV system based on an improved self-organizing map and velocity synthesis method in three-dimensional underwater workspace. IEEE Trans Cybern 2012; 43(2): 504–514.

Zhang

Xia

. Multi-AUV cooperative task allocation based on improved contract network. In: IEEE international conference on mechatronics and automation, Takamatsu, Japan, 6–9 August 2017, pp. 608–613. IEEE.

Roncone

Mangin

Scassellati

. Transparent role assignment and task allocation in human robot collaboration. In: IEEE international conference on robotics and automation, Singapore, 29 May–2 June 2017, pp. 1014–1021. IEEE.

Smith

Simmons

. Point-based POMDP algorithms: improved analysis and implementation. Comput Sci 2012; 2012: 542–555.

Karras

Kyriakopoulos

Karavas

. Towards cooperation of underwater vehicles: a leader-follower scheme using vision-based implicit communications. In: International conference on intelligent robots and systems, Hamburg, Germany, 28 September–2 October 2015, pp. 4852–4857. IEEE.

Spaan

MTJ

Spaan

MTJ

. A point-based POMDP algorithm for robot planning. IEEE International conference on robotics and automation, 2004. proceedings. ICRA, New Orleans, LA, USA, 26 April–1 May 2004, pp. 2399–2404. IEEE.

Zhang

Chen

Fang

. A role-based POMDPs approach for decentralized implicit cooperation of multiple agents. In: IEEE international conference on control and automation, Ohrid, Macedonia, 3–6 July 2017, pp. 496–501. IEEE.

Hollinger

Singh

Djugash

. Efficient multi-robot search for a moving target. Int J Robot Res 2009; 28(28): 201–219.

10.

Sandra

Eduardo

. Formation control using replicator-mutator dynamics for multiple mobile autonomous agents. Neurocomputing 2016; 172(C): 337–344.

11.

Mondal

Bhowmick

Behera

. Trajectory tracking by multiple agents in formation with collision avoidance and connectivity assurance. IEEE Syst J 2017; 12(3): 2449–2460.

12.

Beslon

. Multi-robot path-planning based on implicit cooperation in a robotic swarm. In: International conference on autonomous agents. DBLP, Minneapolis, Minnesota, 10–13 May 1998, pp. 39–46. DBLP.

13.

Anderson

Papanikolopoulos

. Implicit cooperation strategies for multi-robot search of unknown areas. J Intell Robot Syst 2008; 53(4): 381–397.

14.

Wang

Xie

Pan

. Full-state regulation control of asymmetric underactuated surface vehicles. IEEE Trans Ind Electron 2018; 2018: 1–13.

15.

Wang

Pan

. Yaw-guided trajectory tracking control of an asymmetric underactuated surface vehicle. IEEE Trans Ind Inform 2018; 2018: 1–11.

16.

Wang

Hamid

. Accurate trajectory tracking of disturbed surface vehicles: a finite-time control approach. IEEE/ASME Trans Mech 2019; 2019: 1–9.

17.

Liang

Kang

. Distributed task allocation modeling based on agent topology and protocol for collaborative system. Optik – Int J Light Elect Opt 2016; 127(19): 7776–7781.

18.

Liu

Guo

Wang

. TaskMe: multi-task allocation in mobile crowd sensing. In: ACM international joint conference on pervasive and ubiquitous computing, Heidelberg, Germany, 12–16 September 2016, pp. 403–414. ACM.

19.

Kong

Zhang

. A belief propagation-based method for task allocation in open and dynamic cloud environments. Knowl-Based Syst 2016; 115: 123–132.

20.

Farinelli

Iocchi

Nardi

. Distributed on-line dynamic task assignment for multi-robot patrolling. Auton Robot 2016; 41(6): 1–25.

21.

Zhu

Sim

K M

Jiang

. Agent-based dynamic scheduling for earth-observing tasks on multiple airships in emergency. IEEE Syst J 2017; 10(2): 661–672.

22.

Frieze

. An algorithm for algebraic assignment problems. Discrete Appl Math 1979; 1(4): 253–259.

23.

Liu

. Robotic online path planning on point cloud. IEEE Trans Cybern 2016; 46(5): 1217–1228.

Role-based collaborative task planning of heterogeneous multi-autonomous underwater vehicles

Abstract

Keywords

Introduction

Collaborative task planning modeling

Role description

Implicit coordination modeling

Task description

Multi-AUVs role assignment and task planning

Role assignment

Task planning algorithm

Simulation and experimental

Conclusions

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References