Terrain analysis in Real-Time Strategy games is a necessary step to allow spacial reasoning. The goal of terrain analysis is to gather and process data about the map topology and properties to have a qualitative spati...
详细信息
ISBN:
(数字)9781665467087
ISBN:
(纸本)9781665467087
Terrain analysis in Real-Time Strategy games is a necessary step to allow spacial reasoning. The goal of terrain analysis is to gather and process data about the map topology and properties to have a qualitative spatial representation. On StarCraft games, all previous works on terrain analysis propose a crisp analysis based on connected component detection, Voronoi diagram computation and pruning, and region merging. Those methods have been implemented as game-specific libraries, and they can only offer the same kind of analysis for all maps and all users. In this paper, we propose a way to consider terrain analysis as a combinatorial optimization problem. Our method allows different kinds of analysis by changing constraints or the objective function in the problem model. We also present a library, TAUNT, implementing our method and able to handle both StarCraft 1 and StarCraft 2 maps. This makes our library a universal tool for StarCraft bots with different spatial representation needs. We believe our library unlocks the possibility to have real adaptive AIs playing StarCraft, and can be the starting point of a new wave of bots.
Forest management is an activity of prime economic and ecological importance. Managed forest areas can span very large regions and their proper management is paramount to an effective development, in terms both of eco...
详细信息
Forest management is an activity of prime economic and ecological importance. Managed forest areas can span very large regions and their proper management is paramount to an effective development, in terms both of economic and natural resources planning. A managed activity consists of individual and mutually independent policy choices which apply to distinct patches of land-named stands-which, as a whole, make up the forest area. A forest management plan typically spans a period of time on the order of a century and is normally geared towards the optimisation of economic or environmental metrics (e.g. total wood yield.) In this article we present a method which uses a declarative programming approach to formalise and solve a long-term forest management problem. We do so based on a freely available state-of-the-art constraint programming system, which we extend to naturally express concepts related to the core problem and efficiently compute solutions thereto.
The Tokeneer project was an initiative set forth by the National Security Agency (NSA, USA) to be used as a demonstration that developing highly secure systems can be made by applying rigorous methods in a cost-effect...
详细信息
The Tokeneer project was an initiative set forth by the National Security Agency (NSA, USA) to be used as a demonstration that developing highly secure systems can be made by applying rigorous methods in a cost-effective manner. Altran UK was selected by NSA to carry out the development of the Tokeneer ID Station. The company wrote a Z specification later implemented in the SPARK Ada programming language, which was verified using the SPARK Examiner toolset. In this paper, we show that the Z specification can be readily and naturally encoded in the {log} set constraint language, thereby generating a functional prototype. Furthermore, we show that {log}'s automated proving capabilities can discharge all the proof obligations concerning state invariants as well as important security properties. As a consequence, the prototype can be regarded as correct with respect to the verified properties. This provides empirical evidence that Z users can use {log} to generate correct prototypes from their Z specifications. In turn, these prototypes enable or simplify some verification activities discussed in the paper.
Bipartite b-matching is a classical model that is used for utility maximization in various applications such as marketing, healthcare, education, and general resource allocation. Multi-attribute diverse weighted bipar...
详细信息
ISBN:
(纸本)9783031080111;9783031080104
Bipartite b-matching is a classical model that is used for utility maximization in various applications such as marketing, healthcare, education, and general resource allocation. Multi-attribute diverse weighted bipartite b-matching (MDWBM) balances the quality of the matching with its diversity. The recent paper by Ahmadi et al. (2020) introduced the MDWBM but presented an incorrect mixed integer quadra-tic program (MIQP) and a flawed local exchange algorithm. In this work, we develop two constraint programming (CP) models, a binary quadratic programming (BQP) model, and a quadratic unconstrained binary optimization (QUBO) model for both the unconstrained and constrained MDWBM. A thorough empirical evaluation using commercial solvers and specialized QUBO hardware shows that the hardware-based QUBO approach dominates, finding best-known solutions on all tested instances up to an order of magnitude faster than the other approaches. CP is able to achieve better solutions than BQP on unconstrained problems but under-performs on constrained problems.
Motivated by Boeing 777 fully autonomous upright build project, orchestration of human and robotic agents are studied. Tasks must be precisely allocated, sequenced, and coordinated among agents subject to temporal and...
详细信息
Motivated by Boeing 777 fully autonomous upright build project, orchestration of human and robotic agents are studied. Tasks must be precisely allocated, sequenced, and coordinated among agents subject to temporal and spatial constraints. The problem is formulated as a flexible job shop with sequence-dependent setup to capture heterogeneous agents and travel time. Two exact central approaches are proposed: a mixed integer programming and a constraint programming, and tested for real-time perspective. The computational study demonstrates the proposed method can generate optimal schedules up to 100 agents with 1000 subtasks that requires 10 subtasks per agent on average, within 183 seconds, a substantial improvement over all other benchmark approaches in the literature.
U-shaped assembly lines are widely encountered in contemporary JIT systems. Unlike presumptions of deterministic studies, task times may vary according to a probability distribution. In this study, a stochastic U-type...
详细信息
U-shaped assembly lines are widely encountered in contemporary JIT systems. Unlike presumptions of deterministic studies, task times may vary according to a probability distribution. In this study, a stochastic U-type assembly line balancing problem (ALBP) is considered. For this purpose, two new chance-constrained nonlinear models are proposed. While the first model belongs to the mixed-integer programming (MIP) category, the other is constraint programming (CP). The linearized chance-constrained counterparts are developed using a transformation approach to reduce the model complexity and solve the models linearly. Several numerical experiments are performed to test the effectiveness of the proposed models. The results are compared with the results of modified ant colony optimization and a piecewise-linear programming model. The numerical results demonstrate that the proposed CP and MIP models are more effective and successful in solving stochastic U-type ALBP.
This paper focuses on designing a diameter - constrained network where the maximum distance between any pair of nodes is bounded. The objective considered is to minimise a weighted sum of the total length of the links...
详细信息
This paper focuses on designing a diameter - constrained network where the maximum distance between any pair of nodes is bounded. The objective considered is to minimise a weighted sum of the total length of the links followed by the total length of the paths between the pairs of nodes. First, the problem is formulated in terms of Mixed Integer Linear programming and constraint programming to provide two alternative exact approaches. Then, an adaptive large neighbourhood search (LNS) to overcome memory and runtime limitations of the exact methods in large size instances is proposed. Such approach is based on computing an initial solution and repeatedly improve it by solving relatively small subproblems. We investigate various alternatives for finding an initial solution and propose two different heuristics for selecting subproblems. We have introduced a tighter lower bound, which demonstrates the quality of the solution obtained by the proposed approach. The performance of the proposed approach is assessed using three real-world network topologies from Ireland, UK and Italy, which are taken from national telecommunication operators and are used to design a transparent optical core network. Our results demonstrate that the LNS approach is scalable to large networks and it can compute very high quality solutions that are close to being optimal.
The quadratic multiknapsack problem consists of packing a set of items of various weights into knapsacks of limited capacities with profits being associated with pairs of items packed into the same knapsack. This prob...
详细信息
The quadratic multiknapsack problem consists of packing a set of items of various weights into knapsacks of limited capacities with profits being associated with pairs of items packed into the same knapsack. This problem has been solved by various heuristics since its inception, and more recently it has also been solved with an exact method. We introduce a generalization of this problem that includes pairwise conflicts as well as balance constraints, among other particularities. We present and compare constraint programming and integer programming approaches for solving this generalized problem. Summary of Contribution: The quadratic multiknapsack problem consists of packing a set of items of various weights into knapsacks of limited capacities - with profits being associated with pairs of items packed into the same knapsack. This problem has been solved by various heuristics since its inception, and more recently it has also been solved with an exact method. We introduce a generalization of this problem which includes pairwise conflicts as well as balance constraints, among other particularities. We present and compare constraint programming and integer programming approaches for solving this generalized problem. The problem we address is clearly in the core of the operations research applications in which subsets have to be built and, in particular, we add the concept of fairness to the modeling and solution process by computationally evaluating techniques to take fairness into account. This is clearly at the core of computational evaluation of algorithms.
Industry 4.0 promises sustainable and more efficient manufacturing through new digital technologies. However, existing methodologies like Lean Manufacturing have been tested and proven, and could benefit greatly from ...
详细信息
ISBN:
(纸本)9789811661280;9789811661273
Industry 4.0 promises sustainable and more efficient manufacturing through new digital technologies. However, existing methodologies like Lean Manufacturing have been tested and proven, and could benefit greatly from increased digitalisation. In this paper, we claim that the enhancement of existing Lean and related methodologies with digital technology is a necessary step to fulfil Industry 4.0's promise. To demonstrate this claim, we introduce a framework for integrating raw material and finished product inventories and production scheduling. We validate the framework by developing a proof-of-concept system that combines constraint programming (CP) and inventory management to address a combined reactive scheduling and inventory management problem. The production model we use is a Resource-Constrained Project Scheduling Problem (RCPSP) with three finished products and four raw materials, and the two-bin or (s, Q) inventory policy. The system enables coordination of raw material, finished product and work-in-progress inventories through optimal scheduling (minimal makespan). The results inform operators of expected stock-outs and consumption and production rates, while allowing for modifications in case of disruption.
Due to the incorporation of heterogeneous cores in modern multi-core systems, the exploitation of their full potential strongly depends on the proper mapping of an application to the platform. This work presents an ap...
详细信息
ISBN:
(数字)9781665490054
ISBN:
(纸本)9781665490054
Due to the incorporation of heterogeneous cores in modern multi-core systems, the exploitation of their full potential strongly depends on the proper mapping of an application to the platform. This work presents an approach to map static applications on heterogeneous platforms minimizing their makespan based on the Benders decomposition principle combined with an Integer Linear programming (ILP) model. The proposed approach adopts a three-stage decomposition scheme, finding permutations of infeasible solutions to generate multiple cuts in every iteration. The first stage deals with the assignment of the tasks to the cores and the last one with their scheduling, whereas the second stage propagates new bounds based on the current assignment and provides an explanation of the infeasibility in the form of subsets of assignment variables. Based on that, other infeasible combinations are computed by checking their permutations and more Benders cuts are produced. The proposed method is compared with a two-stage decomposition approach and an ILP model and exhibits better performance in terms of solution time and number solved instances to optimality.
暂无评论