These are representative sample records from Science.gov related to your search topic.
For comprehensive and current results, perform a real-time search at Science.gov.
1

Shortest paths algorithms: theory and experimental evaluation  

Microsoft Academic Search

We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove interesting theoretical results suggested by the experimental data. Our computational study is based on several natural problem classes which identify strengths and weaknesses of various algorithms. These problem classes and algorithm implementations form

Boris V. Cherkassky; Andrew V. Goldberg; Tomasz Radzikt

1994-01-01

2

Efficient Algorithms for Shortest Paths in Sparse Networks  

Microsoft Academic Search

Algorithms for finding shortest paths are presented which are faster than algorithms previously known on networks which are relatively sparse in arcs. Known results which the results of this paper extend are surveyed briefly and analyzed. A new implementation for priority queues is employed, and a class of “arc set partition” algorithms is introduced. For the single source problem on

Donald B. Johnson

1977-01-01

3

An Improved Physarum polycephalum Algorithm for the Shortest Path Problem  

PubMed Central

Shortest path is among classical problems of computer science. The problems are solved by hundreds of algorithms, silicon computing architectures and novel substrate, unconventional, computing devices. Acellular slime mould P. polycephalum is originally famous as a computing biological substrate due to its alleged ability to approximate shortest path from its inoculation site to a source of nutrients. Several algorithms were designed based on properties of the slime mould. Many of the Physarum-inspired algorithms suffer from a low converge speed. To accelerate the search of a solution and reduce a number of iterations we combined an original model of Physarum-inspired path solver with a new a parameter, called energy. We undertook a series of computational experiments on approximating shortest paths in networks with different topologies, and number of nodes varying from 15 to 2000. We found that the improved Physarum algorithm matches well with existing Physarum-inspired approaches yet outperforms them in number of iterations executed and a total running time. We also compare our algorithm with other existing algorithms, including the ant colony optimization algorithm and Dijkstra algorithm. PMID:24982960

Wang, Qing; Adamatzky, Andrew; Chan, Felix T. S.; Mahadevan, Sankaran

2014-01-01

4

Modeling wildfire propagation with Delaunay triangulation and shortest path algorithms  

E-print Network

Modeling wildfire propagation with Delaunay triangulation and shortest path algorithms Alexander In this paper, a methodology for modeling surface wildfire propagation through a complex landscape is presented, wildfire modeling 1 Introduction During the years 2000-2004, the National Interagency Fire Center (NIFC

Smith, J. MacGregor

5

On the Representability of Arbitrary Path Sets as Shortest Paths: Theory, Algorithms, and Complexity  

Microsoft Academic Search

\\u000a The question, whether an optional set of routes can be represented as shortest paths, and if yes, then how, has been a rather\\u000a scarcely investigated problem up until now. In turn, an algorithm that, given an arbitrary set of traffic engineered paths,\\u000a can efficiently compute OSPF link weights as to map the given paths to shortest paths may be of

Gábor Rétvári; Róbert Szabó; József Bíró

2004-01-01

6

E cient Algorithms for the Minimum Shortest Path Steiner Arborescence Problem with Applications to VLSI Physical Design  

E-print Network

E cient Algorithms for the Minimum Shortest Path Steiner Arborescence Problem with Applications is a shortest path in G. Given a triple G;N;r, the MinimumShortest-Path Steiner Arborescence MSPSA problem seeks is a shortest path in G. Given a triple G;N;r, the MinimumShortest-Path Steiner Arborescence MSPSA problem seeks

Kahng, Andrew B.

7

A Heuristic Genetic Algorithm for the Single Source Shortest Path Problem  

Microsoft Academic Search

This paper addresses one of the potential graph-based problems that arises when an optimal shortest path solution, or near optimal solution is acceptable, namely the Single Source Shortest Path (SSP) problem. To this end, a novel Heuristic Genetic Algorithm (HGA) to solve the SSSP problem is developed and evaluated. The proposed algorithm employs knowledge from deterministic techniques and the genetic

Basela S. Hasan; Mohammad A. Khamees; Ashraf S. Hasan Mahmoud

2007-01-01

8

Greedy partitioned algorithms for the shortest-path problem  

SciTech Connect

A partitioned, priority-queue algorithm for solving the single-source best-path problem is defined and evaluated. Finding single-source paths for sparse graphs is notable because of its definite lack of parallelism-no known algorithm are scalable. Qualitatively, they discuss the close relationship between the algorithm and previous work by Quinn, Chikayama, and others. Performance measurements of variations of the algorithm, implemented both in concurrent and imperative programming languages on a shared-memory multiprocessor, are presented. This quantitative analysis of the algorithms provides insights into the tradeoffs between complexity and overhead in graph-searching executed in high-level parallel languages with automatic task scheduling.

Adamson, P.; Tick, E. (Univ. of Oregon (United States))

1991-08-01

9

On shortest paths and sorting  

Microsoft Academic Search

In finding shortest paths, the operation of finding, successively, a minimum from a list of numbers may require more work than the remainder of the algorithm. It is shown how algorithms from sorting literature can be used to accomplish this part of the shortest path algorithm. Bounds on the largest possible amount of work are established, and results of a

Ellis L. Johnson

1972-01-01

10

: A Heuristic Search Algorithm for Finding the k Shortest Paths Husain Aljazzar  

E-print Network

K : A Heuristic Search Algorithm for Finding the k Shortest Paths Husain Aljazzar , Stefan Leue, Germany Email addresses: husain.aljazzar@email.de (Husain Aljazzar), Stefan.Leue@uni-konstanz.de (Stefan

Leue, Stefan

11

Research of SoPC-based improved genetic algorithm on shortest path  

NASA Astrophysics Data System (ADS)

The shortest path problem is a classic problem and is unlikely to find an efficient algorithm for solving it directly. It is applied broadly in practice. Thus rapid and effective solving shortest path problem is very important application value in practice. Genetic Algorithm (GA) is a kind of heuristic global optimization search algorithm that simulates the biology evolutionary system. It is resolved efficiently by this improvement Genetic Algorithm. In this paper, a SoPC-based GA framework is proposed .The experiment results show that improved Genetic Algorithm enhances extremely in the same environment.

Ruan, Hang; Ren, Aifeng; Meng, Ming; Zhao, Wei; Luo, Ming

2011-10-01

12

Approximation Algorithms for Shortest Path Motion Planning extended abstract  

E-print Network

in time O(n=#15; + n log n). The data structure is associated with a new variety of Voronoi diagram. Given]. As for approximation algorithms, Papadimitriou [Pap85] has shown that O(n 3 (L + log(n=#15;)) 2 =#15;) time su in this paper is faster than that of [Pap85] when n#15; 3 is large. Also, the number of arithmetic operations

Clarkson, Kenneth L.

13

Planning image-guided endovascular interventions: guidewire simulation using shortest path algorithms  

NASA Astrophysics Data System (ADS)

Endovascular interventional procedures are being used more frequently in cardiovascular surgery. Unfortunately, procedural failure, e.g., vessel dissection, may occur and is often related to improper guidewire and/or device selection. To support the surgeon's decision process and because of the importance of the guidewire in positioning devices, we propose a method to determine the guidewire path prior to insertion using a model of its elastic potential energy coupled with a representative graph construction. The 3D vessel centerline and sizes are determined for a specified vessel. Points in planes perpendicular to the vessel centerline are generated. For each pair of consecutive planes, a vector set is generated which joins all points in these planes. We construct a graph representing these vector sets as nodes. The nodes representing adjacent vector sets are joined by edges with weights calculated as a function of the angle between the corresponding vectors (nodes). The optimal path through this weighted directed graph is then determined using shortest path algorithms, such as topological sort based shortest path algorithm or Dijkstra's algorithm. Volumetric data of an internal carotid artery phantom (Ø 3.5mm) were acquired. Several independent guidewire (Ø 0.4mm) placements were performed, and the 3D paths were determined using rotational angiography. The average RMS distance between the actual and the average simulated guidewire path was 0.7mm; the computation time to determine the path was 3 seconds. The ability to predict the guidewire path inside vessels may facilitate calculation of vessel-branch access and force estimation on devices and the vessel wall.

Schafer, Sebastian; Singh, Vikas; Hoffmann, Kenneth R.; Noël, Peter B.; Xu, Jinhui

2007-03-01

14

Shortest Paths for Disc Obstacles  

Microsoft Academic Search

\\u000a Given a number of obstacles in a plane, the problem of computing a geodesic (or the shortest path) between two points has\\u000a been studied extensively. However, the case where the obstacles are circular discs has not been explored as much as it deserves.\\u000a In this paper, we present an algorithm to compute a geodesic among a set of mutually disjoint

Deok-soo Kim; Kwangseok Yu; Youngsong Cho; Donguk Kim; Chee-keng Yap

2004-01-01

15

Efficient algorithms for the minimum shortest path Steiner arborescence problem with applications to VLSI physical design  

Microsoft Academic Search

Given an undirected graph G = (V; E) with positive edge weights (lengths) w : E ! <,, a set of termi-nals (sinks) N V, and a unique root node r 2 N, a shortest-path Steiner arborescence (simply called an arborescence in the following) is a Steiner tree rooted at r spanning all terminals in N such that every source-to-sink

Jason Cong; Andrew B. Kahng; Kwok-shing Leung

1998-01-01

16

Highway Hierarchies Hasten Exact Shortest Path Queries  

Microsoft Academic Search

\\u000a We present a new speedup technique for route planning that exploits the hierarchy inherent in real world road networks. Our\\u000a algorithm preprocesses the eight digit number of nodes needed for maps of the USA or Western Europe in a few hours using linear\\u000a space. Shortest (i.e. fastest) path queries then take around eight milliseconds to produce exact shortest paths. This

Peter Sanders; Dominik Schultes

2005-01-01

17

Fractal Structure of Shortest Interaction Paths in Native Proteins and Determination of Residues on a Given Shortest Path  

E-print Network

Fractal structure of shortest paths depends strongly on interresidue interaction cutoff distance. Taking the cutoff distance as variable, the paths are self similar above 6.8 {\\AA} with a fractal dimension of 1.12, remarkably close to Euclidean dimension. Below 6.8 {\\AA}, paths are multifractal. The number of steps to traverse a shortest path is a discontinuous function of cutoff size at short wavelengths. An algorithm is introduced to determine the residues on a given shortest path. Shannon entropy of information transport between two residues along a shortest path is lower than the entropies along longer paths between the same two points leading to the conclusion that communication over shortest paths results in highest lossless encoding.

Erman, Burak

2014-01-01

18

Shortest Paths in Microseconds Rachit Agarwal  

E-print Network

to compute and store a partial shortest path tree (PSPT) for each node. The PSPTs have the property to be an extremely small frac- tion of the entire network; hence, PSPTs can be stored efficiently and each shortest path can be computed ex- tremely quickly. For a real network with 5 million nodes and 69 mil- lion

19

Multi-population Genetic Algorithms with Immigrants Scheme for Dynamic Shortest Path  

E-print Network

Memory-Based Immigrants for Genetic Algorithms in Dynamic Environments Shengxiang Yang Department optimization problems. Among these approches, random immigrants and memory schemes have shown to be bene- ficial in many dynamic problems. This paper proposes a hybrid memory and random immigrants scheme

Yang, Shengxiang

20

An Optimal Algorithm for L1 Shortest Paths Among Obstacles in the Plane  

E-print Network

) [Mi3] and O(n log1.5 n) [CKV, Wi]), but before this work the question of obtaining an optimal case of polygonal obstacles). In more recent work, [Mi2, Mi3] have used a continuous Dijkstra algorithm report [Mi3] erroneously claimed that [BG] had proved that g(n) is bounded by O( n log n log log n

Mitchell, Joseph S.B.

21

An E cient Algorithm for Euclidean Shortest Paths Among Polygonal Obstacles in the Plane  

E-print Network

Kapoor Sachindra N. Maheshwari y Joseph S. B. Mitchell z Abstract We give an algorithm to compute, 4, 6, 8, 10, 15, 13, 17, 22, 21, 23], as well as the recent survey chapter of Mitchell 14 of Mitchell 15], which develops the \\continuous Dijkstra" paradigm, and its improvement by Hershberger

Mitchell, Joseph S.B.

22

The Shortest Path Problem Under Partial Monitoring  

Microsoft Academic Search

Abstract. The on-line shortest path problem is considered under partial monitoring scenarios. At each round, a decision maker has to choose a path between two distinguished vertices of a weighted directed acyclic graph whose edge weights can change in an arbitrary (adversarial) way such that the loss of the chosen path (dened as the sum of the weights of its

András György; Tamás Linder; György Ottucsák

2006-01-01

23

On the Shortest Path Game  

E-print Network

Sep 19, 2014 ... tree, whose child nodes are all leaves, the associated player can reach a decision by simply ... moved to its parent node. In this way, we can ... towards t, since the cost of the path from s to v does not influence the decision in v.

2014-09-19

24

Generalized Greedy Algorithm for Shortest Superstring  

E-print Network

Generalized Greedy Algorithm for Shortest Superstring Zhengjun Cao1,2 , Lihua Liu3 , and Olivier University, China Abstract. In the primitive greedy algorithm for shortest superstring, if a pair of strings of optimal set and generalize the primitive greedy algorithm. The generalized algorithm can be reduced

Markowitch, Olivier

25

Shortest Paths, Soap Films, and Minimal Surfaces  

NSDL National Science Digital Library

You know you're in for a real treat when a lecture starts off with "I just happen to have with me today this bucket filled with soap solution, water, and some glycerin." That happens to be the opening line from a talk given by Professor Michael Dorff at the Mathematical Association of America (MAA). Dorff's talk was quite hands-on and it included a number of skeletal Zometool creations and deconstructed Slinkies, among other items. The title of the talk was "Shortest Paths, Soap Films, and Minimal Surfaces" and it is available here in its entirety. In the lecture, Dorff talks (and demonstrates) the shortest distance between four points, neighborhood accessibility, and a number of fascinating topics.

Dorff, Michael

2012-10-10

26

Shortest paths synthesis for a car-like robot  

Microsoft Academic Search

This paper deals with the complete characterization of the shortest paths for a car-like robot. Previous works have shown that the search for a shortest path may be limited to a simple family of trajectories. Our work completes this study by providing a way to select inside this family an optimal path to link any two configurations. We combine the

P. Soueres; J.-P. Laumond

1996-01-01

27

The role of convexity for solving some shortest path problems in plane without triangulation  

NASA Astrophysics Data System (ADS)

Solving shortest path problems inside simple polygons is a very classical problem in motion planning. To date, it has usually relied on triangulation of the polygons. The question: "Can one devise a simple O(n) time algorithm for computing the shortest path between two points in a simple polygon (with n vertices), without resorting to a (complicated) linear-time triangulation algorithm?" raised by J. S. B. Mitchell in Handbook of Computational Geometry (J. Sack and J. Urrutia, eds., Elsevier Science B.V., 2000), is still open. The aim of this paper is to show that convexity contributes to the design of efficient algorithms for solving some versions of shortest path problems (namely, computing the convex hull of a finite set of points and convex rope on rays in 2D, computing approximate shortest path between two points inside a simple polygon) without triangulation on the entire polygons. New algorithms are implemented in C and numerical examples are presented.

An, Phan Thanh; Hai, Nguyen Ngoc; Hoai, Tran Van

2013-09-01

28

Layered Shortest Path (LASH) Routing in Irregular System Area Networks  

Microsoft Academic Search

In recent years we have seen a growing interest in ir- regular network topologies for cluster interconnects. One problem related to such topologies is that the combination of shortest path and deadlock free routing is difficult. As a result of this the existing solutions for routing in irreg- ular networks either guarantee shortest paths relative to some constraint (like up*\\/down*),

Tor Skeie; Olav Lysne; Ingebjørg Theiss

2002-01-01

29

ON THE ACCELERATION OF SHORTEST PATH CALCULATIONS IN TRANSPORTATION NETWORKS  

SciTech Connect

Shortest path algorithms are a key element of many graph problems. They are used in such applications as online direction finding and navigation, as well as modeling of traffic for large scale simulations of major metropolitan areas. As the shortest path algorithms are an execution bottleneck, it is beneficial to move their execution to parallel hardware such as Field-Programmable Gate Arrays (FPGAs). Hardware implementation is accomplished through the use of a small A core replicated on the order of 20 times on an FPGA device. The objective is to maximize the use of on-board random-access memory bandwidth through the use of multi-threaded latency tolerance. Each shortest path core is responsible for one shortest path calculation, and when it is finished it outputs its result and requests the next source from a queue. One of the innovations of this approach is the use of a small bubble sort core to produce the extract-min function. While bubble sort is not usually considered an appropriate algorithm for any non-trivial usage, it is appropriate in this case as it can produce a single minimum out of the list in O(n) cycles, whwere n is the number of elements in the vertext list. The cost of this min operation does not impact the running time of the architecture, because the queue depth for fetching the next set of edges from memory is roughly equivalent to the number of cores in the system. Additionally, this work provides a collection of simulation results that model the behavior of the node queue in hardware. The results show that a hardware queue, implementing a small bubble-type minimum function, need only be on the order of 16 elements to provide both correct and optimal paths. Because the graph database size is measured in the hundreds of megabytes, the Cray SRAM memory is insufficient. In addition to the A* cores, they have developed a memory management system allowing round-robin servicing of the nodes as well as virtual memory managed over the Hypertransport bus. With support for a DRAM graph store with SRAM-based caching on the FPGA, the system provides a speedup of roughly 8.9x over the CPU-based implementation.

BAKER, ZACHARY K. [Los Alamos National Laboratory; GOKHALE, MAYA B. [Los Alamos National Laboratory

2007-01-08

30

The Routing Continuum from Shortest-path to All-path: A Unifying Theory  

E-print Network

The Routing Continuum from Shortest-path to All-path: A Unifying Theory Yanhua Li, Zhi-Li Zhang of data and sensor networks, routing strategies such as shortest-path, multi-path and potential-based ("all-path") routing have been developed. Based on the connection between routing and flow optimization

Boley, Daniel

31

The on-line shortest path problem under partial monitoring  

Microsoft Academic Search

The on-line shortest path problem is considered under various models of partial monitoring. Given a weighted directed acyclic graph whose edge weights can change in an arbitrary (adversarial) way, a decision maker has to choose in each round of a game a path between two distinguished vertices such that the loss of the chosen path (defined as the sum of

Andras Gyorgy; Tamas Linder; Gabor Lugosi; Gyorgy Ottucsak

2007-01-01

32

Distributional properties of stochastic shortest paths for smuggled nuclear material  

SciTech Connect

The shortest path problem on a network with fixed weights is a well studied problem with applications to many diverse areas such as transportation and telecommunications. We are particularly interested in the scenario where a nuclear material smuggler tries to succesfully reach herlhis target by identifying the most likely path to the target. The identification of the path relies on reliabilities (weights) associated with each link and node in a multi-modal transportation network. In order to account for the adversary's uncertainty and to perform sensitivity analysis we introduce random reliabilities. We perform some controlled experiments on the grid and present the distributional properties of the resulting stochastic shortest paths.

Cuellar, Leticia [Los Alamos National Laboratory; Pan, Feng [Los Alamos National Laboratory; Roach, Fred [Los Alamos National Laboratory; Saeger, Kevin J [Los Alamos National Laboratory

2011-01-05

33

Fast Shortest-path Distance Queries on Road Networks by Pruned Highway Labeling  

E-print Network

Fast Shortest-path Distance Queries on Road Networks by Pruned Highway Labeling Takuya Akiba Yoichi- ferred to as highway-based labelings and a preprocessing algorithm for it named pruned highway labeling to as the highway-based labeling framework and a preprocessing algorithm for the framework named pruned highway

Imai, Hiroshi

34

Texture recognition by the shortest path on 3D discrete gray-level surface  

NASA Astrophysics Data System (ADS)

In this paper, we apply geodesic paths (the shortest path which is an important object in the task of 3D shape analysis) to the description of natural textures. We first introduce an approach called propagation algorithm to estimate the shortest paths on discrete surfaces and then derive a set of texture features (LR, PLR, SDR, DIF and 1c) from them. The results of the experiments indicate that these features can reflect texture surface patterns in various aspects and are suitable for texture description.

Liao, Mengyang; Li, Xinliang; Qin, Jiamei; Wang, Sixian

1995-05-01

35

Incremental Network Design with Shortest Paths  

E-print Network

We introduce a class of incremental network design problems focused on inves- tigating the ...... The Annals of Regional Science, 42:621–642,. 2008. ... ceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, SODA '94,.

2013-01-11

36

Shortest distance problems in graphs using history-dependent transition costs with application to kinodynamic path planning  

Microsoft Academic Search

A new algorithm is presented to compute the shortest path on a graph when the node transition costs depend on the prior history of the path to the current node. The algorithm is applied to solve path planning problems with curvature constraints.

Raghvendra V. Cowlagi; Panagiotis Tsiotras

2009-01-01

37

VAN: Vehicle-assisted shortest-time path navigation  

Microsoft Academic Search

Traffic congestion is a very serious problem in large cities. With the number of vehicles increasing rapidly, especially in cities whose economy is booming, the situation is getting even worse. In this paper, by leveraging the techniques of Vehicular Ad hoc Networks (VANETs) we present a dynamic navigation protocol called VAN for individual vehicles to find the shortest-time paths toward

Wenping Chen; Sencun Zhu; Deying Li

2010-01-01

38

The Greedy Algorithm for Shortest Superstrings Haim Kaplan Nira Shafrir  

E-print Network

The Greedy Algorithm for Shortest Superstrings Haim Kaplan #3; Nira Shafrir #3; August 26, 2004 molecule. There is a natural greedy algorithm for the shortest superstring problem, which we refer to as GREEDY. The GREEDY algorithm maintains a set of strings, initialized to be equal to S. At each iteration

Kaplan, Haim

39

Min-Link Shortest Path Maps and Frchet Distance Atlas F. Cook IV  

E-print Network

, so we use our shortest path map structure to represent a free space cell. 1. INTRODUCTIONMin-Link Shortest Path Maps and Fréchet Distance Atlas F. Cook IV Carola Wenk Abstract We present shortest path maps that support min-link queries from any source point on a line segment to destination

Texas at San Antonio, University of

40

A bio-inspired method for the constrained shortest path problem.  

PubMed

The constrained shortest path (CSP) problem has been widely used in transportation optimization, crew scheduling, network routing and so on. It is an open issue since it is a NP-hard problem. In this paper, we propose an innovative method which is based on the internal mechanism of the adaptive amoeba algorithm. The proposed method is divided into two parts. In the first part, we employ the original amoeba algorithm to solve the shortest path problem in directed networks. In the second part, we combine the Physarum algorithm with a bio-inspired rule to deal with the CSP. Finally, by comparing the results with other method using an examples in DCLC problem, we demonstrate the accuracy of the proposed method. PMID:24959603

Wang, Hongping; Lu, Xi; Zhang, Xiaoge; Wang, Qing; Deng, Yong

2014-01-01

41

A Bio-Inspired Method for the Constrained Shortest Path Problem  

PubMed Central

The constrained shortest path (CSP) problem has been widely used in transportation optimization, crew scheduling, network routing and so on. It is an open issue since it is a NP-hard problem. In this paper, we propose an innovative method which is based on the internal mechanism of the adaptive amoeba algorithm. The proposed method is divided into two parts. In the first part, we employ the original amoeba algorithm to solve the shortest path problem in directed networks. In the second part, we combine the Physarum algorithm with a bio-inspired rule to deal with the CSP. Finally, by comparing the results with other method using an examples in DCLC problem, we demonstrate the accuracy of the proposed method. PMID:24959603

Wang, Hongping; Lu, Xi; Wang, Qing

2014-01-01

42

The d-edge shortest-path problem for a Monge graph  

SciTech Connect

A complete edge-weighted directed graph on vertices 1,2,...,n that assigns cost c(i,j) to the edge (i,j) is called Monge if its edge costs form a Monge array, i.e., for all i < k and j < l, c[i, j]+c[k,l]{le} < c[i,l]+c[k,j]. One reason Monge graphs are interesting is that shortest paths can be computed quite quickly in such graphs. In particular, Wilber showed that the shortest path from vertex 1 to vertex n of a Monge graph can be computed in O(n) time, and Aggarwal, Klawe, Moran, Shor, and Wilber showed that the shortest d-edge 1-to-n path (i.e., the shortest path among all 1-to-n paths with exactly d edges) can be computed in O(dn) time. This paper`s contribution is a new algorithm for the latter problem. Assuming 0 {le} c[i,j] {le} U and c[i,j + 1] + c[i + 1,j] {minus} c[i,j] {minus} c[i + 1, j + 1] {ge} L > 0 for all i and j, our algorithm runs in O(n(1 + 1g(U/L))) time. Thus, when d {much_gt} 1 + 1g(U/L), our algorithm represents a significant improvement over Aggarwal et al.`s O(dn)-time algorithm. We also present several applications of our algorithm; they include length-limited Huffman coding, finding the maximum-perimeter d-gon inscribed in a given convex n-gon, and a digital-signal-compression problem.

Bein, W.W. [New Mexico Univ., Albuquerque, NM (United States). Dept. of Computer Science; Larmore, L.L. [California Univ., Riverside, CA (United States). Dept. of Computer Science; Park, J.K. [Sandia National Labs.,Albuquerque, NM (United States)

1992-07-14

43

A Graph Search Heuristic for Shortest Distance Paths  

SciTech Connect

This paper presents a heuristic for guiding A* search for finding the shortest distance path between two vertices in a connected, undirected, and explicitly stored graph. The heuristic requires a small amount of data to be stored at each vertex. The heuristic has application to quickly detecting relationships between two vertices in a large information or knowledge network. We compare the performance of this heuristic with breadth-first search on graphs with various topological properties. The results show that one or more orders of magnitude improvement in the number of vertices expanded is possible for large graphs, including Poisson random graphs.

Chow, E

2005-03-24

44

Shortest-Path Network Analysis Is a Useful Approach toward Identifying Genetic Determinants of Longevity  

PubMed Central

Background Identification of genes that modulate longevity is a major focus of aging-related research and an area of intense public interest. In addition to facilitating an improved understanding of the basic mechanisms of aging, such genes represent potential targets for therapeutic intervention in multiple age-associated diseases, including cancer, heart disease, diabetes, and neurodegenerative disorders. To date, however, targeted efforts at identifying longevity-associated genes have been limited by a lack of predictive power, and useful algorithms for candidate gene-identification have also been lacking. Methodology/Principal Findings We have utilized a shortest-path network analysis to identify novel genes that modulate longevity in Saccharomyces cerevisiae. Based on a set of previously reported genes associated with increased life span, we applied a shortest-path network algorithm to a pre-existing protein–protein interaction dataset in order to construct a shortest-path longevity network. To validate this network, the replicative aging potential of 88 single-gene deletion strains corresponding to predicted components of the shortest-path longevity network was determined. Here we report that the single-gene deletion strains identified by our shortest-path longevity analysis are significantly enriched for mutations conferring either increased or decreased replicative life span, relative to a randomly selected set of 564 single-gene deletion strains or to the current data set available for the entire haploid deletion collection. Further, we report the identification of previously unknown longevity genes, several of which function in a conserved longevity pathway believed to mediate life span extension in response to dietary restriction. Conclusions/Significance This work demonstrates that shortest-path network analysis is a useful approach toward identifying genetic determinants of longevity and represents the first application of network analysis of aging to be extensively validated in a biological system. The novel longevity genes identified in this study are likely to yield further insight into the molecular mechanisms of aging and age-associated disease. PMID:19030232

Managbanag, J. R.; Witten, Tarynn M.; Bonchev, Danail; Fox, Lindsay A.; Tsuchiya, Mitsuhiro; Kennedy, Brian K.; Kaeberlein, Matt

2008-01-01

45

Corridor location: the multi-gateway shortest path model  

NASA Astrophysics Data System (ADS)

The problem of corridor location can be found in a number of fields including power transmission, highways, and pipelines. It involves the placement of a corridor or rights-of-way that traverses a landscape starting at an origin and ending at a destination. Since most systems are subject to environmental review, it is important to generate competitive, but different alternatives. This paper addresses the problem of generating efficient, spatially different alternatives to the corridor location problem. We discuss the weaknesses in current models and propose a new approach which is designed to overcome many of these problems. We present an application of this model to a real landscape and compare the results to past work. Overall, the new model called the multi-gateway shortest path problem can generate a wide variety of efficient alignments, which eclipse what could be generated by past work.

Scaparra, Maria P.; Church, Richard L.; Medrano, F. Antonio

2014-07-01

46

Damage detection via shortest-path network sampling  

NASA Astrophysics Data System (ADS)

Large networked systems are constantly exposed to local damages and failures that can alter their functionality. The knowledge of the structure of these systems is, however, often derived through sampling strategies whose effectiveness at damage detection has not been thoroughly investigated so far. Here, we study the performance of shortest-path sampling for damage detection in large-scale networks. We define appropriate metrics to characterize the sampling process before and after the damage, providing statistical estimates for the status of nodes (damaged, not damaged). The proposed methodology is flexible and allows tuning the trade-off between the accuracy of the damage detection and the number of probes used to sample the network. We test and measure the efficiency of our approach considering both synthetic and real networks data. Remarkably, in all of the systems studied, the number of correctly identified damaged nodes exceeds the number of false positives, allowing us to uncover the damage precisely.

Ciulla, Fabio; Perra, Nicola; Baronchelli, Andrea; Vespignani, Alessandro

2014-05-01

47

Efficient shortest-path-tree computation in network routing based on pulse-coupled neural networks.  

PubMed

Shortest path tree (SPT) computation is a critical issue for routers using link-state routing protocols, such as the most commonly used open shortest path first and intermediate system to intermediate system. Each router needs to recompute a new SPT rooted from itself whenever a change happens in the link state. Most commercial routers do this computation by deleting the current SPT and building a new one using static algorithms such as the Dijkstra algorithm at the beginning. Such recomputation of an entire SPT is inefficient, which may consume a considerable amount of CPU time and result in a time delay in the network. Some dynamic updating methods using the information in the updated SPT have been proposed in recent years. However, there are still many limitations in those dynamic algorithms. In this paper, a new modified model of pulse-coupled neural networks (M-PCNNs) is proposed for the SPT computation. It is rigorously proved that the proposed model is capable of solving some optimization problems, such as the SPT. A static algorithm is proposed based on the M-PCNNs to compute the SPT efficiently for large-scale problems. In addition, a dynamic algorithm that makes use of the structure of the previously computed SPT is proposed, which significantly improves the efficiency of the algorithm. Simulation results demonstrate the effective and efficient performance of the proposed approach. PMID:23144039

Qu, Hong; Yi, Zhang; Yang, Simon X

2013-06-01

48

The Weight of the Shortest Path Tree Remco van der Hofstad  

E-print Network

The Weight of the Shortest Path Tree Remco van der Hofstad Gerard Hooghiemstra Piet Van Mieghem December 22, 2005 Abstract The minimal weight of the shortest path tree in a complete graph with independent and expo- nential (mean 1) random link weights, is shown to converge to a Gaussian distribution

Van Mieghem, Piet

49

Weight of a link in a shortest path tree and the Dedekind Eta Piet Van Mieghem  

E-print Network

Weight of a link in a shortest path tree and the Dedekind Eta function Piet Van Mieghem Delft University of Technology September 11, 2009 Abstract The weight of a randomly chosen link in the shortest path tree on the complete graph with exponential i.i.d. link weights is studied. The corresponding

Van Mieghem, Piet

50

HAMILTONIAN PATHS ALGORITHMS FOR DISK SCHEDULING  

Microsoft Academic Search

The problem of optimally scheduling the read\\/write requests in a disk storage system is considered. A new class of algorithms for the disk scheduling problem is presented, and the relations between this problem and the shortest hamiltonian path problem on asymmetric graphs are investigated. The problem of deriving realistic upper bounds for the disk utilization factor, one of the main

Giorgio Gallo; Federico Malucelli; Martina Marrè

51

A minimum resource neural network framework for solving multiconstraint shortest path problems.  

PubMed

Characterized by using minimum hard (structural) and soft (computational) resources, a novel parameter-free minimal resource neural network (MRNN) framework is proposed for solving a wide range of single-source shortest path (SP) problems for various graph types. The problems are the k-shortest time path problems with any combination of three constraints: time, hop, and label constraints, and the graphs can be directed, undirected, or bidirected with symmetric and/or asymmetric traversal time, which can be real and time dependent. Isomorphic to the graph where the SP is to be sought, the network is activated by generating autowave at source neuron and the autowave travels automatically along the paths with the speed of a hop in an iteration. Properties of the network are studied, algorithms are presented, and computation complexity is analyzed. The framework guarantees globally optimal solutions of a series of problems during the iteration process of the network, which provides insight into why even the SP is still too long to be satisfied. The network facilitates very large scale integrated circuit implementation and adapt to very large scale problems due to its massively parallel processing and minimum resource utilization. When implemented in a sequentially processing computer, experiments on synthetic graphs, road maps of cities of the USA, and vehicle routing with time windows indicate that the MRNN is especially efficient for large scale sparse graphs and even dense graphs with some constraints, e.g., the CPU time taken and the iteration number used for the road maps of cities of the USA is even less than  ? 2% and 0.5% that of the Dijkstra's algorithm. PMID:25050952

Zhang, Junying; Zhao, Xiaoxue; He, Xiaotao

2014-08-01

52

Snell's law and light traveling along the shortest path  

Microsoft Academic Search

the problem to be analyzed follows: Given a starting point s, an ending point t and a set of n Weighted Faces (or regions) in a 2-dimensional space, find the best path from s to t, where the length of the path is defined as the weighted sum of the Euclidean length of the sub paths inside each region. Let

Carlos Lara

2006-01-01

53

DT-MRI Fiber Tracking: A Shortest Paths Approach  

Microsoft Academic Search

We derive a new fiber tracking algorithm for DT- MRI that parts with the locally 'greedy' paradigm intrinsic to conventional tracking algorithms. We demonstrate the ability to precisely reconstruct a diverse range of fiber trajectori es in authentic and computer-generated DT-MRI data, for which well- known conventional tracking algorithms are shown to fail. Our approach is to pose fiber tracking

Andrew Zalesky

2008-01-01

54

Performance of multihop wireless networks: shortest path is not enough  

Microsoft Academic Search

Existing wireless ad hoc routing protocols typically find routes with the minimum hop-count. This paper presents experimental evidence from two wireless test-beds which shows that there are usually multiple minimum hop-count paths, many of which have poor throughput. As a result, minimum-hop-count routing often chooses routes that have significantly less capacity than the best paths that exist in the network.

Douglas S. J. De Couto; Daniel Aguayo; Benjamin A. Chambers; Robert Morris

2003-01-01

55

Integer programming formulations for the elementary shortest path ...  

E-print Network

cost path between two nodes s and t such that each node of G is visited ..... In order to compare MCF and GCS, we need to project out also the q-variables .... generated by building a connected component including all the nodes, and then.

2014-09-26

56

Fast and accurate global multiphase arrival tracking: the irregular shortest-path method in a 3-D spherical earth model  

NASA Astrophysics Data System (ADS)

The traditional grid/cell-based wavefront expansion algorithms, such as the shortest path algorithm, can only find the first arrivals or multiply reflected (or mode converted) waves transmitted from subsurface interfaces, but cannot calculate the other later reflections/conversions having a minimax time path. In order to overcome the above limitations, we introduce the concept of a stationary minimax time path of Fermat's Principle into the multistage irregular shortest path method. Here we extend it from Cartesian coordinates for a flat earth model to global ray tracing of multiple phases in a 3-D complex spherical earth model. The ray tracing results for 49 different kinds of crustal, mantle and core phases show that the maximum absolute traveltime error is less than 0.12 s and the average absolute traveltime error is within 0.09 s when compared with the AK135 theoretical traveltime tables for a 1-D reference model. Numerical tests in terms of computational accuracy and CPU time consumption indicate that the new scheme is an accurate, efficient and a practical way to perform 3-D multiphase arrival tracking in regional or global traveltime tomography.

Huang, Guo-Jiao; Bai, Chao-Ying; Greenhalgh, Stewart

2013-09-01

57

Spatial Interpolation of Fine Particulate Matter Concentrations Using the Shortest Wind-Field Path Distance  

PubMed Central

Effective assessments of air-pollution exposure depend on the ability to accurately predict pollutant concentrations at unmonitored locations, which can be achieved through spatial interpolation. However, most interpolation approaches currently in use are based on the Euclidean distance, which cannot account for the complex nonlinear features displayed by air-pollution distributions in the wind-field. In this study, an interpolation method based on the shortest path distance is developed to characterize the impact of complex urban wind-field on the distribution of the particulate matter concentration. In this method, the wind-field is incorporated by first interpolating the observed wind-field from a meteorological-station network, then using this continuous wind-field to construct a cost surface based on Gaussian dispersion model and calculating the shortest wind-field path distances between locations, and finally replacing the Euclidean distances typically used in Inverse Distance Weighting (IDW) with the shortest wind-field path distances. This proposed methodology is used to generate daily and hourly estimation surfaces for the particulate matter concentration in the urban area of Beijing in May 2013. This study demonstrates that wind-fields can be incorporated into an interpolation framework using the shortest wind-field path distance, which leads to a remarkable improvement in both the prediction accuracy and the visual reproduction of the wind-flow effect, both of which are of great importance for the assessment of the effects of pollutants on human health. PMID:24798197

Li, Longxiang; Gong, Jianhua; Zhou, Jieping

2014-01-01

58

Design and Analysis of Improved Shortest Path Tree Update for Network Routing  

Microsoft Academic Search

The quick construction of the Shortest Path Tree (SPT) is essential to achieve fast routing speed for an interior net- work using link state protocols, such as OSPF and IS-IS. Whenever the network topology changes, the old SPT must be updated. In a network with a large number of nodes, the technology with the whole SPT re-computation by tra- ditional

Bin Xiao; Qingfeng Zhuge; Zili Shao; Edwin Hsing-mean Sha

2003-01-01

59

k-Link Shortest Paths in Weighted Subdivisions Ovidiu Daescu1  

E-print Network

k-Link Shortest Paths in Weighted Subdivisions Ovidiu Daescu1 , Joseph S.B. Mitchell2 , Simeon nonnegative weight. The weighted length of a line segment, ab, joining two points a and b within the same by NSF grant CCF-0430366. J. Mitchell is partially supported by the U.S.-Israel Binational Science

Mitchell, Joseph S.B.

60

Arrival Time Dependent Shortest Path by On-Road Routing in Mobile Ad-Hoc Network  

Microsoft Academic Search

\\u000a Arrival time dependent shortest path finding is an important function in the field of traffic information systems or telematics.\\u000a However large number of mobile objects on the road network results in a scalability problem for frequently updating and handling\\u000a their real-time location. In this paper, we propose a query processing method in MANET(Mobile Ad-hoc Network) environment\\u000a to find an arrival

Kyoung-sook Kim; So-young Hwang; Ki-joune Li

2004-01-01

61

Energy-efficient broadcasting in ad-hoc networks: combining MSTs with shortest-path trees  

Microsoft Academic Search

We investigate the problem of constructing a multicast tree in ad-hoc networks. In particular, we address the issue of the power consumption, that is, the overall energy that the stations must spend to implement such a tree. We focus on two extreme cases of multicast: broadcast (one-to-all) and unicast (one-to-one). Minimum Spanning Trees (MSTs) and Shortest-Path Trees (SPTs) yield optimal

Paolo Penna; Carmine Ventre

2004-01-01

62

Shortest-path queries for complex networks: exploiting low tree-width outside the core  

Microsoft Academic Search

We present new and improved methods for efficient shortest-path query processing. Our methods are tailored to work for two specific classes of graphs: graphs with small tree-width and complex networks. Seemingly unrelated at first glance, these two classes of graphs have some commonalities: complex networks are known to have a core--fringe structure with a dense core and a tree-like fringe.

Takuya Akiba; Christian Sommer; Ken-ichi Kawarabayashi

2012-01-01

63

Approximation of greedy algorithms for Max-ATSP, Maximal Compression, and Shortest Cyclic Cover of Strings  

E-print Network

Approximation of greedy algorithms for Max-ATSP, Maximal Compression, and Shortest Cyclic Cover the approximation of associated greedy algorithms for these four problems, and show they reach a ratio of 1. For these problems, greedy algorithms are easier to implement and often faster than existing approximation algorithms

Paris-Sud XI, Université de

64

A Computational Study Identifies HIV Progression-Related Genes Using mRMR and Shortest Path Tracing  

PubMed Central

Since statistical relationships between HIV load and CD4+ T cell loss have been demonstrated to be weak, searching for host factors contributing to the pathogenesis of HIV infection becomes a key point for both understanding the disease pathology and developing treatments. We applied Maximum Relevance Minimum Redundancy (mRMR) algorithm to a set of microarray data generated from the CD4+ T cells of viremic non-progressors (VNPs) and rapid progressors (RPs) to identify host factors associated with the different responses to HIV infection. Using mRMR algorithm, 147 gene had been identified. Furthermore, we constructed a weighted molecular interaction network with the existing protein-protein interaction data from STRING database and identified 1331 genes on the shortest-paths among the genes identified with mRMR. Functional analysis shows that the functions relating to apoptosis play important roles during the pathogenesis of HIV infection. These results bring new insights of understanding HIV progression. PMID:24244287

Liu, Lei

2013-01-01

65

A Continuous-State Version of Discrete Randomized Shortest-Paths, with Application to Path Planning  

E-print Network

are of capital importance in a variety of problems, from robot path planning, to maze solving. Path planning [16] is a well-known problem in the robotics community, described by [26] as "checking the consequences. This distribution, though peaked around optimal paths, let the random walker take a random transition according

Del Moral , Pierre

66

Effective usage of shortest paths promotes transportation efficiency on scale-free networks  

NASA Astrophysics Data System (ADS)

With rapid economic and social development, the problem of traffic congestion is getting more and more serious. Accordingly, network traffic models have attracted extensive attention. In this paper, we introduce a shortest-remaining-path-first queuing strategy into a network traffic model on Barabási-Albert scale-free networks under efficient routing protocol, where one packet’s delivery priority is related to its current distance to the destination. Compared with the traditional first-in-first-out queuing strategy, although the network capacity has no evident changes, some other indexes reflecting transportation efficiency are significantly improved in the congestion state. Extensive simulation results and discussions are carried out to explain the phenomena. Our work may be helpful for the designing of optimal networked-traffic systems.

Du, Wen-Bo; Wu, Zhi-Xi; Cai, Kai-Quan

2013-09-01

67

SHORTEST PATHS FOR THE REEDS-SHEPP CAR: A WORKED OUT EXAMPLE OF THE USE OF GEOMETRIC TECHNIQUES IN NONLINEAR OPTIMAL CONTROL. 1  

Microsoft Academic Search

We illustrate the use of the techniques of modern geometric optimal control theory by studying the shortest paths for a model of a car that can move forwards and backwards. This problem was discussed in recent work by Reeds and Shepp who showed, by special methods, (a) that shortest path motion could always be achieved by means of trajectories of

J. Sussmann; Guoqing Tang

1991-01-01

68

Shortest-path constraints for 3D multiobject semiautomatic segmentation via clustering and Graph Cut.  

PubMed

We derive shortest-path constraints from graph models of structure adjacency relations and introduce them in a joint centroidal Voronoi image clustering and Graph Cut multiobject semiautomatic segmentation framework. The vicinity prior model thus defined is a piecewise-constant model incurring multiple levels of penalization capturing the spatial configuration of structures in multiobject segmentation. Qualitative and quantitative analyses and comparison with a Potts prior-based approach and our previous contribution on synthetic, simulated, and real medical images show that the vicinity prior allows for the correct segmentation of distinct structures having identical intensity profiles and improves the precision of segmentation boundary placement while being fairly robust to clustering resolution. The clustering approach we take to simplify images prior to segmentation strikes a good balance between boundary adaptivity and cluster compactness criteria furthermore allowing to control the trade-off. Compared with a direct application of segmentation on voxels, the clustering step improves the overall runtime and memory footprint of the segmentation process up to an order of magnitude without compromising the quality of the result. PMID:23807445

Kéchichian, Razmig; Valette, Sébastien; Desvignes, Michel; Prost, Rémy

2013-11-01

69

Scaling of average weighted shortest path and average receiving time on weighted expanded Koch networks  

NASA Astrophysics Data System (ADS)

Deterministic network models have been attractive media for discussing dynamical processes' dependence on network structural features. On the other hand, the heterogeneity of weights affect dynamical processes taking place on networks. In this paper, we present a family of weighted expanded Koch networks based on Koch networks. They originate from a r-polygon, and each node of current generation produces m r-polygons including the node and whose weighted edges are scaled by factor w in subsequent evolutionary step. We derive closed-form expressions for average weighted shortest path length (AWSP). In large network, AWSP stays bounded with network order growing (0 < w < 1). Then, we focus on a special random walks and trapping issue on the networks. In more detail, we calculate exactly the average receiving time (ART). ART exhibits a sub-linear dependence on network order (0 < w < 1), which implies that nontrivial weighted expanded Koch networks are more efficient than un-weighted expanded Koch networks in receiving information. Besides, efficiency of receiving information at hub nodes is also dependent on parameters m and r. These findings may pave the way for controlling information transportation on general weighted networks.

Wu, Zikai; Hou, Baoyu; Zhang, Hongjuan; Jin, Feng

2014-04-01

70

Challenging of path planning algorithms for autonomous robot in known environment  

NASA Astrophysics Data System (ADS)

Most of the mobile robot path planning is estimated to reach its predetermined aim through the shortest path and avoiding the obstacles. This paper is a survey on path planning algorithms of various current research and existing system of Unmanned Ground Vehicles (UGV) where their challenging issues to be intelligent autonomous robot. The focuses are some short reviews on individual papers for UGV in the known environment. Methods and algorithms in path planning for the autonomous robot had been discussed. From the reviews, we obtained that the algorithms proposed are appropriate for some cases such as single or multiple obstacles, static or movement obstacle and optimal shortest path. This paper also describes some pros and cons for every reviewed paper toward algorithms improvement for further work.

Farah, R. N.; Irwan, N.; Zuraida, Raja Lailatul; Shaharum, Umairah; Hanafi@Omar, Hafiz Mohd

2014-06-01

71

Path and Trajectory Diversity Theory and Algorithms  

E-print Network

Path and Trajectory Diversity Theory and Algorithms Ross A. Knepper International Conference and Kuffner, SIGGRAPH, 2006] Introduction ConclusionResultsAlgorithmsApproach Theory #12;R.A. Knepper PathResultsAlgorithmsApproach Theory #12;R.A. Knepper Path and Trajectory Diversity 4 Diversity Spectrum Easy to increase diversity

Branicky, Michael S.

72

A Multilevel Probabilistic Beam Search Algorithm for the Shortest Common Supersequence Problem  

PubMed Central

The shortest common supersequence problem is a classical problem with many applications in different fields such as planning, Artificial Intelligence and especially in Bioinformatics. Due to its NP-hardness, we can not expect to efficiently solve this problem using conventional exact techniques. This paper presents a heuristic to tackle this problem based on the use at different levels of a probabilistic variant of a classical heuristic known as Beam Search. The proposed algorithm is empirically analysed and compared to current approaches in the literature. Experiments show that it provides better quality solutions in a reasonable time for medium and large instances of the problem. For very large instances, our heuristic also provides better solutions, but required execution times may increase considerably. PMID:23300667

Gallardo, Jose E.

2012-01-01

73

Identification of Colorectal Cancer Related Genes with mRMR and Shortest Path in Protein-Protein Interaction Network  

PubMed Central

One of the most important and challenging problems in biomedicine and genomics is how to identify the disease genes. In this study, we developed a computational method to identify colorectal cancer-related genes based on (i) the gene expression profiles, and (ii) the shortest path analysis of functional protein association networks. The former has been used to select differentially expressed genes as disease genes for quite a long time, while the latter has been widely used to study the mechanism of diseases. With the existing protein-protein interaction data from STRING (Search Tool for the Retrieval of Interacting Genes), a weighted functional protein association network was constructed. By means of the mRMR (Maximum Relevance Minimum Redundancy) approach, six genes were identified that can distinguish the colorectal tumors and normal adjacent colonic tissues from their gene expression profiles. Meanwhile, according to the shortest path approach, we further found an additional 35 genes, of which some have been reported to be relevant to colorectal cancer and some are very likely to be relevant to it. Interestingly, the genes we identified from both the gene expression profiles and the functional protein association network have more cancer genes than the genes identified from the gene expression profiles alone. Besides, these genes also had greater functional similarity with the reported colorectal cancer genes than the genes identified from the gene expression profiles alone. All these indicate that our method as presented in this paper is quite promising. The method may become a useful tool, or at least plays a complementary role to the existing method, for identifying colorectal cancer genes. It has not escaped our notice that the method can be applied to identify the genes of other diseases as well. PMID:22496748

Liu, Lei; Cai, Yu-Dong; Chou, Kuo-Chen

2012-01-01

74

Gauss Meets Canadian Traveler: Shortest-Path Problems with Correlated Natural Dynamics  

E-print Network

experiments in the aircraft navigation sce- nario with real wind data demonstrate that our framework can Planning; Canadian Traveler Problem; Gaussian Process; Aircraft Routing ABSTRACT In a variety of real world problems from robot navigation to logistics, agents face the challenge of path optimization on a graph

Horvitz, Eric

75

Finding the K shortest hyperpaths  

Microsoft Academic Search

The K shortest paths problem has been extensively studied for many years. Ecien t methods have been devised, and many practical applications are known. Shortest hyperpath models have been proposed for several problems in dieren t areas, for example in relation with routing in dynamic networks. However, the K shortest hyperpaths problem has not yet been investigated. In this paper

Lars Relund Nielsen; Kim Allan Andersen; Daniele Pretolani

2005-01-01

76

A Path Algorithm for Constrained Estimation  

PubMed Central

Many least-square problems involve affine equality and inequality constraints. Although there are a variety of methods for solving such problems, most statisticians find constrained estimation challenging. The current article proposes a new path-following algorithm for quadratic programming that replaces hard constraints by what are called exact penalties. Similar penalties arise in l1 regularization in model selection. In the regularization setting, penalties encapsulate prior knowledge, and penalized parameter estimates represent a trade-off between the observed data and the prior knowledge. Classical penalty methods of optimization, such as the quadratic penalty method, solve a sequence of unconstrained problems that put greater and greater stress on meeting the constraints. In the limit as the penalty constant tends to ?, one recovers the constrained solution. In the exact penalty method, squared penalties!are replaced by absolute value penalties, and the solution is recovered for a finite value of the penalty constant. The exact path-following method starts at the unconstrained solution and follows the solution path as the penalty constant increases. In the process, the solution path hits, slides along, and exits from the various constraints. Path following in Lasso penalized regression, in contrast, starts with a large value of the penalty constant and works its way downward. In both settings, inspection of the entire solution path is revealing. Just as with the Lasso and generalized Lasso, it is possible to plot the effective degrees of freedom along the solution path. For a strictly convex quadratic program, the exact penalty algorithm can be framed entirely in terms of the sweep operator of regression analysis. A few well-chosen examples illustrate the mechanics and potential of path following. This article has supplementary materials available online. PMID:24039382

Zhou, Hua; Lange, Kenneth

2013-01-01

77

Robot path planning using a genetic algorithm  

NASA Technical Reports Server (NTRS)

Robot path planning can refer either to a mobile vehicle such as a Mars Rover, or to an end effector on an arm moving through a cluttered workspace. In both instances there may exist many solutions, some of which are better than others, either in terms of distance traversed, energy expended, or joint angle or reach capabilities. A path planning program has been developed based upon a genetic algorithm. This program assumes global knowledge of the terrain or workspace, and provides a family of good paths between the initial and final points. Initially, a set of valid random paths are constructed. Successive generations of valid paths are obtained using one of several possible reproduction strategies similar to those found in biological communities. A fitness function is defined to describe the goodness of the path, in this case including length, slope, and obstacle avoidance considerations. It was found that with some reproduction strategies, the average value of the fitness function improved for successive generations, and that by saving the best paths of each generation, one could quite rapidly obtain a collection of good candidate solutions.

Cleghorn, Timothy F.; Baffes, Paul T.; Wang, Liu

1988-01-01

78

Adaptive path planning: Algorithm and analysis  

SciTech Connect

To address the need for a fast path planner, we present a learning algorithm that improves path planning by using past experience to enhance future performance. The algorithm relies on an existing path planner to provide solutions difficult tasks. From these solutions, an evolving sparse work of useful robot configurations is learned to support faster planning. More generally, the algorithm provides a framework in which a slow but effective planner may be improved both cost-wise and capability-wise by a faster but less effective planner coupled with experience. We analyze algorithm by formalizing the concept of improvability and deriving conditions under which a planner can be improved within the framework. The analysis is based on two stochastic models, one pessimistic (on task complexity), the other randomized (on experience utility). Using these models, we derive quantitative bounds to predict the learning behavior. We use these estimation tools to characterize the situations in which the algorithm is useful and to provide bounds on the training time. In particular, we show how to predict the maximum achievable speedup. Additionally, our analysis techniques are elementary and should be useful for studying other types of probabilistic learning as well.

Chen, Pang C.

1995-03-01

79

Evolutionary development of path planning algorithms  

SciTech Connect

This paper describes the use of evolutionary software techniques for developing both genetic algorithms and genetic programs. Genetic algorithms are evolved to solve a specific problem within a fixed and known environment. While genetic algorithms can evolve to become very optimized for their task, they often are very specialized and perform poorly if the environment changes. Genetic programs are evolved through simultaneous training in a variety of environments to develop a more general controller behavior that operates in unknown environments. Performance of genetic programs is less optimal than a specially bred algorithm for an individual environment, but the controller performs acceptably under a wider variety of circumstances. The example problem addressed in this paper is evolutionary development of algorithms and programs for path planning in nuclear environments, such as Chernobyl.

Hage, M

1998-09-01

80

A new efficient optimal path planner for mobile robot based on Invasive Weed Optimization algorithm  

NASA Astrophysics Data System (ADS)

Planning of the shortest/optimal route is essential for efficient operation of autonomous mobile robot or vehicle. In this paper Invasive Weed Optimization (IWO), a new meta-heuristic algorithm, has been implemented for solving the path planning problem of mobile robot in partially or totally unknown environments. This meta-heuristic optimization is based on the colonizing property of weeds. First we have framed an objective function that satisfied the conditions of obstacle avoidance and target seeking behavior of robot in partially or completely unknown environments. Depending upon the value of objective function of each weed in colony, the robot avoids obstacles and proceeds towards destination. The optimal trajectory is generated with this navigational algorithm when robot reaches its destination. The effectiveness, feasibility, and robustness of the proposed algorithm has been demonstrated through series of simulation and experimental results. Finally, it has been found that the developed path planning algorithm can be effectively applied to any kinds of complex situation.

Mohanty, Prases K.; Parhi, Dayal R.

2014-08-01

81

An Adaptive Path Planning Algorithm for Cooperating Unmanned Air Vehicles  

SciTech Connect

An adaptive path planning algorithm is presented for cooperating Unmanned Air Vehicles (UAVs) that are used to deploy and operate land-based sensor networks. The algorithm employs a global cost function to generate paths for the UAVs, and adapts the paths to exceptions that might occur. Examples are provided of the paths and adaptation.

Cunningham, C.T.; Roberts, R.S.

2000-09-12

82

Adaptive path planning algorithm for cooperating unmanned air vehicles  

SciTech Connect

An adaptive path planning algorithm is presented for cooperating Unmanned Air Vehicles (UAVs) that are used to deploy and operate land-based sensor networks. The algorithm employs a global cost function to generate paths for the UAVs, and adapts the paths to exceptions that might occur. Examples are provided of the paths and adaptation.

Cunningham, C T; Roberts, R S

2001-02-08

83

Minefield path planning: architecture and algorithms obeying kinematic constraints  

NASA Astrophysics Data System (ADS)

We have been developing path planning techniques to look for paths that balance the utility and risk associated with different routes through a minefield. Such methods will allow a battlegroup commander to evaluate alternative route options while searching for low risk paths. Extending on previous years' efforts, we have implemented a generalized path planning framework to allow rapid evaluation and integration of new path planning algorithms. We have also implemented a version of Rapidly-Explored Random Trees (RRTs) for mine path planning which integrates path risk, path time, and dynamic and kinematic concerns. Several variants of the RRT algorithm and our existing path planning algorithms were quantitatively evaluated using the generalized path planning framework and an algorithm-dynamic evaluation graphical user interface.

McCubbin, Christopher B.; Piatko, Christine D.; Marshall, Steven J.

2004-09-01

84

Parallel implementations of dynamic traffic assignment models and algorithms for dynamic shortest path problems  

E-print Network

This thesis aims at the development of faster Dynamic Traffic Assignment (DTA) models to meet the computational efficiency required by real world applications. A DTA model can be decomposed into several sub-models, of which ...

Jiang, Hai, 1979-

2004-01-01

85

Efficient Algorithms for the Minimum Shortest Path Steiner Arborescence Problem with Applications to VLSI Physical Design  

E-print Network

]. The rectilinear version of the MSPSA problem is called the Minimum Rectilinear Steiner Arborescence (MRSA) problem(N) ) be the induced Hanan grid graph [10] of N . It can be shown that an MSPSA of (G H(N) ; N; r) is an MRSA of N . Exact methods for the MRSA problem can be classified into (1) dynamic programming, (2) integer

Kahng, Andrew B.

86

To appear in the International Journal of Robotics Research, 2004 Expected Shortest Paths for Landmark-Based  

E-print Network

strategies in the presence of significant sensor uncertainty. The navigation environments are modeled is continually updated during subsequent navigation. All motion paths are planned from landmark to landmark can be detected. These estimates are based on the history of all observations made by the robot

Scharstein, Daniel

87

An ordinary differential equation based solution path algorithm.  

PubMed

Efron, Hastie, Johnstone and Tibshirani (2004) proposed Least Angle Regression (LAR), a solution path algorithm for the least squares regression. They pointed out that a slight modification of the LAR gives the LASSO (Tibshirani, 1996) solution path. However it is largely unknown how to extend this solution path algorithm to models beyond the least squares regression. In this work, we propose an extension of the LAR for generalized linear models and the quasi-likelihood model by showing that the corresponding solution path is piecewise given by solutions of ordinary differential equation systems. Our contribution is twofold. First, we provide a theoretical understanding on how the corresponding solution path propagates. Second, we propose an ordinary differential equation based algorithm to obtain the whole solution path. PMID:21532936

Wu, Yichao

2011-01-01

88

PCB drill path optimization by combinatorial cuckoo search algorithm.  

PubMed

Optimization of drill path can lead to significant reduction in machining time which directly improves productivity of manufacturing systems. In a batch production of a large number of items to be drilled such as printed circuit boards (PCB), the travel time of the drilling device is a significant portion of the overall manufacturing process. To increase PCB manufacturing productivity and to reduce production costs, a good option is to minimize the drill path route using an optimization algorithm. This paper reports a combinatorial cuckoo search algorithm for solving drill path optimization problem. The performance of the proposed algorithm is tested and verified with three case studies from the literature. The computational experience conducted in this research indicates that the proposed algorithm is capable of efficiently finding the optimal path for PCB holes drilling process. PMID:24707198

Lim, Wei Chen Esmonde; Kanagaraj, G; Ponnambalam, S G

2014-01-01

89

A Path-Planning Algorithm for Image-Guided Neurosurgery  

E-print Network

. A computer algorithm for determining optimal surgical paths in the brain is presented. The algorithm computes a cost function associated with each point on the outer brain boundary, which is treated as a candidate entry point. The cost function is determined partly based on a segmentation of the patients images into gray and white matter, and partly based on a spatially transformed atlas of the human brain registered to the patient's MR images. The importance of various structures, such as thalamic nuclei, optic nerve and radiations, and individual Brodman's areas, can be defined on the atlas and transferred onto the patient's images through the spatial transformation. The cost of a particular path associated with each critical structure, as well as the total cost of each path are computed and displayed, allowing the surgeon to define a low cost path, to visualize an arbitrary cross-section through the patient's MR images that contains this path, and to examine all the cross-sectiona...

Marc Vaillant; Christos Davatzikos; Russell H. Taylor; R. Nick Bryan

90

The excess mean free path transport condensed history algorithm  

Microsoft Academic Search

A new Condensed History algorithm is introduced to enhance the Monte Carlo simulation of electron transport problems. Unlike established multiple scattering algorithms, this method is a true transport process--it simulates a transport equation that approximates the exact Boltzmann equation. The new equation has a larger mean free path than, and preserves two angular moments of, the Boltzmann equation. Thus, the

E W Larsen; D R Tolar

1999-01-01

91

Regularization Path Algorithms for Detecting Gene Interactions  

E-print Network

/classification settings is to incorporate an L1 regularization constraint. Tibshirani (1996) first introduced Lasso (2004), Tibshirani (1997), or Zhu, Rosset, Hastie & Tibshirani (2003). Efron, Hastie, Johnstone & Tibshirani (2004) proposed the Lars algorithm, a slight modification of which gave a fast way to fit

Hastie, Trevor

92

Global path planning approach based on ant colony optimization algorithm  

Microsoft Academic Search

Ant colony optimization (ACO) algorithm was modified to optimize the global path. In order to simulate the real ant colonies,\\u000a according to the foraging behavior of ant colonies and the characteristic of food, conceptions of neighboring area and smell\\u000a area were presented. The former can ensure the diversity of paths and the latter ensures that each ant can reach the

Zhi-qiang Wen; Zi-xing Cai

2006-01-01

93

Globally-Optimal Greedy Algorithms for Tracking a Variable Number of Hamed Pirsiavash Deva Ramanan Charless C. Fowlkes  

E-print Network

Globally-Optimal Greedy Algorithms for Tracking a Variable Number of Objects Hamed Pirsiavash Deva that sequentially instantiates tracks using shortest path computations on a flow network. Greedy algorithms allow of the tracking prob- lem by using a greedy, successive shortest-path algorithm to reduce the best

Fowlkes, Charless

94

Mobile transporter path planning using a genetic algorithm approach  

NASA Technical Reports Server (NTRS)

The use of an optimization technique known as a genetic algorithm for solving the mobile transporter path planning problem is investigated. The mobile transporter is a traveling robotic vehicle proposed for the Space Station which must be able to reach any point of the structure autonomously. Specific elements of the genetic algorithm are explored in both a theoretical and experimental sense. Recent developments in genetic algorithm theory are shown to be particularly effective in a path planning problem domain, though problem areas can be cited which require more research. However, trajectory planning problems are common in space systems and the genetic algorithm provides an attractive alternative to the classical techniques used to solve these problems.

Baffes, Paul; Wang, Lui

1988-01-01

95

Extracting optimal paths from roadmaps for motion planning  

Microsoft Academic Search

We present methods for extracting optimal paths from motion planning roadmaps. Our system enables any combination of opti- mization criteria, such as collision detection, kinematic\\/dynamic constraints, or minimum clearance, and relaxed definitions of the goal state, to be used when selecting paths from roadmaps. Our algorithm is an augmented version of Dijkstra's shortest path algorithm which allows edge weights to

Jinsuck Kim; Roger A. Pearce; Nancy M. Amato

2003-01-01

96

ONLINE ALGORITHMS FOR PATH SELECTION IN A NONBLOCKING NETWORK #  

E-print Network

ON­LINE ALGORITHMS FOR PATH SELECTION IN A NONBLOCKING NETWORK # SANJEEV ARORA + , F. THOMSON selection in an optimal­size non­ blocking network. In particular, we describe an N­input, N, routing algo­ rithm AMS subject classifications. 68M10, 90B12, 94C10 1. Introduction. 1.1. Definitions

Maggs, Bruce M.

97

Path Planning Algorithms for Autonomous Border Patrol Vehicles  

NASA Astrophysics Data System (ADS)

This thesis presents an online path planning algorithm developed for unmanned vehicles in charge of autonomous border patrol. In this Pursuit-Evasion game, the unmanned vehicle is required to capture multiple trespassers on its own before any of them reach a target safe house where they are safe from capture. The problem formulation is based on Isaacs' Target Guarding problem, but extended to the case of multiple evaders. The proposed path planning method is based on Rapidly-exploring random trees (RRT) and is capable of producing trajectories within several seconds to capture 2 or 3 evaders. Simulations are carried out to demonstrate that the resulting trajectories approach the optimal solution produced by a nonlinear programming-based numerical optimal control solver. Experiments are also conducted on unmanned ground vehicles to show the feasibility of implementing the proposed online path planning algorithm on physical applications.

Lau, George Tin Lam

98

Using a modified invasive weed optimization algorithm for a personalized urban multi-criteria path optimization problem  

NASA Astrophysics Data System (ADS)

The personalized urban multi-criteria quasi-optimum path problem (PUMQPP) is a branch of multi-criteria shortest path problems (MSPPs) and it is classified as a NP-hard problem. To solve the PUMQPP, by considering dependent criteria in route selection, there is a need for approaches that achieve the best compromise of possible solutions/routes. Recently, invasive weed optimization (IWO) algorithm is introduced and used as a novel algorithm to solve many continuous optimization problems. In this study, the modified algorithm of IWO was designed, implemented, evaluated, and compared with the genetic algorithm (GA) to solve the PUMQPP in a directed urban transportation network. In comparison with the GA, the results have shown the significant superiority of the proposed modified IWO algorithm in exploring a discrete search-space of the urban transportation network. In this regard, the proposed modified IWO algorithm has reached better results in fitness function, quality metric and running-time values in comparison with those of the GA.

Pahlavani, Parham; Delavar, Mahmoud R.; Frank, Andrew U.

2012-08-01

99

A bat algorithm with mutation for UCAV path planning.  

PubMed

Path planning for uninhabited combat air vehicle (UCAV) is a complicated high dimension optimization problem, which mainly centralizes on optimizing the flight route considering the different kinds of constrains under complicated battle field environments. Original bat algorithm (BA) is used to solve the UCAV path planning problem. Furthermore, a new bat algorithm with mutation (BAM) is proposed to solve the UCAV path planning problem, and a modification is applied to mutate between bats during the process of the new solutions updating. Then, the UCAV can find the safe path by connecting the chosen nodes of the coordinates while avoiding the threat areas and costing minimum fuel. This new approach can accelerate the global convergence speed while preserving the strong robustness of the basic BA. The realization procedure for original BA and this improved metaheuristic approach BAM is also presented. To prove the performance of this proposed metaheuristic method, BAM is compared with BA and other population-based optimization methods, such as ACO, BBO, DE, ES, GA, PBIL, PSO, and SGA. The experiment shows that the proposed approach is more effective and feasible in UCAV path planning than the other models. PMID:23365518

Wang, Gaige; Guo, Lihong; Duan, Hong; Liu, Luo; Wang, Heqi

2012-01-01

100

Autonomous routing algorithms for networks with wide-spread failures  

E-print Network

We study end-to-end delay performance of different routing algorithms in networks with random failures. Specifically, we compare delay performances of differential backlog (DB) and shortest path (SP) routing algorithms and ...

Modiano, Eytan H.

101

Path Planning Algorithms for the Adaptive Sensor Fleet  

NASA Technical Reports Server (NTRS)

The Adaptive Sensor Fleet (ASF) is a general purpose fleet management and planning system being developed by NASA in coordination with NOAA. The current mission of ASF is to provide the capability for autonomous cooperative survey and sampling of dynamic oceanographic phenomena such as current systems and algae blooms. Each ASF vessel is a software model that represents a real world platform that carries a variety of sensors. The OASIS platform will provide the first physical vessel, outfitted with the systems and payloads necessary to execute the oceanographic observations described in this paper. The ASF architecture is being designed for extensibility to accommodate heterogenous fleet elements, and is not limited to using the OASIS platform to acquire data. This paper describes the path planning algorithms developed for the acquisition phase of a typical ASF task. Given a polygonal target region to be surveyed, the region is subdivided according to the number of vessels in the fleet. The subdivision algorithm seeks a solution in which all subregions have equal area and minimum mean radius. Once the subregions are defined, a dynamic programming method is used to find a minimum-time path for each vessel from its initial position to its assigned region. This path plan includes the effects of water currents as well as avoidance of known obstacles. A fleet-level planning algorithm then shuffles the individual vessel assignments to find the overall solution which puts all vessels in their assigned regions in the minimum time. This shuffle algorithm may be described as a process of elimination on the sorted list of permutations of a cost matrix. All these path planning algorithms are facilitated by discretizing the region of interest onto a hexagonal tiling.

Stoneking, Eric; Hosler, Jeff

2005-01-01

102

Algorithms for hardware allocation in data path synthesis  

Microsoft Academic Search

Novel algorithms for the simultaneous cost\\/resource-constrained allocation of registers, arithmetic units, and interconnect in a data path have been developed. The entire allocation process can be formulated as a two-dimensional placement problem of microinstructions in space and time. This formulation readily lends itself to the use of a variety of heuristics for solving the allocation problem. The authors present simulated-annealing-based

Srinivas Devadas; A. Richard Newton

1989-01-01

103

Algorithm Plans Collision-Free Path for Robotic Manipulator  

NASA Technical Reports Server (NTRS)

An algorithm has been developed to enable a computer aboard a robot to autonomously plan the path of the manipulator arm of the robot to avoid collisions between the arm and any obstacle, which could be another part of the robot or an external object in the vicinity of the robot. In simplified terms, the algorithm generates trial path segments and tests each segment for potential collisions in an iterative process that ends when a sequence of collision-free segments reaches from the starting point to the destination. The main advantage of this algorithm, relative to prior such algorithms, is computational efficiency: the algorithm is designed to make minimal demands upon the limited computational resources available aboard a robot. This path-planning algorithm utilizes a modified version of the collision-detection method described in "Improved Collision-Detection Method for Robotic Manipulator" (NPO-30356), NASA Tech Briefs, Vol. 27, No. 3 (June 2003), page 72. The method involves utilization of mathematical models of the robot constructed prior to operation and similar models of external objects constructed automatically from sensory data acquired during operation. This method incorporates a previously developed method, known in the art as the method of oriented bounding boxes (OBBs), in which an object is represented approximately, for computational purposes, by a box that encloses its outer boundary. Because many parts of a robotic manipulator are cylindrical, the OBB method has been extended in this method to enable the approximate representation of cylindrical parts by use of octagonal or other multiple-OBB assemblies denoted oriented bounding prisms (OBPs). A multiresolution OBB/OBP representation of the robot and its manipulator arm and a multiresolution OBB representation of external objects (including terrain) are constructed and used in a process in which collisions at successively finer resolutions are detected through computational detection of overlaps between the corresponding OBB and OBP models. For computational efficiency, the process is started at the coarsest resolution and stopped as soon as possible, preferably before reaching the finest resolution. At the coarsest resolution, there is a single OBB enclosing all relevant external objects and a single OBB enclosing the entire robot. At the next finer level of resolution, the coarsest-resolution OBB is divided into two OBBs, and so forth. If no collision is detected at the coarsest resolution, then there is no need for further computation to detect collisions. If a collision is detected at the coarsest resolution, then tests for collisions are performed at the next finer level of resolution. This process is continued to successively finer resolutions until either no more collisions are detected or the finest resolution is reached.

Backes, Paul; Diaz-Calderon, Antonio

2007-01-01

104

The shortest-network problem  

SciTech Connect

The Steiner problem asks for the shortest network of line segments that will interconnect a set of given points. The Steiner problem cannot be solved by simply drawing lines between the given points, but it can be solved by adding new ones, called Steiner points, that serve as junctions in a shortest network. To determine the location and number of Steiner points, mathematicians and computer scientists have developed algorithms, or precise procedures. Yet even the best of these algorithms running on the fastest computers cannot provide a solution for a large set of given points because the time it would take to solve such a problem is impractically long. Furthermore, the Steiner problem belongs to a class of problem for which many computer scientists now believe an efficient algorithm may never be found. Approximate solutions to the shortest-network problem are computed routinely for numerous applications, among them designing integrated circuits, determining the evolutionary tree of a group of organisms and minimizing materials used for networks of telephone lines, pipelines and roadways.

Bern, M.W.; Graham, R.L.

1989-01-01

105

Genetic Algorithms with Elitism-based Immigrants for Dynamic Shortest Path Problem in Mobile Ad Hoc Networks  

E-print Network

William Berthomière L'immigration d'ex-URSS et les colonies de Cisjordanie et de Gaza In: Revue : Berthomière William. L'immigration d'ex-URSS et les colonies de Cisjordanie et de Gaza. In: Revue européenne. 201-218 201 NOTE D'ACTUALIT� L'immigration d'ex-URSS et les colonies de Cisjordanie et de Gaza William

Yang, Shengxiang

106

Fast computation of optimal paths using a parallel Dijkstra algorithm with embedded constraints  

Microsoft Academic Search

We have developed a new optimal path algorithm in which the paths are subjected to turning constraints. The restriction which we have incorporated is the next link in the path must not make an angle exceeding 45 ° in magnitude with the preceeding link. This algorithm has a natural implementation as an artificial neural system with either synchronous or asynchronous

Jeffrey L. Solka; James C. Perry; Brian R. Poellinger; George W. Rogers

1995-01-01

107

Path and Trajectory Diversity: Theory and Algorithms Michael S. Branicky Ross A. Knepper James J. Kuffner  

E-print Network

Path and Trajectory Diversity: Theory and Algorithms Michael S. Branicky Ross A. Knepper James J sets of candidate paths or trajectories down to smaller subsets that maintain desirable characteristics in terms of overall reachability and path length. Consider the example of a set of candidate paths

Branicky, Michael S.

108

Feasibility of Onboard Processing of Heuristic Path Planning and Navigation Algorithms within SUAS Autopilot Computational Constraints.  

National Technical Information Service (NTIS)

This research addresses the flight path optimality of Small Unmanned Aerial Systems (SUAS) conducting overwatch missions for convoys or other moving ground targets. Optimal path planning algorithms have been proposed, but are computationally excessive for...

C. J. Neal

2014-01-01

109

An Analysis of Path-Vector Routing Protocol Convergence Algorithms  

Microsoft Academic Search

Today's Internet uses a path vector routing protocol, BGP, for global routing. After a connectivity change, a path vector protocol tends to explore a potentially large number of alternative paths before converging on new stable paths. Several techniques for improving path vector convergence have been proposed, however there has been no comparative analysis to judge the relative merit of each

Dan Pei; UCLA CSD; Beichuan Zhang; Dan Massey; Lixia Zhang

110

Evolutionary algorithm based offline\\/online path planner for UAV navigation  

Microsoft Academic Search

Abstract—An evolutionary algorithm based framework, a combination of modified breeder genetic algorithms incorporating characteristics of classic genetic algorithms, is utilized to design an offline\\/online path planner for unmanned,aerial vehicles (UAVs) autonomous,navigation. The path planner calculates a curved path line with desired characteristics in a three?dimensional (3-D) rough terrain environment, represented using B-Spline curves, with the coordinates of its control points

Ioannis K. Nikolos; Kimon P. Valavanis; Nikos C. Tsourveloudis; Anargyros N. Kostaras

2003-01-01

111

Lecture 16 -GREEDY ALGORITHMS CLRS-Chapter 16  

E-print Network

Lecture 16 -GREEDY ALGORITHMS CLRS-Chapter 16 We have already seen two general problem: the greedy paradigm. A greedy algorithm for an optimization problem always makes the choice that looks best already seen are Dijkstra's shortest path algorithm and Prim/Kruskal's MST algorithms. Greedy algorithms

Golin, Mordecai J.

112

On-line exact shortest distance query processing  

Microsoft Academic Search

Shortest-path query processing not only serves as a long es- tablished routine for numerous applications in the past but also is of increasing popularity to support novel graph appli- cations in very large databases nowadays. For a large graph, there is the new scenario to query intensively against arbi- trary nodes, asking to quickly return node distance or even shortest

Jiefeng Cheng; Jeffrey Xu Yu

2009-01-01

113

An Algorithm for Measurement and Detection of Path Cheating in Virtual Environments  

E-print Network

An Algorithm for Measurement and Detection of Path Cheating in Virtual Environments Dewan Tanvir, shervin}@discover.uottawa.ca Abstract -- In this paper, we introduce a cheat-free path discovering process of the users, but cheating is detected through a controller. The controller recalculates a path segment when

Ottawa, University of

114

Jumping Scanning Path Error Diffusion: A Novel Halftoning Algorithm Improving Mid-tone Quality  

Microsoft Academic Search

In this paper, we describe a novel error diffusion scheme for higher halftone quality with less visual artifacts. The proposed algorithm improves mid- tone quality of error diffusion significantly by diffusing the error along a jumping scanning path. The algorithm calculates the accumulative error to determine the point where breaks up the scanning path. A cost function is developed to

Yan Zhou; Chun Chen; Qiang Wang; Jiajun Bu

2011-01-01

115

A modified PLS path modeling algorithm handling reflective categorical variables and a new model building strategy  

Microsoft Academic Search

Partial least squares (PLS) path modeling has found increased applications in customer satisfaction analysis thanks to its ability to handle complex models. A modified PLS path modeling algorithm together with a model building strategy are introduced and applied to customer satisfaction analysis at the French energy supplier Electricité de France. The modified PLS algorithm handles all kinds of scales (categorical

Emmanuel Jakobowicz; Christian Derquenne

2007-01-01

116

ON-LINE ALGORITHMS FOR PATH SELECTION IN A NONBLOCKING NETWORK  

E-print Network

ON-LINE ALGORITHMS FOR PATH SELECTION IN A NONBLOCKING NETWORK SANJEEV ARORA , F. THOMSON LEIGHTON , AND BRUCE M. MAGGS § Abstract. This paper presents the first optimal-time algorithms for path selection AMS subject classifications. 68M10, 90B12, 94C10 1. Introduction. 1.1. Definitions. Nonblocking

Arora, Sanjeev

117

Design requirements and development of an airborne descent path definition algorithm for time navigation  

NASA Technical Reports Server (NTRS)

The design requirements for a 4D path definition algorithm are described. These requirements were developed for the NASA ATOPS as an extension of the Local Flow Management/Profile Descent algorithm. They specify the processing flow, functional and data architectures, and system input requirements, and recommended the addition of a broad path revision (reinitialization) function capability. The document also summarizes algorithm design enhancements and the implementation status of the algorithm on an in-house PDP-11/70 computer. Finally, the requirements for the pilot-computer interfaces, the lateral path processor, and guidance and steering function are described.

Izumi, K. H.; Thompson, J. L.; Groce, J. L.; Schwab, R. W.

1986-01-01

118

Research on Application of Key Infrastructure Algorithm about Smart IC Card System  

Microsoft Academic Search

A new method of optimized path planning about smart card based on Dijkstra algorithm is proposed in this paper, for the path planning problem of China road charges. The IC Card Key Infrastructure and CRC check code technology of city uni-card system are combined in the algorithm, and the division with the shortest path using the minimum rate of fees

Xie JianHua; Zhong JianPeng

2009-01-01

119

Lecture 14: Greedy Algorithms CLRS section 16  

E-print Network

Lecture 14: Greedy Algorithms CLRS section 16 Outline of this Lecture We have already seen two introduce a third basic technique: the greedy paradigm . A greedy algorithm for an optimization problem al­ ples already seen are Dijkstra's shortest path algo­ rithm and Prim/Kruskal's MST algorithms . Greedy

Wu, Dekai

120

Lecture 14: Greedy Algorithms CLRS section 16  

E-print Network

Lecture 14: Greedy Algorithms CLRS section 16 Outline of this Lecture We have already seen two introduce a third basic technique: the greedy paradigm . A greedy algorithm for an optimization problem al- ples already seen are Dijkstra's shortest path algo- rithm and Prim/Kruskal's MST algorithms . Greedy

Wu, Dekai

121

An Improved Bidirectional Heuristic Search Algorithm  

Microsoft Academic Search

A modification of Pohl's bidirectional heuristic search algorithm is described together with a simplified implementation. Theorems are proved about conditions yielding shortest paths. The results are given of a worst-case analysis of different algorithms, suggesting a rank order of their quality. Results that Pohl had obtained with a unidirectional heuristic search algorithm on the 15-puzzle are compared with the results

Lenie Sint; Dennis de Champeaux

1977-01-01

122

Optimal assembly path planning algorithm for aircraft part maintenance  

Microsoft Academic Search

In a virtual environment (VE), a maintenance process scheme can simulate the real world maintenance process. With this idea, path planning becomes more important as a factor that affects the overall efficiency of the system. This situation requires that the planner consider path planning, under such constraints as obstacles, the part distance from the initial position to its final position,

Christiand; Jungwon Yoon

2007-01-01

123

A Path to Understanding the Effects of Algorithm Awareness  

E-print Network

of algorithmically curated feeds in online news and social media sites raises a new question for designers, critics, and scholars of media: how aware are users of the role of algorithms and filters in their news sources to the actual proprietary algorithms at work. Author Keywords Visualization; perception; social media; reverse

Karahalios, Karrie G.

124

Optimal and receding-horizon path planning algorithms for communications relay vehicles in complex environments  

E-print Network

This thesis presents new algorithms for path planning in a communications constrained environment for teams of unmanned vehicles. This problem involves a lead vehicle that must gather information from a set of locations ...

Kulling, Karl Christian

2009-01-01

125

Autonomous Local Path-Planning for a Mobile Robot Using a Genetic Algorithm  

E-print Network

Autonomous Local Path-Planning for a Mobile Robot Using a Genetic Algorithm Kamran H. Sedighi obstacle avoidance (local feasible path) of a mobile robot in a given search space. The method tries in intelligent control of an autonomous mobile robot [7-9]. The work presented here is part of a larger project

Wainwright, Roger L.

126

Path-Following Algorithms and Experiments for an Unmanned Surface Vehicle  

E-print Network

Path-Following Algorithms and Experiments for an Unmanned Surface Vehicle Marco Bibuli Istituto di of path-following in two-dimensional space for underactuated unmanned surface vehicles (USVs), defining number of Unmanned Surface Vehicles (USVs) have been developed for a large set of applications

Paris-Sud XI, Université de

127

Microwave radiometer measurements at Liquid water path algorithm development and accuracy  

E-print Network

1 Microwave radiometer measurements at Chilbolton Liquid water path algorithm development Project Report #12;2 CONTENTS 1. INTRODUCTION. 1.1Liquid water clouds 1.2Microwave emission from the atmosphere 1.3Liquid water path retrieval 2. MICROWAVE RADIOMETERS. 2.1Radiometer description. 2.2 Radiometer

Reading, University of

128

An analysis of the multiple paths used in traffic assignment algorithms  

E-print Network

AN ANALYSIS OF THE MULTIPLE PATHS USED IN TRAFFIC ASSIGNMENT ALGORITHMS A Thesis by JULIA ANN KUHN BUTORAC Submitted to the Office of Graduate Studies of Texas A&M University in partial fulfillment of the requirements for the degree... of MASTER OF SCIENCE December 1997 Major Subject: Civil Engineering AN ANALYSIS OF THE MULTIPLE PATHS USED IN TRAFFIC ASSIGNMENT ALGORITHMS A Thesis by JULIA ANN KUHN BUTORAC Submitted to the Office of Graduate Studies of Texas AkM University...

Butorac, Julia Ann Kuhn

2012-06-07

129

Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs  

Microsoft Academic Search

The edge and vertex-disjoint path problems together with their unsplittable flow generalization are NP-hard problems with a multi- tude of applications in areas such as routing, scheduling and bin packing. Given the hardness of the problems, we study polynomial-time approxi- mation algorithms with bounded performance guarantees. We introduce techniques which yield new algorithms for a wide range of disjoint-path problems.

Stavros G. Kolliopoulos; Clifford Stein

1998-01-01

130

A Network Architecture with Virtual Path Hopping and Dynamic Virtual Path Allocation Algorithm  

Microsoft Academic Search

Connection oriented packet networks such as IP\\/MPLS can better meet the QoS guarantees in terms of delay jitter, bandwidth etc. required by premium traffic (PT). These connection oriented networks are more vulnerable to failures and they can be classified into link\\/path and degraded failures. Virtual path hopping concept eliminates all terminations of data communications due to degraded type failures detected

Manodha GAMAGE; Mitsuo HAYASAKA; Tetsuya MIKI

2005-01-01

131

An Algorithm for the Hierarchical Organization of Path Diagrams and Calculation of Components of Expected Covariance.  

ERIC Educational Resources Information Center

Presents an algorithm for the production of a graphical diagram from a matrix formula in such a way that its components are logically and hierarchically arranged. The algorithm, which relies on the matrix equations of J. McArdle and R. McDonald (1984), calculates the individual path components of expected covariance between variables and…

Boker, Steven M.; McArdle, J. J.; Neale, Michael

2002-01-01

132

Path planning using a hybrid evolutionary algorithm based on tree structure encoding.  

PubMed

A hybrid evolutionary algorithm using scalable encoding method for path planning is proposed in this paper. The scalable representation is based on binary tree structure encoding. To solve the problem of hybrid genetic algorithm and particle swarm optimization, the "dummy node" is added into the binary trees to deal with the different lengths of representations. The experimental results show that the proposed hybrid method demonstrates using fewer turning points than traditional evolutionary algorithms to generate shorter collision-free paths for mobile robot navigation. PMID:24971389

Ju, Ming-Yi; Wang, Siao-En; Guo, Jian-Horn

2014-01-01

133

Sampling-based algorithms for optimal path planning problems  

E-print Network

Sampling-based motion planning received increasing attention during the last decade. In particular, some of the leading paradigms, such the Probabilistic RoadMap (PRM) and the Rapidly-exploring Random Tree (RRT) algorithms, ...

Karaman, Sertac

2012-01-01

134

Finite Mixture and Genetic Algorithm Segmentation in Partial Least Squares Path Modeling: Identification of Multiple Segments in Complex Path Models  

NASA Astrophysics Data System (ADS)

When applying structural equation modeling methods, such as partial least squares (PLS) path modeling, in empirical studies, the assumption that the data have been collected from a single homogeneous population is often unrealistic. Unobserved heterogeneity in the PLS estimates on the aggregate data level may result in misleading interpretations. Finite mixture partial least squares (FIMIX-PLS) and PLS genetic algorithm segmentation (PLS-GAS) allow the classification of data in variance-based structural equation modeling. This research presents an initial application and comparison of these two methods in a computational experiment in respect of a path model which includes multiple endogenous latent variables. The results of this analysis reveal particular advantages and disadvantages of the approaches. This study further substantiates the effectiveness of FIMIX-PLS and PLS-GAS and provides researchers and practitioners with additional information they need to proficiently evaluate their PLS path modeling results by applying a systematic means of analysis. If significant heterogeneity were to be uncovered by the procedures, the analysis may result in group-specific path modeling outcomes, thus allowing further differentiated and more precise conclusions to be formed.

Ringle, Christian M.; Sarstedt, Marko; Schlittgen, Rainer

135

Robust Flight Path Determination for Mars Precision Landing Using Genetic Algorithms  

NASA Technical Reports Server (NTRS)

This paper documents the application of genetic algorithms (GAs) to the problem of robust flight path determination for Mars precision landing. The robust flight path problem is defined here as the determination of the flight path which delivers a low-lift open-loop controlled vehicle to its desired final landing location while minimizing the effect of perturbations due to uncertainty in the atmospheric model and entry conditions. The genetic algorithm was capable of finding solutions which reduced the landing error from 111 km RMS radial (open-loop optimal) to 43 km RMS radial (optimized with respect to perturbations) using 200 hours of computation on an Ultra-SPARC workstation. Further reduction in the landing error is possible by going to closed-loop control which can utilize the GA optimized paths as nominal trajectories for linearization.

Bayard, David S.; Kohen, Hamid

1997-01-01

136

The Shortest-Network Problem  

Microsoft Academic Search

The Steiner problem asks for the shortest network of line segments that will interconnect a set of given points. The Steiner problem cannot be solved by simply drawing lines between the given points, but it can be solved by adding new ones, called Steiner points, that serve as junctions in a shortest network. To determine the location and number of

Marshall W. Bern; Ronald L. Graham

1989-01-01

137

JHAV' - Floyd's Algorithm  

NSDL National Science Digital Library

Visualization of Floyd's all-pairs shortest paths algorithm. Includes dynamically highlighted pseudo code. Associated HTML page contains an algorithm description, pseudo code, and example trace, and discussion of efficiency analysis. The AV is set up as a series of 'slides' in one pane, and pseudocode in the adjacent pane. As the user steps through the 'slides', the associated pseudocode is highlighted. Occasional questions pop up for the user to answer. In addition to coloration for the graph as the algorithm progresses, there is a 2D array showing the algorithm's currently computed shortest distances. The explanation pages are a pretty good supplement to the AV (and vice versa). Students might still have a little bit of difficulty understanding the concept of the 'k paths', and there is no reference to dynamic programming, which would be helpful. Recommended as lecture aide, standalone, self-study suppliment to tutorial or lecture.

Richard Teviotdale, Tom N.

138

A Hybrid Metaheuristic DE/CS Algorithm for UCAV Three-Dimension Path Planning  

PubMed Central

Three-dimension path planning for uninhabited combat air vehicle (UCAV) is a complicated high-dimension optimization problem, which primarily centralizes on optimizing the flight route considering the different kinds of constrains under complicated battle field environments. A new hybrid metaheuristic differential evolution (DE) and cuckoo search (CS) algorithm is proposed to solve the UCAV three-dimension path planning problem. DE is applied to optimize the process of selecting cuckoos of the improved CS model during the process of cuckoo updating in nest. The cuckoos can act as an agent in searching the optimal UCAV path. And then, the UCAV can find the safe path by connecting the chosen nodes of the coordinates while avoiding the threat areas and costing minimum fuel. This new approach can accelerate the global convergence speed while preserving the strong robustness of the basic CS. The realization procedure for this hybrid metaheuristic approach DE/CS is also presented. In order to make the optimized UCAV path more feasible, the B-Spline curve is adopted for smoothing the path. To prove the performance of this proposed hybrid metaheuristic method, it is compared with basic CS algorithm. The experiment shows that the proposed approach is more effective and feasible in UCAV three-dimension path planning than the basic CS model. PMID:23193383

Wang, Gaige; Guo, Lihong; Duan, Hong; Wang, Heqi; Liu, Luo; Shao, Mingzhen

2012-01-01

139

A hybrid metaheuristic DE/CS algorithm for UCAV three-dimension path planning.  

PubMed

Three-dimension path planning for uninhabited combat air vehicle (UCAV) is a complicated high-dimension optimization problem, which primarily centralizes on optimizing the flight route considering the different kinds of constrains under complicated battle field environments. A new hybrid metaheuristic differential evolution (DE) and cuckoo search (CS) algorithm is proposed to solve the UCAV three-dimension path planning problem. DE is applied to optimize the process of selecting cuckoos of the improved CS model during the process of cuckoo updating in nest. The cuckoos can act as an agent in searching the optimal UCAV path. And then, the UCAV can find the safe path by connecting the chosen nodes of the coordinates while avoiding the threat areas and costing minimum fuel. This new approach can accelerate the global convergence speed while preserving the strong robustness of the basic CS. The realization procedure for this hybrid metaheuristic approach DE/CS is also presented. In order to make the optimized UCAV path more feasible, the B-Spline curve is adopted for smoothing the path. To prove the performance of this proposed hybrid metaheuristic method, it is compared with basic CS algorithm. The experiment shows that the proposed approach is more effective and feasible in UCAV three-dimension path planning than the basic CS model. PMID:23193383

Wang, Gaige; Guo, Lihong; Duan, Hong; Wang, Heqi; Liu, Luo; Shao, Mingzhen

2012-01-01

140

On-line algorithms for path selection in a nonblocking network  

Microsoft Academic Search

Abstract. This paper presents the rst optimal-time algorithms for path selection in an optimal-size non-blocking network. In particular, we describe an N-input, N-output, nonblocking network with O(N log N) bounded-degree nodes, and an algorithm that can satisfy any request for a connection or disconnection between an input and an output in O(log N) bit steps, even if many requests are

S. Arora; Tom Leighton; Bruce Maggs

1990-01-01

141

A statistical-based scheduling algorithm in automated data path synthesis  

NASA Technical Reports Server (NTRS)

In this paper, we propose a new heuristic scheduling algorithm based on the statistical analysis of the cumulative frequency distribution of operations among control steps. It has a tendency of escaping from local minima and therefore reaching a globally optimal solution. The presented algorithm considers the real world constraints such as chained operations, multicycle operations, and pipelined data paths. The result of the experiment shows that it gives optimal solutions, even though it is greedy in nature.

Jeon, Byung Wook; Lursinsap, Chidchanok

1992-01-01

142

A guided tabu search\\/path relinking algorithm for the job shop problem  

Microsoft Academic Search

The job shop scheduling problem with makespan criterion is valuable from both practical and theoretical points of view. This\\u000a problem has been attacked by most of the well-known meta-heuristic algorithms. Among them, tabu search has emerged as the\\u000a most effective approach. The proposed algorithm takes advantages of both N1 and N6 neighborhoods. N1 neighborhood is used\\u000a as a path relinking

Mohammad Mahdi Nasiri; Farhad Kianfar

143

On the Method of Shortest Residuals for Unconstrained Optimization  

Microsoft Academic Search

The paper discusses several versions of the method of shortest residuals, a specific variant of the conjugate gradient algorithm,\\u000a first introduced by Lemarchal and Wolfe and discussed by Hestenes in a quadratic case. In the paper we analyze the global\\u000a convergence of the versions considered. Numerical comparison of these versions of the method of shortest residuals and an\\u000a implementation of

R. Pytlak; T. Tarnawski

2007-01-01

144

Evolutionary algorithm based offline/online path planner for UAV navigation.  

PubMed

An evolutionary algorithm based framework, a combination of modified breeder genetic algorithms incorporating characteristics of classic genetic algorithms, is utilized to design an offline/online path planner for unmanned aerial vehicles (UAVs) autonomous navigation. The path planner calculates a curved path line with desired characteristics in a three-dimensional (3-D) rough terrain environment, represented using B-spline curves, with the coordinates of its control points being the evolutionary algorithm artificial chromosome genes. Given a 3-D rough environment and assuming flight envelope restrictions, two problems are solved: i) UAV navigation using an offline planner in a known environment, and, ii) UAV navigation using an online planner in a completely unknown environment. The offline planner produces a single B-Spline curve that connects the starting and target points with a predefined initial direction. The online planner, based on the offline one, is given on-board radar readings which gradually produces a smooth 3-D trajectory aiming at reaching a predetermined target in an unknown environment; the produced trajectory consists of smaller B-spline curves smoothly connected with each other. Both planners have been tested under different scenarios, and they have been proven effective in guiding an UAV to its final destination, providing near-optimal curved paths quickly and efficiently. PMID:18238242

Nikolos, I K; Valavanis, K P; Tsourveloudis, N C; Kostaras, A N

2003-01-01

145

An evolution based path planning algorithm for autonomous motion of a UAV through uncertain environments  

Microsoft Academic Search

Adaptive and intelligent on-board path planning is a required part of a fully autonomous UAV. In controlled airspace, such a UAV would have to interact with other vehicles moving though its environment. The locations of obstacles (other vehicles) that form obstructions in the environment may only be known with limited accuracy. Evolutionary algorithms (EA) have been successfully used to compute

David Rathbun; Sean Kragelund; Anawat Pongpunwattana; Brian Capozzi

2002-01-01

146

Balancing safety and speed in the military path finding problem: analysis of different ACO algorithms  

Microsoft Academic Search

hCHAC, a MOACO implemented to solve the problem of finding the path that minimizes resources, while maximi- zing safety for a military unit in realistic battlefields, is compared with some other approaches: two extreme me- thods, which only considers one objective in the search, and a mono-objective algorithm, which combines the two objec- tives terms of the formulae in a

Antonio Miguel Mora; Juan Julián Merelo Guervós; Juan Luís Jiménez Laredo; Pedro A. Castillo Valdivieso; Cristian Millán; Juan Torrecillas

2007-01-01

147

Generalized Hough transform: A useful algorithm for signal path detection  

NASA Astrophysics Data System (ADS)

How is it possible to recognize ETI signals coming from exoplanets? This is one of the questions that SETI researchers must answer. In early 1998, the Italian SETI program [S. Montebugnoli, et al., SETItalia, A new era in bioastronomy, ASP Conference Series, vol. 213, 2000, pp. 501-504.] started in Medicina with the installation of the Serendip IV 24Million Channel digital spectrometer. This system daily acquires a huge quantity of data to be processed off line, in order to detect possible ETI signals. The programs devoted to this topic are collectively called SALVE 2. Here a natural evolution of a previous effort is presented, which was based on a simple Hough transform and was limited to the detection of short linear tracks in the join time frequency matrix (JTFM) stored by SIV. The new generalized Hough algorithm allows us to detect the sinusoidal tracks by the transformation of the JTF bidimensional Cartesian space (x,y), in the generalized Hough quadridimensional space, where the main vectors are the sine parameters amplitude, frequency, phase and offset. At the end of the paper some results, obtained with the computation of real and simulated JTFM, are shown.

Monari, Jader; Montebugnoli, Stelio; Orlati, Andrea; Ferri, Massimo; Leone, Giorgio

2006-02-01

148

Short paths in expander graphs  

SciTech Connect

Graph expansion has proved to be a powerful general tool for analyzing the behavior of routing algorithms and the interconnection networks on which they run. We develop new routing algorithms and structural results for bounded-degree expander graphs. Our results are unified by the fact that they are all based upon, and extend, a body of work asserting that expanders are rich in short, disjoint paths. In particular, our work has consequences for the disjoint paths problem, multicommodify flow, and graph minor containment. We show: (i) A greedy algorithm for approximating the maximum disjoint paths problem achieves a polylogarithmic approximation ratio in bounded-degree expanders. Although our algorithm is both deterministic and on-line, its performance guarantee is an improvement over previous bounds in expanders. (ii) For a multicommodily flow problem with arbitrary demands on a bounded-degree expander, there is a (1 + {epsilon})-optimal solution using only flow paths of polylogarithmic length. It follows that the multicommodity flow algorithm of Awerbuch and Leighton runs in nearly linear time per commodity in expanders. Our analysis is based on establishing the following: given edge weights on an expander G, one can increase some of the weights very slightly so the resulting shortest-path metric is smooth - the min-weight path between any pair of nodes uses a polylogarithmic number of edges. (iii) Every bounded-degree expander on n nodes contains every graph with O(n/log{sup O(1)} n) nodes and edges as a minor.

Kleinberg, J. [MIT, Cambridge, MA (United States); Rubinfeld, R. [Cornell Univ., Ithaca, NY (United States)

1996-12-31

149

Optimal network problem: a branch-and-bound algorithm  

Microsoft Academic Search

The problem of selecting a subset of links so as to minimize the sum of shortest path distances between all pairs of nodes, subject to a budget constraint on total length of links, may be solved by a modification of a branch-and-bound algorithm developed for optimal variable selection problems in statistics. The modified algorithm is described in detail, and encouraging

D E Boyce; A Farhi; R Weischedel

1973-01-01

150

Research of the Image Segmentation Based on Ant Colony Algorithm  

Microsoft Academic Search

Ant colony algorithm, based on behavior of real ants, is a natural approach to establish from their nest to food source. An ant moves randomly and detects a previously laid pheromone on a path in order to find the shortest way between their nest and the food source. Ant system algorithm is an important methodology to apply on non-linear optimal

Zhe Yan; Han-ming Gu

2009-01-01

151

Modified a* Algorithm Implementation in the Routing Optimized for Use in Geospatial Information Systems  

NASA Astrophysics Data System (ADS)

Among the main issues in the theory of geometric grids on spatial information systems, is the problem of finding the shortest path routing between two points. In this paper tried to using the graph theory and A* algorithms in transport management, the optimal method to find the shortest path with shortest time condition to be reviewed. In order to construct a graph that consists of a network of pathways and modelling of physical and phasing area, the shortest path routes, elected with the use of the algorithm is modified A*.At of the proposed method node selection Examining angle nodes the desired destination node and the next node is done. The advantage of this method is that due to the elimination of some routes, time of route calculation is reduced.

Ayazi, S. M.; Mashhorroudi, M. F.; Ghorbani, M.

2014-10-01

152

Formal language constrained path problems  

SciTech Connect

In many path finding problems arising in practice, certain patterns of edge/vertex labels in the labeled graph being traversed are allowed/preferred, while others are disallowed. Motivated by such applications as intermodal transportation planning, the authors investigate the complexity of finding feasible paths in a labeled network, where the mode choice for each traveler is specified by a formal language. The main contributions of this paper include the following: (1) the authors show that the problem of finding a shortest path between a source and destination for a traveler whose mode choice is specified as a context free language is solvable efficiently in polynomial time, when the mode choice is specified as a regular language they provide algorithms with improved space and time bounds; (2) in contrast, they show that the problem of finding simple paths between a source and a given destination is NP-hard, even when restricted to very simple regular expressions and/or very simple graphs; (3) for the class of treewidth bounded graphs, they show that (i) the problem of finding a regular language constrained simple path between source and a destination is solvable in polynomial time and (ii) the extension to finding context free language constrained simple paths is NP-complete. Several extensions of these results are presented in the context of finding shortest paths with additional constraints. These results significantly extend the results in [MW95]. As a corollary of the results, they obtain a polynomial time algorithm for the BEST k-SIMILAR PATH problem studied in [SJB97]. The previous best algorithm was given by [SJB97] and takes exponential time in the worst case.

Barrett, C.; Jacob, R.; Marathe, M.

1997-07-08

153

A path planning algorithm for lane-following-based autonomous mobile robot navigation  

NASA Astrophysics Data System (ADS)

In this paper we address the problem of autonomous robot navigation in a "roadway" type environment, where the robot has to drive forward on a defined path that could be impeded by the presence of obstacles. The specific context is the Autonomous Challenge of the Intelligent Ground Vehicle Competition (www.igvc.org). The task of the path planner is to ensure that the robot follows the path without turning back, as can happen in switchbacks, and/or leaving the course, as can happen in dashed or single lane line situations. A multi-behavior path planning algorithm is proposed. The first behavior determines a goal using a center of gravity (CoG) computation from the results of image processing techniques designed to extract lane lines. The second behavior is based on developing a sense of the current "general direction" of the contours of the course. This is gauged based on the immediate path history of the robot. An adaptive-weight-based fusion of the two behaviors is used to generate the best overall direction. This multi-behavior path planning strategy has been evaluated successfully in a Player/Stage simulation environment and subsequently implemented in the 2009 IGVC. The details of our experience will be presented at the conference.

Aljeroudi, Yazan; Paulik, Mark; Krishnan, Mohan; Luo, Chaomin

2010-01-01

154

Calibration of neural networks using genetic algorithms, with application to optimal path planning  

NASA Technical Reports Server (NTRS)

Genetic algorithms (GA) are used to search the synaptic weight space of artificial neural systems (ANS) for weight vectors that optimize some network performance function. GAs do not suffer from some of the architectural constraints involved with other techniques and it is straightforward to incorporate terms into the performance function concerning the metastructure of the ANS. Hence GAs offer a remarkably general approach to calibrating ANS. GAs are applied to the problem of calibrating an ANS that finds optimal paths over a given surface. This problem involves training an ANS on a relatively small set of paths and then examining whether the calibrated ANS is able to find good paths between arbitrary start and end points on the surface.

Smith, Terence R.; Pitney, Gilbert A.; Greenwood, Daniel

1987-01-01

155

Orbital Systolic Algorithms and Array Processors for Solution of the Algebraic Path Problem  

NASA Astrophysics Data System (ADS)

The algebraic path problem (APP) is a general framework which unifies several solution procedures for a number of well-known matrix and graph problems. In this paper, we present a new 3-dimensional (3-D) orbital algebraic path algorithm and corresponding 2-D toroidal array processors which solve the n × n APP in the theoretically minimal number of 3n time-steps. The coordinated time-space scheduling of the computing and data movement in this 3-D algorithm is based on the modular function which preserves the main technological advantages of systolic processing: simplicity, regularity, locality of communications, pipelining, etc. Our design of the 2-D systolic array processors is based on a classical 3-D?2-D space transformation. We have also shown how a data manipulation (copying and alignment) can be effectively implemented in these array processors in a massively-parallel fashion by using a matrix-matrix multiply-add operation.

Sedukhin, Stanislav G.; Miyazaki, Toshiaki; Kuroda, Kenichi

156

On-Line Algorithms for Path Selection in a Nonblocking Network  

Microsoft Academic Search

Nonblocking networks arise in a variety of communication contextsincluding telephone systems and distributed-memory computer architectures.Although asymptotically optimal constructions are known forseveral species of nonblocking networks, it is generally not known howto select paths for the desired network connections efficiently on-line.In this paper, we present the first optimal-time algorithms for pathselection in an optimal-size nonblocking network. In particular, we describean...

Sanjeev Arora; Frank Thomson Leighton; Bruce M. Maggs

1996-01-01

157

A randomized algorithm for finding a path subject to multiple QoS requirements  

Microsoft Academic Search

An important aspect of quality-of-service (QoS) provisioning in integrated networks is the ability to find a feasible route that satisfies a set of end-to-end QoS requirements (or constraints) while efficiently using network resources. In general, finding a path subject to multiple additive constraints (e.g., delay, delay-jitter) is an NP-complete problem. We propose an efficient randomized heuristic algorithm to this problem.

Turgay Korkmaz; Marwan Krunz

2001-01-01

158

A Memetic Algorithm for OSPF Routing Luciana S. Buriol, UNICAMP, Campinas, SP, Brazil  

E-print Network

paths, splitting flow at nodes with more than one outgoing link on a shortest path to the destination IP assignment problem is NP-hard. Ericsson, Resende, and Pardalos [2] proposed a genetic algorithm (GA) for OSPF weight setting. In this paper, we extend the GA by adding to it a local improvement procedure, resulting

Resende, Mauricio G. C.

159

Application of GA, PSO, and ACO algorithms to path planning of autonomous underwater vehicles  

NASA Astrophysics Data System (ADS)

In this paper, an underwater vehicle was modeled with six dimensional nonlinear equations of motion, controlled by DC motors in all degrees of freedom. Near-optimal trajectories in an energetic environment for underwater vehicles were computed using a numerical solution of a nonlinear optimal control problem (NOCP). An energy performance index as a cost function, which should be minimized, was defined. The resulting problem was a two-point boundary value problem (TPBVP). A genetic algorithm (GA), particle swarm optimization (PSO), and ant colony optimization (ACO) algorithms were applied to solve the resulting TPBVP. Applying an Euler-Lagrange equation to the NOCP, a conjugate gradient penalty method was also adopted to solve the TPBVP. The problem of energetic environments, involving some energy sources, was discussed. Some near-optimal paths were found using a GA, PSO, and ACO algorithms. Finally, the problem of collision avoidance in an energetic environment was also taken into account.

Aghababa, Mohammad Pourmahmood; Amrollahi, Mohammad Hossein; Borjkhani, Mehdi

2012-09-01

160

Shortest Recurrence Periods of Novae  

NASA Astrophysics Data System (ADS)

Stimulated by the recent discovery of the 1 yr recurrence period nova M31N 2008-12a, we examined the shortest recurrence periods of hydrogen shell flashes on mass-accreting white dwarfs (WDs). We discuss the mechanism that yields a finite minimum recurrence period for a given WD mass. Calculating the unstable flashes for various WD masses and mass accretion rates, we identified a shortest recurrence period of about two months for a non-rotating 1.38 M ? WD with a mass accretion rate of 3.6 × 10-7 M ? yr-1. A 1 yr recurrence period is realized for very massive (gsim 1.3 M ?) WDs with very high accretion rates (gsim 1.5 × 10-7 M ? yr-1). We revised our stability limit of hydrogen shell burning, which will be useful for binary evolution calculations toward Type Ia supernovae.

Kato, Mariko; Saio, Hideyuki; Hachisu, Izumi; Nomoto, Ken'ichi

2014-10-01

161

Shortest Recurrence Periods of Novae  

E-print Network

Stimulated by the recent discovery of the 1 yr recurrence period nova M31N 2008-12a, we examined shortest recurrence periods of hydrogen shell flashes on mass-accreting white dwarfs (WDs). We discuss the mechanism that yields a finite minimum recurrence period for a given WD mass. Calculating unstable flashes for various WD masses and mass-accretion rates, we identified the shortest recurrence period of about two months for a non-rotating 1.38 M_\\sun WD with a mass-accretion rate of 3.6 \\times 10^{-7} M_\\sun yr^{-1}. One year recurrence period is realized for very massive (> 1.3 M_\\sun) WDs with very high accretion rates (>1.5 \\times 10^{-7} M_\\sun yr^{-1}). We also present a revised stability limit of hydrogen shell burning, which will be useful for binary evolution calculations toward Type Ia supernovae.

Kato, Mariko; Hachisu, Izumi; Nomoto, Ken'ichi

2014-01-01

162

Practical Routing and Wavelength Assignment algorithms for All Optical Networks with Limited Wavelength Conversion  

E-print Network

Practical Routing and Wavelength Assignment algorithms for All Optical Networks with Limited Wavelength Conversion M.D. Swaminathan*, Indian Institute of Science, Bangalore, India. K.N. Sivarajan, kumar and a Ã? shortest path based heuristic algorithm for solving the Rout- ing and Wavelength Assignment

Swaminathan, Madhavan

163

IPED: inheritance path-based pedigree reconstruction algorithm using genotype data.  

PubMed

The problem of inference of family trees, or pedigree reconstruction, for a group of individuals is a fundamental problem in genetics. Various methods have been proposed to automate the process of pedigree reconstruction given the genotypes or haplotypes of a set of individuals. Current methods, unfortunately, are very time-consuming and inaccurate for complicated pedigrees, such as pedigrees with inbreeding. In this work, we propose an efficient algorithm that is able to reconstruct large pedigrees with reasonable accuracy. Our algorithm reconstructs the pedigrees generation by generation, backward in time from the extant generation. We predict the relationships between individuals in the same generation using an inheritance path-based approach implemented with an efficient dynamic programming algorithm. Experiments show that our algorithm runs in linear time with respect to the number of reconstructed generations, and therefore, it can reconstruct pedigrees that have a large number of generations. Indeed it is the first practical method for reconstruction of large pedigrees from genotype data. PMID:24093229

He, Dan; Wang, Zhanyong; Han, Buhm; Parida, Laxmi; Eskin, Eleazar

2013-10-01

164

Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings  

E-print Network

)-approximate distributed algorithms for the generalized Steiner forest problem, the minimum routing cost spanning tree optimization problems. Our approach is randomized and based on a probabilistic tree em- bedding due problem, and the k-source shortest paths problem in arbitrary networks. The time complexities of our

Khan, Maleq

165

Algorithm for the Optimal Riding Scheme Problem in Public traffic  

Microsoft Academic Search

A two-stage algorithm is proposed for the optimal riding scheme problem in public traffic querying system. The first stage is to find out the least transfer schemes, in which bus line network model is presented to convert the least transfer scheme problem into the shortest path problem. The second stage is to search out the optimal riding scheme from the

Dong Jiyang; Chen Luzhuo

2005-01-01

166

An Improved Artificial Bee Colony Algorithm Based on Balance-Evolution Strategy for Unmanned Combat Aerial Vehicle Path Planning  

PubMed Central

Unmanned combat aerial vehicles (UCAVs) have been of great interest to military organizations throughout the world due to their outstanding capabilities to operate in dangerous or hazardous environments. UCAV path planning aims to obtain an optimal flight route with the threats and constraints in the combat field well considered. In this work, a novel artificial bee colony (ABC) algorithm improved by a balance-evolution strategy (BES) is applied in this optimization scheme. In this new algorithm, convergence information during the iteration is fully utilized to manipulate the exploration/exploitation accuracy and to pursue a balance between local exploitation and global exploration capabilities. Simulation results confirm that BE-ABC algorithm is more competent for the UCAV path planning scheme than the conventional ABC algorithm and two other state-of-the-art modified ABC algorithms. PMID:24790555

Gong, Li-gang; Yang, Wen-lun

2014-01-01

167

Robot Path Integration in Manufacturing Processes: Genetic Algorithm Versus Ant Colony Optimization  

Microsoft Academic Search

Tool path planning for automated manufacturing processes is a computationally complex task. This paper addresses the problem of tool path integration in the context of spray-forming processes. Tool paths for geometry-complicated parts are generated by partitioning them into individual freeform surfaces, generating the paths for each partition, and then, finally, interconnecting the paths from the different patches so as to

Tewolde S. Tewolde; Weihua Sheng

2008-01-01

168

Fast two-dimensional phase-unwrapping algorithm based on sorting by reliability following a noncontinuous path.  

PubMed

We describe what is to our knowledge a novel technique for phase unwrapping. Several algorithms based on unwrapping the most-reliable pixels first have been proposed. These were restricted to continuous paths and were subject to difficulties in defining a starting pixel. The technique described here uses a different type of reliability function and does not follow a continuous path to perform the unwrapping operation. The technique is explained in detail and illustrated with a number of examples. PMID:12502301

Herráez, Miguel Arevallilo; Burton, David R; Lalor, Michael J; Gdeisat, Munther A

2002-12-10

169

An Algorithm to Compute Statistics of Stochastic Paths on Complex Landscapes  

NASA Astrophysics Data System (ADS)

Many systems in physics, chemistry, and biology can be modeled as a random walk on a network subject to a potential landscape. There is great interest in understanding the statistical properties of pathways on these landscapes, especially their times, lengths, and distributions in space. The complexity of the networks and landscapes arising in many models makes them difficult to solve by traditional analytical and computational tools. Moreover, standard methods do not always provide the most relevant information for characterizing these pathways. We develop an explicitly path-based formalism for studying these problems, which we implement using a numerical dynamic programming algorithm. It is especially well-suited to studying first-passage problems and rare transitions between metastable states. This method is valid for arbitrary networks and landscapes, as well as semi-Markovian processes with non-exponential waiting-time distributions. We explore this method on a variety of simple models including regular lattices, fractals, and protein sequence evolution.

Manhart, Michael; Morozov, Alexandre V.

2013-03-01

170

WORM ALGORITHM PATH INTEGRAL MONTE CARLO APPLIED TO THE 3He-4He II SANDWICH SYSTEM  

NASA Astrophysics Data System (ADS)

We present a numerical investigation of the thermal and structural properties of the 3He-4He sandwich system adsorbed on a graphite substrate using the worm algorithm path integral Monte Carlo (WAPIMC) method [M. Boninsegni, N. Prokof'ev and B. Svistunov, Phys. Rev. E74, 036701 (2006)]. For this purpose, we have modified a previously written WAPIMC code originally adapted for 4He on graphite, by including the second 3He-component. To describe the fermions, a temperature-dependent statistical potential has been used. This has proven very effective. The WAPIMC calculations have been conducted in the millikelvin temperature regime. However, because of the heavy computations involved, only 30, 40 and 50 mK have been considered for the time being. The pair correlations, Matsubara Green's function, structure factor, and density profiles have been explored at these temperatures.

Al-Oqali, Amer; Sakhel, Asaad R.; Ghassib, Humam B.; Sakhel, Roger R.

2012-12-01

171

Cloud Liquid Water Path for the Rain/No-rain Classification Method over Ocean in the GSMaP Algorithm  

NASA Astrophysics Data System (ADS)

The rain/no-rain threshold value of cloud liquid water path is important for rain/no-rain classification in microwave precipitation retrieval algorithms. In our previous study, we proposed a parameterization of rain/no-rain threshold value of cloud liquid water path as a function of storm height for the Global Satellite Mapping of Precipitation (GSMaP) algorithm. In this study, we determine rain/no-rain threshold value of cloud liquid water path using the CloudSat precipitation product. The threshold values of cloud liquid water path from the CloudSat precipitation product are lower than 0.5 kg m-2 for GSMaP over all regions. The threshold value of cloud liquid water path is found at its peak in the tropics and decreases poleward. The threshold value of cloud liquid water content computed from threshold value of cloud liquid water path divided by the zonal mean storm height is employed on the parameterization of threshold values of cloud liquid water path. The result shows that GSMaP with new parameterization can detect the shallow rain observed by CloudSat and improves the rain-rate distribution over rain rate less than 0.1 mm h-1.

Kida, Satoshi; Shige, Shoichi; Manabe, Takeshi; L'Ecuyer, Tristan; Liu, Gousheng

172

Constraint satisfaction using a hybrid evolutionary hill-climbing algorithm that performs opportunistic arc and path revision  

SciTech Connect

This paper introduces a hybrid evolutionary hill-climbing algorithm that quickly solves (Constraint Satisfaction Problems (CSPs)). This hybrid uses opportunistic arc and path revision in an interleaved fashion to reduce the size of the search space and to realize when to quit if a CSP is based on an inconsistent constraint network. This hybrid outperforms a well known hill-climbing algorithm, the Iterative Descent Method, on a test suite of 750 randomly generated CSPs.

Bowen, J. [National Univ. of Ireland, Cork (Ireland); Dozier, G. [North Carolina A& T State Univ., Greensboro, NC (United States)

1996-12-31

173

VTL Zone-Aware Path Cloaking Algorithm Bin Zan Peng Hao* Marco Gruteser XueGang Ban*  

E-print Network

--Traffic engineering applications often benefit from collecting vehicle GPS traces in well-defined locations. As a motivating example, we will consider a traffic signal performance evaluation technique which requires GPS to 82% compared to a zone-unaware path cloaking algorithm, while achieving a similar degree of privacy

Gruteser, Marco

174

Adiabatic path integral molecular dynamics methods. II. Algorithms Department of Chemistry, University of Pennsylvania, Philadelphia, Pennsylvania 19104-6323  

E-print Network

. A semiclassical, finite temperature, quantum dynamics scheme based on the use of classical time correlation funcAdiabatic path integral molecular dynamics methods. II. Algorithms J. Cao Department of Chemistry approximations to quantum dynamics both of which require trajectories generated on potentials of mean force

Cao, Jianshu

175

Spreading paths in partially observed social networks.  

PubMed

Understanding how and how far information, behaviors, or pathogens spread in social networks is an important problem, having implications for both predicting the size of epidemics, as well as for planning effective interventions. There are, however, two main challenges for inferring spreading paths in real-world networks. One is the practical difficulty of observing a dynamic process on a network, and the other is the typical constraint of only partially observing a network. Using static, structurally realistic social networks as platforms for simulations, we juxtapose three distinct paths: (1) the stochastic path taken by a simulated spreading process from source to target; (2) the topologically shortest path in the fully observed network, and hence the single most likely stochastic path, between the two nodes; and (3) the topologically shortest path in a partially observed network. In a sampled network, how closely does the partially observed shortest path (3) emulate the unobserved spreading path (1)? Although partial observation inflates the length of the shortest path, the stochastic nature of the spreading process also frequently derails the dynamic path from the shortest path. We find that the partially observed shortest path does not necessarily give an inflated estimate of the length of the process path; in fact, partial observation may, counterintuitively, make the path seem shorter than it actually is. PMID:22587148

Onnela, Jukka-Pekka; Christakis, Nicholas A

2012-03-01

176

Spreading paths in partially observed social networks  

PubMed Central

Understanding how and how far information, behaviors, or pathogens spread in social networks is an important problem, having implications for both predicting the size of epidemics, as well as for planning effective interventions. There are, however, two main challenges for inferring spreading paths in real-world networks. One is the practical difficulty of observing a dynamic process on a network, and the other is the typical constraint of only partially observing a network. Using a static, structurally realistic social network as a platform for simulations, we juxtapose three distinct paths: (1) the stochastic path taken by a simulated spreading process from source to target; (2) the topologically shortest path in the fully observed network, and hence the single most likely stochastic path, between the two nodes; and (3) the topologically shortest path in a partially observed network. In a sampled network, how closely does the partially observed shortest path (3) emulate the unobserved spreading path (1)? Although partial observation inflates the length of the shortest path, the stochastic nature of the spreading process also frequently derails the dynamic path from the shortest path. We find that the partially observed shortest path does not necessarily give an inflated estimate of the length of the process path; in fact, partial observation may, counterintuitively, make the path seem shorter than it actually is. PMID:22587148

Onnela, Jukka-Pekka; Christakis, Nicholas A.

2012-01-01

177

Spreading paths in partially observed social networks  

NASA Astrophysics Data System (ADS)

Understanding how and how far information, behaviors, or pathogens spread in social networks is an important problem, having implications for both predicting the size of epidemics, as well as for planning effective interventions. There are, however, two main challenges for inferring spreading paths in real-world networks. One is the practical difficulty of observing a dynamic process on a network, and the other is the typical constraint of only partially observing a network. Using static, structurally realistic social networks as platforms for simulations, we juxtapose three distinct paths: (1) the stochastic path taken by a simulated spreading process from source to target; (2) the topologically shortest path in the fully observed network, and hence the single most likely stochastic path, between the two nodes; and (3) the topologically shortest path in a partially observed network. In a sampled network, how closely does the partially observed shortest path (3) emulate the unobserved spreading path (1)? Although partial observation inflates the length of the shortest path, the stochastic nature of the spreading process also frequently derails the dynamic path from the shortest path. We find that the partially observed shortest path does not necessarily give an inflated estimate of the length of the process path; in fact, partial observation may, counterintuitively, make the path seem shorter than it actually is.

Onnela, Jukka-Pekka; Christakis, Nicholas A.

2012-03-01

178

Tool path integration for spray forming processes using a genetic algorithm  

Microsoft Academic Search

Spray forming is a new manufacturing process. The automated tool planning for this process is a nontrivial problem, especially for geometry-complicated parts consisting of multiple freeform surfaces. We have developed a tool path planning system which can automatically generate optimized tool plans. This paper focuses on the path integration problem, or how to connect the paths from different surface patches

Weihua Sheng; Girma Tewolde; Heping Chen

2005-01-01

179

A bidding algorithm for optimized utility-based resource allocation in ad hoc networks  

E-print Network

- sically derived shadow prices. We then combine the admission control scheme with a utility-aware on-demand shortest path routing algorithm where shadow prices are used as a natural distance metric. As a baseline close to the optimum. Next we isolate the performance of price-based routing and show its advantages

180

Continuous-Time Dynamic Shortest Path BRIAN C. DEAN  

E-print Network

and Computer Science on May 21, 1999, in partial fulfillment of the requirements for the degrees of Bachelor of Electrical Engineering and Computer Science in partial fulfillment of the requirements for the degrees of Bachelor of Science in Electrical Engineering and Computer Science and Master of Engineering in Computer

Dean, Brian C.

181

Assignment of Shortest Paths Spanning Trees in Meshes  

Microsoft Academic Search

Summary form only given. Broadcast operations are commonly used in a large variety of applications like: video-conference, television, etc. These applications need high level of QoS. Moreover, in such applications, each receiver has to pay to receive data. In the particular case of broadcast, the price paid by a given receiver is determined by multiple parameters like its location in

Christian Destré; Christian Laforest; Sandrine Vial

2004-01-01

182

Expected Shortest Paths for Landmark-Based Robot Navigation  

E-print Network

of planning reliable landmark- based robot navigation strategies in the presence of significant sensor and constructs their visibility graph. This graph is continually updated during subsequent navigation. All motion can be detected. These estimates are based on the history of all observations made by the robot

Scharstein, Daniel

183

A computational study of routing algorithms for realistic transportation networks  

SciTech Connect

The authors carry out an experimental analysis of a number of shortest path (routing) algorithms investigated in the context of the TRANSIMS (Transportation Analysis and Simulation System) project. The main focus of the paper is to study how various heuristic and exact solutions, associated data structures affected the computational performance of the software developed especially for realistic transportation networks. For this purpose the authors have used Dallas Fort-Worth road network with very high degree of resolution. The following general results are obtained: (1) they discuss and experimentally analyze various one-one shortest path algorithms, which include classical exact algorithms studied in the literature as well as heuristic solutions that are designed to take into account the geometric structure of the input instances; (2) they describe a number of extensions to the basic shortest path algorithm. These extensions were primarily motivated by practical problems arising in TRANSIMS and ITS (Intelligent Transportation Systems) related technologies. Extensions discussed include--(i) time dependent networks, (ii) multi-modal networks, (iii) networks with public transportation and associated schedules. Computational results are provided to empirically compare the efficiency of various algorithms. The studies indicate that a modified Dijkstra`s algorithm is computationally fast and an excellent candidate for use in various transportation planning applications as well as ITS related technologies.

Jacob, R.; Marathe, M.V.; Nagel, K.

1998-12-01

184

Nearly arc-length tool path generation and tool radius compensation algorithm research in FTS turning  

NASA Astrophysics Data System (ADS)

In the non-rotational symmetrical microstrcture surfaces generation using turning method with Fast Tool Servo(FTS), non-uniform distribution of the interpolation data points will lead to long processing cycle and poor surface quality. To improve this situation, nearly arc-length tool path generation algorithm is proposed, which generates tool tip trajectory points in nearly arc-length instead of the traditional interpolation rule of equal angle and adds tool radius compensation. All the interpolation points are equidistant in radial distribution because of the constant feeding speed in X slider, the high frequency tool radius compensation components are in both X direction and Z direction, which makes X slider difficult to follow the input orders due to its large mass. Newton iterative method is used to calculate the neighboring contour tangent point coordinate value with the interpolation point X position as initial value, in this way, the new Z coordinate value is gotten, and the high frequency motion components in X direction is decomposed into Z direction. Taking a typical microstructure with 4?m PV value for test, which is mixed with two 70?m wave length sine-waves, the max profile error at the angle of fifteen is less than 0.01?m turning by a diamond tool with big radius of 80?m. The sinusoidal grid is machined on a ultra-precision lathe succesfully, the wavelength is 70.2278?m the Ra value is 22.81nm evaluated by data points generated by filtering out the first five harmonics.

Zhao, Minghui; Zhao, Xuesen; Li, Zengqiang; Sun, Tao

2014-08-01

185

Assessing path-following performance for Unmanned Marine Vehicles with algorithms from Numerical Commutative Algebra  

E-print Network

a desired generic curvilinear path. The main advantages of the method are represented by the possibility and research (both theoretical and application-oriented) about possible techniques for quantitatively measuring performance indices and metrics to quantitatively measure and compare path-following performance. It focuses

Robbiano, Lorenzo

186

Path-Distance Heuristics for the Steiner Problem in Undirected Networks  

Microsoft Academic Search

An integrative overview of the algorithmic characteristics of three well-known polynomialtime heuristics for the undirected\\u000a Steiner minimum tree problem:shortest path heuristic (SPH),distance network heuristic (DNH), andaverage distance heuristic (ADH) is given. The performance of thesesingle-pass heuristics (and some variants) is compared and contrasted with several heuristics based onrepetitive applications of the SPH. It is shown that two of these repetitive

Pawel Winter; J. Macgregor Smith

1992-01-01

187

An enhanced dynamic Delaunay triangulation-based path planning algorithm for autonomous mobile robot navigation  

NASA Astrophysics Data System (ADS)

An enhanced dynamic Delaunay Triangulation-based (DT) path planning approach is proposed for mobile robots to plan and navigate a path successfully in the context of the Autonomous Challenge of the Intelligent Ground Vehicle Competition (www.igvc.org). The Autonomous Challenge course requires the application of vision techniques since it involves path-based navigation in the presence of a tightly clustered obstacle field. Course artifacts such as switchbacks, ramps, dashed lane lines, trap etc. are present which could turn the robot around or cause it to exit the lane. The main contribution of this work is a navigation scheme based on dynamic Delaunay Triangulation (DDT) that is heuristically enhanced on the basis of a sense of general lane direction. The latter is computed through a "GPS (Global Positioning System) tail" vector obtained from the immediate path history of the robot. Using processed data from a LADAR, camera, compass and GPS unit, a composite local map containing both obstacles and lane line segments is built up and Delaunay Triangulation is continuously run to plan a path. This path is heuristically corrected, when necessary, by taking into account the "GPS tail" . With the enhancement of the Delaunay Triangulation by using the "GPS tail", goal selection is successfully achieved in a majority of situations. The robot appears to follow a very stable path while navigating through switchbacks and dashed lane line situations. The proposed enhanced path planning and GPS tail technique has been successfully demonstrated in a Player/Stage simulation environment. In addition, tests on an actual course are very promising and reveal the potential for stable forward navigation.

Chen, Jun; Luo, Chaomin; Krishnan, Mohan; Paulik, Mark; Tang, Yipeng

2010-01-01

188

High-quality path planning for autonomous mobile robots with ?3-splines and parallel genetic algorithms  

Microsoft Academic Search

In this paper we apply the composite eta3 splines to collision-free curvature-derivative continuous shorter path planning of wheeled mobile robots, modelled as unicycle, within known static environments. The path planning problem is formulated as a bi-objective optimization problem of searching a sequence of N ordered intermediate configurations between start and goal configurations over the group of all possible configurations that

Han-Chih Chang; Jing-Sin Liu

2009-01-01

189

An algorithm to find minimum free-energy paths using umbrella integration  

NASA Astrophysics Data System (ADS)

The calculation of free-energy barriers by umbrella sampling and many other methods is hampered by the necessity for an a priori choice of the reaction coordinate along which to sample. We avoid this problem by providing a method to search for saddle points on the free-energy surface in many coordinates. The necessary gradients and Hessians of the free energy are obtained by multidimensional umbrella integration. We construct the minimum free-energy path by following the gradient down to minima on the free-energy surface. The change of free energy along the path is obtained by integrating out all coordinates orthogonal to the path. While we expect the method to be applicable to large systems, we test it on the alanine dipeptide in vacuum. The minima, transition states, and free-energy barriers agree well with those obtained previously with other methods.

Bohner, Matthias U.; Kästner, Johannes

2012-07-01

190

Evaluation of P2P Search Algorithms for Discovering Trust Paths  

E-print Network

, Trust Paths. 1 Introduction The effectiveness and efficiency of any commercial interaction depends strongly on the level of trust that exists between involved parties. Trust determines if parties are willing to depend on each other, even if negative consequences are Supported by CNPq. This work

Newcastle upon Tyne, University of

191

Hierarchical oriented genetic algorithms for coverage path planning of multi-robot teams with load balancing  

Microsoft Academic Search

Multi-robot coverage path planning problems require every point in a given area to be covered by at least one member of the robot team using their sensors. For a time-efficient coverage, the environment needs to be partitioned among robots in a balanced manner. So the problem can be modeled as task assignment problem with load balancing. In this study, we

Metin Ozkan; Ahmet Yazici; Muzaffer Kapanoglu; Osman Parlaktuna

2009-01-01

192

Path Planning with obstacle avoidance  

NASA Technical Reports Server (NTRS)

The research report here summarizes a solution for two dimensional Path Planning with obstacle avoidance in a workspace with stationary obstacles. The solution finds the shortest path for the end effector of a manipulator arm. The program uses an overhead image of the robot work space and the starting and ending positions of the manipulator arm end effector to generate a search graph which is used to find the shortest path through the work area. The solution was originally implemented in VAX Pascal, but was later converted to VAX C.

Krause, Donald M.

1987-01-01

193

Efficient algorithms for semiclassical instanton calculations based on discretized path integrals.  

PubMed

Path integral instanton method is a promising way to calculate the tunneling splitting of energies for degenerated two state systems. In order to calculate the tunneling splitting, we need to take the zero temperature limit, or the limit of infinite imaginary time duration. In the method developed by Richardson and Althorpe [J. Chem. Phys. 134, 054109 (2011)], the limit is simply replaced by the sufficiently long imaginary time. In the present study, we have developed a new formula of the tunneling splitting based on the discretized path integrals to take the limit analytically. We have applied our new formula to model systems, and found that this approach can significantly reduce the computational cost and gain the numerical accuracy. We then developed the method combined with the electronic structure calculations to obtain the accurate interatomic potential on the fly. We present an application of our ab initio instanton method to the ammonia umbrella flip motion. PMID:25027993

Kawatsu, Tsutomu; Miura, Shinichi

2014-07-14

194

Improvement of phase diversity algorithm for non-common path calibration in extreme AO context  

Microsoft Academic Search

Exoplanet direct imaging with a ground-based telescope needs a very high performance adaptive optics (AO) system, so-called eXtreme AO (XAO), a coronagraph device, and a smart imaging process. One limitation of AO system in operation remains the Non Common Path Aberrations (NCPA). To achieve the ultimate XAO performance, these aberrations have to be measured with a dedicated wavefront sensor placed

Clélia Robert; Thierry Fusco; Jean-François Sauvage; Laurent Mugnier

2008-01-01

195

Dijkstra's Algorithm with Fibonacci Heaps: An Executable Description in CHR  

Microsoft Academic Search

We construct a readable, compact and ecien t implementation of Dijkstra's shortest path algorithm and Fibonacci heaps using Constraint Handling Rules (CHR), which is increasingly used as a high-level rule-based general-purpose programming language. We measure its performance in dieren t CHR systems, investigating both the theoretical asymp- totic complexity and the constant factors realized in practice. Constraint Handling Rules (CHR)

Jon Sneyers; Tom Schrijvers; Bart Demoen

2006-01-01

196

Securing a mobile adhoc network from routing attacks through the application of genetic algorithm  

E-print Network

In recent years, the static shortest path (SP) problem has been well addressed using intelligent optimization techniques, e.g., artificial neural networks, genetic algorithms (GAs), particle swarm optimization, etc. However, with the advancement in wireless communications, more and more mobile wireless networks appear, e.g., mobile networks [mobile ad hoc networks (MANETs)], wireless sensor networks, etc. One of the most important characteristics in mobile wireless networks is the topology dynamics, i.e., the network topology changes over time due to energy conservation or node mobility. Therefore, the SP routing problem in MANETs turns out to be a dynamic optimization problem. GA's are able to find, if not the shortest, at least an optimal path between source and destination in mobile ad-hoc network nodes. And we obtain the alternative path or backup path to avoid reroute discovery in the case of link failure or node failure.

Nikhil, Kumar; Sharma, Pankaj

2012-01-01

197

An Improved Algorithm for the Solution of the Entire Regulation Path ...  

E-print Network

process in the form of a linear program, an initialization routine that deals with ... heuristics-based routine and update formula to speed up the algorithm. .... this happens when one or more of the following changes to the index sets take place:

2009-04-22

198

An Energy-Efficient Algorithm For Conflict-Free AGV Routing On A Linear Path Layout  

E-print Network

for short) and the car park are distributed on the side of one lane. The algorithms proposed in [6-7] can of AGVs. We present a new linear layout in which the mirror virtual stations of [6] are now actual

Zeng, Jianyang "Michael"

199

An EnergyEfficient Algorithm For ConflictFree AGV Routing On A Linear Path Layout  

E-print Network

for short) and the car park are distributed on the side of one lane. The algorithms proposed in [6­7] can of AGVs. We present a new linear layout in which the mirror virtual stations of [6] are now actual

Zeng, Jianyang "Michael"

200

Research and implementation of group animation path planning based on Firefly algorithm  

Microsoft Academic Search

Based on the standard FA easily traps in a local optimum, this paper presents a method that the current particle choose the one in its visual field which has the best fitness as the global best particle. The experiment shows the advantaged algorithm has a better global search ability. The paper uses the advantaged FA into the group animation, the

Xu Shijie; Jiang Shuming; Zhang Jianfeng; Wei Zhiqiang; Li Jian; Wang Shuai

2012-01-01

201

Information Spread of Emergency Events: Path Searching on Social Networks  

PubMed Central

Emergency has attracted global attentions of government and the public, and it will easily trigger a series of serious social problems if it is not supervised effectively in the dissemination process. In the Internet world, people communicate with each other and form various virtual communities based on social networks, which lead to a complex and fast information spread pattern of emergency events. This paper collects Internet data based on data acquisition and topic detection technology, analyzes the process of information spread on social networks, describes the diffusions and impacts of that information from the perspective of random graph, and finally seeks the key paths through an improved IBF algorithm. Application cases have shown that this algorithm can search the shortest spread paths efficiently, which may help us to guide and control the information dissemination of emergency events on early warning. PMID:24600323

Hu, Hongzhi; Wu, Tunan

2014-01-01

202

Optimization of the mean radius flow path of a multi-stage steam turbine with evolution algorithms  

NASA Astrophysics Data System (ADS)

A prototype model of the mean radius flow path of a four-stage, high speed 1 MWe axial steam turbine was optimized by using evolution algorithms, DE (differential evolution) algorithm in this case. Also the cost-benefits of the optimization were inspected. The optimization was successfully performed but the accuracy of the optimization was slightly less than hoped when compared to the control modeling executed with the CFD (computational fluid dynamics). The mentioned inaccuracy could have been hardly avoided because of problems with an initial presumption involving semi-empiric calculations and of the uncertainty concerning the absolute areas of qualification of the functions. This kind of algebraic modeling was essential for the success of the optimization because e.g. CFD-calculation could not have been done on each step of the optimization. During the optimization some problems occurred with the adequacy of the computer capacity and with finding a suitable solution that would keep the algorithms within mathematically allowable boundaries but would not restrict the progress of the optimization too much. The rest of the problems were due to the novelty of the application and problems with preciseness when handling the areas of qualification of the functions. Although the accuracy of the optimization results was not exactly in accordance with the objective, they did have a favorable effect on the designing of the turbine. The optimization executed with the help of the DE-algorithm got at least about 3.5 % more power out of the turbine which means about 150 000 € cost-benefit per turbine in the form of additional electricity capacity.

Huttunen, Jukka; Larjola, Jaakko; Turunen-Saaresti, Teemu; Backman, Jari

2011-08-01

203

Methodology for Augmenting Existing Paths with Additional Parallel Transects  

SciTech Connect

Visual Sample Plan (VSP) is sample planning software that is used, among other purposes, to plan transect sampling paths to detect areas that were potentially used for munition training. This module was developed for application on a large site where existing roads and trails were to be used as primary sampling paths. Gap areas between these primary paths needed to found and covered with parallel transect paths. These gap areas represent areas on the site that are more than a specified distance from a primary path. These added parallel paths needed to optionally be connected together into a single path—the shortest path possible. The paths also needed to optionally be attached to existing primary paths, again with the shortest possible path. Finally, the process must be repeatable and predictable so that the same inputs (primary paths, specified distance, and path options) will result in the same set of new paths every time. This methodology was developed to meet those specifications.

Wilson, John E.

2013-09-30

204

Generation of an atlas for commodity chemical production in Escherichia coli and a novel pathway prediction algorithm, GEM-Path.  

PubMed

The production of 75% of the current drug molecules and 35% of all chemicals could be achieved through bioprocessing (Arundel and Sawaya, 2009). To accelerate the transition from a petroleum-based chemical industry to a sustainable bio-based industry, systems metabolic engineering has emerged to computationally design metabolic pathways for chemical production. Although algorithms able to provide specific metabolic interventions and heterologous production pathways are available, a systematic analysis for all possible production routes to commodity chemicals in Escherichia coli is lacking. Furthermore, a pathway prediction algorithm that combines direct integration of genome-scale models at each step of the search to reduce the search space does not exist. Previous work (Feist et al., 2010) performed a model-driven evaluation of the growth-coupled production potential for E. coli to produce multiple native compounds from different feedstocks. In this study, we extended this analysis for non-native compounds by using an integrated approach through heterologous pathway integration and growth-coupled metabolite production design. In addition to integration with genome-scale model integration, the GEM-Path algorithm developed in this work also contains a novel approach to address reaction promiscuity. In total, 245 unique synthetic pathways for 20 large volume compounds were predicted. Host metabolism with these synthetic pathways was then analyzed for feasible growth-coupled production and designs could be identified for 1271 of the 6615 conditions evaluated. This study characterizes the potential for E. coli to produce commodity chemicals, and outlines a generic strain design workflow to design production strains. PMID:25080239

Campodonico, Miguel A; Andrews, Barbara A; Asenjo, Juan A; Palsson, Bernhard O; Feist, Adam M

2014-09-01

205

Adaptive path A priori path  

E-print Network

of being the shortest: Sigal et al. (1980) Least possible travel time: Miller-hooks & Mahmassani (1998) Maximize the probability of being the shortest: Sigal et al. (1980) Least possible travel time: Miller

Illinois at Chicago, University of

206

Path planning for UAVs  

Microsoft Academic Search

In this paper, a two step path-planning algorithm for UAVs is proposed. The algorithm generates a stealthy path through a set of enemy radar sites of known location, and provides an intuitive way to trade-off stealth versus path length. In the first step, a suboptimal rough-cut path is generated through the radar sites by constructing and searching a graph based

S. A. Bortoff; E. Hartford

2000-01-01

207

Real-Time Disk Scheduling Based on Urgent Group and Shortest Seek Time First  

Microsoft Academic Search

Real-time applications dealing with a large amount of data often require timely service of disk I\\/O requests. This paper presents a new real-time disk scheduling method called Urgent Group and Shortest Seek Time First(UG-SSTF) for soft real-time systems. According to this algorithm, the urgent group is formed by identifying urgent requests awaiting the disk service in a queue, among which

Kitae Hwang; Heonshik Shin

1993-01-01

208

Extremal paths on a random Cayley tree  

Microsoft Academic Search

We investigate the statistics of extremal path(s) (both the shortest and the longest) from the root to the bottom of a Cayley tree. The lengths of the edges are assumed to be independent identically distributed random variables drawn from a distribution rho(l). Besides, the number of branches from any node is also random. Exact results are derived for arbitrary distribution

Satya N. Majumdar; P. L. Krapivsky

2000-01-01

209

Neighborhood-privacy protected shortest distance computing in cloud  

Microsoft Academic Search

With the advent of cloud computing, it becomes desirable to utilize cloud computing to efficiently process complex operations on large graphs without compromising their sensitive information. This paper studies shortest distance computing in the cloud, which aims at the following goals: i) preventing outsourced graphs from neighborhood attack, ii) preserving shortest distances in outsourced graphs, iii) minimizing overhead on the

Jun Gao; Jeffrey Xu Yu; Ruoming Jin; Jiashuai Zhou; Tengjiao Wang; Dongqing Yang

2011-01-01

210

Flight tests of three-dimensional path-redefinition algorithms for transition from Radio Navigation (RNAV) to Microwave Landing System (MLS) navigation when flying an aircraft on autopilot  

NASA Technical Reports Server (NTRS)

This report contains results of flight tests for three path update algorithms designed to provide smooth transition for an aircraft guidance system from DME, VORTAC, and barometric navaids to the more precise MLS by modifying the desired 3-D flight path. The first algorithm, called Zero Cross Track, eliminates the discontinuity in cross-track and altitude error at transition by designating the first valid MLS aircraft position as the desired first waypoint, while retaining all subsequent waypoints. The discontinuity in track angle is left unaltered. The second, called Tangent Path, also eliminates the discontinuity in cross-track and altitude errors and chooses a new desired heading to be tangent to the next oncoming circular arc turn. The third, called Continued Track, eliminates the discontinuity in cross-track, altitude, and track angle errors by accepting the current MLS position and track angle as the desired ones and recomputes the location of the next waypoint. The flight tests were conducted on the Transportation Systems Research Vehicle, a small twin-jet transport aircraft modified for research under the Advanced Transport Operating Systems program at Langley Research Center. The flight tests showed that the algorithms provided a smooth transition to MLS.

Hueschen, Richard M.

1988-01-01

211

The Dwarf Novae of Shortest Period  

E-print Network

We present observations of the dwarf novae GW Lib, V844 Her, and DI UMa. Radial velocities of H-alph yield orbital periods of 0.05332 +- 0.00002 d (= 76.78 m) for GW Lib and and 0.054643 +- 0.000007 d (= 78.69 m) for V844 Her. Recently, the orbital period of DI UMa was found to be only 0.054564 +- 0.000002 d (= 78.57 m) by Fried et al. (1999), so these are the three shortest orbital periods among dwarf novae with normal-abundance secondaries. GW Lib has attracted attention as a cataclysmic binary showing apparent ZZ Ceti-type pulsations of the white dwarf primary. Its spectrum shows sharp Balmer emission flanked by strong, broad Balmer absorption, indicating a dominant contribution by white-dwarf light. Analysis of the Balmer absorption profiles is complicated by the unknown residual accretion luminosity and lack of coverage of the high Balmer lines. Our best-fit model atmospheres are marginally hotter than the ZZ Ceti instability strip, in rough agreement with recent ultraviolet results from HST. The spectrum and outburst behavior of GW Lib make it a near twin of WZ Sge, and we estimate it to have a quiescent V absolute magnitude 12. Comparison with archival data reveals proper motion of 65 +- 12 mas/yr. The mean spectrum of V844 Her is typical of SU UMa dwarf novae. We detected superhumps in the 1997 May superoutburst with superhump period = 0.05597 +- 0.00005 d. The spectrum of DI UMa appears normal for a dwarf nova near minimum light. These three dwarf novae have nearly identical short periods but completely dissimilar outburst characteristics. We discuss possible implications.

J. R. Thorstensen; J. O. Patterson; J. Kemp; S. Vennes

2002-06-25

212

Minimum distance collision-free path planning for industrial robots with a prismatic joint  

NASA Astrophysics Data System (ADS)

A collision-free path is a path which an industrial robot can physically take while traveling from one location to another in an environment containing obstacles. Usually the obstacles are expanded to compensate for the body width of the robot. For robots with a prismatic joint, which allows only a translational motion along its axis, additional problems created by the long boom are handled by means of pseudoobstacles which are generated by real obstacle's edges and faces. The environment is then modified by the inclusion of pseudoobstacles which contribute to the forbidden regions. This process allows the robot itself again to be represented by a point specifying the location of its end effector in space. An algorithm for determining the shortest distance collision-free path given a sequence of edges to be traversed has been developed for the case of stationary obstacles.

Luh, J. U. S.; Campbell, C. E., Jr.

1984-08-01

213

Adaptive DNA Computing Algorithm by Using PCR and Restriction Enzyme  

NASA Astrophysics Data System (ADS)

In this paper, we introduce an adaptive DNA computing algorithm by using polymerase chain reaction (PCR) and restriction enzyme. The adaptive algorithm is designed based on Adleman-Lipton paradigm[3] of DNA computing. In this work, however, unlike the Adleman- Lipton architecture a cutting operation has been introduced to the algorithm and the mechanism in which the molecules used by computation were feedback to the next cycle devised. Moreover, the amplification by PCR is performed in the molecule used by feedback and the difference concentration arisen in the base sequence can be used again. By this operation the molecules which serve as a solution candidate can be reduced down and the optimal solution is carried out in the shortest path problem. The validity of the proposed adaptive algorithm is considered with the logical simulation and finally we go on to propose applying adaptive algorithm to the chemical experiment which used the actual DNA molecules for solving an optimal network problem.

Kon, Yuji; Yabe, Kaoru; Rajaee, Nordiana; Ono, Osamu

214

A reconfigurable multiprocessor IC for rapid prototyping of algorithmic-specific high-speed DSP data paths  

Microsoft Academic Search

A field-programmable multiprocessor integrated circuit, PADDI (programmable arithmetic devices for high-speed digital signal processing), has been designed for the rapid prototyping of high-speed data paths typical to real-time digital signal processing applications. The processor architecture addresses the key requirements of these data paths: (a) fast, concurrently operating, multiple arithmetic units, (b) conflict-free data routing, (c) moderate hardware multiplexing (of the

Dev C. Chen; Jan M. Rabaey

1992-01-01

215

The Trade-offs of Multicast Trees and Algorithms  

Microsoft Academic Search

Multicast trees can be shared across sources (shared trees) or may be source-specific (shortest pathtrees). Inspired by recent interests in using shared trees for interdomain multicasting, we investigate thetrade-offs among shared tree types and source specific shortest path trees, by comparing performanceover both individual multicast group and the whole network. The performance is evaluated in termsof path length, link cost,

Liming Wei; Deborah Estrin

1995-01-01

216

Operator calculus in generalized zeon algebras: theory and application to multi-constrained path  

E-print Network

Operator calculus in generalized zeon algebras: theory and application to multi-constrained path single-source Pareto paths remaining. 2 Theory: Generalized zeon algebras Zeon algebras are commutative-constrained path problems is described. keywords: shortest paths, message routing, operator calculus, semigroup

Paris-Sud XI, Université de

217

Operator calculus in generalized zeon algebras: theory and application to multi-constrained path  

E-print Network

Operator calculus in generalized zeon algebras: theory and application to multi-constrained path-constrained path problems is described. keywords: shortest paths, message routing, operator calculus, semigroup about self-avoiding structures (paths, cycles, trails, etc.) in the graph are revealed by computing

Schott, René - Institut de Mathématiques �lie Cartan, Université Henri Poincaré

218

Computing the length of the shortest telomere in the nucleus.  

PubMed

The telomere length can either be shortened or elongated by an enzyme called telomerase after each cell division. Interestingly, the shortest telomere is involved in controlling the ability of a cell to divide. Yet, its dynamics remains elusive. We present here a stochastic approach where we model this dynamics using a Markov jump process. We solve the forward Fokker-Planck equation to obtain the steady state distribution and the statistical moments of telomere lengths. We focus specifically on the shortest one and we estimate its length difference with the second shortest telomere. After extracting key parameters such as elongation and shortening dynamics from experimental data, we compute the length of telomeres in yeast and obtain as a possible prediction the minimum concentration of telomerase required to ensure a proper cell division. PMID:24329474

Duc, K Dao; Holcman, D

2013-11-27

219

The formulation of quantum statistical mechanics based on the Feynman path centroid density. IV. Algorithms for centroid molecular dynamics  

E-print Network

to calculate dynamical time correlation functions for general many-body quantum systems. Approaches based of the aforementioned research is an approximate method for computing quantum dynamical time correlation functions. Algorithms for centroid molecular dynamics Jianshu Cao and Gregory A. Voth Department of Chemistry

Cao, Jianshu

220

Extremal paths on a random Cayley tree  

Microsoft Academic Search

We investigate the statistics of extremal path(s) (both the shortest and the\\u000alongest) from the root to the bottom of a Cayley tree. The lengths of the edges\\u000aare assumed to be independent identically distributed random variables drawn\\u000afrom a distribution \\\\rho(l). Besides, the number of branches from any node is\\u000aalso random. Exact results are derived for arbitrary distribution

Satya N. Majumdar; P. L. Krapivsky

2000-01-01

221

Structural phase transition path-following and stable phase scouting through a coupled DFT-BFB algorithm  

NASA Astrophysics Data System (ADS)

Understanding structural phase transformations in solid-state materials is of great scientific and technological interest. These phenomena are governed by electronic degrees of freedom and thus, in principle, can be described with quantum mechanics alone. However, any realistic material has multiple length and time scales and access to these scales is a formidable task to deal with using quantum mechanics. On the contrary, for the continuum regime, empirical constitutive models have severe difficulties capturing material properties that ultimately arise from (sub-)atomic effects, and further, must be fit to experimental data. Thus, in order to obtain a predictive, complete understanding of a material subjected to different external loading parameters, the two regimes- atomistic and continuum-must be coupled. The present work formulates a coupled quantum-continuum model for scanning phase-space in order to determine the material's stable structure at any given pressure. This is accomplished by coupling quantumbased Density Functional Theory (DFT) calculations (employing periodic boundary conditions) with Branch- Following and Bifurcation (BFB) techniques. BFB is capable of mapping out equilibrium paths (stable and unstable) as a function of the applied pressure and ultimately creates "bifurcation maps" that identify the material's stable structures and connections between them, including: soft deformation directions, transition states, transformation mechanisms, etc.. This study shows that the coupled DFT-BFB methodology is capable of efficiently mapping out equilibrium paths. This includes the identification of stable and unstable pressure ranges and the identification of the deformation modes that first become soft-resulting in the structure's loss of stability. Example computations are provided for iron and silicon. The results obtained so far indicate that the new DFT-BFB methodology has the potential to provide a significant new insight on the mechanisms that drive structural phase transitions in a wide range of technologically important materials.

Ghosh, Dipta Bhanu; Cococcioni, Matteo; Elliott, Ryan S.

2010-04-01

222

Estimating 13.8-GHz path-integrated attenuation from 10.7-GHz brightness temperatures for the TRMM combined PR-TMI precipitation algorithm  

SciTech Connect

This study presents research in support of the design and implementation of a combined radar-radiometer algorithm to be used for precipitation retrieval during the Tropical Rainfall Measuring Mission (TRMM). The combined algorithm approach is expected to overcome various difficulties that arise with a radar-only approach, particularly related to estimates of path-integrated attenuation (PIA)along the TRMM radar beam. A technique is described for estimating PIA at the 13.8-GHz frequency of the TRMM precipitation radar (PR) from 10.7-GHz brightness temperature T{sub B} measurements obtained from the TRMM microwave imager. Through the use of variational or probabilistic techniques, the independent PIA calculations provide a means to adjust for errors that accumulate in estimates of range-dependent rain rates at progressively increasing range positions from radar reflectivity vectors. The accepted radar approach for obtaining PIA from ocean-viewing radar reflectivity measurements is called the surface reference technique, a scheme based on the difference in ocean surface cross sections between cloud-free and raining radar pixels. This technique has encountered problems, which are discussed and analyzed with the aid of coordinated aircraft radar (Airborne Rain Mapping Radar) and radiometer (Advanced Microwave Precipitation Radiometer) measurements obtained during the west Pacific Tropical Ocean Global Atmosphere Coupled Ocean-Atmosphere Response Experiment in 1993. 97 refs., 12 figs., 5 tabs.

Smith, E.A.; Farrar, M.R.; Xiang, X. [Florida State Univ., Tallahassee, FL (United States)] [Florida State Univ., Tallahassee, FL (United States); Turk, F.J. [Naval Research Lab., Monterey, CA (United States)] [Naval Research Lab., Monterey, CA (United States); Mugnai, A. [Instituto di Fisica dell`Atmosfera-CNR, Frascati (Italy)] [Instituto di Fisica dell`Atmosfera-CNR, Frascati (Italy)

1997-04-01

223

?minimax: An Optimally Randomized MINIMAX Algorithm.  

PubMed

This paper proposes a simple extension of the celebrated MINIMAX algorithm used in zero-sum two-player games, called ?minimax. The ?minimax algorithm allows controlling the strength of an artificial rival by randomizing its strategy in an optimal way. In particular, the randomized shortest-path framework is applied for biasing the artificial intelligence (AI) adversary toward worse or better solutions, therefore controlling its strength. In other words, our model aims at introducing/implementing bounded rationality to the MINIMAX algorithm. This framework takes into account all possible strategies by computing an optimal tradeoff between exploration (quantified by the entropy spread in the tree) and exploitation (quantified by the expected cost to an end game) of the game tree. As opposed to other tree-exploration techniques, this new algorithm considers complete paths of a tree (strategies) where a given entropy is spread. The optimal randomized strategy is efficiently computed by means of a simple recurrence relation while keeping the same complexity as the original MINIMAX. As a result, the ?minimax implements a nondeterministic strength-adapted AI opponent for board games in a principled way, thus avoiding the assumption of complete rationality. Simulations on two common games show that ?minimax behaves as expected. PMID:22893439

García Díez, Silvia; Laforge, Jérôme; Saerens, Marco

2012-08-01

224

Mobile transporter path planning  

NASA Technical Reports Server (NTRS)

The use of a genetic algorithm (GA) for solving the mobile transporter path planning problem is investigated. The mobile transporter is a traveling robotic vehicle proposed for the space station which must be able to reach any point of the structure autonomously. Elements of the genetic algorithm are explored in both a theoretical and experimental sense. Specifically, double crossover, greedy crossover, and tournament selection techniques are examined. Additionally, the use of local optimization techniques working in concert with the GA are also explored. Recent developments in genetic algorithm theory are shown to be particularly effective in a path planning problem domain, though problem areas can be cited which require more research.

Baffes, Paul; Wang, Lui

1990-01-01

225

Nonoptimal Component Placement, but Short Processing Paths, due to Long-Distance Projections in Neural Systems  

PubMed Central

It has been suggested that neural systems across several scales of organization show optimal component placement, in which any spatial rearrangement of the components would lead to an increase of total wiring. Using extensive connectivity datasets for diverse neural networks combined with spatial coordinates for network nodes, we applied an optimization algorithm to the network layouts, in order to search for wire-saving component rearrangements. We found that optimized component rearrangements could substantially reduce total wiring length in all tested neural networks. Specifically, total wiring among 95 primate (Macaque) cortical areas could be decreased by 32%, and wiring of neuronal networks in the nematode Caenorhabditis elegans could be reduced by 48% on the global level, and by 49% for neurons within frontal ganglia. Wiring length reductions were possible due to the existence of long-distance projections in neural networks. We explored the role of these projections by comparing the original networks with minimally rewired networks of the same size, which possessed only the shortest possible connections. In the minimally rewired networks, the number of processing steps along the shortest paths between components was significantly increased compared to the original networks. Additional benchmark comparisons also indicated that neural networks are more similar to network layouts that minimize the length of processing paths, rather than wiring length. These findings suggest that neural systems are not exclusively optimized for minimal global wiring, but for a variety of factors including the minimization of processing steps. PMID:16848638

Kaiser, Marcus; Hilgetag, Claus C

2006-01-01

226

Optimal paths for a car that goes both forwards and backwards  

Microsoft Academic Search

The path taken by a car with a given minimum turning radius has a lower bound on its radius of curvature at each point, but the path has cusps if the car shifts into or out of reverse gear. What is the shortest such path a car can travel between two points if its starting and ending directions are specified?

J. A. Reeds; L. A. Shepp

1990-01-01

227

Shortest Path Stochastic Control for Hybrid Electric Vehicles , J.W. Grizzle2  

E-print Network

, its power management system must be charge sustaining over the drive cycle, meaning that the battery of the test. During the test cycle, the power management system is free to vary the battery SOC so problem associated with the design of the power management system because it allows deviations of battery

Grizzle, Jessy W.

228

Random Generation of Shortest Path Test Networks Dennis J. Adams-Smith Douglas R. Shier  

E-print Network

, 200 trials Method Mean Deg(r) STD Deg(r) Mean D2(G) STD D2(G) Mean diam Uniform 2.835 1.578 6.855 4 edges, 200 trials Method Mean Deg(r) STD Deg(r) Mean D2(G) STD D2(G) Mean diam Uniform 3.050 1.674 8 nodes, 350 edges, 200 trials Method Mean Deg(r) STD Deg(r) Mean D2(G) STD D2(G) Mean diam Uniform 3

Shier, Douglas R.

229

Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions \\Lambda  

E-print Network

problem and maximum area contained triangle problem have applications to robotics and stock­cutting. The results of this paper will appear also in [33]. Key Words and Phrases: robotics, stock­cutting

Souvaine, Diane

230

Performance Evaluation 48 (2002) 201223 On open shortest path first related network optimisation problems  

E-print Network

a Department of Communication Systems, Lund Institute of Technology, Lund, Sweden b Institute of Telecommunications, Warsaw University of Technology, Nowowiejska 15/19, 00-665 Warszawa, Poland c Ericsson Research of Technology, Nowowiejska 15/19, 00665 Warszawa, Poland. Tel.: +48-22-825-98-20; fax: +48-22-660-7564. E

Jüttner, Alpár

231

Algorithmic Strategies in Combinatorial Chemistry  

SciTech Connect

Combinatorial Chemistry is a powerful new technology in drug design and molecular recognition. It is a wet-laboratory methodology aimed at ``massively parallel'' screening of chemical compounds for the discovery of compounds that have a certain biological activity. The power of the method comes from the interaction between experimental design and computational modeling. Principles of ``rational'' drug design are used in the construction of combinatorial libraries to speed up the discovery of lead compounds with the desired biological activity. This paper presents algorithms, software development and computational complexity analysis for problems arising in the design of combinatorial libraries for drug discovery. The authors provide exact polynomial time algorithms and intractability results for several Inverse Problems-formulated as (chemical) graph reconstruction problems-related to the design of combinatorial libraries. These are the first rigorous algorithmic results in the literature. The authors also present results provided by the combinatorial chemistry software package OCOTILLO for combinatorial peptide design using real data libraries. The package provides exact solutions for general inverse problems based on shortest-path topological indices. The results are superior both in accuracy and computing time to the best software reports published in the literature. For 5-peptoid design, the computation is rigorously reduced to an exhaustive search of about 2% of the search space; the exact solutions are found in a few minutes.

GOLDMAN,DEBORAH; ISTRAIL,SORIN; LANCIA,GIUSEPPE; PICCOLBONI,ANTONIO; WALENZ,BRIAN

2000-08-01

232

Averaging Tens to Hundreds of Icosahedral Particle Images to Resolve Protein Secondary Structure Elements using a Multi-Path Simulated Annealing Optimization Algorithm  

PubMed Central

Accurately determining a cryoEM particle’s alignment parameters is crucial to high resolution single particle 3-D reconstruction. We developed Multi-Path Simulated Annealing, a Monte Carlo type of optimization algorithm, for globally aligning the center and orientation of a particle simultaneously. A consistency criterion was developed to ensure the alignment parameters are correct and to remove some bad particles from a large pool of images of icosahedral particles. Without using any a priori model, this procedure is able to reconstruct a structure from a random initial model. Combining the procedure above with a new empirical double threshold particle selection method, we are able to pick tens of best quality particles to reconstruct a subnanometer resolution map from scratch. Using the best 62 particles of rice dwarf virus, the reconstruction reached 9.6Å resolution at which 4 helices of the P3A subunit of RDV are resolved. Furthermore, with the 284 best particles, the reconstruction is improved to 7.9Å resolution, and 21 of 22 helices and 6 of 7 beta sheets are resolved. PMID:17698370

Liu, Xiangan; Jiang, Wen; Jakana, Joanita; Chiu, Wah

2007-01-01

233

Dispersion of nonlinear group velocity determines shortest envelope solitons  

SciTech Connect

We demonstrate that a generalized nonlinear Schroedinger equation (NSE), which includes dispersion of the intensity-dependent group velocity, allows for exact solitary solutions. In the limit of a long pulse duration, these solutions naturally converge to a fundamental soliton of the standard NSE. In particular, the peak pulse intensity times squared pulse duration is constant. For short durations, this scaling gets violated and a cusp of the envelope may be formed. The limiting singular solution determines then the shortest possible pulse duration and the largest possible peak power. We obtain these parameters explicitly in terms of the parameters of the generalized NSE.

Amiranashvili, Sh.; Bandelow, U.; Akhmediev, N. [Weierstrass Institute for Applied Analysis and Stochastics, Mohrenstrasse 39, D-10117 Berlin (Germany); Optical Sciences Group, Research School of Physics and Engineering, Institute of Advanced Studies, Australian National University, Canberra ACT 0200 (Australia)

2011-10-15

234

A Flexible Reservation Algorithm for Advance Network Provisioning  

SciTech Connect

Many scientific applications need support from a communication infrastructure that provides predictable performance, which requires effective algorithms for bandwidth reservations. Network reservation systems such as ESnet's OSCARS, establish guaranteed bandwidth of secure virtual circuits for a certain bandwidth and length of time. However, users currently cannot inquire about bandwidth availability, nor have alternative suggestions when reservation requests fail. In general, the number of reservation options is exponential with the number of nodes n, and current reservation commitments. We present a novel approach for path finding in time-dependent networks taking advantage of user-provided parameters of total volume and time constraints, which produces options for earliest completion and shortest duration. The theoretical complexity is only O(n2r2) in the worst-case, where r is the number of reservations in the desired time interval. We have implemented our algorithm and developed efficient methodologies for incorporation into network reservation frameworks. Performance measurements confirm the theoretical predictions.

Balman, Mehmet; Chaniotakis, Evangelos; Shoshani, Arie; Sim, Alex

2010-04-12

235

Sampling diffusive transition paths  

SciTech Connect

We address the problem of sampling double-ended diffusive paths. The ensemble of paths is expressed using a symmetric version of the Onsager-Machlup formula, which only requires evaluation of the force field and which, upon direct time discretization, gives rise to a symmetric integrator that is accurate to second order. Efficiently sampling this ensemble requires avoiding the well-known stiffness problem associated with sampling infinitesimal Brownian increments of the path, as well as a different type of stiffness associated with sampling the coarse features of long paths. The fine-features sampling stiffness is eliminated with the use of the fast sampling algorithm (FSA), and the coarse-feature sampling stiffness is avoided by introducing the sliding and sampling (S&S) algorithm. A key feature of the S&S algorithm is that it enables massively parallel computers to sample diffusive trajectories that are long in time. We use the algorithm to sample the transition path ensemble for the structural interconversion of the 38-atom Lennard-Jones cluster at low temperature.

F. Miller III, Thomas; Predescu, Cristian

2006-10-12

236

The Trade-offs of Multicast Trees and Algorithms  

Microsoft Academic Search

Multicast trees can be shared across sources (shared trees)or may be source-specific (shortest path trees). Inspired byrecent interests in using shared trees for interdomain multicasting,we investigate the trade-offs among shared treetypes and source specific shortest path trees, by comparingperformance over both individual multicast group and thewhole network. The performance is evaluated in terms ofpath length, link cost, and traffic concentration.We

Deborah Estrin; Liming Wei

1994-01-01

237

Path-Based, Randomized, Oblivious, Minimal Routing  

E-print Network

Path-based, Randomized, Oblivious, Minimal routing (PROM) is a family of oblivious, minimal, path-diverse routing algorithms especially suitable for Network-on-Chip applications with n x n mesh geometry. Rather than choosing ...

Cho, Myong Hyon

2009-01-01

238

Measurement of the world's shortest X-ray pulses  

NASA Astrophysics Data System (ADS)

One of the essential characteristics of LCLS and other FELs that are currently in operation or still under development is their ultrashort pulse duration, further enhanced just recently by novel schemes of electron bunch compression, which opens up unprecedented opportunities for the detailed investigation of reaction dynamics. However, to date there is no measuring device or concept which is able to determine precisely the pulse duration of the generated X-ray pulses. By overlapping the FEL with a synchronized optical laser in a gas target and measuring the energy of the IR laser dressed photoelectrons ('streaking spectroscopy') we were able to determine the pulse duration of the shortest FEL pulses available at LCLS to be not more than 4 fs. In addition, an analysis of the pulse substructure yields an estimation for the length of the underlying single-spikes in the order of 600 as.

Helml, Wolfram; Maier, Andreas R.; Schweinberger, Wolfgang; Gagnon, Justin; Cavalieri, Adrian L.; Grguras, Ivanka; Radcliffe, Paul; Tschentscher, Thomas; Meyer, Michael; Doumy, Gilles; Roedig, Chris; Bozek, John D.; Coffee, Ryan; Costello, John; Duesterer, Stefan; Kienberger, Reinhard

2011-06-01

239

Tornado Paths  

NSDL National Science Digital Library

This website catalogs all the tornado paths in the United States since 1950. The tornado path data is overlaid onto a Google Maps base for easy browsing and manipulation of the map view. Clicking on individual tornados provides the user with information such as its Fujita rating, the amount of damage caused by the tornado, the size of the path that the tornado made, and the length of time the tornado was on the ground.

Samson, Perry; Michigan, University O.

240

All-Optical Monitoring Path Computation Using Lower Bounds of Required Number of Paths  

NASA Astrophysics Data System (ADS)

To reduce the cost of fault management in all-optical networks, it is a promising approach to detect the degradation of optical signal quality solely at the terminal points of all-optical monitoring paths. The all-optical monitoring paths must be routed so that all single-link failures can be localized using route information of monitoring paths where signal quality degradation is detected. However, route computation for the all-optical monitoring paths that satisfy the above condition is time consuming. This paper proposes a procedure for deriving the lower bounds of the required number of monitoring paths to localize all single-link failures, and proposes an efficient monitoring path computation method based on the derived lower bounds. The proposed method repeats the route computation for the monitoring paths until feasible routes can be found, while the assumed number of monitoring paths increases, starting from the lower bounds. With the proposed method, the minimum number of monitoring paths with the overall shortest routes can be obtained quickly by solving several small-scale integer linear programming problems when the possible terminal nodes of monitoring paths are arbitrarily given. Thus, the proposed method can minimize the required number of monitors for detecting the degradation of signal quality and the total overhead traffic volume transferred through the monitoring paths.

Ogino, Nagao; Nakamura, Hajime

241

Design and Evaluation of a Dynamic Programming Flight Routing Algorithm Using the Convective Weather Avoidance Model  

NASA Technical Reports Server (NTRS)

The optimization of traffic flows in congested airspace with varying convective weather is a challenging problem. One approach is to generate shortest routes between origins and destinations while meeting airspace capacity constraint in the presence of uncertainties, such as weather and airspace demand. This study focuses on development of an optimal flight path search algorithm that optimizes national airspace system throughput and efficiency in the presence of uncertainties. The algorithm is based on dynamic programming and utilizes the predicted probability that an aircraft will deviate around convective weather. It is shown that the running time of the algorithm increases linearly with the total number of links between all stages. The optimal routes minimize a combination of fuel cost and expected cost of route deviation due to convective weather. They are considered as alternatives to the set of coded departure routes which are predefined by FAA to reroute pre-departure flights around weather or air traffic constraints. A formula, which calculates predicted probability of deviation from a given flight path, is also derived. The predicted probability of deviation is calculated for all path candidates. Routes with the best probability are selected as optimal. The predicted probability of deviation serves as a computable measure of reliability in pre-departure rerouting. The algorithm can also be extended to automatically adjust its design parameters to satisfy the desired level of reliability.

Ng, Hok K.; Grabbe, Shon; Mukherjee, Avijit

2010-01-01

242

Pokemon Cards and the Shortest Common Superstring Mark Stamp Austin E Stamp  

E-print Network

Pok´emon Cards and the Shortest Common Superstring Mark Stamp Austin E Stamp June 12, 2003 Abstract Evidence is presented that certain sequences of Pok´emon cards are determined by selecting consecutive (SCS), i.e., the shortest string that contains each of the Pok´emon card sequences as a consecutive

Stamp, Mark

243

Path planning by optimal-path-map construction for homogeneous-cost two-dimensional regions  

Microsoft Academic Search

Algorithms to construct optimal-path maps for single isolated homogeneous-cost convex-polygonal regions are discussed. Assuming the ability to construct optimal paths for a certain set of key points, a complete analysis is given of one of the four possible single-region situations, showing how to partition the map into regions of similar path behavior. An algorithm is then proposed for constructing optimal-path

Robert S. Alexander; Neil C. Rowe

1990-01-01

244

Effectiveness of the statistical potential in the description of fermions in a worm-algorithm path-integral Monte Carlo simulation of 3He atoms placed on a 4He layer adsorbed on graphite  

NASA Astrophysics Data System (ADS)

We demonstrate the effectiveness of a statistical potential (SP) in the description of fermions in a worm-algorithm path-integral Monte Carlo simulation of a few 3He atoms floating on a 4He layer adsorbed on graphite. The SP in this work yields successful results, as manifested by the clusterization of 3He, and by the observation that the 3He atoms float on the surface of 4He. We display the positions of the particles in 3D coordinate space, which reveal clusterization of the 3He component. The correlation functions are also presented, which give further evidence for the clusterization.

Ghassib, Humam B.; Sakhel, Asaad R.; Obeidat, Omar; Al-Oqali, Amer; Sakhel, Roger R.

2012-01-01

245

Effectiveness of the statistical potential in the description of fermions in a worm-algorithm path-integral Monte Carlo simulation of 3He atoms placed on a 4He layer adsorbed on graphite.  

PubMed

We demonstrate the effectiveness of a statistical potential (SP) in the description of fermions in a worm-algorithm path-integral Monte Carlo simulation of a few 3He atoms floating on a 4He layer adsorbed on graphite. The SP in this work yields successful results, as manifested by the clusterization of 3He, and by the observation that the 3He atoms float on the surface of 4He. We display the positions of the particles in 3D coordinate space, which reveal clusterization of the 3He component. The correlation functions are also presented, which give further evidence for the clusterization. PMID:22400696

Ghassib, Humam B; Sakhel, Asaad R; Obeidat, Omar; Al-Oqali, Amer; Sakhel, Roger R

2012-01-01

246

Inter-Domain Redundancy Path Computation Methods Based on PCE  

NASA Astrophysics Data System (ADS)

This paper evaluates three inter-domain redundancy path computation methods based on PCE (Path Computation Element). Some inter-domain paths carry traffic that must be assured of high quality and high reliability transfer such as telephony over IP and premium virtual private networks (VPNs). It is, therefore, important to set inter-domain redundancy paths, i. e. primary and secondary paths. The first scheme utilizes an existing protocol and the basic PCE implementation. It does not need any extension or modification. In the second scheme, PCEs make a virtual shortest path tree (VSPT) considering the candidates of primary paths that have corresponding secondary paths. The goal is to reduce blocking probability; corresponding secondary paths may be found more often after a primary path is decided; no protocol extension is necessary. In the third scheme, PCEs make a VSPT considering all candidates of primary and secondary paths. Blocking probability is further decreased since all possible candidates are located, and the sum of primary and secondary path cost is reduced by choosing the pair with minimum cost among all path pairs. Numerical evaluations show that the second and third schemes offer only a few percent reduction in blocking probability and path pair total cost, while the overheads imposed by protocol revision and increase of the amount of calculation and information to be exchanged are large. This suggests that the first scheme, the most basic and simple one, is the best choice.

Hayashi, Rie; Oki, Eiji; Shiomoto, Kohei

247

Path Sensitization in Critical Path Problem  

Microsoft Academic Search

Since the delay of a circuit is determined by the delay of its longest sensitizable paths (such paths are called critical paths), the problem of estimating the delay of a circuit is called critical path problem. One important aspect of the critical path problem is to decide whether a path is sensitizable. A framework which allows various previously proposed path

Hsi-chuan Chen; David Hung-chang Du

1991-01-01

248

Heuristic Instruction Scheduling Algorithm Using Available Distance for Partial Forwarding Processor  

NASA Astrophysics Data System (ADS)

Partial forwarding is a design method to place forwarding paths on a part of processor pipeline. Hardware cost of processor can be reduced without performance loss by partial forwarding. However, compiler with the instruction scheduler which considers partial forwarding structure of the target processor is required since conventional scheduling algorithm cannot make the most of partial forwarding structure. In this paper, we propose a heuristic instruction scheduling method for processors with partial forwarding structure. The proposed algorithm uses available distance to schedule instructions which are suitable for the target partial forwarding processor. Experimental results show that the proposed method generates near-optimal solutions in practical time and some of the optimized codes for partial forwarding processor run in the shortest time among the target processors. It also shows that the proposed method is superior to hazard detection unit.

Hieda, Takuji; Tanaka, Hiroaki; Sakanushi, Keishi; Takeuchi, Yoshinori; Imai, Masaharu

249

Path Pascal  

NASA Technical Reports Server (NTRS)

Path Pascal is high-level experimental programming language based on PASCAL, which incorporates extensions for systems and real-time programming. Pascal is extended to treat real-time concurrent systems.

Campbell, R. H.; Kolstad, R. B.; Holle, D. F.; Miller, T. J.; Krause, P.; Horton, K.; Macke, T.

1983-01-01

250

Parallel Shortest Lattice Vector Enumeration on Graphics Cards  

E-print Network

of parallel computing systems. To illustrate the algorithm, it was implemented on graphics cards using CUDA, exhaustive search 1 Introduction Lattice-based cryptosystems are assumed to be secure against quantum com, especially to implementation aspects. In this paper we consider parallelization and special hardware

251

On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem  

Microsoft Academic Search

We prove the equivalence, up to a small polynomial approximation factor Ö{n\\/logn}\\\\sqrt{n\\/\\\\log n}, of the lattice problems uSVP (unique Shortest Vector Problem), BDD (Bounded Distance Decoding) and GapSVP (the decision version of the Shortest Vector Problem). This resolves a long-standing open problem about the relationship\\u000a between uSVP and the more standard GapSVP, as well the BDD problem commonly used in

Vadim Lyubashevsky; Daniele Micciancio

2009-01-01

252

Disk scheduling algorithms based on rotational position  

Microsoft Academic Search

When sufficient processor power is available, disk scheduling based on rotational position as well as disk arm position is shown to provide improved performance. A taxonomy of algorithms based on Shortest Access Time First (SATF) have been developed, and several of them have been explored through simulations. The access-time based algorithms match or outperform all the seek-time ones we studied.

D. Jacobsen; J. Wilkes

1991-01-01

253

REPRESENTING RECTILINEAR STEINER TREES IN GENETIC ALGORITHMS  

E-print Network

- clidean plane. The rectilinear Steiner problem seeks a rectilinear Steiner tree of minimum length algorithm for the rectilinear Steiner problem. The #12;rst is based on Prufer's proof of Cayley's for- mula|and compares the two codings in a genetic algorithm for the rectilinear Steiner problem, which seeks a shortest

Julstrom, Bryant A.

254

Algorithm Engineering: It's All About Speed  

E-print Network

? Research Tools: run many experiments to test hypotheses and for discovery Production Tools: obviously, save, shortest paths, convex hulls, Delaunay triangulations, matching and flow). Rome School on Alg. Eng. ­ p.8 to enable the design of much better solutions than are possible for the general problem. Rome School on Alg

Moret, Bernard

255

Multicriteria adaptive paths in stochastic, time-varying networks  

Microsoft Academic Search

In this paper, exact algorithms are proposed for addressing multicriteria adaptive path problems, where arc attributes are stochastic and time-varying. Adaptive paths comprise a set of path strategies that enable the traveler to select a direction among all Pareto-optimal solutions at each node in response to knowledge of the arrival time at the intermediate nodes. Such paths can be viewed

Sathaporn Opasanon; Elise Miller-hooks

2006-01-01

256

A simple dynamic load balancing algorithm for homogeneous distributed systems  

Microsoft Academic Search

In this paper, a simple decentralized dynamic load balancing algorithm, is presented. The algorithm is a variant of “join the shortest queue” algorithm. It uses remote jobs as carriers to transfer current node state information between nodes. We assume that remote jobs are partially processed at the remote sites and return back to their original site for more processing. A

Hany H. Ammar; Su Deng

1988-01-01

257

Term Paths  

NSDL National Science Digital Library

Students follow several pathways using anatomical directions on a simulated "body" produced from a copy of a school building's fire evacuation plan. The main hallways are designated as major blood vessels and the various areas of the school, the head, chest, abdomen, etc. Students complete several pathways using anatomical terms as directions. For example, one of my paths begins, "Ex- ot-, ad- superior, ecto- derm-, peri-frontal, circum- rhino-, " which loosely means, exit the ear, go to the superior region, outside the skin, around the frontal region, around the nose. At the end of each path I leave a clue that lets me know the students actually made it. The combined clues form a sentence.

BEGIN:VCARD VERSION:2.1 FN:Cynthia Ann Radle N:Ann Radle;Cynthia ORG:McCullough High School REV:2005-04-13 END:VCARD

1995-06-30

258

On r-locating-dominating sets in paths  

Microsoft Academic Search

Assume that G=(V,E) is a simple undirected graph, and C is a nonempty subset of V. For every v?V, we define Ir(v)={u?C?dG(u,v)?r}, where dG(u,v) denotes the number of edges on any shortest path between u and v. If the sets Ir(v) for v??C are pairwise different, and none of them is the empty set, we say that C is an

Iiro S. Honkala

2009-01-01

259

Route choices of transport bicyclists: a comparison of actually used and shortest routes  

PubMed Central

Background Despite evidence that environmental features are related to physical activity, the association between the built environment and bicycling for transportation remains a poorly investigated subject. The aim of the study was to improve our understanding of the environmental determinants of bicycling as a means of transportation in urban European settings by comparing the spatial differences between the routes actually used by bicyclists and the shortest possible routes. Methods In the present study we examined differences in the currently used and the shortest possible bicycling routes, with respect to distance, type of street, and environmental characteristics, in the city of Graz, Austria. The objective measurement methods of a Global Positioning System (GPS) and a Geographic Information System (GIS) were used. Results Bicycling routes actually used were significantly longer than the shortest possible routes. Furthermore, the following attributes were also significantly different between the used route compared to the shortest possible route: Bicyclists often used bicycle lanes and pathways, flat and green areas, and they rarely used main roads and crossings. Conclusion The results of the study support our hypothesis that bicyclists prefer bicycle pathways and lanes instead of the shortest possible routes. This underlines the importance of a well-developed bicycling infrastructure in urban communities. PMID:24597725

2014-01-01

260

Parallelism and Greedy Algorithms  

Microsoft Academic Search

Abstract A number,of greedy algorithms,are examined,algorithms are presented for finding a maximal path, for finding a . maximal set of disjoint paths in a layered dag,and for finding the largest induced subgraph of a graph,that,has,all vertices,of degree,at least Ic. It is shown,that,for all of these algorithms, the problem of determining if a given node is

Richard Anderson; Ernst Mayr

261

Metabolic Flux-Based Modularity using Shortest Retroactive distances  

PubMed Central

Background Graph-based modularity analysis has emerged as an important tool to study the functional organization of biological networks. However, few methods are available to study state-dependent changes in network modularity using biological activity data. We develop a weighting scheme, based on metabolic flux data, to adjust the interaction distances in a reaction-centric graph model of a metabolic network. The weighting scheme was combined with a hierarchical module assignment algorithm featuring the preservation of metabolic cycles to examine the effects of cellular differentiation and enzyme inhibitions on the functional organization of adipocyte metabolism. Results Our analysis found that the differences between various metabolic states primarily involved the assignment of two specific reactions in fatty acid synthesis and glycerogenesis. Our analysis also identified cyclical interactions between reactions that are robust with respect to metabolic state, suggesting possible co-regulation. Comparisons based on cyclical interaction distances between reaction pairs suggest that the modular organization of adipocyte metabolism is stable with respect to the inhibition of an enzyme, whereas a major physiological change such as cellular differentiation leads to a more substantial reorganization. Conclusion Taken together, our results support the notion that network modularity is influenced by both the connectivity of the network’s components as well as the relative engagements of the connections. PMID:23270532

2012-01-01

262

Neither Shortest Path Nor Dominating Set: Aggregation Scheduling by Greedy Growing Tree in Multihop Wireless Sensor Networks  

Microsoft Academic Search

Data aggregation is a fundamental task in multihop wireless sensor networks. Minimum-latency aggregation schedul- ing (MLAS) seeks to minimize the number of scheduled time slots to perform an aggregation. In this paper, we present the first work on a solvable mathematical formulation of the MLAS problem. The optimal solution of small example networks sug- gests that an optimal scheduling can

Chen Tian; Hongbo Jiang; Chonggang Wang; Zuodong Wu; Jinhua Chen; Wenyu Liu

2011-01-01

263

GENERATING PROBABILISTIC PATH OBSERVATION FROM GPS DATA FOR ROUTE CHOICE MODELING  

E-print Network

map matching algorithms are the conventional way to generate a unique true path from GPS data trace to paths. In this paper, we introduce detailed techniques of an algorithm proposed by Bierlaire, Newman et

Bierlaire, Michel

264

Protecting Location Privacy Through Path Confusion  

Microsoft Academic Search

We present a path perturbation algorithm which can maximize users? location privacy given a quality of service constraint. This work concentrates on a class of applications that continuously collect location samples from a large group of users, where just removing user identifiers from all samples is insufficient because an adversary could use trajectory information to track paths and follow users?

Baik Hoh; Marco Gruteser

2005-01-01

265

Control-path Oriented Workflow Intelligence Analyses  

Microsoft Academic Search

This paper proposes two kinds of control-path oriented workflow knowledge analy- sis approaches which will be applied to a workflow intelligence and quality improve- ment framework aiming at the high degree of the workflow traceability and rediscover- ability. The framework needs two kinds of algorithms ? One is for generating the total sequences of the control-paths from a workflow model,

Minjae Park; Kwanghoon Kim

2008-01-01

266

Ray Paths  

NSDL National Science Digital Library

For the next two exercises, we will break up into groups of four. Each member of the group will represent one of four waves leaving the source: direct wave, ground roll, reflected wave, and head wave. All four "waves" will leave the source at the same time and travel at a particular speed and path as directed by the instructor. ALL students will record the arrival time of each "wave" at each geophone until all 12 geophones have been used. Plot arrival time versus distance for each "wave". Do any of the time versus distance curves fit a straight line? Do any of them not fit a straight line? Explain why they do or don't fit a straight line. Uses online and/or real-time data Has minimal/no quantitative component

267

Data-Oriented Algorithm for Route Choice Set Generation in a Metropolitan Area with Mobile Phone GPS Data  

NASA Astrophysics Data System (ADS)

Nowadays, for the estimation of traffic demand or people flow, modelling route choice activity in road networks is an important task and many algorithms have been developed to generate route choice sets. However, developing an algorithm based on a small amount of data that can be applied generally within a metropolitan area is difficult. This is because the characteristics of road networks vary widely. On the other hand, recently, the collection of people movement data has lately become much easier, especially through mobile phones. Lately, most mobile phones include GPS functionality. Given this background, we propose a data-oriented algorithm to generate route choice sets using mobile phone GPS data. GPS data contain a number of measurement errors; hence, they must be adjusted to account for these errors before use in advanced people movement analysis. However, this is time-consuming and expensive, because an enormous amount of daily data can be obtained. Hence, the objective of this study is to develop an algorithm that can easily manage GPS data. Specifically, at first movement data from all GPS data are selected by calculating the speed. Next, the nearest roads in the road network are selected from the GPS location and count such data for each road. Then An algorithm based on the GSP (Gateway Shortest Path) algorithm is proposed, which searches the shortest path through a given gateway. In the proposed algorithm, the road for which the utilization volume calculated by GPS data is large is selected as the gateway. Thus, route choice sets that are based on trends in real GPS data are generated. To evaluate the proposed method, GPS data from 0.7 million people a year in Japan and DRM (Digital Road Map) as the road network are used. DRM is one of the most detailed road networks in Japan. Route choice sets using the proposed algorithm are generated and the cover rate of the utilization volume of each road under evaluation is calculated. As a result, the proposed route generation algorithm and GPS data cleaning process work well and a huge variety of routes that have high potential to be used in the real world can be generated.

Nakamura, T.; Sekimoto, Y.; Usui, T.; Shibasaki, R.

2012-07-01

268

Simulation-efficient shortest probability intervals Ying Liu, Andrew Gelman, and Tian Zheng  

E-print Network

, these can be noisy (that is, have a high Monte Carlo error). We derive an optimal weighting strategy using Monte Carlo error than empirical shortest intervals. We implement the new method in an R package (SPIn such as the nor- mal and gamma but are more difficult to compute from simulations. We would like to go back

Gelman, Andrew

269

The Length of the Shortest Telomere as the Major Determinant of the Onset of Replicative Senescence  

PubMed Central

The absence of telomerase in many eukaryotes leads to the gradual shortening of telomeres, causing replicative senescence. In humans, this proliferation barrier constitutes a tumor suppressor mechanism and may be involved in cellular aging. Yet the heterogeneity of the senescence phenotype has hindered the understanding of its onset. Here we investigated the regulation of telomere length and its control of senescence heterogeneity. Because the length of the shortest telomeres can potentially regulate cell fate, we focus on their dynamics in Saccharomyces cerevisiae. We developed a stochastic model of telomere dynamics built on the protein-counting model, where an increasing number of protein-bound telomeric repeats shift telomeres into a nonextendable state by telomerase. Using numerical simulations, we found that the length of the shortest telomere is well separated from the length of the others, suggesting a prominent role in triggering senescence. We evaluated this possibility using classical genetic analyses of tetrads, combined with a quantitative and sensitive assay for senescence. In contrast to mitosis of telomerase-negative cells, which produces two cells with identical senescence onset, meiosis is able to segregate a determinant of senescence onset among the telomerase-negative spores. The frequency of such segregation is in accordance with this determinant being the length of the shortest telomere. Taken together, our results substantiate the length of the shortest telomere as being the key genetic marker determining senescence onset in S. cerevisiae. PMID:23733785

Xu, Zhou; Duc, Khanh Dao; Holcman, David; Teixeira, Maria Teresa

2013-01-01

270

A Comparison of Two Path Planners for Planetary Rovers  

NASA Technical Reports Server (NTRS)

The paper presents two path planners suitable for planetary rovers. The first is based on fuzzy description of the terrain, and genetic algorithm to find a traversable path in a rugged terrain. The second planner uses a global optimization method with a cost function that is the path distance divided by the velocity limit obtained from the consideration of the rover static and dynamic stability. A description of both methods is provided, and the results of paths produced are given which show the effectiveness of the path planners in finding near optimal paths. The features of the methods and their suitability and application for rover path planning are compared

Tarokh, M.; Shiller, Z.; Hayati, S.

1999-01-01

271

Ant Algorithms 4.1 4 Some applications of distributed  

E-print Network

intelligence: ant algorithms There is some degree of communication among the ants, just enough to keep them from wandering off completely at random. By this minimal communication they can remind each other that they are not alone but are cooperating with teammates. D. Hofstader (1979) In the previous chapter we looked at a number of examples of distributed systems. Among others, we saw that ants are capable of finding the shortest path to a food source via a process of self-organization mediated through pheromone trails (Chapter 3, Section 3.2). Through such stigmergic interactions 1, i.e. interactions mediated by modifications of the environment (deposition of pheromones), ants manage to solve a complex optimization problem. In addition to solving such a problem, their behavior is robust, i.e. the “solution ” is immune to noise. The ants remain also adaptive, in the sense that if the environmental situation changes, for example if a path is no longer present or a shortcut becomes available, they find

unknown authors

272

A hybrid genetic algorithm for the weight setting problem in OSPF\\/ISIS routing  

Microsoft Academic Search

Intradomain traffic engineering aims to make more effi- cient use of network resources within an autonomous system. Interior Gateway Protocols such as OSPF (Open Shortest Path First) and IS-IS (Intermediate System- Intermediate System) are commonly used to select the paths along which traffic is routed within an autonomous system. These routing protocols direct traffic based on link weights assigned by

Luciana S. Buriol; Mauricio G. C. Resende; Celso C. Ribeiro; Mikkel Thorup

2005-01-01

273

THE PATH-PARTITION PROBLEM IN BIPARTITE DISTANCE-HEREDITARY GRAPHS  

Microsoft Academic Search

A path partition of a graph is a collection of vertex-disjoint paths that cover all vertices of the graph. The path-partition problem is to nd a path partition of minimum size. This paper gives a linear-time algorithm for the path-partition problem in bipartite distance-hereditary graphs.

Hong-Gwa Yeh; Gerard J. Chang

1998-01-01

274

Performance Evaluation of Two New Disk Scheduling algorithms for Real-Time Systems  

Microsoft Academic Search

In this paper, we present two new disk scheduling algorithms for real-time systems. The twoalgorithms, called SSEDO(for Shortest Seek and Earliest Deadline by Ordering) and SSEDV(forShortest Seek and Earliest Deadline by Value), combine deadline information and disk servicetime information in different ways. The basic idea behind these new algorithms is to give thedisk I\\/O request with the earliest deadline a

Shenze Chen; John A. Stankovic; James F. Kurose; Donald F. Towsley

1991-01-01

275

New Approximation Algorithms for the Steiner Tree Problems  

E-print Network

New Approximation Algorithms for the Steiner Tree Problems Marek Karpinski \\Lambda Alexander Zelikovsky y Abstract The Steiner tree problem asks for the shortest tree connecting a given set of terminal points in a metric space. We design new approximation algorithms for the Steiner tree problems using

Karpinski, Marek

276

Tracking hurricane paths  

NASA Technical Reports Server (NTRS)

The South East coastal region experiences hurricane threat for almost six months in every year. To improve the accuracy of hurricane forecasts, meteorologists would need the storm paths of both the present and the past. A hurricane path can be established if we could identify the correct position of the storm at different times right from its birth to the end. We propose a method based on both spatial and temporal image correlations to locate the position of a storm from satellite images. During the hurricane season, the satellite images of the Atlantic ocean near the equator are examined for the hurricane presence. This is accomplished in two steps. In the first step, only segments with more than a particular value of cloud cover are selected for analysis. Next, we apply image processing algorithms to test the presence of a hurricane eye in the segment. If the eye is found, the coordinate of the eye is recorded along with the time stamp of the segment. If the eye is not found, we examine adjacent segments for the existence of hurricane eye. It is probable that more than one hurricane eye could be found from different segments of the same period. Hence, the above process is repeated till the entire potential area for hurricane birth is exhausted. The subsequent/previous position of each hurricane eye will be searched in the appropriate adjacent segments of the next/previous period to mark the hurricane path. The temporal coherence and spatial coherence of the images are taken into account by our scheme in determining the segments and the associated periods required for analysis.

Prabhakaran, Nagarajan; Rishe, Naphtali; Athauda, Rukshan

1997-01-01

277

Maximum Flux Transition Paths of Conformational Change  

PubMed Central

Given two metastable states A and B of a biomolecular system, the problem is to calculate the likely paths of the transition from A to B. Such a calculation is more informative and more manageable if done for a reduced set of collective variables chosen so that paths cluster in collective variable space. The computational task becomes that of computing the “center” of such a cluster. A good way to define the center employs the concept of a committor, whose value at a point in collective variable space is the probability that a trajectory at that point will reach B before A. The committor “foliates” the transition region into a set of isocommittors. The maximum flux transition path is defined as a path that crosses each isocommittor at a point which (locally) has the highest crossing rate of distinct reactive trajectories. This path is based on the same principle as the minimum resistance path of Berkowitz et al (1983), but it has two advantages: (i) the path is invariant with respect to a change of coordinates in collective variable space and (ii) the differential equations that define the path are simpler. It is argued that such a path is nearer to an ideal path than others that have been proposed with the possible exception of the finite-temperature string method path. To make the calculation tractable, three approximations are introduced, yielding a path that is the solution of a nonsingular two-point boundary-value problem. For such a problem, one can construct a simple and robust algorithm. One such algorithm and its performance is discussed. PMID:20890401

Zhao, Ruijun; Shen, Juanfang; Skeel, Robert D.

2010-01-01

278

A new loop-reducing routing algorithm  

E-print Network

distances for all pairs of nodes in the subnet, and distributes updated routing information to all the nodes. The centralized algorithm, however, is vulnerable to a. single node failure ? if the NRC fails, all nodes in the network must stop their rout... the shortest distances are computed for every node to every other node in a, distributed manner. Due to the simplicity and robustness (the Bellman- Ford algorithm will converge with arbitrary initial conditions), many of the other computer networks adapted...

Park, Sung-Woo

2012-06-07

279

Minimum-Risk Path Finding by an Adaptive Amoebal Network Toshiyuki Nakagaki,1,2,* Makoto Iima,1  

E-print Network

is formed that connects the food sources through the shortest route. When the light- avoiding organism risk as the experimentally measurable rate of light-avoiding movement, the minimum-risk path maintaining sufficient connectivity to permit intracellular communication. Such behavior in a primitive

Showalter, Kenneth

280

Path Planning Algorithms for Multiple Heterogeneous Vehicles  

E-print Network

as the \\Precedence Constrained Asymmetric Travelling Salesman Problem" (PCATSP). v ACKNOWLEDGMENTS Special thanks to the Air Force Research Laboratory (AFRL) Air Vehicles Direc- torate for providing funding and motivation for portions of this thesis, Waqar Malik... as the \\Precedence Constrained Asymmetric Travelling Salesman Problem" (PCATSP). v ACKNOWLEDGMENTS Special thanks to the Air Force Research Laboratory (AFRL) Air Vehicles Direc- torate for providing funding and motivation for portions of this thesis, Waqar Malik...

Oberlin, Paul V.

2010-01-16

281

Seeding the Population: Improved Performance in a Genetic Algorithm for the Rectilinear Steiner Problem  

E-print Network

Steiner problem, genetic algorithms, seeding the pop- ulation. Abstract|A hybrid genetic algorithm of such seeding on a genetic algorithm for the rectilinear Steiner problem, which seeks a shortest rectilinear are called Steiner points. The problem of #12;nding a rectilinear Steiner tree of minimum length on a set

Julstrom, Bryant A.

282

Average path length for Sierpinski pentagon  

E-print Network

In this paper,we investigate diameter and average path length(APL) of Sierpinski pentagon based on its recursive construction and self-similar structure.We find that the diameter of Sierpinski pentagon is just the shortest path lengths between two nodes of generation 0. Deriving and solving the linear homogenous recurrence relation the diameter satisfies, we obtain rigorous solution for the diameter. We also obtain approximate solution for APL of Sierpinski pentagon, both diameter and APL grow approximately as a power-law function of network order $N(t)$, with the exponent equals $\\frac{\\ln(1+\\sqrt{3})}{\\ln(5)}$. Although the solution for APL is approximate,it is trusted because we have calculated all items of APL accurately except for the compensation($\\Delta_{t}$) of total distances between non-adjacent branches($\\Lambda_t^{1,3}$), which is obtained approximately by least-squares curve fitting. The compensation($\\Delta_{t}$) is only a small part of total distances between non-adjacent branches($\\Lambda_t^{1,3}$) and has little effect on APL. Further more,using the data obtained by iteration to test the fitting results, we find the relative error for $\\Delta_{t}$ is less than $10^{-7}$, hence the approximate solution for average path length is almost accurate.

Junhao Peng; Guoai Xu

2011-12-21

283

Finding the optimal-path maps for path planning across weighted regions  

SciTech Connect

Optimal-path maps tell robots or people the best way to reach a goal point from anywhere in a known terrain area, eliminating most of the need to plan during travel. The authors address the construction of optimal-path maps for two-dimensional polygonal weighted-region terrain, terrain partitioned into polygonal areas such that the cost per unit of distance traveled is homogeneous and isotropic within each area. This is useful for overland route planning across varied ground surfaces and vegetation. The authors propose a new algorithm that recursively partitions terrain into regions of similar optimal-path behavior, and defines corresponding path subspaces for these regions. This process constructs a piecewise-smooth function of terrain position whose gradient direction is everywhere the optimal-path direction, permitting quick path finding. The algorithm used is more complicated than the current path-caching and wavefront-propagation algorithms, but it gives more accurate maps requiring less space to represent. Experiments with an implementation confirm the practicality of the authors' algorithm.

Rowe, N.C.; Alexander, R.S.

2000-02-01

284

Learning to improve path planning performance  

SciTech Connect

In robotics, path planning refers to finding a short. collision-free path from an initial robot configuration to a desired configuratioin. It has to be fast to support real-time task-level robot programming. Unfortunately, current planning techniques are still too slow to be effective, as they often require several minutes, if not hours of computation. To remedy this situation, we present and analyze a learning algorithm that uses past experience to increase future performance. The algorithm relies on an existing path planner to provide solutions to difficult tasks. From these solutions, an evolving sparse network of useful robot configurations is learned to support faster planning. More generally, the algorithm provides a speedup-learning framework in which a slow but capable planner may be improved both cost-wise and capability-wise by a faster but less capable planner coupled with experience. The basic algorithm is suitable for stationary environments, and can be extended to accommodate changing environments with on-demand experience repair and object-attached experience abstraction. To analyze the algorithm, we characterize the situations in which the adaptive planner is useful, provide quantitative bounds to predict its behavior, and confirm our theoretical results with experiments in path planning of manipulators. Our algorithm and analysis are sufficiently, general that they may also be applied to other planning domains in which experience is useful.

Chen, Pang C.

1995-04-01

285

Computational path planner for product assembly in complex environments  

NASA Astrophysics Data System (ADS)

Assembly path planning is a crucial problem in assembly related design and manufacturing processes. Sampling based motion planning algorithms are used for computational assembly path planning. However, the performance of such algorithms may degrade much in environments with complex product structure, narrow passages or other challenging scenarios. A computational path planner for automatic assembly path planning in complex 3D environments is presented. The global planning process is divided into three phases based on the environment and specific algorithms are proposed and utilized in each phase to solve the challenging issues. A novel ray test based stochastic collision detection method is proposed to evaluate the intersection between two polyhedral objects. This method avoids fake collisions in conventional methods and degrades the geometric constraint when a part has to be removed with surface contact with other parts. A refined history based rapidly-exploring random tree (RRT) algorithm which bias the growth of the tree based on its planning history is proposed and employed in the planning phase where the path is simple but the space is highly constrained. A novel adaptive RRT algorithm is developed for the path planning problem with challenging scenarios and uncertain environment. With extending values assigned on each tree node and extending schemes applied, the tree can adapts its growth to explore complex environments more efficiently. Experiments on the key algorithms are carried out and comparisons are made between the conventional path planning algorithms and the presented ones. The comparing results show that based on the proposed algorithms, the path planner can compute assembly path in challenging complex environments more efficiently and with higher success. This research provides the references to the study of computational assembly path planning under complex environments.

Shang, Wei; Liu, Jianhua; Ning, Ruxin; Liu, Mi

2013-03-01

286

A Source-Initiated On-Demand Routing Algorithm Based on the Thorup-Zwick Theory for Mobile Wireless Sensor Networks  

PubMed Central

The unreliability and dynamics of mobile wireless sensor networks make it hard to perform end-to-end communications. This paper presents a novel source-initiated on-demand routing mechanism for efficient data transmission in mobile wireless sensor networks. It explores the Thorup-Zwick theory to achieve source-initiated on-demand routing with time efficiency. It is able to find out shortest routing path between source and target in a network and transfer data in linear time. The algorithm is easy to be implemented and performed in resource-constrained mobile wireless sensor networks. We also evaluate the approach by analyzing its cost in detail. It can be seen that the approach is efficient to support data transmission in mobile wireless sensor networks. PMID:24453826

Zhu, Ping

2013-01-01

287

Ant Algorithms for Discrete Optimization  

E-print Network

. Ants can smell pheromone and, when choosing their way, they tend to choose, in probability, pathsAnt Algorithms for Discrete Optimization Marco Dorigo and Gianni Di Caro IRIDIA, Universit#19;e, Switzerland luca@idsia.ch Abstract This paper overviews recent work on ant algorithms, that is, algorithms

Ducatelle, Frederick

288

Adaptive path planning for flexible manufacturing  

SciTech Connect

Path planning needs to be fast to facilitate real-time robot programming. Unfortunately, current planning techniques are still too slow to be effective, as they often require several minutes, if not hours of computation. To overcome this difficulty, we present an adaptive algorithm that uses past experience to speed up future performance. It is a learning algorithm suitable for automating flexible manufacturing in incrementally-changing environments. The algorithm allows the robot to adapt to its environment by having two experience manipulation schemes: For minor environmental change, we use an object-attached experience abstraction scheme to increase the flexibility of the learned experience; for major environmental change, we use an on-demand experience repair scheme to retain those experiences that remain valid and useful. Using this algorithm, we can effectively reduce the overall robot planning time by re-using the computation result for one task to plan a path for another.

Chen, Pang C.

1994-08-01

289

Identifying codes and locating-dominating sets on paths and cycles  

Microsoft Academic Search

Let $G=(V,E)$ be a graph and let $r\\\\ge 1$ be an integer. For a set $D \\\\subseteq V$, define $N_r[x] = \\\\{y \\\\in V: d(x, y) \\\\leq r\\\\}$ and $D_r(x) = N_r[x] \\\\cap D$, where $d(x,y)$ denotes the number of edges in any shortest path between $x$ and $y$. $D$ is known as an $r$-identifying code ($r$-locating-dominating set, respectively), if

Chunxia Chen; Changhong Lu; Zhengke Miao

2009-01-01

290

DISCUSS: Critical Path Analysis  

NSDL National Science Digital Library

This module, by Barrie Baker and Neville Hunt of Coventry University, introduces critical path analysis and addresses the following topics: Networks, Critical paths, Floats, Activity-on-node (AON) networks. Excel spreadsheets are used to provide examples and exercises.

Baker, Barrie; Hunt, Neville

2009-04-23

291

Extremal paths on a random cayley tree  

PubMed

We investigate the statistics of extremal path(s) (both the shortest and the longest) from the root to the bottom of a Cayley tree. The lengths of the edges are assumed to be independent identically distributed random variables drawn from a distribution rho(l). Besides, the number of branches from any node is also random. Exact results are derived for arbitrary distribution rho(l). In particular, for the binary 0,1 distribution rho(l)=pdelta(l,1)+(1-p)delta(l, 0), we show that as p increases, the minimal length undergoes an unbinding transition from a "localized" phase to a "moving" phase at the critical value, p=p(c)=1-b(-1), where b is the average branch number of the tree. As the height n of the tree increases, the minimal length saturates to a finite constant in the localized phase (pp(c)) where the velocity v(min)(p) is determined via a front selection mechanism. At p=p(c), the minimal length grows with n in an extremely slow double-logarithmic fashion. The length of the maximal path, on the other hand, increases linearly as v(max)(p)n for all p. The maximal and minimal velocities satisfy a general duality relation, v(min)(p)+v(max)(1-p)=1, which is also valid for directed paths on finite-dimensional lattices. PMID:11138046

Majumdar; Krapivsky

2000-12-01

292

Reconfigurable data path processor  

NASA Technical Reports Server (NTRS)

A reconfigurable data path processor comprises a plurality of independent processing elements. Each of the processing elements advantageously comprising an identical architecture. Each processing element comprises a plurality of data processing means for generating a potential output. Each processor is also capable of through-putting an input as a potential output with little or no processing. Each processing element comprises a conditional multiplexer having a first conditional multiplexer input, a second conditional multiplexer input and a conditional multiplexer output. A first potential output value is transmitted to the first conditional multiplexer input, and a second potential output value is transmitted to the second conditional multiplexer output. The conditional multiplexer couples either the first conditional multiplexer input or the second conditional multiplexer input to the conditional multiplexer output, according to an output control command. The output control command is generated by processing a set of arithmetic status-bits through a logical mask. The conditional multiplexer output is coupled to a first processing element output. A first set of arithmetic bits are generated according to the processing of the first processable value. A second set of arithmetic bits may be generated from a second processing operation. The selection of the arithmetic status-bits is performed by an arithmetic-status bit multiplexer selects the desired set of arithmetic status bits from among the first and second set of arithmetic status bits. The conditional multiplexer evaluates the select arithmetic status bits according to logical mask defining an algorithm for evaluating the arithmetic status bits.

Donohoe, Gregory (Inventor)

2005-01-01

293

Evaluation of concurrent priority queue algorithms. Technical report  

SciTech Connect

The priority queue is a fundamental data structure that is used in a large variety of parallel algorithms, such as multiprocessor scheduling and parallel best-first search of state-space graphs. This thesis addresses the design and experimental evaluation of two novel concurrent priority queues: a parallel Fibonacci heap and a concurrent priority pool, and compares them with the concurrent binary heap. The parallel Fibonacci heap is based on the sequential Fibonacci heap, which is theoretically the most efficient data structure for sequential priority queues. This scheme not only preserves the efficient operation time bounds of its sequential counterpart, but also has very low contention by distributing locks over the entire data structure. The experimental results show its linearly scalable throughput and speedup up to as many processors as tested (currently 18). A concurrent access scheme for a doubly linked list is described as part of the implementation of the parallel Fibonacci heap. The concurrent priority pool is based on the concurrent B-tree and the concurrent pool. The concurrent priority pool has the highest throughput among the priority queues studied. Like the parallel Fibonacci heap, the concurrent priority pool scales linearly up to as many processors as tested. The priority queues are evaluated in terms of throughput and speedup. Some applications of concurrent priority queues such as the vertex cover problem and the single source shortest path problem are tested.

Huang, Q.

1991-02-01

294

Average path length for Sierpinski pentagon  

E-print Network

In this paper,we investigate diameter and average path length(APL) of Sierpinski pentagon based on its recursive construction and self-similar structure.We find that the diameter of Sierpinski pentagon is just the shortest path lengths between two nodes of generation 0. Deriving and solving the linear homogenous recurrence relation the diameter satisfies, we obtain rigorous solution for the diameter. We also obtain approximate solution for APL of Sierpinski pentagon, both diameter and APL grow approximately as a power-law function of network order $N(t)$, with the exponent equals $\\frac{\\ln(1+\\sqrt{3})}{\\ln(5)}$. Although the solution for APL is approximate,it is trusted because we have calculated all items of APL accurately except for the compensation($\\Delta_{t}$) of total distances between non-adjacent branches($\\Lambda_t^{1,3}$), which is obtained approximately by least-squares curve fitting. The compensation($\\Delta_{t}$) is only a small part of total distances between non-adjacent branches($\\Lambda_t^{1...

Peng, Junhao

2011-01-01

295

Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors  

Microsoft Academic Search

In this paper, we propose a static scheduling algorithm for allocating task graphs to fully- connected multiprocessors. We discuss six recently reported scheduling algorithms and show that they possess one drawback or the other which can lead to poor performance. The proposed algorithm, which is called the Dynamic Critical-Path (DCP) scheduling algorithm, is different from the previously proposed algorithms in

Yu-kwong Kwok; Ishfaq Ahmad

1996-01-01

296

Complexity of parallel algorithms  

SciTech Connect

This thesis addresses a number of theoretical issues in parallel computation. There are many open questions relating to what can be done with parallel computers and what are the most effective techniques to use to develop parallel algorithms. Various problems are examined in hope of gaining insight to the general questions. One topic investigated is the relationship between sequential and parallel algorithms. The concept of a P-complete algorithm is introduced to capture what it means for an algorithm to be inherently sequential. It is shown that a number of sequential greedy algorithms are P-complete, including the greedy algorithm for finding a path in a graph. However, an algorithm being P-complete does not necessarily mean that the problem is difficult. In some cases, the natural sequential algorithm is P-complete but a different technique gives a fast parallel algorithm. This shows that it is necessary to use different techniques for parallel computation than are used for sequential computation. Fast parallel algorithms are given for a number of simple graph theory problems. The algorithms illustrate a number of different techniques that are useful for parallel algorithms. A number of results on approximating P-complete problems with parallel algorithms are given that are similar to results on approximating NP-complete problems with sequential algorithms.

Anderson, R.J.

1986-01-01

297

Hard paths, soft paths or no paths? Cross-cultural perceptions of water solutions  

E-print Network

Hard paths, soft paths or no paths? Cross-cultural perceptions of water solutions Drew Blasco1 to the availability of clean, safe water. In this study we examined cross cultural preferences for soft path vs. hard conceptualize water solutions (hard paths, soft paths, no paths) cross-culturally? 2) What role does development

Hall, Sharon J.

298

Optimized Cell Planning for Path Loss Reduction  

Microsoft Academic Search

In this paper, an optimized cell planning for path loss reduction has been proposed. A 10 by 10 Km square block is considered as traffic required area (TRA) which consists of number of base stations (BSs) and mobile stations (MSs). The optimization algorithm: Tabu search, is used to optimize the position of base stations in such a way that the

Nagendra Sah

2008-01-01

299

Constrained Optimization Path Following of Wheeled Robots  

E-print Network

Abstract. A smooth-primitive constrained-optimization-based path-tracking algorithm for mobile robots that compensates for rough terrain, predictable vehicle dynamics, and vehicle mobility constraints has been developed, implemented, and tested on the DARPA LAGR platform. Traditional methods for the geometric path following control problem involve trying to meet position constraints at fixed or velocity dependent look-ahead distances using arcs. We have reformulated the problem as an optimal control problem, using a trajectory generator that can meet arbitrary boundary state constraints. The goal state along the target path is determined dynamically by minimizing a utility function based on corrective trajectory feasibility and cross-track error. A set of field tests compared the proposed method to an implementation of the pure pursuit algorithm and showed that the smooth corrective trajectory constrained optimization approach exhibited higher performance than pure pursuit by achieving rough four times lower average cross-track error and two times lower heading error. 1

Thomas M. Howard; Alonzo Kelly

2006-01-01

300

Walden's Paths - Ensemble Edition  

NSDL National Science Digital Library

WaldenÂs Paths enables users of digital document collections (e.g. the Web) to exploit these documents by reusing them for previously unintended audiences in an academic setting. Authors of paths (usually educators) overlay a linear, directed meta-structure over the Web documents and recontextualize these by adding explanatory text to achieve their curricular goals. Paths do not modifythe structure or content of the Web resources that they include. The creation of a path over pre-organized content (e.g. books, Web pages) to reorganize and associate related information serves to facilitate easy retrieval and communication. WaldenÂs Paths displays the information that the path points to in conjunction with the textual annotations added by the author of the path.

2011-01-04

301

Multiobjective Evolutionary Path Planning via Sugeno-Based Tournament Selection  

NASA Technical Reports Server (NTRS)

This paper introduces a new tournament selection algorithm that can be used for evolutionary path planning systems. The fuzzy (Sugeno) tournament selection algorithm (STSA) described in this paper selects candidate paths (CPs) to be parents and undergo reproduction based on: (1) path feasibility, (2) the euclidean distance of a path from the origin to its destination, and (3) the average change in the slope of a path. In this paper, we provide a detailed description of the fuzzy inference system used in the STSA as well as some examples of its usefulness. We then use 12 instances of our STSA to rank a population of CPs based on the above criteria. We also show how the STSA can obviate the need for the development of an explicit (lexicographic multiobjective) evaluation function and use it to develop multiobjective motion paths.

Dozier, Gerry; McCullough, Shaun; Homaifar, Abdollah; Esterline, Albert

1998-01-01

302

A global path planning approach for redundant manipulators  

NASA Technical Reports Server (NTRS)

A new approach for global path planning of redundant manipulators is proposed. It poses the path planning problem as a finite time nonlinear control problem. The solution is found by a Newton-Raphson type algorithm. This technique is capable of handling various goal task descriptions as well as incorporating both joint and task space constraints. The algorithm has shown promising preliminary results in planning joint path sequences for 3R and 4R planar robots to meet Cartesian tip tracking and goal endpoint planning. It is robust with respect to local path planning problems such as singularity considerations and local minimum problems. Repetitive joint path solutions for cyclic end-effector tasks are also generated. Eventual goals of this work include implementation on full spatial robots, as well as provision of an interface for supervisory input to aid in path planning for more complex problems.

Seereeram, Sanjeev; Wen, J.

1993-01-01

303

Intricacies of quantum computational paths  

NASA Astrophysics Data System (ADS)

Graph search represents a cornerstone in computer science and is employed when the best algorithmic solution to a problem consists in performing an analysis of a search space representing computational possibilities. Typically, in such problems it is crucial to determine the sequence of transitions performed that led to certain states. In this work we discuss how to adapt generic quantum search procedures, namely quantum random walks and Grover's algorithm, in order to obtain computational paths. We then compare these approaches in the context of tree graphs. In addition we demonstrate that in a best-case scenario both approaches differ, performance-wise, by a constant factor speedup of two, whilst still providing a quadratic speedup relatively to their classical equivalents. We discuss the different scenarios that are better suited for each approach.

Tarrataca, Luís; Wichert, Andreas

2013-02-01

304

Finding Minimum Energy Disjoint Paths in Wireless Ad-Hoc Networks  

Microsoft Academic Search

We develop algorithms for finding minimum energy disjoint paths in an all-wireless network, for both the node and link-disjoint cases. Our major results include a novel polynomial time algorithm that optimally solves the minimum energy 2 link-disjoint paths problem, as well as a polynomial time algorithm for the minimum energy k node-disjoint paths problem. In addition, we present efficient heuristic

Anand Srinivas; Eytan Modiano

2005-01-01

305

Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings  

E-print Network

algorithms for various problems, in partic- ular the generalized Steiner forest problem (including the minimum Steiner tree problem), the minimum routing cost spanning tree problem, and the k-source shortest problems. Our approach is randomized and based on a probabilistic tree embedding due to Fakcharoenphol, Rao

Khan, Maleq

306

New Approximation Algorithms for the Steiner Tree Problems  

Microsoft Academic Search

The Steiner tree problem asks for the shortest tree connecting a given set of terminal points ina metric space. We design new approximation algorithms for the Steiner tree problems usinga novel technique of choosing Steiner points in dependence on the possible deviation from theoptimal solutions. We achieve the best up to now approximation ratios of 1.644 in arbitrarymetric and 1.267

Marek Karpinski; Alexander Zelikovsky

1995-01-01

307

Path Relaxation: Path Planning for a Mobile Robot  

Microsoft Academic Search

Path Relaxation is a method of planning safe paths around obstacles for mobile robots. It works in two steps: a global grid starch that finds a rough path, followed by a local relaxation step that adjusts each node on the path to lower the overall path cost. The representation used by Path Relaxation allows an explicit tradeoff among length of

Charles E. Thorpe; L. Matthies

1984-01-01

308

A novel approach to the prediction of musculotendon paths.  

PubMed

One of the most important aspects of the modelling of musculoskeletal systems is the determination of muscle moment arms which are dependent upon the paths of the muscles. These paths are often required to wrap around passive structures that can be modelled as simple geometric shapes. A novel technique for the prediction of the paths of muscles modelled as strings when wrapping around smooth analytical surfaces is presented. The theory of geodesics is used to calculate the shortest path of the string on the surface and a smoothness constraint is used to determine the correct solutions for the string path between insertions. The application of the technique to tapered cylinders and ellipsoids is presented as an extension of previous work on right-circular cylinders and spheres. The technique is assessed with reference to a particular biomechanical scenario; string lengths and moment arms are calculated and compared with alternative approximate methods. This illustrates the potential of the technique to provide more accurate muscle moment arm predictions. PMID:18335718

Marsden, S P; Swailes, D C

2008-01-01

309

A weighted coding in a genetic algorithm for the degree-constrained minimum spanning tree problem  

Microsoft Academic Search

The coding by which chromosomes represent candidate solu- tions is a fundamental design choice in a genetic algorithm. This paper describes a novel coding of spanning trees in a genetic algorithm for the degree-constrained minimum span- ning tree problem. For a connected, weighted graph, this problem seeks to identify the shortest spanning tree whose degree does not exceed an upper

Günther R. Raidl; Bryant A. Julstrom

2000-01-01

310

New Approximation Algorithms for the Steiner Trees Problems Marek Karpinski Alexander Zelikovskyy  

E-print Network

New Approximation Algorithms for the Steiner Trees Problems Marek Karpinski Alexander Zelikovskyy Abstract The Steiner tree problem requires to nd a shortest tree connecting a given set of terminal points in a metric space. We design approximation algorithms for the Steiner problems in graphs

Eckmiller, Rolf

311

New Approximation Algorithms for the Steiner Trees Problems Marek Karpinski \\Lambda Alexander Zelikovsky y  

E-print Network

New Approximation Algorithms for the Steiner Trees Problems Marek Karpinski \\Lambda Alexander Zelikovsky y Abstract The Steiner tree problem requires to find a shortest tree connecting a given set of terminal points in a metric space. We design approximation algorithms for the Steiner problems in graphs

Eckmiller, Rolf

312

New Approximation Algorithms for the Steiner Tree Problems Marek Karpinski \\Lambda Alexander Zelikovsky y  

E-print Network

New Approximation Algorithms for the Steiner Tree Problems Marek Karpinski \\Lambda Alexander Zelikovsky y Abstract The Steiner tree problem asks for the shortest tree connecting a given set of terminal points in a metric space. We design new approximation algorithms for the Steiner tree problems using

Zelikovsky, Alexander

313

Path Following Mobile Robot in the Presence of Velocity Constraints  

E-print Network

Path Following Mobile Robot in the Presence of Velocity Constraints Martin Bak , Niels Kjølstad@imm.dtu.dk Abstract This paper focuses on path following algorithms for mobile robots with velocity constraints the robot through the turnings while fulfilling the velocity constraints. Keywords: Mobile Robots

314

Path planning for a humanoid using NURBS curves  

Microsoft Academic Search

In this paper we present an algorithm for planning the path of a 3 DOF mobile platform for a humanoid robot. It is simple enough to be executed online and yet powerful enough to generate a smooth path from starting point and orientation to a destination point with a different orientation. Thus we strive to achieve a human-like appearance of

Andreas J. Schmid; Heinz Woern

2005-01-01

315

Path Planning for a Humanoid Robot Using NURBS Curves  

Microsoft Academic Search

In this paper we present an algorithm for planning the path of a 3 DOF mobile platform for a humanoid robot. It is simple enough to be executed online and yet powerful enough to generate a smooth path from starting point and orientation to a destination point with a different orientation. Thus we strive to achieve a human-like appearance of

Andreas J. Schmid; Heinz Woern

316

Attention trees and semantic paths  

NASA Astrophysics Data System (ADS)

In the last few decades several techniques for image content extraction, often based on segmentation, have been proposed. It has been suggested that under the assumption of very general image content, segmentation becomes unstable and classification becomes unreliable. According to recent psychological theories, certain image regions attract the attention of human observers more than others and, generally, the image main meaning appears concentrated in those regions. Initially, regions attracting our attention are perceived as a whole and hypotheses on their content are formulated; successively the components of those regions are carefully analyzed and a more precise interpretation is reached. It is interesting to observe that an image decomposition process performed according to these psychological visual attention theories might present advantages with respect to a traditional segmentation approach. In this paper we propose an automatic procedure generating image decomposition based on the detection of visual attention regions. A new clustering algorithm taking advantage of the Delaunay- Voronoi diagrams for achieving the decomposition target is proposed. By applying that algorithm recursively, starting from the whole image, a transformation of the image into a tree of related meaningful regions is obtained (Attention Tree). Successively, a semantic interpretation of the leaf nodes is carried out by using a structure of Neural Networks (Neural Tree) assisted by a knowledge base (Ontology Net). Starting from leaf nodes, paths toward the root node across the Attention Tree are attempted. The task of the path consists in relating the semantics of each child-parent node pair and, consequently, in merging the corresponding image regions. The relationship detected in this way between two tree nodes generates, as a result, the extension of the interpreted image area through each step of the path. The construction of several Attention Trees has been performed and partial results will be shown.

Giusti, Christian; Pieroni, Goffredo G.; Pieroni, Laura

2007-02-01

317

Path Integrals and Hamiltonians  

NASA Astrophysics Data System (ADS)

1. Synopsis; Part I. Fundamental Principles: 2. The mathematical structure of quantum mechanics; 3. Operators; 4. The Feynman path integral; 5. Hamiltonian mechanics; 6. Path integral quantization; Part II. Stochastic Processes: 7. Stochastic systems; Part III. Discrete Degrees of Freedom: 8. Ising model; 9. Ising model: magnetic field; 10. Fermions; Part IV. Quadratic Path Integrals: 11. Simple harmonic oscillators; 12. Gaussian path integrals; Part V. Action with Acceleration: 13. Acceleration Lagrangian; 14. Pseudo-Hermitian Euclidean Hamiltonian; 15. Non-Hermitian Hamiltonian: Jordan blocks; 16. The quartic potential: instantons; 17. Compact degrees of freedom; Index.

Baaquie, Belal E.

2014-03-01

318

Complexity of parallel algorithms  

SciTech Connect

This thesis addresses a number of theoretical issues in parallel computation. There are many open questions relating to what can be done with parallel computers and what are the most effective techniques to use to develop parallel algorithms. The author examines various problems in hope of gaining insight to the general questions. One topic investigated is the relationship between sequential and parallel algorithms. Introduced is the concept of a P-complete algorithm to capture what it means for an algorithm to be inherently sequential . It is shown that a number of sequential greedy algorithms are P-complete, including the greedy algorithm for finding a path in a graph. However, a problem is not necessarily difficult if an algorithm to solve it is P-complete. In some cases, the natural sequential algorithm is P-complete but a different technique gives a fast parallel algorithm. This shows that it is necessary to use different techniques for parallel computation than are used for sequential computation. Fast parallel algorithms for a number of simple graph theory problems are given. The algorithms illustrate a number of different techniques that are useful for parallel algorithms. The final topic that we address is parallel approximation of P-complete problems.

Anderson

1985-11-01

319

Iron(III) catalyzed direct synthesis of cis-2,7-disubstituted oxepanes. The shortest total synthesis of (+)-isolaurepan.  

PubMed

Prins cyclization of bis-homoallylic alcohols with aldehydes catalyzed by iron(III) salts shows excellent cis selectivity and yields to form 2,7-disubstituted oxepanes. The iron(III) is able to catalyze this process with unactivated olefins. This cyclization was used as the key step in the shortest total synthesis of (+)-isolaurepan. PMID:23167915

Purino, Martín A; Ramírez, Miguel A; Daranas, Antonio H; Martín, Víctor S; Padrón, Juan I

2012-12-01

320

Bootlegging and path dependency  

Microsoft Academic Search

This paper confirms the importance of path dependency in the accumulation of firm-specific technological competencies. It shows that firms are guided by the selective logic of path dependency in their innovation processes, even if management has no part in decisions to invest in a new business idea. The research focuses on the output of bootlegging, defined as research in which

Peter Augsdorfer

2005-01-01

321

The SunPath  

NSDL National Science Digital Library

This site features an interactive applet that models the Sun's path from a geocentric view. It calculates and visualizes the position of the Sun based on latitude and time, and allows students to simulate the Sun's position and path for an hour, a day, a month or a year.

University, Australian N.

322

Call-graph-based inter-class MM path generation  

NASA Astrophysics Data System (ADS)

Inter-class testing is the testing of classes for composing an object-oriented system or subsystem during integration. MM Path is defined as an interleaved sequence of method executions linked by messages. It represents the interactions between methods in object-oriented software well, hence fits for object-oriented integration testing. However, the current MM Path generation methods only support intra-class testing. In this paper, a call-graph-based approach is proposed to promote MM Path automatic generation from intra-class to inter-class level. The approach is evaluated by controlled experiments on 12 Java benchmark programs with two typical call graph construction algorithms, Class Hierarchy Analysis and Anderson's Points-to Analysis. Then, the impact of the two algorithms on inter-class MM path generation efficiency is studied. The result shows that our approach is practicable and Anderson's Points-to Analysis outperforms Class Hierarchy Analysis for inter-class MM Path generation.

He, Wei; Zhao, Ruilian

2012-01-01

323

Dynamic Task Assignment and Path Planning of Multi-AUV System Based on an Improved Self-Organizing Map and Velocity Synthesis Method in Three-Dimensional Underwater Workspace.  

PubMed

For a 3-D underwater workspace with a variable ocean current, an integrated multiple autonomous underwater vehicle (AUV) dynamic task assignment and path planning algorithm is proposed by combing the improved self-organizing map (SOM) neural network and a novel velocity synthesis approach. The goal is to control a team of AUVs to reach all appointed target locations for only one time on the premise of workload balance and energy sufficiency while guaranteeing the least total and individual consumption in the presence of the variable ocean current. First, the SOM neuron network is developed to assign a team of AUVs to achieve multiple target locations in 3-D ocean environment. The working process involves special definition of the initial neural weights of the SOM network, the rule to select the winner, the computation of the neighborhood function, and the method to update weights. Then, the velocity synthesis approach is applied to plan the shortest path for each AUV to visit the corresponding target in a dynamic environment subject to the ocean current being variable and targets being movable. Lastly, to demonstrate the effectiveness of the proposed approach, simulation results are given in this paper. PMID:22949070

Zhu, Daqi; Huang, Huan; Yang, Simon X

2012-08-27

324

Towards real implementations of dynamic robust routing exploiting path diversity  

Microsoft Academic Search

In this paper we compare the performance of tree different dynamic traffic engineering algorithms exploiting path diversity in the Internet, TEXCP, TRUMP and MIRTO. We passed through a thorough implementation phase of these algorithms solving a number of issues related to protocol imple- mentation that allows a complete analysis in real traffic settings in real networks. We discuss the performance

Luca Muscariello; Diego Perino; Bruno Nardelli

2009-01-01

325

Farmwork path planning for field coverage with minimum overlapping  

Microsoft Academic Search

This paper presents a path planning algorithm for a tractor to execute specific farmwork tasks requiring the complete coverage of a field while minimizing the overlapping between successive passages. The proposed method is based on the determination of a set of characteristic points from which a graph is defined. The covering trajectory is determined by means of a greedy algorithm

S. Fabre; P. Soures; M. Taix; L. Cordesses

2001-01-01

326

PathFinder: a negotiation-based performance-driven router for FPGAs  

Microsoft Academic Search

Routing FPGAs is a challenging problem because of the relative scarcity of routing resources, both wires and connection points. This can lead either to slow implementations caused by long wiring paths that avoid congestion or a failure to route all signals. This paper presents PathFinder, a router that balances the goals of performance and routability. PathFinder uses an iterative algorithm

Larry McMurchie; Carl Ebeling

1995-01-01

327

Impact of transmission performance on path routing in all-optical transport networks  

Microsoft Academic Search

The impact of transmission related issues on the routing strategies for transparent all-optical wavelength division multiplexed (WDM) transport networks is analyzed in this paper. Three different categories of routing algorithms are analyzed: algorithms based on the wavelength path (WP) strategy, based on the virtual wavelength path (VWP) strategy and requiring only a limited number of wavelength converters in the network

Roberto Sabella; Eugenio Iannone; Marco Listanti; Massimo Berdusco; Stefano Binetti

1998-01-01

328

On the stability of paths, Steiner trees and connected dominating sets in mobile ad hoc networks  

Microsoft Academic Search

We propose algorithms that use the complete knowledge of future topology changes to set up benchmarks for the minimum number of times a communication structure (like paths, trees, connected dominating sets, etc.) should change in the presence of a dynamically changing topology. We first present an efficient algorithm called OptPathTrans that operates on a simple greedy principle: whenever a new

Natarajan Meghanathan; Andras Farago

2008-01-01

329

Automated CAD-guided robot path planning for spray painting of compound surfaces  

Microsoft Academic Search

In this paper, a CAD-guided robot path generator is developed for the spray painting of compound surfaces commonly seen in automotive manufacturing. Instead of widely used parametric representation of surfaces, a planar facet scheme is used to approximate the painting surfaces. As a result, a new combinatorial gun path planning algorithm is proposed. In this algorithm, big patches are formed

Weihua Sheng; Ning Xi; Mumin Song; Yifan Chen; Perry Macneille

2000-01-01

330

Longest jobs first algorithm in solving job shop scheduling using adaptive genetic algorithm (GA)  

NASA Astrophysics Data System (ADS)

In this paper, genetic algorithm was used to solve job shop scheduling problems. One example discussed in JSSP (Job Shop Scheduling Problem) and I described how we can solve such these problems by genetic algorithm. The goal in JSSP is to gain the shortest process time. Furthermore I proposed a method to obtain best performance on performing all jobs in shortest time. The method mainly, is according to Genetic algorithm (GA) and crossing over between parents always follows the rule which the longest process is at the first in the job queue. In the other word chromosomes is suggested to sorts based on the longest processes to shortest i.e. "longest job first" says firstly look which machine contains most processing time during its performing all its jobs and that is the bottleneck. Secondly, start sort those jobs which are belonging to that specific machine descending. Based on the achieved results," longest jobs first" is the optimized status in job shop scheduling problems. In our results the accuracy would grow up to 94.7% for total processing time and the method improved 4% the accuracy of performing all jobs in the presented example.

Alizadeh Sahzabi, Vahid; Karimi, Iman; Alizadeh Sahzabi, Navid; Mamaani Barnaghi, Peiman

2012-01-01

331

Quickest Paths for Different Network Router Mechanisms  

SciTech Connect

The quickest path problem deals with the transmission of a message of size {sigma} from a source to a destination with the minimum end-to-end delay over a network with bandwidth and delay constraints on the links. The authors consider four basic modes and two variations for the message delivery at the nodes reflecting the mechanisms such as circuit switching, Internet protocol, and their combinations. For each of the first three modes, they present O(m{sup 2} + mn log n) time algorithm to compute the quickest path for a given message size {sigma}. For the last mode, the quickest path can be computed in O(m + n log n) time.

Rao, N.S.V.; Grimmell, W.C.; Radhakrishnan, S.; Bang, Y.C.

2000-06-01

332

Path integral learning of multidimensional movement trajectories  

NASA Astrophysics Data System (ADS)

This paper explores the use of Path Integral Methods, particularly several variants of the recent Path Integral Policy Improvement (PI2) algorithm in multidimensional movement parametrized policy learning. We rely on Dynamic Movement Primitives (DMPs) to codify discrete and rhythmic trajectories, and apply the PI2-CMA and PIBB methods in the learning of optimal policy parameters, according to different cost functions that inherently encode movement objectives. Additionally we merge both of these variants and propose the PIBB-CMA algorithm, comparing all of them with the vanilla version of PI2. From the obtained results we conclude that PIBB-CMA surpasses all other methods in terms of convergence speed and iterative final cost, which leads to an increased interest in its application to more complex robotic problems.

André, João; Santos, Cristina; Costa, Lino

2013-10-01

333

Tortuous path chemical preconcentrator  

DOEpatents

A non-planar, tortuous path chemical preconcentrator has a high internal surface area having a heatable sorptive coating that can be used to selectively collect and concentrate one or more chemical species of interest from a fluid stream that can be rapidly released as a concentrated plug into an analytical or microanalytical chain for separation and detection. The non-planar chemical preconcentrator comprises a sorptive support structure having a tortuous flow path. The tortuosity provides repeated twists, turns, and bends to the flow, thereby increasing the interfacial contact between sample fluid stream and the sorptive material. The tortuous path also provides more opportunities for desorption and readsorption of volatile species. Further, the thermal efficiency of the tortuous path chemical preconcentrator is comparable or superior to the prior non-planar chemical preconcentrator. Finally, the tortuosity can be varied in different directions to optimize flow rates during the adsorption and desorption phases of operation of the preconcentrator.

Manginell, Ronald P. (Albuquerque, NM); Lewis, Patrick R. (Albuquerque, NM); Adkins, Douglas R. (Albuquerque, NM); Wheeler, David R. (Albuquerque, NM); Simonson, Robert J. (Cedar Crest, NM)

2010-09-21

334

Accretion disc mapping of the shortest period eclipsing binary SDSS J0926+36  

NASA Astrophysics Data System (ADS)

AM CVn stars are ultracompact binaries (P_{orb}< 65 min) where a hydrogen-deficient low-mass, degenerate donor star overfills its Roche lobe and transfers matter to a companion white dwarf via an accretion disc. SDSS J0926+36 is currently the only eclipsing AM CVn star and also the shortest period eclipsing binary known. Its light curve displays deep (˜ 2 mag) eclipses every 28.3 min, which last for ˜ 2 min, as well as ˜ 2 mag amplitude outbursts every ˜ 100-200 d. Superhumps were seen in its quiescent light curve in some occasions, probably as a reminiscence of a (in some cases undetected) previous outburst. Its eclipsing nature allows a unique opportunity to disentangle the emission from several different light sources, and to map the surface brightness distribution of its hydrogen-deficient accretion disc with the aid of maximum entropy eclipse mapping techniques. Here we report the eclipse mapping analysis of optical light curves of SDSS J0926+36, collected with the 2.4 m Liverpool Robotic Telescope, covering 20 orbits of the binary over 5 nights of observations between 2012 February and March. The object was in quiescence at all runs. Our data show no evidence of superhumps nor of orbital modulation due to anisotropic emission from a bright spot at disc rim. Accordingly, the average out-of-eclipse flux level is consistent with that of the superhump-subtracted previous light curves. We combined all runs to obtain an orbital light curve of improved S/N. The corresponding eclipse map shows a compact source at disc centre (T_{b}simeq 17000 K), a faint, cool accretion disc (˜ 4000 K) plus enhanced emission along the gas stream (˜ 6000 K) beyond the impact point at the outer disc rim, suggesting the occurrence of gas stream overflow at that epoch.

Schlindwein, W.; Baptista, R.

2014-10-01

335

NLTT 5306: the shortest period detached white dwarf+brown dwarf binary  

NASA Astrophysics Data System (ADS)

We have spectroscopically confirmed a brown dwarf mass companion to the hydrogen atmosphere white dwarf NLTT 5306. The white dwarf's atmospheric parameters were measured using the Sloan Digital Sky Survey and X-shooter spectroscopy as Teff = 7756 ± 35 K and log(g) = 7.68 ± 0.08, giving a mass for the primary of MWD = 0.44 ± 0.04 M? at a distance of 71 ± 4 pc with a cooling age of 710 ± 50 Myr. The existence of the brown dwarf secondary was confirmed through the near-infrared arm of the X-shooter data and a spectral type of dL4-dL7 was estimated using standard spectral indices. Combined radial velocity measurements from the Sloan Digital Sky Survey, X-shooter and the Hobby-Eberly Telescope's High Resolution Spectrograph of the white dwarf give a minimum mass of 56 ± 3 MJup for the secondary, confirming the substellar nature. The period of the binary was measured as 101.88 ± 0.02 min using both the radial velocity data and i'-band variability detected with the Isaac Newton Telescope. This variability indicates `day' side heating of the brown dwarf companion. We also observe H? emission in our higher resolution data in phase with the white dwarf radial velocity, indicating that this system is in a low level of accretion, most likely via a stellar wind. This system represents the shortest period white dwarf+brown dwarf binary and the secondary has survived a stage of common envelope evolution, much like its longer period counterpart, WD 0137-349. Both systems likely represent bona fide progenitors of cataclysmic variables with a low-mass white dwarf and a brown dwarf donor.

Steele, P. R.; Saglia, R. P.; Burleigh, M. R.; Marsh, T. R.; Gänsicke, B. T.; Lawrie, K.; Cappetta, M.; Girven, J.; Napiwotzki, R.

2013-03-01

336

AH Cam: A metal-rich RR Lyrae star with the shortest known Blazhko period  

NASA Technical Reports Server (NTRS)

Analysis of 746 new V-band observations of the RR Lyrae star AH Cam obtained during 1989 - 1992 clearly show that its light curve cannot be described by a single period. In fact, at first glance, the Fourier spectrum of the photometry resembles that of a double-mode pulsator, with peaks at a fundamental period of 0.3686 d and an apparent secondary period of 0.2628 d. Nevertheless, the dual-mode solution is a poor fit to the data. Rather, we believe that AH Cam is a single-mode RR Lyrae star undergoing the Blazhko effect: periodic modulation of the amplitude and shape of its light curve. What was originally taken to be the period of the second mode is instead the 1-cycle/d alias of a modulation sidelobe in the Fourier spectrum. The data are well described by a modulation period of just under 11 d, which is the shortest Blazhko period reported to date in the literature and confirms the earlier suggestion by Goranskii. A low-resolution spectrum of AH Cam indicates that it is relatively metal rich, with delta-S less than or = 2. Its high metallicity and short modulation period may provide a critical test of at least one theory for the Blazhko effect. Moskalik's internal resonance model makes specific predictions of the growth rate of the fundamental model vs fundamental period. AH Cam falls outside the regime of other known Blazhko variables and resonance model predictions, but these are appropriate for metal-poor RR Lyrae stars. If the theory matches the behavior of AH Cam for a metal-rich stellar model, this would bolster the resonance hypothesis.

Smith, Horace A.; Matthews, Jaymie M.; Lee, Kevin M.; Williams, Jeffrey; Silbermann, N. A.; Bolte, Michael

1994-01-01

337

Ad-Hoc Analysis of Synop Observations to enhance shortest-term wind power predictions  

NASA Astrophysics Data System (ADS)

Shortest term wind power predictions with forecast horizons less than 12 hours benefit from observed data. So comparison between Synop observations and numerical weather predictions can serve as assessment of the available forecasts. This ad-hoc analysis depends very much on the observed data whose spatial distribution is very patchy in some areas. A powerful interpolation method helps to create a correct representation of the observed fields. The Kriging method finds a correlation function which describes the variation of the spatial field best. An unknown data point is estimated by weighted observation points, taking distance and clustering effects into account. We use mean sea level pressure data measured at Synop and ship stations in Europe and the Atlantic to assess the quality of the predicted mean sea level pressure from Numerical Weather Prediction models. Those models serve as base of wind power predictions and influence the prediction error considerably. If this error can be estimated, a rating of different Numerical Weather Prediction Models which are taken into consideration can follow. The choice of the area that represents the area of interest in terms of prediction errors depend on the moving direction of the low pressure systems. First calculations show that errors of the ad-hoc analysis are in good agreement with the ECMWF analysis. The evaluation of the ad-hoc analysis in an area over Great Britain/North Sea and the comparison with available ECMWF forecasts over Germany reveals phase shifts for some time intervals. This supports the assumption of moving prediction errors along low pressure systems.

Busch-Saleck, N.; von Bremen, L.

2010-09-01

338

Partial charge transfer in the shortest possible metallofullerene peapod, la@c82 ?[11]cycloparaphenylene.  

PubMed

[11]Cycloparaphenylene ([11]CPP) selectively encapsulates La@C82 to form the shortest possible metallofullerene-carbon nanotube (CNT) peapod, La@C82 ?[11]CPP, in solution and in the solid state. Complexation in solution was affected by the polarity of the solvent and was 16?times stronger in the polar solvent nitrobenzene than in the nonpolar solvent 1,2-dichlorobenzene. Electrochemical analysis revealed that the redox potentials of La@C82 were negatively shifted upon complexation from free La@C82 . Furthermore, the shifts in the redox potentials increased with polarity of the solvent. These results are consistent with formation of a polar complex, (La@C82 )(?-) ?[11]CPP(?+) , by partial electron transfer from [11]CPP to La@C82 . This is the first observation of such an electronic interaction between a fullerene pea and CPP pod. Theoretical calculations also supported partial charge transfer (0.07) from [11]CPP to La@C82 . The structure of the complex was unambiguously determined by X-ray crystallographic analysis, which showed the La atom inside the C82 near the periphery of the [11]CPP. The dipole moment of La@C82 was projected toward the CPP pea, nearly perpendicular to the CPP axis. The position of the La atom and the direction of the dipole moment in La@C82 ?[11]CPP were significantly different from those observed in La@C82 ?CNT, thus indicating a difference in orientation of the fullerene peas between fullerene-CPP and fullerene-CNT peapods. These results highlight the importance of pea-pea interactions in determining the orientation of the metallofullerene in metallofullerene-CNT peapods. PMID:25224281

Iwamoto, Takahiro; Slanina, Zdenek; Mizorogi, Naomi; Guo, Jingdong; Akasaka, Takeshi; Nagase, Shigeru; Takaya, Hikaru; Yasuda, Nobuhiro; Kato, Tatsuhisa; Yamago, Shigeru

2014-10-27

339

The reweighted path ensemble.  

PubMed

We introduce a reweighting scheme for the path ensembles in the transition interface sampling framework. The reweighting allows for the analysis of free energy landscapes and committor projections in any collective variable space. We illustrate the reweighting scheme on a two dimensional potential with a nonlinear reaction coordinate and on a more realistic simulation of the Trp-cage folding process. We suggest that the reweighted path ensemble can be used to optimize possible nonlinear reaction coordinates. PMID:21054008

Rogal, Jutta; Lechner, Wolfgang; Juraszek, Jarek; Ensing, Bernd; Bolhuis, Peter G

2010-11-01

340

Predicting Tor path compromise by exit port  

Microsoft Academic Search

Abstract—Tor is currently the most,popular low,latency anonymizing overlay network for TCP-based applications. How- ever, it is well understood that Tor’s path selection algorithm is vulnerable to end-to-end traffic correlation attacks since it chooses Tor routers in proportion to their perceived bandwidth capabilities. Prior work has shown that the fraction of malicious routers and the amount,of adversary-controlled bandwidth are significant factors

Kevin S. Bauer; Dirk Grunwald; Douglas C. Sicker

2009-01-01

341

Joint subcarrier channel and time slots allocation algorithm in OFDMA passive optical networks  

NASA Astrophysics Data System (ADS)

This paper investigates upstream resource allocation problem in Orthogonal Frequency Division Multiplexing Access Passive Optical Networks (OFDMA-PON). One assignment problem with subcarrier channel utilization and Total Grant Time (TGT) is analyzed and formulated. The Shortest Request First Scheduling (SRF) algorithm and Greedy Scheduling Algorithm (GSA) are demonstrated and evaluated through simulations. The results show that the proposed algorithms achieve less TGT and higher channel utilization compared with traditional sequence scheme.

Bi, Meihua; Xiao, Shilin; Wang, Li

2013-01-01

342

Image-based path planning for automated virtual colonoscopy navigation  

NASA Astrophysics Data System (ADS)

Virtual colonoscopy (VC) is a noninvasive method for colonic polyp screening, by reconstructing three-dimensional models of the colon using computerized tomography (CT). In virtual colonoscopy fly-through navigation, it is crucial to generate an optimal camera path for efficient clinical examination. In conventional methods, the centerline of the colon lumen is usually used as the camera path. In order to extract colon centerline, some time consuming pre-processing algorithms must be performed before the fly-through navigation, such as colon segmentation, distance transformation, or topological thinning. In this paper, we present an efficient image-based path planning algorithm for automated virtual colonoscopy fly-through navigation without the requirement of any pre-processing. Our algorithm only needs the physician to provide a seed point as the starting camera position using 2D axial CT images. A wide angle fisheye camera model is used to generate a depth image from the current camera position. Two types of navigational landmarks, safe regions and target regions are extracted from the depth images. Camera position and its corresponding view direction are then determined using these landmarks. The experimental results show that the generated paths are accurate and increase the user comfort during the fly-through navigation. Moreover, because of the efficiency of our path planning algorithm and rendering algorithm, our VC fly-through navigation system can still guarantee 30 FPS.

Hong, Wei

2008-03-01

343

Multipath Binomial Congestion Control Algorithms  

NASA Astrophysics Data System (ADS)

Nowadays portable devices with multiple wireless interfaces and using multimedia services are becoming more popular on the Internet. This paper describes a family of multipath binomial congestion control algorithms for audio/video streaming, where a low variant of transmission rate is important. We extend the fluid model of binomial algorithms for single-path transmission to support the concurrent transmission of packets across multiple paths. We focus on the extension of two particular algorithms, SQRT and IIAD, for multiple paths, called MPSQRT and MPIIAD, respectively. Additionally, we apply the design technique (using the multipath fluid model) for multipath TCP (MPTCP) into the extension of SQRT and IIAD, called fbMPSQRT and fbMPIIAD, respectively. Both two approaches ensure that multipath binomial congestion control algorithms achieve load-balancing, throughput improvement, and fairness to single-path binomial algorithms at shared bottlenecks. Through the simulations and comparison with the uncoordinated protocols MPSQRT/MPIIAD, fbMPSQRT/fbMPIIAD and MPTCP, we find that our extended multipath transport protocols can preserve lower latency and transmission rate variance than MPTCP, fairly share with single-path SQRT/IIAD, MPTCP and TCP, and also can achieve throughput improvements and load-balancing equivalent to those of MPTCP under various scenarios and network conditions.

Le, Tuan Anh; Hong, Choong Seon; Lee, Sungwon

344

The dynamic, resource-constrained shortest path problem on an acyclic graph with application in column generation and literature review on sequence-dependent scheduling  

E-print Network

of scheduling problems that involve SDS times (costs), an important consideration in many practical applications. It focuses on papers published within the last decade, addressing a variety of machine configurations - single machine, parallel machine, flow shop...

Zhu, Xiaoyan

2007-04-25

345

Adaptive robot path planning in changing environments  

SciTech Connect

Path planning needs to be fast to facilitate real-time robot programming. Unfortunately, current planning techniques are still too slow to be effective, as they often require several minutes, if not hours of computation. To overcome this difficulty, we present an adaptive algorithm that uses past experience to speed up future performance. It is a learning algorithm suitable for incrementally-changing environments such as those encountered in manufacturing of evolving products and waste-site remediation. The algorithm allows the robot to adapt to its environment by having two experience manipulation schemes: For minor environmental change, we use an object-attached experience abstraction scheme to increase the flexibility of the learned experience; for major environmental change, we use an on-demand experience repair scheme to retain those experiences that remain valid and useful. Using this algorithm, we can effectively reduce the overall robot planning time by re-using the computation result for one task to plan a path for another.

Chen, P.C.

1994-08-01

346

Birds tended to display greater predator anxiety in mesic parks (Fig. 3), but birds in Palomino Park, a xeric park with low shrub density, cats, and no coyotes exhibited the greatest predator anxiety, i.e. shortest open foraging durations and shortest dis  

E-print Network

Results Birds tended to display greater predator anxiety in mesic parks (Fig. 3), but birds anxiety, i.e. shortest open foraging durations and shortest distances from cover (not shown). As predicted) significantly correlated with foraging anxiety. Sample sizes were too small to distinguish between effects

Hall, Sharon J.

347

Fairness in optimal routing algorithms  

E-print Network

. Tsei Dr. Pierce E. Cantrell A study of fairness in multiple path optimal routing algorithms is discussed. Fair- ness measures are developed to evaluate multiple path routing in virtual circuit and datagram implementations. Several objective.... One objective function is shown to have perfect fairness for virtual circuits. The objective function optimized was shown to have little effect on the average packet delay. To my parents and my brother ACKNOWLEDGMENTS I wish to express my...

Goos, Jeffrey Alan

2012-06-07

348

Identifying codes and locating–dominating sets on paths and cycles  

Microsoft Academic Search

Let G=(V,E) be a graph and let r?1 be an integer. For a set D?V, define Nr[x]={y?V:d(x,y)?r} and Dr(x)=Nr[x]?D, where d(x,y) denotes the number of edges in any shortest path between x and y. D is known as an r-identifying code (r-locating-dominating set, respectively), if for all vertices x?V (x?V?D, respectively), Dr(x) are all nonempty and different. Roberts and Roberts

Chunxia Chen; Changhong Lu; Zhengke Miao

2011-01-01

349

Gas Path Seal.  

National Technical Information Service (NTIS)

A gas path seal suitable for use with a turbine engine or compressor is described. A shroud wearable or abradable by the abrasion of the rotor blades of the turbine or compressor shrouds the rotor bades. A compliant backing surrounds the shroud. The backi...

R. C. Bill, R. D. Johnson

1979-01-01

350

DNA Computing Hamiltonian path  

E-print Network

2014 DNA DNA #12;DNA Computing · Feynman · Adleman · DNASIMD · ... · · · · · DNADNA #12;DNA · DNA · · · · DNA · · #12;2000 2005 2010 1995 Hamiltonian path DNA tweezers DNA tile DNA origami DNA box Sierpinski DNA tile self assembly DNA logic gates Whiplash PCR DNA automaton DNA spider MAYA

Hagiya, Masami

351

World nuclear energy paths  

Microsoft Academic Search

In examing the world nuclear energy paths, the following assumptions were adopted: the world economy will grow somewhat more slowly than in the past, leading to reductions in electricity demand growth rates; national and international political impediments to the deployment of nuclear power will gradually disappear over the next few years; further development of nuclear power will proceed steadily, without

T. J. Connolly; U. Hansen; W. Jaek; K. H. Beckurts

1979-01-01

352

Off the Beaten Path.  

ERIC Educational Resources Information Center

Describes "Off the Beaten Path", a program that takes at-risk students out of the traditional classroom and puts them into a camping atmosphere in order to increase academic achievement, improve self-esteem, and promote better social skills. (WRM)

Grimm, Karen

1999-01-01

353

An Unplanned Path  

ERIC Educational Resources Information Center

The authors elucidate what they saw as three important challenges to overcome along the path to becoming elementary school mathematics teacher leaders: marginal interest in math, low self-confidence, and teaching in isolation. To illustrate how these challenges were mitigated, they focus on the stories of two elementary school teachers--Laura and…

McGarvey, Lynn M.; Sterenberg, Gladys Y.; Long, Julie S.

2013-01-01

354

Path planning for machine vision assisted, teleoperated pavement crack sealer  

SciTech Connect

During the last few years, several teleoperated and machine-vision-assisted systems have been developed in construction and maintenance areas such as pavement crack sealing, sewer pipe rehabilitation, excavation, surface finishing, and materials handling. This paper presents a path-planning algorithm used for a machine-vision-assisted automatic pavement crack sealing system. In general, path planning is an important task for optimal motion of a robot whether its environment is structured or unstructured. Manual path planning is not always possible or desirable. A simple greedy path algorithm is utilized for optimal motion of the automated pavement crack sealer. Some unique and broadly applicable computational tools and data structures are required to implement the algorithm in a digital image domain. These components are described, then the performance of the algorithm is compared with the implicit manual path plans of system operators. The comparison is based on computational cost versus overall gains in crack-sealing-process efficiency. Applications of this work in teleoperation, graphical control, and other infrastructure maintenance areas are also suggested.

Kim, Y.S.; Haas, C.T.; Greer, R. [Univ. of Texas, Austin, TX (United States)

1998-03-01

355

Approximation Algorithms for Average Stretch Scheduling Michael A. Bender 1 S. Muthukrishnan 2 Rajmohan Rajaraman 3  

E-print Network

of jobs on a single processor. Consider an online stream of jobs, and let the ith job arrive at time r-time approximation factor of 2 achieved by the online algorithm srpt, that always schedules a job with the shortest uniprocessing scheduling scenario. We have a single processor that processes jobs as they arrive online. The ith

Rajaraman, Rajmohan

356

Approximation Algorithms for Average Stretch Scheduling Michael A. Bender 1 S. Muthukrishnan 2 Rajmohan Rajaraman 3  

E-print Network

of jobs on a single processor. Consider an online stream of jobs, and let the ith job arrive at time r by the online algorithm srpt that always schedules a job with the shortest remaining processing time. In recent have a single processor that processes jobs as they arrive online. The ith job arrives at time r

Bender, Michael

357

A Constant-Factor Approximation Algorithm for TSP with Neighborhoods in the Plane  

E-print Network

A Constant-Factor Approximation Algorithm for TSP with Neighborhoods in the Plane Joseph S. B. Mitchell Abstract In the Euclidean TSP with neighborhoods (TSPN) problem we seek a shortest tour a PTAS by the results of Arora [2], Mitchell [15, 14], and Rao and Smith [19], the TSP with neighborhoods

Mitchell, Joseph S.B.

358

The traffic equilibrium problem with nonadditive path costs  

SciTech Connect

In this paper the authors present a version of the (static) traffic equilibrium problem in which the cost incurred on a path is not simply the sum of the costs on the arcs that constitute that path. The authors motivate this nonadditive version of the problem by describing several situations in which the classical additivity assumption fails. They also present an algorithm for solving nonadditive problems that is based on the recent NE/SQP algorithm, a fast and robust method for the nonlinear complementarity problem. Finally, they present a small example that illustrates both the importance of using nonadditive costs and the effectiveness of the NE/SQP method.

Gabriel, S.A. [Argonne National Lab., IL (United States). Mathematics and Computer Science Div.; Bernstein, D. [Princeton Univ., NJ (United States). Dept. of Civil Engineering and Operations Research

1995-08-21

359

Some Materials for Discrete Mathematics  

NSDL National Science Digital Library

Files in PDF, DVI, and Postscript format. Contents include: an algorithm for solving linear Diophantine equations, the Chinese remainder theorem, mathematical induction and recursive algorithms, Change of base to Cantor representation, Dijkstra's algorithm for shortest path, and amortization.

Lady, E. L.

2007-03-13

360

Quad-rotor flight path energy optimization  

NASA Astrophysics Data System (ADS)

Quad-Rotor unmanned areal vehicles (UAVs) have been a popular area of research and development in the last decade, especially with the advent of affordable microcontrollers like the MSP 430 and the Raspberry Pi. Path-Energy Optimization is an area that is well developed for linear systems. In this thesis, this idea of path-energy optimization is extended to the nonlinear model of the Quad-rotor UAV. The classical optimization technique is adapted to the nonlinear model that is derived for the problem at hand, coming up with a set of partial differential equations and boundary value conditions to solve these equations. Then, different techniques to implement energy optimization algorithms are tested using simulations in Python. First, a purely nonlinear approach is used. This method is shown to be computationally intensive, with no practical solution available in a reasonable amount of time. Second, heuristic techniques to minimize the energy of the flight path are tested, using Ziegler-Nichols' proportional integral derivative (PID) controller tuning technique. Finally, a brute force look-up table based PID controller is used. Simulation results of the heuristic method show that both reliable control of the system and path-energy optimization are achieved in a reasonable amount of time.

Kemper, Edward

361

Efficiently finding the minimum free energy path from steepest descent path  

NASA Astrophysics Data System (ADS)

Minimum Free Energy Path (MFEP) is very important in computational biology and chemistry. The barrier in the path is related to the reaction rate, and the start-to-end difference gives the relative stability between reactant and product. All these information is significant to experiment and practical application. But finding MFEP is not an easy job. Lots of degrees of freedom make the computation very complicated and time consuming. In this paper, we use the Steepest Descent Path (SDP) to accelerate the sampling of MFEP. The SHAKE algorithm and the Lagrangian multipliers are used to control the optimization of both SDP and MFEP. These strategies are simple and effective. For the former, it is more interesting. Because as we known, SHAKE algorithm was designed to handle the constraints in molecular dynamics in the past, has never been used in geometry optimization. Final applications on ALA dipeptide and 10-ALA peptide show that this combined optimization method works well. Use the information in SDP, the initial path could reach the more optimal MFEP. So more accurate free energies could be obtained and the amount of computation time could be saved.

Chen, Changjun; Huang, Yanzhao; Ji, Xiaofeng; Xiao, Yi

2013-04-01

362

Stabilizing Intelligent Route Control: Randomized Path Monitoring, Randomized Path  

E-print Network

Stabilizing Intelligent Route Control: Randomized Path Monitoring, Randomized Path Switching or History-aware Path Switching? Alexandre Fonte1,2 , Jos´e Martins1 , Marilia Curado1 , and Edmundo Monteiro, Castelo Branco, Portugal Abstract. Multihoming Intelligent Route Control (IRC) plays a signif- icant role

Monteiro, Edmundo

363

Lander flight path analysis  

NASA Technical Reports Server (NTRS)

The primary functions of the Lander Flight Path Analysis Team (LFPAT) were to (1) design the Viking Lander (VL) descent trajectory and compute the descent guidance parameters for command transmission to the Viking Lander and Viking Orbiter (VO), (2) reconstruct the VL trajectory from separation to touchdown using data transmitted from the VL to Earth via the VO during descent, and (3) predict the VL/VO relay link system performance during descent and post touchdown. The preflight VL capability, the history of proposed descent trajectory designs as the site selection process evolved, and the final trajectory design and guidance parameters for each vehicle are addressed along with the trajectory reconstruction process, including the overall reconstructed VL flight path summary and a detailed discussion of the entry trajectory and atmosphere reconstruction results. The postland relay link prediction function is discussed.

Euler, E. A.; Adams, G. L.; Hopper, F. W.

1979-01-01

364

Structural Semi-Join: A light-weight structural join operator for efficient XML path query pattern matching  

Microsoft Academic Search

Optimal evaluation of structural relationships between XML nodes is crucial for efficient processing of XML queries. Though stack-based structural join algorithms showed improved performance over the merge-based algorithms, the algorithms still suffer potential overhead in processing XML path expressions. This is mainly because the existing structural join algorithms have been designed for returning (ancestor, descendant) node pairs even when the

Seokhyun Son; Hyoseop Shin; Zhiwei Xu

2007-01-01

365

IEEE JOURNAL OF ROBOTICS AND AUTOMATION, VOL. FA-3,NO. 2, APRIL 1987 101 Robot Path Planning using Intersecting Convex  

E-print Network

IEEE JOURNAL OF ROBOTICS AND AUTOMATION, VOL. FA-3,NO. 2, APRIL 1987 101 Robot Path Planning using Intersecting Convex Shapes: Analysis and Simulation Abstract-An automated path planning algorithm for a mobile graph arcs, and the graph is searched for a path between source and destination. A disadvantage

Wagh, Meghanad

366

PATHS groundwater hydrologic model  

SciTech Connect

A preliminary evaluation capability for two-dimensional groundwater pollution problems was developed as part of the Transport Modeling Task for the Waste Isolation Safety Assessment Program (WISAP). Our approach was to use the data limitations as a guide in setting the level of modeling detail. PATHS Groundwater Hydrologic Model is the first level (simplest) idealized hybrid analytical/numerical model for two-dimensional, saturated groundwater flow and single component transport; homogeneous geology. This document consists of the description of the PATHS groundwater hydrologic model. The preliminary evaluation capability prepared for WISAP, including the enhancements that were made because of the authors' experience using the earlier capability is described. Appendixes A through D supplement the report as follows: complete derivations of the background equations are provided in Appendix A. Appendix B is a comprehensive set of instructions for users of PATHS. It is written for users who have little or no experience with computers. Appendix C is for the programmer. It contains information on how input parameters are passed between programs in the system. It also contains program listings and test case listing. Appendix D is a definition of terms.

Nelson, R.W.; Schur, J.A.

1980-04-01

367

Interferometric sensors based on sinusoidal optical path length modulation  

NASA Astrophysics Data System (ADS)

Sinusoidal optical path length modulation of the reference or the measurement arm of an interferometer is a technique which is a fast alternative to white light or phase shifting interferometry. In this paper three different sensors using this periodical modulation are presented. In addition, signal processing algorithms based on Discrete Fourier Transform, Hilbert Transform and parameter estimation are analyzed. These algorithms are used to obtain measurement results which demonstrate the capabilities of the presented interferometric sensors.

Knell, Holger; Schake, Markus; Schulz, Markus; Lehmann, Peter

2014-05-01

368

Randomized Algorithms  

Microsoft Academic Search

The last decade has witnessed a tremendous growth in the area of randomized algorithms.During this period, randomized algorithms went from being a tool in computational number theory to finding widespread application in many types of algorithms. Two benefits of randomization have spearheaded this growth: simplicity and speed. For many applications, a randomized algorithm is the simplest algorithm available, or the

Rajeev Motwani; Prabhakax Raghavan

1995-01-01

369

Penetration distances and their applications to path planning  

NASA Astrophysics Data System (ADS)

The proximal relationship of two objects is of interest for many reasons, e.g., the interference detection problem in robot motion planning. When the mathematical representations of two objects are separated the natural measure of the proximal relationship is the shortest Euclidean distance. However, much less is known when the representations intersect. In this dissertation, one of the main foci is the characterization and computation of measures of the proximal relationship between two intersecting objects. We call these measures penetration distances. A formal exposition of penetration distances and their mathematical properties is given. A penetration distance is defined by the least 'movement' needed to separate the two objects. In general, 'movement' involves both rotation and translation. Several ways of measuring the degree of rotation and translation are introduced and each yields a different definition of penetration distance. In the special case of convex objects, it is shown that the various penetration distances are the same and are determined from translational motion alone. The above-mentioned penetration distances are difficult to compute. An important contribution of this thesis is the development of a new penetration distance based on ideas of 'growing' the mathematical representations of objects. It is called the growth distance and can be computed easily for a pair of convex objects. The mathematical properties and computational aspects of the growth distance are developed at length. For instance, its relationship to the other penetration distances is determined. When two objects are separated, the growth distance is also a measure of separation. An important application of the growth distance is to path finding for robotic systems in the presence of obstacles. Our approach is to convert the path finding problem into an optimization problem. path. &This novel approach involves searching among collision paths. Problems unique to this formulation are discussed. Our approach has several advantages over existing approaches and has performed well in several examples.

Ong, Chong Jin

370

Combined Single-Path Routing and Flow Control in Many-User Region: A Case for Nash Efficiency  

E-print Network

Combined Single-Path Routing and Flow Control in Many-User Region: A Case for Nash Efficiency Huigang Chen and John S. Baras Abstract-- We consider the problem of combined single- path routing on the solutions brought out by the simplest local algorithm, the Nash algorithm. We first examine a special type

Baras, John S.

371

MINIMUM WEIGHT PATHS TIMEDEPENDENT NETWORKS  

E-print Network

MINIMUM WEIGHT PATHS in TIME­DEPENDENT NETWORKS Ariel Orda Raphael Rom Department of Electrical) ABSTRACT We investigate the minimum weight path problem in networks whose link weights and link delays weight problem always has a solution. We also characterize the structure of an infinite optimal path

Orda, Ariel

372

Path Following with Slip Compensation for a Mars Rover  

NASA Technical Reports Server (NTRS)

A software system for autonomous operation of a Mars rover is composed of several key algorithms that enable the rover to accurately follow a designated path, compensate for slippage of its wheels on terrain, and reach intended goals. The techniques implemented by the algorithms are visual odometry, full vehicle kinematics, a Kalman filter, and path following with slip compensation. The visual-odometry algorithm tracks distinctive scene features in stereo imagery to estimate rover motion between successively acquired stereo image pairs, by use of a maximum-likelihood motion-estimation algorithm. The full-vehicle kinematics algorithm estimates motion, with a no-slip assumption, from measured wheel rates, steering angles, and angles of rockers and bogies in the rover suspension system. The Kalman filter merges data from an inertial measurement unit (IMU) and the visual-odometry algorithm. The merged estimate is then compared to the kinematic estimate to determine whether and how much slippage has occurred. The kinematic estimate is used to complement the Kalman-filter estimate if no statistically significant slippage has occurred. If slippage has occurred, then a slip vector is calculated by subtracting the current Kalman filter estimate from the kinematic estimate. This slip vector is then used, in conjunction with the inverse kinematics, to determine the wheel velocities and steering angles needed to compensate for slip and follow the desired path.

Helmick, Daniel; Cheng, Yang; Clouse, Daniel; Matthies, Larry; Roumeliotis, Stergios

2005-01-01

373

Optimization Algorithms  

Microsoft Academic Search

\\u000a The right choice of an optimization algorithm can be crucially important in finding the right solutions for a given optimization\\u000a problem. There exist a diverse range of algorithms for optimization, including gradient-based algorithms, derivative-free\\u000a algorithms and metaheuristics. Modern metaheuristic algorithms are often nature-inspired, and they are suitable for global\\u000a optimization. In this chapter, we will briefly introduce optimization algorithms such

Xin-She Yang

374

A combined NLP-differential evolution algorithm approach for the optimization of looped water distribution systems  

NASA Astrophysics Data System (ADS)

This paper proposes a novel optimization approach for the least cost design of looped water distribution systems (WDSs). Three distinct steps are involved in the proposed optimization approach. In the first step, the shortest-distance tree within the looped network is identified using the Dijkstra graph theory algorithm, for which an extension is proposed to find the shortest-distance tree for multisource WDSs. In the second step, a nonlinear programming (NLP) solver is employed to optimize the pipe diameters for the shortest-distance tree (chords of the shortest-distance tree are allocated the minimum allowable pipe sizes). Finally, in the third step, the original looped water network is optimized using a differential evolution (DE) algorithm seeded with diameters in the proximity of the continuous pipe sizes obtained in step two. As such, the proposed optimization approach combines the traditional deterministic optimization technique of NLP with the emerging evolutionary algorithm DE via the proposed network decomposition. The proposed methodology has been tested on four looped WDSs with the number of decision variables ranging from 21 to 454. Results obtained show the proposed approach is able to find optimal solutions with significantly less computational effort than other optimization techniques.

Zheng, Feifei; Simpson, Angus R.; Zecchin, Aaron C.

2011-08-01

375

Start and Stop Rules for Exploratory Path Analysis.  

ERIC Educational Resources Information Center

Describes a method for choosing rejection probabilities for the tests of independence that are used in constraint-based algorithms of exploratory path analysis. The method consists of generating a Markov or semi-Markov model from the equivalence class represented by a partial ancestral graph and then testing the d-separation implications. (SLD)

Shipley, Bill

2002-01-01

376

Allocation of multiport memories in data path synthesis  

Microsoft Academic Search

An algorithm to synthesize registers using multiport memories during data-path synthesis is presented. The proposed approach considers not only the access requirements of registers but also their interconnection to operators in order to minimize required interconnections. The same approach can be applied to select the optimum number of buses in a multibus architecture. The method is illustrated with an example

M. Balakrishnan; Arun K. Majumdar; Dilip K. Banerji; James G. Linders; Jayanti C. Majithia

1988-01-01

377

A method of probabilistic map distribution of path Michel Bierlaire  

E-print Network

in the location data trace and network are taken into account in the method. An algorithm is designed to calculate way to estimate a single true path from a trace of location data. Significant advancements have been ultimately generate a unique result from observations. This paper gives detailed techniques

Bierlaire, Michel

378

Path loss exponent estimation for wireless sensor network localization  

Microsoft Academic Search

The wireless received signal strength (RSS) based localization techniques have attracted significant research interest for their simplicity. The RSS based localization techniques can be divided into two categories: the distance estimation based and the RSS profiling based techniques. The path loss exponent (PLE) is a key parameter in the distance estimation based localization algorithms, where distance is estimated from the

Guoqiang Mao; Brian D. O. Anderson; Baris Fidan

2007-01-01

379

PATH COUPLED ACCOUNTING MECHANISMS FOR "ALL IP NETWORKS"  

E-print Network

PATH COUPLED ACCOUNTING MECHANISMS FOR "ALL IP NETWORKS" Andreas Klenk*, Philipp Schlicker*, Ralph: Accounting, All IP Networks, Meter Selection Algorithms, Distributed Load Balancing, NSIS Abstract Accounting of the services grows the demand for an equally flexible accounting mechanism increases as well. However nowadays

Breu, Ruth

380

Cobra: Parallel path following for computing the matrix pseudospectrum  

Microsoft Academic Search

The construction of an accurate approximation of the ffl-pseudospectrum of a matrixby means of the standard grid method is a demanding computational task, evenfor matrices of medium size. In this paper we describe Cobra, a new domain-basedmethod for the computation of pseudospectra that is a hybrid of the path followingbased algorithm of Bruhl and the standard grid approach. We implement

Constantine Bekas; Efstratios Gallopoulos

2001-01-01

381

Time-Optimal Control of Robotic Manipulators Along Specified Paths  

Microsoft Academic Search

The minimum-time manipulator control problem is solved for the case when the path is specified and the actuator torque limitations are known. The optimal open-loop torques are found, and a method is given for implementing these torques with a conventional linear feedback control system. The algorithm allows bounds on the torques that may be arbitrary functions of the joint angles

J. E. Bobrow; S. Dubowsky; J. S. Gibson

1985-01-01

382

JAVA PathFinder  

NASA Technical Reports Server (NTRS)

JPF is an explicit state software model checker for Java bytecode. Today, JPF is a swiss army knife for all sort of runtime based verification purposes. This basically means JPF is a Java virtual machine that executes your program not just once (like a normal VM), but theoretically in all possible ways, checking for property violations like deadlocks or unhandled exceptions along all potential execution paths. If it finds an error, JPF reports the whole execution that leads to it. Unlike a normal debugger, JPF keeps track of every step how it got to the defect.

Mehhtz, Peter

2005-01-01

383

Byrds Flight Path  

NSDL National Science Digital Library

The Ohio State Universitys Library web site notes As a navigational aviator, Byrd pioneered in the technology that would be the foundation for modern polar exploration and investigation. As a decorated and much celebrated hero, Byrd drew popular attention to areas of the world that became focal points of scientific investigation in numerous disciplines. More information about Admiral Richard E. Byrd can be found at (http:--www.lib.ohio-state.edu-arvweb-polar-byrd-byrd.htm). The next animation, #1001, shows Byrds plane as it follows the flight path presented in this animation.

Biddlecome, Tom; Snodgrass, Stuart; Newcombe, Marte; Jezek, Ken

1999-11-08

384

Identifying codes and locating-dominating sets on paths and cycles  

E-print Network

Let $G=(V,E)$ be a graph and let $r\\ge 1$ be an integer. For a set $D \\subseteq V$, define $N_r[x] = \\{y \\in V: d(x, y) \\leq r\\}$ and $D_r(x) = N_r[x] \\cap D$, where $d(x,y)$ denotes the number of edges in any shortest path between $x$ and $y$. $D$ is known as an $r$-identifying code ($r$-locating-dominating set, respectively), if for all vertices $x\\in V$ ($x \\in V\\backslash D$, respectively), $D_r(x)$ are all nonempty and different. In this paper, we provide complete results for $r$-identifying codes in paths and odd cycles; we also give complete results for 2-locating-dominating sets in cycles.

Chen, Chunxia; Miao, Zhengke

2009-01-01

385

Ant Algorithms for Discrete Optimization  

E-print Network

ant-based al- gorithms to many different discrete optimization problems [5, 21]. Recent applications. Ants can smell pheromone, and when choosing their way, they tend to choose, in probability, pathsAnt Algorithms for Discrete Optimization Marco Dorigo Gianni Di Caro IRIDIA CP 194/6 Universit

Libre de Bruxelles, Université

386

Routing, Wavelength and Time-Slot-Assignment Algorithms for Wavelength-Routed Optical WDM/TDM Networks  

NASA Astrophysics Data System (ADS)

This paper studies the connection-assignment problem for a time-division-multiplexed (TDM) wavelength-routed (WR) optical wavelength-division-multiplexing (WDM) network. In a conventional WR network, an entire wavelength is assigned to a given connection (or session). This can lead to lower channel utilization when individual sessions do not need the entire channel bandwidth. This paper considers a TDM-based approach to reduce this inefficiency, where multiple connections are multiplexed onto each wavelength channel. The resultant network is a TDM-based WR network (TWRN), where the wavelength bandwidth is partitioned into fixed-length time slots organized as a fixed-length frame. Provisioning a connection in such a network involves determining a time-slot assignment, in addition to the route and wavelength. This problem is defined as the routing, wavelength, and time-slot-assignment (RWTA) problem. In this paper, we present a family of RWTA algorithms and study the resulting blocking performance. For routing, we use the existing shortest path routing algorithm with a new link cost function called least resistance weight (LRW) function, which incorporates wavelength-utilization information. For wavelength assignment, we employ the existing least loaded (LL) wavelength selection; and for time-slot allocation, we present the LL time-slot (LLT) algorithm with different variations. Simulation-based analyses are used to compare the proposed TDM architecture to traditional WR networks, both with and without wavelength conversion. The objective is to compare the benefits of TDM and wavelength conversion, relative to WR networks, towards improving performance. The results show that the use of TDM provides substantial gains, especially for multifiber networks.

Wen, Bo; Shenai, Ramakrishna; Sivalingam, Krishna

2005-09-01

387

Solving the Find-Path Problem by Representing Free Space as Generalized Cones  

E-print Network

Free space is represented as a union of (possibly overlapping) generalized cones. An algorithm is presented which efficiently finds good collision free paths for convex polygonal bodies through space littered with ...

Brooks, Rodney A.

1982-05-01

388

Regularization Paths for Generalized Linear Models via Coordinate Descent.  

PubMed

We develop fast algorithms for estimation of generalized linear models with convex penalties. The models include linear regression, two-class logistic regression, and multinomial regression problems while the penalties include ?(1) (the lasso), ?(2) (ridge regression) and mixtures of the two (the elastic net). The algorithms use cyclical coordinate descent, computed along a regularization path. The methods can handle large problems and can also deal efficiently with sparse features. In comparative timings we find that the new algorithms are considerably faster than competing methods. PMID:20808728

Friedman, Jerome; Hastie, Trevor; Tibshirani, Rob

2010-01-01

389

Regularization Paths for Generalized Linear Models via Coordinate Descent  

PubMed Central

We develop fast algorithms for estimation of generalized linear models with convex penalties. The models include linear regression, two-class logistic regression, and multinomial regression problems while the penalties include ?1 (the lasso), ?2 (ridge regression) and mixtures of the two (the elastic net). The algorithms use cyclical coordinate descent, computed along a regularization path. The methods can handle large problems and can also deal efficiently with sparse features. In comparative timings we find that the new algorithms are considerably faster than competing methods. PMID:20808728

Friedman, Jerome; Hastie, Trevor; Tibshirani, Rob

2010-01-01

390

Tool path generation and 3D tolerance analysis for free-form surfaces  

E-print Network

in the tool paths. Several parts, for which the CC points are generated using the proposed algorithm, are machined using a three axes milling machine. As part of the validation process, the tool paths generated during machining are analyzed to compare...

Choi, Young Keun

2005-08-29

391

Identification of limit cycles in multi-nonlinearity, multiple path systems  

NASA Technical Reports Server (NTRS)

A method of analysis which identifies limit cycles in autonomous systems with multiple nonlinearities and multiple forward paths is presented. The FORTRAN code for implementing the Harmonic Balance Algorithm is reported. The FORTRAN code is used to identify limit cycles in multiple path and nonlinearity systems while retaining the effects of several harmonic components.

Mitchell, J. R.; Barron, O. L.

1979-01-01

392

Load Balanced Short Path Routing in Wireless Networks Jie Gao, IEEE member, Li Zhang  

E-print Network

1 Load Balanced Short Path Routing in Wireless Networks Jie Gao, IEEE member, Li Zhang Abstract, and achieve good load balance, for balancing the energy use. We consider the special case when all the nodes that of the most load-balanced algorithm without path length constraint. In addition, our routing algo- rithms make

Gao, Jie

393

ESCAP: Efficient SCan for Alternate Paths to Achieve IP Fast Rerouting  

E-print Network

ESCAP: Efficient SCan for Alternate Paths to Achieve IP Fast Rerouting Kang Xi and H. Jonathan Chao called Efficient SCan for Alternate Paths (ESCAP) to achieve fast rerouting. The algorithm guarantees 100 equal cost. The implementation of ESCAP has low complexity and does not introduce explicit signaling

Chao, Jonathan

394

Optimal View Path Planning for Visual SLAM Sebastian Haner and Anders Heyden  

E-print Network

Optimal View Path Planning for Visual SLAM Sebastian Haner and Anders Heyden Centre efficient iterative algorithm targeted toward application within real-time SLAM systems is presented and tested on simulated data. Keywords: Next best view planning, path optimization, SLAM 1 Introduction

Lunds Universitet

395

Control-path Oriented Workflow Intelligence Analysis on EnterprizeWorkflow Grids  

Microsoft Academic Search

This paper1 proposes a workflow intelligence and quality improvement framework maximizing the workflow trace- ability and rediscoverability by analyzing the total sequences of the control-path perspective of a workflow model and by rediscovering their runtime enactment history from the workflow log information. The framework needs two kinds of algorithms - One is for generating the total sequences of the control-paths

Kwang-hoon Kim

2005-01-01

396

Genetic algorithms  

NASA Technical Reports Server (NTRS)

Genetic algorithms are mathematical, highly parallel, adaptive search procedures (i.e., problem solving methods) based loosely on the processes of natural genetics and Darwinian survival of the fittest. Basic genetic algorithms concepts are introduced, genetic algorithm applications are introduced, and results are presented from a project to develop a software tool that will enable the widespread use of genetic algorithm technology.

Wang, Lui; Bayer, Steven E.

1991-01-01

397

Quantum Algorithms  

E-print Network

This article surveys the state of the art in quantum computer algorithms, including both black-box and non-black-box results. It is infeasible to detail all the known quantum algorithms, so a representative sample is given. This includes a summary of the early quantum algorithms, a description of the Abelian Hidden Subgroup algorithms (including Shor's factoring and discrete logarithm algorithms), quantum searching and amplitude amplification, quantum algorithms for simulating quantum mechanical systems, several non-trivial generalizations of the Abelian Hidden Subgroup Problem (and related techniques), the quantum walk paradigm for quantum algorithms, the paradigm of adiabatic algorithms, a family of ``topological'' algorithms, and algorithms for quantum tasks which cannot be done by a classical computer, followed by a discussion.

Michele Mosca

2008-08-04

398

Algorithms for Solving Rubik's Cubes  

E-print Network

The Rubik's Cube is perhaps the world's most famous and iconic puzzle, well-known to have a rich underlying mathematical structure (group theory). In this paper, we show that the Rubik's Cube also has a rich underlying algorithmic structure. Specifically, we show that the n x n x n Rubik's Cube, as well as the n x n x 1 variant, has a "God's Number" (diameter of the configuration space) of Theta(n^2/log n). The upper bound comes from effectively parallelizing standard Theta(n^2) solution algorithms, while the lower bound follows from a counting argument. The upper bound gives an asymptotically optimal algorithm for solving a general Rubik's Cube in the worst case. Given a specific starting state, we show how to find the shortest solution in an n x O(1) x O(1) Rubik's Cube. Finally, we show that finding this optimal solution becomes NP-hard in an n x n x 1 Rubik's Cube when the positions and colors of some of the cubies are ignored (not used in determining whether the cube is solved).

Demaine, Erik D; Eisenstat, Sarah; Lubiw, Anna; Winslow, Andrew

2011-01-01

399

757 Path Loss Measurements  

NASA Technical Reports Server (NTRS)

Path Loss Measurements were obtained on three (3) GPS equipped 757 aircraft. Systems measured were Marker Beacon, LOC, VOR, VHF (3), Glide Slope, ATC (2), DME (2), TCAS, and GPS. This data will provide the basis for assessing the EMI (Electromagnetic Interference) safety margins of comm/nav (communication and navigation) systems to portable electronic device emissions. These Portable Electronic Devices (PEDs) include all devices operated in or around the aircraft by crews, passengers, servicing personnel, as well as the general public in the airport terminals. EMI assessment capability is an important step in determining if one system-wide PED EMI policy is appropriate. This data may also be used comparatively with theoretical analysis and computer modeling data sponsored by NASA Langley Research Center and others.

Horton, Kent; Huffman, Mitch; Eppic, Brian; White, Harrison

2005-01-01

400

Flight Paths of Orbiting Satellites  

NSDL National Science Digital Library

This is an activity to help students visualize the relationship of motion, time and space as it relates to objects orbiting the earth. They will be able to track the path of an orbiting object on a globe, plot the path of an orbiting object on a flat world map, and explain that an object orbiting earth on a plane will produce a flight path which appears as wavy lines on the earths surface.

401

Path Layout in ATM Networks  

Microsoft Academic Search

This paper surveys recent results in the area of virtual path layout in ATM networks. We focus on the one-to-all (or broadcast) and the all-to-all problems. We present a model for theoretical studies of these layouts, which amounts to covering the network with simple paths, under various constraints. The constraints are the hop count (the number of paths traversed between

Shmuel Zaks

1997-01-01

402

Path and path deviation equations for p-branes  

NASA Astrophysics Data System (ADS)

Path and path deviation equations for neutral, charged, spinning and spinning charged test particles, using a modified Bazanski Lagrangian, are derived. We extend this approach to strings and branes. We show how the Bazanski Lagrangian for charged point particles and charged branes arises à la Kaluza-Klein from the Bazanski Lagrangian in 5-dimensions.

Pavši?, Matej; Kahil, Magd E.

2012-04-01

403

Stabilizing Intelligent Route Control: Randomized Path Monitoring, Randomized Path Switching or History-Aware Path Switching?  

Microsoft Academic Search

Multihoming Intelligent Route Control (IRC) plays a significant role in improving the performance of Internet accesses. However,\\u000a in a competitive environment, IRC systems may introduce persistent route oscillations, causing significant performance degradation.\\u000a In this study, three design alternatives to cope with this issue are investigated: Randomized Path Monitoring, Randomized\\u000a Path Switching and History-aware Path Switching. The simulation results show that

Alexandre Fonte; José Martins; Marilia Curado; Edmundo Monteiro

2008-01-01

404

An Improved Ant Algorithm for Network Traffic Control  

Microsoft Academic Search

This paper proposed an improved ant algorithm with feedback function extension and dynamic pheromone design (dynamicAnt) for the network traffic management issue. The scheme first mapped the network traffic path delay and bandwidth metrics into the parameters of the basic ant algorithm. And then extended the network feedback function to the basic ant algorithm by simulated it as the food

Qi Bing; Jun Lu; Yan Long

2008-01-01

405

A tabu search algorithm for the open shop scheduling problem  

Microsoft Academic Search

An approximation algorithm of finding a minimum makespan in a nonpreemptive open shop is presented. The algorithm is based on the tabu search technique with a neighborhood structure defined using blocks of operations on a critical path. An efficient procedure is also developed for evaluating a neighborhood. The algorithm is tested on 450 randomly generated problems and a set of

Ching-fang Liaw

1999-01-01

406

New algorithms for the disk scheduling problem  

SciTech Connect

Processor speed and memory capacity are increasing several times faster than disk speed. This disparity suggests that disk I/O performance will become an important bottleneck. Methods are needed for using disks more efficiently. Past analysis of disk scheduling algorithms has largely been experimental and little attempt has been made to develop algorithms with provable performance guarantees. We consider the following disk scheduling problem. Given a set of requests on a computer disk and a convex reachability function which determines how fast the disk head travels between tracks, our goal is to schedule the disk head so that it services all the requests in the shortest time possible. We present a 312-approximation algorithm (with a constant additive term). For the special case in which the reachability function is linear we present an optimal polynomial-time solution. The disk scheduling problem is related to the special case of the asymmetric Traveling Salesman Problem with the triangle inequality (ATSP-{Delta}) in which all distances are either 0 or some constants. We show how to find the optimal tour in polynomiaI time and describe how this gives another approximation algorithm for the disk scheduling problem. Finally we consider the on-line version of the problem in which uniformly-distributed requests arrive over time. We present an algorithm (related to the above ATSP-{Delta}) that appears to give higher throughput than previously existing head scheduling algorithms.

Andrews, M.; Zhang, L.; Bender, M.A.

1996-12-31

407

Muscle fibers typically fall within a size range of 10100m along the shortest axis (e.g. Russell et al., 2000). Dimensions  

E-print Network

is that the distribution of mitochondria varies as a function of fiber size. In juveniles, mitochondria are uniformly distributed throughout the fibers and the population is equally divided between subsarcolemmal4045 Muscle fibers typically fall within a size range of 10­100·µm along the shortest axis (e

Kinsey, Stephen

408

Analysis of Crossing Path Crashes.  

National Technical Information Service (NTIS)

This report defines the problem of crossing path crashes in the United States. This crash type involves one moving vehicle that cuts across the path of another when their initial approach comes from either lateral or opposite directions and they typically...

W. G. Najm, J. D. Smith, D. L. Smith

2001-01-01

409

Path Jacobians: Theory and Applications  

Microsoft Academic Search

In accordance with Fermat's Variation Principle, a ray path connecting two arbitrary points in a scene via multiple reflectors is given by a non-linear system. If we fix one of the two points and let the other change, the system can be considered as a function relating the reflection points along the path to the varying point. In this paper,

Min Chen; James Arvo

1998-01-01

410

Algorithms for an Unmanned Vehicle Path Planning Problem  

E-print Network

e e?E ? + zN N?V \\{o} ? ? i i?N ? Let S denote a subset of vertices not containing the root vertex o. If subset S only contains vertices spanned by solution tree T, obviously S and T intersect each other. Thus there must be at least... this constraint: x e e?? (S ) ? + zN N ?S ? ? 1 S ? V \\{o} To ensure that there is at most one subset N that satisfies zN = 1, we add a second constraint: zN N?V \\{o} ? ? 1 Noting that because of the second term of the objective function...

Qin, Jianglei

2013-06-25

411

AN INEXACT PROXIMAL PATH-FOLLOWING ALGORITHM FOR ...  

E-print Network

joint treatment of proximal and self-concordant barrier concepts and illustrate that .... the optimality condition for (1.2) and then describe key technical results in deriving ...... Leukemia, where the GMRF sizes are p = 587 and 1255, respectively.

2013-11-07

412

Efficient Algorithms for Path Problems in Weighted Graphs  

E-print Network

: Guy Blelloch, Chair Manuel Blum Anupam Gupta Uri Zwick (Tel Aviv University) Submitted in partial as a collective effort of a large group of people. This group includes my advisor and coauthors, my family help and for believing in me. Firstly, I am deeply grateful to my family: to my mother Tanya and my

413

Minimizing the number of paths in BDDs: Theory and algorithm  

Microsoft Academic Search

Abstract BDDs are used in several fields as e g formal verifica - tion or synthesis Minimizing the number of nodes in a BDD is a common technique, to reduce the memory needed to ex - press a function But recently applications like SAT - solving or synthesis have been shown to benefit from a small num - ber of

Görschwin Fey; Rolf Drechsler

2006-01-01

414

Numerical Algorithms  

NSDL National Science Digital Library

CSC 325. (MAT 325) Numerical Algorithms (3) Prerequisite: CSC 112 or 121, MAT 162. An introduction to the numerical algorithms fundamental to scientific computer work. Includes elementary discussion of error, polynomial interpolation, quadrature, linear systems of equations, solution of nonlinear equations and numerical solution of ordinary differential equations. The algorithmic approach and the efficient use of the computer are emphasized.

Tagliarini, Gene

2003-04-21

415

Optimization and correction of the tool path of the five-axis milling machine: Part 1. Spatial optimization  

Microsoft Academic Search

We introduce three algorithms for optimization of a tool path of a numerically controlled five-axis milling machine. The unifying idea is a flexible geometric structure which adapts itself to a certain cost function defined on the required part surface. Algorithm 1 is based on the variational grid generation, Algorithm 2 is based on a new modification of the space filling

Stanislav S. Makhanov

2007-01-01

416

Hard paths, soft paths or no paths? Cross-cultural perceptions of water solutions  

NASA Astrophysics Data System (ADS)

In this study, we examine how development status and water scarcity shape people's perceptions of "hard path" and "soft path" water solutions. Based on ethnographic research conducted in four semi-rural/peri-urban sites (in Bolivia, Fiji, New Zealand, and the US), we use content analysis to conduct statistical and thematic comparisons of interview data. Our results indicate clear differences associated with development status and, to a lesser extent, water scarcity. People in the two less developed sites were more likely to suggest hard path solutions, less likely to suggest soft path solutions, and more likely to see no path to solutions than people in the more developed sites. Thematically, people in the two less developed sites envisioned solutions that involve small-scale water infrastructure and decentralized, community-based solutions, while people in the more developed sites envisioned solutions that involve large-scale infrastructure and centralized, regulatory water solutions. People in the two water-scarce sites were less likely to suggest soft path solutions and more likely to see no path to solutions (but no more likely to suggest hard path solutions) than people in the water-rich sites. Thematically, people in the two water-rich sites seemed to perceive a wider array of unrealized potential soft path solutions than those in the water-scarce sites. On balance, our findings are encouraging in that they indicate that people are receptive to soft path solutions in a range of sites, even those with limited financial or water resources. Our research points to the need for more studies that investigate the social feasibility of soft path water solutions, particularly in sites with significant financial and natural resource constraints.

Wutich, A.; White, A. C.; White, D. D.; Larson, K. L.; Brewis, A.; Roberts, C.

2014-01-01

417

Hard paths, soft paths or no paths? Cross-cultural perceptions of water solutions  

NASA Astrophysics Data System (ADS)

In this study, we examine how development status and water scarcity shape people's perceptions of "hard path" and "soft path" water solutions. Based on ethnographic research conducted in four semi-rural/peri-urban sites (in Bolivia, Fiji, New Zealand, and the US), we use content analysis to conduct statistical and thematic comparisons of interview data. Our results indicate clear differences based on development status and, to a lesser extent, water scarcity. People in less developed sites were more likely to suggest hard path solutions, less likely to suggest soft path solutions, and more likely to see no path to solutions than people in more developed sites. Thematically, people in less developed sites envisioned solutions that involve small-scale water infrastructure and decentralized, community based solutions, while people in more developed sites envisioned solutions that involve large-scale infrastructure and centralized, regulatory water solutions. People in water-scarce sites were less likely to suggest soft path solutions and more likely to see no path to solutions (but no more likely to suggest hard path solutions) than people in water-rich sites. Thematically, people in water-rich sites seemed to perceive a wider array of unrealized potential soft path solutions than those in water-scarce sites. On balance, our findings are encouraging in that they indicate that people are receptive to soft path solutions in a range of sites, even those with limited financial or water resources. Our research points to the need for more studies that investigate the social feasibility of soft path water solutions, particularly in sites with significant financial and natural resource constraints.

Wutich, A.; White, A. C.; Roberts, C. M.; White, D. D.; Larson, K. L.; Brewis, A.

2013-06-01

418

On load paths and load bearing topology from finite element analysis  

NASA Astrophysics Data System (ADS)

Load paths can be mapped from vector plots of 'pointing stress vectors'. They define a path along which a component of load remains constant as it traverses the solution domain. In this paper the theory for the paths is first defined. Properties of the plots that enable a designer to interpret the structural behavior from the contours are then identified. Because stress is a second order tensor defined on an orthogonal set of axes, the vector plots define separate paths for load transfer in each direction of the set of axes. An algorithm is therefore presented that combines the vectors to define a topology to carry the loads. The algorithm is shown to straighten the paths reducing bending moments and removing stress concentration. Application to a bolted joint, a racing car body and a yacht hull demonstrate the usefulness of the plots.

Kelly, D.; Reidsema, C.; Lee, M.

2010-06-01

419

Accelerating tool path computing in CAD\\/CAM: A FPGA architecture for turning lathe machining  

Microsoft Academic Search

Tool path generation is one of the most complex problems in computer aided manufacturing. The algorithm called virtual digitizing avoids this problem by its own definition but its computing cost is high. Presented in the paper there is a virtual digitizing hardware\\/software architecture that takes advantage of field programmable gate arrays (FPGAs) to improve the algorithm efficiency and to meet

Antonio Jimeno-morenilla; Antonio Martínez; Sergio Cuenca; Jose Luis Sánchez-romero

2007-01-01

420

Path-Integral Renormalization Group Method for Numerical Study of Strongly Correlated Electron Systems  

Microsoft Academic Search

A numerical algorithm for studying strongly correlated electron systems is proposed. The groundstate wavefunction is projected out after a numerical renormalization procedure in the path integral formalism. The wavefunction is expressed from the optimized linear combination of retained states in the truncated Hilbert space with a numerically chosen basis. This algorithm does not suffer from the negative sign problem and

Masatoshi Imada; Tsuyoshi Kashima

2000-01-01

421

Protein structure alignment by incremental combinatorial extension (CE) of the optimal path  

Microsoft Academic Search

A new algorithm is reported which builds an alignment between two protein structures. The algorithm involves a combinatorial extension (CE) of an alignment path defined by aligned fragment pairs (AFPs) rather than the more conventional techniques using dynamic programming and Monte Carlo optimization. AFPs, as the name suggests, are pairs of fragments, one from each protein, which confer structure similarity.

Ilya N. Shindyalov; Philip E. Bourne

1998-01-01

422

Autonomous routing algorithms for networks with wide-spread failures : a case for differential backlog routing  

E-print Network

We study the performance of a differential backlog routing algorithm in a network with random failures. Differential Backlog routing is a novel routing algorithm where packets are routed through multiple paths to their ...

Khan, Wajahat Faheem

2008-01-01

423

Multiresolution path planning for mobile robots  

Microsoft Academic Search

The problem of automatic collision-free path planning is central to mobile robot applications. An approach to automatic path planning based on a quadtree representation is presented. Hierarchical path-searching methods are introduced, which make use of this multiresolution representation, to speed up the path planning process considerably. The applicability of this approach to mobile robot path planning is discussed.

S. Kambhampati; L. S. Davis

1986-01-01

424

221A Lecture Notes Path Integral  

E-print Network

221A Lecture Notes Path Integral 1 Feynman's Path Integral Formulation Feynman's formulation with a weight factor given by the classical action for each path. Hence the name path integral. This is it. Note of quantum mechanics using the so-called path inte- gral is arguably the most elegant. It can be stated

Murayama, Hitoshi

425

Chemotaxis can take plant-parasitic nematodes to the source of a chemo-attractant via the shortest possible routes  

PubMed Central

It has long been recognized that chemotaxis is the primary means by which nematodes locate host plants. Nonetheless, chemotaxis has received scant attention. We show that chemotaxis is predicted to take nematodes to a source of a chemo-attractant via the shortest possible routes through the labyrinth of air-filled or water-filled channels within a soil through which the attractant diffuses. There are just two provisos: (i) all of the channels through which the attractant diffuses are accessible to the nematodes and (ii) nematodes can resolve all chemical gradients no matter how small. Previously, this remarkable consequence of chemotaxis had gone unnoticed. The predictions are supported by experimental studies of the movement patterns of the root-knot nematodes Meloidogyne incognita and Meloidogyne graminicola in modified Y-chamber olfactometers filled with Pluronic gel. By providing two routes to a source of the attractant, one long and one short, our experiments, the first to demonstrate the routes taken by nematodes to plant roots, serve to test our predictions. Our data show that nematodes take the most direct route to their preferred hosts (as predicted) but often take the longest route towards poor hosts. We hypothesize that a complex of repellent and attractant chemicals influences the interaction between nematodes and their hosts. PMID:20880854

Reynolds, Andy M.; Dutta, Tushar K.; Curtis, Rosane H. C.; Powers, Stephen J.; Gaur, Hari S.; Kerry, Brian R.

2011-01-01

426

A Trajectory Algorithm to Support En Route and Terminal Area Self-Spacing Concepts  

NASA Technical Reports Server (NTRS)

This document describes an algorithm for the generation of a four dimensional aircraft trajectory. Input data for this algorithm are similar to an augmented Standard Terminal Arrival Route (STAR) with the augmentation in the form of altitude or speed crossing restrictions at waypoints on the route. Wind data at each waypoint are also inputs into this algorithm. The algorithm calculates the altitude, speed, along path distance, and along path time for each waypoint.

Abbott, Terence S.

2007-01-01

427

Structural Testing: An Introduction Flow Graphs Path Testing Conclusions Path Testing  

E-print Network

Structural Testing: An Introduction Flow Graphs Path Testing Conclusions Path Testing Mohammad Mousavi Eindhoven University of Technology, The Netherlands Software Testing, 2012 Mousavi: Path Testing #12;Structural Testing: An Introduction Flow Graphs Path Testing Conclusions Outline Structural

Mousavi, Mohammad

428

Structural Testing: An Introduction Flow Graphs Path Testing Conclusions Path Testing  

E-print Network

Structural Testing: An Introduction Flow Graphs Path Testing Conclusions Path Testing Mohammad Mousavi Eindhoven University of Technology, The Netherlands Software Testing, 2013 Mousavi: Path Testing #12;Structural Testing: An Introduction Flow Graphs Path Testing Conclusions Outline Structural

Mousavi, Mohammad

429

Learning for informative path planning  

E-print Network

Through the combined use of regression techniques, we will learn models of the uncertainty propagation efficiently and accurately to replace computationally intensive Monte- Carlo simulations in informative path planning. ...

Park, Sooho, S.M. Massachusetts Institute of Technology

2008-01-01

430

Collaborative Authoring of Walden's Paths  

E-print Network

The World Wide Web contains rich collections of digital materials that can be used in education and learning settings. The collaborative authoring prototype of Walden's Paths targets two groups of users: educators and learners. From the perspective...

Li, Yuanling

2012-10-19

431

Morse theory in path space  

E-print Network

We consider the path space of a curved manifold on which a point particle is introduced in a conservative physical system with constant total energy to formulate its action functional and geodesic equation together with breaks on the path. The second variation of the action functional is exploited to yield the geodesic deviation equation and to discuss the Jacobi fields on the curved manifold. We investigate the topology of the path space using the action functional on it and its physical meaning by defining the gradient of the action functional, the space of bounded flow energy solutions and the moduli space associated with the critical points of the action functional. We also consider the particle motion on the $n$-sphere $S^{n}$ in the conservative physical system to discuss explicitly the moduli space of the path space and the corresponding homology groups.

Yong Seung Cho; Soon-Tae Hong

2007-06-01

432

Guidewire path simulation using equilibrium of forces  

NASA Astrophysics Data System (ADS)

Vascular diseases are among the major causes of death in developed countries and the treatment of those pathologies may require endovascular interventions, in which the physician utilizes guidewires and catheters through the vascular system to reach the injured vessel region. Several computational studies related to endovascular procedures are in constant development. So, predicting the guidewire path may be of great value for both physicians and researchers. We propose a method to simulate and predict the guidewire and catheter path inside a blood vessel based on equilibrium of forces, which leads, iteratively, to the minimum energy configuration. This technique was validated with physical models using a Ø0.33mm stainless steel guidewire. This method presented RMS error, in average, less than 1 mm. Moreover, the algorithm presented low variation (in average, ?=0.03mm) due to the variation of the input parameters. Therefore, even for a wide range of different parameters configuration, similar results are presented, which makes this technique easier to work with. Since this method is based on basic physics, it is simple, intuitive, easy to learn and easy to adapt.

Cardoso, Fernando M.; Furuie, Sergio S.

2014-03-01

433

Sampling-based algorithms for optimal motion planning  

E-print Network

During the last decade, sampling-based path planning algorithms, such as probabilistic roadmaps (PRM) and rapidly exploring random trees (RRT), have been shown to work well in practice and possess theoretical guarantees ...

Karaman, Sertac

434

A Synthesized Heuristic Task Scheduling Algorithm  

PubMed Central

Aiming at the static task scheduling problems in heterogeneous environment, a heuristic task scheduling algorithm named HCPPEFT is proposed. In task prioritizing phase, there are three levels of priority in the algorithm to choose task. First, the critical tasks have the highest priority, secondly the tasks with longer path to exit task will be selected, and then algorithm will choose tasks with less predecessors to schedule. In resource selection phase, the algorithm is selected task duplication to reduce the interresource communication cost, besides forecasting the impact of an assignment for all children of the current task permits better decisions to be made in selecting resources. The algorithm proposed is compared with STDH, PEFT, and HEFT algorithms through randomly generated graphs and sets of task graphs. The experimental results show that the new algorithm can achieve better scheduling performance.

Dai, Yanyan; Zhang, Xiangli

2014-01-01

435

Partnership for Advancing Technologies in Housing (PATH)  

NSF Publications Database

... Technology Systems Interactions and Whole House Approaches PATH?s mission is to advance technology ... technology arena. Far reaching exploratory research that can lead to breakthrough technologies and ...

436

THE SHORTEST PERIOD sdB PLUS WHITE DWARF BINARY CD-30 11223 (GALEX J1411-3053)  

SciTech Connect

We report on the discovery of the shortest period binary comprising a hot subdwarf star (CD-30 11223, GALEX J1411-3053) and a massive unseen companion. Photometric data from the All Sky Automated Survey show ellipsoidal variations of the hot subdwarf primary and spectroscopic series revealed an orbital period of 70.5 minutes. The large velocity amplitude suggests the presence of a massive white dwarf in the system (M{sub 2}/M{sub Sun} {approx}> 0.77) assuming a canonical mass for the hot subdwarf (0.48 M{sub Sun }), although a white dwarf mass as low as 0.75 M{sub Sun} is allowable by postulating a subdwarf mass as low as 0.44 M{sub Sun }. The amplitude of ellipsoidal variations and a high rotation velocity imposed a high-inclination to the system (i {approx}> 68 Degree-Sign ) and, possibly, observable secondary transits (i {approx}> 74 Degree-Sign ). At the lowest permissible inclination and assuming a subdwarf mass of {approx}0.48 M{sub Sun }, the total mass of the system reaches the Chandrasekhar mass limit at 1.35 M{sub Sun} and would exceed it for a subdwarf mass above 0.48 M{sub Sun }. The system should be considered, like its sibling KPD 1930+2752, a candidate progenitor for a Type Ia supernova. The system should become semi-detached and initiate mass transfer within Almost-Equal-To 30 Myr.

Vennes, S.; Kawka, A.; Nemeth, P. [Astronomicky ustav, Akademie ved Ceske republiky, Fricova 298, CZ-251 65 Ondrejov (Czech Republic); O'Toole, S. J. [Australian Astronomical Observatory, P.O. Box 915, 1670 North Ryde NSW (Australia); Burton, D. [Faculty of Sciences, University of Southern Queensland, Toowoomba, QLD 4350 (Australia)

2012-11-01

437

A Parameter-free Hedging Algorithm Kamalika Chaudhuri  

E-print Network

action to be a path (sequence of states) over the state space. The loss of an action at time of the learner is to predict a path which has loss close to that of the action with the lowest cumulative lossA Parameter-free Hedging Algorithm Kamalika Chaudhuri ITA, UC San Diego kamalika@soe.ucsd.edu Yoav

Freund, Yoav

438

EECS 495: Randomized Algorithms Lecture 7 Using Chernoff  

E-print Network

-fixing · T(el) = # paths using el · By symmetry, all T(el) equal · Expected path length n/2 · LOE, total dest. for 7n steps. Power of Two Choices Algorithm: For each ball, pick two bins ran- domly, place

Immorlica, Nicole

439

Path planning for robotic truss assembly  

NASA Astrophysics Data System (ADS)

A new Potential Fields approach to the robotic path planning problem is proposed and implemented. Our approach, which is based on one originally proposed by Munger, computes an incremental joint vector based upon attraction to a goal and repulsion from obstacles. By repetitively adding and computing these 'steps', it is hoped (but not guaranteed) that the robot will reach its goal. An attractive force exerted by the goal is found by solving for the the minimum norm solution to the linear Jacobian equation. A repulsive force between obstacles and the robot's links is used to avoid collisions. Its magnitude is inversely proportional to the distance. Together, these forces make the goal the global minimum potential point, but local minima can stop the robot from ever reaching that point. Our approach improves on a basic, potential field paradigm developed by Munger by using an active, adaptive field - what we will call a 'flexible' potential field. Active fields are stronger when objects move towards one another and weaker when they move apart. An adaptive field's strength is individually tailored to be just strong enough to avoid any collision. In addition to the local planner, a global planning algorithm helps the planner to avoid local field minima by providing subgoals. These subgoals are based on the obstacles which caused the local planner to fail. A best-first search algorithm A* is used for graph search.

Sanderson, Arthur C.

1993-09-01

440

Smooth coverage path planning and control of mobile robots based on high-resolution grid map representation  

Microsoft Academic Search

This paper presents a new approach to a time and energy efficient online complete coverage solution for a mobile robot. While most conventional approaches strive to reduce path overlaps, this work focuses on smoothing the coverage path to reduce accelerations and yet to increase the average velocity for faster coverage. The proposed algorithm adopts a high-resolution grid map representation to

Tae-Kyeong Lee; Sang-Hoon Baek; Young-Ho Choi; Se-Young Oh

2011-01-01

441

Optical path strategies in WDM all-optical networks: minimization of wavelength converters in optical cross connects  

Microsoft Academic Search

There is a significant debate in progress about the need for translating the wavelength of a signal within an optical network and on the comparison of the performance of the wavelength path (WP) and virtual wavelength path (VWP) approaches. This paper investigates these issues in more depth. An analysis of the algorithms allowing VWP and WP schemes is reported. Their

Marco Listanti; Massimo Berdusco; Roberto Sabella

1997-01-01

442

Autonomous Path-Following by Approximate Inverse Dynamics and Vector Field Prediction  

NASA Astrophysics Data System (ADS)

In this dissertation, we develop two general frameworks for the navigation and control of autonomous vehicles that must follow predefined paths. These frameworks are designed such that they inherently provide accurate navigation and control of a wide class of systems directly from a model of the vehicle's dynamics. The first framework introduced is the inverse dynamics by radial basis function (IDRBF) algorithm, which exploits the best approximation property of radial basis functions to accurately approximate the inverse dynamics of non-linear systems. This approximation is then used with the known, desired state of the system at a future time point to generate the system input that must be applied to reach the desired state in the specified time interval. The IDRBF algorithm is then tested on two non-linear dynamic systems, and accurate path-following is demonstrated. The second framework introduced is the predictive vector field (PVF) algorithm. The PVF algorithm uses the equations of motion and constraints of the system to predict a set of reachable states by sampling the system's configuration space. By finding and minimizing a continuous mapping between the system's configuration space and a cost space relating the reachable states of the system with a vector field (VF), one can determine the system inputs required to follow the VF. The PVF algorithm is then tested on the Dubin's vehicle and aircraft models, and accurate path-following is demonstrated. As the PVF algorithm's performance is dependent on the quality of the underlying system model and VF, algorithms are introduced for automatically generating VFs for constant altitude paths defined by a series of waypoints and for handling modeling uncertainties. Additionally, we provide a mathematical proof showing that this method can automatically produce VFs of the desired form. To handle modeling uncertainties, we enhance the PVF algorithm with the Gaussian process machine learning framework, enabling the algorithm to learn the true system model, online, in the presence of measurement noise. We call this algorithm the PVF-GP algorithm. To demonstrate the PVF-GP algorithm, we compare its performance to the PVF algorithm after introducing modeling uncertainties to the underlying system model and introducing an external wind disturbance. Test results show the PVF-GP algorithm offers dramatically improved path-following performance over the non-learning PVF algorithm.

Gerlach, Adam R.

443

Visual algorithms  

SciTech Connect

Nonlinear, local and highly parallel algorithms can perform several simple but important visual computations. Specific classes of algorithms can be considered in an abstract way. The author here the class of polynomial algorithms to exemplify some of the important issues for visual processing like linear vs. nonlinear and local vs. global. Polynomial algorithms are a natural extension of Perceptrons to time dependent grey level images. Although they share most of the limitations of Perceptrons, they are powerful parallel computational devices. Several of their properties are characterized and especially their equivalence with Perceptrons for geometrical figures and the synthesis of nonlinear algorithms(mapping) via associative learning. Finally, the paper considers how algorithms of this type could be implemented in nervous hardware, in terms of synaptic interactions strategically located in a dendritic tree. The implementation of three specific algorithms is briefly outlined: direction sensitive motion detection; detection of discontinuities in the optical flow; and detection and localization of zero-crossings in the convolution of the image with the Laplacian (of a Gaussian). In the appendix, another (nonlinear) differential operator, the second directional derivative along the gradient, is briefly discussed as an alternative to the Laplacian.

Lozano-Perez, T.

1982-05-01

444

Algorithms: Greedy Algorithms Amotz Bar-Noy  

E-print Network

Algorithms: Greedy Algorithms Amotz Bar-Noy CUNY Spring 2012 Amotz Bar-Noy (CUNY) Greedy Algorithms Spring 2012 1 / 62 #12;Greedy Algorithms Greedy algorithms make decisions that "seem" to be the best) Greedy Algorithms Spring 2012 2 / 62 #12;How and When to use Greedy Algorithms? Initial solution

Bar-Noy, Amotz

445

Gas-path seal technology  

NASA Technical Reports Server (NTRS)

Improved gas-path seals are needed for better fuel economy, longer performance retention, and lower maintenance, particularly in advanced, high-performance gas turbine engines. Problems encountered in gas-path sealing are described, as well as new blade-tip sealing approaches for high-pressure compressors and turbines. These include a lubricant coating for conventional, porous-metal, rub-strip materials used in compressors. An improved hot-press metal alloy shows promise to increase the operating surface temperatures of high-pressure-turbine, blade-tip seals to 1450 K (2150 F). Three ceramic seal materials are also described that have the potential to allow much higher gas-path surface operating temperatures than are possible with metal systems.

Zuk, J.

1976-01-01

446

Path Abstraction for Combined Navigation and Animation  

NASA Astrophysics Data System (ADS)

Natural motion of virtual characters is crucial in games and simulations. The quality of such motion strongly depends on the path the character walks and the animation of the character locomotion. Therefore, much work has been done on path planning and character animation. However, the combination of both fields has received less attention. Combining path planning and motion synthesis introduces several problems. A path generated by a path planner is often a simplification of the character movement. This raises the question which (body) part of the character should follow the path generated by the path planner and to what extent it should closely follow the path. We will show that enforcing the pelvis to follow the path will lead to unnatural animations and that our proposed solution, using path abstractions, generates significantly better animations.

van Basten, Ben J. H.; Egges, Arjan

447

Crack Path Selection Fatigue crack path imaged via SEM  

E-print Network

phases fail in a brittle manner Fatigue Crack Growth ABSTRACT Advanced aerospace materials continue Crack path selects secondary phases and interface Conclusions ·Nb-Si Alloys tested exhibited toughness at high temperatures. An important property of any high temperature aerospace engineering material is its

Rollins, Andrew M.

448

Multiple paths in complex tasks  

NASA Technical Reports Server (NTRS)

The relationship between utility judgments of subtask paths and the utility of the task as a whole was examined. The convergent validation procedure is based on the assumption that measurements of the same quantity done with different methods should covary. The utility measures of the subtasks were obtained during the performance of an aircraft flight controller navigation task. Analyses helped decide among various models of subtask utility combination, whether the utility ratings of subtask paths predict the whole tasks utility rating, and indirectly, whether judgmental models need to include the equivalent of cognitive noise.

Galanter, Eugene; Wiegand, Thomas; Mark, Gloria

1987-01-01

449

Real-time path planning for a robot arm in changing environments  

Microsoft Academic Search

We present a practical strategy for real-time path planning for articulated robot arms in changing environments by integrating PRM for Changing Environments with 3D sensor data. Our implementation on Care-O-Bot 3 identifies bottlenecks in the algorithm and introduces new methods that solve the overall task of detecting obstacles and planning a path around them in under 100 ms. A fast

Tobias Kunz; Ulrich Reiser; Mike Stilman; Alexander Verl

2010-01-01

450

Application of path planning and visualization for industrial-design and maintainability-analysis  

Microsoft Academic Search

Software applications Product Vision, and its successor, Galileo, were developed to allow engineers to interactively fly through a digital virtual jet engine, and automatically determine removal paths for maintenance simulations. Three equally significant hurdles have been overcome during the development of this software, with the following results: state-of-the-art algorithms have been developed to find part-removal paths, create swept volumes, and

C. C. Law; L. Sobierajski Avila; W. Schroeder

1998-01-01

451

Contour-parallel tool-path planning of free surface using Voronoi diagram approach  

Microsoft Academic Search

In this paper, an important method for computing the tool-path, and constructing the offset curves of pocket boundary generates its tool-path planning is the Contour-parallel strategy. But it is very difficult for the judgment and disposal of loop. The main disfigurement of the algorithm in the contour-parallel calculation includes to judge and dispose the linking of offset curves, and to

Zhiqiang Jiang; Xilan Feng; Xianzhang Feng; Yuanpeng Liu

2010-01-01

452

Virtual Fiber Networking and Impact of Optical Path Grooming on Creating Efficient Layer One Services  

NASA Astrophysics Data System (ADS)

This paper presents a novel “virtual fiber” network service that exploits wavebands. This service provides virtual direct tunnels that directly convey wavelength paths to connect customer facilities. To improve the resource utilization efficiency of the service, a network design algorithm is developed that can allow intermediate path grooming at limited nodes and can determine the best node location. Numerical experiments demonstrate the effectiveness of the proposed service architecture.

Naruse, Fumisato; Yamada, Yoshiyuki; Hasegawa, Hiroshi; Sato, Ken-Ichi

453

Algorithmic embeddings  

E-print Network

We present several computationally efficient algorithms, and complexity results on low distortion mappings between metric spaces. An embedding between two metric spaces is a mapping between the two metric spaces and the ...

B?doiu, Mihai, 1978-

2006-01-01

454

Algorithms, Theory  

E-print Network

Ant robots have very low computational power and limited memory. They communicate by leaving pheromones in the environment. In order to create a cooperative intelligent behavior, ants may need to get together; however, they may not know the locations of other ants. Hence, we focus on an ant variant of the rendezvous problem, in which two ants are to be brought to the same location in finite time. We introduce two algorithms that solve this problem for two ants by simulating a bidirectional search in different environment settings. An algorithm for an environment with no obstacles and a general algorithm that handles all types of obstacles. We provide detailed discussion on the different attributes, size of pheromone required, and the performance of these algorithms.

Asaf Shiloni; Alon Levy; Ariel Felner; Meir Kalech

455

?f Algorithm  

NASA Astrophysics Data System (ADS)

The ?f Algorithm is a low noise particle code algorithm. The perturbation of the distribution function ( ?f) away from a large equilibrium is evolved rather than the total distribution function. "Particles" in the code are actually Lagrangian markers at which the value of the distribution function is known, The magnitude of the numerical noise is characteristic of the size of the perturbation rather than the equilibrium and scales roughly as the inverse of the number of particles, In this paper, the algorithm is described, and conserved energies are derived for linear and nonlinear sets of equations. Two different forms of the energy principle test separately adequate resolution in time and space and adequacy of the number of simulation particles. A semi-implicit time step method is described which allows violation of the Courant condition. Low noise capabilities of a linear code using the algorithm are demonstrated.

Denton, Richard E.; Kotschenreuther, M.

1995-07-01

456

Strategic algorithms  

E-print Network

Classical algorithms from theoretical computer science arise time and again in practice. However,a practical situations typically do not fit precisely into the traditional theoretical models. Additional necessary components ...

Nikolova, Evdokia Velinova

2009-01-01

457

Cluster algorithms  

E-print Network

Cluster algorithms for classical and quantum spin systems are discussed. In particular, the cluster algorithm is applied to classical O(N) lattice actions containing interactions of more than two spins. The performance of the multi-cluster and single--cluster methods, and of the standard and improved estimators are compared. (Lecture given at the summer school on `Advances in Computer Simulations', Budapest, July 1996.)

Ferenc Niedermayer

1997-04-21

458

Fixed Point Decimal Multiplication Using RPS Algorithm  

Microsoft Academic Search

Decimal multiplication is an integral part of financial, commercial, and Internet-based computations. A novel design for single digit decimal multiplication that reduces the critical path delay and area for an iterative multiplier is proposed in this research. The partial products are generated using single digit multipliers, and are accumulated based ona novel RPS algorithm. This design uses n single digit

Rekha K. James; T. K. Shahana; K. Poulose Jacob; Sreela Sasi

2008-01-01

459

COMPUTER SCIENCE: MISCONCEPTIONS, CAREER PATHS  

E-print Network

Undergraduate Student) #12;Computer Science Misconceptions Intro to Computer Science - Florida International much can I make out of college? Data from the Bureau of Labor Statistics #12;Computer ScienceCOMPUTER SCIENCE: MISCONCEPTIONS, CAREER PATHS AND RESEARCH CHALLENGES School of Computing

Hristidis, Vagelis

460

The Path of Human Evolution  

Microsoft Academic Search

A complex series of evolutionary steps, contingent upon a dynamic environmental context and a long biological heritage, have led to the ascent of Homo sapiens as a dominant component of the modern biosphere. In a field where missing links still abound and new discoveries regularly overturn theoretical paradigms, our understanding of the path of human evolution has made tremendous advances

C. S. Feibel

2004-01-01

461

Advances in steam path technology  

Microsoft Academic Search

For many years, GE has been conducting research to understand better the loss mechanisms that degrade the aerodynamic performance of steam turbine stages, and to develop new computational fluid dynamics (CFD) computer programs to predict these losses accurately. This paper describes a number of new steam path design features that have been introduced in the GE steam turbine product line

John I. Cofer; J. I. IV

1996-01-01

462

Commercializing Biorefineries The Path Forward  

E-print Network

Commercializing Biorefineries The Path Forward Bioenergy ExCo 59 Workshop Golden, CO Lawrence J/R&DFocus Timeframe for R&D Successes & Commercialization 2006 200920082007 20112010 2012: R&D on bench and pilot for commercial demonstration projects 2006: Announced loan guarantee program for projects employing new energy

463

Career Paths in Environmental Sciences  

EPA Science Inventory

Career paths, current and future, in the environmental sciences will be discussed, based on experiences and observations during the author's 40 + years in the field. An emphasis will be placed on the need for integrated, transdisciplinary systems thinking approaches toward achie...

464

Immigration: Rubio's path to presidency?  

E-print Network

Immigration: Rubio's path to presidency? In media blitz retorting conservative critics, he aims Writer Of the four Democratic and four Republican senators who wrote the immigration reform proposal now, both in Congress and nationwide, need more convincing on immigration reform than Democrats. And Rubio

Fernandez, Eduardo

465

Career Paths of Academic Deans.  

ERIC Educational Resources Information Center

This paper examines various career paths leading to deanship and considers the implications of the findings for women and minorities who aspire to this position. The paper is part of a larger study of academic deanship conducted by the Center for Academic Leadership at Washington State University between October 1996 and January 1997. Data for the…

Wolverton, Mimi; Gonzales, Mary Jo

466

A triangular path inverting interferometer  

Microsoft Academic Search

A triangular path inverting interferometer is described with application to the study of thermal 'schlieren'. This is practically free of any vibration and coherence troubles, and possesses the unique feature that either differential or total shear may be obtained only with proper positioning of the object; once aligned, the optical components need not be disturbed further. This simple and stable

D. Chakrabarti; S. P. Basu; M. De

1977-01-01

467

NPRE at Illinois Three Paths  

E-print Network

production; Nuclear power operations and control � Plasma sciences; Applied plasma physics; Nuclear fusionNPRE at Illinois Three Paths Students choose from three concentrations: � Plasma and Fusion � Power and interactions of radiation with matter � Applications of nuclear processes � Nuclear fission for electric power

Gilbert, Matthew

468

Kinetic Constrained Optimization of the Golf Swing Hub Path  

PubMed Central

This study details an optimization of the golf swing, where the hand path and club angular trajectories are manipulated. The optimization goal was to maximize club head velocity at impact within the interaction kinetic limitations (force, torque, work, and power) of the golfer as determined through the analysis of a typical swing using a two-dimensional dynamic model. The study was applied to four subjects with diverse swing capabilities and styles. It was determined that it is possible for all subjects to increase their club head velocity at impact within their respective kinetic limitations through combined modifications to their respective hand path and club angular trajectories. The manner of the modifications, the degree of velocity improvement, the amount of kinetic reduction, and the associated kinetic limitation quantities were subject dependent. By artificially minimizing selected kinetic inputs within the optimization algorithm, it was possible to identify swing trajectory characteristics that indicated relative kinetic weaknesses of a subject. Practical implications are offered based upon the findings of the study. Key Points The hand path trajectory is an important characteristic of the golf swing and greatly affects club head velocity and golfer/club energy transfer. It is possible to increase the energy transfer from the golfer to the club by modifying the hand path and swing trajectories without increasing the kinetic output demands on the golfer. It is possible to identify relative kinetic output strengths and weakness of a golfer through assessment of the hand path and swing trajectories. Increasing any one of the kinetic outputs of the golfer can potentially increase the club head velocity at impact. The hand path trajectory has important influences over the club swing trajectory.

Nesbit, Steven M.; McGinnis, Ryan S.

2014-01-01

469

A multistage algorithm for the job shop scheduling problem  

Microsoft Academic Search

This paper presents a multistage algorithm for the job shop scheduling problem (JSP). A theorem is proved that the calculability of a solution is the sufficient and necessary condition for its feasibility. Therefore, an infeasible solution will be discarded immediately and the improved critical path algorithm is applied to perform the local search for a feasible solution. The computational results

Jianshuang Cui; Liang Cheng; Tieke Li

2009-01-01

470

An Empirical Comparison of Dynamic Impact Analysis Algorithms Alessandro Orso,  

E-print Network

of the algorithms they employ, CoverageImpact and PathImpact are expected to differ in terms of cost and precisionAn Empirical Comparison of Dynamic Impact Analysis Algorithms Alessandro Orso, Taweesup of Technology Atlanta, Georgia {orso, term, harrold}@cc.gatech.edu Computer Science Department Oregon State

Harrold, Mary Jean

471

Comparison of different Ant Colony Based Routing Algorithms  

E-print Network

A Mobile Ad-Hoc Network (MANET) [1] is a collection of wireless mobile nodes forming a temporary network without using centralized access points, infrastructure, or centralized administration. Many researchers have developed proactive and reactive algorithms for MANETs. DSR and AODV are reactive algorithms establishing paths only when they are needed. When a node has some data to send to another node, it searches for a path by flooding the network with control messages. Their dissemination introduces some delay before data packets can be sent and reactive routing algorithms are inefficient when there is much continuous but intermittent traffic in the network. DSDV on the other hand, is a typical proactive routing algorithm. They prepare paths to all destination nodes beforehand and maintain them by exchanging control messages periodically. They require a network to carry a lot of control traffic into a network. Swarm Intelligence (SI) [1] is an artificial intelligence technique based around on the study of collective behavior in decentralized, self-organized systems. Ant Colony Optimization is popular among other Swarm Intelligent Techniques. Ants-based routing algorithms have attracted the attention of researchers because they are more robust, reliable, and scalable than other conventional routing algorithms. Since they do not involve extra message exchanges to maintain paths when network topology changes, they are suitable for mobile ad-hoc networks where nodes move dynamically and topology changes frequently. In this paper a detailed comparison of different Ant based algorithms is presented. The algorithms discussed here are Ant

Vasundhara Uchhula; Dharamsinh Desai; Brijesh Bhatt; Dharamsinh Desai

472

A novel Fly Optimization Algorithm for swarming application  

Microsoft Academic Search

This paper presents an initial development stage of Fly Optimization Algorithm which will be used for the path planning system of a swarm of autonomous surface vehicles. This algorithm was initially designed to be implemented for a swarm of robots which would be able to locate the deepest portion of lakes. The ability of the robots to reach the designated

Zulkifli Zainal Abidin; Umi Kalthum Ngah; Mohd Rizal Arshad; Ong Boon Ping

2010-01-01

473

CYCLIC GENETIC ALGORITHMS FOR EVOLVING MULTI-LOOP CONTROL PROGRAMS  

E-print Network

, genetic algorithms, sensors, learning, search, hexapod 1. INTRODUCTION The Cyclic Genetic Algorithm (CGA for hexapod gaits and area coverage path planning. However, in order for a robot to react properly to sensor walls and locate the desired target. The agent modeled in simulation is a hexapod robot equipped

Parker, Gary B.

474

CYCLIC GENETIC ALGORITHMS FOR EVOLVING MULTILOOP CONTROL PROGRAMS  

E-print Network

algorithms, sensors, learning, search, hexapod 1. INTRODUCTION Cyclic Genetic Algorithm (CGA), a variant of traditional successfully been used evolve single loop control programs hexapod gaits and area coverage path modeled simulation a hexapod robot equipped with sensors. The task of learning search behavior autonomous

Parker, Gary B.

475

Rose algorithm for fast and even routing in sensor networks  

Microsoft Academic Search

In this paper, the novel ROSE Algorithm is proposed for fast and even routing in sensor networks. The algorithm uses the concepts of the differences of sets and the node relative degree to find the paths from the sink to all nodes in the network. It is developed in the manner of a rose blossoming. The protocol forms a tree?architecture

2009-01-01

476

An Efficient Algorithm for Shielding Electromagnetic Topological Diagram  

Microsoft Academic Search

An electromagnetic topology method used to analyze interactions between electronic systems and electromagnetic environment is presented. Combining electromagnetic topology model with the graph theory, an efficient algorithm is obtained. The algorithm can find out all the paths which have a lower shielding coefficient than the given threshold K in the shielding electromagnetic topological diagram.

Yongfeng Wang; Chengda Yu; Chaowei Zhang

2010-01-01

477

Hybrid Support Vector Regression and GA\\/TS for Radio-Wave Path-Loss Prediction  

Microsoft Academic Search

\\u000a This paper presents support vector regression with hybrid genetic algorithms and tabu search (GA\\/TS) algorithms (SVRGA\\/TS)\\u000a models for the prediction of radio-wave path-loss in suburban environment. The support vector regression (SVR) model is a\\u000a novel forecasting approach and has been successfully used to solve time series problems. However, the application of SVR model\\u000a in a radio-wave path-loss forecasting has not

Kuo-Chen Hung; Kuo-Ping Lin; Gino K. Yang; Yuan-Cheng Tsai

2010-01-01

478

Benchmarking Gas Path Diagnostic Methods: A Public Approach  

NASA Technical Reports Server (NTRS)

Recent technology reviews have identified the need for objective assessments of engine health management (EHM) technology. The need is two-fold: technology developers require relevant data and problems to design and validate new algorithms and techniques while engine system integrators and operators need practical tools to direct development and then evaluate the effectiveness of proposed solutions. This paper presents a publicly available gas path diagnostic benchmark problem that has been developed by the Propulsion and Power Systems Panel of The Technical Cooperation Program (TTCP) to help address these needs. The problem is coded in MATLAB (The MathWorks, Inc.) and coupled with a non-linear turbofan engine simulation to produce "snap-shot" measurements, with relevant noise levels, as if collected from a fleet of engines over their lifetime of use. Each engine within the fleet will experience unique operating and deterioration profiles, and may encounter randomly occurring relevant gas path faults including sensor, actuator and component faults. The challenge to the EHM community is to develop gas path diagnostic algorithms to reliably perform fault detection and isolation. An example solution to the benchmark problem is provided along with associated evaluation metrics. A plan is presented to disseminate this benchmark problem to the engine health management technical community and invite technology solutions.

Simon, Donald L.; Bird, Jeff; Davison, Craig; Volponi, Al; Iverson, R. Eugene

2008-01-01

479

Preweld Joint Tracking System For Weld Path Teaching  

NASA Astrophysics Data System (ADS)

Precision welding of aircraft engine assemblies requires accurate tracking of the weld joint under conditions of positional uncertainty. Real-time laser based joint tracking systems are becoming available but currently cost, accuracy, field-of-view, and applicability to specific joint types, weld processes and robot controllers limit their use. When tracking prior to welding is a feasible alternative to real-time tracking, these issues can be addressed. The software and hardware for such a system is described. The system can track weld joints in two dimensions and offset weld path programs to compensate for assembly and/or fixturing errors. The technique is applicable to both plasma arc welding (PAW) and tungsten inert gas (TIG) welding as the sensor is mounted ahead of the weld torch. The weld path tracking software refines a coarsely taught weld path. To enhance tracking accuracy, reliability and speed, the joint tracking algorithm searches for the joint along a line. Search direction is calculated as the normal to the coarse path trajectory. Search direction is accomplished by rotating a window of the image. A prototype system has been implemented. The system consists of a welding robot, a custom vision system, a CCD camera and fiber optic incandescent lighting. The system has been used to successfully weld production assemblies.

Packer, Scott M.; Pietrzak, Kenneth A.; Skinner, Michael J.; Dunne, Kenneth C.

1990-03-01

480

Photon path length distributions inferred from rotating shadowband spectrometer measurements at the Atmospheric Radiation Measurements Program Southern Great Plains site  

Microsoft Academic Search

An algorithm for retrieving the first two moments of the photon path length probability density function for both the oxygen A-band and the 0.820 mum water vapor band from measurements of the second generation Rotating Shadowband Spectrometer (RSS) is developed and applied to data from the Atmospheric Radiation Measurements (ARM) Program Southern Great Plains (SGP) site. In the algorithm, solar

Qilong Min; Eugene E. Clothiaux

2003-01-01

481

Efficient DNA sticker algorithms for NP-complete graph problems  

NASA Astrophysics Data System (ADS)

Adleman's successful solution of a seven-vertex instance of the NP-complete Hamiltonian directed path problem by a DNA algorithm initiated the field of biomolecular computing. We provide DNA algorithms based on the sticker model to compute all k-cliques, independent k-sets, Hamiltonian paths, and Steiner trees with respect to a given edge or vertex set. The algorithms determine not merely the existence of a solution but yield all solutions (if any). For an undirected graph with n vertices and m edges, the running time of the algorithms is linear in n+ m. For this, the sticker algorithms make use of small combinatorial input libraries instead of commonly used large libraries. The described algorithms are entirely theoretical in nature. They may become very useful in practice, when further advances in biotechnology lead to an efficient implementation of the sticker model.

Zimmermann, Karl-Heinz

2002-04-01

482

Greedy Algorithms and Matroids  

E-print Network

Greedy Algorithms and Matroids Andreas Klappenecker #12;Greedy Algorithms A greedy algorithm solves of algorithms. #12;Correct Greedy Algorithms When a greedy algorithm terminates, then the hope is always reached, then the algorithm is correct. #12;Properties A greedy algorithm successively solves

Klappenecker, Andreas

483

Fast greedy triangulation algorithms  

Microsoft Academic Search

The greedy triangulation (GT) of a set S of n points in the plane is the triangulation obtained by starting with the empty set and at each step adding the shortest compatible edge between two of the points, where a compatible edge is de ned to be an edge that crosses none of the previously added edges. In this paper

Matthew T. Dickerson; Scott A. McElfresh; Emo Welzl

1994-01-01

484

Algorithmic alternatives  

SciTech Connect

A large variety of Monte Carlo algorithms are being used for lattice gauge simulations. For purely bosonic theories, present approaches are generally adequate; nevertheless, overrelaxation techniques promise savings by a factor of about three in computer time. For fermionic fields the situation is more difficult and less clear. Algorithms which involve an extrapolation to a vanishing step size are all quite closely related. Methods which do not require such an approximation tend to require computer time which grows as the square of the volume of the system. Recent developments combining global accept/reject stages with Langevin or microcanonical updatings promise to reduce this growth to V/sup 4/3/.

Creutz, M.

1987-11-01

485

Kinematics, controls, and path planning results for a redundant manipulator  

NASA Technical Reports Server (NTRS)

The inverse kinematics solution, a modal position control algorithm, and path planning results for a 7 degree of freedom manipulator are presented. The redundant arm consists of two links with shoulder and elbow joints and a spherical wrist. The inverse kinematics problem for tip position is solved and the redundant joint is identified. It is also shown that a locus of tip positions exists in which there are kinematic limitations on self-motion. A computationally simple modal position control algorithm has been developed which guarantees a nearly constant closed-loop dynamic response throughout the workspace. If all closed-loop poles are assigned to the same location, the algorithm can be implemented with very little computation. To further reduce the required computation, the modal gains are updated only at discrete time intervals. Criteria are developed for the frequency of these updates. For commanding manipulator movements, a 5th-order spline which minimizes jerk provides a smooth tip-space path. Schemes for deriving a corresponding joint-space trajectory are discussed. Modifying the trajectory to avoid joint torque saturation when a tip payload is added is also considered. Simulation results are presented.

Gretz, Bruce; Tilley, Scott W.

1989-01-01

486

Path integral on star graph  

NASA Astrophysics Data System (ADS)

In this paper we study path integral for a single spinless particle on a star graph with N edges, whose vertex is known to be described by U(N) family of boundary conditions. After carefully studying the free particle case, both at the critical and off-critical levels, we propose a new path integral formulation that correctly captures all the scale-invariant subfamily of boundary conditions realized at fixed points of boundary renormalization group flow. Our proposal is based on the folding trick, which maps a scalar-valued wave function on star graph to an N-component vector-valued wave function on half-line. All the parameters of scale-invariant subfamily of boundary conditions are encoded into the momentum independent weight factors, which appear to be associated with the two distinct path classes on half-line that form the cyclic group Z2. We show that, when bulk interactions are edge-independent, these weight factors are generally given by an N-dimensional unitary representation of Z2. Generalization to momentum dependent weight factors and applications to worldline formalism are briefly discussed.

Ohya, Satoshi

2012-06-01

487

Model for Delay Faults Based upon Paths  

Microsoft Academic Search

Delay testing of combinational logic in a clocked environment is analyzed. A model based upon paths is introduced for delay faults. Any path with a total delay exceeding the clock interval is called a \\

Gordon L. Smith

1985-01-01

488

Electron Inelastic-Mean-Free-Path Database  

National Institute of Standards and Technology Data Gateway

SRD 71 NIST Electron Inelastic-Mean-Free-Path Database (PC database, no charge)   This database provides values of electron inelastic mean free paths (IMFPs) for use in quantitative surface analyses by AES and XPS.

489

Image processing meta-algorithm development via genetic manipulation of existing algorithm graphs  

NASA Astrophysics Data System (ADS)

Automatic algorithm generation for image processing applications is not a new idea, however previous work is either restricted to morphological operates or impractical. In this paper, we show recent research result in the development and use of meta-algorithms, i.e. algorithms which lead to new algorithms. Although the concept is generally applicable, the application domain in this work is restricted to image processing. The meta-algorithm concept described in this paper is based upon out work in dynamic algorithm. The paper first present the concept of dynamic algorithms which, on the basis of training and archived algorithmic experience embedded in an algorithm graph (AG), dynamically adjust the sequence of operations applied to the input image data. Each node in the tree-based representation of a dynamic algorithm with out degree greater than 2 is a decision node. At these nodes, the algorithm examines the input data and determines which path will most likely achieve the desired results. This is currently done using nearest-neighbor classification. The details of this implementation are shown. The constrained perturbation of existing algorithm graphs, coupled with a suitable search strategy, is one mechanism to achieve meta-algorithm an doffers rich potential for the discovery of new algorithms. In our work, a meta-algorithm autonomously generates new dynamic algorithm graphs via genetic recombination of existing algorithm graphs. The AG representation is well suited to this genetic-like perturbation, using a commonly- employed technique in artificial neural network synthesis, namely the blueprint representation of graphs. A number of exam. One of the principal limitations of our current approach is the need for significant human input in the learning phase. Efforts to overcome this limitation are discussed. Future research directions are indicated.

Schalkoff, Robert J.; Shaaban, Khaled M.

1999-07-01

490

Data-path layout design inside SOC  

Microsoft Academic Search

As more data-path stacks are integrated into system-on-a-chip (SOC), data-path is becoming a critical part of the whole giga-scale integrated circuits (GSI) design. The traditional layout design methodology can not satisfy the data-path performance requirements because it has no knowledge of the data-path bit-sliced structure and the strict performance (such as timing, coupling, and crosstalk) constraints. In this paper, we

Tong Jing; Xian-Long Hong; Yi-Ci Cai; Jing-Yu Xu; Chang-Qi Yang; Yi-Qian Zhang; Qiang Zhou; Weimin Wu

2002-01-01

491

Multiple Paths to Encephalization and Technical Civilizations  

NASA Astrophysics Data System (ADS)

We propose consideration of at least two possible evolutionary paths for the emergence of intelligent life with the potential for technical civilization. The first is the path via encephalization of homeothermic animals; the second is the path to swarm intelligence of so-called superorganisms, in particular the social insects. The path to each appears to be facilitated by environmental change: homeothermic animals by decreased climatic temperature and for swarm intelligence by increased oxygen levels.

Schwartzman, David; Middendorf, George

2011-12-01

492

A Revised Trajectory Algorithm to Support En Route and Terminal Area Self-Spacing Concepts  

NASA Technical Reports Server (NTRS)

This document describes an algorithm for the generation of a four dimensional trajectory. Input data for this algorithm are similar to an augmented Standard Terminal Arrival (STAR) with the augmentation in the form of altitude or speed crossing restrictions at waypoints on the route. This version of the algorithm accommodates descent Mach values that are different from the cruise Mach values. Wind data at each waypoint are also inputs into this algorithm. The algorithm calculates the altitude, speed, along path distance, and along path