PaperlayerView exact revision on arXiv

Source-linked AI summary

Solving Complex Multi-UAV Mission Planning Problems using Multi-objective Genetic Algorithms

Cristian Ramirez-Atencia, Gema Bello-Orgaz, Maria D R-Moreno, David Camacho

arXiv:2402.06504v1cs.NEeess.SP

TL;DR

Complex UAV missions require coordinating multiple vehicles and GCSs, while existing planning systems are rudimentary and the problem is NP-hard. The paper introduces a CSP-checked, Pareto-based genetic algorithm; across varied datasets it obtains good results and reaches the optimal frontier in most cases, though more complex problems require more generations.

  • Problem

    Multi-UAV mission planning is NP-hard, involves coordinating many requirements and GCSs, and existing systems rely on rudimentary preplanned or manually provided plans.

    Source: §1 · p. 2

  • Method

    A hybrid multi-objective genetic algorithm checks plan validity with CSP constraints, then uses Pareto-based optimization to minimize mission objectives.

    Source: §7 · p. 26

  • Results

    Across varied datasets, MOGA-CSP obtains good results and converges to the optimal Pareto frontier in most cases; optimizing distance and makespan gives good results across all variables.

    Source: §7 · p. 26

  • Takeaways & Limitations

    Distance and makespan are the best objective combination tested for obtaining good results across all mission variables.

    Source: §7 · p. 26

    As problem complexity increases, MOGA-CSP needs more generations to reach an optimal or near-optimal solution.

    Source: §7 · p. 26

Abstract

from arXiv · show

Due to recent booming of UAVs technologies, these are being used in many fields involving complex tasks. Some of them involve a high risk to the vehicle driver, such as fire monitoring and rescue tasks, which make UAVs excellent for avoiding human risks. Mission Planning for UAVs is the process of planning the locations and actions (loading/dropping a load, taking videos/pictures, acquiring information) for the vehicles, typically over a time period. These vehicles are controlled from Ground Control Stations (GCSs) where human operators use rudimentary systems. This paper presents a new Multi-Objective Genetic Algorithm for solving complex Mission Planning Problems (MPP) involving a team of UAVs and a set of GCSs. A hybrid fitness function has been designed using a Constraint Satisfaction Problem (CSP) to check if solutions are valid and Pareto-based measures to look for optimal solutions. The algorithm has been tested on several datasets optimizing different variables of the mission, such as the makespan, the fuel consumption, distance, etc. Experimental results show that the new algorithm is able to obtain good solutions, however as the problem becomes more complex, the optimal solutions also become harder to find.

1 Introduction

Multi-UAV mission planning requires coordinating complex tasks across vehicles and Ground Control Stations, but existing planning systems are rudimentary. The paper proposes a multi-objective genetic algorithm that checks plan validity with CSP constraints and optimizes mission objectives using Pareto-based measures.

1 Introduction

  • UAVs can perform high-risk tasks such as forest-fire detection and rescue without risking human lives, and can reach difficult-to-access areas.Source: §1 · p. 2
  • Mission planning systems rely on rudimentary preplanned or manually provided plans, while complex coordinated missions require more advanced capabilities.Planning encompasses tactical goals, command structure, coordination, and timing for a UAV team.Source: §1 · p. 2
  • Multi-UAV mission planning is NP-hard, and coordinating many requirements across several GCSs makes it harder to solve.The requirements create large search graphs with substantial computational demands.Source: §1 · p. 2
  • The proposed fitness function first checks plan validity against UAV and GCS constraints using a CSP, then optimizes solution quality with a Pareto-based function.The approach extends prior work.Source: §1 · p. 2

2 Related Work

The related work surveys mission planning, CSP methods, and genetic algorithms, connecting these areas to coordinated UAV missions and multi-objective optimization.

2 Related Work

  • The section situates mission planning, CSPs, and genetic algorithms as the three bodies of work relevant to the paper.Source: §2 · p. 3

2.1 Mission Planning

  • Mission planning assigns tasks to resources over time while satisfying constraints; prior work includes planning and monitoring frameworks, cooperative task assignment, collaborative UAV planning, and CSP formulations.The section notes few deliberative approaches to cooperative task assignment and mission planning.Source: §2.1 · pp. 3–4

2.2 Constraint Satisfaction Problems

  • CSPs represent variables, domains, and constraints; optimization extensions seek high-quality assignments, while temporal CSPs encode relations among task times.Reviewed solution approaches include search and consistency techniques, Branch & Bound, and other optimization methods.Source: §2.2 · pp. 4–5

2.3 Genetic Algorithms

  • Genetic algorithms are stochastic optimization methods used across domains, and prior UAV mission-planning work applies them to constrained missions, military scheduling, and task planning.The section also identifies multi-objective GAs, including SPEA2 and NSGA-II, as Pareto-based approaches for optimizing multiple mission criteria.Source: §2.3 · p. 5
  • Hypervolume measures the volume between an approximate and optimal Pareto frontier; zero indicates the optimal frontier, and larger values indicate a worse approximation.The figure distinguishes the optimal frontier in red, algorithm solutions in blue, and the intervening hypervolume in yellow.Source: §2.3 · p. 6, Figure 1 · p. 6
  • A commonly used stopping criterion halts execution when the Pareto frontier remains unchanged for a specified number of generations.Source: §2.3 · p. 6

3 Description of the Multi-UAV Mission Planning Problem

A mission plan assigns tasks to UAVs and UAVs to GCSs while accounting for task requirements and assignment timing. The problem definition also specifies vehicle, station, and task characteristics that constrain those assignments.

3 Description of the Multi-UAV Mission Planning Problem

  • A mission solution assigns each task to a UAV and each UAV to a GCS, with trajectories avoiding no-flight zones.Source: §3 · p. 6

3.1 Task Description

  • Tasks such as monitoring and photography use compatible UAV sensors, and their time intervals may specify start and end times or only duration.Source: §3.1 · pp. 7–8
  • Task dependencies can require the same or different UAVs, or constrain the temporal relation between tasks using Allen’s Interval Algebra [2].Source: §3.1 · p. 8

3.2 UAV Description

  • UAV features and positions are represented for checking plan correctness, and the approach considers four basic UAV types.Source: §3.2 · p. 8

3.3 GCS Description

  • Each UAV must be controlled by an appropriate GCS, whose features are considered in the mission model.Source: §3.3 · p. 8

3.4 Task Assignment Processes

  • Task assignment computes departure, travel, task, loiter, and return times using flight-profile speeds and distances; task times may be fixed or derived during assignment.Source: §3.4 · pp. 8, 10
  • Fuel and distance totals are computed for path, task, loiter, and return phases, supporting checks that an assigned UAV can fulfill a task within its interval.Source: §3.4 · pp. 10–11

4 Modelling the MPP as a CSP

The MPP is modelled as a CSP with variables for task assignments, schedules, UAV–GCS assignments, and operating choices, plus constraints that check mission feasibility.

4.1 CSP variables

  • Task-to-UAV assignments, task orders, and UAV-to-GCS assignments form core CSP variables; −1 marks an unassigned task or UAV.The assignment array is binary, and the order variables are used when task times are not fixed.Source: §4.1 · p. 11
  • Path and return flight profiles and task sensors encode operating choices, while propagation computes time, fuel, and distance variables.Sensor variables are needed when an assigned UAV has multiple sensors capable of the task.Source: §4.1 · p. 12

4.2 CSP constraints

  • Sensor constraints require a shared task–UAV sensor, and order constraints keep assigned tasks within the UAV’s task count and give them distinct orders.The stated sensor condition requires the intersection of available task and UAV sensors to be nonempty.Source: §4.2 · p. 12
  • GCS constraints check UAV-type compatibility, the station’s handling capacity, and coverage of each UAV during the mission.Source: §4.2 · p. 13
  • Temporal constraints relate departure, path duration, task start and end times, loiter, and return; they also prevent time-colliding tasks from sharing a UAV.Path duration is computed from path distance and the speed specified by its flight profile.Source: §4.2 · pp. 13–14
  • Dependency constraints encode task timing relations and require paired tasks to use either the same UAV or different UAVs, as specified.Source: §4.2 · pp. 14–15
  • Autonomy and range constraints bound each UAV’s total flight time and traversed distance by its autonomy and range.The totals include path, task, loiter, and return components.Source: §4.2 · p. 15
  • Fuel constraints keep consumption below initial fuel; path distance calculations use GeographicLb1 and Theta* to avoid no-fly zones and terrain obstacles.The path fuel calculation multiplies path duration by the flight profile’s fuel-consumption ratio.Source: §4.2 · p. 15

5 MOGA-CSP Algorithm for Multi-UAV Mission Planning Problems

MOGA-CSP combines genetic search with CSP-based feasibility checks and Pareto optimization. Its representation encodes mission assignments and operating choices, while allele-specific genetic operators evolve candidate solutions.

5 MOGA-CSP Algorithm for Multi-UAV Mission Planning Problems

  • MOGA-CSP applies CSP constraints as penalties during genetic-algorithm evaluation, then optimizes feasible solutions with a multi-objective fitness function.Source: §5 · p. 16, §5.2 · p. 17

5.1 Encoding

  • Six alleles encode UAV assignments, task order, GCS assignments, path profiles, task sensors, and return profiles.The example figure depicts a possible solution with five tasks, three UAVs, and two GCSs.Source: §5.1 · p. 16, Figure 4 · p. 17
  • The sensor allele permits only sensors valid for the assigned task, avoiding solutions that violate sensor constraints.Source: §5.1 · p. 17

5.2 Fitness Function

  • The fitness function assigns the worst value to constraint-violating solutions; feasible solutions are compared for a Pareto-optimal frontier using NSGA-II.The optimization variables are listed in Table 5.Source: §5.2 · pp. 17–18, Table 5 · p. 17

5.3 Algorithm

  • Selection retains N best individuals before roulette-wheel selection chooses parents; allele-specific crossover uses 2-point crossover or PMX for task-order permutations.The same crossover points are reused across assignment, path-profile, and sensor alleles to maintain multi-UAV task size and sensor consistency.Source: §5.3 · pp. 18–19, Figure 5 · p. 19
  • Mutation uses uniform changes for several alleles and insert mutation for task order; it is applied with probability Pm, usually about 5%.The insert mutation moves one randomly selected task next to another in the permutation.Source: §5.3 · pp. 19–20, Figure 6 · p. 20
  • The algorithm stops when the Pareto frontier remains unchanged for a specified number of generations.Source: §5.3 · p. 20

6 Experiments

The experiments compare objective-variable choices and test MOGA-CSP across missions with different configurations. Optimizing distance and makespan approximates the Pareto frontier well in most cases, although more complex problems require more generations.

6.1 Experimental setup

6.2 Comparative Assessment of objective variables

  • Individually optimizing UAV count or makespan had not converged by generation 300; distance achieved the best rating and nearly best flight time while also optimizing cost.Source: §6.2 · pp. 22–23, Table 8 · p. 22
  • Distance and makespan were selected because they gave medium results across all variables; distance with flight time or cost rated higher but performed poorly on UAV count and makespan.Source: §6.2 · p. 23
  • Optimizing all six variables produced worse averages than the selected distance-and-makespan combination and its rating value.Source: §6.2 · p. 24, Table 10 · p. 24

6.3 Evaluation of the algorithm results

  • Datasets 1–3 converged quickly, while datasets 4–5 converged near generation 50; dataset 4d performed worse after missing the best distance solution.Source: §6.3 · p. 25, Figure 7 · p. 25
  • Mission 5, with 7 tasks, 5 UAVs, and 3 GCSs, converged at generation 122 with hypervolume close to the optimum Pareto frontier.Source: §6.3 · p. 25
  • Distance-and-makespan MOGA-CSP approximates the Pareto frontier well in most datasets, but needs more generations as problem complexity, especially the number of GCSs, increases.Source: §6.3 · p. 25

7 Discussion

The discussion presents multi-GCS UAV mission planning with task dependencies, no-fly-zone avoidance, and timing constraints, then describes a hybrid genetic-algorithm and CSP approach. Across the tested datasets it reports good solutions, while noting that greater complexity requires more generations.

7 Discussion

  • The mission-planning problem includes task dependencies, no-fly-zone avoidance, and time computations in task assignment.Source: §7 · pp. 25–26
  • The problem is modeled as a Temporal CSP with variables for assignments, ordering, GCSs, flight profiles, and sensors, subject to temporal, dependency, autonomy, and distance constraints.Source: §7 · p. 26
  • MOGA-CSP uses a two-phase fitness function: CSP-based penalties check validity, then a multi-objective function seeks the Pareto frontier; its genetic operators and stopping criteria are tailored to the approach.Source: §7 · p. 26
  • Across the designed datasets, distance and makespan gave the best combination for good results across variables, and MOGA-CSP converged to the optimal frontier in most cases; greater complexity required more generations.Source: §7 · p. 26
  • Future work proposes comparisons with SPEA2, meta-evolutionary parameter tuning, and a decision-making layer for operator selection of objectives and solutions.Source: §7 · p. 26
Loading 2402.06504v1…