Integrated method for multi-UAV task assignment and trajectory planning with deadlock based on Three-dimensional...

Area of Science:

• Robotics and Automation
• Operations Research
• Artificial Intelligence

Background:

• Decoupled solutions for Unmanned Aerial Vehicle (UAV) task assignment and path planning often result in suboptimal outcomes.
• Multi-heterogeneous UAV systems present complex challenges in coordinating tasks and trajectories.
• Existing methods struggle to efficiently solve the integrated problem of task assignment and track planning.

Purpose of the Study:

• To develop an integrated approach for solving the coupled task assignment and path planning problem for multi-heterogeneous UAVs.
• To overcome the limitations of local optimality associated with decoupled solution methods.
• To enhance the efficiency and effectiveness of UAV mission planning.

Main Methods:

• Discretization of the UAV's heading angle within a 3D Dubins model to formulate a discrete graph model.
• Application of a parallel processing-based genetic algorithm to efficiently solve the mixed-integer programming problem.
• Integration of a depth-first algorithm to detect cycles in timing constraint graphs, thereby eliminating execution deadlocks.

Main Results:

• The integrated solution technique significantly outperforms decoupled methods in achieving optimal planning results.
• The distributed genetic algorithm demonstrates superior solution efficiency compared to traditional centralized genetic algorithms.
• The depth-first algorithm effectively identifies and resolves potential deadlocks in task execution.

Conclusions:

• An integrated approach for UAV task assignment and path planning yields superior results compared to decoupled methods.
• Parallel processing significantly enhances the efficiency of genetic algorithms for complex optimization problems.
• The proposed method provides a robust and efficient solution for multi-heterogeneous UAV mission planning.