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

IEEE International Conference on Robotics and Automation (ICRA)

作者： Hsu, D Sánchez-Ante, G Sun, Z Natl Univ Singapore Dept Comp Sci Singapore Singapore

ISBN: (纸本)078038914X

A number of advanced sampling strategies have been proposed in recent years to address the narrow passage problem for probabilistic roadmap (PRM) planning. These sampling strategies all have unique strengths, but none of them solves the problem completely. In this paper, we present a general and systematic approach for adaptively combining multiple sampling strategies so that their individual strengths are preserved. We have performed experiments with this approach on robots with up to 12 degrees of freedom in complex 3-D environments. Experiments show that although the performance of individual sampling strategies varies across different environments, the adaptive hybrid sampling strategies constructed with this approach perform consistently well in all environments. Further, we show that, under reasonable assumptions, the adaptive strategies are provably competitive against all individual strategies used.

关键词： robotics motion planning randomized algorithms probabilistic roadmap planners

来源：评论

学校读者我要写书评

暂无评论

Making 3D binary digital images well-composed

Making 3D binary digital images well-composed

引用

Conference on Vision Geometry XIII

作者： Siqueira, M Latecki, LJ Gallier, J Univ Penn Philadelphia PA 19104 USA

ISBN: (纸本)0819456489

A 3D binary digital image is said to be well-composed if and only if the set of points in the faces shared by the voxels of foreground and background points of the image is a 2D manifold. Well-composed images enjoy important topological and geometric properties;in particular, there is only one type of connected component in any well-composed image, as 6-, 14-, 18-, and 26-connected components are equal. This implies that several algorithms used in computer vision, computer graphics, and image processing become simpler. For example, thinning algorithms do not suffer from the irreducible thickness problem if the image is well-composed, and the extraction of isosurfaces from well-composed images using the Marching Cubes (MC) algorithm or some of its enhanced variations can be simplified, as only six out of the fourteen canonical cases of cube-isosurface intersection can occur. In this paper, we introduce a new randomized algorithm for making 3D binary digital images that are not well-composed into well-composed ones. We also analyze the complexity and convergence of our algorithm, and present experimental evidence of its effectiveness when faced with practical medical imaging data.

关键词： well-composed images digital topology randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Utility optimal scheduling for general reward states and stability constraint

Utility optimal scheduling for general reward states and sta...

引用

44th IEEE Conference on Decision Control/European Control Conference (CCD-ECC)

作者： Chaporkar, Prasanna Sarkar, Saswati Univ Penn Dept Elect & Syst Engn Philadelphia PA 19104 USA

ISBN: (纸本)0780395670

We consider a queueing system with n parallel queues, which receives a reward for the service it provides. Our aim is to maximize the expected reward obtained per unit time (utility) while ensuring that the mean queue length in each of the queues is bounded (stability). We show that the optimal policy has counter intuitive properties because of the general reward states and stability constraint. For example, the greedy policy of serving a customer that fetches maximum reward need not be optimal. In addition, the optimal policy may belong to a class of non work-conserving policies. We obtain two different policies that attain the above optimality goal. The first policy arbitrates service randomly based on the current reward states and probabilities that depend on system statistics. The second policy arbitrates service deterministically based only on the queue lengths and the current reward states, and does not require any knowledge of the system statistics. The proposed policies are optimal in a large class of policies that includes off-line policies, which use knowledge of past, present and even future arrival and reward states in their decision processes.

关键词： queueing theory utility maximization stability randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A better algorithm for uniform metrical task systems with few states

A better algorithm for uniform metrical task systems with fe...

引用

8th International Symposium on Parallel Architectures, algorithms and Networks

作者： Bein, W Larmore, LL Noga, J Univ Nevada Sch Comp Sci Las Vegas NV 89154 USA

ISBN: (纸本)0769525091

We give a randomized algorithm (the "Wedge Algorithm") of competitiveness (3)/H-2(k) - (1)/(2k) for any metrical task system on a uniform space of k points, for any k >= 2, where H-k = Sigma(k)(i=1) (1)/(i) the k(th) harmonic number. This algorithm has better competitiveness than the Irani-Seiden algorithm if k is smaller than 10(8). The algorithm is better by a factor of 2 if k < 47.

关键词： online algorithms randomized algorithms task systems

来源：评论

学校读者我要写书评

暂无评论

Automated surveillance track filter tuning by randomized algorithms

Automated surveillance track filter tuning by Randomized alg...

引用

5th International Conference on Information Fusion (FUSION 2002)

作者： Boers, Y Driessen, H Laclé, N THALES NEDERLAND Hengelo Netherlands

ISBN: (纸本)0972184414

Tuning of fine tuning of a tracker system turns out to be a hard job in practice. The main reason for this is that in a practical (surveillance) tracker system there are a lot of design parameters and a lot of competing requirements to be met. This paper provides the user with an algorithm to tune a tracker system automatically and at the same time obtain quantitative results in terms of the optimality of the solution. The theory of randomized algorithms is used to obtain probabilistic statements on the quality, of the output of the tuning process. A simplified example illustrates how the developed theory is to be used.

关键词： target tracking tuning randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized qeue management for DiffServ 05

Randomized qeue management for DiffServ

引用

Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures

作者： Nir Andelman Tel-Aviv University Tel-Aviv Israel

ISBN: (纸本)9781581139860

We focus on the online problem of queue management in networks providing differentiated services. As in DiffServ, packets are divided into two priority groups. Low priority packets are assigned the value of 1 and high priority packets are assigned the value of α > 1. The goal is to maximize the total value of packets that are sent. Restricted to FIFO queues, the packets must be sent by the order of their arrival, however we are allowed to preempt packets from the *** deterministic online algorithms for this model have been presented in previous papers. Currently, the best online algorithm known for this problem has a competitive ratio of 1.304 for the worst case α [17]. In this work we consider randomized online algorithms. Our main result is an online policy that outperforms any deterministic policy and achieves a competitive ratio of 1.25, by using a single random bit. This result is lower than the deterministic lower bound of 1.281 [19]. We then derive a general lower bound for randomized algorithms of 1.197.A natural extension of this model is to assign arbitrary packet values to the input packets. Currently, the best competitive ratio achieved for a deterministic policy is 1.75 [7]. We present a randomized comparison based online policy with the same competitive ratio. Since no deterministic comparison based policy is known to have a competitive ratio better than 2, we believe that this result demonstrates the potential of using randomization to outperform deterministic policies, as in the two value model.

关键词： active queue management randomized algorithms online algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Two algorithms for leader election and network size estimation in mobile ad hoc networks

Two algorithms for leader election and network size estimati...

引用

作者： Neumann, Nicholas Gerard Texas A&M University

We develop two algorithms for important problems in mobile ad hoc networks (MANETs). A MANET is a collection of mobile processors (nodes) which communicate via message passing over wireless links. Each node can communicate directly with other nodes within a speciﬁed transmission radius; other communication is accomplished via message relay. Communication links may go up and down in a MANET (as nodes move toward or away from each other); thus, the MANET can consist of multiple connected components, and connected components can split and merge over time. We ﬁrst present a deterministic leader election algorithm for asynchronous MANETs along with a correctness proof for it. Our work involves substantial modiﬁcations of an existing algorithm and its proof, and we adapt the existing algorithm to the asynchronous environment. Our algorithms running time and message complexity compare favorably with existing algorithms for leader election in MANETs. Second, many algorithms for MANETs require or can beneﬁt from knowledge about the size of the network in terms of the number of processors. As such, we present an algorithm to approximately determine the size of a MANET. While the algorithms approximations of network size are only rough ones, the algorithm has the important qualities of requiring little communication overhead and being tolerant of link failures.

关键词： mobile ad hoc networks leader election network size estimation distributed computing randomized algorithms Book Thesis

来源：评论

学校读者我要写书评

暂无评论

Work-competitive scheduling for cooperative computing with dynamic groups

引用

SIAM JOURNAL ON COMPUTING 2005年第4期34卷 848-862页

作者： Georgiou, C Russell, A Shvartsman, AA Univ Cyprus Dept Comp Sci Nicosia Cyprus Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA MIT Lab Comp Sci & Artificial Intelligence Cambridge MA 02139 USA

The problem of cooperatively performing a set of t tasks in a decentralized computing environment subject to failures is one of the fundamental problems in distributed computing. The setting with partitionable networks is especially challenging, as algorithmic solutions must accommodate the possibility that groups of processors become disconnected ( and, perhaps, reconnected) during the computation. The efficiency of task-performing algorithms is often assessed in terms of work: the total number of tasks, counting multiplicities, performed by all of the processors during the computation. In general, the scenario where the processors are partitioned into g disconnected components causes any task-performing algorithm to have work Omega( t center dot g) even if each group of processors performs no more than the optimal number of Theta(t) tasks. Given that such pessimistic lower bounds apply to any scheduling algorithm, we pursue a competitive analysis. Specifically, this paper studies a simple randomized scheduling algorithm for p asynchronous processors, connected by a dynamically changing communication medium, to complete t known tasks. The performance of this algorithm is compared against that of an omniscient off-line algorithm with full knowledge of the future changes in the communication medium. The paper describes a notion of computation width, which associates a natural number with a history of changes in the communication medium, and shows both upper and lower bounds on work-competitiveness in terms of this quantity. Specifically, it is shown that the simple randomized algorithm obtains the competitive ratio ( 1 + cw/ e), where cw is the computation width and e is the base of the natural logarithm ( e = 2.7182...);this competitive ratio is then shown to be tight.

关键词： on-line algorithms competitive analysis partitionable networks distributed computation independent tasks randomized algorithms work complexity

来源：评论

学校读者我要写书评

暂无评论

Abstract combinatorial programs and efficient property testers

引用

SIAM JOURNAL ON COMPUTING 2005年第3期34卷 580-615页

作者： Czumaj, A Sohler, C New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA Univ Paderborn Heinz Nixdorf Inst D-33102 Paderborn Germany Univ Paderborn Dept Comp Sci D-33102 Paderborn Germany

Property testing is a relaxation of classical decision problems which aims at distinguishing between functions having a predetermined property and functions being far from any function having the property. In this paper we present a novel framework for analyzing property testing algorithms. Our framework is based on a connection of property testing and a new class of problems which we call abstract combinatorial programs. We show that if the problem of testing a property can be reduced to an abstract combinatorial program of small dimension, then the property has an efficient tester. We apply our framework to a variety of problems. We present efficient property testing algorithms for geometric clustering problems, for the reversal distance problem, and for graph and hypergraph coloring problems. We also prove that, informally, any hereditary graph property can be efficiently tested if and only if it can be reduced to an abstract combinatorial program of small size. Our framework allows us to analyze all our testers in a unified way, and the obtained complexity bounds either match or improve the previously known bounds. Furthermore, even if the asymptotic complexity of the testers is not improved, the obtained proofs are significantly simpler than the previous ones. We believe that our framework will help to understand the structure of efficiently testable properties.

关键词： randomized algorithms approximation algorithms property testing clustering problems coloring hereditary graph properties

来源：评论

学校读者我要写书评

暂无评论

PROBABILISTIC ALGORITHMIC KNOWLEDGE

引用

LOGICAL METHODS IN COMPUTER SCIENCE 2005年第3期1卷

作者： Halpern, Joseph Pucella, Riccardo Cornell Univ Ithaca NY 14853 USA Northeastern Univ Boston MA 02115 USA

The framework of algorithmic knowledge assumes that agents use deterministic knowledge algorithms to compute the facts they explicitly know. We extend the framework to allow for randomized knowledge algorithms. We then characterize the information provided by a randomized knowledge algorithm when its answers have some probability of being incorrect. We formalize this information in terms of evidence;a randomized knowledge algorithm returning "Yes" to a query about a fact psi provides evidence for psi being true. Finally, we discuss the extent to which this evidence can be used as a basis for decisions.

关键词： Knowledge Probability Evidence randomized algorithms Algorithmic Knowledge Logic

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：