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

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

Все темы | Новая тема  Стр.10 (39) << < Пред. | След. > >>    Поиск:
Автор	Тема: На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:56 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =106=> 0603p Russian Doll Search with Tree Decomposition, Marti Sanchez, David Allouche, Simon de Givry, Thomas Schiex, http://ijcai.org/papers09/Abstracts/106.html Optimization in graphical models is an important problem which has been studied in many AI frameworks such as weighted CSP, maximum satisfiability or probabilistic networks. By identifying conditionally independent subproblems, which are solved independently and whose optimum is cached, recent Branch and Bound algorithms offer better asymptotic time complexity. But the locality of bounds induced by decomposition often hampers the practical effects of this result because subproblems are often uselessly solved to optimality.Following the Russian Doll Search (RDS) algorithm, a possible approach to overcome this weakness is to (inductively) solve a relaxation of each subproblem to strengthen bounds. The algorithm obtained generalizes both RDS and tree-decomposition based algorithms such as BTD or AND-OR Branch and Bound. We study its efficiency on different problems, closing a very hard frequency assignment instance which has been open for more than 10 years. text: http://ijcai.org/papers09/Papers/IJCAI09-106.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:56 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =107=> 0609p Memory-Based Heuristics for Explicit State Spaces, Nathan R. Sturtevant, Ariel Felner, Max Barrer, Jonathan Schaeffer, Neil Burch, http://ijcai.org/papers09/Abstracts/107.html In many scenarios, quickly solving a relatively small search problem with an arbitrary start and arbitrary goal state is important (e.g., GPS navigation). In order to speed this process, we introduce a new class of memory-based heuristics, called true distance heuristics, that store true distances between some pairs of states in the original state space can be used for a heuristic between any pair of states. We provide a number of techniques for using and improving true distance heuristics such that most of the benefits of the all-pairs shortest-path computation can be gained with less than 1% of the memory. Experimental results on a number of domains show a 6-14 fold improvement in search speed compared to traditional heuristics. The requested URL /papers09/Papers/IJCAI07-107.pdf was not found on this server!!! //* text: http://ijcai.org/papers09/Papers/IJCAI09-107.pdf *// ========================================== PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =108=> 0615p Efficient Incremental Search for Moving Target Search, Xiaoxun Sun, William Yeoh, Sven Koenig, http://ijcai.org/papers09/Abstracts/108.html Incremental search algorithms reuse information from previous searches to speed up the current search and are thus often able to find shortest paths for series of similar search problems faster than by solving each search problem independently from scratch. However, they do poorly on moving target search problems, where both the start and goal cells change over time. In this paper, we thus develop Fringe-Retrieving A* (FRA*), an incremental version of A* that repeatedly finds shortest paths for moving target search in known gridworlds. We demonstrate experimentally that it runs up to one order of magnitude faster than a variety of state-of-the-art incremental search algorithms applied to moving target search in known gridworlds. text: http://ijcai.org/papers09/Papers/IJCAI09-108.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:56 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =109=> 0621p Solving Dynamic Constraint Satisfaction Problems by Identifying Stable Features, Richard J. Wallace, Diarmuid Grimes, Eugene C. Freuder, http://ijcai.org/papers09/Abstracts/109.html This paper presents a new analysis of dynamic constraint satisfaction problems (DCSPs) with finite domains and a new approach to solving them. We first show that even very small changes in a CSP, in the form of addition of constraints or changes in constraint relations, can have profound effects on search performance. These effects are reflected in the amenability of the problem to different forms of heuristic action as well as overall quality of search. In addition, classical DCSP methods perform poorly on these problems because there are sometimes no solutions similar to the original one found. We then show that the same changes do not markedly affect the locations of the major sources of contention in the problem. A technique for iterated sampling that performs a careful assessment of this property and uses the information during subsequent search, performs well even when it only uses information based on the original problem in the DCSP sequence. The result is a new approach to solving DCSPs that is based on a robust strategy for ordering variables rather than on robust solutions. text: http://ijcai.org/papers09/Papers/IJCAI09-109.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:56 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =110=> 0628p Qualitative CSP, Finite CSP, and SAT: Comparing Methods for Qualitative Constraint-based Reasoning, Matthias Westphal, Stefan Wölfl, http://ijcai.org/papers09/Abstracts/110.html Qualitative Spatial and Temporal Reasoning (QSR) is concerned with constraint-based formalisms for representing, and reasoning with, spatial and temporal information over infinite domains. Within the QSR community it has been a widely accepted assumption that genuine qualitative reasoning methods outperform other reasoning methods that are applicable to encodings of qualitative CSP instances. Recently this assumption has been tackled by several authors, who proposed to encode qualitative CSP instances as finite CSP or SAT instances. In this paper we report on the results of a broad empirical study in which we compared the performance of several reasoners on instances from different qualitative formalisms. Our results show that for small-sized qualitative calculi (e.g., Allen's interval algebra and RCC-8) a state-of-the-art implementation of QSR methods currently gives the most efficient performance. However, on recently suggested large-size calculi, e.g., OPRA4, finite CSP encodings provide a considerable performance gain. These results confirm a conjecture by Bessière stating that support-based constraint propagation algorithms provide better performance for large-sized qualitative calculi. text: http://ijcai.org/papers09/Papers/IJCAI09-110.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:57 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =111=> 0634p A* Search with Inconsistent Heuristics, Zhifu Zhang, Nathan R. Sturtevant, R.Holte, J.Schaeffer, A.Felner, http://ijcai.org/papers09/Abstracts/111.html Early research in heuristic search discovered that using inconsistent heuristics with A* could result in an exponential increase in the number of node expansions. As a result, the use of inconsistent heuristics has largely disappeared from practice. Recently, inconsistent heuristics have been shown to be effective in IDA*, especially when applying the bidirectional pathmax (BPMX) enhancement. This paper presents new worst-case complexity analysis of A*'s behavior with inconsistent heuristics, discusses how BPMX can be used with A*, and gives experimental results justifying the use of inconsistent heuristics in A* searches. text: http://ijcai.org/papers09/Papers/IJCAI09-111.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:57 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =112=> 0640p Combining Breadth-First and Depth-First Strategies in Searching for Treewidth, Rong Zhou, Eric A. Hansen, http://ijcai.org/papers09/Abstracts/112.html Breadth-first and depth-first search are basic search strategies upon which many other search algorithms are built. In this paper, we describe an approach to integrating these two strategies in a single algorithm that combines the complementary strengths of both. We show the benefits of this approach using the treewidth problem as an example. text: http://ijcai.org/papers09/Papers/IJCAI09-112.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:57 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: =113=> 0646p Mixing Search Strategies for Multi-Player Games, Inon Zuckerman, Ariel Felner, Sarit Kraus, http://ijcai.org/papers09/Abstracts/113.html There are two basic approaches to generalize the propagation mechanism of the two-player Minimax search algorithm to multi-player (3 or more) games: the MaxN algorithm and the Paranoid algorithm. The main shortcoming of these approaches is that their strategy is fixed. In this paper we suggest a new approach (called MP-Mix) that dynamically changes the propagation strategy based on the players' relative strengths between MaxN, Paranoid and a newly presented offensive strategy. In addition, we introduce the Opponent Impact factor for multi-player games, which measures the players' ability to impact their opponents' score, and show its relation to the relative performance of our new MP-Mix strategy. Experimental results show that MP-Mix outperforms all other approaches under most circumstances. text: http://ijcai.org/papers09/Papers/IJCAI09-113.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:57 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:57 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:57 PART-2: CONSTRAINTS, SATISFIABILITY, and SEARCH: [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:58 [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:58 [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:58 [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:58 [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:58 [Ответ][Цитата]
Стр.10 (39): 1  ...  6  7  8  9  [10]  11  12  13  14  ...  39 << < Пред. | След. > >>