An Algorithm for Task Allocation and Planning for a Heterogeneous Multi-Robot System to Minimize the Last Task...

Area of Science:

• Robotics
• Operations Research
• Artificial Intelligence

Background:

• Multiple heterogeneous mobile robot systems are crucial for diverse applications like delivery and surveillance.
• Existing algorithms often struggle with complex routing problems involving multiple depots and asymmetric costs.

Purpose of the Study:

• To develop an algorithm for operational strategies in multi-robot systems.
• To solve the min-max multiple depot heterogeneous asymmetric traveling salesperson problem (MDHATSP).
• To minimize the last task completion time while ensuring all targets are visited.

Main Methods:

• A primal-dual technique is employed to design the algorithm.
• The algorithm finds tours for heterogeneous robots from distinct depots.
• Focus on achieving sub-optimal solutions efficiently for real-time application.

Main Results:

• The algorithm effectively addresses generalized MDHATSP, including asymmetric costs and min-max objectives.
• Simulations with varying problem sizes demonstrate the algorithm's effectiveness.
• Reliable solutions are produced within reasonable computation times.

Conclusions:

• The proposed algorithm offers a practical approach for real-time operational strategies in complex multi-robot systems.
• It provides a balance between solution quality and computational efficiency.
• The findings support the deployment of such systems in logistics, monitoring, and emergency response.