GMP: A Genetic Mission Planner for Heterogeneous Multirobot System Applications

Area of Science:

• Artificial Intelligence
• Operations Research
• Computer Science

Background:

• The increasing application of multiagent systems (MASs) necessitates automated mission planning for complex tasks.
• Developing a generalized approach for MAS mission representation is key to solving the automated planning problem.
• Existing methods may face challenges in efficiency and optimality for real-world MAS mission planning.

Purpose of the Study:

• To propose a novel method for automated mission planning in heterogeneous multiagent systems.
• To adapt the Traveling Salesperson Problem (TSP) for MAS mission planning.
• To develop and evaluate a genetic mission planner (GMP) against established solvers.

Main Methods:

• Representing MAS missions as an extension of the Traveling Salesperson Problem (TSP).
• Developing a mixed-integer linear programming formulation for MAS mission planning.
• Implementing a genetic mission planner (GMP) with a local plan refinement algorithm for solving the formulated problem.

Main Results:

• The proposed genetic mission planner (GMP) demonstrates strong performance in generating mission plans for MASs.
• Comparative evaluation shows GMP outperforms CPLEX in terms of timing and solution optimality for most tested instances, especially under time constraints.
• Benchmarking on diverse problem instances validates the effectiveness of the GMP approach.

Conclusions:

• The genetic mission planner (GMP) provides an effective and efficient solution for automated mission planning in heterogeneous multiagent systems.
• Casting MAS missions as a TSP extension offers a viable modeling approach for automated planning.
• The GMP approach is particularly advantageous when timing constraints are critical in complex mission scenarios.