Game theory is a highly successful paradigm for strategic decision making between multiple agents having conflicting objectives. Since a few years, games have been studied in a computational perspective, raising new i...
详细信息
ISBN:
(纸本)9781479929733
Game theory is a highly successful paradigm for strategic decision making between multiple agents having conflicting objectives. Since a few years, games have been studied in a computational perspective, raising new issues like complexity of equilibria or succinctness of representation. Indeed, the main representation for general games is still a n-dimensional matrix of exponential size called normal form. In this paper, we introduce the framework of constraint Games to model strategic interaction between players. A constraint Game is composed of a set of variables shared by all the players. Among these variables, each player owns a set of decision variables she can control and a constraint Optimization Problem defining her preferences. Since the preferences of a player depend on the decisions taken by the other players, each player may try to improve her position by choosing an assignment that optimizes her preferences. Pure Nash equilibria are situations in which no player may improve her preferences unilaterally. constraint Games are thus a generic tool to model general games and can be exponentially more succinct than their normal form. We show the practical utility of the framework by modelling a few realistic problems and we propose an algorithm based on tabu search to compute pure Nash equilibria in constraint games that outperforms the algorithms based on normal form. In addition, constraint Games raise some interesting research issues that deserve further attention.
This paper presents a new method that solves a mixed constraints problem by transforming it into a mixed integer programming problem. The method builds the connection between the feasibility of a mixed constraint prob...
详细信息
This paper presents a new method that solves a mixed constraints problem by transforming it into a mixed integer programming problem. The method builds the connection between the feasibility of a mixed constraint problem and the solution to a mixed integer programming problem. The correctness of this method is proven. This method will be beneficial for the further integration of constraint programming and optimization methods.
Cooperation among constraint solvers is difficult because different solving paradigms have different theoretical foundations. Recent works have shown that abstract interpretation can provide a unifying theory for vari...
详细信息
constraint programming (CP) allows to solve constraint satisfaction and optimization problems by building and then exploring a search tree of potential solutions. Potential solutions are generated by firstly selecting...
详细信息
ISBN:
(纸本)9781467398183
constraint programming (CP) allows to solve constraint satisfaction and optimization problems by building and then exploring a search tree of potential solutions. Potential solutions are generated by firstly selecting a variable and then a value from the given problem, phase known as enumeration. In this context, Autonomous Search (AS) that is a particular case of adaptive systems, enables the problem solver to control and adapt its internal configuration during solving time, based on performance metrics in order to be more efficient. The goal is to provide a mechanism for CP solvers, integrating a component able to evaluate the solving performance process. In particular, we employ a classic decision making method called Choice Function (CF). In this paper, we present an evaluation of different choice functions, based on performance exhibited in a indicators set. The results are promising and show that it is feasible to solve constraint satisfaction problems with this new technique.
作者：
Hà, Minh HoàngTa, Dinh QuyNguyen, Trung ThanhORLab
Faculty of Computer Science Phenikaa University Hanoi12116 Viet Nam ORLab
Faculty of Information Technology VNU University of Engineering and Technology Hanoi Viet Nam
Machine scheduling problems involving conflict jobs can be seen as a constrained version of the classical scheduling problem, in which some jobs are conflict in the sense that they cannot be proceeded simultaneously o...
详细信息
Open forms of global constraints allow the addition of new variables to an argument during the execution of a constraint program. Such forms are needed for difficult constraint programming problems where problem const...
详细信息
In robotics, pose errors are known as positional and rotational errors of a given mechanical system. Those errors are commonly produced by the play among joined components, commonly known as joint clearances. Predicti...
详细信息
In robotics, pose errors are known as positional and rotational errors of a given mechanical system. Those errors are commonly produced by the play among joined components, commonly known as joint clearances. Predicting pose errors can be done via the formulation of two optimization models holding continuous domains, which belong to the NP-Hard class of problems. This paper focuses on providing rigorous and reliable solution to this problem by using constraint programing.
We integrate integrity constraints to stableKanren to enable a new problem-solving paradigm in combinatorial search problems. stableKanren extends miniKanren to reasoning about contradictions under stable model semant...
详细信息
Despite the advancements in constraint propagation methods, most CP solvers still apply fixed predetermined propagators on each constraint of the problem. However, selecting the appropriate propagator for a constraint...
详细信息
ISBN:
(纸本)9781479902279
Despite the advancements in constraint propagation methods, most CP solvers still apply fixed predetermined propagators on each constraint of the problem. However, selecting the appropriate propagator for a constraint can be a difficult task that requires expertise. One way to overcome this is through the use of machine learning. A different approach uses heuristics to dynamically adapt the propagation method during search. The heuristics of this category proposed in [1] displayed promising results, but their evaluation and application suffered from two important drawbacks: They were only defined and tested on binary constraints and they required calibration of their input parameters. In this paper we follow this line of work by describing and evaluating simple, fully automated heuristics that are applicable on constraints of any arity. Experimental results from various problems show that the proposed heuristics can outperform a standard approach that applies a preselected propagator on each constraint resulting in an efficient and robust solver.
In this paper we present GRASPER, a graph constraint solver, based on set constraints, that shows promising results when compared to an existing similar solver at this early stage of development.
ISBN:
(纸本)9783540770008
In this paper we present GRASPER, a graph constraint solver, based on set constraints, that shows promising results when compared to an existing similar solver at this early stage of development.
暂无评论