Форум: Проблемы искусственного интеллекта

Регистрация | Вход

Все темы | Новая тема  Стр.8 (39) << < Пред. | След. > >>    Поиск:
Автор	Тема: На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:50 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =076=> 0412p Circuit Complexity and Decompositions of Global Constraints, Christian Bessiere, G.Katsirelos, Nina Narodytska, Toby Walsh, http://ijcai.org/papers09/Abstracts/076.html We show that tools from circuit complexity can be used to study decompositions of global constraints. In particular, we study decompositions of global constraints into conjunctive normal form with the property that unit propagation on the decomposition enforces the same level of consistency as a specialized propagation algorithm. We prove that a constraint propagator has a a polynomial size decomposition if and only if it can be computed by a polynomial size monotone Boolean circuit. Lower bounds on the size of monotone Boolean circuits thus translate to lower bounds on the size of decompositions of global constraints. For instance, we prove that there is no polynomial sized decomposition of the domain consistency propagator for the alldiff constraint. text: http://ijcai.org/papers09/Papers/IJCAI09-076.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:50 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =077=> 0419p Decompositions of all Different, Global Cardinality and Related Constraints, Christian Bessiere, George Katsirelos, Nina Narodytska, Claude-Guy Quimper, Toby Walsh, http://ijcai.org/papers09/Abstracts/077.html We show that some common and important global constraints like ALLDIFFERENT and GCC can be decomposed into simple arithmetic constraints on which we achieve bound or range consistency, and in some cases even greater pruning. These decompositions can be easily added to new solvers. They also provide other constraints with access to the state of the propagator by sharing variables. Such sharing can be used to improve propagation between constraints. We report experiments with our decomposition in a pseudo-Boolean solver. text: http://ijcai.org/papers09/Papers/IJCAI09-077.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:50 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =078=> 0425p Making Bound Consistency as Effective as Arc Consistency, Christian Bessiere, Thierry Petit, Bruno Zanuttini, http://ijcai.org/papers09/Abstracts/078.html We study under what conditions bound consistency (BC) and arc consistency (AC), two forms of propagation used in constraint solvers, are equivalent to each other. We show that they prune exactly the same values when the propagated constraint is connected row convex / closed under median and its complement is row convex. This characterization is exact for binary constraints. Since row convexity depends on the order of the values in the domains, we give polynomial algorithms for computing orders under which BC and AC are equivalent, if any. text: http://ijcai.org/papers09/Papers/IJCAI09-078.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:50 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =079=> 0431p TBA*: Time-Bounded A*, Yngvi Björnsson, Vadim Bulitko, Nathan Sturtevant, http://ijcai.org/papers09/Abstracts/079.html Real-time heuristic search algorithms are used for planning by agents in situations where a constant-bounded amount of deliberation time is required for each action regardless of the problem size. Such algorithms interleave their planning and execution to ensure real-time response. Furthermore, to guarantee completeness, they typically store improved heuristic estimates for previously expanded states. Although subsequent planning steps can benefit from updated heuristic estimates, many of the same states are expanded over and over again. Here we propose a variant of the A* algorithm, Time-Bounded A* (TBA*), that guarantees real-time response. In the domain of path-finding on video-game maps TBA* expands an order of magnitude fewer states than traditional real-time search algorithms, while finding paths of comparable quality. It reaches the same level of performance as recent state-of-the-art real-time search algorithms but, unlike these, requires neither state-space abstractions nor pre-computed pattern databases. text: http://ijcai.org/papers09/Papers/IJCAI09-079.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:50 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =080=> 0437p Canadian Traveler Problem with Remote Sensing, Zahy Bnaya, Ariel Felner, Solomon Eyal Shimony, http://ijcai.org/papers09/Abstracts/080.html The Canadian Traveler Problem (CTP) is a navigation problem where a graph is initially known, but some edges may be blocked with a known probability. The task is to minimize travel effort of reaching the goal. We generalize CTP to allow for remote sensing actions, now requiring minimization of the sum of the travel cost and the remote sensing cost. Finding optimal policies for both versions is intractable. We provide optimal solutions for special case graphs. We then develop a framework that utilizes heuristics to determine when and where to sense the environment in order to minimize total costs. Several such heuristics, based on the expected total cost are introduced. Empirical evaluations show the benefits of our heuristics and support some of the theoretical results. text: http://ijcai.org/papers09/Papers/IJCAI09-080.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:50 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =081=> 0443p Experiments with Massively Parallel Constraint Solving, Lucas Bordeaux, Youssef Hamadi, Horst Samulowitz, http://ijcai.org/papers09/Abstracts/081.html The computing industry is currently facing a major architectural shift. Extra computing power is not coming anymore from higher processor frequencies, but from a growing number of computing cores and processors. For AI, and constraint solving in particular, this raises the question of how to scale current solving techniques to massively parallel architectures. While prior work focusses mostly on small scale parallel constraint solving, we conduct the first study on scalability of constraint solving on 100 processors and beyond in this paper. We propose techniques that are simple to apply and show empirically that they scale surprisingly well. These techniques establish a performance baseline for parallel constraint solving technologies against which more sophisticated parallel algorithms need to compete in the future. text: http://ijcai.org/papers09/Papers/IJCAI09-081.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:51 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =082=> 0449p Best-First Heuristic Search for Multi-Core Machines, Ethan Burns, Seth Lemons, Rong Zhou, Wheeler Ruml, http://ijcai.org/papers09/Abstracts/082.html To harness modern multi-core processors, it is imperative to develop parallel versions of fundamental algorithms. In this paper, we present a general approach to best-first heuristic search in a shared-memory setting. Each thread attempts to expand the most promising open nodes. By using abstraction to partition the state space, we detect duplicate states without requiring frequent locking. We allow speculative expansions when necessary to keep threads busy. We identify and fix potential livelock conditions in our approach, verifying its correctness using temporal logic. In an empirical comparison on STRIPS planning, grid pathfinding, and sliding tile puzzle problems using an 8-core machine, we show that A* implemented in our framework yields faster search than improved versions of previous parallel search proposals. Our approach extends easily to other best-first searches, such as Anytime weighted A*. text: http://ijcai.org/papers09/Papers/IJCAI09-082.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:51 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =083=> 0456p Nested Monte-Carlo Search, Tristan Cazenave, http://ijcai.org/papers09/Abstracts/083.html Many problems have a huge state space and no good heuristic to order moves so as to guide the search toward the best positions. Random games can be used to score positions and evaluate their interest. Random games can also be improved using random games to choose a move to try at each step of a game. Nested Monte-Carlo Search addresses the problem of guiding the search toward better states when there is no available heuristic. It uses nested levels of random games in order to guide the search. The algorithm is studied theoretically on simple abstract problems and applied successfully to three different games: Morpion Solitaire, SameGame and 16x16 Sudoku. text: http://ijcai.org/papers09/Abstracts/083.html [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:51 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =084=> 0462p Reasoning with Lines in the Euclidean Space, Khalil Raymond Challita, http://ijcai.org/papers09/Abstracts/084.html The main result of this paper is to show that the problem of instantiating a finite and path-consistent constraint network of lines in the Euclidean space is NP-complete. Indeed, we already know that reasoning with lines in the Euclidean space is NP-hard. In order to prove that this problem is NP-complete, we first establish that a particular instance of this problem can be solved by a nondeterministic polynomial-time algorithm, and then we show that solving any finite and path-consistent constraint network of lines in the Euclidean space is at most as difficult as solving that instance. text: http://ijcai.org/papers09/Papers/IJCAI09-084.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:51 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =085=> 0468p Search Strategies for an Anytime Usage of the Branch and Prune Algorithm, Raphaël Chenouard, Alexandre Goldsztejn, Christophe Jermann, http://ijcai.org/papers09/Abstracts/085.html When applied to numerical CSPs, the branch and prune algorithm (BPA) computes a sharp covering of the solution set. The BPA is therefore impractical when the solution set is large, typically when it has a dimension larger than four or five which is often met in underconstrained problems. The purpose of this paper is to present a new search tree exploration strategy for BPA that hybridizes depth-first and breadth-first searches. This search strategy allows the BPA discovering potential solutions in different areas of the search space in early stages of the exploration, hence allowing an anytime usage of the BPA. The merits of the proposed search strategy are experimentally evaluated. text: http://ijcai.org/papers09/Papers/IJCAI09-085.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:51 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =086=> 0474p Monte Carlo Tree Search Techniques in the Game of Kriegspiel, Paolo Ciancarini, Gian Piero Favini, http://ijcai.org/papers09/Abstracts/086.html Monte Carlo tree search has brought significant improvements to the level of computer players in games such as Go, but so far it has not been used very extensively in games of strongly imperfect information with a dynamic board and an emphasis on risk management and decision making under uncertainty. In this paper we explore its application to the game of Kriegspiel (invisible chess), providing three Monte Carlo methods of increasing strength for playing the game with little specific knowledge. We compare these Monte Carlo agents to the strongest known minimax-based Kriegspiel player, obtaining significantly better results with a considerably simpler logic and less domain-specific knowledge. text: http://ijcai.org/papers09/Papers/IJCAI09-086.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:52 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =087=> 0480p Duplicate Avoidance in Depth-First Search with Applications to Treewidth, P. Alex Dow, Richard E. Korf, http://ijcai.org/papers09/Abstracts/087.html Depth-first search is effective at solving hard combinatorial problems, but if the problem space has a graph structure the same nodes may be searched many times. This can increase the size of the search exponentially. We explore two techniques that prevent this: duplicate detection and duplicate avoidance. We illustrate these techniques on the treewidth problem, a combinatorial optimization problem with applications to a variety of research areas. The bottleneck for previous treewidth algorithms is a large memory requirement. We develop a duplicate avoidance technique for treewidth and demonstrate that it significantly outperforms other algorithms when memory is limited. Additionally, we are able to find, for the first time, the treewidth of several hard benchmark graphs. text: http://ijcai.org/papers09/Papers/IJCAI09-087.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:52 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =088=> 0486p Local Search: Is Brute-Force Avoidable?, Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, S.Saurabh, Yngve Villanger, http://ijcai.org/papers09/Abstracts/088.html Many local search algorithms are based on searching in the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of finding an improved solution. However, for inputs of size n, a naive brute-force search of the k-exchange neighborhood requires nO(k) time, which is not practical even for very small values of k. We show that for several classes of sparse graphs, like planar graphs, graphs of bounded vertex degree and graphs excluding some fixed graph as a minor, an improved solution in the k-exchange neighborhood for many problems can be found much more efficiently. Our algorithms run in time O(τ (k) · nc), where τ is a function depending on k only and c is a constant independent of k. We demonstrate the applicability of this approach on different problems like r-CENTER, VERTEX COVER, ODD CYCLE TRANSVERSAL, MAX-CUT, and MIN-BISECTION. In particular, on planar graphs, all our algorithms searching for a k local improvement run in time O(2O(k) ·n2), which is polynomial for k = O(log n). We also complement the algorithms with complexity results indicating that—brute force search is unavoidable—in more general classes of sparse graphs. text: http://ijcai.org/papers09/Papers/IJCAI09-088.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:52 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =089=> p0492p Minimum Proof Graphs and Fastest-Cut-First Search Heuristics, Timothy Furtak, Michael Buro, http://ijcai.org/papers09/Abstracts/089.html Alpha-Beta is the most common game tree search algorithm, due to its high-performance and straightforward implementation. In practice one must find the best trade-off between heuristic evaluation time and bringing the subset of nodes explored closer to a minimum proof graph. In this paper we present a series of structural properties of minimum proof graphs that help us to prove that finding such graphs is NP-hard for arbitrary DAG inputs, but can be done in linear time for trees. We then introduce the class of fastest-cut-first search heuristics that aim to approximate minimum proof graphs by sorting moves based on approximations of sub-DAG values and sizes. To explore how various aspects of the game tree (such as branching factor and distribution of move values) affect the performance of Alpha-Beta we introduce the class of ``Prefix Value Game Trees'' that allows us to label interior nodes with true minimax values on the fly without search. Using these trees we show that by explicitly attempting to approximate a minimum game tree we are able to achieve performance gains over Alpha-Beta with common extensions. txt: http://ijcai.org/papers09/Papers/IJCAI09-089.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:52 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =09==> 0499p Control-based Clause Sharing in Parallel SAT Solving, Youssef Hamadi, Said Jabbour, Lakhdar Sais, http://ijcai.org/papers09/Abstracts/090.html Conflict driven clause learning, one of the most important component of modern SAT solvers, is also recognized as very important in parallel SAT solving. Indeed, it allows clause sharing between multiple processing units working on related (sub-)problems. However, without limitation, sharing clauses might lead to an exponential blow up in communication or to the sharing of irrelevant clauses. This paper, proposes two innovative policies to dynamically adjust the size of shared clauses between any pair of processing units. The first approach controls the overall number of exchanged clauses whereas the second additionally exploits the relevance quality of shared clauses. Experimental results show important improvements of the state-of the-art parallel SAT solver. text: http://ijcai.org/papers09/Papers/IJCAI09-090.pdf [Ответ][Цитата]
Стр.8 (39): 1  ...  4  5  6  7  [8]  9  10  11  12  ...  39 << < Пред. | След. > >>