research-article

A knee point based evolutionary multi-objective optimization for mission planning problems

Authors:

Cristian Ramirez-Atencia,

Sanaz Mostaghim,

David CamachoAuthors Info & Claims

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 1216 - 1223

https://doi.org/10.1145/3071178.3071319

Published: 01 July 2017 Publication History

Abstract

The current boom of Unmanned Aerial Vehicles (UAVs) is increasing the number of potential industrial and research applications. One of the most demanded topics in this area is related to the automated planning of a UAVs swarm, controlled by one or several Ground Control Stations (GCSs). In this context, there are several variables that influence the selection of the most appropriate plan, such as the makespan, the cost or the risk of the mission. This problem can be seen as a Multi-Objective Optimization Problem (MOP). On previous approaches, the problem was modelled as a Constraint Satisfaction Problem (CSP) and solved using a Multi-Objective Genetic Algorithm (MOGA), so a Pareto Optimal Frontier (POF) was obtained. The main problem with this approach is based on the large number of obtained solutions, which hinders the selection of the best solution. This paper presents a new algorithm that has been designed to obtain the most significant solutions in the POF. This approach is based on Knee Points applied to MOGA. The new algorithm has been proved in a real scenario with different number of optimization variables, the experimental results show a significant improvement of the algorithm performance.

References

[1]

James F Allen. 1983. Maintaining knowledge about temporal intervals. Commun. ACM 26, 11 (1983), 832--843.

Digital Library

[2]

Slim Bechikh, Lamjed Ben Said, and Khaled Ghédira. 2011. Searching for knee regions of the Pareto front using mobile reference points. Soft Computing 15, 9 (2011), 1807--1823.

Digital Library

[3]

Jürgen Branke, Kalyanmoy Deb, Henning Dierolf, and Matthias Osswald. 2004. Finding knees in multi-objective optimization. In Parallel Problem Solving from Nature - PPSN VIII. PPSN 2004. Lecture Notes in Computer Science, X. Yao (Ed.), Vol. 3242. Springer, Berlin, Heidelberg, 722--731.

[4]

Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. Evolutionary Computation 6, 2 (2002), 182--197.

Digital Library

[5]

Kalyanmoy Deb, Pawan Zope, and Abhishek Jain. 2003. Distributed computing of pareto-optimal solutions with evolutionary algorithms. In International Conference on Evolutionary Multi-Criterion Optimization, Vol. 2632. Springer, 534--549.

Digital Library

[6]

Xingxing Hao and Jing Liu. 2017. A multiagent evolutionary algorithm with direct and indirect combined representation for constraint satisfaction problems. Soft Computing 21, 3 (2017), 781--793.

Digital Library

[7]

Sara Perez-Carabaza, Eva Besada-Portas, José Antonio López Orozco, and Jesús Manuel de la Cruz. 2016. A Real World Multi-UAV Evolutionary Planner for Minimum Time Target Detection. In Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, Denver, CO, USA, July 20 -- 24, 2016. 981--988.

Digital Library

[8]

Robin C Purshouse, Kalyanmoy Deb, Maszatul M Mansor, Sanaz Mostaghim, and Rui Wang. 2014. A review of hybrid evolutionary multiple criteria decision making methods. In 2014 IEEE congress on evolutionary computation (CEC). IEEE, 1147--1154.

[9]

Cristian Ramirez-Atencia, Gema Bello-Orgaz, Maria D R-Moreno, and David Camacho. 2015. Performance Evaluation of Multi-UAV Cooperative Mission Planning Models. In Computational Collective Intelligence. Springer International Publishing, 203--212.

[10]

Cristian Ramirez-Atencia, Gema Bello-Orgaz, Maria D. R-Moreno, and David Camacho. 2016. Solving Complex Multi-UAV Mission Planning Problems using Multi-objective Genetic Algorithms. Soft Computing (2016), 1--18.

[11]

Víctor Rodríguez-Fernández, Héctor D Menéndez, and David Camacho. 2017. Analysing temporal performance profiles of UAV operators using time series clustering. Expert Systems with Applications 70 (2017), 103--118.

[12]

J. J. Roldn, J. del Cerro, and A. Barrientos. 2015. A proposal of methodology for multi-UAV mission modeling. In 2015 23rd Mediterranean Conference on Control and Automation (MED). 1--7.

[13]

J. J. Ruiz, J. R. Martinez de Dios, J. A. Cobano, and A. Ollero. 2016. A multipayload simulator for cooperative UAS missions. In 2016 International Conference on Unmanned Aircraft Systems (ICUAS). 1192--1199.

[14]

Oliver Schütze, Marco Laumanns, and Carlos A. Coello Coello. 2008. Approximating the knee of an MOP with stochastic search algorithms. In Parallel Problem Solving from Nature fi PPSN X. PPSN 2008. Lecture Notes in Computer Science, G. Rudolph, T. Jansen, N. Beume, S. Lucas, and C. Poloni (Eds.), Vol. 5199. Springer Berlin Heidelberg, 795--804.

[15]

Heiner Zille, Hisao Ishibuchi, Sanaz Mostaghim, and Yusuke Nojima. 2016. Weighted Optimization Framework for Large-scale Multi-objective Optimization. In Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion. ACM, 83--84.

Digital Library

Cited By

Tang JWang HJin Y(2025)Knee-oriented expensive many-objective optimization via aggregation-dominance: A multi-task perspectiveSwarm and Evolutionary Computation10.1016/j.swevo.2024.10181392(101813)Online publication date: Feb-2025
https://doi.org/10.1016/j.swevo.2024.101813
Sun YLi S(2024)A knee-oriented many-objective differential evolution with bi-strategy and Manhattan distance-domination rangeSwarm and Evolutionary Computation10.1016/j.swevo.2024.10163789(101637)Online publication date: Aug-2024
https://doi.org/10.1016/j.swevo.2024.101637
Zhang TTan QZhang THe LYu XZhang S(2024)A multi-objective optimization decision-making methodology for fostering synergies in the water-energy-food nexusJournal of Cleaner Production10.1016/j.jclepro.2024.144051(144051)Online publication date: Oct-2024
https://doi.org/10.1016/j.jclepro.2024.144051
Show More Cited By

Index Terms

Recommendations

Approximate non-dominated sorting for evolutionary many-objective optimization

Non-dominated sorting has widely been adopted and shown to be very effective in dominance based evolutionary multi-objective optimization where the number of objectives is two or three. In dealing with many-objective optimization problems, where the ...
Solving complex multi-UAV mission planning problems using multi-objective genetic algorithms

Due to recent booming of unmanned air vehicles (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 ...
A Hybrid MOGA-CSP for Multi-UAV Mission Planning
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

Mission Planning Problem for a large number of Unmanned Air Vehicles (UAV) consists of a set of locations to visit in different time windows, and the actions that the vehicle can perform based on its features such as the sensors, speed or fuel capacity. ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

July 2017

1427 pages

ISBN:9781450349208

DOI:10.1145/3071178

General Chair:
Peter A. N. Bosman
Centrum Wiskunde & Informatica (CWI)

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Spanish Ministry of Economy and Competitivity
European Union's Justice Program
Airbus Defence & Space
Comunidad Autonoma de Madrid
European Regional Development Fund FEDER

Conference

GECCO '17

Sponsor:

SIGEVO

GECCO '17: Genetic and Evolutionary Computation Conference

July 15 - 19, 2017

Berlin, Germany

Acceptance Rates

GECCO '17 Paper Acceptance Rate 178 of 462 submissions, 39%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
344
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tang JWang HJin Y(2025)Knee-oriented expensive many-objective optimization via aggregation-dominance: A multi-task perspectiveSwarm and Evolutionary Computation10.1016/j.swevo.2024.10181392(101813)Online publication date: Feb-2025
https://doi.org/10.1016/j.swevo.2024.101813
Sun YLi S(2024)A knee-oriented many-objective differential evolution with bi-strategy and Manhattan distance-domination rangeSwarm and Evolutionary Computation10.1016/j.swevo.2024.10163789(101637)Online publication date: Aug-2024
https://doi.org/10.1016/j.swevo.2024.101637
Zhang TTan QZhang THe LYu XZhang S(2024)A multi-objective optimization decision-making methodology for fostering synergies in the water-energy-food nexusJournal of Cleaner Production10.1016/j.jclepro.2024.144051(144051)Online publication date: Oct-2024
https://doi.org/10.1016/j.jclepro.2024.144051
Duxbury DPaton NKeane J(2024)Dynamic decision making for situational awareness using drones: Requirements, identification and comparison of decision support methodsExpert Systems with Applications10.1016/j.eswa.2024.124057252(124057)Online publication date: Oct-2024
https://doi.org/10.1016/j.eswa.2024.124057
Wang CSun HWei LHu Z(2024)A novel knee-guided algorithm based on frequency analysis for non-cyclic dynamic multiobjective optimization problemsExpert Systems with Applications10.1016/j.eswa.2023.121538237(121538)Online publication date: Mar-2024
https://doi.org/10.1016/j.eswa.2023.121538
Zhang HChen QXue BBanzhaf WZhang M(2024)Improving Generalization of Evolutionary Feature Construction with Minimal Complexity Knee Points in RegressionGenetic Programming10.1007/978-3-031-56957-9_9(142-158)Online publication date: 28-Mar-2024
https://doi.org/10.1007/978-3-031-56957-9_9
Saxena DMittal SKapoor SDeb K(2023)A Localized High-Fidelity-Dominance-Based Many-Objective Evolutionary AlgorithmIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.318806427:4(923-937)Online publication date: Aug-2023
https://doi.org/10.1109/TEVC.2022.3188064
Tang JWang HXiong L(2023)Surrogate-assisted multi-objective optimization via knee-oriented Pareto front estimationSwarm and Evolutionary Computation10.1016/j.swevo.2023.10125277(101252)Online publication date: Mar-2023
https://doi.org/10.1016/j.swevo.2023.101252
Yu GMa LJin YDu WLiu QZhang H(2022)A Survey on Knee-Oriented Multiobjective Evolutionary OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.314488026:6(1452-1472)Online publication date: Dec-2022
https://doi.org/10.1109/TEVC.2022.3144880
Li KNie HGao HYao X(2022)Posterior Decision Making Based on Decomposition-Driven Knee Point IdentificationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2021.311612126:6(1409-1423)Online publication date: Dec-2022
https://doi.org/10.1109/TEVC.2021.3116121
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten