GotAI.NET
Форум: Проблемы искусственного интеллекта
Регистрация
|
Вход
Все темы
|
Новая тема
Стр.9 (39)
<<
< Пред.
|
След. >
>>
Поиск:
Автор
Тема: На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Capt.Drew
Сообщений: 4179
На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Добавлено: 21 авг 09 6:52
PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH:
=091=> 0505p
Solving 8x8 Hex
,
Philip Henderson, Broderick Arneson, Ryan B Hayward,
http://ijcai.org/papers09/Abstracts/091.html
Using efficient methods that reduce the search space, we design an algorithm strong enough to solve all 8x8 Hex openings. text:
http://ijcai.org/papers09/Papers/IJCAI09-091.pdf
[
Ответ
][
Цитата
]
Capt.Drew
Сообщений: 4179
На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Добавлено: 21 авг 09 6:53
PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH:
=092=> 0511p
New Improvements in Optimal Rectangle Packing
,
Eric Huang, Richard E. Korf,
http://ijcai.org/papers09/Abstracts/092.html
The rectangle packing problem consists of finding an enclosing rectangle of smallest area that can contain a given set of rectangles without overlap. Our algorithm picks the x-coordinates of all the rectangles before picking any of the y-coordinates. For the x-coordinates, we present a dynamic variable ordering heuristic and an adaptation of a pruning algorithm used in previous solvers. We then transform the rectangle packing problem into a perfect packing problem that has no empty space, and present inference rules to reduce the instance size. For the y-coordinates we search a space that models empty positions as variables and rectangles as values. Our solver is over 19 times faster than the previous state-of-the-art on the largest problem solved to date, allowing us to extend the known solutions for a consecutive-square packing benchmark from N=27 to N=32. text:
http://ijcai.org/papers09/Papers/IJCAI09-092.pdf
[
Ответ
][
Цитата
]
Capt.Drew
Сообщений: 4179
На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Добавлено: 21 авг 09 6:53
PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH:
=093=> 0517p
SATenstein: Automatically Building Local Search SAT Solvers From Components
,
Ashiqur R. KhudaBukhsh, Lin Xu, Holger H. Hoos, Kevin Leyton-Brown,
http://ijcai.org/papers09/Abstracts/093.html
Designing high-performance algorithms for computationally hard problems is a difficult and often time-consuming task. In this work, we demonstrate that this task can be automated in the context of stochastic local search (SLS) solvers for the propositional satisfiability problem (SAT). We first introduce a generalised, highly parameterised solver framework, dubbed SATenstein, that includes components gleaned from or inspired by existing high-performance SLS algorithms for SAT. The parameters of SATenstein control the selection of components used in any specific instantiation and the behaviour of these components. SATenstein can be configured to instantiate a broad range of existing high-performance SLSbased SAT solvers, and also billions of novel algorithms. We used an automated algorithm configuration procedure to find instantiations of SATenstein that perform well on several well-known, challenging distributions of SAT instances. Overall, we consistently obtained significant improvements over the previously best-performing SLS algorithms, despite expending minimal manual effort. text:
http://ijcai.org/papers09/Papers/IJCAI09-093.pdf
[
Ответ
][
Цитата
]
Capt.Drew
Сообщений: 4179
На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Добавлено: 21 авг 09 6:53
PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH:
=094=> 0525p
Exploiting Decomposition on Constraint Problems with High Tree-Width
,
Matthew Kitching, Fahiem Bacchus,
http://ijcai.org/papers09/Abstracts/094.html
Decomposition is an effective technique for solving discrete Constraint Optimization Problems (COPs) with low tree-width. On problems with high treewidth, however, existing decomposition algorithms offer little advantage over branch and bound search (B&B). In this paper we propose a method for exploiting decomposition on problems with high treewidth. Our technique involves modifying B&B to detect and exploit decomposition on a selected subset of the problem’s objectives. Decompositions over this subset, generated during search, are exploited to compute tighter bounds allowing B&B to prune more of its search space. We present a heuristic for selecting an appropriate subset of objectives—one that readily decomposes during search and yet can still provide good bounds. We demonstrate empirically that our approach can significantly improve B&B’s performance and outperform standard decomposition algorithms on a variety of high tree-width problems. text:
http://ijcai.org/papers09/Papers/IJCAI09-094.pdf
[
Ответ
][
Цитата
]
Capt.Drew
Сообщений: 4179
На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Добавлено: 21 авг 09 6:53
PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH:
=095=> 0532p
Set Branching in Constraint Optimization
,
Matthew Kitching, Fahiem Bacchus,
http://ijcai.org/papers09/Abstracts/095.html
Branch and bound is an effective technique for solving constraint optimization problems (COP’s). However, its search space expands very rapidly as the domain sizes of the problem variables grow. In this paper, we present an algorithm that clusters the values of a variable’s domain into sets. Branch and bound can then branch on these sets of values rather than on individual values, thereby reducing the branching factor of its search space. The aim of our clustering algorithm is to construct a collection of sets such that branching on these sets will still allow effective bounding. In conjunction with the reduced branching factor, the size of the explored search space is thus significantly reduced. We test our method and show empirically that it can yield significant performance gains over existing stateof- the-art techniques.
text:
http://ijcai.org/papers09/Papers/IJCAI09-095.pdf
[
Ответ
][
Цитата
]
Capt.Drew
Сообщений: 4179
На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Добавлено: 21 авг 09 6:53
PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH:
=096=> 0638p
Multi-Way Number Partitioning
,
Richard Earl Korf,
http://ijcai.org/papers09/Abstracts/096.html
The number partitioning problem is to divide a given set of integers into a collection of subsets, so that the sum of the numbers in each subset are as nearly equal as possible. While a very efficient algorithm exists for optimal two-way partitioning, it is not nearly as effective for multi-way partitioning. We develop two new linear-space algorithms for multi-way partitioning, and demonstrate their performance on three, four, and five-way partitioning. In each case, our algorithms outperform the previous state of the art by orders of magnitude, in one case by over six orders of magnitude. Empirical analysis of the running times of our algorithms strongly suggest that their asymptotic growth is less than that of previous algorithms. The key insight behind both our new algorithms is that if an optimal k-way partition includes a particular subset, then optimally partitioning the numbers not in that set k-1 ways results in an optimal k-way partition.
text:
http://ijcai.org/papers09/Papers/IJCAI09-096.pdf
[
Ответ
][
Цитата
]
Capt.Drew
Сообщений: 4179
На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Добавлено: 21 авг 09 6:54
PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH:
=097=> 0544p
Integrating Systematic and Local Search Paradigms: A New Strategy for MaxSAT
,
Lukas Kroc, Ashish Sabharwal, Carla P. Gomes, Bart Selman,
http://ijcai.org/papers09/Abstracts/097.html
Systematic search and local search paradigms forcombinatorial problems are generally believed tohave complementary strengths. Nevertheless, attemptsto combine the power of the two paradigmshave had limited success, due in part to the expensiveinformation communication overhead involved.We propose a hybrid strategy based onshared memory, ideally suited for multi-core processorarchitectures. This method enables continuousinformation exchange between two solverswithout slowing down either of the two. Such a hybridsearch strategy is surprisingly effective, leadingto substantially better quality solutions to manychallenging Maximum Satisfiability (MaxSAT) instancesthan what the current best exact or heuristicmethods yield, and it often achieves this within seconds.This hybrid approach is naturally best suitedto MaxSAT instances for which proving unsatisfiabilityis already hard; otherwise the method fallsback to pure local search. text:
http://ijcai.org/papers09/Papers/IJCAI09-097.pdf
[
Ответ
][
Цитата
]
Capt.Drew
Сообщений: 4179
На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Добавлено: 21 авг 09 6:54
PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH:
=098=> 0552p
Variety Reasoning for Multiset Constraint Propagation
,
Yat Chiu Law, Jimmy Ho Man Lee, May Hiu Chun Woo,
http://ijcai.org/papers09/Abstracts/098.html
Set variables in constraint satisfaction problems (CSPs) are typically propagated by enforcing set bounds consistency together with cardinality reasoning, which uses some inference rules involving the cardinality of a set variable to produce more prunings than set bounds propagation alone. Multiset variables are a generalization of set variables by allowing the elements to have repetitions. In this paper, we generalize cardinality reasoning for multiset variables. In addition, we propose to exploit the variety of a multiset — the number of distinct elements in it — to improve modeling expressiveness and further enhance constraint propagation. We derive a number of inference rules involving the varieties of multiset variables. The rules interact varieties with the traditional components of multiset variables (such as cardinalities) to obtain stronger propagation. We also demonstrate how to apply the rules to perform variety reasoning on some common multiset constraints. Experimental results show that performing variety reasoning on top of cardinality reasoning can effectively reduce more search space and achieve better runtime in solving multiset CSPs. text:
http://ijcai.org/papers09/Papers/IJCAI09-098.pdf
[
Ответ
][
Цитата
]
Capt.Drew
Сообщений: 4179
На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Добавлено: 21 авг 09 6:55
PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH:
=099=> 0559p
Towards Efficient Consistency Enforcement
for Global Constraints in Weighted Constraint Satisfaction
,
Jimmy H. M. Lee, Ka Lun Leung,
http://ijcai.org/papers09/Abstracts/099.html
Powerful consistency techniques, such as AC* and FDAC*, have been developed for Weighted Constraint Satisfaction Problems (WCSPs) to reduce the space in solution search, but are restricted to only unary and binary constraints. On the other hand, van Hoeve et al developed efficient graph-based algorithms for handling soft constraints as classical constraint optimization problems. We prove that naively incorporating van Hoeve's method into the WCSP framework can enforce a strong form of varnothing-Inverse Consistency, which can prune infeasible values and deduce good lower bound estimates. We further show how Van Hoeve's method can be modified so as to handle cost projection and extension to maintain the stronger AC* and FDAC* generalized for non-binary constraints. Using the soft allDifferent constraint as a testbed, preliminary results demonstrate that our proposal gives improvements up to an order of magnitude both in terms of time and pruning. text:
http://ijcai.org/papers09/Papers/IJCAI09-099.pdf
[
Ответ
][
Цитата
]
Capt.Drew
Сообщений: 4179
На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Добавлено: 21 авг 09 6:55
PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH:
=100=> 0556p
A Soft Global Precedence Constraint
,
David Lesaint, Deepak Mehta, Barry O'Sullivan, Luis Quesada, Nic Wilson,
http://ijcai.org/papers09/Abstracts/100.html
Hard and soft precedence constraints play a key role in many application domains. In telecommunications, one application is the configuration of call control feature subscriptions where the task is to sequence a set of user-selected features subject to a set of hard (catalogue) precedence constraints and a set of soft (user-selected) precedence constraints. When no such consistent sequence exists, the task is to find an optimal relaxation by discarding some features or user precedences. For this purpose, we present the global constraint SOFTPREC. Enforcing Generalized Arc Consistency (GAC) on SOFTPREC is NP-complete. Therefore, we approximate GAC based on domain pruning rules that follow from the semantics of SOFTPREC; this pruning is polynomial. Empirical results demonstrate that the search effort required by SOFTPREC is up to one order of magnitude less then the previously known best CP approach for the feature subscription problem. SOFTPREC is also applicable to other problem domains including minimum cutset problems for which initial experiments confirm the interest.
text:
http://ijcai.org/papers09/Papers/IJCAI09-100.pdf
[
Ответ
][
Цитата
]
Capt.Drew
Сообщений: 4179
На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Добавлено: 21 авг 09 6:55
PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH:
=101=> 0572p
A Divide-and-Conquer Approach for Solving Interval Algebra Networks
,
Jason Jingshi Li, Jinbo Huang, Jochen Renz,
http://ijcai.org/papers09/Abstracts/101.html
Deciding consistency of constraint networks is a fundamental problem in qualitative spatial and temporal reasoning. In this paper we introduce a divide-and-conquer method that recursively partitions a given problem into smaller sub-problems in deciding consistency. We identify a key theoretical property of a qualitative calculus that ensures the soundness and completeness of this method, and show that it is satisfied by the Interval Algebra (IA) and the Point Algebra (PA). We develop a new encoding scheme for IA networks based on a combination of our divide-and-conquer method with an existing encoding of IA networks into SAT. We empirically show that our new encoding scheme scales to much larger problems and exhibits a consistent and significant improvement in efficiency over state-of-the-art solvers on the most difficult instances.
text:
http://ijcai.org/papers09/Papers/IJCAI09-101.pdf
[
Ответ
][
Цитата
]
Capt.Drew
Сообщений: 4179
На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Добавлено: 21 авг 09 6:55
PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH:
=102=> 0578p
Open Contractible Global Constraints
,
Michael Maher,
http://ijcai.org/papers09/Abstracts/102.html
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 construction and problem solving are interleaved. However, in general, filtering that is sound for a global constraint can be unsound when the constraint is open. This paper provides a simple characterization, called contractibility, of the constraints where filtering remains sound when the constraint is open. With this characterization we can easily determine whether a constraint is contractible or not. In the latter case, we can use it to derive the strongest contractible approximation to the constraint. We demonstrate how specific algorithms for some closed contractible constraints are easily adapted to open constraints.
text:
http://ijcai.org/papers09/Papers/IJCAI09-102.pdf
[
Ответ
][
Цитата
]
Capt.Drew
Сообщений: 4179
На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Добавлено: 21 авг 09 6:55
PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH:
=103=> 0584p
Evaluating Strategies for Running from the Cops
,
Carsten Moldenhauer, Nathan Reed Sturtevant,
http://ijcai.org/papers09/Abstracts/103.html
Moving target search (MTS) or the game of cops and robbers has a broad field of application reaching from law enforcement to computer games. Within the recent years research has focused on computing move policies for one or multiple pursuers (cops). The present work motivates to extend this perspective to both sides, thus developing algorithms for the target (robber). We investigate the game with perfect information for both players and propose two new methods, named TrailMax and Dynamic Abstract Trailmax, to compute move policies for the target. Experiments are conducted by simulating games on 20 maps of the commercial computer game Baldur's Gate and measuring survival time and computational complexity. We test seven algorithms: Cover, Dynamic Abstract Minimax, minimax, hill climbing with distance heuristic, a random beacon algorithm, TrailMax and DATrailMax. Analysis shows that our methods outperform all the other algorithms in quality, achieving up to 98% optimality, while meeting modern computer game computation time constraints. text:
http://ijcai.org/papers09/Papers/IJCAI09-103.pdf
[
Ответ
][
Цитата
]
Capt.Drew
Сообщений: 4179
На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Добавлено: 21 авг 09 6:56
PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH:
=104=> 0590p
A New d-DNNF-Based Bound Computation Algorithm for Functional E-MAJSAT
,
Knot Pipatsrisawat, Adnan Darwiche,
http://ijcai.org/papers09/Abstracts/104.html
We present a new algorithm for computing upper bounds for an optimization version of the EMAJSAT problem called functional E-MAJSAT. The algorithm utilizes the compilation language d- DNNF which underlies several state-of-the-art algorithms for solving related problems. This bound computation can be used in a branch-and-bound solver for solving functional E-MAJSAT. We then present a technique for pruning values from the branch-and-bound search tree based on the information available after each bound computation. We evaluated the proposed techniques in a MAP solver and a probabilistic conformant planner. In both cases, our experiments showed that the new techniques improved the efficiency of state-of-the-art solvers by orders of magnitude. text:
http://ijcai.org/papers09/Papers/IJCAI09-104.pdf
[
Ответ
][
Цитата
]
Capt.Drew
Сообщений: 4179
На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Добавлено: 21 авг 09 6:56
PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH:
=105=> 0594p
A Structural Approach to Reasoning with Quantified Boolean Formulas
,
Luca Pulina, Armando Tacchella,
http://ijcai.org/papers09/Abstracts/105.html
In this paper we approach the problem of reasoning with quantified Boolean formulas (QBFs) by combining search and resolution, and by switching between them according to structural properties of QBFs. We provide empirical evidence that QBFs which cannot be solved by search or resolution alone, can be solved by combining them, and that our approach makes a proof-of-concept implementation competitive with current QBF solvers. text:
http://ijcai.org/papers09/Papers/IJCAI09-105.pdf
[
Ответ
][
Цитата
]
Стр.9 (39)
:
1
...
5
6
7
8
[9]
10
11
12
13
...
39
<<
< Пред.
|
След. >
>>
Главная
|
Материалы
|
Справочник
|
Гостевая книга
|
Форум
|
Ссылки
|
О сайте
Вопросы и замечания направляйте нам по
адресу
Copyright © 2001-2022, www.gotai.net