Publications
- HomePublications
2017 |
Ramirez-Atencia, Cristian; Mostaghim, Sanaz; Camacho, David A Knee Point Based Evolutionary Multi-objective Optimization for Mission Planning Problems Inproceedings Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1216–1223, ACM, Berlin, Germany, 2017, ISBN: 978-1-4503-4920-8. Abstract | Links | BibTeX | Tags: Constraint Satisfaction Problems, evolutionary multi-objective optimization, knee point, Mission Planning, Multi-objective Optimization, UAVs @inproceedings{Ramirez-Atencia2017b, title = {A Knee Point Based Evolutionary Multi-objective Optimization for Mission Planning Problems}, author = {Cristian Ramirez-Atencia and Sanaz Mostaghim and David Camacho}, url = {http://doi.acm.org/10.1145/3071178.3071319}, doi = {10.1145/3071178.3071319}, isbn = {978-1-4503-4920-8}, year = {2017}, date = {2017-01-01}, booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference}, pages = {1216--1223}, publisher = {ACM}, address = {Berlin, Germany}, series = {GECCO '17}, 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.}, keywords = {Constraint Satisfaction Problems, evolutionary multi-objective optimization, knee point, Mission Planning, Multi-objective Optimization, UAVs}, pubstate = {published}, tppubtype = {inproceedings} } 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. |
2016 |
Ramirez-Atencia, Cristian; Bello-Orgaz, Gema; R-Moreno, Maria D; Camacho, David A Weighted Penalty Fitness for a Hybrid MOGA-CSP to solve Mission Planning Problems Inproceedings XI Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados (MAEB 2016), pp. 305–314, 2016. Abstract | Links | BibTeX | Tags: Constraint Satisfaction Problems, Mission Planning, Muli-UAV, Multi-Objective Genetic Algorithm, Multi-objective Optimization, NSGA2, Unmanned Aerial Vehicles @inproceedings{Ramirez-Atencia2016a, title = {A Weighted Penalty Fitness for a Hybrid MOGA-CSP to solve Mission Planning Problems}, author = {Cristian Ramirez-Atencia and Gema Bello-Orgaz and Maria D R-Moreno and David Camacho}, url = {http://aida.ii.uam.es/wp-content/uploads/2017/03/A-Weighted-Penalty-Fitness-for-a-Hybrid-MOGA-CSP-to-solve-Mission-Planning-Problems.pdf}, year = {2016}, date = {2016-01-01}, booktitle = {XI Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados (MAEB 2016)}, pages = {305--314}, abstract = {Unmanned Aerial Vehicles (UAVs) are currently booming due to their high number of potential applications. In Mission Planning problems, several tasks must be performed by a team of UAVs, under the supervision of one or more Ground Control Stations (GCSs). In our approach, we have modelled the problem as a Constraint Satisfaction Problem (CSP), and solved it using a Multi-Objective Genetic Algorithm (MOGA). The algorithm has been designed to minimize several variables of the mission such as the fuel consumption or the makespan. In addition, the fitness function takes a new consideration when solutions are not valid. It uses the number of constraints fulfilled for each solution as a weighted penalty function. In this way, the number of constraints fulfilled is maximized in the elitism phase of the MOGA. Results show that the approach outperforms the convergence with respect to previous results.}, keywords = {Constraint Satisfaction Problems, Mission Planning, Muli-UAV, Multi-Objective Genetic Algorithm, Multi-objective Optimization, NSGA2, Unmanned Aerial Vehicles}, pubstate = {published}, tppubtype = {inproceedings} } Unmanned Aerial Vehicles (UAVs) are currently booming due to their high number of potential applications. In Mission Planning problems, several tasks must be performed by a team of UAVs, under the supervision of one or more Ground Control Stations (GCSs). In our approach, we have modelled the problem as a Constraint Satisfaction Problem (CSP), and solved it using a Multi-Objective Genetic Algorithm (MOGA). The algorithm has been designed to minimize several variables of the mission such as the fuel consumption or the makespan. In addition, the fitness function takes a new consideration when solutions are not valid. It uses the number of constraints fulfilled for each solution as a weighted penalty function. In this way, the number of constraints fulfilled is maximized in the elitism phase of the MOGA. Results show that the approach outperforms the convergence with respect to previous results. |
Ramirez-Atencia, Cristian; Bello-Orgaz, Gema; R-Moreno, Maria D; Camacho, David MOGAMR: A Multi-Objective Genetic Algorithm for Real-Time Mission Replanning Inproceedings 2016 IEEE Symposium Series on Computational Intelligence (SSCI), 2016, ISBN: 978-1-5090-4240-1, 978-1-5090-4241-8. Abstract | Links | BibTeX | Tags: Constraint Satisfaction Problems, Metaheuristics, Mission Planning, Multi-objective Optimization, NSGA2, Replanning, Unmanned Aircraft Systems @inproceedings{Ramirez-Atencia2016b, title = {MOGAMR: A Multi-Objective Genetic Algorithm for Real-Time Mission Replanning}, author = {Cristian Ramirez-Atencia and Gema Bello-Orgaz and Maria D R-Moreno and David Camacho}, doi = {10.1109/SSCI.2016.7850235}, isbn = {978-1-5090-4240-1, 978-1-5090-4241-8}, year = {2016}, date = {2016-01-01}, booktitle = {2016 IEEE Symposium Series on Computational Intelligence (SSCI)}, abstract = {From the last few years the interest and repercussion on Unmanned Aerial Vehicle (UAV) technologies have been extended from pure military applications to industrial and societal applications. One of the basic tasks to any UAV problems is related to the Mission Planning. This problem is particularly complex when a set of UAVs is considered. In the field of MultiUAV Mission Planning, some approaches have been carried out in the last years. However, there are few works related to realtime Mission Replanning, which is the focus of this work. In Mission Replanning, some changes in the mission, such as the arrival of new tasks, require to update the preplanned solution as fast as possible. In this paper a Multi-Objective Genetic Algorithm for Mission Replanning (MOGAMR) is proposed to handle this problem. This approach uses a set of previous plans (or solutions), generated using an offlline planning process, in order to initialize the population of the algorithm, then acts as a complete regeneration method. In order to simulate a real-time system we have fixed a time limit of 2 minutes. This has been considered as an appropriate time for a human operator to take a decision. Using this time restriction, a set of experiments adding from 1 to 5 new tasks in the Replanning Problems has been carried out. The experiments show that the algorithm works well with this few number of new tasks during the replanning process generating a set of feasible solutions under the time restriction considered.}, keywords = {Constraint Satisfaction Problems, Metaheuristics, Mission Planning, Multi-objective Optimization, NSGA2, Replanning, Unmanned Aircraft Systems}, pubstate = {published}, tppubtype = {inproceedings} } From the last few years the interest and repercussion on Unmanned Aerial Vehicle (UAV) technologies have been extended from pure military applications to industrial and societal applications. One of the basic tasks to any UAV problems is related to the Mission Planning. This problem is particularly complex when a set of UAVs is considered. In the field of MultiUAV Mission Planning, some approaches have been carried out in the last years. However, there are few works related to realtime Mission Replanning, which is the focus of this work. In Mission Replanning, some changes in the mission, such as the arrival of new tasks, require to update the preplanned solution as fast as possible. In this paper a Multi-Objective Genetic Algorithm for Mission Replanning (MOGAMR) is proposed to handle this problem. This approach uses a set of previous plans (or solutions), generated using an offlline planning process, in order to initialize the population of the algorithm, then acts as a complete regeneration method. In order to simulate a real-time system we have fixed a time limit of 2 minutes. This has been considered as an appropriate time for a human operator to take a decision. Using this time restriction, a set of experiments adding from 1 to 5 new tasks in the Replanning Problems has been carried out. The experiments show that the algorithm works well with this few number of new tasks during the replanning process generating a set of feasible solutions under the time restriction considered. |
Ramirez-Atencia, Cristian; Bello-Orgaz, Gema; R-Moreno, Maria D; Camacho, David Solving complex multi-UAV mission planning problems using multi-objective genetic algorithms Journal Article Soft Computing, In Press , pp. 1–18, 2016, ISSN: 1432-7643; 1433-7479. Abstract | Links | BibTeX | Tags: Constraint Satisfaction Problems, Genetic Algorithms, Mission Planning, Multi-objective Optimization, NSGA2, Unmanned air vehicles @article{Ramirez-Atencia2016c, title = {Solving complex multi-UAV mission planning problems using multi-objective genetic algorithms}, author = {Cristian Ramirez-Atencia and Gema Bello-Orgaz and Maria D R-Moreno and David Camacho}, url = {http://aida.ii.uam.es/wp-content/uploads/2017/03/RamirezEtAl.pdf}, doi = {10.1007/s00500-016-2376-7}, issn = {1432-7643; 1433-7479}, year = {2016}, date = {2016-01-01}, journal = {Soft Computing}, volume = {In Press}, pages = {1--18}, publisher = {Springer Verlag}, 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.}, keywords = {Constraint Satisfaction Problems, Genetic Algorithms, Mission Planning, Multi-objective Optimization, NSGA2, Unmanned air vehicles}, pubstate = {published}, tppubtype = {article} } 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. |
2015 |
RodrÍguez-Fernández, Víctor; Ramirez-Atencia, Cristian; Camacho, David A Summary of Player Assessment in a Multi-UAV Mission Planning Serious Game Inproceedings 2st Congreso de la Sociedad Española para las Ciencias del Videojuego, pp. 186–191, 2015. Abstract | Links | BibTeX | Tags: Mission Planning, Muli-UAV, Multi-objective Optimization, Player Assessment, Serious Games, Unmanned Aircraft Systems @inproceedings{rodriguezsummary, title = {A Summary of Player Assessment in a Multi-UAV Mission Planning Serious Game}, author = {Víctor RodrÍguez-Fernández and Cristian Ramirez-Atencia and David Camacho}, url = {http://aida.ii.uam.es/wp-content/uploads/2015/09/rodriguezsummary.pdf}, year = {2015}, date = {2015-07-31}, booktitle = {2st Congreso de la Sociedad Española para las Ciencias del Videojuego}, journal = {2st Congreso de la Sociedad Española para las Ciencias del Videojuego}, volume = {1394}, pages = {186--191}, abstract = {Mission Planning for a large number of Unmanned Aerial Vehicles (UAVs) involves a set of locations to visit in different time intervals, and the actions that a vehicle must perform depending on its features and sensors. Analyzing how humans solve this problem is sometimes hard due to the complexity of the problem and the lack of data available. This paper presents a summary of a serious videogame-based framework created to assess the quality of the mission plans designed by players, comparing them against the optimal solutions obtained by a Multi-Objective Optimization algorithm.}, keywords = {Mission Planning, Muli-UAV, Multi-objective Optimization, Player Assessment, Serious Games, Unmanned Aircraft Systems}, pubstate = {published}, tppubtype = {inproceedings} } Mission Planning for a large number of Unmanned Aerial Vehicles (UAVs) involves a set of locations to visit in different time intervals, and the actions that a vehicle must perform depending on its features and sensors. Analyzing how humans solve this problem is sometimes hard due to the complexity of the problem and the lack of data available. This paper presents a summary of a serious videogame-based framework created to assess the quality of the mission plans designed by players, comparing them against the optimal solutions obtained by a Multi-Objective Optimization algorithm. |
Ramirez-Atencia, Cristian; Bello-Orgaz, Gema; R-Moreno, María D; Camacho, David A Hybrid MOGA-CSP for Multi-UAV Mission Planning Inproceedings Proceedings of the Companion Publication of the 2015 on Genetic and Evolutionary Computation Conference, pp. 1205–1208, ACM 2015. Links | BibTeX | Tags: Constraint Satisfaction Problems, Genetic Algorithms, Mission Planning, Multi-objective Optimization, Unmanned Aircraft Systems @inproceedings{ramirez2015hybrid, title = {A Hybrid MOGA-CSP for Multi-UAV Mission Planning}, author = {Cristian Ramirez-Atencia and Gema Bello-Orgaz and María D R-Moreno and David Camacho}, url = {http://aida.ii.uam.es/wp-content/uploads/2015/09/ramirez-atenciaHybrid.pdf}, year = {2015}, date = {2015-01-01}, booktitle = {Proceedings of the Companion Publication of the 2015 on Genetic and Evolutionary Computation Conference}, pages = {1205--1208}, organization = {ACM}, keywords = {Constraint Satisfaction Problems, Genetic Algorithms, Mission Planning, Multi-objective Optimization, Unmanned Aircraft Systems}, pubstate = {published}, tppubtype = {inproceedings} } |
Rodriguez-Fernandez, Victor; Ramirez-Atencia, Cristian; Camacho, David A multi-UAV Mission Planning videogame-based framework for player analysis Inproceedings Evolutionary Computation (CEC), 2015 IEEE Congress on, pp. 1490–1497, IEEE 2015. Abstract | Links | BibTeX | Tags: Mission Planning, Multi-objective Optimization, Player Assessment, Serious Games, Unmanned Aircraft Systems @inproceedings{rodriguez2015multi, title = {A multi-UAV Mission Planning videogame-based framework for player analysis}, author = {Victor Rodriguez-Fernandez and Cristian Ramirez-Atencia and David Camacho}, url = {http://aida.ii.uam.es/wp-content/uploads/2015/09/07257064.pdf}, year = {2015}, date = {2015-01-01}, booktitle = {Evolutionary Computation (CEC), 2015 IEEE Congress on}, pages = {1490--1497}, organization = {IEEE}, abstract = {The problem of Mission Planning for a large number of Unmanned Air Vehicles (UAVs) comprises a set of locations to visit in different time windows, and the actions that the vehicle can perform based on its features, such as sensors, speed or fuel consumption. Although this problem is increasingly more supported by Artificial Intelligence systems, nowadays human factors are still critical to guarantee the success of the designed plan. Studying and analyzing how humans solve this problem is sometimes difficult due to the complexity of the problem and the lack of data available. To overcome this problem, we have developed an analysis framework for Multi-UAV Cooperative Mission Planning Problem (MCMPP) based on a videogame that gamifies the problem and allows a player to design plans for multiple UAVs intuitively. On the other hand, we have also developed a mission planner algorithm based on Constraint Satisfaction Problems (CSPs) and solved with a Multi-Objective Branch & Bound (MOBB) method which optimizes the objective variables of the problem and gets the best solutions in the Pareto Optimal Frontier (POF). To prove the environment potential, we have performed a comparative study between the plans generated by a heterogenous group of human players and the solutions obtained by this planner.}, keywords = {Mission Planning, Multi-objective Optimization, Player Assessment, Serious Games, Unmanned Aircraft Systems}, pubstate = {published}, tppubtype = {inproceedings} } The problem of Mission Planning for a large number of Unmanned Air Vehicles (UAVs) comprises a set of locations to visit in different time windows, and the actions that the vehicle can perform based on its features, such as sensors, speed or fuel consumption. Although this problem is increasingly more supported by Artificial Intelligence systems, nowadays human factors are still critical to guarantee the success of the designed plan. Studying and analyzing how humans solve this problem is sometimes difficult due to the complexity of the problem and the lack of data available. To overcome this problem, we have developed an analysis framework for Multi-UAV Cooperative Mission Planning Problem (MCMPP) based on a videogame that gamifies the problem and allows a player to design plans for multiple UAVs intuitively. On the other hand, we have also developed a mission planner algorithm based on Constraint Satisfaction Problems (CSPs) and solved with a Multi-Objective Branch & Bound (MOBB) method which optimizes the objective variables of the problem and gets the best solutions in the Pareto Optimal Frontier (POF). To prove the environment potential, we have performed a comparative study between the plans generated by a heterogenous group of human players and the solutions obtained by this planner. |