For comprehensive and current results, perform a real-time search at Science.gov.

1

Engineering Shortest Path Algorithms Camil Demetrescu1

Engineering Shortest Path Algorithms Camil Demetrescu1 and Giuseppe F. Italiano2 1 Dipartimento di: italiano@disp.uniroma2.it, URL: http://www.disp.uniroma2.it/users/italiano/ Abstract. In this paper, we

Demetrescu, Camil

2

Experimental analysis of dynamic all pairs shortest path algorithms

We present the results of an extensive computational study on dynamic algorithms for all pairs shortest path problems. We describe our implementations of the recent dynamic algorithms of King [18] and of Demetrescu and Italiano [7], and compare them to the dynamic algorithm of Ramalingam and Reps [25] and to static algorithms on random, real-world and hard instances. Our experimental

Camil Demetrescu; Stefano Emiliozzi; Giuseppe F. Italiano

2004-01-01

3

Efficient Algorithms for Shortest Paths in Sparse Networks

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

4

Fully Dynamic Algorithms for Maintaining Shortest Paths Trees

We propose fully dynamic algorithms for maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions, and weight updates of edges. The algorithms require linear space and optimal query time. The cost of the update operations depends on the class of the considered

Daniele Frigioni; Alberto Marchetti-spaccamela; Umberto Nanni

2000-01-01

5

An Improved Physarum polycephalum Algorithm for the Shortest Path Problem

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

6

Multiple Object Tracking Using the Shortest Path Faster Association Algorithm

To solve the persistently multiple object tracking in cluttered environments, this paper presents a novel tracking association approach based on the shortest path faster algorithm. First, the multiple object tracking is formulated as an integer programming problem of the flow network. Then we relax the integer programming to a standard linear programming problem. Therefore, the global optimum can be quickly obtained using the shortest path faster algorithm. The proposed method avoids the difficulties of integer programming, and it has a lower worst-case complexity than competing methods but better robustness and tracking accuracy in complex environments. Simulation results show that the proposed algorithm takes less time than other state-of-the-art methods and can operate in real time. PMID:25215322

Liu, Heping; Liu, Huaping; Yang, Bin

2014-01-01

7

Quantum algorithms for shortest paths problems in structured instances

We consider the quantum time complexity of the all pairs shortest paths (APSP) problem and some of its variants. The trivial classical algorithm for APSP and most all pairs path problems runs in $O(n^3)$ time, while the trivial algorithm in the quantum setting runs in $\\tilde{O}(n^{2.5})$ time, using Grover search. A major open problem in classical algorithms is to obtain a truly subcubic time algorithm for APSP, i.e. an algorithm running in $O(n^{3-\\varepsilon})$ time for constant $\\varepsilon>0$. To approach this problem, many truly subcubic time classical algorithms have been devised for APSP and its variants for structured inputs. Some examples of such problems are APSP in geometrically weighted graphs, graphs with small integer edge weights or a small number of weights incident to each vertex, and the all pairs earliest arrivals problem. In this paper we revisit these problems in the quantum setting and obtain the first nontrivial (i.e. $O(n^{2.5-\\varepsilon})$ time) quantum algorithms for the problems.

Aran Nayebi; Virginia Vassilevska Williams

2014-10-23

8

Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths

The fusion tree method is extended to develop a linear-time algorithm for the minimum spanning tree problem and an O(m +n log n\\/log log n) implementation of Dijkstra's shortest-path algorithm for a graph with n vertices and m edges. The shortest-path algorithm surpasses information-theoretic limitations. The extension of the fusion tree method involves the development of a new data structure,

Michael L. Fredman; Dan E. Willard

1990-01-01

9

A FAST ALGORITHM FOR FINDING THE SHORTEST PATH BY SOLVING INITIAL VALUE ODE'S

, such as the combinatorial methods or partial differential equation methods, our algorithm seems to be faster and easier methods are based on the theory of differential equations. For instance, in the planar path evolution differential equations under random perturbations. The idea is based on the fact that every shortest path

Soatto, Stefano

10

An exact algorithm for computing the shortest path touring n circles in 2D

This paper introduces the problem of computing the shortest Euclidean path touring n disjoint circles in 2D. The problem is a generalization of Travelling Salesman Problem (TSP) in Euclidean 2D space and is not a purely combinatorial problem. Based on the author's previous work, this paper proposes an exact algorithm to solve the studied problem. The proposed algorithm can be

Chang-Chien Chou

2010-01-01

11

Finding splitting lines for touching cell nuclei with a shortest path algorithm.

A shortest path-based algorithm is proposed in this paper to find splitting lines for touching cell nuclei. First, an initial splitting line is obtained through the distance transform of a marker image and the watershed algorithm. The initial splitting line is then separated into different line segments as necessary, and the endpoint positions of these line segments are adjusted to the concave points on the contour. Finally, a shortest path algorithm is used to find the accurate splitting line between the starting-point and the end-point, and the final split can be achieved by the contour of the touching cell nuclei and the splitting lines. Comparisons of experimental results show that the proposed algorithm is effective for segmentation of different types of touching cell nuclei. PMID:25458811

Bai, Xiangzhi; Wang, Peng; Sun, Changming; Zhang, Yu; Zhou, Fugen; Meng, Cai

2014-10-22

12

A branch and bound algorithm for the robust shortest path problem with interval data

Many real problems in transportation and telecommunications can be modelled in mathematical terms as shortest path problems on in- terval digraphs, where an interval of costs is associated with each arc. Intervals represent uncertainty, typical of real situations, about the exact values of costs. In this context, a robust shortest path is a path which is ideally not too far

R. Montemanni; L. M. Gambardella; A. E. Rizzoli; A. V. Donati

2002-01-01

13

A branch and bound algorithm for the robust shortest path problem with interval data

Many real problems in transportation and telecommunications can be modelled in mathematical terms as shortest path problems on interval digraphs, where an interval cost is associated with each arc. Intervals represent uncertainty, typical of real situations, about the exact values of costs. A robust shortest path is a path which is not too far from the best one, whatever the

Roberto Montemanni; Luca Maria Gambardella; Alberto V. Donati

2004-01-01

14

Parallel shortest augmenting path algorithm for the assignment problem. Technical report

We describe a parallel version of the shortest augmenting path algorithm for the assignment problem. While generating the initial dual solution and partial assignment in parallel does not require substantive changes in the sequential algorithm, using several augmenting paths in parallel does require a new dual variable recalculation method. The parallel algorithm was tested on a 14-processor Butterfly Plus computer, on problems with up to 900 million variables. The speedup obtained increases with problem size. The algorithm was also embedded into a parallel branch and bound procedure for the traveling salesman problem on a directed graph, which was tested on the Butterfly Plus on problems involving up to 7,500 cities. To our knowledge, these are the largest assignment problems and traveling salesman problems solved so far.

Balas, E.; Miller, D.; Pekny, J.; Toth, P.

1989-04-01

15

Exploring the runtime of an evolutionary algorithm for the multi-objective shortest path problem.

We present a natural vector-valued fitness function f for the multi-objective shortest path problem, which is a fundamental multi-objective combinatorial optimization problem known to be NP-hard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomial-time randomized approximation scheme (FPRAS) for the problem under consideration, which exemplifies how EAs are able to find good approximate solutions for hard problems. Furthermore, we present lower bounds for the worst-case optimization time. PMID:20560760

Horoba, Christian

2010-01-01

16

A comparison of two new exact algorithms for the robust shortest path problem

Real road networks can be modelled in mathematical terms as interval digraphs, where an interval of travel times (costs) is associated with each arc. Intervals represent uncer- tainty, typical of real situations, about exact travel times. A robust shortest path is a path which is not too far from the shortest one, whatever the exact values of arc costs are.

Roberto Montemanni; Luca Maria; Gambardella Alberto Donati

2004-01-01

17

NASA Astrophysics Data System (ADS)

Successful applications of virtual endoscopy often require the generation of centerlines as flight paths for fly-through examinations of anatomic structures. Criteria for design of effective centerline algorithms should include the following: (1) tracking of the most medial path possible, (2) robustness to segmentation errors, (3) computational efficiency, and (4) minimum of user interaction. To satisfy these design goals, we have developed a centerline generation algorithm based on the chamfer distance transform and Dijkstra's single-source shortest path algorithm. The distance transformation is applied to a segmented volume to determine the distance from each object voxel to the nearest background voxel -- a 'medialness' measure for each voxel. From a user specified source voxel, the distance and path from each object voxel to the source voxel is determined using Dijkstra's single-source shortest path algorithm, with the 'medialness' measure used as the weighting or distance factor between voxels. After execution of the algorithm is complete, paths from all voxels in the object to the source can be easily computed, a feature that is useful for all implementations of virtual endoscopy, but particularly for virtual bronchoscopy, which involves branching. The algorithm runs in O[2n(1 + f)] time, where n is the number of voxels in the volume, and f is the ratio of object voxels to total voxels in the volume. The algorithm is efficient, requiring approximately 90 seconds for a 60 megabyte dataset containing a segmented colon, and is robust to noise, segmentation errors, and start/end voxel selection. The only user interaction required is choosing the starting and ending voxels for the path. We report on objective and subjective evaluations of the algorithm when applied to several mathematical phantoms, the Visible Human Male Dataset and patient exams.

Blezek, Daniel J.; Robb, Richard A.

1999-05-01

18

An exact algorithm for the robust shortest path problem with interval data

terms as shortest path problems on weighted digraphs, where a fixed cost is associated with each arcÂ´nski [10]), is the one we adopt. This criterion is discussed in Kouvelis and Yu [6], a book entirely

Gambardella, Luca Maria

19

In Internet Routing, the static shortest path (SP) problem has been addressed using well known intelligent optimization techniques like artificial neural networks, genetic algorithms (GAs) and particle swarm optimization. Advancement in wireless communication lead more and more mobile wireless networks, such as mobile networks [mobile ad hoc networks (MANETs)] and wireless sensor networks. Dynamic nature of the network is the main characteristic of MANET. Therefore, the SP routing problem in MANET turns into dynamic optimization problem (DOP). Here the nodes ae made aware of the environmental condition, thereby making it intelligent, which goes as the input for GA. The implementation then uses GAs with immigrants and memory schemes to solve the dynamic SP routing problem (DSPRP) in MANETS. In our paper, once the network topology changes, the optimal solutions in the new environment can be searched using the new immigrants or the useful information stored in the memory. Results shows GA with new immigrants sho...

Nair, T R Gopalakrishnan; Yashoda, M B

2011-01-01

20

Gastric cancer, as one of the leading causes of cancer related deaths worldwide, causes about 800,000 deaths per year. Up to now, the mechanism underlying this disease is still not totally uncovered. Identification of related genes of this disease is an important step which can help to understand the mechanism underlying this disease, thereby designing effective treatments. In this study, some novel gastric cancer related genes were discovered based on the knowledge of known gastric cancer related ones. These genes were searched by applying the shortest path algorithm in protein-protein interaction network. The analysis results suggest that some of them are indeed involved in the biological process of gastric cancer, which indicates that they are the actual gastric cancer related genes with high probability. It is hopeful that the findings in this study may help promote the study of this disease and the methods can provide new insights to study various diseases. PMID:24729971

Shi, Ying; Li, Li-Peng; Ren, Hui

2014-01-01

21

An algorithm for the relative robust shortest path problem with interval data

Many real transport and telecommunications problems can be rep- resented in mathematical terms as shortest path problems on weighted digraphs, where a fixed cost is associated with each arc. Sometimes the level of abstraction induced by this model is too high, and consequently more complex representations of reality have to be considered. In this paper the interval data model, where

R. Montemanni; L. M. Gambardella

2002-01-01

22

Highway Hierarchies Hasten Exact Shortest Path Queries

\\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

23

Shorter Path Constraints for the Resource Constrained Shortest Path Problem

Recently, new cost-based filtering algorithms for shorter-path con- straints have been developed. However, so far only the theoretical properties of shorter-path constraint filtering have been studied. We provide the first extensive experimental evaluation of the new algorithms in the context of the resource con- strained shortest path problem. We show how reasoning about path-substructures in combination with CP-based Lagrangian relaxation

Thorsten Gellermann; Meinolf Sellmann; Robert Wright

2005-01-01

24

A shortest path representation for video summarisation

A novel approach is presented to select multiple key frames within an isolated video shot where there is cam- era motion causing significant scene change. This is achieved by determining the dominant motion between frame pairs whose similarities are represented using a di- rected weighted graph. The shortest path in the graph, found using the search algorithm, designates the key

Sarah V. Porter; Majid Mirmehdi; Barry T. Thomas

2003-01-01

25

Robust constrained shortest path problems under budgeted ...

2Department of Mechanical, Energy and Management Engineering, University of ... We study the robust constrained shortest path problem under resource uncertainty. ... can readily extend the algorithms presented in this paper to problems that ... such properties are related to the computational complexity and probabilistic ...

2014-09-12

26

A fuzzy shortest path with the highest reliability

NASA Astrophysics Data System (ADS)

This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max-min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141-164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm.

Keshavarz, Esmaile; Khorram, Esmaile

2009-08-01

27

Semiring Frameworks and Algorithms for Shortest-Distance Problems

We dene general algebraic frameworks for shortest-distance problems based on the structure of semirings. We give a generic algorithm for nding single-source shortest distances in a weighted directed graph when the weights satisfy the conditions of our general semiring framework. The same algorithm can be used to solve ecien tly clas- sical shortest paths problems or to nd the k-shortest

Mehryar Mohri

2002-01-01

28

A branch and bound algorithm for the robust shortest path problem with interval data

problems on interval digraphs, where intervals represent uncertainty about real costs and a robust path, a road network is usually represented as a weighted digraph, where each arc is asso- ciated with a road to a destination node on a network. Also in this case, where the network is usually modelled as a weighted digraph

Gambardella, Luca Maria

29

Finding Shortest Path for Developed Cognitive Map Using Medial Axis

this paper presents an enhancement of the medial axis algorithm to be used for finding the optimal shortest path for developed cognitive map. The cognitive map has been developed, based on the architectural blueprint maps. The idea for using the medial-axis is to find main path central pixels; each center pixel represents the center distance between two side boarder pixels. The need for these pixels in the algorithm comes from the need of building a network of nodes for the path, where each node represents a turning in the real world (left, right, critical left, critical right...). The algorithm also ignores from finding the center pixels paths that are too small for intelligent robot navigation. The Idea of this algorithm is to find the possible shortest path between start and end points. The goal of this research is to extract a simple, robust representation of the shape of the cognitive map together with the optimal shortest path between start and end points. The intelligent robot will use this algorithm i...

Farhan, Hazim A; Al-Ghazi, Suhaib I

2011-01-01

30

Detecting duplicate biological entities using Shortest Path Edit Distance.

Duplicate entity detection in biological data is an important research task. In this paper, we propose a novel and context-sensitive Shortest Path Edit Distance (SPED) extending and supplementing our previous work on Markov Random Field-based Edit Distance (MRFED). SPED transforms the edit distance computational problem to the calculation of the shortest path among two selected vertices of a graph. We produce several modifications of SPED by applying Levenshtein, arithmetic mean, histogram difference and TFIDF techniques to solve subtasks. We compare SPED performance to other well-known distance algorithms for biological entity matching. The experimental results show that SPED produces competitive outcomes. PMID:20815139

Rudniy, Alex; Song, Min; Geller, James

2010-01-01

31

All pairs almost shortest paths

Let G = (V, E) be an unweighted undirected graph on n vertices. A simple argument shows that computing all distances in G with an additive one-sided error of at most is as hard as Boolean matrix multiplication. Building on recent work of Aingworth, Chekuri and Motwani, we describe an O(min n{sup 3/2}m{sup 1/2}, n{sup 7/3}) time algorithm APASP{sub 2} for computing all distances in G with an additive one-sided error of at most 2. The algorithm APASP{sub 2} is simple, easy to implement, and faster than the fastest known matrix multiplication algorithm. Furthermore, for every even k > 2, we describe an O(min n{sup 2} 2/k +2 m 2/2+k, n{sup 2+} 2/3k-2) time algorithm APASP{sub {infinity}} for computing all distances in G with an additive one-sided error of at most k. We also give an O(n 2) time algorithm APASP{sub {infinity}}. for producing stretch 3 estimated distances in an unweighted and undirected graph on n vertices. No constant stretch factor was previously achieved in O(n{sup 2}) time. We say that a weighted graph F = (V,E`) k-emulates an unweighted graph G = (V,E) if for every u, v {element_of} V we have {delta}{sub G} (u, {nu}) {le} {delta}{sub F} (u, {nu}) {le} {delta}{sub G} (u, {nu}) + k. We show that every unweighted graph on n vertices has a 2-emulator with O(n{sup 3/2}) edges and a 4-emulator with O(n{sup 4/3}) edges. These results are asymptotically tight. Finally, we show that any weighted undirected graph on n vertices has a 3-spanner with O(n{sup 1/2}) edges and that such a 3-spanner can be built in O(mn{sup 1/2}) time. We also describe an O(n (m{sup 2/3} + n)) time algorithm for estimating all distances in a weighted undirected graph on n vertices with a stretch factor of at most 3.

Dor, D.; Halperin, S.; Zwick, U. [Tel Aviv Univ. (Israel)

1996-12-31

32

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

33

Fully Dynamic All Pairs Shortest Paths with Real Edge Weights

We present the first fully dynamic algorithm for maintaining all pairs shortest paths in directed graphs with real-valued edge weights. Given a dynamic directed graph G such that each edge can assume at most S different real values, we show how to support updates in O(n2.5 ? S log3 n) amor- tized time and queries in optimal worst-case time. This

Camil Demetrescu; Giuseppe F. Italiano

2001-01-01

34

A new approach to dynamic all pairs shortest paths

We study novel combinatorial properties of graphs that allow us to devise a completely new approach to dynamic all pairs shortest paths problems. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative real-valued edge weights that supports any sequence of operations in O(n2log3n) amortized time per update and unit worst-case time per distance query, where n

Camil Demetrescu; Giuseppe F. Italiano

2004-01-01

35

A new approach to dynamic all pairs shortest paths

We study novel combinatorial properties of graphs that allow us to devise a completely new approach to dynamic all pairs shortest paths problems. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative real-valued edge weights that supports any sequence of operations in Õ(n2) amortized time per update and unit worst-case time per distance query, where n

Camil Demetrescu; Giuseppe F. Italiano

2003-01-01

36

Shortest paths synthesis for a car-like robot

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

37

ON THE ACCELERATION OF SHORTEST PATH CALCULATIONS IN TRANSPORTATION NETWORKS

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

38

An Effective Evolutionary Approach for Bicriteria Shortest Path Routing Problems

NASA Astrophysics Data System (ADS)

Routing problem is one of the important research issues in communication network fields. In this paper, we consider a bicriteria shortest path routing (bSPR) model dedicated to calculating nondominated paths for (1) the minimum total cost and (2) the minimum transmission delay. To solve this bSPR problem, we propose a new multiobjective genetic algorithm (moGA): (1) an efficient chromosome representation using the priority-based encoding method; (2) a new operator of GA parameters auto-tuning, which is adaptively regulation of exploration and exploitation based on the change of the average fitness of parents and offspring which is occurred at each generation; and (3) an interactive adaptive-weight fitness assignment mechanism is implemented that assigns weights to each objective and combines the weighted objectives into a single objective function. Numerical experiments with various scales of network design problems show the effectiveness and the efficiency of our approach by comparing with the recent researches.

Lin, Lin; Gen, Mitsuo

39

Intra-domain traffic engineering with shortest path routing protocols

Throughout the last decade, extensive deployment of popular intra-domain routing protocols such as open shortest path first\\u000a and intermediate system–intermediate system, has drawn an ever increasing attention to Internet traffic engineering. This\\u000a paper reviews optimization techniques that have been deployed for managing intra-domain routing in networks operated with\\u000a shortest path routing protocols, and the state-of-the-art research that has been carried

Aysegül Altin; Bernard Fortz; Mikkel Thorup

2009-01-01

40

Distributional properties of stochastic shortest paths for smuggled nuclear material

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

41

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

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

42

Shortest Path Planning for a Tethered Robot or an Anchored Cable

We consider the problem of planning shortest paths for a tethered robot with a finite length tether in a 2D environment with polygonal obstacles. We present an algorithm that runs in time O((k{sub 1} + 1){sup 2}n{sup 4}) and finds the shortest path or correctly determines that none exists that obeys the constraints; here n is the number obstacle vertices, and k{sub 1} is the number loops in the initial configuration of the tether. The robot may cross its tether but nothing can cross obstacles, which cause the tether to bend. The algorithm applies as well for planning a shortest path for the free end of an anchored cable.

Xavier, P.G.

1999-02-22

43

Interval order representation via shortest paths Garth Isaak

results for potentials in digraphs. This viewpoint yields short proofs of the representation theorems the reals may be required. For more on this see Fish- burn's book [4]. For this paper we will stick to potentials, shortest paths and negative cycles in digraphs. We will assume that all orders considered

Isaak, Garth

44

Minimizing communication in all-pairs shortest paths Edgar Solomonik

Minimizing communication in all-pairs shortest paths Edgar Solomonik Aydin Buluc James Demmel Electrical Engineering and Computer Sciences University of California at Berkeley Technical Report No. UCB Solomonik Univ. of California, Berkeley Department of EECS solomon@eecs.berkeley.edu Aydin BuluÃ§ Lawrence

California at Berkeley, University of

45

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

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

46

A Bio-Inspired Method for the Constrained Shortest Path Problem

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

47

A Graph Search Heuristic for Shortest Distance Paths

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

48

The robust shortest path problem with interval data via Benders decomposition

Many real problems can be modelled as robust shortest path problems on digraphs with interval costs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible configuration of the arc costs. In this paper we discuss the application of a Benders decomposition approach to this problem. Computational results

Roberto Montemanni; Luca Maria Gambardella

2005-01-01

49

Damage detection via shortest-path network sampling.

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. PMID:25353853

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

2014-05-01

50

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

51

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

52

A Benders decomposition approach for the robust shortest path problem with interval data

}@idsia.ch Abstract Many real problems can be modelled as robust shortest path problems on digraphs with interval terms, a network is usually represented as a weighted digraph, where arcs are associated], a book entirely devoted to robust discrete optimization. A robust deviation shortest path from

Gambardella, Luca Maria

53

MIKKEL THORUP & MATTHEW ROUGHAN 1 Avoiding Ties in Shortest Path First Routing

MIKKEL THORUP & MATTHEW ROUGHAN 1 Avoiding Ties in Shortest Path First Routing Mikkel Thorup,roughan)@research.att.com Abstract---First we discuss problems associated with ties and flow splitting with shortest path first ties and yet minimize congesÂ tion. On real and synthetic networks we demonstrate experimentally

Roughan, Matthew

54

MIKKEL THORUP & MATTHEW ROUGHAN 1 Avoiding Ties in Shortest Path First Routing

MIKKEL THORUP & MATTHEW ROUGHAN 1 Avoiding Ties in Shortest Path First Routing Mikkel Thorup,roughan)@research.att.com Abstract--First we discuss problems associated with ties and flow splitting with shortest path first ties and yet minimize conges- tion. On real and synthetic networks we demonstrate experimentally

Roughan, Matthew

55

We provide an improved FPTAS for multiobjective shortest paths—a fundamental (NP-hard) problem in multiobjective optimization—along\\u000a with a new generic method for obtaining FPTAS to any multiobjective optimization problem with non-linear objectives. We show how these results can be used to obtain better approximate solutions to three related problems, multiobjective\\u000a constrained [optimal] path and non-additive shortest path, that have important applications

George Tsaggouris; Christos D. Zaroliagis

2009-01-01

56

We provide an improved FPTAS for multiobjective shortest paths—a fundamental (NP-hard) problem in multiobjective optimization—along with a new generic method for obtaining FPTAS to any multiobjective optimization problem with non-linear objectives. We show how these results can be used to obtain better approximate solutions to three related problems, multiobjective constrained (optimal) path and non-additive shortest path, that have important applications

George Tsaggouris; Christos D. Zaroliagis

2006-01-01

57

A NEW APPROACH IN SYSTEM RELIABILITY EVALUATION, SHORTEST PATH OF E-NETWORKS

By applying shortest path analysis in stochastic networks, we introduce a new approach to obtain the reliability function of time-dependent systems. We assume that not all elements of the system are set to function from the beginning. Upon the failure of each element of the active path in the reliability graph, the system switches to the next path. Then, the

A. AZARON; M. MODARRES

58

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

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

59

Snell's law and light traveling along the shortest path

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

60

Discrete Approximation to Continuous Anisotropic Shortest-Path Problem

-path (CSP) problem in 3D. Â· Incorporates ellipsoid model of radar cross sections of UAVs. Carlyle, Royset-Risk Path Planning for Groups of UAVs James Riehl JoÃ£o Hespanha INFORMS Meeting November 6, 2007 #12;start + #12;Minimum-Risk Path Planning for Groups of UAVs ( , )x v xi xf Â· Heterogeneous group of M UAVs Â· K

Hespanha, JoÃ£o Pedro

61

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

62

FAST NUMERICAL METHODS BASED ON SDES FOR SEVERAL PROBLEMS RELATED TO THE SHORTEST PATH

or disappearing at arbitrary times. The methods are based on solving finite dimensional stochastic differential into a finite dimensional problem of finding points on the boundaries to connect those line segments and arcs, JUN LU, HAO-MIN ZHOU Figure 1. Structure of a shortest path set, namely a finite dimensional set K

Soatto, Stefano

63

Transitive Functional Annotation by Shortest-path Analysis of Gene Expression Data

attribute to link genes of the same biological pathway. Based on large-scale yeast microarray expression data, we use the shortest-path analysis to identify transitive genes between two given genes from the same biological process. We find that not only functionally related genes with correlated expression profiles are identified but also those without. In the latter case, we compare our method

Xianghong Zhou; Ming-Chih J. Kao; Wing Hung Wong

2002-01-01

64

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

65

algorithmic applications (see survey papers [14, 6, 21]), and the problem underlying many cryptographic for the cryptographic function. In this paper we present and analyze new algorithms to find the shortest vectorFaster exponential time algorithms for the shortest vector problem Daniele Micciancio Panagiotis

Wang, Deli

66

Solution Methods for the Multi-trip Elementary Shortest Path ...

Previous Work. Because ... The most common resources considered are such things as vehicle capacity, time windows, and maximum ... Outline. One typical setting in which an algorithm for the ESPPRC is required is the solution of the capac-.

2011-03-15

67

NASA Astrophysics Data System (ADS)

We present an algorithm which returns a shortest path and related number of entanglements for a given configuration of a polymeric system in 2 or 3 dimensions. Rubinstein and Helfand, and later Everaers et al. introduced a concept to extract primitive paths for dense polymeric melts made of linear chains (a multiple disconnected multibead 'path'), where each primitive path is defined as a path connecting the (space-fixed) ends of a polymer under the constraint of non-interpenetration (excluded volume) between primitive paths of different chains, such that the multiple disconnected path fulfills a minimization criterion. The present algorithm uses geometrical operations and provides a—model independent—efficient approximate solution to this challenging problem. Primitive paths are treated as 'infinitely' thin (we further allow for finite thickness to model excluded volume), and tensionless lines rather than multibead chains, excluded volume is taken into account without a force law. The present implementation allows to construct a shortest multiple disconnected path (SP) for 2D systems (polymeric chain within spherical obstacles) and an optimal SP for 3D systems (collection of polymeric chains). The number of entanglements is then simply obtained from the SP as either the number of interior kinks, or from the average length of a line segment. Further, information about structure and potentially also the dynamics of entanglements is immediately available from the SP. We apply the method to study the 'concentration' dependence of the degree of entanglement in phantom chain systems. Program summaryTitle of program:Z Catalogue number:ADVG Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADVG Program obtainable from: CPC Program Library, Queen's University of Belfast, N. Ireland Computer for which the program is designed and others on which it has been tested: Silicon Graphics (Irix), Sun (Solaris), PC (Linux) Operating systems or monitors under which the program has been tested: UNIX, Linux Program language used: USANSI Fortran 77 and Fortran 90 Memory required to execute with typical data: 1 MByte No. of lines in distributed program, including test data, etc.: 10 660 No. of bytes in distributed program, including test data, etc.: 119 551 Distribution formet:tar.gz Nature of physical problem: The problem is to obtain primitive paths substantiating a shortest multiple disconnected path (SP) for a given polymer configuration (chains of particles, with or without additional single particles as obstacles for the 2D case). Primitive paths are here defined as in [M. Rubinstein, E. Helfand, J. Chem. Phys. 82 (1985) 2477; R. Everaers, S.K. Sukumaran, G.S. Grest, C. Svaneborg, A. Sivasubramanian, K. Kremer, Science 303 (2004) 823] as the shortest line (path) respecting 'topological' constraints (from neighboring polymers or point obstacles) between ends of polymers. There is a unique solution for the 2D case. For the 3D case it is unique if we construct a primitive path of a single chain embedded within fixed line obstacles [J.S.B. Mitchell, Geometric shortest paths and network optimization, in: J.-R. Sack, J. Urrutia (Eds.), Handbook of Computational Geometry, Elsevier, Amsterdam, 2000, pp. 633-701]. For a large 3D configuration made of several chains, short is meant to be the Euclidean shortest multiple disconnected path (SP) where primitive paths are constructed for all chains simultaneously. While the latter problem, in general, does not possess a unique solution, the algorithm must return a locally optimal solution, robust against minor displacements of the disconnected path and chain re-labeling. The problem is solved if the number of kinks (or entanglements Z), explicitly deduced from the SP, is quite insensitive to the exact conformation of the SP which allows to estimate Z with a small error. Efficient method of solution: Primitive paths are constructed from the given polymer configuration (a non-shortest multiple disconnected path, including obstacles, if present) by first replacing each polymer contour by a line wi

Kröger, Martin

2005-06-01

68

A critical exponent for shortest-path scaling in continuum percolation

NASA Astrophysics Data System (ADS)

We carry out Monte Carlo experiments to study the scaling behavior of shortest path lengths in continuum percolation. These studies suggest that the critical exponent governing this scaling is the same for both continuum and lattice percolation. We use splitting, a technique that has not yet been fully exploited in the physics literature, to increase the speed of our simulations. This technique can also be applied to other models where clusters are grown sequentially.

Brereton, Tim; Hirsch, Christian; Schmidt, Volker; Kroese, Dirk

2014-12-01

69

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

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

70

An exact algorithm for the capacitated shortest spanning arborescence

We are given a complete and loop-free digraphG=(V, A), whereV={1,...,n} is the vertex set,A={(i, j) :i, j ?V} the arc set, andr ?V is a distinguishedroot vertex. For each arc (i, j) ?A, letcij be the associatedcost, and for each vertexi, letqi?0 be the associateddemand (withqr=0). Moreover, a nonnegativebranch capacity, Q, is defined.A Capacitated Shortest Spanning Arborescence rooted at r

Paolo Toth; Daniele Vigo

1995-01-01

71

Shortest-path fractal dimension for percolation in two and three dimensions.

We carry out a high-precision Monte Carlo study of the shortest-path fractal dimension d(min) for percolation in two and three dimensions, using the Leath-Alexandrowicz method which grows a cluster from an active seed site. A variety of quantities are sampled as a function of the chemical distance, including the number of activated sites, a measure of the radius, and the survival probability. By finite-size scaling, we determine d(min)=1.13077(2) and 1.3756(6) in two and three dimensions, respectively. The result in two dimensions rules out the recently conjectured value d(min)=217/192 [Deng et al., Phys. Rev. E 81, 020102(R) (2010)]. PMID:23367887

Zhou, Zongzheng; Yang, Ji; Deng, Youjin; Ziff, Robert M

2012-12-01

72

A Shortest Path Representation for Video Summarisation S.V. Porter, M. Mirmehdi and B.T. Thomas

A Shortest Path Representation for Video Summarisation S.V. Porter, M. Mirmehdi and B.T. Thomas information from the video and enable content-based video browsing. 2 Video Summarisation Different approaches to video summarisation often de- pend on the purpose of the abstract. Lienhart et al. [8] concentrate

Mirmehdi, Majid

73

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

Bi-Qing Li; Tao Huang; Lei Liu; Yu-Dong Cai; Kuo-Chen Chou

2012-01-01

74

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

75

Shortest trajectory planning of wheeled mobile robots with constraints

In this paper, we suggest a shortest trajectory planning algorithm for wheeled mobile robots with constraints; bounded curvature paths and moving forward only motion of robots; for example, aerial vehicles or moving forward car-like mobile robots. The main purpose of the paper is to find the optimal shortest path between a starting point and a goal point with constraints. Based

Joe W. Yeol; Y. S. Ryu; M. A. Montalvo

2005-01-01

76

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

77

A path-following algorithm for missiles

The missile path-following problem has not been studied particularly as much as other vehicles. This fact is the source of our motivation behind this work. In this paper, a path-following algorithm, which is specifically designed for missiles but can be applied to other vehicles as well, is proposed. Presented algorithm is composed of a feedback and feed-forward control rule. Feedback

Gorkem Secer

2012-01-01

78

Stochastic Evolutionary Algorithms for Planning Robot Paths

NASA Technical Reports Server (NTRS)

A computer program implements stochastic evolutionary algorithms for planning and optimizing collision-free paths for robots and their jointed limbs. Stochastic evolutionary algorithms can be made to produce acceptably close approximations to exact, optimal solutions for path-planning problems while often demanding much less computation than do exhaustive-search and deterministic inverse-kinematics algorithms that have been used previously for this purpose. Hence, the present software is better suited for application aboard robots having limited computing capabilities (see figure). The stochastic aspect lies in the use of simulated annealing to (1) prevent trapping of an optimization algorithm in local minima of an energy-like error measure by which the fitness of a trial solution is evaluated while (2) ensuring that the entire multidimensional configuration and parameter space of the path-planning problem is sampled efficiently with respect to both robot joint angles and computation time. Simulated annealing is an established technique for avoiding local minima in multidimensional optimization problems, but has not, until now, been applied to planning collision-free robot paths by use of low-power computers.

Fink, Wolfgang; Aghazarian, Hrand; Huntsberger, Terrance; Terrile, Richard

2006-01-01

79

Computing shortest heterochromatic monotone routes

Abstract. Given a set of n points on the plane colored with k • n colors, the Trip Planning Problem asks for the shortest path visiting the k colors. It is a well-known NP-hard problem. We show that under some natural constraints on the path, the problem can be solved in polynomial time. Keywords: Routing; Heterochromatic Monotone Route; Shortest Path;

José Miguel Díaz-báñez; G. Hernández; D. Oliveros; A. Ramírez-vigueras; Joan Antoni Sellarès; Jorge Urrutia; Inmaculada Ventura

2008-01-01

80

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

81

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-12-01

82

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

83

Percolation threshold, Fisher exponent, and shortest path exponent for four and five dimensions.

We develop a method of constructing percolation clusters that allows us to build very large clusters using very little computer memory by limiting the maximum number of sites for which we maintain state information to a number of the order of the number of sites in the largest chemical shell of the cluster being created. The memory required to grow a cluster of mass s is of the order of s(straight theta) bytes where straight theta ranges from 0.4 for two-dimensional (2D) lattices to 0.5 for six (or higher)-dimensional lattices. We use this method to estimate d(min), the exponent relating the minimum path l to the Euclidean distance r, for 4D and 5D hypercubic lattices. Analyzing both site and bond percolation, we find d(min)=1.607+/-0.005 (4D) and d(min)=1.812+/-0.006 (5D). In order to determine d(min) to high precision, and without bias, it was necessary to first find precise values for the percolation threshold, p(c): p(c)=0.196889+/-0.000003 (4D) and p(c)=0.14081+/-0.00001 (5D) for site and p(c)=0.160130+/-0.000003 (4D) and p(c)=0.118174+/-0.000004 (5D) for bond percolation. We also calculate the Fisher exponent tau determined in the course of calculating the values of p(c): tau=2.313+/-0.003 (4D) and tau=2.412+/-0.004 (5D). PMID:11497659

Paul, G; Ziff, R M; Stanley, H E

2001-08-01

84

An Adaptive Path Planning Algorithm for Cooperating Unmanned Air Vehicles

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

85

Adaptive path planning algorithm for cooperating unmanned air vehicles

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

86

Path Cost Optimization Using Genetic Algorithm with Supervised Crossover Operator

Path Cost Optimization Using Genetic Algorithm with Supervised Crossover Operator Chi-Tsun Cheng of these algorithms rise dras- tically. Meta-heuristic algorithms such as evolutionary al- gorithms and genetic-based path cost optimization algorithm is proposed. The generic crossover operator in genetic algorithms

Tse, Chi K. "Michael"

87

Algorithms and Sensors for Small Robot Path Following

NASA Technical Reports Server (NTRS)

Tracked mobile robots in the 20 kg size class are under development for applications in urban reconnaissance. For efficient deployment, it is desirable for teams of robots to be able to automatically execute path following behaviors, with one or more followers tracking the path taken by a leader. The key challenges to enabling such a capability are (l) to develop sensor packages for such small robots that can accurately determine the path of the leader and (2) to develop path following algorithms for the subsequent robots. To date, we have integrated gyros, accelerometers, compass/inclinometers, odometry, and differential GPS into an effective sensing package. This paper describes the sensor package, sensor processing algorithm, and path tracking algorithm we have developed for the leader/follower problem in small robots and shows the result of performance characterization of the system. We also document pragmatic lessons learned about design, construction, and electromagnetic interference issues particular to the performance of state sensors on small robots.

Hogg, Robert W.; Rankin, Arturo L.; Roumeliotis, Stergios I.; McHenry, Michael C.; Helmick, Daniel M.; Bergh, Charles F.; Matthies, Larry

2002-01-01

88

PCB drill path optimization by combinatorial cuckoo search algorithm.

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

PCB Drill Path Optimization by Combinatorial Cuckoo Search Algorithm

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

90

Algorithms for Computing QoS Paths with Restoration

1 Algorithms for Computing QoS Paths with Restoration Yigal Bejerano, Yuri Breitbart, Member, IEEE and the restoration topology should be a major consideration of the routing process. We undertake a comprehensive study of problems related to finding suitable restoration topologies for QoS paths. We consider both

Sprintson, Alexander

91

In the cancer research recently, it still doesn't have a definitive conclusion for the regulatory mechanisms of tumorigenesis and metastasis. But different genes have different biological functions, and these functions with interactions between genes play an important key in gene regulatory networks. Microarray is a tool most commonly used in the disease research, and scientists usually use that the feature

Meng-Hsiun Tsai; Hsiao-Han Ko; Sheng-Chuan Chiu

2010-01-01

92

Extracting optimal paths from roadmaps for motion planning

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

93

The optimal path algorithm for emergency rescue for drilling accidents

Addressing flaws in the traditional Dijkstra Algorithm, this paper proposes an improved optimal path algorithm applicable to the GIS drilling accident emergency rescue system. To begin, the paper uses the modified comprehensive analytic hierarchy process to analyze various factors of road conditions, considers the element of urgency, then sets up the digraph with weights of the running time of the

Wenjing Ma; Yingzhuo Xu; Hui Xie

2009-01-01

94

Path Planning Algorithms for Multiple Heterogeneous Vehicles

: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30 viii LIST OF FIGURES FIGURE Page 1 Example solution of PCATSP : : : : : : : : : : : : : : : : : : : : : : 12 2 Example solutions of Hamiltonian path problem : : : : : : : : : : : : 15 3 Edge subset in an infeasible solution... : : : : : : : : : : : : : : : : : : 17 4 "W" set in an infeasible solution : : : : : : : : : : : : : : : : : : : : 17 5 Edges dictating the "W" cut : : : : : : : : : : : : : : : : : : : : : : 18 6 LP feasible solution : : : : : : : : : : : : : : : : : : : : : : : : : : : 20 7 Remove...

Oberlin, Paul V.

2010-01-16

95

Aviation safety is the base for the operation of air transportation system. It plays a significant role in maneuvering accidents quickly and efficiently. In this paper, the network of airport on the airside was analyzed from the aspect of aviation safety; then a nodes-arcs relation database was built to describe the airside network topology and the Dijkstra algorithm was employed

Chen Xin; Xiucheng Guo; Dongtao Fan

2011-01-01

96

ONLINE ALGORITHMS FOR PATH SELECTION IN A NONBLOCKING NETWORK #

. (bmm@cs.cmu.edu). 1 #12; 2 S. ARORA AND F. T. LEIGHTON AND B. M. MAGGS Bob Ted Pat Vanna Carol AliceONÂLINE ALGORITHMS FOR PATH SELECTION IN A NONBLOCKING NETWORK # SANJEEV ARORA + , F. THOMSON, routing algoÂ rithm AMS subject classifications. 68M10, 90B12, 94C10 1. Introduction. 1.1. Definitions

Maggs, Bruce M.

97

A genetic algorithm approach to piping route path planning

A genetic algorithm (GA) approach to support interactive planning of a piping route path in plant layout design is presented. To present this approach, the paper mainly describes the basic ideas used in the methodology, which include the definition of genes to deal with pipe routes, the concept of spatial potential energy, the method of generating initial individuals for GA

TERUAKI ITO

1999-01-01

98

Faster algorithms for minimum-link paths with restricted orientations

Faster algorithms for minimum-link paths with restricted orientations Valentin Polishchuk and Mikko-vertex rectilinear domain in 3D, and let s, t P be given points; the goal is to find a minimum-link rectilinear s-t

99

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

100

Genetic-algorithm-based path optimization methodology for spatial decision

NASA Astrophysics Data System (ADS)

In this paper, we proposed a method based on GA to solve the path-optimization problem. Unlike the traditional methods, it considers many other factors besides the road length including the task assignment and its balance, which are beyond the capability of path analysis and make this problem a Combinatorial Optimization problem. It can't be solved by a traditional graph-based algorithm. This paper proposes a new algorithm that integrates the Graph Algorithm and Genetic Algorithm together to solve this problem. The traditional Graph-Algorithm is responsible for preprocessing data and GA is responsible for the global optimization. The goal is to find the best combination of paths to meet the requirement of time, cost and the reasonable task assignment. The prototype of this problem is named the TSP (Traveling Salesman Problem) problem and known as NP-Hard Problem. However, we demonstrate how these problems are resolved by the GA without complicated programming, the result proves it's effective. The technique presented in this paper is helpful to those GIS developer working on an intelligent system to provide more effective decision-making.

Yu, Liang; Bian, Fuling

2006-10-01

101

A Bat Algorithm with Mutation for UCAV Path Planning

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

102

A bat algorithm with mutation for UCAV path planning.

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

103

Sep 19, 2014 ... ?Andreas Darmann was supported by the Austrian Science Fund (FWF): [P .... der the additional restriction that the degree of every vertex is bounded by a ...... on Logic in Computer Science, LICS 2012, pages 205–214, 2012.

2014-09-19

104

Analysis of the contact graph routing algorithm: Bounding interplanetary paths

NASA Astrophysics Data System (ADS)

Interplanetary communication networks comprise orbiters, deep-space relays, and stations on planetary surfaces. These networks must overcome node mobility, constrained resources, and significant propagation delays. Opportunities for wireless contact rely on calculating transmit and receive opportunities, but the Euclidean-distance diameter of these networks (measured in light-seconds and light-minutes) precludes node discovery and contact negotiation. Propagation delay may be larger than the line-of-sight contact between nodes. For example, Mars and Earth orbiters may be separated by up to 20.8 min of signal propagation time. Such spacecraft may never share line-of-sight, but may uni-directionally communicate if one orbiter knows the other's future position. The Contact Graph Routing (CGR) approach is a family of algorithms presented to solve the messaging problem of interplanetary communications. These algorithms exploit networks where nodes exhibit deterministic mobility. For CGR, mobility and bandwidth information is pre-configured throughout the network allowing nodes to construct transmit opportunities. Once constructed, routing algorithms operate on this contact graph to build an efficient path through the network. The interpretation of the contact graph, and the construction of a bounded approximate path, is critically important for adoption in operational systems. Brute force approaches, while effective in small networks, are computationally expensive and will not scale. Methods of inferring cycles or other librations within the graph are difficult to detect and will guide the practical implementation of any routing algorithm. This paper presents a mathematical analysis of a multi-destination contact graph algorithm (MD-CGR), demonstrates that it is NP-complete, and proposes realistic constraints that make the problem solvable in polynomial time, as is the case with the originally proposed CGR algorithm. An analysis of path construction to complement hop-by-hop forwarding is presented as the CGR-EB algorithm. Future work is proposed to handle the presence of dynamic changes to the network, as produced by congestion, link disruption, and errors in the contact graph. We conclude that pre-computation, and thus CGR style algorithms, is the only efficient method of routing in a multi-node, multi-path interplanetary network and that algorithmic analysis is the key to its implementation in operational systems.

Birrane, Edward; Burleigh, Scott; Kasch, Niels

2012-06-01

105

On Models of Nonlinear Evolution Paths in Adiabatic Quantum Algorithms

NASA Astrophysics Data System (ADS)

In this paper, we study two different nonlinear interpolating paths in adiabatic evolution algorithms for solving a particular class of quantum search problems where both the initial and final Hamiltonian are one-dimensional projector Hamiltonians on the corresponding ground state. If the overlap between the initial state and final state of the quantum system is not equal to zero, both of these models can provide a constant time speedup over the usual adiabatic algorithms by increasing some another corresponding “complexity". But when the initial state has a zero overlap with the solution state in the problem, the second model leads to an infinite time complexity of the algorithm for whatever interpolating functions being applied while the first one can still provide a constant running time. However, inspired by a related reference, a variant of the first model can be constructed which also fails for the problem when the overlap is exactly equal to zero if we want to make up the “intrinsic" fault of the second model — an increase in energy. Two concrete theorems are given to serve as explanations why neither of these two models can improve the usual adiabatic evolution algorithms for the phenomenon above. These just tell us what should be noted when using certain nonlinear evolution paths in adiabatic quantum algorithms for some special kind of problems.

Sun, Jie; Lu, Song-Feng; Samuel, L. Braunstein

2013-01-01

106

Algorithms for an Unmanned Vehicle Path Planning Problem

ALGORITHMS FOR AN UNMANNED VEHICLE PATH PLANNING PROBLEM A Thesis by JIANGLEI QIN 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... Chair of Committee, Sivakumar Rathinam Committee Members, Darbha Swaroop Bruce Wang Head of Department, Andreas A. Polycarpou August 2013 Major Subject: Mechanical Engineering Copyright 2013 Jianglei Qin ii ABSTRACT Unmanned...

Qin, Jianglei

2013-06-25

107

A surface hopping algorithm for nonadiabatic minimum energy path calculations.

The article introduces a robust algorithm for the computation of minimum energy paths transiting along regions of near-to or degeneracy of adiabatic states. The method facilitates studies of excited state reactivity involving weakly avoided crossings and conical intersections. Based on the analysis of the change in the multiconfigurational wave function the algorithm takes the decision whether the optimization should continue following the same electronic state or switch to a different state. This algorithm helps to overcome convergence difficulties near degeneracies. The implementation in the MOLCAS quantum chemistry package is discussed. To demonstrate the utility of the proposed procedure four examples of application are provided: thymine, asulam, 1,2-dioxetane, and a three-double-bond model of the 11-cis-retinal protonated Schiff base. © 2015 Wiley Periodicals, Inc. PMID:25564760

Schapiro, Igor; Roca-Sanjuán, Daniel; Lindh, Roland; Olivucci, Massimo

2015-02-15

108

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

109

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

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

110

A Method Based on Genetic Algorithm for Anti-ship Missile Path Planning

This paper presented a novel approach to search and optimize path points for anti-ship missile path planning. We utilized the method of MAKLINK graph to construct free space, and then, a global state connected graph is built up for searching for all possible routes. genetic algorithm is used to search and optimize path points severally in these local routes. According

Xuechun Zhao; Xiaohong Fan

2009-01-01

111

Microwave radiometer measurements at Liquid water path algorithm development and accuracy

temperature is twice as sensitive to liquid water as to water vapour. (Sensitivity to ice is negligible calibration. 3. LIQUID WATER PATH RETRIEVAL ALGORITHM. 3.1 Relationship between radiometer output temperature 4.6.2 Water vapour path and liquid water path 5. CONCLUSION. REFERENCES. #12;3 1 INTRODUCTION

Reading, University of

112

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

113

A Generic Path Algorithm for Regularized Statistical Estimation

Regularization is widely used in statistics and machine learning to prevent overfitting and gear solution towards prior information. In general, a regularized estimation problem minimizes the sum of a loss function and a penalty term. The penalty term is usually weighted by a tuning parameter and encourages certain constraints on the parameters to be estimated. Particular choices of constraints lead to the popular lasso, fused-lasso, and other generalized ?1 penalized regression methods. In this article we follow a recent idea by Wu (2011, 2012) and propose an exact path solver based on ordinary differential equations (EPSODE) that works for any convex loss function and can deal with generalized ?1 penalties as well as more complicated regularization such as inequality constraints encountered in shape-restricted regressions and nonparametric density estimation. Non-asymptotic error bounds for the equality regularized estimates are derived. In practice, the EPSODE can be coupled with AIC, BIC, Cp or cross-validation to select an optimal tuning parameter, or provides a convenient model space for performing model averaging or aggregation. Our applications to generalized ?1 regularized generalized linear models, shape-restricted regressions, Gaussian graphical models, and nonparametric density estimation showcase the potential of the EPSODE algorithm. PMID:25242834

Zhou, Hua; Wu, Yichao

2014-01-01

114

A Distributed Multi-commodity Flow Approximation Algorithm for Path Restoration

A Distributed Multi-commodity Flow Approximation Algorithm for Path Restoration S multicommodity network flow prob- lem has many applications in the areas of routing and telecom- munications. Compared to decades of research in centralized multicommodity flow algorithms, distributed algorithms have

Venkatesan, S.

115

Genetic Algorithm-Based Test Data Generation for Multiple Paths via Individual Sharing

The application of genetic algorithms in automatically generating test data has aroused broad concerns and obtained delightful achievements in recent years. However, the efficiency of genetic algorithm-based test data generation for path testing needs to be further improved. In this paper, we establish a mathematical model of generating test data for multiple paths coverage. Then, a multipopulation genetic algorithm with individual sharing is presented to solve the established model. We not only analyzed the performance of the proposed method theoretically, but also applied it to various programs under test. The experimental results show that the proposed method can improve the efficiency of generating test data for many paths' coverage significantly.

Gong, Dunwei

2014-01-01

116

.4 TSA for repeatedly solving RCSP......................................................................42 5.5 Summary.............................................................................................................43 VI LABEL...-SETTING ALGORITHM ...........................................................................44 VII COMPUTATIONAL EVALUATION OF TSA......................................................47 7.1 Test problems and computational platform...

Zhu, Xiaoyan

2007-04-25

117

Design and Protection Algorithms for Path Level Aggregation of Traffic in WDM Metro Optical Networks

Design and Protection Algorithms for Path Level Aggregation of Traffic in WDM Metro Optical . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv CHAPTER 1. IP over Optical Networks - Introduction . . . . . . . . . . . . 1 1.1 Traditional Metro . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 New Metro Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1

118

The Path-of-Probability Algorithm for Steering and Feedback Control of Flexible Needles

In this paper we develop a new framework for path planning of flexible needles with bevel tips. Based on a stochastic model of needle steering, the probability density function for the needle tip pose is approximated as a Gaussian. The means and covariances are estimated using an error propagation algorithm which has second order accuracy. Then we adapt the path-of-probability (POP) algorithm to path planning of flexible needles with bevel tips. We demonstrate how our planning algorithm can be used for feedback control of flexible needles. We also derive a closed-form solution for the port placement problem for finding good insertion locations for flexible needles in the case when there are no obstacles. Furthermore, we propose a new method using reference splines with the POP algorithm to solve the path planning problem for flexible needles in more general cases that include obstacles. PMID:21151708

Park, Wooram; Wang, Yunfeng; Chirikjian, Gregory S.

2010-01-01

119

Transport path optimization algorithm based on fuzzy integrated weights

NASA Astrophysics Data System (ADS)

Natural disasters cause significant damage to roads, making route selection a complicated logistical problem. To overcome this complexity, we present a method of using a trapezoidal fuzzy number to select the optimal transport path. Using the given trapezoidal fuzzy edge coefficients, we calculate a fuzzy integrated matrix, and incorporate the fuzzy multi-weights into fuzzy integrated weights. The optimal path is determined by taking two sets of vertices and transforming undiscovered vertices into discoverable ones. Our experimental results show that the model is highly accurate, and requires only a few measurement data to confirm the optimal path. The model provides an effective, feasible, and convenient method to obtain weights for different road sections, and can be applied to road planning in intelligent transportation systems.

Hou, Yuan-Da; Xu, Xiao-Hao

2014-11-01

120

Path Planning Using a Hybrid Evolutionary Algorithm Based on Tree Structure Encoding

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

Wang, Siao-En; Guo, Jian-Horn

2014-01-01

121

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

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

122

Some Applications of String Algorithms in Human-Computer Interaction

NASA Astrophysics Data System (ADS)

Two applications of string algorithms in human-computer interaction are reviewed: one for comparing error rates of text entry techniques, another for abstracting collections of scan paths (paths of eye movements). For both applications, the classic string edit distance algorithm proves useful. For the latter application shortest common supersequences provide one option for further development. Applying them as such could be misleading, but a suitable approximation could provide a useful representation of a set of scan paths.

Räihä, Kari-Jouko

123

Quantum Adiabatic Algorithms, Small Gaps, and Different Paths

We construct a set of instances of 3SAT which are not solved efficiently using the simplestquantum adiabatic algorithm. These instances are obtained by picking randomclauses all consistent with two disparate planted solutions ...

Farhi, Edward

124

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.

125

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

126

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

127

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

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

128

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

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

129

Formal language constrained path problems

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

130

Short paths in expander graphs

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

131

Interval Order Representation via Shortest Paths

Our goal in this paper is to illustrate how the representation theorems for finite interval orders and semiorders can be seen\\u000a as special instances of existence results for potentials in digraphs. This viewpoint yields short proofs of the representation\\u000a theorems and provides a framework for certain types of additional constraints on the intervals. We also use it to obtain a

Garth Isaak

132

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

133

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

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

134

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

135

ON-LINE ALGORITHMS FOR PATH SELECTION IN A NONBLOCKING NETWORK

. ARORA AND F. T. LEIGHTON AND B. M. MAGGS Bob Ted Pat Vanna Carol Alice Fig. 1.1. A nonblocking networkON-LINE ALGORITHMS FOR PATH SELECTION IN A NONBLOCKING NETWORK SANJEEV ARORA , F. THOMSON LEIGHTON AMS subject classifications. 68M10, 90B12, 94C10 1. Introduction. 1.1. Definitions. Nonblocking

Arora, Sanjeev

136

Cycles and Paths in Semicomplete Multipartite Digraphs, Theorems and Algorithms: A Survey

digraphs too) and a book by J. Moon [58] where the properties of tournaments are considered. J. Moon [58Cycles and Paths in Semicomplete Multipartite Digraphs, Theorems and Algorithms: A Survey G. Gutin March 9, 2003 Abstract A digraph obtained by replacing each edge of a complete m-partite graph by an arc

Gutin, Gregory

137

A fast algorithm for determining the propagation path of multiple diffracted rays

1 A fast algorithm for determining the propagation path of multiple diffracted rays Patrizia of multiple diffracted rays relevant to ray tracing techniques. The focus is on double diffracted rays edges. Index Terms-- Multiple diffraction, Ray tracing, Electromag- netic edge diffraction, HF wave

Buffa, Annalisa

138

A 'near-optimum' multiple path routing algorithm for space-based SDI networks

NASA Astrophysics Data System (ADS)

An adaptive routing algorithm for a midcourse, space-based SDI (Strategic Defense Initiative) architecture is presented. The goals include rapid recovery from both predictable and unpredictable outages as well as load balancing. Robust operation is critical. The routing table update algorithm is distributed, and it produces loop-free routes from periodic topology update information. In addition, multiple routes are found from source to destination nodes. This allows load splitting among these routes to achieve more effective load balancing. A heuristic is used to distribute the load among these routes. The basic algorithm also provides a mechanism to provide path diversity for added survivability. Recovery from failures detected locally occurs immediately through the use of alternate routes and an event-driven failure recovery algorithm. Simulation results are presented to demonstrate the algorithm behavior.

Cain, J. Bibb; Adams, Stanley L.; Noakes, Michael D.; Kryst, Tom; Althouse, Edwin L.

139

AUTONOMOUS ROBOT NAVIGATION USING A GENETIC ALGORITHM WITH AN EFFICIENT GENOTYPE ADITIA HERMANU

1 AUTONOMOUS ROBOT NAVIGATION USING A GENETIC ALGORITHM WITH AN EFFICIENT GENOTYPE STRUCTURE ADITIA & Computer Sciences Tulsa, Oklahoma ABSTRACT The goal for real-time mobile robots is to travel the shortest robots to plan this path without the need for human intervention. The path- planning problem has been

Wainwright, Roger L.

140

NSDL National Science Digital Library

Started in the 1970s as an agency to assist men and women in gaining access to a variety of birth control methods, PATH has since expanded its focus to provide "sustainable, culturally relevant [health] solutions, enabling communities worldwide to break longstanding cycles of poor health." The PATH website has more than a dozen videos and slideshows available to visitors at the "Our Multimedia" link near the bottom right hand corner of the homepage. A three-minute video entitled "Better Nutrition For Life" educates visitors about an innovative rice product that could bring greater nutrition to millions of malnourished people where rice is a staple food. The product is Ultra Rice, and is actually fortified pasta that looks, cooks, and tastes like rice, but is fortified with nutrients. The "rice" can be fortified with the needed nutrients the particular population being served is lacking. A slideshow about TB in the Ukraine, explains to visitors why there has been a resurgence of TB in Eastern Europe, and how PATH and its partners set out to help control it throughout the region.

141

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

142

Accurately determining the attenuation along the propagation path leading to a region of interest could significantly improve diagnostic ultrasound tissue characterization since tissue characterization requires exact compensation for the frequency-dependent attenuation along the propagation path. In a previous study (JASA, 124:1367, 2008), it was shown that the total attenuation can be determined by using the backscattered echoes from multiple sources. The preliminary computer simulation results, had an average error between -0.3 to +0.2 dB/MHz for the cases tested with a trend towards increasing error with increasing correlation length (i.e., characteristic size of the tissue microstructure of the scattering medium) and attenuation along the propagation path. Therefore, the goal of this study was to improve the accuracy of previously derived algorithm and reduce the dependence of the algorithm on correlation length and attenuation. In this study, the previous derivations were redone and the assumptions made by the algorithm regarding the scattering properties of the medium and the shape of the backscattered power spectrum were relaxed. The revised algorithm was then verified using computer simulations of five sources (6, 8, 10, 12, and 14 MHz, 50% bandwidth) exposing a homogeneous tissue region. The simulated tissue had microstructure following a Gaussian spatial correlation function (i.e., exp (?0.827(kaeff)2) where k is the wavenumber) with effective radii, aeff, of 5 to 55 ?m (one size per simulated case) placed at a density of 250/mm3 (?5 scatterers/resolution cell for 14 MHz transducer). The attenuation of the tissue was also varied from 0.1 to 0.9 dB/cm-MHz. The computer simulations demonstrated that the modifications significantly improved the accuracy of the algorithm resulting in average errors between -0.04 and 0.1 dB/MHz which is three times better than the error performance of the original algorithm. PMID:19913861

Bigelow, Timothy A.

2009-01-01

143

Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems

This paper considers the problem of designing fast, approx- imate, combinatorial algorithms for multicommodity flows and other fractional packing problems. We provide a dif- ferent approach to these problems which yields faster and much simpler algorithms. Our approach also allows us to substitute shortest path computations for min-cost flow computations in computing maximum concurrent flow and min-cost multicommodity flow; this

Naveen Garg; Jochen Könemann

1998-01-01

144

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

145

NASA Astrophysics Data System (ADS)

In this Letter a new approach for solving optimal path planning problems for a single rigid and free moving object in a two and three dimensional space in the presence of stationary or moving obstacles is presented. In this approach the path planning problems have some incompatible objectives such as the length of path that must be minimized, the distance between the path and obstacles that must be maximized and etc., then a multi-objective dynamic optimization problem (MODOP) is achieved. Considering the imprecise nature of decision maker's (DM) judgment, these multiple objectives are viewed as fuzzy variables. By determining intervals for the values of these fuzzy variables, flexible monotonic decreasing or increasing membership functions are determined as the degrees of satisfaction of these fuzzy variables on their intervals. Then, the optimal path planning policy is searched by maximizing the aggregated fuzzy decision values, resulting in a fuzzy multi-objective dynamic optimization problem (FMODOP). Using a suitable t-norm, the FMODOP is converted into a non-linear dynamic optimization problem (NLDOP). By using parametrization method and some calculations, the NLDOP is converted into the sequence of conventional non-linear programming problems (NLPP). It is proved that the solution of this sequence of the NLPPs tends to a Pareto optimal solution which, among other Pareto optimal solutions, has the best satisfaction of DM for the MODOP. Finally, the above procedure as a novel algorithm integrating parametrization method and fuzzy aggregation to solve the MODOP is proposed. Efficiency of our approach is confirmed by some numerical examples.

Zamirian, M.; Kamyad, A. V.; Farahi, M. H.

2009-09-01

146

Restoration by Path Concatenation: Fast Recovery of MPLS Paths

Restoration by Path Concatenation: Fast Recovery of MPLS Paths Yehuda Afek Anat Bremler-Barr Haim,natali,haimk}@math.tau.ac.il, {edith,mischu}@research.att.com Abstract A new general theory about restoration of network paths is first introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we

Kaplan, Haim

147

Restoration by Path Concatenation: Fast Recovery of MPLS Paths

Restoration by Path Concatenation: Fast Recovery of MPLS Paths Yehuda Afek Anat Bremler,natali,haimkg@math.tau.ac.il, fedith,mischug@research.att.com Abstract A new general theory about restoration of network paths is first introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we

Bremler-Barr, Anat

148

Trajectory Generation and Path Planning for Autonomous Aerobots

NASA Technical Reports Server (NTRS)

This paper presents global path planning algorithms for the Titan aerobot based on user defined waypoints in 2D and 3D space. The algorithms were implemented using information obtained through a planner user interface. The trajectory planning algorithms were designed to accurately represent the aerobot's characteristics, such as minimum turning radius. Additionally, trajectory planning techniques were implemented to allow for surveying of a planar area based solely on camera fields of view, airship altitude, and the location of the planar area's perimeter. The developed paths allow for planar navigation and three-dimensional path planning. These calculated trajectories are optimized to produce the shortest possible path while still remaining within realistic bounds of airship dynamics.

Sharma, Shivanjli; Kulczycki, Eric A.; Elfes, Alberto

2007-01-01

149

Path Search Algorithm for Connections with Pumps in Crude Oil Pipe Networks Jorge L. Rojas of connections in pipe networks for crude oil transportation, using pumps to overcome negative differences SCADA. We tested the algorithms using data from real pipe networks located in Venezuela. Keywords: Crude

Paris-Sud XI, UniversitÃ© de

150

Spreading paths in partially observed social networks

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

151

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

152

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

153

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

154

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

155

Localization algorithm with on-line path loss estimation and node selection.

RSS-based localization is considered a low-complexity algorithm with respect to other range techniques such as TOA or AOA. The accuracy of RSS methods depends on the suitability of the propagation models used for the actual propagation conditions. In indoor environments, in particular, it is very difficult to obtain a good propagation model. For that reason, we present a cooperative localization algorithm that dynamically estimates the path loss exponent by using RSS measurements. Since the energy consumption is a key point in sensor networks, we propose a node selection mechanism to limit the number of neighbours of a given node that are used for positioning purposes. Moreover, the selection mechanism is also useful to discard bad links that could negatively affect the performance accuracy. As a result, we derive a practical solution tailored to the strict requirements of sensor networks in terms of complexity, size and cost. We present results based on both computer simulations and real experiments with the Crossbow MICA2 motes showing that the proposed scheme offers a good trade-off in terms of position accuracy and energy efficiency. PMID:22163992

Bel, Albert; Vicario, José López; Seco-Granados, Gonzalo

2011-01-01

156

Localization Algorithm with On-line Path Loss Estimation and Node Selection

RSS-based localization is considered a low-complexity algorithm with respect to other range techniques such as TOA or AOA. The accuracy of RSS methods depends on the suitability of the propagation models used for the actual propagation conditions. In indoor environments, in particular, it is very difficult to obtain a good propagation model. For that reason, we present a cooperative localization algorithm that dynamically estimates the path loss exponent by using RSS measurements. Since the energy consumption is a key point in sensor networks, we propose a node selection mechanism to limit the number of neighbours of a given node that are used for positioning purposes. Moreover, the selection mechanism is also useful to discard bad links that could negatively affect the performance accuracy. As a result, we derive a practical solution tailored to the strict requirements of sensor networks in terms of complexity, size and cost. We present results based on both computer simulations and real experiments with the Crossbow MICA2 motes showing that the proposed scheme offers a good trade-off in terms of position accuracy and energy efficiency. PMID:22163992

Bel, Albert; Vicario, José López; Seco-Granados, Gonzalo

2011-01-01

157

constraints [4] and finitely many integral quadratic constraints [5] are derived and studied. Interestingly to solve quadratic optimization problems with infinitely many linear constraints in the case whenA path following algorithm for infinite quadratic programming on a Hilbert space* Andrew E.B. Limf

Moore, John Barratt

158

Cost-based Filtering for Shorter Path Constraints

Many real world problems, e.g. personnel scheduling and transporta- tion planning, can be modeled naturally as Constrained Shortest Path Problems (CSPPs), i.e., as Shortest Path Problems with additional constraints. A well studied problem in this class is the Resource Constrained Shortest Path Problem. Reduction techniques are vital ingredients of solvers for the CSPP, that is frequently NP-hard, depending on the

Meinolf Sellmann; Thorsten Gellermann; Robert Wright

2007-01-01

159

An improved recursive decomposition algorithm for reliability evaluation of lifeline networks

The seismic reliability evaluation of lifeline networks has received considerable attention and been widely studied. In this\\u000a paper, on the basis of an original recursive decomposition algorithm, an improved analytical approach to evaluate the seismic\\u000a reliability of large lifeline systems is presented. The proposed algorithm takes the shortest path from the source to the\\u000a sink of a network as decomposition

Wei Liu; Jie Li

2009-01-01

160

A Linear Algorithm for the Pos\\/Neg-Weighted 1Median Problem on a Cactus

The 1-median problem on a network asks for a vertex minimizing the sum of the weighted shortest path distances from itself\\u000a to all other vertices, each associated with a certain positive weight. We allow fornegative weights as well and devise an exact algorithm for the resulting ‘pos\\/neg-weighted’ problem defined on a cactus. The algorithm\\u000a visits every vertex just once and

Rainer E. Burkard; Jakob Krarup

1998-01-01

161

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

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

162

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

163

Constraint-Based Local Search for Constrained Optimum Paths Problems

NASA Astrophysics Data System (ADS)

Constrained Optimum Path (COP) problems arise in many real-life applications and are ubiquitous in communication networks. They have been traditionally approached by dedicated algorithms, which are often hard to extend with side constraints and to apply widely. This paper proposes a constraint-based local search (CBLS) framework for COP applications, bringing the compositionality, reuse, and extensibility at the core of CBLS and CP systems. The modeling contribution is the ability to express compositional models for various COP applications at a high level of abstraction, while cleanly separating the model and the search procedure. The main technical contribution is a connected neighborhood based on rooted spanning trees to find high-quality solutions to COP problems. The framework, implemented in COMET, is applied to Resource Constrained Shortest Path (RCSP) problems (with and without side constraints) and to the edge-disjoint paths problem (EDP). Computational results show the potential significance of the approach.

Pham, Quang Dung; Deville, Yves; van Hentenryck, Pascal

164

Information Spread of Emergency Events: Path Searching on Social Networks

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

165

A novel multipurpose tree and path matching algorithm with application to airway trees

NASA Astrophysics Data System (ADS)

Tree matching methods have numerous applications in medical imaging, including registration, anatomical labeling, segmentation, and navigation of structures such as vessels and airway trees. Typical methods for tree matching rely on conventional graph matching techniques and therefore suffer potential limitations such as sensitivity to the accuracy of the extracted tree structures, as well as dependence on the initial alignment. We present a novel path-based tree matching framework independent of graph matching. It is based on a point-by-point feature comparison of complete paths rather than branch points, and consequently is relatively unaffected by spurious airways and/or missing branches. A matching matrix is used to enforce one-to-one matching. Moreover our method can reliably match irregular tree structures, resulting from imperfect segmentation and centerline extraction. Also reflecting the nature of these features, our method does not require a precise alignment or registration of tree structures. To test our method we used two thoracic CT scans from each of ten patients, with a median inter-scan interval of 3 months (range 0.5 to 10 months). The bronchial tree structure was automatically extracted from each scan and a ground truth of matching paths was established between each pair of tree structures. Overall 87% of 702 airway paths (average 35.1 per patient matched both ways) were correctly matched using this technique. Based on this success we also present preliminary results of airway-to-artery matching using our proposed methodology.

Kaftan, Jens N.; Kiraly, Atilla P.; Naidich, David P.; Novak, Carol L.

2006-03-01

166

-disjoint paths, hardness of approximation, multicommodity ow, network routing, unsplittable ow, vertex for the directed graph case; we omit de#12;ning their standard restrictions to the undirected case. Multicommodity Flow Problems: In multicommodity problems, we are given a directed graph G = (V; A) and a set T of k

Shepherd, Bruce

167

A Simple Path Non-Existence Algorithm using C-obstacle Query

sampling methods such as probabilistic roadmap planners (PRMs) are relatively simple to implement and work quite well in practice [11]. The strength of PRMs lies in their simplicity and they can be easily applied to general robots with high DOF. However, PRMs have two major issues: path non-existence (i

North Carolina at Chapel Hill, University of

168

Scalable Shortest Paths Browsing on Land Surface Songhua Xing

University of Southern California Los Angeles, CA 90089-0781 sxing@usc.edu Cyrus Shahabi Computer Science Department University of Southern California Los Angeles, CA 90089-0781 shahabi@usc.edu ABSTRACT The growing.g., earthquakes in mountainous regions), military operations, environment protection, tourism applications

Shahabi, Cyrus

169

Fast shortest path distance estimation in large networks

@cs.bu.edu Francesco Bonchi Yahoo! Research, Barcelona bonchi@yahoo-inc.com Carlos Castillo Yahoo! Research, Barcelona chato@yahoo-inc.com Aristides Gionis Yahoo! Research, Barcelona gionis@yahoo-inc.com ABSTRACT We study while the first author was vis- iting Yahoo! Research Barcelona, under the Yahoo! intern- ship program

170

Fast shortest path distance estimation in large networks

@cs.bu.edu Francesco Bonchi Yahoo! Research, Barcelona bonchi@yahooÂinc.com Carlos Castillo Yahoo! Research, Barcelona chato@yahooÂinc.com Aristides Gionis Yahoo! Research, Barcelona gionis@yahooÂinc.com ABSTRACT We study was done while the first author was visÂ iting Yahoo! Research Barcelona, under the Yahoo! internÂ ship

171

OBSTACLE-AVOIDING SIMILARITY METRICS AND SHORTEST PATH PROBLEMS

Foundation grant NSF CAREER CCF-0643597 and the 2009 University of Texas at San Antonio Presidential with guidelines which permit the inclusion as part of the Doctoral Dissertation the text of an original paper

Texas at San Antonio, University of

172

Integer programming formulations for the elementary shortest path ...

In order to compare MCF and GCS, we need to project out also the q-variables of the MCF formulation. ..... imum throughput network routing subject to fair flow allocation,. ISCO, Lecture Notes in Computer Science, vol. 8596, Springer, 2014,.

2014-09-26

173

Shortest Path Computation with No Information Leakage Kyriakos Mouratidis

systems and the diffusion of smart-phones has led to an expanding market of location-based services (LBSs example of a leading mobile device company, which had been tracking the locations of its clients without S that includes s and a number of fake source locations. Similarly, it sends to the LBS a set of candidate

Yiu, Man Lung

174

Methodology for Augmenting Existing Paths with Additional Parallel Transects

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

175

Cycles and Paths in Semicomplete Multipartite Digraphs, Theorems and Algorithms: A Survey

A digraph obtained by replacing each edge of a complete m-partite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a semicom- plete m-partite digraph. We describe results (theorems and algorithms) on directed walks in semicomplete m- partite digraphs including some recent results concerning tournaments.

G. Gutin

2003-01-01

176

Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems

, multicommodity flow, randomized algorithms, rounding, linear programming. 1 Introduction Due to the emergence; the central theme of this work is the underlying multi-commodity flow relaxation. Applications.g., Peleg and Upfal (1989), Broder, Frieze and Upfal (1994), Broder, Frieze and Upfal (1999)), and multi-commodity

Srinivasan, Aravind

177

Data Generation for Path Testing

We present two stochastic search algorithms for generating test cases that execute specified paths in a program. The two algorithms are: a simulated annealing algorithm (SA), and a genetic algorithm (GA). These algorithms are based on an optimization formulation of the path testing problem which include both integer- and real-value test cases. We empirically compare the SA and GA algorithms

Nashat Mansour; Miran Salame

2004-01-01

178

Multi-Path Relay Selection Algorithm Based on the Broadcast TV

NASA Astrophysics Data System (ADS)

This paper presents a relay selection method for Broadcast TV services. This method get through the node's time-delay and power information, obtain the value of the system interrupt as to be a decision threshold, then chose the relay node. At the same time this paper proposes an optimal relay selection strategy which can minimize the system interrupt probability combination with power distribution--Multi-Path Relay Routing Protocol. This protocol can dynamically change the appropriate route according to the shifty network. Simulation results show that the protocol can extend the coverage area, reducing time-delay and increase system throughput, improve system spectral efficiency, and enhance the Qos of the Broadcast TV service.

Zhang, Chaoyi; Luan, Linlin; Wu, Muqing

179

Dijkstra's Algorithm On-Line: An Empirical Case Study from Public Railroad Transport

Traffic information systems are among the most prominent real-world applications of Dijkstra’s algorithm for shortest paths.\\u000a We consider the scenario of a central information server in the realm of public railroad transport on wide-area networks.\\u000a Such a system has to process a large number of on-line queries in real time. In practice, this problem is usually solved by\\u000a heuristical variations

Frank Schulz; Dorothea Wagner; Karsten Weihe

1999-01-01

180

Dijkstra's Algorithm On-Line: An Empirical Case Study from Public Railroad Transport

Traffic information systems are among the most prominent real-world applications of Dijkstra's algorithm for shortest paths. We consider the scenario of a central information server in the realm of public railroad transport on wide-area networks. Such a system has to process a large number of on-line queries for optimal travel connections in real time. In practice, this problem is usually

Frank Schulz; Dorothea Wagner; Karsten Weihe

2000-01-01

181

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

182

Path optimization using sub-Riemannian manifolds with applications to astrodynamics

Differential geometry provides mechanisms for finding shortest paths in metric spaces. This work describes a procedure for creating a metric space from a path optimization problem description so that the formalism of ...

Whiting, James K. (James Kalani), 1980-

2011-01-01

183

Thick Non-Crossing Paths and Minimum-Cost Flows in Polygonal Domains

Math and Statistics Stony Brook University jsbm@ams.stonybrook.edu Valentin Polishchuk Helsinki Institute for Information Technology valentin@compgeom.com ABSTRACT We study the problem of finding shortest of points (s, t), find a shortest s-t path avoiding the obstacles. The non-crossing paths problem

Mitchell, Joseph S.B.

184

Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems

Abstract This paper considers the problem of designing fast, approximate, combinatorial algorithms for multicommodity flows and other fractional packing problems. We provide a different approach,to these problems,which yields faster and much,simpler algorithms. Our approach,also allows us to substitute shortest path computations,for min-cost flow computations,in computing,maximum,concurrent flow and min-cost multicommodity,flow; this yields much,faster algorithms when the number,of commodities,is large.

N. Garg

1997-01-01

185

The longest shortest piercing. B. Kawohl & V. Kurta.

The longest shortest piercing. B. Kawohl & V. Kurta. December 8, 2010 Abstract: We generalize shortest piercing. Mathematics Subject Classification (2010). 52A40 Keywords. starshaped rearrangement, geometric inequality, bisector, piercing 1 Motivation and Result Let be a measurable (possibly unbounded

Kawohl, Bernd

186

Efficient Algorithms and Data Structures for Massive Data Sets

NASA Astrophysics Data System (ADS)

For many algorithmic problems, traditional algorithms that optimise on the number of instructions executed prove expensive on I/Os. Novel and very different design techniques, when applied to these problems, can produce algorithms that are I/O efficient. This thesis adds to the growing chorus of such results. The computational models we use are the external memory model and the W-Stream model. On the external memory model, we obtain the following results. (1) An I/O efficient algorithm for computing minimum spanning trees of graphs that improves on the performance of the best known algorithm. (2) The first external memory version of soft heap, an approximate meldable priority queue. (3) Hard heap, the first meldable external memory priority queue that matches the amortised I/O performance of the known external memory priority queues, while allowing a meld operation at the same amortised cost. (4) I/O efficient exact, approximate and randomised algorithms for the minimum cut problem, which has not been explored before on the external memory model. (5) Some lower and upper bounds on I/Os for interval graphs. On the W-Stream model, we obtain the following results. (1) Algorithms for various tree problems and list ranking that match the performance of the best known algorithms and are easier to implement than them. (2) Pass efficient algorithms for sorting, and the maximal independent set problems, that improve on the best known algorithms. (3) Pass efficient algorithms for the graphs problems of finding vertex-colouring, approximate single source shortest paths, maximal matching, and approximate weighted vertex cover. (4) Lower bounds on passes for list ranking and maximal matching. We propose two variants of the W-Stream model, and design algorithms for the maximal independent set, vertex-colouring, and planar graph single source shortest paths problems on those models.

Alka

2010-05-01

187

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

188

The Trade-offs of Multicast Trees and Algorithms

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

189

Discrete Approximations to Continuous Shortest-Path: Application to Minimum-Risk Path Planning for

in complex 3D environments Â· probability of radar acquisition depends on UAVs attitude Â· "safe-space" is very probability of UAV being acquired by radar on an elementary time interval dt: acquisition density function engagement zone engagement zone changes significantly with the attitude of the UAV with respect to the radar

Hespanha, JoÃ£o Pedro

190

Dynamic routing algorithm for large file transport in optical network

NASA Astrophysics Data System (ADS)

Many distributed computing applications need transfer large files between distributed locations as fast as possible. A dynamic routing algorithm for optical network is designed to modify existing transfers and spare network resources for new request to satisfy both old and new transfers' requirements. In data intensive application on circuit-switch optical network, light-path resources are scarce and there should be concurrent file transfers competing for the same fibers. In static routing optical network, if new coming file transfer cannot acquire light-path with enough bandwidth, it could only wait for the releasing of current used resources. Due to the waiting, the delay time will be large. So we use our dynamic routing algorithm to schedule and modify existing light-paths, to spare a light-path with enough bandwidth for new coming file. Our optimized target is to make every file finish transferring in less time, so we propose two objectives defined in the paper: one is to make maximal delay time of all tasks less and the other is to make average delay time less. The algorithm proposed has two mainly steps: 1) Routing process; 2) Dynamic routing process. In routing step, when task of file arrives we firstly get k random paths, then use Least Congestion Algorithm (LCA) (or Shortest Path Algorithm (SPA)) to get the primary path P1 of maximal residual bandwidth (RB) from k paths and the alternate path P2 of the second maximal RB. If the bandwidth of P1 is enough for this task, transfer the file in P1 path. If not, we go to the dynamic routing process. In the second process, get all the links of P1 then we change the existing light paths of tasks in the P1 path one by one to their alternative paths until we can get enough bandwidth of P1. In the dynamic routing process, we design two different queuing strategies. The first strategy is First Arrive First Modified (FAFM) strategy, namely we schedule the first arrival task firstly. The other is Larger Bandwidth First Modified (LBFM) and the file with larger bandwidth is scheduled firstly. By comparison of simulation results, we can prove that our two kinds of dynamic routing algorithms can get better results for both decreasing maximal delay time and average delay time than LCA and SPA routing algorithms. In the two queuing strategies, LBFM can get better results than FAFM strategy. The receivers in the destinations can get better results by using our dynamic routing algorithm.

Zhang, Pengshan; Guo, Wei; Jin, Yaohui; Sun, Weiqiang; Hu, Weisheng

2007-11-01

191

Neural networks and genetic algorithms are useful for clustering analysis in data mining. Artificial neural networks (ANNs) and genetic algorithms (GAs) have been applied in many areas with very promising results. Thus, this study uses adaptive resonance theory 2 (ART2) neural network to determine an initial solution, and then applies genetic K-means algorithm (GKA) to find the final solution for

R. J. Kuo; J. L. Liao; C. Tu

2005-01-01

192

Novel algorithms for wavelength converters placement in wavelength-routed network

NASA Astrophysics Data System (ADS)

In this paper, the placement problem of wavelength converters in DWDM (Dense Wavelength Division Multiplexing) networks with arbitrary topologies is investigated. We could settle the problem easily by considering the two sub-problems of routing selecting and converter placement simultaneously. A reasonable path algorithm in which load balance and shortest path are considering together was proposed. Based on this model, we presented three simple algorithms A,B and C for wavelength converter placement. Simulation results on the basic characteristic of converter placement of EON and NSFNET are presented. With the three algorithms, the cost (including routing selecting and placement of WC) of optimizing network has been greatly reduced but the blocking performance has not been reduced.

Xu, Hao; Zhang, Xinliang; Liu, Deming; Huang, Dexiu

2005-02-01

193

Optimal paths for a car that goes both forwards and backwards

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

194

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

195

This paper deals with a multi-agent path plan- ning problem for tracking humans in order to obtain detail information such like human behavior and characteristics. To achieve this, paths of agents are planned based on similarity between the predicted positions of humans and agents' field of views, and the path length in the path planning is determined according to the

Noriko Takemura; Yutaka Nakamura; Hiroshi Ishiguro

2011-01-01

196

The intrinsic reaction coordinate (IRC) curve is used widely as a representation of the Reaction Path and can be parameterized taking the potential energy as a reaction coordinate (Aguilar-Mogas et al., J Chem Phys 2008, 128, 104102). Taking this parameterization and its variational nature, an algorithm is proposed that permits to locate this type of curve joining two points from an arbitrary curve that joints the same initial and final points. The initial and final points are minima of the potential energy surface associated with the geometry of reactants and products of the reaction whose mechanism is under study. The arbitrary curves are moved toward the IRC curve by a Runge-Kutta-Fehlberg technique. This technique integrates a set of differential equations resulting from the minimization until value zero of the line integral over the Weierstrass E-function. The Weierstrass E-function is related with the second variation in the theory of calculus of variations. The algorithm has been proved in real chemical systems. PMID:20652993

Aguilar-Mogas, Antoni; Giménez, Xavier; Bofill, Josep Maria

2010-10-01

197

A Decision Processing Algorithm for CDC Location Under Minimum Cost SCM Network

NASA Astrophysics Data System (ADS)

Location of CDC in the matter of network on Supply Chain is becoming on the high concern these days. Present status of methods on CDC has been mainly based on the calculation manually by the spread sheet to achieve the goal of minimum logistics cost. This study is focused on the development of new processing algorithm to overcome the limit of present methods, and examination of the propriety of this algorithm by case study. The algorithm suggested by this study is based on the principle of optimization on the directive GRAPH of SCM model and suggest the algorithm utilizing the traditionally introduced MST, shortest paths finding methods, etc. By the aftermath of this study, it helps to assess suitability of the present on-going SCM network and could be the criterion on the decision-making process for the optimal SCM network building-up for the demand prospect in the future.

Park, N. K.; Kim, J. Y.; Choi, W. Y.; Tian, Z. M.; Kim, D. J.

198

Efficient mapping algorithms for survivable GMPLS networks

NASA Astrophysics Data System (ADS)

With the advent of intelligent IP over optical networks, like GMPLS, connections can be protected against failures effectively; however, to capitalize the advantages, novel sophisticated methods are needed. This paper addresses the task of finding efficient mapping in a survivable multilayer network in order to ensure high availability for connections. Known methods (like running a shortest path algorithm) do not consider finding physically disjoint paths in the upper layer and thus cause failure propagation. Besides formulating the problem, we propose a randomized heuristic method to solve it. The quality of the solution is evaluated (1) by the number of node-pairs for which physically-disjoint path-pair can be found in the upper layer, or (2) by the number of spans used by both working and protection paths (i.e., failure propagation effect). It is shown with numerous simulations that our proposed method finds solution for significantly more node pairs (86% instead of 45% in the 35-node network) than traditional methods. Furthermore, it yields connection availabilities near to the optimum.

Laborczi, Peter

2003-10-01

199

An Almost Linear Time Algorithm for Field Splitting in Radiation Therapy?

In this paper, we study an interesting geometric partition problem, called optimal field splitting, which arises in Intensity-Modulated Radiation Therapy (IMRT). In current clinical practice, a multi-leaf collimator (MLC) with a maximum leaf spread constraint is used to deliver the prescribed intensity maps (IMs). However, the maximum leaf spread of an MLC may require to split a large intensity map into several overlapping sub-IMs with each being delivered separately. We develop a close-to-linear time algorithm for solving the field splitting problem while minimizing the total complexity of the resulting sub-IMs, thus improving the treatment delivery efficiency. Meanwhile, our algorithm strives to minimize the maximum beam-on time of those sub-IMs. Our basic idea is to formulate the field splitting problem as computing a shortest path in a directed acyclic graph, which expresses a special “layered” structure. The edge weights of the graph satisfy the Monge property, which enables us to solve this shortest path problem by examining only a small portion of the graph, yielding a close-to-linear time algorithm. To minimize the maximum beam-on time of the resulting sub-IMs, we consider an interesting min-max slope path problem in a monotone polygon which is solvable in linear time. The min-max slope path problem may be of interest in its own right. Experimental results based on real medical data and computer generated IMs showed that our new algorithm runs fast and produces high quality field splitting results. PMID:24999294

Wu, Xiaodong; Dou, Xin; Bayouth, John E.; Buatti, John M.

2014-01-01

200

An Almost Linear Time Algorithm for Field Splitting in Radiation Therapy.

In this paper, we study an interesting geometric partition problem, called optimal field splitting, which arises in Intensity-Modulated Radiation Therapy (IMRT). In current clinical practice, a multi-leaf collimator (MLC) with a maximum leaf spread constraint is used to deliver the prescribed intensity maps (IMs). However, the maximum leaf spread of an MLC may require to split a large intensity map into several overlapping sub-IMs with each being delivered separately. We develop a close-to-linear time algorithm for solving the field splitting problem while minimizing the total complexity of the resulting sub-IMs, thus improving the treatment delivery efficiency. Meanwhile, our algorithm strives to minimize the maximum beam-on time of those sub-IMs. Our basic idea is to formulate the field splitting problem as computing a shortest path in a directed acyclic graph, which expresses a special "layered" structure. The edge weights of the graph satisfy the Monge property, which enables us to solve this shortest path problem by examining only a small portion of the graph, yielding a close-to-linear time algorithm. To minimize the maximum beam-on time of the resulting sub-IMs, we consider an interesting min-max slope path problem in a monotone polygon which is solvable in linear time. The min-max slope path problem may be of interest in its own right. Experimental results based on real medical data and computer generated IMs showed that our new algorithm runs fast and produces high quality field splitting results. PMID:24999294

Wu, Xiaodong; Dou, Xin; Bayouth, John E; Buatti, John M

2013-08-01

201

Integrated Flight Path Planning System and Flight Control System for Unmanned Helicopters

This paper focuses on the design of an integrated navigation and guidance system for unmanned helicopters. The integrated navigation system comprises two systems: the Flight Path Planning System (FPPS) and the Flight Control System (FCS). The FPPS finds the shortest flight path by the A-Star (A*) algorithm in an adaptive manner for different flight conditions, and the FPPS can add a forbidden zone to stop the unmanned helicopter from crossing over into dangerous areas. In this paper, the FPPS computation time is reduced by the multi-resolution scheme, and the flight path quality is improved by the path smoothing methods. Meanwhile, the FCS includes the fuzzy inference systems (FISs) based on the fuzzy logic. By using expert knowledge and experience to train the FIS, the controller can operate the unmanned helicopter without dynamic models. The integrated system of the FPPS and the FCS is aimed at providing navigation and guidance to the mission destination and it is implemented by coupling the flight simulation software, X-Plane, and the computing software, MATLAB. Simulations are performed and shown in real time three-dimensional animations. Finally, the integrated system is demonstrated to work successfully in controlling the unmanned helicopter to operate in various terrains of a digital elevation model (DEM). PMID:22164029

Jan, Shau Shiun; Lin, Yu Hsiang

2011-01-01

202

A Flexible Reservation Algorithm for Advance Network Provisioning

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

203

Computing the Length of the Shortest Telomere in the Nucleus

NASA Astrophysics Data System (ADS)

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.

Dao Duc, K.; Holcman, D.

2013-11-01

204

The Trade-offs of Multicast Trees and Algorithms

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

205

An efficient QoS-aware routing algorithm for LEO polar constellations

NASA Astrophysics Data System (ADS)

In this work, a Quality of Service (QoS)-aware routing (QAR) algorithm is developed for Low-Earth Orbit (LEO) polar constellations. LEO polar orbits are the only type of satellite constellations where inter-plane inter-satellite links (ISLs) are implemented in real world. The QAR algorithm exploits features of the topology of the LEO satellite constellation, which makes it more efficient than general shortest path routing algorithms such as Dijkstra's or extended Bellman-Ford algorithms. Traffic density, priority, and error QoS requirements on communication delays can be easily incorporated into the QAR algorithm through satellite distances. The QAR algorithm also supports efficient load balancing in the satellite network by utilizing the multiple paths from the source satellite to the destination satellite, and effectively lowers the rate of network congestion. The QAR algorithm supports a novel robust routing scheme in LEO polar constellation, which is able to significantly reduce the impact of inter-satellite link (ISL) congestions on QoS in terms of communication delay and jitter.

Tian, Xin; Pham, Khanh; Blasch, Erik; Tian, Zhi; Shen, Dan; Chen, Genshe

2013-05-01

206

Advisory Algorithm for Scheduling Open Sectors, Operating Positions, and Workstations

NASA Technical Reports Server (NTRS)

Air traffic controller supervisors configure available sector, operating position, and work-station resources to safely and efficiently control air traffic in a region of airspace. In this paper, an algorithm for assisting supervisors with this task is described and demonstrated on two sample problem instances. The algorithm produces configuration schedule advisories that minimize a cost. The cost is a weighted sum of two competing costs: one penalizing mismatches between configurations and predicted air traffic demand and another penalizing the effort associated with changing configurations. The problem considered by the algorithm is a shortest path problem that is solved with a dynamic programming value iteration algorithm. The cost function contains numerous parameters. Default values for most of these are suggested based on descriptions of air traffic control procedures and subject-matter expert feedback. The parameter determining the relative importance of the two competing costs is tuned by comparing historical configurations with corresponding algorithm advisories. Two sample problem instances for which appropriate configuration advisories are obvious were designed to illustrate characteristics of the algorithm. Results demonstrate how the algorithm suggests advisories that appropriately utilize changes in airspace configurations and changes in the number of operating positions allocated to each open sector. The results also demonstrate how the advisories suggest appropriate times for configuration changes.

Bloem, Michael; Drew, Michael; Lai, Chok Fung; Bilimoria, Karl D.

2012-01-01

207

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.

208

Trees, paths and avalanches on random networks

NASA Astrophysics Data System (ADS)

The investigation of equilibrium and non-equilibrium processes in disordered systems and particularly the relation between them is a complex problem that deserves attention. We concentrate on analyzing several relations of this type and appropriate numerical solutions. Invasion percolation (IP) model was motivated by the problem of fluid displacement in disordered media but in principle it could be applied to any invasion process which evolves along the minimum resistance path. Finding the invasion paths is a global optimization problem where the front advances by occupying the least resistant bond. Once the invasion is finished, the union of all the invasion paths on the lattice forms a minimum energy spanning tree (MST). We show that the geometry of a MST on random graphs is universal. Due to this geometric universality, we are able to characterize the energy of this optimal tree for any type of disorder using a scaling distribution found using uniform disorder. Therefore we expect the hopping transport in random media to have universal behavior. Kinetic interfaces is an important branch of statistical mechanics, fueled by application such as fluid-fluid displacement, imbibition in porous media, flame fronts, tumors, etc. These processes can be unified via Kardar-Parisi-Zhang (KPZ) equation, which is mapped exactly to an equilibrium problem (DPRM). We are able to characterize both using Dijkstra's algorithm, which is known to generate shortest path tree in a random network. We found that while obtaining the polymers the algorithm develops a KPZ type interface. We have extracted the interface exponents for both 2d square lattice and 3 d cubic lattice, being in agreement with previously recorded results for KPZ. The IP and KPZ classes are known to be very different: while the first one generates a distinct self-similar (fractal) interface, the second one has a self-similar invasion front. Though they are different we are able to construct a generalized algorithm that interpolates between these two universality classes. We discuss the relationship with the IP, the directed polymer in a random media; and the implications for the broader issue of universality in disordered systems. Random Field Ising Model (RFIM) is one of the most important models of phase transitions in disordered systems. We present exact results for the critical behavior of the RFIM on complete graphs and trees, both at equilibrium and away from equilibrium, i.e., models for hysteresis and Barkhausen noise. We show that for stretched exponential and powerlaw distributions of random fields the behavior on complete graphs is non-universal, while the behavior on Cayley trees is universal even in the limit of large coordination. Until recently, the evolution of WWW, Internet, etc., was thought to be highly complex. The model proposed by Barabasi and Albert shows that such networks can be modeled with the help of "preferential attachment", i.e. a highly connected vertex has a higher chance to get further links compared with a weakly connected vertex. We find that the random network constructed from a self-organized critical mechanism, (IP), falls in the same class without imposing any "preferential" growth rule. The network obtained has a connectivity exponent gamma ? 2.45, close to the WWW outgoing-links exponent.

Dobrin, Radu

209

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

210

Do People Use the Shortest Path? Empirical Test of Wardrop's First

maximization #12;Motivation: I-35W Bridge Collapse MnPASS Program #12;Data Collection #12;Traffic-35W Mississippi River Bridge Collapse, Transportation Research Part A: Policy and Practice, 44DOT, Metropolitan Consortium BRIDGE: Behavioral Response to the I-35W Disruption: Gauging Equilibration (National

Levinson, David M.

211

A Dynamic Programming Approach to Identifying the Shortest Path in Virtual Learning Environments

ERIC Educational Resources Information Center

E-learning has been widely adopted as a promising solution by many organizations to offer learning-on-demand opportunities to individual employees (learners) in order to reduce training time and cost. While successful information systems models have received much attention among researchers, little research has been conducted to assess the success…

Fazlollahtabar, Hamed

2008-01-01

212

mobility concepts has come in sharp focus. Applying new traffic concepts to the real world can be veryStreetMap database yielding simulation re- sults based on real-world transportation data. Â· dynamic creation to be acquired. Therefore, multiagent-based simulation (MABS) can be used to procure well-founded assess- ments

213

Approximating shortest paths in arrangements of lines Prosenjit Bose William Evans David Kirkpatrick

1: (a) An arrangement of lines with cell Cell(st) in bold, (b) cross lines with critical lines arrangement: the arrangement A without the cross lines and including all lines that contain s or t. A cell is an endpoint of a cell edge; it is an upper cell vertex if it is above the line st and is a lower cell vertex

Bose, Prosenjit

214

Approximating shortest paths in arrangements of lines Prosenjit Bose William Evans David Kirkpatrick

) An arrangement of lines, (b) cross lines with critical lines ` + and ` \\Gamma , and (c) cell Cell(st). Definition vertex is an endpoint of a cell edge; it is an upper cell vertex if it is above the line st and is a lower cell vertex if it is below the line st; vertices s and t are both upper and lower cell vertices

Evans, Will

215

NASA Technical Reports Server (NTRS)

The At-Least version of the Generalized Minimum Spanning Tree Problem (L-GMST) is a problem in which the optimal solution connects all defined clusters of nodes in a given network at a minimum cost. The L-GMST is NPHard; therefore, metaheuristic algorithms have been used to find reasonable solutions to the problem as opposed to computationally feasible exact algorithms, which many believe do not exist for such a problem. One such metaheuristic uses a swarm-intelligent Ant Colony System (ACS) algorithm, in which agents converge on a solution through the weighing of local heuristics, such as the shortest available path and the number of agents that recently used a given path. However, in a network using a solution derived from the ACS algorithm, some nodes may move around to different clusters and cause small changes in the network makeup. Rerunning the algorithm from the start would be somewhat inefficient due to the significance of the changes, so a genetic algorithm based on the top few solutions found in the ACS algorithm is proposed to quickly and efficiently adapt the network to these small changes.

Janich, Karl W.

2005-01-01

216

Longest Path Problems on Ptolemaic Graphs

NASA Astrophysics Data System (ADS)

Longest path problem is a problem for finding a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, there are few known graph classes such that the longest path problem can be solved efficiently. Polynomial time algorithms for finding a longest cycle and a longest path in a Ptolemaic graph are proposed. Ptolemaic graphs are the graphs that satisfy the Ptolemy inequality, and they are the intersection of chordal graphs and distance-hereditary graphs. The algorithms use the dynamic programming technique on a laminar structure of cliques, which is a recent characterization of Ptolemaic graphs.

Takahara, Yoshihiro; Teramoto, Sachio; Uehara, Ryuhei

217

Optimization of Operation Sequence in CNC Machine Tools Using Genetic Algorithm

NASA Astrophysics Data System (ADS)

The productivity of machine tools is significantly improved by using microcomputer based CAD/CAM systems for NC program generation. Currently, many commercial CAD/CAM packages that provide automatic NC programming have been developed and applied to various cutting processes. Many cutting processes machined by CNC machine tools. In this paper, we attempt to find an efficient solution approach to determine the best sequence of operations for a set of operations that located in asymmetrical locations and different levels. In order to find the best sequence of operations that achieves the shortest cutting tool travel path (CTTP), genetic algorithm is introduced. After the sequence is optimized, the G-codes that use to code for the travel time is created. CTTP can be formulated as a special case of the traveling salesman problem (TSP). The incorporation of genetic algorithm and TSP can be included in the commercial CAD/CAM packages to optimize the CTTP during automatic generation of NC programs.

Abu Qudeiri, Jaber; Yamamoto, Hidehiko; Ramli, Rizauddin

218

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

219

Efficient Transitive Closure Algorithms

We have developed some efficient algorithms for computing the transitive closure of a directed graph. This paper presents the algorithms for the problem of reachability. The algorithms, however, can be adapted to deal with path computations and a signitkantJy broader class of queries based on onesided recursions. We analyze these algorithms and compare them to algorithms in the literature. The

Yannis E. Ioannidis; Raghu Ramakrishnan

1988-01-01

220

Dispersion of nonlinear group velocity determines shortest envelope solitons

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

221

Unstructured path problems and the making of semirings

The solution of the algebraic path problem, for instance with the algorithm by Floyd and Warshall, is part of the classical repertoire on algorithms. This solution presupposes that path costs are computed in a closed semiring or a similar algebraic structure. The associativity and distributivity laws in such algebraic structures exclude many possible path costs. In the seventies, several authors

T. Lengauer; D. Theune

222

Applications of Path Compression on Balanced Trees

Several fast algorithms are presented for computing functions defined on paths in trees under various assumpuons. The algorithms are based on tree mampulatton methods first used to efficiently represent equivalence relations. The algorithms have O((m + n)a(m + n, n)) running tunes, where m and n are measures of the problem size and a Is a functional reverse of Ackermann's

Robert Endre Tarjan

1979-01-01

223

Automatic test data generation for path testing using GAs

Genetic algorithms (GAs) are inspired by Darwin's the survival of the fittest theory. This paper discusses a genetic algorithm that can automatically generate test cases to test a selected path. This algorithm takes a selected path as a target and executes sequences of operators iteratively for test cases to evolve. The evolved test case will lead the program execution to

Jin-cherng Lin; Pu-lin Yeh

2001-01-01

224

NASA Astrophysics Data System (ADS)

The multidimensional, scalar Helmholtz equation of mathematical physics is addressed. Rather than pursuing traditional approaches for the representation and computation of the fundamental solution, path integral representations, originating in quantum physics, are considered. Constructions focusing on the global, two-way nature of the Helmholtz equation, such as the Feynman/Fradkin, Feynman/Garrod, and Feynman/DeWitt-Morette representations, are reviewed, in addition to the complementary phase space constructions based on the exact, well-posed, one-way reformulation of the Helmholtz equation. Exact, Feynman/Kac, stochastic representations are also briefly addressed. These complementary path integral approaches provide an effective means of highlighting the underlying physics in the solution representation, and, subsequently, exploiting this more transparent structure in natural computational algorithms.

Fishman, Louis

2006-05-01

225

UAV Intelligent Path Planning for Wilderness Search and Rescue Computer Science Department

UAV Intelligent Path Planning for Wilderness Search and Rescue Lanny Lin Computer Science in order to find the missing person in the shortest expected time. When using a UAV to support search of the limited UAV flying time. I. INTRODUCTION The use of mini-UAVs (Unmanned Aerial Vehicles) in Wilderness

Goodrich, Michael A.

226

TIME-OPTIMAL PATHS FOR LATERAL NAVIGATION OF AN AUTONOMOUS UNDERACTUATED AIRSHIP

This paper deals with a characterization of the shortest paths for lateral navigation of an autonomous underactuated airship taking into account its dynamics and actuator limitations. The initial and terminal positions are given. We would like to specify the control forces that steer the unmanned aerial vehicle to the given terminal position requiring the minimal time for lateral navigation. The

Salim Hima; Yasmina Bestaoui

227

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.

Cynthia Ann Radle (McCullough High School REV)

1995-06-30

228

Vanquishing the XCB Question: The Methodological Discovery of the Last Shortest Single Axiom for the

Vanquishing the XCB Question: The Methodological Discovery of the Last Shortest Single Axiom(z y)) z)) a single axiom for the classical equivalential calculus when the rules of inference consist on the other two axioms.) Heretofore, thirteen shortest single axioms for classical equivalence of length

Fitelson, Branden

229

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

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

230

Minimum-Risk Path Finding by an Adaptive Amoebal Network

NASA Astrophysics Data System (ADS)

When two food sources are presented to the slime mold Physarum in the dark, a thick tube for absorbing nutrients is formed that connects the food sources through the shortest route. When the light-avoiding organism is partially illuminated, however, the tube connecting the food sources follows a different route. Defining risk as the experimentally measurable rate of light-avoiding movement, the minimum-risk path is exhibited by the organism, determined by integrating along the path. A model for an adaptive-tube network is presented that is in good agreement with the experimental observations.

Nakagaki, Toshiyuki; Iima, Makoto; Ueda, Tetsuo; Nishiura, Yasumasa; Saigusa, Tetsu; Tero, Atsushi; Kobayashi, Ryo; Showalter, Kenneth

2007-08-01

231

Leaf-sequencing for intensity-modulated arc therapy using graph algorithms

Intensity-modulated arc therapy (IMAT) is a rotational IMRT technique. It uses a set of overlapping or nonoverlapping arcs to create a prescribed dose distribution. Despite its numerous advantages, IMAT has not gained widespread clinical applications. This is mainly due to the lack of an effective IMAT leaf-sequencing algorithm that can convert the optimized intensity patterns for all beam directions into IMAT treatment arcs. To address this problem, we have developed an IMAT leaf-sequencing algorithm and software using graph algorithms in computer science. The input to our leaf-sequencing software includes (1) a set of (continuous) intensity patterns optimized by a treatment planning system at a sequence of equally spaced beam angles (typically 10 deg. apart), (2) a maximum leaf motion constraint, and (3) the number of desired arcs, k. The output is a set of treatment arcs that best approximates the set of optimized intensity patterns at all beam angles with guaranteed smooth delivery without violating the maximum leaf motion constraint. The new algorithm consists of the following key steps. First, the optimized intensity patterns are segmented into intensity profiles that are aligned with individual MLC leaf pairs. Then each intensity profile is segmented into k MLC leaf openings using a k-link shortest path algorithm. The leaf openings for all beam angles are subsequently connected together to form 1D IMAT arcs under the maximum leaf motion constraint using a shortest path algorithm. Finally, the 1D IMAT arcs are combined to form IMAT treatment arcs of MLC apertures. The performance of the implemented leaf-sequencing software has been tested for four treatment sites (prostate, breast, head and neck, and lung). In all cases, our leaf-sequencing algorithm produces efficient and highly conformal IMAT plans that rival their counterpart, the tomotherapy plans, and significantly improve the IMRT plans. Algorithm execution times ranging from a few seconds to 2 min are observed on a laptop computer equipped with a 2.0 GHz Pentium M processor.

Luan Shuang; Wang Chao; Cao Daliang; Chen, Danny Z.; Shepard, David M.; Yu, Cedric X. [Department of Computer Science, University of New Mexico, Albuquerque, New Mexico 87131 (United States); Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, Indiana 46556 (United States); Swedish Cancer Institute, Seattle, Washington 98104 (United States); Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, Indiana 46556 (United States); Swedish Cancer Institute, Seattle, Washington 98104 (United States); Department of Radiation Oncology, University of Maryland School of Medicine, Baltimore, Maryland 21201 (United States)

2008-01-15

232

Analyzing methods for path mining with applications in metabolomics.

Metabolomics is one of the key approaches of systems biology that consists of studying biochemical networks having a set of metabolites, enzymes, reactions and their interactions. As biological networks are very complex in nature, proper techniques and models need to be chosen for their better understanding and interpretation. One of the useful strategies in this regard is using path mining strategies and graph-theoretical approaches that help in building hypothetical models and perform quantitative analysis. Furthermore, they also contribute to analyzing topological parameters in metabolome networks. Path mining techniques can be based on grammars, keys, patterns and indexing. Moreover, they can also be used for modeling metabolome networks, finding structural similarities between metabolites, in-silico metabolic engineering, shortest path estimation and for various graph-based analysis. In this manuscript, we have highlighted some core and applied areas of path-mining for modeling and analysis of metabolic networks. PMID:24230973

Tagore, Somnath; Chowdhury, Nirmalya; De, Rajat K

2014-01-25

233

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

234

Identification of Biochemical Network Modules Based on Shortest Retroactive Distances

Modularity analysis offers a route to better understand the organization of cellular biochemical networks as well as to derive practically useful, simplified models of these complex systems. While there is general agreement regarding the qualitative properties of a biochemical module, there is no clear consensus on the quantitative criteria that may be used to systematically derive these modules. In this work, we investigate cyclical interactions as the defining characteristic of a biochemical module. We utilize a round trip distance metric, termed Shortest Retroactive Distance (ShReD), to characterize the retroactive connectivity between any two reactions in a biochemical network and to group together network components that mutually influence each other. We evaluate the metric on two types of networks that feature feedback interactions: (i) epidermal growth factor receptor (EGFR) signaling and (ii) liver metabolism supporting drug transformation. For both networks, the ShReD partitions found hierarchically arranged modules that confirm biological intuition. In addition, the partitions also revealed modules that are less intuitive. In particular, ShReD-based partition of the metabolic network identified a ‘redox’ module that couples reactions of glucose, pyruvate, lipid and drug metabolism through shared production and consumption of NADPH. Our results suggest that retroactive interactions arising from feedback loops and metabolic cycles significantly contribute to the modularity of biochemical networks. For metabolic networks, cofactors play an important role as allosteric effectors that mediate the retroactive interactions. PMID:22102800

Sridharan, Gautham Vivek; Hassoun, Soha; Lee, Kyongbum

2011-01-01

235

The shortest modulation period Blazhko RR Lyrae star: SS Cnc

Extended BV(RI)c CCD observations of SS Cnc, a short period RRab star are presented. Nearly 1400 data points in each band have been obtained spanning over 79 days during the spring of 2005. The star exhibits light curve modulation, the so called Blazhko effect with small amplitude (B maximum brightness varies 0.1 mag) and with the shortest modulation period (5.309 d) ever observed. In the Fourier spectrum of the V light curve the pulsation frequency components are detected up to the 24th harmonic order, and modulation side lobe frequencies with significantly asymmetric amplitudes are seen up to the 15th and 9th orders for the lower and higher frequency components, respectively. Detailed comparison of the modulation behavior of SS Cnc and RR Gem, the two recently discovered small amplitude, short modulation period Blazhko stars is presented. The modulation frequency (f_m) appears in the Fourier spectrum of both stars with similar amplitude. We also demonstrate that the modulation frequencies have basically different properties as the pulsation and modulation side lobe frequencies have, indicating that the physics behind these frequency components are not the same. The discovery of small amplitude modulations of RRab stars cautions that the large photometric surveys (MACHO, OGLE) may seriously underestimate the number of modulated RR Lyrae stars.

J. Jurcsik; B. Szeidl; Á. Sódor; I. Dékány; Zs. Hurta; K. Posztobányi; K. Vida; M. Váradi; A. Szing

2006-03-20

236

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

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

237

Direct transitive closure algorithms: design and performance evaluation

We present new algorithms for computing transitive closure of large database relations. Unlike iterative algorithms, such as the seminaive and logarithmic algorithms, the termination of our algorithms does not depend on the length of paths in the underlying graph (hence the name direct algorithms). Besides reachability computations, the proposed algorithms can also be used for solving path problems. We discuss

Rakesh Agrawal; Shaul Dar; H. V. Jagadish

1990-01-01

238

Integrated Path Planning and ynamic Steering Control for Autonomous Vehicles

A method is presented for combining two previously proposed algorithms for path-planning and dynamic steering control into a computationally feasible scheme for real-time feedback control of autonomous vehicles in uncertain environments. In the proposed approach to vehicle guidance and control, Path Relaxation is used to compute critical points along a globally desirable path using a priori information and sensor data'.

Bruce P. I. Krogh; Charles E. Thorpe

1986-01-01

239

Integrated path planning and dynamic steering control for autonomous vehicles

A method is presented for combining two previously proposed algorithms for path-planning and dynamic steering control into a computationally feasible scheme for real-time feedback control of autonomous vehicles in uncertain environments. In the proposed approach to vehicle guidance and control, Path Relaxation is used to compute critical points along a globally desirable path using a priori information and sensor data.

B. Krogh; C. Thorpe

1986-01-01

240

NC machine tool path generation from CSG part

NC machine tool path generation from CSG part representations James E Bobrow Recent improvements for machine tool path generation. Current machining algorithms require that any port geometric information of numerically controlled (NC) machine tool paths. In this paper, we discuss the widely used APT 1

Bobrow, James E.

241

Planning Flight Paths of Autonomous Aerobots

NASA Technical Reports Server (NTRS)

Algorithms for planning flight paths of autonomous aerobots (robotic blimps) to be deployed in scientific exploration of remote planets are undergoing development. These algorithms are also adaptable to terrestrial applications involving robotic submarines as well as aerobots and other autonomous aircraft used to acquire scientific data or to perform surveying or monitoring functions.

Kulczycki, Eric; Elfes, Alberto; Sharma, Shivanjli

2009-01-01

242

Evolutionary path planner for UAVs in realistic environments

This paper presents a path planner for Unmanned Air Vehicles (UAVs) based on Evolutionary Algorithms (EA) that can be used in realistic risky scenarios. The path returned by the algorithm fulfills and optimizes multiple criteria which (1) are calculated based on properties of real UAVs, terrains, radars and missiles, and (2) are used to rank the solutions according to the

Jesús Manuel De La Cruz; Eva Besada-portas; Luis Torre-cubillo; Bonifacio Andres-toro; José Antonio López Orozco

2008-01-01

243

Mining Preferred Traversal Paths with HITS

NASA Astrophysics Data System (ADS)

Web usage mining can discover useful information hidden in web logs data. However, many previous algorithms do not consider the structure of web pages, but regard all web pages with the same importance. This paper utilizes HITS values and PNT preferences as measures to mine users' preferred traversal paths. Wë structure mining uses HITS (hypertext induced topic selection) to rank web pages. PNT (preferred navigation tree) is an algorithm that finds users' preferred navigation paths. This paper introduces the Preferred Navigation Tree with HITS (PNTH) algorithm, which is an extension of PNT. This algorithm uses the concept of PNT and takes into account the relationships among web pages using HITS algorithm. This algorithm is suitable for E-commerce applications such as improving web site design and web server performance.

Yeh, Jieh-Shan; Lin, Ying-Lin; Chen, Yu-Cheng

244

Cooperative organic mine avoidance path planning

NASA Astrophysics Data System (ADS)

The JHU/APL Path Planning team has developed path planning techniques to look for paths that balance the utility and risk associated with different routes through a minefield. Extending on previous years' efforts, we investigated real-world Naval mine avoidance requirements and developed a tactical decision aid (TDA) that satisfies those requirements. APL has developed new mine path planning techniques using graph based and genetic algorithms which quickly produce near-minimum risk paths for complicated fitness functions incorporating risk, path length, ship kinematics, and naval doctrine. The TDA user interface, a Java Swing application that obtains data via Corba interfaces to path planning databases, allows the operator to explore a fusion of historic and in situ mine field data, control the path planner, and display the planning results. To provide a context for the minefield data, the user interface also renders data from the Digital Nautical Chart database, a database created by the National Geospatial-Intelligence Agency containing charts of the world's ports and coastal regions. This TDA has been developed in conjunction with the COMID (Cooperative Organic Mine Defense) system. This paper presents a description of the algorithms, architecture, and application produced.

McCubbin, Christopher B.; Piatko, Christine D.; Peterson, Adam V.; Donnald, Creighton R.; Cohen, David

2005-06-01

245

Parallel Shortest Lattice Vector Enumeration on Graphics Cards

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

246

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

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

247

Learning to improve path planning performance

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

248

Nonlinear regularization path for quadratic loss support vector machines.

Regularization path algorithms have been proposed to deal with model selection problem in several machine learning approaches. These algorithms allow computation of the entire path of solutions for every value of regularization parameter using the fact that their solution paths have piecewise linear form. In this paper, we extend the applicability of regularization path algorithm to a class of learning machines that have quadratic loss and quadratic penalty term. This class contains several important learning machines such as squared hinge loss support vector machine (SVM) and modified Huber loss SVM. We first show that the solution paths of this class of learning machines have piecewise nonlinear form, and piecewise segments between two breakpoints are characterized by a class of rational functions. Then we develop an algorithm that can efficiently follow the piecewise nonlinear path by solving these rational equations. To solve these rational equations, we use rational approximation technique with quadratic convergence rate, and thus, our algorithm can follow the nonlinear path much more precisely than existing approaches such as predictor-corrector type nonlinear-path approximation. We show the algorithm performance on some artificial and real data sets. PMID:21880570

Karasuyama, Masayuki; Takeuchi, Ichiro

2011-10-01

249

Path Coupling and Aggregate Path Coupling

In this survey paper, we describe and characterize an extension to the classical path coupling method applied statistical mechanical models, referred to as aggregate path coupling. In conjunction with large deviations estimates, we use this aggregate path coupling method to prove rapid mixing of Glauber dynamics for a large class of statistical mechanical models, including models that exhibit discontinuous phase transitions which have traditionally been more difficult to analyze rigorously. The parameter region for rapid mixing for the generalized Curie-Weiss-Potts model is derived as a new application of the aggregate path coupling method.

Kovchegov, Yevgeniy

2015-01-01

250

Definition of average path and relativity parameter computation in CASA

NASA Astrophysics Data System (ADS)

System CASA (computer-assisted semen analysis) is a medical applicable system which gets the sperm motility and its parameters using image processing method. But there is no any authoritative administration or academic organization gives a set of criterion for CASA now result in lowering the effective compare of work between the labs or researchers. The average path and parameters relative to it as average path velocity, amplitude of lateral head displacement and beat cross frequency are often unable to compare between systems because of different algorithm. The paper presents a new algorithm that could define the average path uniquely and compute those 3 parameters above quickly and handy from any real path.

Wu, Dawei; Huang, Yan; Chen, Xiaohua; Yu, Chang

2001-09-01

251

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

252

An Energy Efficient Stable Election-Based Routing Algorithm for Wireless Sensor Networks

Sensor nodes usually have limited energy supply and they are impractical to recharge. How to balance traffic load in sensors in order to increase network lifetime is a very challenging research issue. Many clustering algorithms have been proposed recently for wireless sensor networks (WSNs). However, sensor networks with one fixed sink node often suffer from a hot spots problem since nodes near sinks have more traffic burden to forward during a multi-hop transmission process. The use of mobile sinks has been shown to be an effective technique to enhance network performance features such as latency, energy efficiency, network lifetime, etc. In this paper, a modified Stable Election Protocol (SEP), which employs a mobile sink, has been proposed for WSNs with non-uniform node distribution. The decision of selecting cluster heads by the sink is based on the minimization of the associated additional energy and residual energy at each node. Besides, the cluster head selects the shortest path to reach the sink between the direct approach and the indirect approach with the use of the nearest cluster head. Simulation results demonstrate that our algorithm has better performance than traditional routing algorithms, such as LEACH and SEP. PMID:24284767

Wang, Jin; Zhang, Zhongqi; Xia, Feng; Yuan, Weiwei; Lee, Sungyoung

2013-01-01

253

Adaptive path planning for flexible manufacturing

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

254

Recently, the proportionate normalized least mean square (PNLMS) algorithm was developed for use in network echo cancelers. In comparison to the normalized least mean square (NLMS) algorithm, PNLMS has very fast initial convergence and tracking when the echo path is sparse. Unfortunately, when the impulse response is dispersive, the PNLMS converges much slower than NLMS. This implies that the rule

Jacob Benesty; Steven L. Gay

2002-01-01

255

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

256

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

257

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

258

Efficient Data Mining for Path Traversal Patterns

In this paper, we explore a new data mining capability that involves mining path traversal patterns in a distributed information-providing environment where documents or objects are linked together to facilitate interactive access. Our solution procedure consists of two steps. First, we derive an algorithm to convert the original sequence of log data into a set of maximal forward references. By

Ming-syan Chen; Jong Soo Park; Philip S. Yu

1998-01-01

259

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

260

Asymptotically optimal path planning and surface reconstruction for inspection

Motivated by inspection applications for marine structures, this thesis develops algorithms to enable their autonomous inspection. Two essential parts of the inspection problem are (1) path planning and (2) surface ...

Papadopoulos, Georgios

2014-01-01

261

Path dependent receding horizon control policies for hybrid electric vehicles

Future hybrid electric vehicles (HEVs) may use path-dependent operating policies to improve fuel economy. In our previous work, we developed a dynamic programming (DP) algorithm for prescribing the battery state of charge ...

Kolmanovsky, Ilya V.

262

Evaluation of concurrent priority queue algorithms. Technical report

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

263

Ridge-valley Path Planning for 3D Terrains

This paper presents a tactical path planning algo- rithm for following ridges or valleys across a 3D terrain. The intent is to generate a path that enables an unmanned vehicle to surveil with maximum observability by traversing the ridges of a terrain or to operate with maximum covertness by navigating the valleys. The input to the algorithm is a 3D

David L. Page; Andreas Koschan; Mongi A. Abidi; James L. Overholt

2006-01-01

264

Monte-Carlo Fork Search for Cooperative Path-Finding

), a new algorithm that solves Cooperative Path-Finding (CPF) problems with simultaneity. The background in the built tree. This idea fits CPF problems in which the branching factor is too large for MCTS or A agents. 1 Introduction Cooperative pathfinding (CPF) addresses the problem of finding paths for a set

Bouzy, Bruno

265

A Framework for Path Sensitive Program Analysis Vijayaraghavan Murali

component is a generic backward algorithm that interleaves the above process with the computationA Framework for Path Sensitive Program Analysis Vijayaraghavan Murali National University that produces path-sensitive analyses with different tradeoffs of accuracy and efficiency. The first component

Jaffar, Joxan

266

Vulnerability of complex networks under path-based attacks

NASA Astrophysics Data System (ADS)

We investigate vulnerability of complex networks including model networks and real-world networks subject to path-based attacks. Specifically, we remove approximately the longest simple path from a network iteratively until there are no paths left in the network. We propose two algorithms, the random augmenting approach (RPA) and the Hamilton-path based approach (HPA), for finding the approximately longest simple path in a network. Results demonstrate that steps of longest-path attacks increase with network density linearly for random networks, while exponentially increasing for scale-free networks. The more homogeneous the degree distribution is, the more fragile the network, which is different from the previous results of node or edge attacks. HPA is generally more efficient than RPA in the longest-path attacks of complex networks. These findings further help us understand the vulnerability of complex systems, better protect complex systems, and design more tolerant complex systems.

Pu, Cun-Lai; Cui, Wei

2015-02-01

267

The shortest-graph method for calculation of the pair-correlation function in crystalline systems

NASA Astrophysics Data System (ADS)

A new method for approximate calculation of the pair correlation function g(r) is proposed for crystalline systems of identical particles with isotropic interactions. The main idea of the method is to account for the relative delocalization of each node in g(r) by using only the shortest lattice graph between the given points, thus neglecting smaller contributions from other (non-shortest) graphs. By employing the Lennard-Jones and Yukawa crystalline systems as representative examples, it is shown that the proposed approach yields very good agreement with the results of molecular dynamics simulations up to the melting line. The approach can be useful in approximating the structure of simple crystals (in particular, of crystalline colloids and plasma crystals), and can also be generalized for systems with anisotropic interactions.

Yurchenko, Stanislav O.

2014-04-01

268

A microwave-based computed tomography system was developed based on a method that uses time domain measurement to determine the shortest path of propagation components between two antennas. The method calculates shortest path of propagation components by examining mixer output DC components, delivering similar precision as chirp-pulse microwave computed tomography. Because post-mixer signal processing need only concerns DC currents, the effects of overshoot characteristics of baseband filters and the like are removed, simplifying measurement. System circuit composition is also simplified, lowering system costs. This paper provides a theoretical framework for the method, an S-parameter verification of the theory, and an experimental verification using a basic hardware construction. Results showed a restored image from the measurement data, indicating the utility of the method for microwave imaging. PMID:22255201

Tamura, Mutsumi; Ogawa, Takahiro; Miyakawa, Michio

2011-01-01

269

ECS 222A: Algorithm Design and Analysis Handout ?? UC Davis --Charles Martel February 10, 2012

the actual cost of a path). We now explore a better approach. Suppose we assign a value h(v) to each vertex, not the sum of the edge weights). c) We now consider how to compute h(v) values so the w (i, j) = w(i, j) + h. We then compute the shortest path from D to each vertex in G (using Bellman-Ford) and let h(v

California at Davis, University of

270

Variational nature, integration, and properties of Newton reaction path.

The distinguished coordinate path and the reduced gradient following path or its equivalent formulation, the Newton trajectory, are analyzed and unified using the theory of calculus of variations. It is shown that their minimum character is related to the fact that the curve is located in a valley region. In this case, we say that the Newton trajectory is a reaction path with the category of minimum energy path. In addition to these findings a Runge-Kutta-Fehlberg algorithm to integrate these curves is also proposed. PMID:21341822

Bofill, Josep Maria; Quapp, Wolfgang

2011-02-21

271

Path Factorization Approach to Stochastic Simulations

NASA Astrophysics Data System (ADS)

The computational efficiency of stochastic simulation algorithms is notoriously limited by the kinetic trapping of the simulated trajectories within low energy basins. Here we present a new method that overcomes kinetic trapping while still preserving exact statistics of escape paths from the trapping basins. The method is based on path factorization of the evolution operator and requires no prior knowledge of the underlying energy landscape. The efficiency of the new method is demonstrated in simulations of anomalous diffusion and phase separation in a binary alloy, two stochastic models presenting severe kinetic trapping.

Athènes, Manuel; Bulatov, Vasily V.

2014-12-01

272

Advanced Physics: Path Integral

NSDL National Science Digital Library

A cursor is shown in an x-y graph. The cursor can be dragged around the graph and its path is marked as it is moved. The data are sent to a DataTable which shows x, y, and the value of the path integral, F.dl.

Christian, Wolfgang; Belloni, Mario

2006-01-19

273

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.

274

Two classes of fracture are defined: I — fracture path completely predictable, and II — fracture path predictable only after initial random propagation. Class I fractures occur when there is a line of principal stress passing through the tip of the initiating notch or slit across which the stress is a maximum away from the tip. All Class II fractures

B. Cotterell

1965-01-01

275

Enzymatic reaction paths as determined by transition path sampling

NASA Astrophysics Data System (ADS)

Enzymes are biological catalysts capable of enhancing the rates of chemical reactions by many orders of magnitude as compared to solution chemistry. Since the catalytic power of enzymes routinely exceeds that of the best artificial catalysts available, there is much interest in understanding the complete nature of chemical barrier crossing in enzymatic reactions. Two specific questions pertaining to the source of enzymatic rate enhancements are investigated in this work. The first is the issue of how fast protein motions of an enzyme contribute to chemical barrier crossing. Our group has previously identified sub-picosecond protein motions, termed promoting vibrations (PVs), that dynamically modulate chemical transformation in several enzymes. In the case of human heart lactate dehydrogenase (hhLDH), prior studies have shown that a specific axis of residues undergoes a compressional fluctuation towards the active site, decreasing a hydride and a proton donor--acceptor distance on a sub-picosecond timescale to promote particle transfer. To more thoroughly understand the contribution of this dynamic motion to the enzymatic reaction coordinate of hhLDH, we conducted transition path sampling (TPS) using four versions of the enzymatic system: a wild type enzyme with natural isotopic abundance; a heavy enzyme where all the carbons, nitrogens, and non-exchangeable hydrogens were replaced with heavy isotopes; and two versions of the enzyme with mutations in the axis of PV residues. We generated four separate ensembles of reaction paths and analyzed each in terms of the reaction mechanism, time of barrier crossing, dynamics of the PV, and residues involved in the enzymatic reaction coordinate. We found that heavy isotopic substitution of hhLDH altered the sub-picosecond dynamics of the PV, changed the favored reaction mechanism, dramatically increased the time of barrier crossing, but did not have an effect on the specific residues involved in the PV. In the mutant systems, we observed changes in the reaction mechanism and altered contributions of the mutated residues to the enzymatic reaction coordinate, but we did not detect a substantial change in the time of barrier crossing. These results confirm the importance of maintaining the dynamics and structural scaffolding of the hhLDH PV in order to facilitate facile barrier passage. We also utilized TPS to investigate the possible role of fast protein dynamics in the enzymatic reaction coordinate of human dihydrofolate reductase (hsDHFR). We found that sub-picosecond dynamics of hsDHFR do contribute to the reaction coordinate, whereas this is not the case in the E. coli version of the enzyme. This result indicates a shift in the DHFR family to a more dynamic version of catalysis. The second inquiry we addressed in this thesis regarding enzymatic barrier passage concerns the variability of paths through reactive phase space for a given enzymatic reaction. We further investigated the hhLDH-catalyzed reaction using a high-perturbation TPS algorithm. Though we saw that alternate reaction paths were possible, the dominant reaction path we observed corresponded to that previously elucidated in prior hhLDH TPS studies. Since the additional reaction paths we observed were likely high-energy, these results indicate that only the dominant reaction path contributes significantly to the overall reaction rate. In conclusion, we show that the enzymes hhLDH and hsDHFR exhibit paths through reactive phase space where fast protein motions are involved in the enzymatic reaction coordinate and exhibit a non-negligible contribution to chemical barrier crossing.

Masterson, Jean Emily

276

The most notable advance in our knowledge of path integration in insects is a new understanding of how the honeybee measures the distance that it travels during its foraging trips. Data from two groups show that the bee's odometer records distance in terms of the net amount of image motion over the retina that is accumulated during a flight. Progress has also been made in clarifying the relation between path integration and other navigational strategies. On unfamiliar ground, path integration is the only available means of navigation. In familiar surroundings, however, guidance by landmarks may override guidance by path integration. Path integration then becomes a back-up strategy that is used primarily when landmarks fail. PMID:11240286

Collett, T S; Collett, M

2000-12-01

277

Optimal paths play a fundamental role in numerous physical applications ranging from random polymers to brittle fracture, from the flow through porous media to information propagation. Here for the first time we explore the path that is activated once this optimal path fails and what happens when this new path also fails and so on, until the system is completely disconnected. In fact many applications can also be found for this novel fracture problem. In the limit of strong disorder, our results show that all the cracks are located on a single self-similar connected line of fractal dimension D(b) approximately = 1.22. For weak disorder, the number of cracks spreads all over the entire network before global connectivity is lost. Strikingly, the disconnecting path (backbone) is, however, completely independent on the disorder. PMID:20366106

Andrade, J S; Oliveira, E A; Moreira, A A; Herrmann, H J

2009-11-27

278

Minimal Path Sets Seismic Reliability Evaluation of Lifeline Networks with Link and Node Failures

A heuristic minimal path sets method for analyzing seismic reliability of lifeline networks is proposed. For large-scale lifeline networks reliability computation can become prohibitive or inaccurate using the current enumeration methods. Although a few studies have considered both node and link failures, none of these methods has utilized the minimal paths method. This paper proposes a minimal path algorithm to

M. B. Javanbarg; C. Scawthorn; J. Kiyono

279

Regularization Paths for Generalized Linear Models via Coordinate Descent

We develop fast algorithms for estimation of generalized linear mod- els 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 de- scent, computed along a regularization path. The methods can

Jerome Friedman; Trevor Hastie; Rob Tibshirani

2008-01-01

280

Natural decomposition of free space for path planning

This paper describes an algorithm that decomposes the free space into nonoverlapping geometric-shaped primitives suitable for path planning. Given a set of polygonal obstacles in space, the algorithm first decomposes concave obstacles into connecting convex obstacles in order to have a uniform obstacle representation, which facilitates later processing. The neighborhood relations among these Convex obstacles are identified and then used

Darwin T. Kuan; James C. Zamiska; Rodney A. Brooks

1985-01-01

281

Path Planning for UAV in Radar Network Area

This paper mainly introduces a path planning algorithm for the unmanned aerial vehicles (UAVs) to avoid radar network. The radar network contains several radars which have different detection ranges. In this algorithm, firstly, according to the theory of the Delaunay triangulations, a directed graph is constructed based on the locations and the detection ranges of the radars. Secondly, the Dijkstra

Fu Xiao-wei; Liu Zhong; Gao Xiao-guang

2010-01-01

282

Disturbance observer based path tracking control of robot manipulator considering torque saturation

This paper proposes a path-tracking algorithm to compensate for path deviation due to torque limits. The algorithm uses a disturbance observer with an additional saturation element at each joint of n degrees of freedom (DOF) manipulator to obtain a simple equivalent robot dynamic (SERD) model. This model is represented as an n independent double integrator system and is designed to

Kwang Sik Eom; Il Hong Suh; Wan Kyun Chung

2001-01-01

283

This is an introductory review of the connection between homotopy theory and path integrals, mainly focus on works done by Schulman [23] that he compared path integral on SO(3) and its universal covering space SU(2), DeWitt and Laidlaw [15] that they proved the theorem to the case of path integrals on the multiply-connected topological spaces. Also, we discuss the application of the theorem in Aharonov-Bohm effect given by [20,24]. An informal introduction to homotopy theory is provided for readers who are not familiar with the theory.

Fumika Suzuki

2011-08-31

284

Feyman path integrals in real time

The numerical calculation of Feynman path integrals (F.P.I.) can be performed in real time, i.e. without continuing to imaginary time, at least for quantum mechanical systems with a small number of degrees of freedom. The algorithm stems from the phase space formulation of the F.P.I. and makes intensive use of the Fast Fourier transform to achieve the required efficiency. Scope

Enrico Onofri; Gian Pietro Tecchiolli

1988-01-01

285

NSDL National Science Digital Library

In this lesson, younger students will be introduced to the various orbital paths that are used for satellites. Using a globe and a satellite model or a large picture of Earth, the teacher will introduce three types of orbital paths (polar, elliptical, and geosynchronous). The students should be able to define 'satellite', define the three types of orbits, describe how satellites orbit the Earth, and understand how they are slowed down by drag from the atmosphere.

286

Twins: The Two Shortest Period Non-Interacting Double Degenerate White Dwarf Stars

We report on the detection of the two shortest period non-interacting white\\u000adwarf binary systems. These systems, SDSS J143633.29+501026.8 and SDSS\\u000aJ105353.89+520031.0, were identified by searching for radial velocity\\u000avariations in the individual exposures that make up the published spectra from\\u000athe Sloan Digital Sky Survey. We followed up these systems with time series\\u000aspectroscopy to measure the period and

F. Mullally; Carles Badenes; Susan E. Thompson; Robert Lupton

2009-01-01

287

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

288

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

2011-12-01

289

NASA Astrophysics Data System (ADS)

Optimal paths computed by conventional path-planning algorithms are usually not "optimal" since realistic traffic information and local road network characteristics are not considered. We present a new experiential approach that computes optimal paths based on the experience of taxi drivers by mining a huge number of floating car trajectories. The approach consists of three steps. First, routes are recovered from original taxi trajectories. Second, an experiential road hierarchy is constructed using travel frequency and speed information for road segments. Third, experiential optimal paths are planned based on the experiential road hierarchy. Compared with conventional path-planning methods, the proposed method provides better experiential optimal path identification. Experiments demonstrate that the travel time is less for these experiential paths than for paths planned by conventional methods. Results obtained for a case study in the city of Wuhan, China, demonstrate that experiential optimal paths can be flexibly obtained in different time intervals, particularly during peak hours.

Li, Qingquan; Zeng, Zhe; Zhang, Tong; Li, Jonathan; Wu, Zhongheng

2011-02-01

290

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

291

Probing nonlinear adiabatic paths with a universal integrator

NASA Astrophysics Data System (ADS)

We apply a flexible numerical integrator to the simulation of adiabatic quantum computation with nonlinear paths. We find that a nonlinear path may significantly improve the performance of adiabatic algorithms versus the conventional straight-line interpolations. The employed integrator is suitable for solving the time-dependent Schrödinger equation for any qubit Hamiltonian. Its flexible storage format significantly reduces cost for storage and matrix-vector multiplication in comparison to common sparse matrix schemes.

Hofmann, Michael; Schaller, Gernot

2014-03-01

292

Adaptive robot path planning in changing environments

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

293

A neural network approach to complete coverage path planning.

Complete coverage path planning requires the robot path to cover every part of the workspace, which is an essential issue in cleaning robots and many other robotic applications such as vacuum robots, painter robots, land mine detectors, lawn mowers, automated harvesters, and window cleaners. In this paper, a novel neural network approach is proposed for complete coverage path planning with obstacle avoidance of cleaning robots in nonstationary environments. The dynamics of each neuron in the topologically organized neural network is characterized by a shunting equation derived from Hodgkin and Huxley's (1952) membrane equation. There are only local lateral connections among neurons. The robot path is autonomously generated from the dynamic activity landscape of the neural network and the previous robot location. The proposed model algorithm is computationally simple. Simulation results show that the proposed model is capable of planning collision-free complete coverage robot paths. PMID:15369113

Yang, Simon X; Luo, Chaomin

2004-02-01

294

Finding reaction paths using the potential energy as reaction coordinate.

The intrinsic reaction coordinate curve (IRC), normally proposed as a representation of a reaction path, is parametrized as a function of the potential energy rather than the arc-length. This change in the parametrization of the curve implies that the values of the energy of the potential energy surface points, where the IRC curve is located, play the role of reaction coordinate. We use Caratheodory's relation to derive in a rigorous manner the proposed parametrization of the IRC path. Since this Caratheodory's relation is the basis of the theory of calculus of variations, then this fact permits to reformulate the IRC model from this mathematical theory. In this mathematical theory, the character of the variational solution (either maximum or minimum) is given through the Weierstrass E-function. As proposed by Crehuet and Bofill [J. Chem. Phys. 122, 234105 (2005)], we use the minimization of the Weierstrass E-function, as a function of the potential energy, to locate an IRC path between two minima from an arbitrary curve on the potential energy surface, and then join these two minima. We also prove, from the analysis of the Weierstrass E-function, the mathematical bases for the algorithms proposed to locate the IRC path. The proposed algorithm is applied to a set of examples. Finally, the algorithm is used to locate a discontinuous, or broken, IRC path, namely, when the path connects two first order saddle points through a valley-ridged inflection point. PMID:18345872

Aguilar-Mogas, Antoni; Giménez, Xavier; Bofill, Josep Maria

2008-03-14

295

A Hybrid Genetic Algorithm for the Point to Multipoint Routing Problem with

A Hybrid Genetic Algorithm for the Point to Multipoint Routing Problem with Single Split Paths Words: Genetic Algorithm, Steiner Trees, Point to Multipoint Routing, Telecommunications Network to Multipoint Routing Problem with Single Split Paths. Our hybrid algorithm uses a genetic algorithm

Wainwright, Roger L.

296

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

297

Test-Data Generation Using Genetic Algorithms

This paper presents a technique that uses a genetic algorithm for automatic test-data generation. A genetic algorithm is a heuristic that mimics the evolution of natural species in searching for the optimal solution to a problem. In the test-data generation application, the solution sought by the genetic algorithm is test data that causes execution of a given statement, branch, path,

Roy P. Pargas; Mary Jean Harrold; Robert R. Peck

1999-01-01

298

Algorithms for effective querying of compound graph-based pathway databases

Background Graph-based pathway ontologies and databases are widely used to represent data about cellular processes. This representation makes it possible to programmatically integrate cellular networks and to investigate them using the well-understood concepts of graph theory in order to predict their structural and dynamic properties. An extension of this graph representation, namely hierarchically structured or compound graphs, in which a member of a biological network may recursively contain a sub-network of a somehow logically similar group of biological objects, provides many additional benefits for analysis of biological pathways, including reduction of complexity by decomposition into distinct components or modules. In this regard, it is essential to effectively query such integrated large compound networks to extract the sub-networks of interest with the help of efficient algorithms and software tools. Results Towards this goal, we developed a querying framework, along with a number of graph-theoretic algorithms from simple neighborhood queries to shortest paths to feedback loops, that is applicable to all sorts of graph-based pathway databases, from PPIs (protein-protein interactions) to metabolic and signaling pathways. The framework is unique in that it can account for compound or nested structures and ubiquitous entities present in the pathway data. In addition, the queries may be related to each other through "AND" and "OR" operators, and can be recursively organized into a tree, in which the result of one query might be a source and/or target for another, to form more complex queries. The algorithms were implemented within the querying component of a new version of the software tool PATIKAweb (Pathway Analysis Tool for Integration and Knowledge Acquisition) and have proven useful for answering a number of biologically significant questions for large graph-based pathway databases. Conclusion The PATIKA Project Web site is http://www.patika.org. PATIKAweb version 2.1 is available at http://web.patika.org. PMID:19917102

2009-01-01

299

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

300

DNA Computing Hamiltonian path

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

301

ERIC Educational Resources Information Center

A growing number of institutions are being more deliberate about bringing in fundraisers who fit the culture of the development department and about assessing skills and providing training that fill specific needs. Development shops are paying more attention to cultivating their staffs, staying attuned to employees' needs and creating career paths…

Coleman, Toni

2012-01-01

302

Scanning path optimization for ultrasound surgery

NASA Astrophysics Data System (ADS)

One of the problems in ultrasound surgery is the long treatment times when large tumour volumes are sonicated. Large tumours are usually treated by scanning the tumour volume using a sequence of individual focus points. During the scanning, it is possible that surrounding healthy tissue suffers from undesired temperature rise. The selection of the scanning path so that the tumour volume is treated as fast as possible while temperature rise in healthy tissue is minimized would increase the efficiency of ultrasound surgery. The main purpose of this paper is to develop a computationally efficient method which optimizes the scanning path. The optimization algorithm is based on the minimum time formulation of the optimal control theory. The developed algorithm uses quadratic cost criteria to obtain the desired thermal dose in the tumour region. The derived method is evaluated with numerical simulations in 3D which are applied to ultrasound surgery of the breast in simplified geometry. Results from the simulations show that the treatment time as well as the total applied energy can be decreased from 16% to 43% as compared to standard sonication. The robustness of the optimized scanning path is studied by varying the perfusion and absorption in the tumour region.

Malinen, Matti; Huttunen, Tomi; Kaipio, Jari P.; Hynynen, Kullervo

2005-08-01

303

TWINS: THE TWO SHORTEST PERIOD NON-INTERACTING DOUBLE DEGENERATE WHITE DWARF STARS

We report on the detection of the two shortest period non-interacting white dwarf binary systems. These systems, SDSS J143633.29+501026.8 and SDSS J105353.89+520031.0, were identified by searching for radial velocity variations in the individual exposures that make up the published spectra from the Sloan Digital Sky Survey. We followed up these systems with time series spectroscopy to measure the period and mass ratios of these systems. Although we only place a lower bound on the companion masses, we argue that they must also be white dwarf stars. With periods of approximately 1 hr, we estimate that the systems will merge in less than 100 Myr, but the merger product will likely not be massive enough to result in a Type 1a supernova.

Mullally, F.; Badenes, Carles; Lupton, Robert [Department of Astrophysical Sciences, Princeton University, Princeton, NJ 08544 (United States); Thompson, Susan E., E-mail: fergal@astro.princeton.ed [Department of Physics and Astronomy, University of Delaware, 217 Sharp Lab, Newark, DE 19716 (United States)

2009-12-10

304

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

305

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

306

This research focuses on trajectory generation algorithms that take into account the stealthiness of autonomous UAVs; generating stealthy paths through a region laden with enemy radars. The algorithm is employed to estimate the risk cost of the navigational space and generate an optimized path based on the user-specified threshold altitude value. Thus the generated path is represented with a set of low-radar risk waypoints being the coordinates of its control points. The radar-aware path planner is then approximated using cubic B-splines by considering the least radar risk to the destination. Simulated results are presented, illustrating the potential benefits of such algorithms.

Ee-may Kan; Meng-hiot Lim; Swee-ping Yeo; Jiun-sien Ho; Zhenhai Shao

2011-01-01

307

SOCIAL PATH FOLLOWING Carmine Oliva

of path following; each agent is now able to avoid static and dynamic obstacles along its path, to predict a specific profile for each agent, our system can also show how different stereotypes of people act in those

Karlsson, Brynjar

308

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

309

Streaming Algorithms for Line Simplification Mohammad Ali Abam

: convex paths where the error is mea- sured using the Hausdorff distance (or FrÂ´echet distance), xy-monotone paths where the error is measured using the Hausdorff distance (or FrÂ´echet distance), and general paths where the error is measured using the FrÂ´echet distance. In the first case the algorithm needs O

Hachenberger, Peter

310

PATHS groundwater hydrologic model

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

311

Path Integrals in Quantum Mechanics

Jean Zinn-Justin's textbook Path Integrals in Quantum Mechanics aims to familiarize the reader with the path integral as a calculational tool in quantum mechanics and field theory. The emphasis is on quantum statistical mechanics, starting with the partition function Tr exp(-? H) and proceeding through the diffusion equation to barrier penetration problems and their semiclassical limit. The 'real time' path

J Louko

2005-01-01

312

A new concept of link-path code has been introduced for a link of a planar kinematic chain with simple joints. An algorithm has been developed for determining link-path codes for all the links of a kinematic chain, leading to the identification of its distinct mechanisms. Based on the concept of link-path code, an algorithm has also been proposed to quantify

V. P Agrawal

1996-01-01

313

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

314

Hierarchical path planning and control of a small fixed-wing UAV: Theory and experimental validation

NASA Astrophysics Data System (ADS)

Recently there has been a tremendous growth of research emphasizing control of unmanned aerial vehicles (UAVs) either in isolation or in teams. As a matter of fact, UAVs increasingly find their way into military and law enforcement applications (e.g., reconnaissance, remote delivery of urgent equipment/material, resource assessment, environmental monitoring, battlefield monitoring, ordnance delivery, etc.). This trend will continue in the future, as UAVs are poised to replace the human-in-the-loop during dangerous missions. Civilian applications of UAVs are also envisioned such as crop dusting, geological surveying, search and rescue operations, etc. In this thesis we propose a new online multiresolution path planning algorithm for a small UAV with limited on-board computational resources. The proposed approach assumes that the UAV has detailed information of the environment and the obstacles only in its vicinity. Information about far-away obstacles is also available, albeit less accurately. The proposed algorithm uses the fast lifting wavelet transform (FLWT) to get a multiresolution cell decomposition of the environment, whose dimension is commensurate to the on-board computational resources. A topological graph representation of the multiresolution cell decomposition is constructed efficiently, directly from the approximation and detail wavelet coefficients. Dynamic path planning is sequentially executed for an optimal path using the A* algorithm over the resulting graph. The proposed path planning algorithm is implemented on-line on a small autopilot. Comparisons with the standard D*-lite algorithm are also presented. We also investigate the problem of generating a smooth, planar reference path from a discrete optimal path. Upon the optimal path being represented as a sequence of cells in square geometry, we derive a smooth B-spline path that is constrained inside a channel that is induced by the geometry of the cells. To this end, a constrained optimization problem is formulated by setting up geometric linear constraints as well as boundary conditions. Subsequently, we construct B-spline path templates by solving a set of distinct optimization problems. For application in UAV motion planning, the path templates are incorporated to replace parts of the entire path by the smooth B-spline paths. Each path segment is stitched together while preserving continuity to obtain a final smooth reference path to be used for path following control. The path following control for a small fixed-wing UAV to track the prescribed smooth reference path is also addressed. Assuming the UAV is equipped with an autopilot for low level control, we adopt a kinematic error model with respect to the moving Serret-Frenet frame attached to a path for tracking controller design. A kinematic path following control law that commands heading rate is presented. Backstepping is applied to derive the roll angle command by taking into account the approximate closed-loop roll dynamics. A parameter adaptation technique is employed to account for the inaccurate time constant of the closed-loop roll dynamics during actual implementation. Finally, we implement the proposed hierarchical path control of a small UAV on the actual hardware platform, which is based on an 1/5 scale R/C model airframe (Decathlon) and the autopilot hardware and software. Based on the hardware-in-the-loop (HIL) simulation environment, the proposed hierarchical path control algorithm has been validated through on-line, real-time implementation on a small micro-controller. By a seamless integration of the control algorithms for path planning, path smoothing, and path following, it has been demonstrated that the UAV equipped with a small autopilot having limited computational resources manages to accomplish the path control objective to reach the goal while avoiding obstacles with minimal human intervention.

Jung, Dongwon

2007-12-01

315

Path Planning on a Compressed Terrain Daniel M. Tracy

-planning algorithm simulates a smugglers and border guards scenario. First, we place observers on a ter- rain so- tection by an observer, path length, and uphill movement. The smuggler is allowed the full range of inter-elevation point terrain visibility is essential for surveying, cell phone tower place- ment

Varela, Carlos

316

Time-Optimal Control of Robotic Manipulators Along Specified Paths

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

317

PATH FOLLOWING CONTROL FOR A MOBILE ROBOT PUSHING A BALL

a rolling ball along a given path, the robot should provide the ball with appropriate force by consecutive pushing operations. A new control algorithm combining a linear feedback control with a normal proportional Moving an object from one position to another is one of the basic tasks of a robot. Normally equipped

Zell, Andreas

318

Multiple Aircraft Deconflicted Path Planning with Weather Avoidance Constraints

Multiple Aircraft Deconflicted Path Planning with Weather Avoidance Constraints Jessica J We present a model predictive control based algorithm for aircraft motion planning that will apply to converging flows of aircraft going through convective weather in the en route airspace. The cost function

Sastry, S. Shankar

319

Path planning for off-road vehicles with a simulator-in-the-loop

This paper describes the development of a real-time path planner for off-road vehicles using a simulator. The work was triggered by a need for an obstacle-avoidance and path-planning system in our work with au- tonomous forest machines. The general idea with the presented system is to extend a standard path-tracking algorithm with a simulator that, in real-time, tries to predict

Thomas Hellström

320

Multiflow and disjoint paths of minimum total cost

We discuss some earlier and recent results in the field of combinatorial network flow theory, considering problems on minimum cost maximum value multiflows (multicommodity flows), minimum cost maximum cardinality sets of edge-disjoint or openly disjoint paths, and related problems. Multiflows (multicommodity flows), minimum cost maximum cardinality sets of edge-disjoint or openly disjoint paths, and related problems. Throughout we deal with the undirected case. We exactly characterize the set of commodity graphs H for which, given an arbitrary network with nonnegative integer-valued capacities and costs, there exists an optimal multiflow f such that the denominator of each component of the vector f is bounded by a constant depending only on H. Moreover, for these H`s there are purely combinatorial polynomial time algorithms for finding such optimal solutions. Another, more complicated, problem is: given a graph G, a subset T of its vertices and a nonnegative function of cost on its edges, find a maximum cardinality set of pairwise edge-disjoint T-paths (i.e., paths in G connecting arbitrary pairs in T) such that the sum of costs of edges occurring in these paths is as small as possible. We give a minimax relation for this problem and develop a strongly polynomial algorithm to solve it. In fact, the former result generalizes the minimax relation involving the maximum number of edge-disjoint T-paths that has been established by Mader and, independently, Lomonosov. As a consequence, one can derive a description of the dominant polyhedron for the set of T,d-joins (a generalization of T-joins) and the dominant polyhedron for the set of so-called multi-joins of a graph. Finally, we present a minimax relation that concerns minimum cost maximum cardinality sets of pairwise openly disjoint T-paths, thus extending another result of Mader. The proof gives rise to a strongly polynomial solution algorithm.

Karzanov, A.

1994-12-31

321

Path planning and control for multiple point surveillance by an unmanned aircraft in wind

In this paper, we explore the surveillance of multiple waypoints by a constant velocity aircraft in the presence of wind. It is assumed that the aircraft has a maximum turning rate and that the wind is equal to a known constant plus small possibly time varying components. The proposed strategy consists of separate path planning and control algorithms. The path

Timothy G. McGee; J. Karl Hedrick

2006-01-01

322

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

323

(Nothing else) MATor(s): Monitoring the Anonymity of Tor's Path Selection

(Nothing else) MATor(s): Monitoring the Anonymity of Tor's Path Selection Michael Backes1,2 Aniket In this paper we present MATor: a framework for rigorously assessing the degree of anonymity in the Tor network deployed Tor, such as its path selection algorithm, Tor consensus data, and the preferences

324

INVESTIGATION OF THE PERFORMANCE OF EP-BAVP (EVOLUTIONARY PROGRAMMING FOR VIRTUAL PATH

INVESTIGATION OF THE PERFORMANCE OF EP-BAVP (EVOLUTIONARY PROGRAMMING FOR VIRTUAL PATH BANDWIDTH investigate the usefulness of an evolutionary programming (EP) optimization algorithm for tackling the problem of Bandwidth Allocation for Virtual Paths (EP-BAVP). Results for two network topologies obtained with EP

Pitsillides, Andreas

325

NSDL National Science Digital Library

This mobile app (available for both iOS and Android devices) was developed by the National Council of Teachers of Mathematics with funding from Verizon Foundation. The app is based on the Decimal Maze from the popular lesson "Too Big or Too Small". The goal is to help Okta reach the target (maximum, minimum, or a specific value) by choosing a path from the top of the maze to the bottom â adding, subtracting, multiplying and dividing as the player goes. Seven levels with seven puzzles in each level test the player's skills with operation with powers of ten, negative numbers, fractions, decimals, and exponents.

2012-01-01

326

NSDL National Science Digital Library

The well known Berkeley Digital Library SunSite, discussed in the February 9, 1996 Scout Report, has recently added a new resource to its collection. The PATH database, maintained by the Harmer E. Davis Transportation Library at the University of California, is "the world's largest bibliographical database pertaining to Intelligent Transportation Systems (ITS)." It is searchable and browsable (Browse by ITS Thesaurus Term), and contains over 9,000 records and abstracts "including monographs, journal articles, conference papers, technical reports, theses and selected media coverage," dating back to the 1940s.

1997-01-01

327

We examine portage sites in the U.S. South, Mid-Atlantic, and Midwest, including those on the fall line, a geomorphological feature in the southeastern U.S. marking the final rapids on rivers before the ocean. Historically, waterborne transport of goods required portage around the falls at these points, while some falls provided water power during early industrialization. These factors attracted commerce and manufacturing. Although these original advantages have long since been made obsolete, we document the continuing importance of these portage sites over time. We interpret these results as path dependence and contrast explanations based on sunk costs interacting with decreasing versus increasing returns to scale. PMID:23935217

Bleakley, Hoyt; Lin, Jeffrey

2012-01-01

328

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

329

A large body of experimental evidence suggests that the hippocampal place field system is involved in reward based navigation learning in rodents. Reinforcement learning (RL) mechanisms have been used to model this, associating the state space in an RL-algorithm to the place-field map in a rat. The convergence properties of RL-algorithms are affected by the exploration patterns of the learner. Therefore, we first analyzed the path characteristics of freely exploring rats in a test arena. We found that straight path segments with mean length 23 cm up to a maximal length of 80 cm take up a significant proportion of the total paths. Thus, rat paths are biased as compared to random exploration. Next we designed a RL system that reproduces these specific path characteristics. Our model arena is covered by overlapping, probabilistically firing place fields (PF) of realistic size and coverage. Because convergence of RL-algorithms is also influenced by the state space characteristics, different PF-sizes and densities, leading to a different degree of overlap, were also investigated. The model rat learns finding a reward opposite to its starting point. We observed that the combination of biased straight exploration, overlapping coverage and probabilistic firing will strongly impair the convergence of learning. When the degree of randomness in the exploration is increased, convergence improves, but the distribution of straight path segments becomes unrealistic and paths become 'wiggly'. To mend this situation without affecting the path characteristic two additional mechanisms are implemented: a gradual drop of the learned weights (weight decay) and path length limitation, which prevents learning if the reward is not found after some expected time. Both mechanisms limit the memory of the system and thereby counteract effects of getting trapped on a wrong path. When using these strategies individually divergent cases get substantially reduced and for some parameter settings no divergence was found anymore at all. Using weight decay and path length limitation at the same time, convergence is not much improved but instead time to convergence increases as the memory limiting effect is getting too strong. The degree of improvement relies also on the size and degree of overlap (coverage density) in the place field system. The used combination of these two parameters leads to a trade-off between convergence and speed to convergence. Thus, this study suggests that the role of the PF-system in navigation learning cannot be considered independently from the animals' exploration pattern. PMID:18446432

Tamosiunaite, Minija; Ainge, James; Kulvicius, Tomas; Porr, Bernd; Dudchenko, Paul; Wörgötter, Florentin

2008-12-01

330

A Potential-Based Path Planning of Articulated Robots with 2DOF Joints

This paper proposes a potential-based path planning algorithm of articulated robots with 2-DOF joints. The algorithm is an extension of a previous algorithm developed for 3-DOF joints. While 3-DOF joints result in a very straightforward potential minimization algorithm, 2-DOF joints are obviously more practical for active operations. The proposed approach computes repulsive force and torque between charged objects by using

Jen-hui Chuang; Chien-chou Lin; Jau-Hong Kao; Cheng-tieng Hsieh

2005-01-01

331

Regularization Paths for Generalized Linear Models via Coordinate Descent

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

332

Decision Path Models for Patient-Specific Modeling of Patient Outcomes

Patient-specific models are constructed to take advantage of the particular features of the patient case of interest compared to commonly used population-wide models that are constructed to perform well on average on all cases. We introduce two patient-specific algorithms that are based on the decision tree paradigm. These algorithms construct a decision path specific for each patient of interest compared to a single population-wide decision tree with many paths that is applicable to all patients of interest that are constructed by standard algorithms. We applied the patient-specific algorithms to predict five different outcomes in clinical datasets. Compared to the population-wide CART decision tree the patient-specific decision path models had superior performance on area under the ROC curve (AUC) and had comparable performance on balanced accuracy. Our results provide support for patient-specific algorithms being a promising approach for predicting clinical outcomes. PMID:24551347

Ferreira, Antonio; Cooper, Gregory F.; Visweswaran, Shyam

2013-01-01

333

Algorithmic randomness and physical entropy

{ital Algorithmic} {ital randomness} provides a rigorous, entropylike measure of disorder of an individual, microscopic, definite state of a physical system. It is defined by the size (in binary digits) of the shortest message specifying the microstate uniquely up to the assumed resolution. Equivalently, algorithmic randomness can be expressed as the number of bits in the smallest program for a universal computer that can reproduce the state in question (for instance, by plotting it with the assumed accuracy). In contrast to the traditional definitions of entropy, algorithmic randomness can be used to measure disorder without any recourse to probabilities. Algorithmic randomness is typically very difficult to calculate exactly but relatively easy to estimate. In large systems, probabilistic ensemble definitions of entropy (e.g., coarse-grained entropy of Gibbs and Boltzmann's entropy {ital H}=ln{ital W}, as well as Shannon's information-theoretic entropy) provide accurate estimates of the algorithmic entropy of an individual system or its average value for an ensemble. One is thus able to rederive much of thermodynamics and statistical mechanics in a setting very different from the usual. {ital Physical} {ital entropy}, I suggest, is a sum of (i) the missing information measured by Shannon's formula and (ii) of the algorithmic information content---algorithmic randomness---present in the available data about the system. This definition of entropy is essential in describing the operation of thermodynamic engines from the viewpoint of information gathering and using systems. These Maxwell demon-type entities are capable of acquiring and processing information and therefore can decide'' on the basis of the results of their measurements and computations the best strategy for extracting energy from their surroundings. From their internal point of view the outcome of each measurement is definite.

Zurek, W.H. (Theoretical Division, Los Alamos National Laboratory, Los Alamos, New Mexico 87545 (US))

1989-10-15

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

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

336

SDSS J0926+3624: the shortest period eclipsing binary star

NASA Astrophysics Data System (ADS)

With orbital periods of the order of tens of minutes or less, the AM Canum Venaticorum stars are ultracompact, hydrogen-deficient binaries with the shortest periods of any binary subclass, and are expected to be among the strongest gravitational wave sources in the sky. To date, the only known eclipsing source of this type is the P= 28 min binary SDSS J0926+3624. We present multiband, high time resolution light curves of this system, collected with William Herschel Telescope (WHT)/ULTRACAM in 2006 and 2009. We supplement these data with additional observations made with Liverpool Telescope/Rapid Imager to Search for Exoplanets (LT/RISE), XMM-Newton and the Catalina Real-Time Transient Survey. From light curve models we determine the mass ratio to be q=M2/M1= 0.041 ± 0.002 and the inclination to be ?. We calculate the mass of the primary white dwarf to be 0.85 ± 0.04 M? and the donor to be 0.035 ± 0.003 M?, implying a partially degenerate state for this component. We observe superhump variations that are characteristic of an elliptical, precessing accretion disc. Our determination of the superhump period excess is in agreement with the established relationship between this parameter and the mass ratio, and is the most precise calibration of this relationship at low q. We also observe a quasi-periodic oscillation in the 2006 data, and we examine the outbursting behaviour of the system over a 4.5 year period.

Copperwheat, C. M.; Marsh, T. R.; Littlefair, S. P.; Dhillon, V. S.; Ramsay, G.; Drake, A. J.; Gänsicke, B. T.; Groot, P. J.; Hakala, P.; Koester, D.; Nelemans, G.; Roelofs, G.; Southworth, J.; Steeghs, D.; Tulloch, S.

2011-01-01

337

Outdoor visual path following experiments

In this paper the performance of a topological- metric visual path following framework is investigated in different environments. The framework relies on a monocular camera as the only sensing modality. The path is represented as a series of reference images such that each neighboring pair contains a number of common landmarks. Local 3D geometries are reconstructed between the neighboring reference

Albert Diosi; Anthony Remazeilles; Sinisa Segvic; François Chaumette

2007-01-01

338

Path integrals as discrete sums

We present a new formulation of Feynman's path integral, based on Voronin's theorems on the universality of the Riemann zeta function. The result is a discrete sum over paths,'' each given by a zeta function. A new measure which leads to the correct quantum mechanics is explicitly given.

Bitar, K.; Khuri, N.N.; Ren, H.C. (Supercomputer Computations Research Institute, Florida State University, Tallahasee, Florida (USA) Department of Physics, The Rockefeller University, New York, New York (USA))

1991-08-12

339

Evolvable Neuronal Paths: A Novel Basis for Information and Search in the Brain

We propose a previously unrecognized kind of informational entity in the brain that is capable of acting as the basis for unlimited hereditary variation in neuronal networks. This unit is a path of activity through a network of neurons, analogous to a path taken through a hidden Markov model. To prove in principle the capabilities of this new kind of informational substrate, we show how a population of paths can be used as the hereditary material for a neuronally implemented genetic algorithm, (the swiss-army knife of black-box optimization techniques) which we have proposed elsewhere could operate at somatic timescales in the brain. We compare this to the same genetic algorithm that uses a standard ‘genetic’ informational substrate, i.e. non-overlapping discrete genotypes, on a range of optimization problems. A path evolution algorithm (PEA) is defined as any algorithm that implements natural selection of paths in a network substrate. A PEA is a previously unrecognized type of natural selection that is well suited for implementation by biological neuronal networks with structural plasticity. The important similarities and differences between a standard genetic algorithm and a PEA are considered. Whilst most experiments are conducted on an abstract network model, at the conclusion of the paper a slightly more realistic neuronal implementation of a PEA is outlined based on Izhikevich spiking neurons. Finally, experimental predictions are made for the identification of such informational paths in the brain. PMID:21887266

Fernando, Chrisantha; Vasas, Vera; Szathmáry, Eörs; Husbands, Phil

2011-01-01

340

Evolvable neuronal paths: a novel basis for information and search in the brain.

We propose a previously unrecognized kind of informational entity in the brain that is capable of acting as the basis for unlimited hereditary variation in neuronal networks. This unit is a path of activity through a network of neurons, analogous to a path taken through a hidden Markov model. To prove in principle the capabilities of this new kind of informational substrate, we show how a population of paths can be used as the hereditary material for a neuronally implemented genetic algorithm, (the swiss-army knife of black-box optimization techniques) which we have proposed elsewhere could operate at somatic timescales in the brain. We compare this to the same genetic algorithm that uses a standard 'genetic' informational substrate, i.e. non-overlapping discrete genotypes, on a range of optimization problems. A path evolution algorithm (PEA) is defined as any algorithm that implements natural selection of paths in a network substrate. A PEA is a previously unrecognized type of natural selection that is well suited for implementation by biological neuronal networks with structural plasticity. The important similarities and differences between a standard genetic algorithm and a PEA are considered. Whilst most experiments are conducted on an abstract network model, at the conclusion of the paper a slightly more realistic neuronal implementation of a PEA is outlined based on Izhikevich spiking neurons. Finally, experimental predictions are made for the identification of such informational paths in the brain. PMID:21887266

Fernando, Chrisantha; Vasas, Vera; Szathmáry, Eörs; Husbands, Phil

2011-01-01

341

BENCHMARKING ROBOT PATH PLANNING ANDREW N. HAND, JAGRUTHI GODUGU, KAVEH ASHENAYI,

1 BENCHMARKING ROBOT PATH PLANNING ANDREW N. HAND, JAGRUTHI GODUGU, KAVEH ASHENAYI, THEODORE W Algorithms (GA's) to develop an algorithm for autonomous robot navigation. We have achieved significant in different categories as Easy, Moderate, Difficult and Very Difficult. INTRODUCTION An autonomous robot

Wainwright, Roger L.

342

British Pathe Newsreels Online

NSDL National Science Digital Library

British Pathe, one of the oldest media companies in the world, recently made available its entire 3500-hour film archive, covering "news, sport, social history and entertainment from 1896 to 1970." At the Web site, users can search by keyword or try out advanced search, if details such as reel numbers or exact titles are known. Casual users may prefer the "Lucky Dip" search, which provides a random selection of films to see. After a search returns a hit list of films, choices include "Preview Film: a page of stills, with a textual description of the clip;" "Download Now: a free, low resolution clip;" or "Add to basket, to purchase higher resolutions of the film." (A rate card giving prices for low and high resolution clips is provided.) One hint for first-time users, though: if files do not seem to download properly, check your email, because you will be sent the URL to retrieve your film. After just a bit of finagling on our first visit, we watched the Beatles at a water-skiing show, Charlie Chaplin, and Sir Ernest Shackleton and his sled dogs photographed in 1916 on returning from their Antarctic expedition.

2002-01-01

343

Algorithms and architectures for high performance analysis of semantic graphs.

Semantic graphs offer one promising avenue for intelligence analysis in homeland security. They provide a mechanism for describing a wide variety of relationships between entities of potential interest. The vertices are nouns of various types, e.g. people, organizations, events, etc. Edges in the graph represent different types of relationships between entities, e.g. 'is friends with', 'belongs-to', etc. Semantic graphs offer a number of potential advantages as a knowledge representation system. They allow information of different kinds, and collected in differing ways, to be combined in a seamless manner. A semantic graph is a very compressed representation of some of relationship information. It has been reported that the semantic graph can be two orders of magnitude smaller than the processed intelligence data. This allows for much larger portions of the data universe to be resident in computer memory. Many intelligence queries that are relevant to the terrorist threat are naturally expressed in the language of semantic graphs. One example is the search for 'interesting' relationships between two individuals or between an individual and an event, which can be phrased as a search for short paths in the graph. Another example is the search for an analyst-specified threat pattern, which can be cast as an instance of subgraph isomorphism. It is important to note than many kinds of analysis are not relationship based, so these are not good candidates for semantic graphs. Thus, a semantic graph should always be used in conjunction with traditional knowledge representation and interface methods. Operations that involve looking for chains of relationships (e.g. friend of a friend) are not efficiently executable in a traditional relational database. However, the semantic graph can be thought of as a pre-join of the database, and it is ideally suited for these kinds of operations. Researchers at Sandia National Laboratories are working to facilitate semantic graph analysis. Since intelligence datasets can be extremely large, the focus of this work is on the use of parallel computers. We have been working to develop scalable parallel algorithms that will be at the core of a semantic graph analysis infrastructure. Our work has involved two different thrusts, corresponding to two different computer architectures. The first architecture of interest is distributed memory, message passing computers. These machines are ubiquitous and affordable, but they are challenging targets for graph algorithms. Much of our distributed-memory work to date has been collaborative with researchers at Lawrence Livermore National Laboratory and has focused on finding short paths on distributed memory parallel machines. Our implementation on 32K processors of BlueGene/Light finds shortest paths between two specified vertices in just over a second for random graphs with 4 billion vertices.

Hendrickson, Bruce Alan

2005-09-01

344

NASA Astrophysics Data System (ADS)

The problem of finding the Hamiltonian path in a graph, or deciding whether a graph has a Hamiltonian path or not, is an NP-complete problem. No exact solution has been found yet, to solve this problem using polynomial amount of time and space. In this paper, we propose a two dimensional (2-D) optical architecture based on optical electronic devices such as micro ring resonators, optical circulators and MEMS based mirror (MEMS-M) to solve the Hamiltonian Path Problem, for undirected graphs in linear time. It uses a heuristic algorithm and employs n+1 different wavelengths of a light ray, to check whether a Hamiltonian path exists or not on a graph with n vertices. Then if a Hamiltonian path exists, it reports the path. The device complexity of the proposed architecture is O(n2).

Shakeri, Nadim; Jalili, Saeed; Ahmadi, Vahid; Rasoulzadeh Zali, Aref; Goliaei, Sama

2015-01-01

345

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

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

346

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

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

347

Heuristically optimal path scanning for high-speed multiphoton circuit imaging

Population dynamics of patterned neuronal firing are fundamental to information processing in the brain. Multiphoton microscopy in combination with calcium indicator dyes allows circuit dynamics to be imaged with single-neuron resolution. However, the temporal resolution of fluorescent measures is constrained by the imaging frequency imposed by standard raster scanning techniques. As a result, traditional raster scans limit the ability to detect the relative timing of action potentials in the imaged neuronal population. To maximize the speed of fluorescence measures from large populations of neurons using a standard multiphoton laser scanning microscope (MPLSM) setup, we have developed heuristically optimal path scanning (HOPS). HOPS optimizes the laser travel path length, and thus the temporal resolution of neuronal fluorescent measures, using standard galvanometer scan mirrors. Minimizing the scan path alone is insufficient for prolonged high-speed imaging of neuronal populations. Path stability and the signal-to-noise ratio become increasingly important factors as scan rates increase. HOPS addresses this by characterizing the scan mirror galvanometers to achieve prolonged path stability. In addition, the neuronal dwell time is optimized to sharpen the detection of action potentials while maximizing scan rate. The combination of shortest path calculation and minimization of mirror positioning time allows us to optically monitor a population of neurons in a field of view at high rates with single-spike resolution, ?125 Hz for 50 neurons and ?8.5 Hz for 1,000 neurons. Our approach introduces an accessible method for rapid imaging of large neuronal populations using traditional MPLSMs, facilitating new insights into neuronal circuit dynamics. PMID:21715667

Sadovsky, Alexander J.; Kruskal, Peter B.; Kimmel, Joseph M.; Ostmeyer, Jared; Neubauer, Florian B.

2011-01-01

348

Heuristically optimal path scanning for high-speed multiphoton circuit imaging.

Population dynamics of patterned neuronal firing are fundamental to information processing in the brain. Multiphoton microscopy in combination with calcium indicator dyes allows circuit dynamics to be imaged with single-neuron resolution. However, the temporal resolution of fluorescent measures is constrained by the imaging frequency imposed by standard raster scanning techniques. As a result, traditional raster scans limit the ability to detect the relative timing of action potentials in the imaged neuronal population. To maximize the speed of fluorescence measures from large populations of neurons using a standard multiphoton laser scanning microscope (MPLSM) setup, we have developed heuristically optimal path scanning (HOPS). HOPS optimizes the laser travel path length, and thus the temporal resolution of neuronal fluorescent measures, using standard galvanometer scan mirrors. Minimizing the scan path alone is insufficient for prolonged high-speed imaging of neuronal populations. Path stability and the signal-to-noise ratio become increasingly important factors as scan rates increase. HOPS addresses this by characterizing the scan mirror galvanometers to achieve prolonged path stability. In addition, the neuronal dwell time is optimized to sharpen the detection of action potentials while maximizing scan rate. The combination of shortest path calculation and minimization of mirror positioning time allows us to optically monitor a population of neurons in a field of view at high rates with single-spike resolution, ? 125 Hz for 50 neurons and ? 8.5 Hz for 1,000 neurons. Our approach introduces an accessible method for rapid imaging of large neuronal populations using traditional MPLSMs, facilitating new insights into neuronal circuit dynamics. PMID:21715667

Sadovsky, Alexander J; Kruskal, Peter B; Kimmel, Joseph M; Ostmeyer, Jared; Neubauer, Florian B; MacLean, Jason N

2011-09-01

349

A Fast Taboo Search Algorithm for the Job Shop Problem

A fast and easily implementable approximation algorithm for the problem of finding a minimum makespan in a job shop is presented. The algorithm is based on a taboo search technique with a specific neighborhood definition which employs a critical path and blocks of operations notions. Computational experiments (up to 2,000 operations) show that the algorithm not only finds shorter makespans

Eugeniusz Nowicki; Czeslaw Smutnicki

1996-01-01

350

A physical retiming algorithm for field programmable gate arrays

In this paper, we present a physical retiming algorithm for sequential circuits implemented in field programmable gate arrays (FPGAs). This algorithm can speed up the sequential circuits by reducing delay of all critical paths with negative slacks. By taking advantage of the physical information provided by placed circuits, this algorithm integrates two operations: retiming and register duplication. Retiming moves registers

Peter Suaris; Dongsheng Wang; Pei-ning Guo; Nan-chi Chou

2003-01-01

351

Robust Path Planning and Feedback Design Under Stochastic Uncertainty

NASA Technical Reports Server (NTRS)

Autonomous vehicles require optimal path planning algorithms to achieve mission goals while avoiding obstacles and being robust to uncertainties. The uncertainties arise from exogenous disturbances, modeling errors, and sensor noise, which can be characterized via stochastic models. Previous work defined a notion of robustness in a stochastic setting by using the concept of chance constraints. This requires that mission constraint violation can occur with a probability less than a prescribed value.In this paper we describe a novel method for optimal chance constrained path planning with feedback design. The approach optimizes both the reference trajectory to be followed and the feedback controller used to reject uncertainty. Our method extends recent results in constrained control synthesis based on convex optimization to solve control problems with nonconvex constraints. This extension is essential for path planning problems, which inherently have nonconvex obstacle avoidance constraints. Unlike previous approaches to chance constrained path planning, the new approach optimizes the feedback gain as wellas the reference trajectory.The key idea is to couple a fast, nonconvex solver that does not take into account uncertainty, with existing robust approaches that apply only to convex feasible regions. By alternating between robust and nonrobust solutions, the new algorithm guarantees convergence to a global optimum. We apply the new method to an unmanned aircraft and show simulation results that demonstrate the efficacy of the approach.

Blackmore, Lars

2008-01-01

352

Partnership for Advancing Technologies in Housing (PATH)

... 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 ...

353

COMPUTER SCIENCE: MISCONCEPTIONS, CAREER PATHS

COMPUTER SCIENCE: MISCONCEPTIONS, CAREER PATHS AND RESEARCH CHALLENGES School of Computing Undergraduate Student) #12;Computer Science Misconceptions Intro to Computer Science - Florida International University 2 Some preconceived ideas & stereotypes about Computer Science (CS) are quite common

Hristidis, Vagelis

354

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

355

Collaborative Authoring of Walden's Paths

of educators, the authoring tool allows educators to collaboratively build a Walden's Path by filtering and organizing web pages into an ordered linear structure for the common information needs, which can be extended, tailored and modified into a derivative...

Li, Yuanling

2012-10-19

356

Scattering theory with path integrals

Starting from well-known expressions for the T-matrix and its derivative in standard nonrelativistic potential scattering, I rederive recent path-integral formulations due to Efimov and Barbashov et al. Some new relations follow immediately.

Rosenfelder, R. [Particle Theory Group, Paul Scherrer Institute, CH-5232 Villigen PSI (Switzerland)] [Particle Theory Group, Paul Scherrer Institute, CH-5232 Villigen PSI (Switzerland)

2014-03-15

357

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

358

Quantum Mechanics: Sum Over Paths

NSDL National Science Digital Library

Created by Edwin F. Taylor a former professor at the Department of Physics at the Massachusetts Institute of Technology, this material describes methods of presenting quantum mechanics using the path-integral formulation. Included are links to a paper and presentation outlining the method, software to simulate the path integrals, and student workbook materials. This course has been used for introducing quantum physics to high school teachers.

Taylor, Edwin F.

2009-05-26

359

Topics in Algorithms 2005 Disjoint Paths, Cuts, Arborescences

A . B' A' . B' x x x x #12;The Cactus of Global Cuts All global min-cuts form a cactus. Any disconnection of the cactus is a min-cut. Exercise?? How many global min-cuts does this imply. x x x x x x x x x

Hariharan, Ramesh

360

Understanding Algorithms by Means of Visualized Path Testing

, Finland Helsinki University of Technology P.O. Box 5400, FIN-02015 HUT, Finland {archie,tarhio}@cs.hut.fi 2 Department of Computer Science University of Joensuu, Finland sutinen@cs.joensuu.fi Abstract Technology Agency, Finland. S. Diehl (Ed.): Software Visualization, LNCS 2269, pp. 256Â268, 2002. c Springer

361

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

362

Lung fissure detection in CT images using global minimal paths

NASA Astrophysics Data System (ADS)

Pulmonary fissures separate human lungs into five distinct regions called lobes. Detection of fissure is essential for localization of the lobar distribution of lung diseases, surgical planning and follow-up. Treatment planning also requires calculation of the lobe volume. This volume estimation mandates accurate segmentation of the fissures. Presence of other structures (like vessels) near the fissure, along with its high variational probability in terms of position, shape etc. makes the lobe segmentation a challenging task. Also, false incomplete fissures and occurrence of diseases add to the complications of fissure detection. In this paper, we propose a semi-automated fissure segmentation algorithm using a minimal path approach on CT images. An energy function is defined such that the path integral over the fissure is the global minimum. Based on a few user defined points on a single slice of the CT image, the proposed algorithm minimizes a 2D energy function on the sagital slice computed using (a) intensity (b) distance of the vasculature, (c) curvature in 2D, (d) continuity in 3D. The fissure is the infimum energy path between a representative point on the fissure and nearest lung boundary point in this energy domain. The algorithm has been tested on 10 CT volume datasets acquired from GE scanners at multiple clinical sites. The datasets span through different pathological conditions and varying imaging artifacts.

Appia, Vikram; Patil, Uday; Das, Bipul

2010-03-01

363

Cross-path LIDAR for Turbulence Profile Determination

NASA Astrophysics Data System (ADS)

Knowledge of the turbulence profile is important for various applications including directed energy systems such as Airborne Laser and Tactical Airborne Laser, ground-based adaptive optics telescopes, and laser communication systems. The known methods for turbulence profile determination have various limitations. We present a concept of a cross-path LIDAR that overcomes these shortcomings. Our sensor system uses laser guide star technology combined with a cross-path wavefront sensing technique. This sensor has several advantages as compared with the known approaches. A cross-path LIDAR has high spatial and temporal resolution, can operate along arbitrary atmospheric paths in the presence of strong turbulence both at daytime and night, and does not depend on the availability of binary stars. We evaluated the feasibility of this approach by carrying out a performance and error budget analysis, developing an analytical model for the wavefront slope cross-correlation and validating this model using wave optics code, examining the sensitivity of the wavefront slope cross-correlation to the variations of the turbulence profile, and developing and testing an inversion algorithm for reconstruction of the turbulence profile from the optical measurements, as well as developing conceptual LIDAR design. The performed study confirmed that the cross-path LIDAR is feasible.

Belenkii, M.; Bruns, D.; Hughes, K.; Rye, V.; Eaton, F.

364

Quantum Adiabatic Algorithms and Large Spin Tunnelling

NASA Technical Reports Server (NTRS)

We provide a theoretical study of the quantum adiabatic evolution algorithm with different evolution paths proposed in this paper. The algorithm is applied to a random binary optimization problem (a version of the 3-Satisfiability problem) where the n-bit cost function is symmetric with respect to the permutation of individual bits. The evolution paths are produced, using the generic control Hamiltonians H (r) that preserve the bit symmetry of the underlying optimization problem. In the case where the ground state of H(0) coincides with the totally-symmetric state of an n-qubit system the algorithm dynamics is completely described in terms of the motion of a spin-n/2. We show that different control Hamiltonians can be parameterized by a set of independent parameters that are expansion coefficients of H (r) in a certain universal set of operators. Only one of these operators can be responsible for avoiding the tunnelling in the spin-n/2 system during the quantum adiabatic algorithm. We show that it is possible to select a coefficient for this operator that guarantees a polynomial complexity of the algorithm for all problem instances. We show that a successful evolution path of the algorithm always corresponds to the trajectory of a classical spin-n/2 and provide a complete characterization of such paths.

Boulatov, A.; Smelyanskiy, V. N.

2003-01-01

365

Finding Shortest Non-Trivial Cycles in Directed Graphs on Surfaces

.cabello@fmf.uni-lj.si Ã?ric Colin de VerdiÃ¨re Laboratoire d'informatique Ã?cole normale supÃ©rieure CNRS, Paris, France Eric.Colin.de.Verdiere@ens.fr Francis Lazarus GIPSA-Lab, CNRS, Grenoble, France Francis.Lazarus@gipsa-lab.grenoble-inp.fr ABSTRACT Let D modeling--Geometric algo- rithms, languages, and systems General Terms: Algorithms, Performance, Theory

Colin de VerdiÃ¨re, Ã?ric

366

On hallucinated garden paths UC San Diego

On hallucinated garden paths Roger Levy UC San Diego Department of Linguistics 2010 LSA Annual., 1995) #12;Garden-pathing in incremental parsing Â· Garden-path sentence a consequence of incrementality recent examples don't match this definition Â· Tabor et al. (2004): garden-paths on continuous substrings

367

Mixed time slicing in path integral simulations

A simple and efficient scheme is presented for using different time slices for different degrees of freedom in path integral calculations. This method bridges the gap between full quantization and the standard mixed quantum-classical (MQC) scheme and, therefore, still provides quantum mechanical effects in the less-quantized variables. Underlying the algorithm is the notion that time slices (beads) may be 'collapsed' in a manner that preserves quantization in the less quantum mechanical degrees of freedom. The method is shown to be analogous to multiple-time step integration techniques in classical molecular dynamics. The algorithm and its associated error are demonstrated on model systems containing coupled high- and low-frequency modes; results indicate that convergence of quantum mechanical observables can be achieved with disparate bead numbers in the different modes. Cost estimates indicate that this procedure, much like the MQC method, is most efficient for only a relatively few quantum mechanical degrees of freedom, such as proton transfer. In this regime, however, the cost of a fully quantum mechanical simulation is determined by the quantization of the least quantum mechanical degrees of freedom.

Steele, Ryan P.; Zwickl, Jill; Shushkov, Philip; Tully, John C. [Department of Chemistry, Yale University, New Haven, Connecticut 06405 (United States)

2011-02-21

368

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

369

FEEDFORWARD ALGORITHMS WITH SIMPLIFIED PLANT MODEL FOR ACTIVE NOISE CONTROL

Most feedforward active noise control (ANC) algorithms require models of electro-acoustic paths. To obtain satisfactory attenuation and keep the system stable these models have to represent the plant well. This, according to the literature, requires estimation of many, often hundreds of coefficients. Then, control filters also have very large, comparable structures. Such an approach reveals significant drawbacks if paths of

M. PAWELCZYK

2002-01-01

370

Nie and Fan THE ARRIVING ON TIME PROBLEM: A DISCRETE ALGORITHM THAT ENSURES

have been introduced, including expected travel time, reliability, value at risk, expectation adaptive optimal path algorithms focus on least expected travel time. Recently, we have proposed an adaptive path finding strategy, named as the SOTA algorithm, to maximize the travel time reliability

Fan, Yueyue

371

Collision-Free Path Planning for Mobile Robots Using Chaotic Particle Swarm Optimization

\\u000a Path planning for mobile robots is an important topic in modern robotics studies. This paper proposes a new approach to collision-free\\u000a path planning problem for mobile robots using the particle swarm optimization combined with chaos iterations. The particle\\u000a swarm optimization algorithm is run to get the global best particle as the candidate solution, and then local chaotic search\\u000a iterations are

Qiang Zhao; Shaoze Yan

2005-01-01

372

Yen-BSR: A New Approach for the Choice of Routes in WDM Networks

NASA Astrophysics Data System (ADS)

In this paper we propose to use an iterative algorithm for optimizing the fixed-alternate shortest path routing in the dynamic routing and wavelength assignment (RWA) problem in wavelength routing optical networks. The algorithm performance is compared, in terms of blocking probability, with the Dijkstra and Yen traditional algorithms, as well as with the recently proposed best among the shortest routes (BSR) algorithm. The results suggest that it is feasible to choose an appropriate set of routes for each pair of nodes (source, destination), among the shortest paths and efficiently balance the network load. For all studied scenarios, the proposed heuristic achieved superior performance.

Santos, A. F.; Almeida, R. C.; Assis, K. D. R.

2014-12-01

373

A new approach to the maximum flow problem

All previously known efftcient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length augmenting paths at once (using the layered network approach of Dinic). An alternative method based on the preflow concept of Karzanov is introduced. A preflow is like a flow, except that the

Andrew V. Goldberg; Robert Endre Tarjan

1986-01-01

374

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

375

Improved transition path sampling methods for simulation of rare events

NASA Astrophysics Data System (ADS)

The free energy surfaces of a wide variety of systems encountered in physics, chemistry, and biology are characterized by the existence of deep minima separated by numerous barriers. One of the central aims of recent research in computational chemistry and physics has been to determine how transitions occur between deep local minima on rugged free energy landscapes, and transition path sampling (TPS) Monte-Carlo methods have emerged as an effective means for numerical investigation of such transitions. Many of the shortcomings of TPS-like approaches generally stem from their high computational demands. Two new algorithms are presented in this work that improve the efficiency of TPS simulations. The first algorithm uses biased shooting moves to render the sampling of reactive trajectories more efficient. The second algorithm is shown to substantially improve the accuracy of the transition state ensemble by introducing a subset of local transition path simulations in the transition state. The system considered in this work consists of a two-dimensional rough energy surface that is representative of numerous systems encountered in applications. When taken together, these algorithms provide gains in efficiency of over two orders of magnitude when compared to traditional TPS simulations.

Chopra, Manan; Malshe, Rohit; Reddy, Allam S.; de Pablo, J. J.

2008-04-01

376

Genetic algorithms (GAs) are search methods based on principles of natural selection and genetics (Fraser, 1957;Bremermann, 1958;Holland, 1975). We start with a brief introduction to simple genetic algorithms and associated terminology.

Kumara Sastry; David Goldberg; Graham Kendall

377

NASA Astrophysics Data System (ADS)

Continuous path tracking control is an important technology for the position control system such as factory automation field. Particulaly, large torque is required for continuous path tracking control at its start position and its goal position. Each AC servo motor of continuous path tracking control have limitation of current and voltage. Therefore, in controlling a multi-degree-of-freedom continuous path tracking control system, even if only the motor torque of one axis has the current limitation, the actual position response is not often equal to the desired trajectory reference. In order to overcome these problems, this paper proposes a new continuous path tracking control algorithm by considering both the saturation of voltage and current. The proposed method assures the coordinated motion by considering the saturation of voltage and current. The effectiveness of the proposed method is confirmed by the experimental results in this paper.

Sazawa, Masaki; Ohishi, Kiyoshi; Katsura, Seiichiro

378

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

379

Research on global path planning based on ant colony optimization for AUV

NASA Astrophysics Data System (ADS)

Path planning is an important issue for autonomous underwater vehicles (AUVs) traversing an unknown environment such as a sea floor, a jungle, or the outer celestial planets. For this paper, global path planning using large-scale chart data was studied, and the principles of ant colony optimization (ACO) were applied. This paper introduced the idea of a visibility graph based on the grid workspace model. It also brought a series of pheromone updating rules for the ACO planning algorithm. The operational steps of the ACO algorithm are proposed as a model for a global path planning method for AUV. To mimic the process of smoothing a planned path, a cutting operator and an insertion-point operator were designed. Simulation results demonstrated that the ACO algorithm is suitable for global path planning. The system has many advantages, including that the operating path of the AUV can be quickly optimized, and it is shorter, safer, and smoother. The prototype system successfully demonstrated the feasibility of the concept, proving it can be applied to surveys of unstructured unmanned environments.

Wang, Hong-Jian; Xiong, Wei

2009-03-01

380

Algorithm Engineering is concerned with the design, analysis, implementation, tun- ing, debugging and experimental evaluation of computer programs for solving algorithmic problems. It provides methodologies and tools for developing and engineering efficient al- gorithmic codes and aims at integrating and reinforcing traditional theoretical approaches for the design and analysis of algorithms and data structures.

Camil Demetrescu; Irene FinocchiGiuseppe; F. Italianok

381

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

382

Path Planning and Obstacle Avoidance Considering Rotary Motion of Load for Overhead Cranes

NASA Astrophysics Data System (ADS)

This paper deals with path planning for autonomous overhead cranes considering load rotation. We present conditions defining interference between rectangular loads and obstacles, and an area in which motion can be performed without interference is determined in configuration space. We then derive a secure path planning algorithm using the potential method based on a 3-dimensional diffusion equation extended to consider rotary motion. A parameter in the extended diffusion equation which suppresses rotary motion is made clear, and its effect is demonstrated. Lastly, we propose a quadratic surface interpolation method for achieving smooth path planning, and its effectiveness is demonstrated through simulation.

Miyoshi, Takanori; Kawakami, Sachio; Terashima, Kazuhiko

383

A Synthesized Heuristic Task Scheduling Algorithm

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. PMID:25254244

Dai, Yanyan; Zhang, Xiangli

2014-01-01

384

Critical Path-Based Thread Placement for NUMA Systems

Multicore multiprocessors use Non Uniform Memory Architecture (NUMA) to improve their scalability. However,NUMA introduces performance penalties due to remote memory accesses. Without efficiently managing data layout and thread mapping to cores, scientific applications, even if they are optimized for NUMA, may suffer performance loss. In this paper, we present an algorithm that optimizes the placement of OpenMP threads on NUMA processors. By collecting information from hardware counters and defining new metrics to capture the effects of thread placement, the algorithm reduces NUMA performance penalty by minimizing the critical path of OpenMP parallel regions and by avoiding local memory resource contention. We evaluate our algorithm with NPB benchmarks and achieve performance improvement between 8.13% and 25.68%, compared to the OS default scheduling.

Su, Chun-Yi [Virginia Polytechnic Institute and State University (Virginia Tech); Li, Dong [ORNL; Nikolopoulos, Dimitrios [FORTH-ICS; Grove, Matthew [Virginia Polytechnic Institute and State University (Virginia Tech); Cameron, Kirk W. [Virginia Polytechnic Institute and State University (Virginia Tech); de Supinski, Bronis R. [Lawrence Livermore National Laboratory (LLNL)

2012-01-01

385

Kinetic constrained optimization of the golf swing hub path.

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 PointsThe 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. PMID:25435779

Nesbit, Steven M; McGinnis, Ryan S

2014-12-01

386

Kinetic Constrained Optimization of the Golf Swing Hub Path

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. PMID:25435779

Nesbit, Steven M.; McGinnis, Ryan S.

2014-01-01

387

A new type of seismic imaging, based on Feynman path integrals for waveform mod- elling, is capable of producing accurate subsurface images without any need for a reference velocity model. Instead of the usual optimization for traveltime curves with maximal signal semblance, a weighted summation over all representative curves avoids the need for velocity analysis, with its common difficulties of

E. Landa; S. Fomel; T. J. Moser

2006-01-01

388

Path integrals for potential scattering

Two path integral representations for the T matrix in nonrelativistic potential scattering are derived and proved to produce the complete Born series when expanded to all orders. They are obtained with the help of ``phantom'' degrees of freedom which take away explicit phases that diverge for asymptotic times. In addition, energy conservation is enforced by imposing a Faddeev-Popov-like constraint in

R. Rosenfelder

2009-01-01

389

Career Paths in Environmental Sciences

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...

390

Describes an approach to probabilistic roadmap planners (PRMs). The overall theme of the algorithm, called Lazy PRM, is to minimize the number of collision checks performed during planning and hence minimize the running time of the planner. Our algorithm builds a roadmap in the configuration space, whose nodes are the user-defined initial and goal configurations and a number of randomly

Robert Bohlin; Lydia E. Kavraki

2000-01-01

391

A transitive closure algorithm for test generation

A transitive-closure-based test generation algorithm is presented. A test is obtained by determining signal values that satisfy a Boolean equation derived from the neural network model of the circuit incorporating necessary conditions for fault activation and path sensitization. The algorithm is a sequence of two main steps that are repeatedly executed: transitive closure computation and decision-making. A key feature of

Srimat T. Chakradhar; Vishwani D. Agrawal; Steven G. Rothweiler

1993-01-01

392

FORMULATIONS FOR DYNAMIC LOT SIZING WITH SERVICE ...

where n is the planning horizon and ? = O(n) is the maximum number of periods in ... Using the proposed shortest path algorithms, we develop alternative tight extended ... [12] for an overview of mixed-integer programming approaches to lot-

2012-05-08

393

Assessing perceptions about hazardous substances (PATHS): the PATHS questionnaire.

How people perceive the nature of a hazardous substance may determine how they respond when potentially exposed to it. We tested a new Perceptions AbouT Hazardous Substances (PATHS) questionnaire. In Study 1 (N = 21), we assessed the face validity of items concerning perceptions about eight properties of a hazardous substance. In Study 2 (N = 2030), we tested the factor structure, reliability and validity of the PATHS questionnaire across four qualitatively different substances. In Study 3 (N = 760), we tested the impact of information provision on Perceptions AbouT Hazardous Substances scores. Our results showed that our eight measures demonstrated good reliability and validity when used for non-contagious hazards. PMID:23104995

Rubin, G James; Amlôt, Richard; Page, Lisa; Pearce, Julia; Wessely, Simon

2013-08-01

394

Obstacle Bypassing in Optimal Ship Routing Using Simulated Annealing

In this paper we are going to discuss a variation on the problem of finding the shortest path between two points in optimal ship routing problems consisting of obstacles that are not allowed to be crossed by the path. Our main goal are going to be the construction of an appropriate algorithm, based in an earlier work by computing the shortest path between two points in the plane that avoids a set of polygonal obstacles.

Kosmas, O. T.; Vlachos, D. S.; Simos, T. E. [University of Pelloponnese, 22100 Tripoli (Greece)

2008-11-06

395

The diagnostic path, a useful visualisation tool in virtual microscopy

Background The Virtual Microscopy based on completely digitalised histological slide. Concerning this digitalisation many new features in mircoscopy can be processed by the computer. New applications are possible or old, well known techniques of image analyses can be adapted for routine use. Aims A so called diagnostic path observes in the way of a professional sees through a histological virtual slide combined with the text information of the dictation process. This feature can be used for image retrieval, quality assurance or for educational purpose. Materials and methods The diagnostic path implements a metadata structure of image information. It stores and processes the different images seen by a pathologist during his "slide viewing" and the obtained image sequence ("observation path"). Contemporary, the structural details of the pathology reports were analysed. The results were transferred into an XML structure. Based on this structure, a report editor and a search function were implemented. The report editor compiles the "diagnostic path", which is the connection from the image viewing sequence ("observation path") and the oral report sequence of the findings ("dictation path"). The time set ups of speech and image viewing serve for the link between the two sequences. The search tool uses the obtained diagnostic path. It allows the user to search for particular histological hallmarks in pathology reports and in the corresponding images. Results The new algorithm was tested on 50 pathology reports and 74 attached histological images. The creation of a new individual diagnostic path is automatically performed during the routine diagnostic process. The test prototype experienced an insignificant prolongation of the diagnosis procedure (oral case description and stated diagnosis by the pathologist) and a fast and reliable retrieval, especially useful for continuous education and quality control of case description and diagnostic work. Discussion The Digital Virtual Microscope has been designed to handle 1000 images per day in the daily routine work of a pathology institution. It implies the necessity of an automatic mechanism of image meta dating. The non – deterministic correlation between the oral statements (case report) and image information content guides the image meta dating. The presented software opens up new possibilities for a content oriented search in a virtual slide, and can successfully support medical education and diagnostic quality assurance. PMID:17092352

Schrader, Thomas; Niepage, Sonja; Leuthold, Thomas; Saeger, Kai; Schluns, Karsten; Hufnagl, Peter; Kayser, Klaus; Dietel, Manfred

2006-01-01

396

Path-Based Failure and Evolution Management

We present a new approach to managing failures and evolution in large, complex distributed systems using runtime paths. We use the paths that requests follow as they move through the system as our core abstraction, and our \\

Mike Y. Chen; Anthony Accardi; Emre Kiciman; David A. Patterson; Armando Fox; Eric A. Brewer

2004-01-01

397

Model for Delay Faults Based upon Paths

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

398

Copper foil provides uniform heat sink path

NASA Technical Reports Server (NTRS)

Thermal path prevents voids and discontinuities which make heat sinks in electronic equipment inefficient. The thermal path combines the high thermal conductivity of copper with the resiliency of silicone rubber.

Phillips, I. E., Jr.; Schreihans, F. A.

1966-01-01

399

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

400

Path entanglement of surface plasmons

NASA Astrophysics Data System (ADS)

Metals can sustain traveling electromagnetic waves at their surfaces supported by the collective oscillations of their free electrons in unison. Remarkably, classical electromagnetism captures the essential physics of these ‘surface plasma’ waves using simple models with only macroscopic features, accounting for microscopic electron–electron and electron–phonon interactions with a single, semi-empirical damping parameter. Nevertheless, in quantum theory these microscopic interactions could be important, as any substantial environmental interactions could decohere quantum superpositions of surface plasmons, the quanta of these waves. Here we report a measurement of path entanglement between surface plasmons with 95% contrast, confirming that a path-entangled state can indeed survive without measurable decoherence. Our measurement suggests that elastic scattering mechanisms of the type that might cause pure dephasing in plasmonic systems must be weak enough not to significantly perturb the state of the metal under the experimental conditions we investigated.

Fakonas, James S.; Mitskovets, Anna; Atwater, Harry A.

2015-02-01

401

A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments

We propose a parallel algorithm which reduces the problem of computing Hamiltonian cycles in tournaments to the problem of computing Hamiltonian paths. The running time of our algorithm is O(log n) using O(n\\u000a2\\/log n) processors on a CRCW PRAM, and O(log n log log n) on an EREW PRAM using O(n\\u000a2\\/log n log log n) processors. As a

Evripidis Bampis; Mohamed El Haddad; Yannis Manoussakis; Miklos Santha

1993-01-01

402

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

403

Multiple paths to encephalization and technical civilizations.

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. PMID:22139517

Schwartzman, David; Middendorf, George

2011-12-01

404

Integrating Temporal Logics and Model Checking Algorithms

in various programming environments that include realÂtime and parallel programs. The diversity of systemsIntegrating Temporal Logics and Model Checking Algorithms Teodor Rus and Eric Van Wyk Department the formulas to quantify the paths over which the satisÂ faction of the temporal operators is defined

Rus, Teodor

405

Squeezed states and path integrals

NASA Technical Reports Server (NTRS)

The continuous-time regularization scheme for defining phase-space path integrals is briefly reviewed as a method to define a quantization procedure that is completely covariant under all smooth canonical coordinate transformations. As an illustration of this method, a limited set of transformations is discussed that have an image in the set of the usual squeezed states. It is noteworthy that even this limited set of transformations offers new possibilities for stationary phase approximations to quantum mechanical propagators.

Daubechies, Ingrid; Klauder, John R.

1992-01-01

406

Accelerating cleanup: Paths to closure

This document was previously referred to as the Draft 2006 Plan. As part of the DOE`s national strategy, the Richland Operations Office`s Paths to Closure summarizes an integrated path forward for environmental cleanup at the Hanford Site. The Hanford Site underwent a concerted effort between 1994 and 1996 to accelerate the cleanup of the Site. These efforts are reflected in the current Site Baseline. This document describes the current Site Baseline and suggests strategies for further improvements in scope, schedule and cost. The Environmental Management program decided to change the name of the draft strategy and the document describing it in response to a series of stakeholder concerns, including the practicality of achieving widespread cleanup by 2006. Also, EM was concerned that calling the document a plan could be misconstrued to be a proposal by DOE or a decision-making document. The change in name, however, does not diminish the 2006 vision. To that end, Paths to Closure retains a focus on 2006, which serves as a point in time around which objectives and goals are established.

Edwards, C.

1998-06-30

407

Fair and efficient call routing and admission control algorithms

We consider the problem of call routing and admission control in general topology networks. Given a network, a call request consists of an origin-destination pair, and a bandwidth requirement. For each request, the routing algorithm must find a path in the network satisfying the bandwidth requirement, and the admission control algorithm must decide whether or not to accept the call.

Lata Narayanan; Yves Saintillan

1999-01-01

408

Multiphoton Path Entanglement by Nonlocal Bunching

Multiphoton path entanglement is created without applying postselection, by manipulating the state of stimulated parametric down-conversion. A specific measurement on one of the two output spatial modes leads to the nonlocal bunching of the photons of the other mode, forming the desired multiphoton path entangled state. We present experimental results for the case of a heralded two-photon path entangled state

H. S. Eisenberg; J. F. Hodelin; G. Khoury; D. Bouwmeester

2005-01-01

409

Multilinear decomposition of human walking paths

In a previous work, the authors have shown how the Principal Components Analysis (PCA) of a set of human walking paths provides sufficient information to derive a linear human-like path generator based on examples. The present work aims to provide an analysis of human walking paths from the perspective of multilinear algebra, using the n-mode Singular Value Decomposition (SVD). This

Christian A. Ramirez; M. Castela?n; G. Arechavaleta

2010-01-01

410

SOME PROPERTIES OF PATH MEASURES CHRISTIAN LEONARD

an unbounded measure. Indeed, its reversing measure is Lebesgue measure (or any of its positive multiple x Rn . Obviously, this path measure has the same unbounded mass as Lebesgue measure.SOME PROPERTIES OF PATH MEASURES CHRISTIAN LÂ´EONARD Abstract. We call any measure on a path space

Paris-Sud XI, UniversitÃ© de

411

Evaluation of the Learning Path Specification

ERIC Educational Resources Information Center

Flexible lifelong learning requires that learners can compare and select learning paths that best meet individual needs, not just in terms of learning goals, but also in terms of planning, costs etc. To this end a learning path specification was developed, which describes both the contents and the structure of any learning path, be it formal,…

Janssen, Jose; Berlanga, Adriana J.; Koper, Rob

2011-01-01

412

Quantifying the Causes of Path Inflation

Researchers have shown that the Internet exhibits path inflation - end-to-end paths can be significantly longer than necessary. We present a trace-driven study of 65 ISPs that characterizes the root causes of path inflation, namely topology and routing policy choices within an ISP, between pairs of ISPs, and across the global Inter- net. To do so, we develop and validate

Neil Spring; Ratul Mahajan; Thomas Anderson

2003-01-01

413

Test data generation and feasible path analysis

This paper describes techniques used by Test Specifica- tion and Determination Tool (TSDT), an experimental prototype for analysis and testing of critical applica- tions written in Ada. Two problems dominate structural testing of programs: exponential explosion in the num- ber of execution paths and feasible path determination, A path is feasible if there exists some input that will cause the

Robert Jasper; Mike Brennan; Keith E. Williamson; Bill Currier; David Zimmerman

1994-01-01

414

Path-independent digital image correlation with high accuracy, speed and robustness

NASA Astrophysics Data System (ADS)

The initial guess transferring mechanism is widely used in iterative DIC algorithms and leads to path-dependence. Using the known deformation at a processed point to estimate the initial guess at its neighboring points could save considerable computation time, and a cogitatively-selected processing path contributes to the improved robustness. In this work, our experimental study demonstrates that a path-independent DIC method is capable to achieve high accuracy, efficiency and robustness in full-field measurement of deformation, by combining an inverse compositional Gauss-Newton (IC-GN) algorithm for sub-pixel registration with a fast Fourier transform-based cross correlation (FFT-CC) algorithm to estimate the initial guess. In the proposed DIC method, the determination of initial guess accelerated by well developed software library can be a negligible burden of computation. The path-independence also endows the DIC method with the ability to handle the images containing large discontinuity of deformation without manual intervention. Furthermore, the possible performance of the proposed path-independent DIC method on parallel computing device is estimated, which shows the feasibility of the development of real-time DIC with high-accuracy.

Jiang, Zhenyu; Kemao, Qian; Miao, Hong; Yang, Jinglei; Tang, Liqun

2015-02-01

415

Mining Relational Paths in Integrated Biomedical Data

Much life science and biology research requires an understanding of complex relationships between biological entities (genes, compounds, pathways, diseases, and so on). There is a wealth of data on such relationships in publicly available datasets and publications, but these sources are overlapped and distributed so that finding pertinent relational data is increasingly difficult. Whilst most public datasets have associated tools for searching, there is a lack of searching methods that can cross data sources and that in particular search not only based on the biological entities themselves but also on the relationships between them. In this paper, we demonstrate how graph-theoretic algorithms for mining relational paths can be used together with a previous integrative data resource we developed called Chem2Bio2RDF to extract new biological insights about the relationships between such entities. In particular, we use these methods to investigate the genetic basis of side-effects of thiazolinedione drugs, and in particular make a hypothesis for the recently discovered cardiac side-effects of Rosiglitazone (Avandia) and a prediction for Pioglitazone which is backed up by recent clinical studies. PMID:22162991

He, Bing; Tang, Jie; Ding, Ying; Wang, Huijun; Sun, Yuyin; Shin, Jae Hong; Chen, Bin; Moorthy, Ganesh; Qiu, Judy; Desai, Pankaj; Wild, David J.

2011-01-01

416

Pareto-path multitask multiple kernel learning.

A traditional and intuitively appealing Multitask Multiple Kernel Learning (MT-MKL) method is to optimize the sum (thus, the average) of objective functions with (partially) shared kernel function, which allows information sharing among the tasks. We point out that the obtained solution corresponds to a single point on the Pareto Front (PF) of a multiobjective optimization problem, which considers the concurrent optimization of all task objectives involved in the Multitask Learning (MTL) problem. Motivated by this last observation and arguing that the former approach is heuristic, we propose a novel support vector machine MT-MKL framework that considers an implicitly defined set of conic combinations of task objectives. We show that solving our framework produces solutions along a path on the aforementioned PF and that it subsumes the optimization of the average of objective functions as a special case. Using the algorithms we derived, we demonstrate through a series of experimental results that the framework is capable of achieving a better classification performance, when compared with other similar MTL approaches. PMID:25532155

Li, Cong; Georgiopoulos, Michael; Anagnostopoulos, Georgios C

2015-01-01

417

Efficient enumeration of monocyclic chemical graphs with given path frequencies

Background The enumeration of chemical graphs (molecular graphs) satisfying given constraints is one of the fundamental problems in chemoinformatics and bioinformatics because it leads to a variety of useful applications including structure determination and development of novel chemical compounds. Results We consider the problem of enumerating chemical graphs with monocyclic structure (a graph structure that contains exactly one cycle) from a given set of feature vectors, where a feature vector represents the frequency of the prescribed paths in a chemical compound to be constructed and the set is specified by a pair of upper and lower feature vectors. To enumerate all tree-like (acyclic) chemical graphs from a given set of feature vectors, Shimizu et al. and Suzuki et al. proposed efficient branch-and-bound algorithms based on a fast tree enumeration algorithm. In this study, we devise a novel method for extending these algorithms to enumeration of chemical graphs with monocyclic structure by designing a fast algorithm for testing uniqueness. The results of computational experiments reveal that the computational efficiency of the new algorithm is as good as those for enumeration of tree-like chemical compounds. Conclusions We succeed in expanding the class of chemical graphs that are able to be enumerated efficiently. PMID:24955135

2014-01-01

418

Completely automated open-path FT-IR spectrometry.

Atmospheric analysis by open-path Fourier-transform infrared (OP/FT-IR) spectrometry has been possible for over two decades but has not been widely used because of the limitations of the software of commercial instruments. In this paper, we describe the current state-of-the-art of the hardware and software that constitutes a contemporary OP/FT-IR spectrometer. We then describe advances that have been made in our laboratory that have enabled many of the limitations of this type of instrument to be overcome. These include not having to acquire a single-beam background spectrum that compensates for absorption features in the spectra of atmospheric water vapor and carbon dioxide. Instead, an easily measured "short path-length" background spectrum is used for calculation of each absorbance spectrum that is measured over a long path-length. To accomplish this goal, the algorithm used to calculate the concentrations of trace atmospheric molecules was changed from classical least-squares regression (CLS) to partial least-squares regression (PLS). For calibration, OP/FT-IR spectra are measured in pristine air over a wide variety of path-lengths, temperatures, and humidities, ratioed against a short-path background, and converted to absorbance; the reference spectrum of each analyte is then multiplied by randomly selected coefficients and added to these background spectra. Automatic baseline correction for small molecules with resolved rotational fine structure, such as ammonia and methane, is effected using wavelet transforms. A novel method of correcting for the effect of the nonlinear response of mercury cadmium telluride detectors is also incorporated. Finally, target factor analysis may be used to detect the onset of a given pollutant when its concentration exceeds a certain threshold. In this way, the concentration of atmospheric species has been obtained from OP/FT-IR spectra measured at intervals of 1 min over a period of many hours with no operator intervention. PMID:18946664

Griffiths, Peter R; Shao, Limin; Leytem, April B

2009-01-01

419

Hypertext Paths and the World-Wide Web: Experiences with Walden's Paths

Walden's Paths applies the concept of hypertextual paths to the World-Wide Web. Walden's Paths is being developed for use in the K-12 school environment. The heterogene- ity of the Web coupled with the desirability of supporting the teacher-student relationship make this an interesting and challenging project. We describe the Walden's Paths imple- mentation, discuss ...

Richard Furuta; Frank M. Shipman III; Catherine C. Marshall; Donald Brenner; Hao-wei Hsieh

1997-01-01

420

Computing LS factor by runoff paths on TIN

NASA Astrophysics Data System (ADS)

The article shows results of topographic factor (the LS factor in USLE) derivation enhancement focused on detailed Airborne Laser Scanning (ALS) based DEMs. It describes a flow paths generation technique using triangulated irregular network (TIN) for terrain morphology description, which is not yet established in soil loss computations. This technique was compared with other procedures of flow direction and flow paths generation based on commonly used raster model (DEM). These overland flow characteristics together with therefrom derived flow accumulation are significant inputs for many scientific models. Particularly they are used in all USLE-based soil erosion models, from which USLE2D, RUSLE3D, Watem/Sedem or USPED can be named as the most acknowledged. Flow routing characteristics are also essential parameters in physically based hydrological and soil erosion models like HEC-HMS, Wepp, Erosion3D, LISEM, SMODERP, etc. Mentioned models are based on regular raster grids, where the identification of runoff direction is problematic. The most common method is Steepest descent (one directional flow), which corresponds well with the concentration of surface runoff into concentrated flow. The Steepest descent algorithm for the flow routing doesn't provide satisfying results, it often creates parallel and narrow flow lines while not respecting real morphological conditions. To overcome this problem, other methods (such as Flux Decomposition, Multiple flow, Deterministic Infinity algorithm etc.) separate the outflow into several components. This approach leads to unrealistic diffusion propagation of the runoff and makes it impossible to be used for simulation of dominant morphological features, such as artificial rills, hedges, sediment traps etc. The modern methods of mapping ground elevations, especially ALS, provide very detailed models even for large river basins, including morphological details. New algorithms for derivation a runoff direction have been developed as a part of the Atlas DMT software package. Starting points for the flow direction generation remain in regular grid (allowing easy contributing area assessment) while realistic direction paths are generated directly at TIN. It turns out that this procedure allows predicting actual runoff paths while ensuring the continuity of the potential runoff by sophisticated filling of sinks and flats. The algorithm is being implemented in a new USLE based erosion model ATLAS EROSION aiming to enhance designing of technical (morphological) soil erosion measures using detailed DEMs. The research has been supported by the research project No. TA02020647 " Atlas EROZE - a modern tool for soil erosion assessment".

Kavka, Petr; Krasa, Josef; Bek, Stanislav

2013-04-01

421

Strategies of Path-Planning for a UAV to Track a Ground Vehicle

In this paper, we present a strategy of path-planning for an unmanned aerial vehicle (UAV) to follow a ground vehicle. The ground vehicle may change its heading and vary its speed from a standstill up to the velocity of the UAV, while the UAV will maintain a fixed airspeed and will maneuver itself to track the ground vehicle. The algorithm

Jusuk Lee; Rosemary Huang; Andrew Vaughn; Xiao Xiao; J. Karl Hedrick; Marco Zennaro; Raja Sengupta

2003-01-01

422

Computer correction of turbulent distortions of image of extended objects on near-Earth paths

An algorithm of computer-based correction of images of extended objects distorted by turbulent atmosphere is developed. The method of computer correction is used to correct a distorted image of an extended object on a horizontal 2300-m-long observation path. The angular size of the corrected-image region was 15'. (image processing)

Averin, A P; Morozov, Yu B; Pryanichkov, V S; Tyapin, V V [Federal State Unitary Enterprise 'I.S.Kos'minov State Scientific-Research Test Laser Centre of Russian Federation 'Raduga' (Russian Federation)

2011-05-31

423

The DLR Robot Motion Simulator Part II: Optimization based path-planning

In Part I of this paper, a novel motion simulator platform is presented, the DLR Robot Motion Simulator with 7 degrees of freedom (DOF). In this Part II, a path-planning algorithm for mentioned platform will be discussed. By replac- ing the widely used hexapod kinematics by an antropomorhic, industrial robot arm mounted on a standard linear axis, a comparably larger

Tobias Bellmann; Martin Otter; Gerd Hirzinger

2011-01-01

424

FPGA implementation of short critical path CORDIC-based approximation of the eight-point DCT

This paper presents an efficient approach for multiplierless implementation for eight-point DCT approximation, which based on coordinate rotation digital computer (CORDIC) algorithm. The main design objective is to make critical path of corresponding circuits shorter and reduce the combinational delay of proposed scheme.

Vashkevich, Maxim; Petrovsky, Alexander

2011-01-01

425

MR-based Real Time Path Planning for Cardiac Operations with Transapical Access

Medical Robotics Lab, and 2 Computer Graphics and Interactive Media Lab, Department of Computer Science invasive surgeries (MIS) have been perpetually evolving due to their potential high impact on improving and surgeries in the beating heart; in this paper we introduce a real-time path planning algorithm

Deng, Zhigang

426

) and Probabilistic Roadmaps (PRMs) are powerful path planning algorithms for high dimensional systems, but even PRMs can solve problems involving 32 robots and 128 total degrees of freedom in less than 10 minutes. We also demonstrate that enhancing RRTs and PRMs with subdimensional expansion can decrease the time

Choset, Howie

427

A combined method for determining reaction paths, minima, and transition state geometries

A combined method for determining reaction paths, minima, and transition state geometries Philippe recently.6Â11 In this paper, we present a combined algorithm that efficiently determines minima, transition and there is no guarantee that the optimization converges to the desired transition state. Combining synchronous transit

Schlegel, H. Bernhard

428

Timeless path integral for relativistic quantum mechanics

NASA Astrophysics Data System (ADS)

Starting from the canonical formalism of relativistic (timeless) quantum mechanics, the formulation of a timeless path integral is rigorously derived. The transition amplitude is reformulated as the sum, or functional integral, over all possible paths in the constraint surface specified by the (relativistic) Hamiltonian constraint, and each path contributes with a phase identical to the classical action divided by ?. The timeless path integral manifests the timeless feature as it is completely independent of the parametrization for paths. For the special case that the Hamiltonian constraint is a quadratic polynomial in momenta, the transition amplitude admits the timeless Feynman's path integral over the (relativistic) configuration space. Meanwhile, the difference between relativistic quantum mechanics and conventional nonrelativistic (with time) quantum mechanics is elaborated on in light of the timeless path integral.

Chiou, Dah-Wei

2013-06-01

429

NASA Technical Reports Server (NTRS)

Yearly, monthly, and time of day fade statistics are presented and characterized. A 19.04 GHz yearly fade distribution, corresponding to a second COMSTAR beacon frequency, is predicted using the concept of effective path length, disdrometer, and rain rate results. The yearly attenuation and rain rate distributions follow with good approximation log normal variations for most fade and rain rate levels. Attenuations were exceeded for the longest and shortest periods of times for all fades in August and February, respectively. The eight hour time period showing the maximum and minimum number of minutes over the year for which fades exceeded 12 db were approximately between 1600 to 2400, and 0400 to 1200 hours, respectively. In employing the predictive method for obtaining the 19.04 GHz fade distribution, it is demonstrated theoretically that the ratio of attenuations at two frequencies is minimally dependent of raindrop size distribution providing these frequencies are not widely separated.

Goldhirsh, J.

1978-01-01

430

The reaction path intrinsic reaction coordinate method and the Hamilton-Jacobi theory.

The definition and location of an intrinsic reaction coordinate path is of crucial importance in many areas of theoretical chemistry. Differential equations used to define the path hitherto are complemented in this study with a variational principle of Fermat type, as Fukui [Int. J. Quantum Chem., Quantum Chem. Symp. 15, 633 (1981)] reported in a more general form some time ago. This definition is more suitable for problems where initial and final points are given. The variational definition can naturally be recast into a Hamilton-Jacobi equation. The character of the variational solution is studied via the Weierstrass necessary and sufficient conditions. The characterization of the local minima character of the intrinsic reaction coordinate is proved. Such result leads to a numerical algorithm to find intrinsic reaction coordinate paths based on the successive minimizations of the Weierstrass E-function evaluated on a guess curve connecting the initial and final points of the desired path. PMID:16008428

Crehuet, Ramon; Bofill, Josep Maria

2005-06-15

431

Path planning method for UUV homing and docking in movement disorders environment.

Path planning method for unmanned underwater vehicles (UUV) homing and docking in movement disorders environment is proposed in this paper. Firstly, cost function is proposed for path planning. Then, a novel particle swarm optimization (NPSO) is proposed and applied to find the waypoint with minimum value of cost function. Then, a strategy for UUV enters into the mother vessel with a fixed angle being proposed. Finally, the test function is introduced to analyze the performance of NPSO and compare with basic particle swarm optimization (BPSO), inertia weight particle swarm optimization (LWPSO, EPSO), and time-varying acceleration coefficient (TVAC). It has turned out that, for unimodal functions, NPSO performed better searching accuracy and stability than other algorithms, and, for multimodal functions, the performance of NPSO is similar to TVAC. Then, the simulation of UUV path planning is presented, and it showed that, with the strategy proposed in this paper, UUV can dodge obstacles and threats, and search for the efficiency path. PMID:25054169

Yan, Zheping; Deng, Chao; Chi, Dongnan; Chen, Tao; Hou, Shuping

2014-01-01

432

Direct path planning in image plane and tracking for visual servoing

NASA Astrophysics Data System (ADS)

The image-based visual servoing would lead to image singularities that might cause control instabilities, and there exit other constraints such as the object should remain in the camera field of view and avoid obstacles. This problem can be solved by coupling path planning and image-based control. The trajectory is planned directly in the image space in our strategy to avoid the 3D estimation of the object, which is required in the motion space based path planning method. In the presented method, the initial path is given using the artificial potential field method without considering the constraints and then genetic algorithm based method is used to check and modify the initial path. This method can achieve satisfactory task while decrease the computation. The proposed method is used to align the micro peg and hole, and the simulation results show that the object can reach its desired position accurately without violation these constrains.

Wang, Junping; Liu, An; Cho, Hyungsuck

2007-10-01

433

Genetics of Path Lengths in Brain Connectivity Networks: HARDI-Based Maps in 457 Adults

Brain connectivity analyses are increasingly popular for investigating organization. Many connectivity measures including path lengths are generally defined as the number of nodes traversed to connect a node in a graph to the others. Despite its name, path length is purely topological, and does not take into account the physical length of the connections. The distance of the trajectory may also be highly relevant, but is typically overlooked in connectivity analyses. Here we combined genotyping, anatomical MRI and HARDI to understand how our genes influence the cortical connections, using whole-brain tractography. We defined a new measure, based on Dijkstra’s algorithm, to compute path lengths for tracts connecting pairs of cortical regions. We compiled these measures into matrices where elements represent the physical distance traveled along tracts. We then analyzed a large cohort of healthy twins and show that our path length measure is reliable, heritable, and influenced even in young adults by the Alzheimer’s risk gene, CLU.

Jahanshad, Neda; Prasad, Gautam; Toga, Arthur W.; McMahon, Katie L.; de Zubicaray, Greig I.; Martin, Nicholas G.; Wright, Margaret J.; Thompson, Paul M.

2014-01-01

434

Path Integration: Effect of Curved Path Complexity and Sensory System on Blindfolded Walking

Path integration refers to the ability to integrate continuous information of the direction and distance travelled by the system relative to the origin. Previous studies have investigated path integration through blindfolded walking along simple paths such as straight line and triangles. However, limited knowledge exists regarding the role of path complexity in path integration. Moreover, little is known about how information from different sensory input systems (like vision and proprioception) contributes to accurate path integration. The purpose of the current study was to investigate how sensory information and curved path complexity affect path integration. Forty blindfolded participants had to accurately reproduce a curved path and return to the origin. They were divided into four groups that differed in the curved path, circle (simple) or figure-eight (complex), and received either visual (previously seen) or proprioceptive (previously guided) information about the path before they reproduced it. The dependent variables used were average trajectory error, walking speed, and distance travelled. The results indicated that (a) both groups that walked on a circular path and both groups that received visual information produced greater accuracy in reproducing the path. Moreover, the performance of the group that received proprioceptive information and later walked on a figure-eight path was less accurate than their corresponding circular group. The groups that had the visual information also walked faster compared to the group that had proprioceptive information. Results of the current study highlight the roles of different sensory inputs while performing blindfolded walking for path integration. PMID:22840893

Koutakis, Panagiotis; Mukherjee, Mukul; Vallabhajosula, Srikant; Blanke, Daniel J.; Stergiou, Nicholas

2012-01-01

435

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 time for each waypoint.

Abbott, Terence S.

2010-01-01

436

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-04-01

437

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

438

A path integral Monte Carlo method for Rényi entanglement entropies

We introduce a quantum Monte Carlo algorithm to measure the R\\'enyi entanglement entropies in systems of interacting bosons in the continuum. This approach is based on a path integral ground state method that can be applied to interacting itinerant bosons in any spatial dimension with direct relevance to experimental systems of quantum fluids. We demonstrate how it may be used to compute spatial mode entanglement, particle partitioned entanglement, and the entanglement of particles, providing insights into quantum correlations generated by fluctuations, indistinguishability and interactions. We present proof-of-principle calculations, and benchmark against an exactly soluble model of interacting bosons in one spatial dimension. As this algorithm retains the fundamental polynomial scaling of quantum Monte Carlo when applied to sign-problem-free models, future applications should allow for the study of entanglement entropy in large scale many-body systems of interacting bosons.

C. M. Herdman; Stephen Inglis; P. -N. Roy; R. G. Melko; A. Del Maestro

2014-04-28

439

Multiple order common path spectrometer

NASA Technical Reports Server (NTRS)

The present invention relates to a dispersive spectrometer. The spectrometer allows detection of multiple orders of light on a single focal plane array by splitting the orders spatially using a dichroic assembly. A conventional dispersion mechanism such as a defraction grating disperses the light spectrally. As a result, multiple wavelength orders can be imaged on a single focal plane array of limited spectral extent, doubling (or more) the number of spectral channels as compared to a conventional spectrometer. In addition, this is achieved in a common path device.

Newbury, Amy B. (Inventor)

2010-01-01

440

Intellimotion: California PATH's Quarterly Newsletter

NSDL National Science Digital Library

The California Partners for Advanced Transit and Highways (PATH) researches methods for increasing highway safety, reducing congestion, and minimizing pollution and energy consumption. Intellimotion is one of its publications that highlights some of the current projects. Although it is labeled as a quarterly newsletter, Intellimotion is released on a very irregular basis. The 2002 issue covers several stories, including a project that makes vehicle navigation with the Global Positioning System extremely accurate. Another article looks at intelligent transportation systems and the issues regarding Bus Rapid Transit. Many past issues of Intellimotion are available on this Web site. This site is also reviewed in the October 25, 2002 Scout Report.

1998-01-01

441

Data Resource Profile: Pathways to Health and Social Equity for Children (PATHS Equity for Children)

The PATHS Data Resource is a unique database comprising data that follow individuals from the prenatal period to adulthood. The PATHS Resource was developed for conducting longitudinal epidemiological research into child health and health equity. It contains individual-level data on health, socioeconomic status, social services and education. Individuals’ data are linkable across these domains, allowing researchers to follow children through childhood and across a variety of sectors. PATHS includes nearly all individuals that were born between 1984 and 2012 and registered with Manitoba’s universal health insurance programme at some point during childhood. All PATHS data are anonymized. Key concepts, definitions and algorithms necessary to work with the PATHS Resource are freely accessible online and an interactive forum is available to new researchers working with these data. The PATHS Resource is one of the richest and most complete databases assembled for conducting longitudinal epidemiological research, incorporating many variables that address the social determinants of health and health equity. Interested researchers are encouraged to contact [mchp_access@cpe.umanitoba.ca] to obtain access to PATHS to use in their own programmes of research. PMID:25212478

Nickel, Nathan C; Chateau, Dan G; Martens, Patricia J; Brownell, Marni D; Katz, Alan; Burland, Elaine MJ; Walld, Randy; Hu, Mingming; Taylor, Carole R; Sarkar, Joykrishna; Goh, Chun Yan

2014-01-01

442

A physical retiming algorithm for field programmable gate arrays (abstract only)

In this paper, we present a physical retiming algorithm for sequential circuits implemented in field programmable gate arrays (FPGAs). This algorithm can speed up the sequential circuits by reducing delay of all critical paths with negative slacks. By taking advantage of the physical information provided by placed circuits, this algorithm integrates two operations: retiming and register duplication. Retiming moves registers

Peter Suaris; Dongsheng Wang; Pei-ning Guo; Nan-chi Chou

2003-01-01

443

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

444

This paper discusses automated scheduling as it applies to complex domains such as factories, transportation, and communications systems. The window-constrained-packing problem is introduced as an ideal model of the scheduling trade offs. Specific algorithms are compared in terms of simplicity, speed, and accuracy. In particular, dispatch, look-ahead, and genetic algorithms are statistically compared on randomly generated job sets. The conclusion

William J. Wolfe; David Wood; Steve Sorensen

1996-01-01

445

Optimum gradient of mountain paths.

By combining the experiment results of R. Margaria (Atti Accad. Naz. Lincei Memorie 7: 299-368, 1938), regarding the metabolic cost of gradient locomotion, together with recent insights on gait biomechanics, a prediction about the most economical gradient of mountain paths (approximately 25%) is obtained and interpreted. The pendulum-like mechanism of walking produces a waste of mechanical work against gravity within the gradient range of up to 15% (the overall efficiency is dominated by the low transmission efficiency), whereas for steeper values only the muscular efficiency is responsible for the (slight) metabolic change (per meter of vertical displacement) with respect to gradient. The speeds at the optimum gradient turned out to be approximately 0.65 m/s (+0.16 m/s vertical) and 1.50 m/s (-0.36 m/s vertical), for uphill and downhill walking, respectively, and the ascensional energy expenditure was 0.4 and 2.0 ml O2.kg body mass-1.vertical m-1 climbed or descended. When the metabolic power becomes a burden, as in high-altitude mountaineering, the optimum gradient should be reduced. A sample of real mountain path gradients, experimentally measured, mimics the obtained predictions. PMID:8594031

Minetti, A E

1995-11-01

446

Transition paths of Met-enkephalin from Markov state modeling of a molecular dynamics trajectory.

Conformational states and their interconversion pathways of the zwitterionic form of the pentapeptide Met-enkephalin (MetEnk) are identified. An explicit solvent molecular dynamics (MD) trajectory is used to construct a Markov state model (MSM) based on dihedral space clustering of the trajectory, and transition path theory (TPT) is applied to identify pathways between open and closed conformers. In the MD trajectory, only four of the eight backbone dihedrals exhibit bistable behavior. Defining a conformer as the string XXXX with X = "+" or "-" denoting, respectively, positive or negative values of a given dihedral angle and obtaining the populations of these conformers shows that only four conformers are highly populated, implying a strong correlation among these dihedrals. Clustering in dihedral space to construct the MSM finds the same four bistable dihedral angles. These state populations are very similar to those found directly from the MD trajectory. TPT is used to obtain pathways, parametrized by committor values, in dihedral state space that are followed in transitioning from closed to open states. Pathway costs are estimated by introducing a kinetics-based procedure that orders pathways from least (shortest) to greater cost paths. The least costly pathways in dihedral space are found to only involve the same XXXX set of dihedral angles, and the conformers accessed in the closed to open transition pathways are identified. For these major pathways, a correlation between reaction path progress (committors) and the end-to-end distance is identified. A dihedral space principal component analysis of the MD trajectory shows that the first three modes capture most of the overall fluctuation, and pick out the same four dihedrals having essentially all the weight in those modes. A MSM based on root-mean-square backbone clustering was also carried out, with good agreement found with dihedral clustering for the static information, but with results that differ significantly for the pathway analysis. PMID:24571787

Banerjee, Rahul; Cukier, Robert I

2014-03-20

447

Methyl alcohol (CH3OH) molecules pumped with the 9R(16) CW CO2 laser line generate two new far-infrared laser lines at wavelengths of 33.4 and 36.4 mu m. The 33.4 mu m line has the shortest wavelength among the sub-mm lines reported so far from CH3OH and its isotopic species pumped with CW CO2 laser lines. Stark splitting is observed on the

N. Sokabe; T. Miyatake; Y. Nishi; A. Murai

1983-01-01

448

Autonomous path-planning navigation system for site characterization

NASA Astrophysics Data System (ADS)

The location and removal of buried munitions is an important yet hazardous task. Current development is aimed at performing both the ordnance location and removal tasks autonomously. An autonomous survey vehicle (ASV) named the Gator has been developed at the Center for Intelligent Machines and Robotics, under the direction of Wright Laboratory, Tyndall Air Force Base, Florida, and the Navy Explosive Ordnance Disposal Technology Division, Indian Head, Maryland. The primary task of the survey vehicle is to autonomously traverse an off-road site, towing behind it a trailer containing a sensor package capable of characterizing the sub-surface contents. Achieving 00 percent coverage of the site is critical to fully characterizing the site. This paper presents a strategy for planning efficient paths for the survey vehicle that guarantees near-complete coverage of a site. A small library of three in-house developed path planners are reviewed. A strategy is also presented to keep the trailer on-path and to calculate the percent of coverage of a site with a resolution of 0.01 m2. All of the algorithms discussed in this paper were initially developed in simulation on a Silicon Graphics computer and subsequently implemented on the survey vehicle.

Rankin, Arturo L.; Crane, Carl D., III; Armstrong, David G., II; Nease, Allen D.; Brown, H. Edward

1996-05-01

449

Path integral Monte Carlo on a lattice: Extended states

NASA Astrophysics Data System (ADS)

The equilibrium properties of a single quantum particle (qp) interacting with a classical gas for a wide range of temperatures that explore the system's behavior in the classical as well as in the quantum regime is investigated. Both the qp and atoms are restricted to the sites of a one-dimensional lattice. A path integral formalism is developed within the context of the canonical ensemble in which the qp is represented by a closed, variable-step random walk on the lattice. Monte Carlo methods are employed to determine the system's properties. For the case of a free particle, analytical expressions for the energy, its fluctuations, and the qp-qp correlation function are derived and compared with the Monte Carlo simulations. To test the usefulness of the path integral formalism, the Metropolis algorithm is employed to determine the equilibrium properties of the qp for a periodic interaction potential, forcing the qp to occupy extended states. We consider a striped potential in one dimension, where every other lattice site is occupied by an atom with potential ?, and every other lattice site is empty. This potential serves as a stress test for the path integral formalism because of its rapid site-to-site variation. An analytical solution was determined in this case by utilizing Bloch's theorem due to the periodicity of the potential. Comparisons of the potential energy, the total energy, the energy fluctuations, and the correlation function are made between the results of the Monte Carlo simulations and the analytical calculations.

O'Callaghan, Mark; Miller, Bruce N.

2014-04-01

450

Efficient growth of complex graph states via imperfect path erasure

NASA Astrophysics Data System (ADS)

Given a suitably large and well connected (complex) graph state, any quantum algorithm can be implemented purely through local measurements on the individual qubits. Measurements can also be used to create the graph state: path erasure techniques allow one to entangle multiple qubits by determining only global properties of the qubits. Here, this powerful approach is extended by demonstrating that even imperfect path erasure can produce the required graph states with high efficiency. By characterizing the degree of error in each path erasure attempt, one can subsume the resulting imperfect entanglement into an extended graph state formalism. The subsequent growth of the improper graph state can be guided, through a series of strategic decisions, in such a way as to bound the growth of the error and eventually yield a high-fidelity graph state. As an implementation of these techniques, we develop an analytic model for atom (or atom-like) qubits in mismatched cavities, under the double-heralding entanglement procedure of Barrett and Kok (2005 Phys. Rev. A 71 060310). Compared to straightforward post-selection techniques our protocol offers a dramatic improvement in growing complex high-fidelity graph states.

Campbell, Earl T.; Fitzsimons, Joseph; Benjamin, Simon C.; Kok, Pieter

2007-06-01

451

A simple way to improve path consistency processing in interval algebra networks

Reasoning about qualitative temporal information is essential in many artificial intelligence problems. In particular, many tasks can be solved using the interval-based temporal algebra introduced by Allen (A1183). In this framework, one of the main tasks is to compute the transitive closure of a network of relations between intervals (also called path consistency in a CSP-like terminology). Almost all previous path consistency algorithms proposed in the temporal reasoning literature were based on the constraint reasoning algorithms PC-1 and PC-2 (Mac77). In this paper, we first show that the most efficient of these algorithms is the one which stays the closest to PC-2. Afterwards, we propose a new algorithm, using the idea {open_quotes}one support is sufficient{close_quotes} (as AC-3 (Mac77) does for arc consistency in constraint networks). Actually, to apply this idea, we simply changed the way composition-intersection of relations was achieved during the path consistency process in previous algorithms.

Bessiere, C. [LIRMM, Montpellier (France)

1996-12-31

452

A Reliable Primary-Backup Routing Algorithm in Wireless Sensor Netwrok

NASA Astrophysics Data System (ADS)

Fault-tolerance is one of important issues in wireless sensor network (WSN) since it is critical in real deployed environments to realize network stability and reduce demand times. In this paper, we propose primary-backup technique by creating a backup path for every sensor on a primary path of data transmission. Especially, we take high reliability path as selected primary or backup path method. The experimental results show that the algorithm not only has the low packet delivery ratio characters, but also ensures the reliability of topology paths and extends the network life-cycle efficiently.

Weipeng, Jing; Qu, Wu; Yaqiu, Liu; Qianlong, Zhang

453

A temperature control algorithm of immersion liquid for immersion lithography

NASA Astrophysics Data System (ADS)

Immersion lithography is one of the main technologies used to manufacture integrated circuits with the shortest feature size. In immersion lithography, temperature of immersion liquid is strictly constrained and its allowable range is less than +/-0.01°C at 22°C. To meet this requirement, a temperature control algorithm adopted by the test rig which controls the temperature of the immersion liquid with process cooling water (PCW) via heat exchangers is proposed. By adjusting the flow rate of PCW through the heat exchangers, the control system varies the amount of heat exchanged, and the temperature of the immersion liquid can be properly controlled. The temperature control rig is a multi-disturbed, timevariant, non-linear and time-delayed system and its transfer function varies with the inlet temperature and flow rates of the streams through the heat exchangers. Considering the characteristics of the system, a cascade-connected fuzzy PID feedback algorithm is designed.

He, Junwei; Li, Xiaoping; Lei, Min; Chen, Bing; Wang, Jinchun

2014-03-01

454

Identifying the primitive path mesh in entangled polymer liquids.

Similar to entangled ropes, polymer chains cannot slide through each other. These topological constraints, the so-called entanglements, dominate the viscoelastic behavior of high-molecular-weight polymeric liquids. Tube models of polymer dynamics and rheology are based on the idea that entanglements confine a chain to small fluctuations around a primitive path which follows the coarse-grained chain contour. To establish the microscopic foundation for these highly successful phenomenological models, we have recently introduced a method for identifying the primitive path mesh that characterizes the microscopic topological state of computer-generated conformations of long-chain polymer melts and solutions. Here we give a more detailed account of the algorithm and discuss several key aspects of the analysis that are pertinent for its successful use in analyzing the topology of the polymer configurations. We also present a slight modification of the algorithm that preserves the previously neglected self-entanglements and allows us to distinguish between local self-knots and entanglements between distant sections of the same chain. Our results indicate that the latter make a negligible contribution to the tube and that the contour length between local self-knots, N{sub 1k} is significantly larger than the entanglement length N{sub e}.

Sukumaran, Sathish K. (Max-Planck-Institut fur Polymerforshung, Postfach, Mainz, Germany); Kremer, Kurt (Max-Planck-Institut fur Polymerforshung, Postfach, Mainz, Germany); Grest, Gary Stephen; Everaers, Ralf (Max-Planck-Institut fur Physik komplexer Systeme, Dresden, Germany)

2004-10-01

455

Autonomous underwater vehicle adaptive path planning for target classification

NASA Astrophysics Data System (ADS)

Autonomous underwater vehicles (AUVs) are being rapidly developed to carry sensors into the sea in ways that have previously not been possible. The full use of the vehicles, however, is still not near realization due to lack of the true vehicle autonomy that is promised in the label (AUV). AUVs today primarily attempt to follow as closely as possible a preplanned trajectory. The key to increasing the autonomy of the AUV is to provide the vehicle with a means to make decisions based on its sensor receptions. The current work examines the use of active sonar returns from mine-like objects (MLOs) as a basis for sensor-based adaptive path planning, where the path planning objective is to discriminate between real mines and rocks. Once a target is detected in the mine hunting phase, the mine classification phase is initialized with a derivative cost function to emphasize signal differences and enhance classification capability. The AUV moves adaptively to minimize the cost function. The algorithm is verified using at-sea data derived from the joint MIT/SACLANTCEN GOATS experiments and advanced acoustic simulation using SEALAB. The mission oriented operating system (MOOS) real-time simulator is then used to test the onboard implementation of the algorithm.

Edwards, Joseph R.; Schmidt, Henrik

2002-11-01

456

Sequential Path Entanglement for Quantum Metrology

Path entanglement is a key resource for quantum metrology. Using path-entangled states, the standard quantum limit can be beaten, and the Heisenberg limit can be achieved. However, the preparation and detection of such states scales unfavourably with the number of photons. Here we introduce sequential path entanglement, in which photons are distributed across distinct time bins with arbitrary separation, as a resource for quantum metrology. We demonstrate a scheme for converting polarization Greenberger-Horne-Zeilinger entanglement into sequential path entanglement. We observe the same enhanced phase resolution expected for conventional path entanglement, independent of the delay between consecutive photons. Sequential path entanglement can be prepared comparably easily from polarization entanglement, can be detected without using photon-number-resolving detectors, and enables novel applications.

Jin, Xian-Min; Peng, Cheng-Zhi; Deng, Youjin; Barbieri, Marco; Nunn, Joshua; Walmsley, Ian A.

2013-01-01

457

-constrained path, QoS routing, phase transition. I. INTRODUCTION THERE is an increasing demand for using real-time--Finding a path in a network based on multiple con- straints (the MCP problem) is often considered an integral. The routing algorithm uses this information to compute shortest paths. Best-effort routing performs

Van Mieghem, Piet

458

Steam Path Audits on Industrial Steam Turbines

steam Path Audits on Industrial steam Turbines DOUGLAS R. MITCHELL. ENGINEER. ENCOTECH, INC., SCHENECTADY, NEW YORK ABSTRACT The electric utility industry has benefitted from steam path audits on steam turbines for several years. Benefits... include the ability to identify areas of performance degradation during a turbine outage. Repair priorities can then be set in accordance with quantitative results from the steam path audit. As a result of optimized repair decisions, turbine...

Mitchell, D. R.

459

Multiphoton Path Entanglement by Nonlocal Bunching

NASA Astrophysics Data System (ADS)

Multiphoton path entanglement is created without applying postselection, by manipulating the state of stimulated parametric down-conversion. A specific measurement on one of the two output spatial modes leads to the nonlocal bunching of the photons of the other mode, forming the desired multiphoton path entangled state. We present experimental results for the case of a heralded two-photon path entangled state and show how to extend this scheme to higher photon numbers.

Eisenberg, H. S.; Hodelin, J. F.; Khoury, G.; Bouwmeester, D.

2005-03-01

460

Multiphoton Path Entanglement by Nonlocal Bunching

Multiphoton path entanglement is created without applying post-selection, by\\u000amanipulating the state of stimulated parametric down-conversion. A specific\\u000ameasurement on one of the two output spatial modes leads to the non-local\\u000abunching of the photons of the other mode, forming the desired multiphoton path\\u000aentangled state. We present experimental results for the case of a heralded\\u000atwo-photon path entangled state

H. S. Eisenberg; J. F. Hodelin; G. Khoury; D. Bouwmeester

2005-01-01

461

Multiphoton path entanglement by nonlocal bunching.

Multiphoton path entanglement is created without applying postselection, by manipulating the state of stimulated parametric down-conversion. A specific measurement on one of the two output spatial modes leads to the nonlocal bunching of the photons of the other mode, forming the desired multiphoton path entangled state. We present experimental results for the case of a heralded two-photon path entangled state and show how to extend this scheme to higher photon numbers. PMID:15783951

Eisenberg, H S; Hodelin, J F; Khoury, G; Bouwmeester, D

2005-03-11

462

Walden's Paths quiz: system design and implementation

assessment io guide instruction, to provide fccdback to students, and to plan for further development ol the path or the Web pages included in the path. Cox and Junkin [13] discuss how instructors can use the results of an automatically evaluated test... Walden's Paths Quiz: System Design and Implementation. (December 2002) Avital Jayant Arora, B. E. , Universiiy of Bombay Chair of Advisory Committee: Dr. Richard Furuta Thts thesis describes the motivation for onlme testing, compares the effectiveness...

Arora, Avital Jayant

2012-06-07

463

Microwave propagation over mountain-diffraction paths

An experimental study was undertaken to obtain a more complete picture of wide-band transmission via microwave propagation over mountain-diffraction paths. Such paths are characterized by obstacles of irregular shape, and pathlength very large compared to wavelength. Swept-frequency transmission was used to provide a record of signal-level variations with time and frequency on two different paths. Other observations included polarization dependence,

A. Carlson

1966-01-01

464

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

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

465

Long linear polymers in strongly disordered media are well described by self-avoiding walks (SAWs) on percolation clusters. The length-distribution of these SAWs encompasses to distinct averages, viz. the averages over cluster- and SAW-conformations. For the latter average, there are two basic options, one being static and one being kinetic. It is well known for static averaging that if the disorder of the underlying medium is weak, differences to the ordered case appear merely in non-universal quantities. Using dynamical field theory, we show that the same holds true for kinetic averaging. For strong disorder, i.e., the medium being close to the percolation point, we employ a field theory for the nonlinear random resistor network in conjunction with a real-world interpretation of Feynman diagrams, and we calculate the scaling exponents for the shortest, the longest and the mean or average SAW to 2-loop order. In addition, we calculate to 2-loop order the entire family of multifractal exponents that governs the moments of the the statistical weights of the elementary constituents (bonds or sites of the underlying fractal cluster) contributing to the SAWs. Our RG analysis reveals that kinetic averaging leads to renormalizability whereas static averaging does not, and hence, we argue that the latter does not lead to a well-defined scaling limit. We discuss the possible implications of this finding for experiments and numerical simulations which have produced wide-spread results for the exponent of the average SAW. To corroborate our results, we also study the well-known Meir-Harris model for SAWs on percolation clusters. We demonstrate that this model leads back to 2-loop order to the renormalizable real world formulation with kinetic averaging if the replica limit is consistently performed at the first possible instant of the calculation.

Hans-Karl Janssen; Olaf Stenull

2011-11-22

466

Langevin equation path integral ground state.

We propose a Langevin equation path integral ground state (LePIGS) approach for the calculation of ground state (zero temperature) properties of molecular systems. The approach is based on a modification of the finite temperature path integral Langevin equation (PILE) method (J. Chem. Phys. 2010, 133, 124104) to the case of open Feynman paths. Such open paths are necessary for a ground state formulation. We illustrate the applicability of the method using model systems and the weakly bound water-parahydrogen dimer. We show that the method can lead to converged zero point energies and structural properties. PMID:23738885

Constable, Steve; Schmidt, Matthew; Ing, Christopher; Zeng, Tao; Roy, Pierre-Nicholas

2013-08-15

467

The Logic behind Feynman's Paths

The classical notions of continuity and mechanical causality are left in order to refor- mulate the Quantum Theory starting from two principles: I) the intrinsic randomness of quantum process at microphysical level, II) the projective representations of sym- metries of the system. The second principle determines the geometry and then a new logic for describing the history of events (Feynman's paths) that modifies the rules of classical probabilistic calculus. The notion of classical trajectory is replaced by a history of spontaneous, random an discontinuous events. So the theory is reduced to determin- ing the probability distribution for such histories according with the symmetries of the system. The representation of the logic in terms of amplitudes leads to Feynman rules and, alternatively, its representation in terms of projectors results in the Schwinger trace formula.

Edgardo T. Garcia Alvarez

2010-11-22

468

Optimal Path Choice in Railway Passenger Travel Network Based on Residual Train Capacity

Passenger's optimal path choice is one of the prominent research topics in the field of railway passenger transport organization. More and more different train types are available, increasing path choices from departure to destination for travelers are unstoppable. However, travelers cannot avoid being confused when they hope to choose a perfect travel plan based on various travel time and cost constraints before departure. In this study, railway passenger travel network is constructed based on train timetable. Both the generalized cost function we developed and the residual train capacity are considered to be the foundation of path searching procedure. The railway passenger travel network topology is analyzed based on residual train capacity. Considering the total travel time, the total travel cost, and the total number of passengers, we propose an optimal path searching algorithm based on residual train capacity in railway passenger travel network. Finally, the rationale of the railway passenger travel network and the optimal path generation algorithm are verified positively by case study. PMID:25097867

Dou, Fei; Yan, Kai; Huang, Yakun; Jia, Limin

2014-01-01

469

Dual-path block size decision for fast motion search in H.264/AVC

NASA Astrophysics Data System (ADS)

We propose a fast motion search method for H.264/AVC with dual-path block size decision. H.264/AVC employs variable block sizes for motion compensation to reduce coding bits of inter-frame prediction error, which requires considerable amount of computation time when motion estimation is performed for every block size. Our algorithm contains two strategies to reduce computation time for motion search; block size mode reduction and search range reduction. According to these strategies, our algorithm consists of two stages. At the first stage, RDCost-based block size mode reduction is conducted. Rate-distortion function (RDCost) for skip mode is calculated at first, which determines the smallest block size for motion search. The second stage is a fast variable block size motion estimation which contains two paths, 16x16-first and 8x8-first. The 16x16-first path is invoked when the minimum block size determined at the first stage is larger than 8x8. In the 8x8-first path, search range for blocks larger than 8x8 is reduced according to distance between motion vectors for 8x8 blocks. From our experiment using JM 8.5, it is confirmed that our algorithm can reduce about 89.3% of computation time as compared to JM, with only negligible PSNR degradation.

Shimizu, Tomoyuki; Yoneyama, Akio; Takishima, Yasuhiro

2005-07-01

470

Cellular Automata Segmentation of Brain Tumors on Post Contrast MR Images

] have been interpreted as special cases of a general seeded segmentation algorithm, which solves to show that the result of its state evolution converges to that of the shortest path algorithm. We demonstrated the proposed algorithm outperforms graph cut and grow cut algorithms in all cases with a lower

Yanikoglu, Berrin

471

Model Checking Almost All Paths Can Be Less Expensive than Checking All Paths

Model Checking Almost All Paths Can Be Less Expensive than Checking All Paths Matthias Schmalz 1 and nite-state systems, the two notions of smallness coincide. More importantly, they coincide 1 Matthias.Schmalz

Varacca, Daniele - Laboratoire Preuves, Programmes et SystÃ¨mes, UniversitÃ© Paris 7

472

NASA Astrophysics Data System (ADS)

Numerical analysis of optical propagation in highly scattering media is investigated when light is normally incident to the surface and re-emerges backward from the same point. This situation corresponds to practical light scattering setups, such as in optical coherence tomography. The simulation uses the path-length-assigned Monte Carlo method based on an ellipsoidal algorithm. The spatial distribution of the scattered light is determined and the dependence of its width and penetration depth on the path-length is found. The backscattered light is classified into three types, in which ballistic, snake, and diffuse photons are dominant.

Ishii, Katsuhiro; Nishidate, Izumi; Iwai, Toshiaki

2014-05-01

473

Resynthesis of Combinational Circuts for Path Count Reduction and for Path Delay Fault Testability

Path delay fault model is the most suitable model for detecting distributed manufacturing defects that can cause delay faults. However, the number of paths in a modern design can be extremely large and the path delay testability of many practical designs could be very low. In this paper we show how to resynthesize a combinational circuit in order to reduce

Angela Krstic; Kwang-Ting Cheng

1996-01-01

474

Backup Path Re-optimizations for Shared Path Protection in Multi-domain Networks

Within the context of dynamic routing models for shared path protection in multi-domain networks, we propose a backup path re-optimization phase with possible rerouting of the existing backup paths in order to increase the bandwidth sharing among them while minimizing the network backup cost. The re- optimization phase is activated periodically or when routing a new connection fails because of

B. Jaumard; T. Dieu Linh Truong

2006-01-01

475

Energetic Path Finding Across Massive Terrain Data

Energetic Path Finding Across Massive Terrain Data Andrew Tsui and ZoÂ¨e Wood California Polytechnic of this work include: Â Tools for managing and performing energetic analysis on massive out-of- core datasets builds on two previous projects involving human centered paths across terrain data, Energetic Analyst [5

Wood, ZoÃ« J.

476

Career path of a corruption entrepreneur

The study of criminal career paths is necessary to understand the methods of success employed by high-performing criminals. The aim of this article is to focus on the career path of Jack Herbert who set up and maintained extensive corruption networks between organised crime groups and police in the Australian state of Queensland. This study builds on Morselli's work on

Mark Lauchs; Zoe Staines

2012-01-01

477

A Random Walk on a Circular Path

ERIC Educational Resources Information Center

This short note introduces an interesting random walk on a circular path with cards of numbers. By using high school probability theory, it is proved that under some assumptions on the number of cards, the probability that a walker will return to a fixed position will tend to one as the length of the circular path tends to infinity.

Ching, W.-K.; Lee, M. S.

2005-01-01

478

Asymmetric fluctuation relaxation paths in FPU models

NASA Astrophysics Data System (ADS)

A recent theory by Bertini, De Sole, Gabrielli, Jona-Lasinio and Landim predicts a temporal asymmetry in the fluctuation-relaxation paths of certain observables of nonequilibrium systems in local thermodynamic equilibrium. We find temporal asymmetries in the fluctuation-relaxation paths of a form of local heat flow, in the nonequilibrium FPU- ? model of Lepri, Livi and Politi.

Giberti, C.; Rondoni, L.; Vernia, C.

2006-06-01

479

Finding Regular Simple Paths in Graph Databases

We consider the following problem: given a labelled directed graph and a regular expression , find all pairs of nodes connected by a simple path such that theconcatenation of the labels along the path satisfies . The problem is motivated by the observation that many recursive queries in relational databases can be expressed in this form, and by the implementation

Alberto O. Mendelzon; Peter T. Wood

1989-01-01

480

Adaptively Ubiquitous Learning in Campus Math Path

ERIC Educational Resources Information Center

The purposes of this study are to develop and evaluate the instructional model and learning system which integrate ubiquitous learning, computerized adaptive diagnostic testing system and campus math path learning. The researcher first creates a ubiquitous learning environment which is called "adaptive U-learning math path system". This system…

Shih, Shu-Chuan; Kuo, Bor-Chen; Liu, Yu-Lung

2012-01-01

481

Katrina'sPath Lake Pontchartrain

'sPath Katrina's Storm Surge #12;Now Scenario Hurricane Toufectis Â· Approaches from the ESE, traveling WNW Â· SSC to Katrina #12;Gotwals'Path Now Scenario Hurricane Gotwals Â· Katrina is as Katrina was Â· Storm track moved 4 Hurricane Horton Â· Katrina is as Katrina was Â· Adding roughly 10" sea level rise (25cm) Impacts Â· Similar

482

Improved methods for path integral Monte Carlo integration in fermionic systems

NASA Astrophysics Data System (ADS)

We generalize the discretized Feynman path integral expansion by replacing the path through pure states with a path through idempotent density matrices. The transformed expression converges to the ordinary path integral, but is computationally more flexible than the ordinary form. By introducing a particular choice of these idempotent density matrices, based on rotational averaging around the two-particle center of mass, we greatly reduce the sign problem for systems of two fermions in three dimensions. In the ordinary path integral Monte Carlo approach, low temperature simulation of fermions is inefficient as the integral decays exponentially faster than the integrand (and its variance) as the temperature decreases. The new rotationally averaged algorithm dramatically retards this relative decay. Fermionic simulations of the model system of Kestner and Sinanoglu, and of the harmonic oscillator, demonstrate this improvement, as integrals calculated at temperatures much lower than the singlet-triplet splitting display negligible decay of the desired averages relative to the partition function of the modified path ensemble.

Newman, William H.; Kuki, Atsuo

1992-01-01

483

Ranking paths in statistical energy analysis models with non-deterministic loss factors

NASA Astrophysics Data System (ADS)

Finding the contributions of transmission paths in statistical energy analysis (SEA) models has become an established valuable tool to detect and remedy vibro-acoustic problems. Paths are identified in SEA according to Craik's definition and recently, very efficient methods have been derived to rank them in the framework of graph theory. However, up to date classification schemes have only considered the mean values of loss factors for path comparison, their variance being ignored. This can result in significant errors in the final results. In this work it is proposed to address this problem by defining stochastic biparametric SEA graphs whose edges are assigned both, mean and variance values. Paths between subsystems are then compared according to a proposed cost function that accounts for the stochastic nature of loss factors. For an efficacious ranking of paths, the stochastic SEA graph is converted to an extended deterministic SEA graph where fast classification deterministic algorithms can be applied. The importance of nonneglecting the influence of the variance in path ranking is illustrated by means of some academic numerical examples.

Aragonès, Àngels; Guasch, Oriol

2015-02-01

484

Improving the Quality of Non-Holonomic Motion by Hybridizing C-PRM Paths

Sampling-based motion planners are an effective means for generating collision-free motion paths. However, the quality of these motion paths, with respect to different quality measures such as path length, clearance, smoothness or energy, is often notoriously low. This problem is accentuated in the case of non-holonomic sampling-based motion planning, in which the space of feasible motion trajectories is restricted. In this study, we combine the C-PRM algorithm by Song and Amato with our recently introduced path-hybridization approach, for creating high quality non-holonomic motion paths, with combinations of several different quality measures such as path length, smoothness or clearance, as well as the number of reverse car motions. Our implementation includes a variety of code optimizations that result in nearly real-time performance, and which we believe can be extended with further optimizations to a real-time tool for the planning of high-quality car-like motion.

Berger, Itamar; Zohar, Gal; Raveh, Barak; Halperin, Dan

2010-01-01

485

Distributed Algorithms for Multicommodity Flow Problems via Approximate Steepest Descent Framework

Distributed Algorithms for Multicommodity Flow Problems via Approximate Steepest Descent Framework Baruch Awerbuch Rohit Khandekar Satish Rao Abstract We consider solutions for distributed multicommodity dimensionality. One classical ex- ample is multicommodity flow: there is an exponential number of paths, yet

Amir, Yair

486

ÂMover Distance . Conclusions and Resources #12; 6 Very Brief History of Embeddings . [Frechet, 1909]: Any metric) -- Technique: generalization of Frechet -- Proof gives a randomized O(n 2 log 2 n) algorithm [Linial Proof . We map f(u)=Au=[a 1 *u,...,a d' *u] , where each entry of A has normal distribution . Need

487