nach oben

Soft Computing

Erschienen in:

03.10.2016 | Focus

Solving complex multi-UAV mission planning problems using multi-objective genetic algorithms

verfasst von: Cristian Ramirez-Atencia, Gema Bello-Orgaz, María D. R-Moreno, David Camacho

Erschienen in: Soft Computing | Ausgabe 17/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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 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 involving a team of UAVs and a set of GCSs. A hybrid fitness function has been designed using a constraint satisfaction problem to check whether 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, and distance. 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.

Vorheriger Artikel Optimizing satisfaction in a multi-courses allocation problem combined with a timetabling problem

Nächster Artikel Large neighborhood search for the most strings with few bad columns problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

http://geographiclib.sourceforge.net/.

http://www.gdal.org/.

Adolf F, Andert F (2010) Onboard mission management for a VTOL UAV using sequence and supervisory control, chap. 19, InTech, pp 301–316

Allen JF (1983) Maintaining knowledge about temporal intervals. Commun ACM 26(11):832–843CrossRefMATH

Barták R (1999) Constraint programming: In pursuit of the holy grail. In: Week of Doctoral Students, pp 555–564

Bello-Orgaz G, Camacho D (2014) Evolutionary clustering algorithm for community detection using graph-based information. In: Evolutionary Computation (CEC), 2014 IEEE congress on, pp 930–937

Bello-Orgaz G, Ramirez-Atencia C, Fradera-Gil J, Camacho D (2015) Gampp: genetic algorithm for uav mission planning problems. In: Intelligent distributed computing IX. Springer International Publishing, pp 167–176

Bessière C (2006) Constraint propagation. Found Artif Intell 2:29–83CrossRef

Bessière C, Meseguer P, Freuder E, Larrosa J (1999) On forward checking for non-binary constraint satisfaction. In: Jaffar J (ed) International conference on principles and practice of constraint programming, lecture notes in computer science, vol 1713. Springer, Berlin, pp 88–102

Bethke B, Valenti M, How JP (2008) UAV task assignment. IEEE Robot Autom Mag 15(1):39–44CrossRef

Bin X, Min W, Yanming L, Yu F (2010) Improved genetic algorithm research for route optimization of logistic distribution. In: Proceedings of the 2010 international conference on computational and information sciences, ICCIS ’10, IEEE Computer Society, Washington, pp 1087–1090

Camacho D, Fernandez F, Rodelgo MA (2006) Roboskeleton: an architecture for coordinating robot soccer agents. Eng Appl Artif Intell 19(2):179–188CrossRef

Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. Evol Comput 6(2):182–197CrossRef

Diaz D, Cesta A, Oddi A, Rasconi R, R-Moreno MD (2013) Efficient energy management for autonomous control in rover missions. IEEE Comput Intell Mag 8(4):12–24 Special Issue on Computational Intelligence for Space Systems and OperationsCrossRef

Doherty P, Kvarnström J, Heintz F (2009) A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems. Auton Agent Multi-agent Syst 19(3):332–377CrossRef

Fabiani P, Fuertes V, Piquereau A, Mampey R, Teichteil-Konigsbuch F (2007) Autonomous flight and navigation of VTOL UAVs: from autonomy demonstrations to out-of-sight flights. Aerosp Sci Technol 11(2–3):183–193CrossRef

Fonseca C, Fleming P (1998) Multiobjective optimization and multiple constraint handling with evolutionary algorithms. A unified formulation. IEEE Trans Syst Man Cybern- A: Syst Hum 28(1):26–37CrossRef

Geng L, Zhang Y, Wang J, Fuh J, Teo S (2013) Cooperative task planning for multiple autonomous uavs with graph representation and genetic algorithm. In: Control and automation (ICCA), 10th IEEE international conference on, pp 394–399. IEEE

Gonzalez-Pardo A, Camacho D (2013) A new CSP graph-based representation for ant colony optimization. In: IEEE conference on evolutionary computation (CEC 2013), vol 1, pp 689–696. IEEE

Gonzalez-Pardo A, Palero F, Camacho D (2014) An empirical study on collective intelligence algorithms for video games problem-solving. Comput Inform 34(1):233–253

Hao X, Liu J (2015) A multiagent evolutionary algorithm with direct and indirect combined representation for constraint satisfaction problems. Soft Comput 1–13. doi:10.1007/s00500-015-1815-1

Holland JH (1992) Adaptation in natural and artificial systems. MIT Press, Cambridge

Kendoul F (2012) Survey of advances in guidance, navigation, and control of unmanned rotorcraft systems. J Field Robot 29(2):315–378CrossRef

Kuter U, Sirin E, Parsia B, Nau D, Hendlerb J (2005) Information gathering during planning for web service composition. Web semantics: science, services and agents on the World Wide Web 3(2):183–205. Selected papers from the international semantic web conference, 2004 ISWC, 2004 3rd international semantic web conference, 2004

Kvarnström J, Doherty P (2010) Automated planning for collaborative UAV systems. In: Control automation robotics and vision, pp 1078–1085. IEEE

Lee Yi, Kim YG (2008) Comparison of fuzzy implication operators by means of fuzzy relational products used for intelligent local path-planning of auvs. Soft Comput 13(6):535–549CrossRefMATH

Menendez HD, Barrero DF, Camacho D (2014) A co-evolutionary multi-objective approach for a k-adaptive graph-based clustering algorithm. In: Evolutionary computation (CEC), 2014 IEEE congress on, pp 2724–2731. IEEE

Merino L, Caballero F, Martínez-de Dios JR, Ferruz J, Ollero A (2006) A cooperative perception system for multiple uavs: application to automatic detection of forest fires. J Field Robot 23(3–4):165–184CrossRef

Mouhoub M (2002) Solving temporal constraints in real time and in a dynamic environment. Tech. Rep. WS-02-17, AAAI

Mouhoub M (2004) Reasoning with numeric and symbolic time information. Artif Intell Rev 21(1):25–56CrossRefMATH

Nash A, Daniel K, Koenig S, Felner A (2007) Theta*: any-angle path planning on grids. In: Proceedings of the National Conference on Artificial Intelligence, vol 22. AAAI Press, MIT Press, Menlo Park, Cambridge, London, pp 1177–1183

Pascarella D, Venticinque S, Aversa R, Mattei M, Blasi L (2015) Parallel and distributed computing for uavs trajectory planning. J Ambient Intell Humaniz Comput 6(6):773–782CrossRef

Pereira E, Bencatel R, Correia J, Félix L, Gonçalves G, Morgado J, Sousa J (2009) Unmanned air vehicles for coastal and environmental research. J Coast Res II(56):1557–1561

Ramirez-Atencia C, Bello-Orgaz G, R-Moreno MD, Camacho D (2015a) A hybrid MOGA-CSP for multi-UAV mission planning. In: Proceedings of the companion publication of the 2015 on genetic and evolutionary computation conference. ACM, pp 1205–1208

Ramirez-Atencia C, Bello-Orgaz G, R-Moreno MD, Camacho D (2015b) Performance evaluation of multi-UAV cooperative mission planning models. In: Computational collective intelligence. Springer International Publishing, pp 203–212

Rasmussen S, Shima T (2006) Branch and bound tree search for assigning cooperating uavs to multiple tasks. In: American control conference. IEEE, pp 6–14

Rodríguez-Fernández V, Menéndez HD, Camacho D (2015a) Automatic profile generation for uav operators using a simulation-based training environment. Prog Artif Intell 5(1):37–46

Rodriguez-Fernandez V, Ramirez-Atencia C, Camacho D (2015b) A multi-uav mission planning videogame-based framework for player analysis. In: Evolutionary computation (CEC), 2015 IEEE congress on. IEEE, pp 1490–1497

Rollon E, Larrosa J (2006) Bucket elimination for multiobjective optimization problems. J Heuristics 12(4–5):307–328CrossRefMATH

Rollon E, Larrosa J (2007) Multi-objective Russian doll search. In: Proceedings of the national conference on artificial intelligence, vol 22. AAAI Press, MIT Press, Menlo Park, Cambridge, London, pp 249–254

Savuran H, Karakaya M (2015) Efficient route planning for an unmanned air vehicle deployed on a moving carrier. Soft Comput 20(7):2905–2920CrossRef

Schwalb E, Vila L (1998) Temporal constraints: a survey. Constraints 3(2–3):129–149MathSciNetCrossRefMATH

Soliday SW, et al. (1999) A genetic algorithm model for mission planning and dynamic resource allocation of airborne sensors. In: Proceedings, 1999 IRIS National Symposium on Sensor and Data Fusion. Citeseer

Tang L, Zhu C, Zhang W, Liu Z (2011) Robust mission planning based on nested genetic algorithm. In: Advanced computational intelligence (IWACI), 2011 fourth international workshop on, pp 45–49. IEEE. doi:10.1109/IWACI.2011.6159972

Vachtsevanos G, Tang L, Drozeski G, Gutierrez L (2005) From mission planning to flight control of unmanned aerial vehicles: strategies and implementation tools. Ann Rev Control 29(1):101–115CrossRef

Van Veldhuizen D, Lamont GB, et al. (2000) On measuring multiobjective evolutionary algorithm performance. In: Evolutionary computation, 2000. Proceedings of the 2000 congress on, vol 1. IEEE, pp 204–211

Wagner T, Trautmann H, Martí L (2011) A taxonomy of online stopping criteria for multi-objective evolutionary algorithms. In: Evolutionary multi-criterion optimization. Springer, pp 16–30

Wu J, Zhou G (2006) High-resolution planimetric mapping from uav video for quick-response to natural disaster. In: Geoscience and remote sensing symposium, 2006. IGARSS 2006. IEEE international conference on. IEEE, pp 3333–3336

Zhou A, Qu BY, Li H, Zhao SZ, Suganthan PN, Zhang Q (2011) Multiobjective evolutionary algorithms: a survey of the state of the art. Swarm Evolut Comput 1(1):32–49CrossRef

Zitzler E, Laumanns M, Thiele L (2001) SPEA2: Improving the strength pareto evolutionary algorithm. In: Eurogen, vol. 3242, pp. 95–100

Zitzler E, Laumanns M, Bleuler S (2004) A tutorial on evolutionary multiobjective optimization. In: Metaheuristics for multiobjective optimisation. Springer, pp 3–37

Zitzler E, Brockhoff D, Thiele L (2007) The hypervolume indicator revisited: On the design of pareto-compliant indicators via weighted integration. In: Evolutionary multi-criterion optimization. Springer, pp 862–876

Titel: Solving complex multi-UAV mission planning problems using multi-objective genetic algorithms
verfasst von: Cristian Ramirez-Atencia
Gema Bello-Orgaz
María D. R-Moreno
David Camacho
Publikationsdatum: 03.10.2016
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 17/2017
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-016-2376-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 17/2017

An r-dominance-based preference multi-objective optimization for many-objective optimization

A preference-based multi-objective evolutionary algorithm using preference selection radius

A multi-tier adaptive grid algorithm for the evolutionary multi-objective optimisation of complex problems

Formal framework for distributed swarm computing: abstract model and properties

A binary PSO approach to mine high-utility itemsets

Multi-attribute group decision making approach based on interval-valued intuitionistic fuzzy sets and evidential reasoning methodology