Task-Extended Utility Tensor Method for Decentralized Multi-Vehicle Mission Planning

In multi-vehicle systems, the coupling problem between the task allocation and path planning and the variability of task execution solutions creates challenges for utility estimation and affects the effectiveness of distributed mission planning. To characterize the effect of task sequences on the task utilities and implement a task-extended distributed allocation, we propose a task-extended utility tensor algorithm (TEUTA) based on market mechanism. In the mission planning problem of multi-vehicle system, we consider the impact of the task schedule on the vehicle trajectory, and indicate the vehicle task execution utilities under different preceding task points in the form of tensors. Further, a task-extended utility tensor iterative algorithm (TEUTIA) is presented based on an iterative strategy to improve the algorithm in terms of computational complexity. A task execution utility estimation model and an algorithm framework are designed for the implementation of the two proposed algorithms. The simulation and experimental results show that compared with the non-tensor method, TEUTA and TEUTIA can achieve higher task execution performance, and TEUTIA has better computational efficiency.
Note to Practitioners
—This work presents two novel multi-vehicle distributed mission planning algorithms based on the market mechanism. TEUTA and TEUTIA proposed in this paper can be applied to address the impact of vehicle motion constraints on mission planning, which are widely present in various types of common nonholonomic vehicles such as two-wheel differential drive vehicles and Ackerman steering vehicles. In the application of the algorithms, an accurate kinematic model of the vehicles is required for trajectory planning to estimate the task execution reward precisely, which is necessary for effective mission planning. When the vehicle trajectory planning algorithm is computationally intensive, TEUTIA can significantly reduce the computational consumption and improve the mission planning efficiency compared with TEUTA without losing task execution reward. Finally, a stable inter-vehicle communication network is required for the interactive process of the market mechanism, where bi-directional communication exists between any two vehicles, to ensure the stability of mission planning.