Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFractals2019: Combinatorial Optimisation with Dynamic Constraint Annealing
56
0
0.0
(
0
)
Added by
Mikhail Prokopenko
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Fractals2019 started as a new experimental entry in the RoboCup Soccer 2D Simulation League, based on Gliders2d code base, and advanced to become a RoboCup-2019 champion. We employ combinatorial optimisation methods, within the framework of Guided Self-Organisation, with the search guided by local constraints. We present examples of several tactical tasks based on the Gliders2d code (version v2), including the search for an optimal assignment of heterogeneous player types, as well as blocking behaviours, offside trap, and attacking formations. We propose a new method, Dynamic Constraint Annealing, for solving dynamic constraint satisfaction problems, and apply it to optimise thermodynamic potential of collective behaviours, under dynamically induced constraints.
rate research
Read More
We developed and compared Constraint Programming (CP) and Quantum Annealing (QA) approaches for rolling stock optimisation considering necessary maintenance tasks. To deal with such problems in CP we investigated specialised pruning rules and implemented them in a global constraint. For the QA approach, we developed quadratic unconstrained binary optimisation (QUBO) models. For testing, we use data sets based on real data from Deutsche Bahn and run the QA approach on real quantum computers from D-Wave. Classical computers are used to run the CP approach as well as tabu search for the QUBO models. We find that both approaches tend at the current development stage of the physical quantum annealers to produce comparable results, with the caveat that QUBO does not always guarantee that the maintenance constraints hold, which we fix by adjusting the QUBO model in preprocessing, based on how close the trains are to a maintenance threshold distance.
In this paper we present an algorithmic framework for solving a class of combinatorial optimization problems on graphs with bounded pathwidth. The problems are NP-hard in general, but solvable in linear time on this type of graphs. The problems are relevant for assessing network reliability and improving the networks performance and fault tolerance. The main technique considered in this paper is dynamic programming.
The tile-based multiplayer game Mahjong is widely played in Asia and has also become increasingly popular worldwide. Face-to-face or online, each player begins with a hand of 13 tiles and players draw and discard tiles in turn until they complete a winning hand. An important notion in Mahjong is the deficiency number (a.k.a. shanten number in Japanese Mahjong) of a hand, which estimates how many tile changes are necessary to complete the hand into a winning hand. The deficiency number plays an essential role in major decision-making tasks such as selecting a tile to discard. This paper proposes a fast algorithm for computing the deficiency number of a Mahjong hand. Compared with the baseline algorithm, the new algorithm is usually 100 times faster and, more importantly, respects the agents knowledge about available tiles. The algorithm can be used as a basic procedure in all Mahjong variants by both rule-based and machine learning-based Mahjong AI.
The broad applicability of Quadratic Unconstrained Binary Optimization (QUBO) constitutes a general-purpose modeling framework for combinatorial optimization problems and are a required format for gate array and quantum annealing computers. QUBO annealers as well as other solution approaches benefit from starting with a diverse set of solutions with local optimality an additional benefit. This paper presents a new method for generating a set of one-flip local optima leveraging constraint programming. Further, as demonstrated in experimental testing, analysis of the solution set allows the generation of soft constraints to help guide the optimization process.
Efficient scheduling is of great significance to rationally make use of scarce satellite resources. Task clustering has been demonstrated to realize an effective strategy to improve the efficiency of satellite scheduling. However, the previous task clustering strategy is static. That is, it is integrated into the scheduling in a two-phase manner rather than in a dynamic fashion, without expressing its full potential in improving the satellite scheduling performance. In this study, we present an adaptive Simulated Annealing based scheduling algorithm aggregated with a dynamic task clustering strategy (or ASA-DTC for short) for satellite observation scheduling problems (SOSPs). First, we develop a formal model for the scheduling of Earth observing satellites. Second, we analyze the related constraints involved in the observation task clustering process. Thirdly, we detail an implementation of the dynamic task clustering strategy and the adaptive Simulated Annealing algorithm. The adaptive Simulated Annealing algorithm is efficient, with the endowment of some sophisticated mechanisms, i.e. adaptive temperature control, tabu-list based revisiting avoidance mechanism, and intelligent combination of neighborhood structures. Finally, we report on experimental simulation studies to demonstrate the competitive performance of ASA-DTC. Moreover, we show that ASA-DTC is especially effective when SOSPs contain a large number of targets or these targets are densely distributed in a certain area.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
