In the map verification problem, a robot is given a (possibly incorrect) map M of the world G with its position and orientation indicated on the map. The task is to find out whether this map, for the given robot posit...
详细信息
In the map verification problem, a robot is given a (possibly incorrect) map M of the world G with its position and orientation indicated on the map. The task is to find out whether this map, for the given robot position and its orientation in the map, is correct for the world G. We consider the world model of a graph G = (V-G, E-G) in which, for each vertex, edges incident to the vertex are ordered cyclically around that vertex. (This also holds for the map M = (V-M, E-M).) The robot can traverse edges and enumerate edges incident on the current vertex, but it cannot distinguish vertices (and edges) from each other. To solve the verification problem, the robot uses a portable edge marker, that it can put down at an edge of the graph world G and pick up later as needed. The robot can recognize the edge marker when it encounters it in the world G. By reducing the verification problem to an exploration problem, verification can be completed in O(\V-G\ x \E-G\) edge traversals (the mechanical cost) with the help of a single vertex marker which can be dropped and picked up at vertices of the graph world (G. Dudek, M. Jenkin, E. Milios, and D. Wilkes, IEEE Trans. on Robotics and Automation, vol. 7, pp. 859-865, 1991;Robotics and Autonomous Systems, vol. 22(2), pp. 159-178, 1997). In this paper, we show a strategy that verifies a map in O(\V-M\) edge traversals only, using a single edge marker, when M is a plane embedded graph, even though G may not be planar (e.g., G may contain overpasses, tunnels, etc.).
作者：
Koga, HFujitsu Labs Ltd
Network Processor Lab Nakahara Ku Kawasaki Kanagawa 2118588 Japan Univ Tokyo
Dept Informat Sci Tokyo 113 Japan
To playback multimedia data smoothly via the world-wide Internet, jitter, the variability of delay of individual packets, must be kept low. We examine on-line algorithms in a router to regulate jitter for a given mult...
详细信息
To playback multimedia data smoothly via the world-wide Internet, jitter, the variability of delay of individual packets, must be kept low. We examine on-line algorithms in a router to regulate jitter for a given multimedia stream by holding packets in an internal buffer. The previous work solved the problem with focusing only on the buffer size, allowing a packet to stay in the router infinitely long unless the internal buffer is full. This assumption is unrealistic for many real-time applications. Our main contribution is to introduce a new constraint that a packet can stay in the router at most for a constant time which we name the permitted delay time in order to provide the stream communication with real-time property, besides the conventional constraint about the buffer size. We present a nearly optimal on-line algorithm in terms of competitiveness for this new version of the problem. Our analysis yields the result that the competitiveness of on-line algorithms depends on the permitted delay time rather than the buffer size. We also make clear quantitatively how much jitter is removed by our on-line algorithm. Copyright (C) 2001 John Wiley & Sons, Ltd.
We present an on-line strategy that enables a mobile robot with vision to explore an unknown simple polygon. We prove that the resulting tour is less than 26.5 times as long as the shortest watchman tour that could be...
详细信息
We present an on-line strategy that enables a mobile robot with vision to explore an unknown simple polygon. We prove that the resulting tour is less than 26.5 times as long as the shortest watchman tour that could be computed off-line. Our analysis is doubly founded on a novel geometric structure called the angle hull. Let D be a connected region inside a simple polygon, P. We de ne the angle hull of D, AH(D), to be the set of all points in P that can see two points of D at a right angle. We show that the perimeter of AH (D) cannot exceed in length the perimeter of D by more than a factor of 2. This upper bound is tight.
In this note we consider a new problem, the so-called bin-batching problem related to variable-sized bin covering. A best possible onlinealgorithm is presented. (C) 2001 Elsevier Science B.V. All rights reserved.
In this note we consider a new problem, the so-called bin-batching problem related to variable-sized bin covering. A best possible onlinealgorithm is presented. (C) 2001 Elsevier Science B.V. All rights reserved.
An on-line portfolio selection strategy with transaction costs is presented. It ensures investors to achieve at least the same exponential growth rate of wealth as the best stock for a long term. This equipped with a ...
详细信息
An on-line portfolio selection strategy with transaction costs is presented. It ensures investors to achieve at least the same exponential growth rate of wealth as the best stock for a long term. This equipped with a new prediction method based on "cross rates" for price relative sequences yields a profitable algorithm, which has been tested on real data from the London Stock Exchange.
Consider the execution of a parallel application that dynamically generates parallel jobs with specified resource requirements during its execution. We assume that there is not sufficient knowledge about the running t...
详细信息
Consider the execution of a parallel application that dynamically generates parallel jobs with specified resource requirements during its execution. We assume that there is not sufficient knowledge about the running times and the number of jobs generated in order to precompute a schedule for such applications. Rather, the scheduling decisions have to be made on-line during runtime based on incomplete information. We present several on-line scheduling algorithms for various interconnection topologies that use some a priori information about the job running times or guarantee a good competitive ratio that depends on the runtime ratio of all generated jobs. All algorithms presented have optimal competitive ratio up to small additive constants, and are easy to implement. (C) 2001 Elsevier Science B.V. All rights reserved.
：We present three open combinatorial optimization problems from the standpoint of competitive analysis, in the case that there is no complete information.
：We present three open combinatorial optimization problems from the standpoint of competitive analysis, in the case that there is no complete information.
We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of 3 + root 8 approximate to 5.828 for the deterministic ve...
详细信息
We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of 3 + root 8 approximate to 5.828 for the deterministic version, and 3.31/ln 2.155 approximate to 4.311 for its randomized variant, improving the previous competitive ratios of 8 and 2e approximate to 5.436. We also prove lower bounds of 2.4380 on the: competitive ratio of deterministic algorithms and 1.8372 on the competitive ratio of randomized algorithms for this problem. (C) 2000 Academic Press.
Configurable digital systems offer flexibility that leads to cost reduction, performance tuning, and fault tolerance. While one can use FPGA-based methods to synthesize configurable arithmetic structures, this approac...
详细信息
ISBN:
(纸本)0780365143
Configurable digital systems offer flexibility that leads to cost reduction, performance tuning, and fault tolerance. While one can use FPGA-based methods to synthesize configurable arithmetic structures, this approach results in limited functionality and/or excessive complexity, given that off-the-shelf FPGAs are endowed with only bit-level computational capabilities. Using serial arithmetic cells can increase the ratio of resources devoted to computation (arithmetic, logic) versus communication (wiring), thereby improving per-chip performance or cost-effectiveness. When combined with pipelining, even the absolute latency can be improved. We argue that a controlled-precision digit-serial additive multiplier constitutes an ideal building block for configurable arithmetic arrays and detail our solutions for control of functionality, selection of precision, and reduction of power dissipation within such an array.
The input and output of an on-line computation involving redundant numbers must generally be compatible with standard nonredundant formats. When rounding of a result is required in the last computation step, the proce...
详细信息
ISBN:
(纸本)0780365143
The input and output of an on-line computation involving redundant numbers must generally be compatible with standard nonredundant formats. When rounding of a result is required in the last computation step, the process can be combined with on-the-fly conversion of the redundant output into nonredundant form and thus introduces no extra delay. However, if multiple on-line operations are to be performed before obtaining a final result, the preceding method would be inapplicable to the intermediate results. We present a solution scheme where rounding (subtraction of ulp, no action, addition of ulp) is represented by an additional digit attached to the number, thus obviating the need for modifying any of the previously produced digits. This added digit forms a second least-significant digit (LSD), leading to the designation "double-LSD numbers" for the resulting representation. We show that on-line arithmetic with double-LSD numbers is only slightly more complex than with ordinary signed-digit numbers.
暂无评论