Call Us :+34 914972288
Email :
aida.research@uam.es
Publications
- HomePublications
Ant Colony Optimization behavioral patterns Clustering Computational Intelligence Computer-based Education Computer-based Simulation Constraint Satisfaction Problems CSP-graph based representation Data Analysis Data Mining eLearning Genetic Algorithms Graph Theory Human-Machine Interaction Information Extraction knowledge-based Mission Planning Multi-agents systems Multi-objective Algorithms Multi-objective Optimization Normalized Compression Distance Planning Semantic Web Social Networks Temporal Constraint Satisfaction Problems Twitter Unmanned Aircraft Systems Videogames Virtual World Web Services
2016 |
Bello-Orgaz, Gema; Ramirez-Atencia, Cristian; Fradera-Gil, Jaime; Camacho, David GAMPP: Genetic Algorithm for UAV Mission Planning Problems Incollection Intelligent Distributed Computing IX, pp. 167–176, Springer International Publishing, 2016. Abstract | Links | BibTeX | Tags: Genetic Algorithms, Mission Planning, Unmanned Aircraft Systems @incollection{bello2016gampp, title = {GAMPP: Genetic Algorithm for UAV Mission Planning Problems}, author = {Gema Bello-Orgaz and Cristian Ramirez-Atencia and Jaime Fradera-Gil and David Camacho}, url = {http://aida.ii.uam.es/wp-content/uploads/2015/11/IDC15_BelloOrgazEtAl.pdf}, year = {2016}, date = {2016-01-01}, booktitle = {Intelligent Distributed Computing IX}, pages = {167--176}, publisher = {Springer International Publishing}, abstract = {Due to the rapid development of the UAVs capabilities, these are being incorporated into many fields to perform increasingly complex tasks. Some of these tasks are becoming very important because they involve a high risk to the vehicle driver, such as detecting forest fires or rescue tasks, while using UAVs avoids risking human lives. Recent researches on artificial intelligence techniques applied to these systems provide a new degree of high-level autonomy of them. Mission planning for teams of UAVs can be defined as the planning process of locations to visit (waypoints) and the vehicle actions to do (loading/dropping a load, taking videos/pictures, acquiring information), typically over a time period. Currently, UAVs are controlled remotely by human operators from ground control stations, or use rudimentary systems. This paper presents a new Genetic Algorithm for solving Mission Planning Problems (GAMPP) using a cooperative team of UAVs. The fitness function has been designed combining several measures to look for optimal solutions minimizing the fuel consumption and the mission time (or makespan). The algorithm has been experimentally tested through several missions where its complexity is incrementally modified to measure the scalability of the problem. Experimental results show that the new algorithm is able to obtain good solutions improving the runtime of a previous approach based on CSPs.}, keywords = {Genetic Algorithms, Mission Planning, Unmanned Aircraft Systems}, pubstate = {published}, tppubtype = {incollection} } Due to the rapid development of the UAVs capabilities, these are being incorporated into many fields to perform increasingly complex tasks. Some of these tasks are becoming very important because they involve a high risk to the vehicle driver, such as detecting forest fires or rescue tasks, while using UAVs avoids risking human lives. Recent researches on artificial intelligence techniques applied to these systems provide a new degree of high-level autonomy of them. Mission planning for teams of UAVs can be defined as the planning process of locations to visit (waypoints) and the vehicle actions to do (loading/dropping a load, taking videos/pictures, acquiring information), typically over a time period. Currently, UAVs are controlled remotely by human operators from ground control stations, or use rudimentary systems. This paper presents a new Genetic Algorithm for solving Mission Planning Problems (GAMPP) using a cooperative team of UAVs. The fitness function has been designed combining several measures to look for optimal solutions minimizing the fuel consumption and the mission time (or makespan). The algorithm has been experimentally tested through several missions where its complexity is incrementally modified to measure the scalability of the problem. Experimental results show that the new algorithm is able to obtain good solutions improving the runtime of a previous approach based on CSPs. |
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. |
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. |
Rodríguez-Fernández, Víctor; Menéndez, Héctor D; Camacho, David Diseño de un Simulador de Bajo Coste para Vehículos Aéreos no Tripulados Inproceedings Actas del X Congreso español sobre metaheurísticas, algoritmos evolutivos y bioinspirados: MAEB, pp. 447-454, Mérida, Cáceres, 2015, ISBN: 978-84-697-2150-6. Abstract | Links | BibTeX | Tags: Computer-based Simulation, Unmanned Aircraft Systems, Web Application Development @inproceedings{@inproceedings, title = {Diseño de un Simulador de Bajo Coste para Vehículos Aéreos no Tripulados}, author = {Víctor Rodríguez-Fernández and Héctor D Menéndez and David Camacho}, url = {http://aida.ii.uam.es/wp-content/uploads/2015/05/RodriguezMenendezCamacho.pdf}, isbn = {978-84-697-2150-6}, year = {2015}, date = {2015-02-04}, booktitle = {Actas del X Congreso español sobre metaheurísticas, algoritmos evolutivos y bioinspirados: MAEB}, pages = {447-454}, address = {Mérida, Cáceres}, abstract = {La utilización de vehículos aéreos no tripulados, o Unmanned Aircraft Vehicles (UAVs), se ha popularizado enormemente en los últimos tiempos. Estos nuevos sistemas, introducidos en su mayoría por Google, han ganado una importante relevancia, dado que podrían suponer una mejora destacable en la seguridad ciudadana y tienen muchísimas aplicaciones a niveles profesionales dentro de campos muy variados, como la agricultura o el envío postal de paquetes. Sin embargo, el coste a la hora de realizar pruebas en entornos reales con estos dispositivos es muy elevado, por eso se crean simuladores capaces de poner a prueba distintas estrategias a la hora de planificar misiones en estos dispositivos. Este trabajo presenta un simulador orientado a este tipo de sistemas. Este simulador pretende ser una aproximación de bajo coste y fácilmente distribuible, que ayude a simular misiones llevadas a cabo por múltiples drones. Para evaluar su eficacia, se le ha sometido a pruebas de estrés con miles de usuarios, donde ha demostrado tener una respuesta potencialmente competitiva.}, keywords = {Computer-based Simulation, Unmanned Aircraft Systems, Web Application Development}, pubstate = {published}, tppubtype = {inproceedings} } La utilización de vehículos aéreos no tripulados, o Unmanned Aircraft Vehicles (UAVs), se ha popularizado enormemente en los últimos tiempos. Estos nuevos sistemas, introducidos en su mayoría por Google, han ganado una importante relevancia, dado que podrían suponer una mejora destacable en la seguridad ciudadana y tienen muchísimas aplicaciones a niveles profesionales dentro de campos muy variados, como la agricultura o el envío postal de paquetes. Sin embargo, el coste a la hora de realizar pruebas en entornos reales con estos dispositivos es muy elevado, por eso se crean simuladores capaces de poner a prueba distintas estrategias a la hora de planificar misiones en estos dispositivos. Este trabajo presenta un simulador orientado a este tipo de sistemas. Este simulador pretende ser una aproximación de bajo coste y fácilmente distribuible, que ayude a simular misiones llevadas a cabo por múltiples drones. Para evaluar su eficacia, se le ha sometido a pruebas de estrés con miles de usuarios, donde ha demostrado tener una respuesta potencialmente competitiva. |
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. |
Ramírez-Atencia, Cristian; Orgaz, Gema Bello; Rodríguez-Moreno, María Dolores; Camacho, David Performance Evaluation of Multi-UAV Cooperative Mission Planning Models Inproceedings Computational Collective Intelligence - 7th International Conference, ICCCI 2015, Madrid, Spain, September 21-23, 2015, Proceedings, Part II, pp. 203–212, 2015. Abstract | Links | BibTeX | Tags: branch and bound, Constraint Satisfaction Problems, Mission Planning, Unmanned Aircraft Systems @inproceedings{DBLP:conf/iccci/Ramirez-Atencia15, title = {Performance Evaluation of Multi-UAV Cooperative Mission Planning Models}, author = {Cristian Ramírez-Atencia and Gema Bello Orgaz and María Dolores Rodríguez-Moreno and David Camacho}, url = {http://dx.doi.org/10.1007/978-3-319-24306-1_20 http://aida.ii.uam.es/wp-content/uploads/2015/09/ramirez-atenciaPerformance.pdf}, year = {2015}, date = {2015-01-01}, booktitle = {Computational Collective Intelligence - 7th International Conference, ICCCI 2015, Madrid, Spain, September 21-23, 2015, Proceedings, Part II}, pages = {203--212}, crossref = {DBLP:conf/iccci/2015-2}, abstract = {The Multi-UAV Cooperative Mission Planning Problem (MCMPP) is a complex problem which can be represented with a lower or higher level of complexity. In this paper we present a MCMPP which is modelled as a Constraint Satisfaction Problem (CSP) with 5 increasing levels of complexity. Each level adds additional variables and constraints to the problem. Using previous models, we solve the problem using a Branch and Bound search designed to minimize the fuel consumption and number of UAVs employed in the mission, and the results show how runtime increases as the level of complexity increases in most cases, as expected, but there are some cases where the opposite happens.}, keywords = {branch and bound, Constraint Satisfaction Problems, Mission Planning, Unmanned Aircraft Systems}, pubstate = {published}, tppubtype = {inproceedings} } The Multi-UAV Cooperative Mission Planning Problem (MCMPP) is a complex problem which can be represented with a lower or higher level of complexity. In this paper we present a MCMPP which is modelled as a Constraint Satisfaction Problem (CSP) with 5 increasing levels of complexity. Each level adds additional variables and constraints to the problem. Using previous models, we solve the problem using a Branch and Bound search designed to minimize the fuel consumption and number of UAVs employed in the mission, and the results show how runtime increases as the level of complexity increases in most cases, as expected, but there are some cases where the opposite happens. |
2014 |
Ramirez-Atencia, Cristian; Bello-Orgaz, Gema; Camacho, David; others, Solving UAV Mission Planning based on Temporal Constaint Satisfaction Problem using Genetic Algorithms Miscellaneous Doctoral Program Proceedings of The 20th International Conference on Principles and Practice of Constraint Programming (CP 2014), 2014. Abstract | Links | BibTeX | Tags: Genetic Algorithms, Mission Planning, Temporal Constraint Satisfaction Problems, Unmanned Aircraft Systems @misc{ramirez2014solving, title = {Solving UAV Mission Planning based on Temporal Constaint Satisfaction Problem using Genetic Algorithms}, author = {Cristian Ramirez-Atencia and Gema Bello-Orgaz and David Camacho and others}, url = {http://aida.ii.uam.es/wp-content/uploads/2014/12/RamirezEtAl.pdf}, year = {2014}, date = {2014-09-12}, abstract = {The problem of Mission Planning for a large number of Unmanned Air Vehicles (UAV) consists of a set of locations to visit in di erent time windows, and the actions that the vehicle can perform based on its features such as the payload, speed or fuel capacity. We study how this problem can be formulated as a Temporal Constraint Satisfaction Problem (TCSP). This problem contains several constraints assuring UAVs are assigned to tasks they have enough characteristics to perform, and soft-constraints for optimizing the time and fuel spent in the process. Our goal is to implement this model and then try to solve it using Genetic Algorithms (GAs). For this purpose, we will carry out a mission simulation containing m UAVs with di erent sensors and characteristics located in di erent waypoints, and n requested tasks varying mission priorities. The GA will match the model constraints and use a multi-objective function in order to minimize the cost.}, howpublished = {Doctoral Program Proceedings of The 20th International Conference on Principles and Practice of Constraint Programming (CP 2014)}, keywords = {Genetic Algorithms, Mission Planning, Temporal Constraint Satisfaction Problems, Unmanned Aircraft Systems}, pubstate = {published}, tppubtype = {misc} } The problem of Mission Planning for a large number of Unmanned Air Vehicles (UAV) consists of a set of locations to visit in di erent time windows, and the actions that the vehicle can perform based on its features such as the payload, speed or fuel capacity. We study how this problem can be formulated as a Temporal Constraint Satisfaction Problem (TCSP). This problem contains several constraints assuring UAVs are assigned to tasks they have enough characteristics to perform, and soft-constraints for optimizing the time and fuel spent in the process. Our goal is to implement this model and then try to solve it using Genetic Algorithms (GAs). For this purpose, we will carry out a mission simulation containing m UAVs with di erent sensors and characteristics located in di erent waypoints, and n requested tasks varying mission priorities. The GA will match the model constraints and use a multi-objective function in order to minimize the cost. |
Ramirez-Atencia, Cristian; Bello-Orgaz, Gema; Camacho, David; others, A simple CSP-based model for Unmanned Air Vehicle Mission Planning Inproceedings Innovations in Intelligent Systems and Applications (INISTA) Proceedings, 2014 IEEE International Symposium on, pp. 146–153, IEEE 2014. Abstract | Links | BibTeX | Tags: Backtracking, Mission Planning, Temporal Constraint Satisfaction Problems, Unmanned Aircraft Systems @inproceedings{ramirez2014simple, title = {A simple CSP-based model for Unmanned Air Vehicle Mission Planning}, author = {Cristian Ramirez-Atencia and Gema Bello-Orgaz and David Camacho and others}, url = {http://aida.ii.uam.es/wp-content/uploads/2014/12/Ramirez-AtenciaEtAl.pdf}, year = {2014}, date = {2014-01-01}, booktitle = {Innovations in Intelligent Systems and Applications (INISTA) Proceedings, 2014 IEEE International Symposium on}, pages = {146--153}, organization = {IEEE}, abstract = {The problem of Mission Planning for a large number of Unmanned Air Vehicles (UAV) can be formulated as a Temporal Constraint Satisfaction Problem (TCSP). It consists on a set of locations that should visit in different time windows, and the actions that the vehicle can perform based on its features such as the payload, speed or fuel capacity. In this paper, a temporal constraint model is implemented and tested by performing Backtracking search in several missions where its complexity has been incrementally modified. The experimental phase consists on two different phases. On the one hand, several mission simulations containing (n) UAVs using different sensors and characteristics located in different waypoints, and (m) requested tasks varying mission priorities have been carried out. On the other hand, the second experimental phase uses a backtracking algorithm to look through the whole solutions space to measure the scalability of the problem. This scalability has been measured as a relation between the number of tasks to be performed in the mission and the number of UAVs needed to perform it.}, keywords = {Backtracking, Mission Planning, Temporal Constraint Satisfaction Problems, Unmanned Aircraft Systems}, pubstate = {published}, tppubtype = {inproceedings} } The problem of Mission Planning for a large number of Unmanned Air Vehicles (UAV) can be formulated as a Temporal Constraint Satisfaction Problem (TCSP). It consists on a set of locations that should visit in different time windows, and the actions that the vehicle can perform based on its features such as the payload, speed or fuel capacity. In this paper, a temporal constraint model is implemented and tested by performing Backtracking search in several missions where its complexity has been incrementally modified. The experimental phase consists on two different phases. On the one hand, several mission simulations containing (n) UAVs using different sensors and characteristics located in different waypoints, and (m) requested tasks varying mission priorities have been carried out. On the other hand, the second experimental phase uses a backtracking algorithm to look through the whole solutions space to measure the scalability of the problem. This scalability has been measured as a relation between the number of tasks to be performed in the mission and the number of UAVs needed to perform it. |
Ramirez-Atencia, Cristian; Bello-Orgaz, Gema; R-Moreno, Maria D; Camacho, David Branching to Find Feasible Solutions in Unmanned Air Vehicle Mission Planning Incollection Intelligent Data Engineering and Automated Learning--IDEAL 2014, 8669 , pp. 286–294, Springer International Publishing, 2014. Abstract | Links | BibTeX | Tags: branch and bound, Mission Planning, Temporal Constraint Satisfaction Problems, Unmanned Aircraft Systems @incollection{ramirez2014branching, title = {Branching to Find Feasible Solutions in Unmanned Air Vehicle Mission Planning}, 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/2014/12/Ramirez-AtenciaEtAl1.pdf}, year = {2014}, date = {2014-01-01}, booktitle = {Intelligent Data Engineering and Automated Learning--IDEAL 2014}, volume = {8669}, pages = {286--294}, publisher = {Springer International Publishing}, abstract = {Mission Planning is a classical problem that has been traditionally studied in several cases from Robotics to Space missions. This kind of problems can be extremely difficult in real and dynamic scenarios. This paper provides a first analysis for mission planning to Unmanned Air Vehicles (UAVs), where sensors and other equipment of UAVs to perform a task are modelled based on Temporal Constraint Satisfaction Problems (TCSPs). In this model, a set of resources and temporal constraints are designed to represent the main characteristics (task time, fuel consumption, ...) of this kind of aircrafts. Using this simplified TCSP model, and a Branch and Bound (B&B) search algorithm, a set of feasible solutions will be found trying to minimize the fuel cost, flight time spent and the number of UAVs used in the mission. Finally, some experiments will be carried out to validate both the quality of the solutions found and the spent runtime to found them.}, keywords = {branch and bound, Mission Planning, Temporal Constraint Satisfaction Problems, Unmanned Aircraft Systems}, pubstate = {published}, tppubtype = {incollection} } Mission Planning is a classical problem that has been traditionally studied in several cases from Robotics to Space missions. This kind of problems can be extremely difficult in real and dynamic scenarios. This paper provides a first analysis for mission planning to Unmanned Air Vehicles (UAVs), where sensors and other equipment of UAVs to perform a task are modelled based on Temporal Constraint Satisfaction Problems (TCSPs). In this model, a set of resources and temporal constraints are designed to represent the main characteristics (task time, fuel consumption, ...) of this kind of aircrafts. Using this simplified TCSP model, and a Branch and Bound (B&B) search algorithm, a set of feasible solutions will be found trying to minimize the fuel cost, flight time spent and the number of UAVs used in the mission. Finally, some experiments will be carried out to validate both the quality of the solutions found and the spent runtime to found them. |