Browsing by Keyword "Constraint satisfaction problem"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Efficiency of tree-search like heuristics to solve complex mixed-integer programming problems applied to space trajectory design(International Astronautical Federation, IAF, 2021) Bellome, A.; Carrillo, M.; Sánchez, J. P.; Ser, J. Del; Kemble, S.; Felicetti, L.; IAIn the past, space trajectory optimization was limited to optimal design of transfers to single destinations, where optimality refers to minimum propellant consumption or transfer time. New technologies, and a more daring approach to space, are today making the space community consider missions that target multiple destinations. In the present paper, we focus on missions that aim to visit multiple asteroids within a single launch. The trajectory design of these missions is complicated by the fact that the asteroid sequences are not known a priori but are the objective of the optimization itself. Usually, these problems are formulated as global optimization (GO) problems, under the formulation of mixed-integer non-linear programming (MINLP), on which the decision variables assume both continuous and discrete values. However, beyond the aim of finding the global optimum, mission designers are usually interested in providing a wide range of mission design options reflecting the multi-modality of the problems at hand. In this sense, a Constraint Satisfaction Problem (CSP) formulation is also relevant. With the present paper we focus on these two needs (i.e. tackling both the GO and the CSP) for the asteroid tour problem. First, a tree-search algorithm based upon the Bellman's principle of optimality is described using dynamic programming approach to address the feasibility of solving the GO problem. This results in an efficient and scalable procedure to obtain global optimum solutions within large datasets of asteroids. Secondly, tree-search strategies like Beam Search and Ant Colony Optimization with back-tracking are tested over the CSP formulations. Results show that BS handles better the multi-modality of the search space compared to ACO, as this bias the elite solutions which resulting in the diversity loss.Item Weighted strategies to guide a multi-objective evolutionary algorithm for multi-UAV mission planning(2019-02) Ramirez Atencia, Cristian; Del Ser, Javier; Camacho, David; IAManagement and mission planning over a swarm of unmanned aerial vehicle (UAV) remains to date as a challenging research trend in what regards to this particular type of aircrafts. These vehicles are controlled by a number of ground control station (GCS), from which they are commanded to cooperatively perform different tasks in specific geographic areas of interest. Mathematically the problem of coordinating and assigning tasks to a swarm of UAV can be modeled as a constraint satisfaction problem, whose complexity and multiple conflicting criteria has hitherto motivated the adoption of multi-objective solvers such as multi-objective evolutionary algorithm (MOEA). The encoding approach consists of different alleles representing the decision variables, whereas the fitness function checks that all constraints are fulfilled, minimizing the optimization criteria of the problem. In problems of high complexity involving several tasks, UAV and GCS, where the space of search is huge compared to the space of valid solutions, the convergence rate of the algorithm increases significantly. To overcome this issue, this work proposes a weighted random generator for the creation and mutation of new individuals. The main objective of this work is to reduce the convergence rate of the MOEA solver for multi-UAV mission planning using weighted random strategies that focus the search on potentially better regions of the solution space. Extensive experimental results over a diverse range of scenarios evince the benefits of the proposed approach, which notably improves this convergence rate with respect to a naïve MOEA approach.