检索结果-内蒙古大学图书馆

Constraint models for Sequential planning

Constraint Models for Sequential Planning

6th International Conference Integration of AI and OR Techniques in Constraint Programming for Combinatial Optimization problems

作者： Bartak, Roman Toropila, Daniel Charles Univ Prague Fac Math & Phys CR-11800 Prague 1 Czech Republic

ISBN: (纸本)9783642019289

planning and constraint satisfaction are important areas of Artificial Intelligence, but surprisingly constraint satisfaction techniques are not widely applied to planning problems where dedicated solving algorithms dominate. Classical AI planning deals with finding a sequence of actions that transfer the initial state of the world into a desired state. One of the main difficulties of planning is that the size of the solution - the length of the plan - is unknown in advance. On the other hand, a constraint satisfaction problem needs to be fully specified in advance before the constraint model goes to the solver. As Kautz and Selman showed, the problem of shortest-plan planning can be translated to a series of SAT problems, where each SAT instance encodes the problem of finding a plan of a given length. First, we start with finding a plan of length 1 and if it does not exist then we continue with a plan of length 2 etc. until the plan is found. the same approach can be applied when constraint satisfaction is used instead of SAT. there exists a straightforward constraint model of this type but more advanced constraint models exploit the structure of a so called planning graph, namely GP-CSP and CSP-PLAN. there also exist hand-crafted constraint models for particular planning problems such as CPlan. All these models share the logical representation of the problem where Boolean variables describe whether a given proposition holds in a given state and whether a given action is applied to a given state. Constraints are in the form of logical formulae (frequently implications). In our opinion, these models do not exploit fully the potential of constraint satisfaction, namely domain filtering techniques and global constraints. therefore, we suggested to use multi-valued representation of states based on the state variable formalism SAS^∈+∈ that contributes to fewer variables with larger domains where domain filtering pays off. Also, we proposed to encapsulate the

关键词： Constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

On truthfulness and approximation for scheduling selfish tasks

On truthfulness and approximation for scheduling selfish tas...

引用

Biannual workshop on models and algorithms for planning and scheduling problems

作者： Angel, Eric Bampis, Evripidis Pascual, Fanny Tchetgnia, Alex-Ariel Univ Evry IBISC CNRS 2873 Evry France Univ Paris 06 LIP6 Paris France

We consider the problem of designing truthful mechanisms for scheduling n tasks on a set of m parallel related machines in order to minimize the makespan. In what follows, we consider that each task is owned by a selfish agent. this is a variant of the KP-model introduced by Koutsoupias and Papadimitriou (Proc. of STACS 1999, pp. 404413, 1999) (and of the CKN-model of Christodoulou et al. in Proc. of ICALP 2004, pp. 345-357, 2004) in which the agents cannot choose the machine on which their tasks will be executed. this is done by a centralized authority, the scheduler. However, the agents may manipulate the scheduler by providing false information regarding the length of their tasks. We introduce the notion of increasing algorithm and a simple reduction that transforms any increasing algorithm into a truthful one. Furthermore, we show that some of the classical scheduling algorithms are indeed increasing: the LPT algorithm, the PTAS of Graham (SIAM J. Appl. Math. 17( 2): 416-429, 1969) in the case of two machines, as well as a simple PTAS for the case of m machines, with m a fixed constant. Our results yield a randomized r(1 + epsilon)-approximation algorithm where r is the ratio between the largest and the smallest speed of the related machines. Furthermore, by combining our approach with the classical result of Shmoys et al. (SIAM J. Comput. 24(6): 1313-1331, 1995), we obtain a randomized 2r(1 + epsilon)-competitive algorithm. It has to be noticed that these results are obtained without payments, unlike most of the existing works in the field of Mechanism Design. Finally, we show that if payments are allowed then our approach gives a (1 + epsilon)-algorithm for the off-line case with related machines.

关键词： scheduling Approximation algorithms Truthfulness Game theory

来源：评论

学校读者我要写书评

暂无评论

Robust Solutions in Unstable Optimization problems

Robust Solutions in Unstable Optimization Problems

引用

13th Annual International workshop on Constraint Solving and Constraint Logic Programming

作者： Pini, Maria Silvia Rossi, Francesca Venable, Kristen Brent Dechter, Rina Univ Padua Dipartimento Matemat Pura Applicata I-35100 Padua Italy Univ Calif Irvine Sch Informat & Comp Sci Irvine CA USA

ISBN: (纸本)9783642032509

We consider constraint optimization problems where costs (or preferences) are all given, but some are tagged as possibly unstable, and provided with a range of alternative values. We also allow for some uncontrollable variables, whose value cannot be decided by the agent in charge, of taking the decisions, but will be decided by Nature or by some other agent. these two forms of uncertainty are often found in many scheduling and planning scenarios. For such problems, we define several notions of desirable solutions. Such notions take into account not only the optimality of the solutions, but also their degree of robustness (of the optimality status, or of the cost) w.r.t. the uncertainty present in the problem. We provide an algorithm to find solutions accordingly to the considered notions of optimality, and we study the properties of these algorithms. For the uncontrollable variables, we propose to adopt a variant of classical variable elimination, where we act pessimistically rather than optimistically.

关键词： Constrained optimization

来源：评论

学校读者我要写书评

暂无评论

From Marriages to Coalitions: A Soft CSP Approach

From Marriages to Coalitions: A Soft CSP Approach

引用

13th Annual International workshop on Constraint Solving and Constraint Logic Programming

作者： Bistarelli, Stefano Foley, Simon O'Sullivan, Barry Santini, Francesco Univ G dAnnunzio Dipartimento Sci Chieti Italy Istituto Informat Telemat CNR Pisa Italy Univ Perugia Dipartimento Matemat Informat Perugia Italy Univ Coll Cork Dept Comp Sci Cork Ireland Univ Coll Cork Cork Constraint Computat Ctr Cork Ireland IMT Scuola Studi Avanzati Lucca Italy

ISBN: (纸本)9783642032509

In this work we represent the Optimal Stable Marriage problem as a Soft Constraint Satisfaction Problem. In addition, we extend this problem from couples of individuals to coalitions of generic agents, in order to define new coalition-formation principles and stability conditions. In the coalition case, we suppose the preference value as a trust score, since trust can describe the belief of a node in the capabilities of another node, in its honesty and reliability. Semiring-based soft constraints represent a general and expressive framework that is able to deal with distinct concepts of optimality by only changing the related c-semiring structure, instead of using different ad-hoc algorithms. At last, we propose an implementation of the classical OSM problem using integer linear programming tools.

关键词： Constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Feasible distributed CSP models for scheduling problems

引用

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 2008年第5期21卷 723-732页

作者： Salido, Miguel A. Giret, Adriana Univ Politecn Valencia Dept Sistemas Informat & Computac Valencia 46022 Spain

A distributed constraint satisfaction problem (DisCSP) is a CSP in which variables and constraints are distributed among multiple automated agents. Many researchers have developed techniques for solving DisCSPs. they assume for simplicity that each agent has exactly one variable. For real planning and scheduling problems, these techniques require a large number of messages passing among agents, so these problems are very difficult to solve. In this paper, we present a general distributed model for solving real-life scheduling problems. this distributed model is based on the idea of holonic systems. Furthermore, we propose some guidelines for distributing large-scale problems. Finally, we present two case studies in which two scheduling problems are distributed by using our model. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： distributed CSP constraint satisfaction holonic system multi-agent system scheduling

来源：评论

学校读者我要写书评

暂无评论

Distributed search in railway scheduling problems

引用

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 2008年第5期21卷 744-755页

作者： Abril, Montserrat Salido, Miguel A. Barber, Federico Univ Politecn Valencia Dpto Sistemas Informat & Computac Valencia 46022 Spain

Many problems of theoretical and practical interest can be formulated as Constraint Satisfaction problems (CSPs). Solving a general CSP is known to be NP-complete;however, distributed models may take advantage of dividing the problem into a set of simpler inter-connected sub-problems which can be more easily solved. the purpose of this paper is three-fold: first, we present a technique to distribute the constraint network by means of selection of tree structures. thus, the CSP is represented as a meta-tree CSP structure that is used as a hierarchy of communication by our distributed algorithm. then, a distributed and asynchronous search algorithm (DTS) is presented. DTS is committed to solving the meta-tree CSP structure in a depth-first search tree. Finally, an intra-agent search algorithm is presented. this algorithm takes into account the Nogood_message to prune the search space. We have focused our research on the railway scheduling problem which can be distributed by tree structures. We show that our distributed algorithm outperforms well-known centralized algorithms. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： Constraint Satisfaction problems distributed CSP meta-tree CSP structure tree partition train timetabling

来源：评论

学校读者我要写书评

暂无评论

Joint Equilibrium Policy Search for Multi-Agent scheduling problems

Joint Equilibrium Policy Search for Multi-Agent Scheduling P...

引用

6th German Conference on Multiagent System Technologies

作者： Gabel, thomas Riedmiller, Martin Univ Osnabruck Inst Cognit Sci Dept Math & Comp Sci Neuroinformat Grp D-49069 Osnabruck Germany

ISBN: (纸本)9783540878049

We propose joint equilibrium policy search as a multi-agent learning algorithm for decentralized Markov decision processes with changing action sets. In its basic form, it relies on stochastic agent-specific policies parameterized by probability distributions defined for every state as well as on a heuristic that tells whether a joint equilibrium could be obtained. We also suggest an extended version where each agent employs a global policy parameterization which renders the approach applicable to larger-scale problems. Joint-equilibrium policy search is well suited for production planning, traffic control, and other application problems. In support of this, we apply our algorithms to a number of challenging scheduling benchmark problems, finding that solutions of very high quality can be obtained.

关键词： Multi agent systems

来源：评论

学校读者我要写书评

暂无评论

Link scheduling in local interference models

引用

4th International workshop on Algorithmic Aspects of Wireless Sensor Networks, ALGOSENSORS 2008

作者： Katz, Bastian Völker, Markus Wagner, Dorothea Germany

ISBN: (纸本)3540928618

Choosing an appropriate interference model is crucial for link scheduling problems in sensor networks. While graph-based interference models allow for distributed and purely local coloring approaches which lead to many interesting results, a more realistic and widely agreed on model such as the signal-to-noise-plus-interference ratio (SINR) inherently makes scheduling radio transmission a non-local task, and thus impractical for the development of distributed and scalable scheduling protocols in sensor networks. In this work, we focus on interference models that are local in the sense that admissibility of transmissions only depends on local concurrent transmissions, and correct with respect to the geometric SINR model. In our analysis, we show lower bounds on the limitations that these restrictions impose an any such model as well as approximation results for greedy scheduling algorithms in a class of these models. © 2008 Springer Berlin Heidelberg.

关键词： Sensor networks

来源：评论

学校读者我要写书评

暂无评论

Multiagent System Technologies - 6th German Conference, MATES 2008, Proceedings

Multiagent System Technologies - 6th German Conference, MATE...

引用

6th German Conference on Multiagent System Technologies, MATES 2008

ISBN: (纸本)3540878041

the proceedings contain 18 papers. the topics discussed include: logic for automated mechanism design and analysis;coordination in multi-agent systems: towards a technology of agreement;optimistic-pessimistic Q-learning algorithm for multi-agent systems;how to program organizations and roles in the JADE framework;agent models for concurrent software systems;filtering algorithms for agent-based incident communication support in mobile human surveillance;joint equilibrium policy search for multi-agent scheduling problems;making allocations collectively: iterative group decision making under uncertainty;compiling GOAL agent problems into Jazzyk behavioral state machines;knowledge and strategic ability for model checking: a refined approach;and agent learning instead of behavior implementation for simulations- a case study using classifier systems.

关键词：

来源：评论

学校读者我要写书评

暂无评论

A simulation-based approach to job shop scheduling with bottlenecks

A simulation-based approach to job shop scheduling with bott...

引用

IEEE International Conference on Industrial Informatics (INDIN)

作者： Rui Zhang Cheng Wu Department of Automation Tsinghua University Beijing China

A bottleneck machine identification algorithm is proposed for the job shop scheduling problem in which either the makespan or the total tardiness should be minimized. the scheduling policies on bottleneck machines can have significant impact on the final scheduling performance and therefore need to be optimized with more computational effort. In order to describe the characteristic information concerning bottleneck machines, a statistics-based algorithm to compute the bottleneck characteristic values is devised. the algorithm first constructs a simulation data set which consists of a number of different solutions in the form of scheduling rules, and then statistically analyzes the correlation between various scheduling policies on each machine and the overall scheduling objective value. Two genetic algorithms based on different encoding schemes are designed to verify the effectiveness of the proposed method, and it is proved that intensifying the local search operations for bottleneck machines will generally result in higher solution quality for the job shop scheduling problem.

关键词： Job shop scheduling Genetic algorithms Processor scheduling Encoding Search problems Data models

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：