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

MATHEMATICAL AND COMPUTER MODELLING 1997年第3期25卷 103-115页

作者： Musman, SA Lehner, PE Elsaesser, C MITRE CORP CTR ARTIFICIAL INTELLIGENCEMCLEANVA 22102

Problems such as searching for enemy units on a battlefield, detecting smugglers as they cross an international border, and skip tracing involve generating plans to employ limited collection resources to search for moving targets that are trying to avoid detection. This paper presents an automated approach for generating plans to search for ''elusive agents''. We also describe an implementation for the military problem of searching for mobile enemy ground units. The approach consists of three steps. First, it uses automated mobility and terrain analysis to hypothesize a set of possible movement plans for the targets. These plans are weighted with user-specified and heuristic probability estimates. Next, models of the available sensor resources are applied to identify observation ''windows''. These windows are regions in space and time where the target agents may be detected if they are following one of the hypothesized plans. Third, we generate a search plan for the available sensor assets (which can be any combination of mobile and fixed sensors) by heuristically searching through alternative subsets of the observation windows. Each search plan, defined as a temporally-ordered set of observation windows, is evaluated by exercising an automatically-constructed Bayesian network that summarizes the results of the terrain, route planning, and sensor coverage analysis. An empirical evaluation of this system was performed with results supporting its utility.

关键词： moving target search probabilistic reasoning anytime algorithm sensors planning

来源：评论

学校读者我要写书评

暂无评论

Bargaining with limited computation: Deliberation equilibrium

引用

ARTIFICIAL INTELLIGENCE 2001年第2期132卷 183-217页

作者： Larson, K Sandholm, T Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

We develop a normative theory of interaction-negotiation in particular-among self-interested computationally limited agents where computational actions are game theoretically treated as part of an agent's strategy. We focus on a 2-agent setting where each agent has an intractable individual problem, and there is a potential gain from pooling the problems, giving rise to an intractable joint problem. At any time, an agent can compute to improve its solution to its own problem, its opponent's problem, or the joint problem. At a deadline the agents then decide whether to implement the joint solution, and if so, how to divide its value (or cost). We present a fully normative model for controlling anytime algorithms where each agent has statistical performance profiles which are optimally conditioned on the problem instance as well as on the path of results of the algorithm run so far. Using this model, we introduce a solution concept, which we call deliberation equilibrium. It is the perfect Bayesian equilibrium of the game where deliberation actions are part of each agent's strategy. The equilibria differ based on whether the performance profiles are deterministic or stochastic, whether the deadline is known or not, and whether the proposer is known in advance or not. We present algorithms for finding the equilibria. Finally, we show that there exist instances of the deliberation-bargaining problem where no pure strategy equilibria exist and also instances where the unique equilibrium outcome is not Pareto efficient. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： automated negotiation multiagent systems game theory resource-bounded reasoning bounded rationality bargaining anytime algorithm

来源：评论

学校读者我要写书评

暂无评论

Combined planning and scheduling in a divergent production system with co-production: A case study in the lumber industry

引用

COMPUTERS & OPERATIONS RESEARCH 2011年第9期38卷 1238-1250页

作者： Gaudreault, Jonathan Frayret, Jean-Marc Rousseau, Alain D'Amours, Sophie Univ Laval FORAC Res Consortium Quebec City PQ G1K 7P4 Canada

Many research initiatives carried out in production management consider process planning and operations scheduling as two separate and sequential functions. However, in certain contexts, the two functions must be better integrated. This is the case in divergent production systems with co-production (i.e. production of different products at the same time from a single product input) when alternative production processes are available. This paper studies such a context and focuses on the case of drying and finishing operations in a softwood lumber facility. The situation is addressed using a single model that simultaneously performs process planning and scheduling. We evaluate two alternative formulations. The first one is based on mixed integer programming (MIP) and the second on constraint programming (CP). We also propose a search procedure to improve the performance of the CP approach. Both approaches are compared with respect to their capacity to generate good solutions in short computation time. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Integrated planning and scheduling Mathematical programming Constraint programming Wood drying and finishing anytime algorithm Lumber industry

来源：评论

学校读者我要写书评

暂无评论

CABOB: A fast, optimal algorithm for winner determination in combinatorial auctions

引用

MANAGEMENT SCIENCE 2005年第3期51卷 374-390页

作者： Sandholm, T Suri, S Gilpin, A Levine, D Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA CombineNet Inc Pittsburgh PA 15222 USA

Combinatorial auctions where bidders can bid on bundles of items' can lead to more economically efficient allocations, but determining the winners is NP-complete and inapproximable. We present CABOB, a sophisticated optimal search algorithm for the problem. It uses decomposition techniques, upper and lower, bounding (also across components), elaborate and dynamically chosen bid-ordering heuristics, and a host of structural observations. CABOB attempts to capture structure in any instance. without making assumptions about the instance distribution. Experiments against the fastest prior algorithm, CPLEX 8.0, show that CABOB is often faster, seldom drastically slower, and in many cases drastically faster-especially in cases with structure. CABOB's search runs in linear space and has significantly better anytime performance than CPLEX We also uncover interesting aspects of the problem itself. First, problems with short bids, which were hard for the first generation of specialized algorithms, are easy. Second, almost all of the CATS distributions are easy, and the run time is virtually unaffected by the number of goods. Third, we test several random restart strategies, showing that they do not help on this problem-the run-time distribution does not have a heavy tail.

关键词： auction combinatorial auction winner determination winner-determination algorithm search branch and bound MIP anytime algorithm branching heuristics dynamically chosen heuristic bounding across components random restart

来源：评论

学校读者我要写书评

暂无评论

Whole-Book Recognition

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2012年第12期34卷 2467-2480页

作者： Xiu, Pingping Baird, Henry S. Microsoft Advertising R&D Redmond WA 98052 USA Lehigh Univ Dept Comp Sci & Engn Bethlehem PA 18015 USA

Whole-book recognition is a document image analysis strategy that operates on the complete set of a book's page images using automatic adaptation to improve accuracy. We describe an algorithm which expects to be initialized with approximate iconic and linguistic models-derived from (generally errorful) OCR results and (generally imperfect) dictionaries-and then, guided entirely by evidence internal to the test set, corrects the models which, in turn, yields higher recognition accuracy. The iconic model describes image formation and determines the behavior of a character-image classifier, and the linguistic model describes word-occurrence probabilities. Our algorithm detects "disagreements" between these two models by measuring cross entropy between 1) the posterior probability distribution of character classes (the recognition results resulting from image classification alone) and 2) the posterior probability distribution of word classes (the recognition results from image classification combined with linguistic constraints). We show how disagreements can identify candidates for model corrections at both the character and word levels. Some model corrections will reduce the error rate over the whole book, and these can be identified by comparing model disagreements, summed across the whole book, before and after the correction is applied. Experiments on passages up to 180 pages long show that when a candidate model adaptation reduces whole-book disagreement, it is also likely to correct recognition errors. Also, the longer the passage operated on by the algorithm, the more reliable this adaptation policy becomes, and the lower the error rate achieved. The best results occur when both the iconic and linguistic models mutually correct one another. We have observed recognition error rates driven down by nearly an order of magnitude fully automatically without supervision (or indeed without any user intervention or interaction). Improvement is nearly monotonic, and asymp

关键词： Whole-book recognition document image recognition book recognition style consistency isogeny adaptive classification adaptive OCR adaptive machine learning model adaptation anytime algorithm cross entropy

来源：评论

学校读者我要写书评

暂无评论

Improved Lower Bounds for Graph Edit Distance

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2018年第3期30卷 503-516页

作者： Blumenthal, David B. Gamper, Johann Free Univ Bozen Bolzano Fac Comp Sci I-39100 South Tyrol Bozen Italy

The problem of deriving lower and upper bounds for the edit distance between undirected, labeled graphs has recently received increasing attention. However, only one algorithm has been proposed that allegedly computes not only an upper but also a lower bound for non-uniform edit costs and incorporates information about both node and edge labels. In this paper, we demonstrate that this algorithm is incorrect. We present a corrected version BRANCH that runs in O(n(2)Delta(3) + n(3)) time, where Delta is the maximum of the maximum degrees of input graphs G and H. We also develop a speed-up BRANCHFAST that runs in O(n(2)Delta(3) + n(3)) time and computes an only slightly less accurate lower bound. The lower bounds produced by BRANCH and BRANCHFAST are shown to be pseudo-metrics on a collection of graphs. Finally, we suggest an anytime algorithm BRANCHTIGHT that iteratively improves BRANCH's lower bound. BRANCHTIGHT runs in O(n(3)Delta(2) + I (n(2)Delta(3) + n(3)) time, where the number of iterations I is controlled by the user. A detailed experimental evaluation shows that all suggested algorithms are Pareto optimal, that they are very effective when used as filters for edit distance range queries, and that they perform excellently when used within classification frameworks.

关键词： Graph edit distance lower bounds anytime algorithm graph databases graph matching

来源：评论

学校读者我要写书评

暂无评论

Learning while solving problems in best first search

引用

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART A-SYSTEMS AND HUMANS 1998年第4期28卷 535-542页

作者： Sarkar, S Chakrabarti, PP Ghose, S Indian Inst Technol Dept Comp Sci & Engn Guwahati 781001 India Indian Inst Technol Dept Comp Sci & Engn Kharagpur 721302 W Bengal India

We investigate the role of learning in search-based systems for solving optimization problems. Many AI problem solving systems solve problems repeatedly from the same domain. If the problems come from the same distribution in the learning phase and the problem solving phase, the problem solver can acquire information while solving problems, which can be used to solve subsequent problems faster. We use a learning model, where the values of a set of features can be used to induce a clustering of the problem state space. The feasible set of h* values corresponding to each cluster is called h*set. If we relax the optimality guarantee, and tolerate a risk factor, the distribution of h*set can be used to expedite search and produce results within a given risk of suboptimality. The offline learning method consists of solving a batch of problems by using A* to learn the distribution of the h*set in the learning phase. This distribution can be used to solve the-rest of the problems effectively. We show how the knowledge acquisition phase can be integrated with the problem solving phase. We present a continuous on-line learning scheme that uses an "anytime" algorithm to learn continuously while solving problems. The system starts with initial assumed distributions of h*set which are used to solve the initial problems. The results are used to update the distributions continuously and with time the distributions converge.

关键词： anytime algorithm best first search continuous learning heuristic features learning problem solving

来源：评论

学校读者我要写书评

暂无评论

Generalized Alternating Projection for Weighted-l_2,1 Minimization with Applications to Model-Based Compressive Sensing

引用

SIAM JOURNAL ON IMAGING SCIENCES 2014年第2期7卷 797-823页

作者： Liao, Xuejun Li, Hui Carin, Lawrence Duke Univ Dept Elect & Comp Engn Durham NC 27708 USA Duke Univ Durham NC 27708 USA

We consider the group basis pursuit problem, which extends basis pursuit by replacing the l(1) norm with a weighted-l(2,1) norm. We provide an anytime algorithm, called generalized alternating projection (GAP), to solve this problem. The GAP algorithm extends classical alternating projection to the case in which projections are performed between convex sets that undergo a systematic sequence of changes. We prove that, under a set of group-restricted isometry property (group-RIP) conditions, the reconstruction error of GAP monotonically converges to zero. Thus the algorithm can be interrupted at any time to return a valid solution and can be resumed subsequently to improve the solution. This anytime convergence property saves iterations on retracting and correcting mistakes, which, along with an effective acceleration scheme, makes GAP converge fast. Moreover, the periteration computation is inexpensive, consisting of sorting of a linear array followed by groupwise thresholding and linear transform of vectors for which fast algorithms often exist. We evaluate the algorithmic performance through extensive experiments in which GAP is compared to other state-of-the-art algorithms and applied to compressive sensing of natural images and video.

关键词： weighted l(2,1) minimization generalized alternating projection anytime algorithm group-RIP conditions compressive sensing image and video reconstruction

来源：评论

学校读者我要写书评

暂无评论

Flexible adjustment of data: An exercise in relational algebra

引用

INTERNATIONAL JOURNAL OF GENERAL SYSTEMS 1997年第1-2期26卷 165-177页

作者： Pittarelli, MA Department of Computer and Information Science State University of New York Institute of Technology at Utica/Rome Utica NY 13504-3050 P.O. Box 3050 United States

Databases may exhibit many forms of incompleteness. This paper explores methods for overcoming incompleteness in the form of missing tuples. Specifically, algorithms are investigated for replacing a relation that is known to be incomplete with a superset. Of particular interest are algorithms that make available at any time a current approximation and with the property that the approximate solution improves monotonically with computing time. Although this paper concentrates on rule matching in rule-based systems, application of these and similar methods to problems of knowledge discovery in incomplete databases is also discussed.

关键词： relational algebra flexible algorithm anytime algorithm rule-based systems

来源：评论

学校读者我要写书评

暂无评论

Coalition structure generation with worst case guarantees

引用

ARTIFICIAL INTELLIGENCE 1999年第1-2期111卷 209-238页

作者： Sandholm, T Larson, K Andersson, M Shehory, O Tohmé, F Washington Univ Dept Comp Sci St Louis MO 63130 USA Carnegie Mellon Univ Inst Robot Pittsburgh PA 15213 USA

Coalition formation is a key topic in multiagent systems. One may prefer a coalition structure that maximizes the sum of the values of the coalitions, but often the number of coalition structures is too large to allow exhaustive search for the optimal one. Furthermore, finding the optimal coalition structure is NP-complete. But then, can the coalition structure found via a partial search be guaranteed to be within a bound from optimum? We show that none of the previous coalition structure generation algorithms can establish any bound because they search fewer nodes than a threshold that we show necessary for establishing a bound. We present an algorithm that establishes a tight bound within this minimal amount of search, and show that any other algorithm would have to search strictly more. The fraction of nodes needed to be searched approaches zero as the number of agents grows. If additional time remains, our anytime algorithm searches further, and establishes a progressively lower tight bound. Surprisingly, just searching one more node drops the bound in half. As desired, our algorithm lowers the bound rapidly early on, and exhibits diminishing returns to computation. It also significantly outperforms its obvious contenders. Finally, we show how to distribute the desired search across self-interested manipulative agents. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： coalition formation anytime algorithm multiagent systems game theory negotiation distributed AI resource-bounded reasoning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：