Note: This page contains sample records for the topic shortest path algorithm from Science.gov.
While these samples are representative of the content of Science.gov,
they are not comprehensive nor are they the most current set.
We encourage you to perform a real-time search of Science.gov
to obtain the most current and comprehensive results.
Last update: November 12, 2013.
1

Shortest path algorithms  

Microsoft Academic Search

Theshortest path problem is considered from a computational point of view. Eight algorithms which solve theshortest path tree problem on directed graphs are presented, together with the results of wide-ranging experimentation designed to compare their relative performances on different graph topologies. The focus of this paper is on the implementation of the different data structures used in the algorithms. A

Giorgio Gallo; Stefano Pallottino

1988-01-01

2

Shortest paths algorithms: theory and experimental evaluation  

Microsoft Academic Search

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

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

1994-01-01

3

Faster algorithms for the shortest path problem  

Microsoft Academic Search

Efficient implementations of Dijkstra's shortest path algorithm are investigated. A new data structure, called the radix heap, is proposed for use in this algorithm. On a network with n vertices, m edges, and nonnegative integer arc costs bounded by C, a one-level form of radix heap gives a time bound for Dijkstra's algorithm of O(m + n log C). A

Ravindra K. Ahuja; Kurt Mehlhorn; James B. Orlin; Robert Endre Tarjan

1990-01-01

4

An Improved Shortest Path Algorithm for Computing One-to-One Shortest Paths on Road Networks  

Microsoft Academic Search

Computing one-to-one shortest paths on road networks is a fundamental work in many practical applications, especially in network and transportation related analyses. Pallottino's graph growth algorithm implemented with two queues (TWO-Q) is recommended as one of the top candidates to this kind of problems in literature. However, as a label-correcting shortest path algorithm, original TWO-Q algorithm begins scan from the

JinFu Leng; Wen Zeng

2009-01-01

5

Shortest path algorithm based on city emergency system  

Microsoft Academic Search

It requires that the savers get to the spot with the quickest speed when the accidents take place in the City Emergency System, therefore the Shortest Path problem is one of the pivotal technology to satisfy the system. This paper put forward a real-time and effective algorithm realization of Shortest Path, according to the characteristics of City Emergency System, taking

Gui-Qin Dou; Yan-Song Zhu; Yu-Min Han

2011-01-01

6

I\\/O-Efficiency of Shortest Path Algorithms: An Analysis  

Microsoft Academic Search

To establish the behavior of algorithms in a paging environment, the author analyzes the input\\/output (I\\/O) efficiency of several representative shortest path algorithms. These algorithms include single-course, multisource, and all pairs ones. The results are also applicable for other path problems such as longest paths, most reliable paths, and bill of materials. The author introduces the notation and a model

Bin Jiang; ETH Zurich

1992-01-01

7

Efficient Algorithms for Shortest Paths in Sparse Networks  

Microsoft Academic Search

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

Donald B. Johnson

1977-01-01

8

Average Network Flow Problem: Shortest Path and Minimum Cost Flow Formulations, Algorithms, Heuristics, and Complexity.  

National Technical Information Service (NTIS)

Integrating value focused thinking with the shortest path problem results in a unique formulation called the multiobjective average shortest path problem. We prove this is NP-complete for general graphs. For directed acyclic graphs, an efficient algorithm...

J. D. Jordan

2012-01-01

9

Dynamic behavior of shortest path routing algorithms for communication networks  

NASA Astrophysics Data System (ADS)

Several proposed routing algorithms for store and forward communication networks, including one currently in operation in the ARPANET, route messages along shortest paths computed by using some set of link lengths. When these lengths depend on current traffic conditions as they must in an adaptive algorithm, dynamic behavior questions such as stability convergence, and speed of convergence are of interest. This paper is the first attempt to analyze systematically these issues. It is shown that minimum queuing delay path algorithms tend to exhibit violent oscillatory behavior in the absence of a damping mechanism. The oscillations can be damped by means of several types of schemes, two of which are analyzed in this paper. In the first scheme a constant bias is added to the queuing delay thereby providing a preference towards paths with a small number of links. In the second scheme the effects of several past routings are averaged as, for example, when the link lengths are computed and communicated asynchronously throughout the network.

Bertsekas, D. P.

1980-06-01

10

Algorithm for shortest path search in Geographic Information Systems by using reduced graphs.  

PubMed

The use of Geographic Information Systems has increased considerably since the eighties and nineties. As one of their most demanding applications we can mention shortest paths search. Several studies about shortest path search show the feasibility of using graphs for this purpose. Dijkstra's algorithm is one of the classic shortest path search algorithms. This algorithm is not well suited for shortest path search in large graphs. This is the reason why various modifications to Dijkstra's algorithm have been proposed by several authors using heuristics to reduce the run time of shortest path search. One of the most used heuristic algorithms is the A* algorithm, the main goal is to reduce the run time by reducing the search space. This article proposes a modification of Dijkstra's shortest path search algorithm in reduced graphs. It shows that the cost of the path found in this work, is equal to the cost of the path found using Dijkstra's algorithm in the original graph. The results of finding the shortest path, applying the proposed algorithm, Dijkstra's algorithm and A* algorithm, are compared. This comparison shows that, by applying the approach proposed, it is possible to obtain the optimal path in a similar or even in less time than when using heuristic algorithms. PMID:24010024

Rodríguez-Puente, Rafael; Lazo-Cortés, Manuel S

2013-07-01

11

Greedy partitioned algorithms for the shortest-path problem  

SciTech Connect

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

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

1991-08-01

12

A distributed shortest path protocol  

NASA Astrophysics Data System (ADS)

We present a distributed protocol for obtaining the shortest paths between all pairs of nodes in a network with weighted links. The protocol is based on an extension of the Dijkstra (centralized) shortest path algorithm and uses collaboration between neighboring nodes to transfer the information needed at the nodes for the successive construction of the shortest paths. A formal description of the protocol is given by indicating the exact algorithm performed by each node. The validation proofs are greatly simplified by separating the communication mechanism from the computation at the nodes, the latter being the transposition of the Dijkstra shortest path algorithm to the decentralized protocol.

Zerbib, F. B. M.; Segall, A.

1981-06-01

13

Linear-Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons  

Microsoft Academic Search

Given a triangulation of a simple polygonP, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility withinP. These problems include calculation of the collection of all shortest paths insideP from a given source vertexS to all the other vertices ofP, calculation of the subpolygon ofP consisting of points that are visible from a given

Leonidas J. Guibas; John Hershberger; Daniel Leven; Micha Sharir; Robert Endre Tarjan

1987-01-01

14

A genetic algorithm for shortest path routing problem and the sizing of populations  

Microsoft Academic Search

This paper presents a genetic algorithmic approach to the shortest path (SP) routing problem. Variable-length chromosomes (strings) and their genes (parameters) have been used for encoding the problem. The crossover operation exchanges partial chromosomes (partial routes) at positionally independent crossing sites and the mutation operation maintains the genetic diversity of the population. The proposed algorithm can cure all the infeasible

Chang Wook Ahn; Rudrapatna S. Ramakrishna

2002-01-01

15

a Shortest Path Algorithm for a Network with Various Fuzzy Arc Lengths  

NASA Astrophysics Data System (ADS)

We are concerned with the design of a model and an algorithm for computing a shortest path in a network having various types of fuzzy arc lengths. First, we develop a new technique for the addition of various fuzzy numbers in a path using ? -cuts. Then, we propose a regression model for obtaining membership function for the considered addition. Finally, we present a dynamic programming method for finding a shortest path in the network. An example is worked out to illustrate the applicability of the proposed approach.

Tajdin, Ali; Mahdavi, Iraj; Mahdavi-Amiri, Nezam; Sadeghpour-Gildeh, Bahram; Hadighi, Rofideh

2010-06-01

16

Linear time algorithms for visibility and shortest path problems inside simple polygons  

Microsoft Academic Search

We present linear time algorithms for solving the following problems involving a simple planar polygon P: (i) Computing the collection of all shortest paths inside P from a given source vertex s to all the other vertices of P; (ii) Computing the subpolygon of P consisting of points that are visible from a segment within P; (iii) Preprocessing P so

Leonidas J. Guibas; John Hershberger; Daniel Leven; Micha Sharir; Robert Endre Tarjan

1986-01-01

17

Fighting organized crimes: using shortest-path algorithms to identify associations in criminal networks  

Microsoft Academic Search

Effective and efficient link analysis techniques are needed to help law enforcement and intelligence agencies fight organized crimes such as narcotics violation, terrorism, and kidnapping. In this paper, we propose a link analysis technique that uses shortest-path algorithms, priority-first-search (PFS) and two-tree PFS, to identify the strongest association paths between entities in a criminal network. To evaluate effectiveness, we compared

Jennifer Jie Xu; Hsinchun Chen

2004-01-01

18

Genetic Algorithm for Solving Fuzzy Shortest Path Problem in a Network with mixed fuzzy arc lengths  

NASA Astrophysics Data System (ADS)

We are concerned with the design of a model and an algorithm for computing a shortest path in a network having various types of fuzzy arc lengths. First, we develop a new technique for the addition of various fuzzy numbers in a path using ? -cuts by proposing a linear least squares model to obtain membership functions for the considered additions. Then, using a recently proposed distance function for comparison of fuzzy numbers. we propose a new approach to solve the fuzzy APSPP using of genetic algorithm. Examples are worked out to illustrate the applicability of the proposed model.

Mahdavi, Iraj; Tajdin, Ali; Hassanzadeh, Reza; Mahdavi-Amiri, Nezam; Shafieian, Hosna

2011-06-01

19

An Improved Ant Colony Algorithm for the Shortest Path Problem in Time-Dependent Networks  

NASA Astrophysics Data System (ADS)

Research of the shortest path problem in time-dependent networks has important practical value. An improved pheromone update strategy suitable for time-dependent networks was proposed. Under this strategy, the residual pheromone of each road can accurately reflect the change of weighted value of each road. An improved selection strategy between adjacent cities was used to compute the cities' transfer probabilities, as a result, the amount of calculation is greatly reduced. To avoid the algorithm converging to the local optimal solution, the ant colony algorithm was combined with genetic algorithm. In this way, the solutions after each traversal were used as the initial species to carry out single-point crossover. An improved ant colony algorithm for the shortest path problem in time-dependent networks based on these improved strategies was presented. The simulation results show that the improved algorithm has greater probability to get the global optimal solution, and the convergence rate of algorithm is better than traditional ant colony algorithm.

Chang, Qing; Liu, Yongqiang; Xiong, Huagang

20

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

SciTech Connect

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

21

Physarum can compute shortest paths.  

PubMed

Physarum polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model has been proposed by Tero et al. (Journal of Theoretical Biology, 244, 2007, pp. 553-564) to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foraging two food sources s(0) and s(1). We prove that, under this model, the mass of the mold will eventually converge to the shortest s(0)-s(1) path of the network that the mold lies on, independently of the structure of the network or of the initial mass distribution. This matches the experimental observations by Tero et al. and can be seen as an example of a "natural algorithm", that is, an algorithm developed by evolution over millions of years. PMID:22732274

Bonifaci, Vincenzo; Mehlhorn, Kurt; Varma, Girish

2012-06-23

22

A New Algorithm for Finding the Shortest Path Tree Using Competitive Pulse Coupled Neural Network  

Microsoft Academic Search

The competitive pulse coupled neural network (CPCNN) model is proposed based on the pulse coupled neural network (PCNN), the\\u000a properties of pulse wave propagation of the CPCNN are analyzed for the solution of network shortest routing. The setting terms\\u000a of the neuron parameters for the pulse wave propagation along the routing of the shortest path tree (SPT) of network routing

Dongming Zhou; Rencan Nie; Dongfeng Zhao

2008-01-01

23

Efficient computation of geodesic shortest paths  

Microsoft Academic Search

This paper describes an ecient algorithm for the geodesic shortest path problem, i.e. the problemof nding shortest paths between pairs of points on the surface of a 3-dimensional polyhedron suchthat the path is constrained to lie on the surface of the polyhedron. We use the wavefront methodand show an O(nlog2n) time bound for this problem, when there are O(n) vertices

Sanjiv Kapoor; Hauz Khan

1999-01-01

24

A Shortest Path Processor for Traffic Engineering of VPN Services  

Microsoft Academic Search

The shortest path problem is common in many different fields (transportation systems, mechanical systems, etc). Most of the telecommunication industry protocols such as PNNI, OSPF and IISP use Dijkstra's algorithm or Bellman-Ford's algorithm to solve the shortest path problem. Today, the majority of the shortest path computations are performed in software, which is inefficient for real-time applications that are sensitive

Mohamed Abou-Gabal; Raymond Peterkin; Dan Ionescu; C. Lambiri; Voicu Groza

25

Shortest paths in synchronized traffic-light networks  

Microsoft Academic Search

The time-constrained shortest path problem is an important generalization of the shortest path problem. The basic feature in time-constrained shortest path problem is considering when a node in the network can be visited under some time constraints. In this paper, a label-setting shortest path algorithm will be proposed to use in the synchronized traffic-light networks which uses the waiting times

Mohammad Khanjary; Karim Faez; Mohammad Reza Meybodi; Masoud Sabaei

2011-01-01

26

Approximate Euclidean shortest path in 3-space  

Microsoft Academic Search

Papadimitriou's approximation approach to the Euclidean shortest path (ESP) problem in 3-space is revisited. As this problem is NP-hard, his approach represents an important step towards practical algorithms. Unfortunately, there are non-trivial gaps in the original description. Besides giving a complete treatment, we also give an alternative to his subdivision method which has some nice properties. Among the tools needed

Joonsoo Choi; Jürgen Sellen; Chee-Keng Yap

1994-01-01

27

k-Link Shortest Paths in Weighted Subdivisions  

Microsoft Academic Search

We study the shortest path problem in weighted polygonal subdivisions of the plane, with the additional constraint of an upper bound, k, on the number of links (segments) in the path. We prove structural properties of optimal paths and utilize these results to ob- tain approximation algorithms that yield a path having O(k) links and weighted length at most (1

Ovidiu Daescu; Joseph S. B. Mitchell; Simeon C. Ntafos; James D. Palmer; Chee-keng Yap

2005-01-01

28

Shortest path based splitting line finding for touching cells  

NASA Astrophysics Data System (ADS)

A shortest path based algorithm is proposed in this paper to find splitting lines for touching cells. Firstly, an initial splitting line is obtained through the distance transform of a marker image and the watershed algorithm. Then, the initial splitting line is separated into different line segments if necessary, and the start and end points of these line segments act as the start and end points of shortest path. Finally, the shortest path algorithm is used to find the splitting line between the start and end points, and the final result of touching cells splitting can be formed by the contour of the touching cells and the splitting lines. Experimental results show that the proposed algorithm is efficient for different types of touching cells.

Bai, Xiangzhi; Sun, Changming; Wang, Peng; Zhou, Fugen

2013-10-01

29

Fuzzy shortest path problems incorporating interactivity among paths  

Microsoft Academic Search

This paper deals with a shortest path problem on a network in which a fuzzy number, instead of a real number, is assigned to each arc length. Such a problem is “ill-posed” because each arc cannot be identified as being either on the shortest path or not. Therefore, based on the possibility theory, we introduce the concept of “degree of

Shinkoh Okada

2004-01-01

30

Computing Point-to-Point Shortest Paths from External Memory  

Microsoft Academic Search

We study the ALT algorithm (19) for the point-to-point shortest path problem in the context of road networks. We suggest improvements to the algorithm itself and to its preprocessing stage. We also develop a memory-ecien t implementation of the algorithm that runs on a Pocket PC. It stores graph data in a ash memory card and uses RAM to store

Andrew V. Goldberg; Renato Fonseca F. Werneck

2005-01-01

31

Wavelength Conversion in Shortest-Path All-Optical Networks  

Microsoft Academic Search

We consider all-optical networks with shortest-path routing that use wavelength- division multiplexing and employ wavelength conversion at specic nodes in order to maximize their capacity usage. We present ecien t algorithms for deciding whether a placement of wavelength converters allows the network to run at maximum capacity, and for nding an optimal wavelength assignment when such a placement of con-

Thomas Erlebach; Stamatis Stefanakos

2003-01-01

32

Shortest path ray tracing with sparse graphs  

SciTech Connect

A technique for improving the efficiency of shortest path ray tracing (SPR) is presented. The authors analyze situations where SPR fails and provide quantitative measures to assess the performance of SPR ray tracing with varying numbers of nodes. Their improvements include perturbing the ray at interfaces according to Snell's Law, and a method to find correct rays efficiently in regions of low velocity contract. This approach allows the investigator to use fewer nodes in the calculation, thereby increasing the computational efficiency. In two-dimensional (2-D) cross-borehole experiments they find that with their improvements, they need only use 2/3 as many nodes, saving up to 60 percent in time. Savings should be even greater in three dimensions. These improvements make SPR more attractive for tomographic applications in three dimensions.

Fischer, R.; Lees, J.M. (Yale Univ., New Haven, CT (United States). Dept. of Geology and Geophysics)

1993-07-01

33

Shortest paths synthesis for a car-like robot  

Microsoft Academic Search

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

P. Soueres; J.-P. Laumond

1996-01-01

34

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

NASA Astrophysics Data System (ADS)

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

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

2013-09-01

35

Fast and accurate estimation of shortest paths in large graphs  

Microsoft Academic Search

Computing shortest paths between two given nodes is a fundamental operation over graphs, but known to be nontrivial over large disk-resident instances of graph data. While a number of techniques exist for answering reachability queries and approximating node distances efficiently, determining actual shortest paths (i.e. the sequence of nodes involved) is often neglected. However, in applications arising in massive online

Andrey Gubichev; Srikanta J. Bedathur; Stephan Seufert; Gerhard Weikum

2010-01-01

36

Weight functions for shortest path routing of periodically scheduled burst flows  

Microsoft Academic Search

We investgate weighted shortest path routing mechanisms based on Dijkstra’s algorithm to find optimal paths for periodically scheduled burst flows in optical burst switching networks. Our objective is to reduce the flow blocking rate. We propose three dynamic weight functions to estimate the path level flow blocking probability based on wavelength utilization. We evaluate the performance of these weight functions

Li Lei; Srinivas Sampalli

2007-01-01

37

Ports Logistics Cost Optimization with Linear Transportation Cost Function and Shortest Path  

Microsoft Academic Search

Suppose the goods transported in accordance with the shortest path and transportation fixed cost considered in land and sea transport system, the sea and land transport problem is analyzed. And then, mathematical models are established and corresponding algorithm is proposed. The algorithm complex degree is. Furthermore, a computational example is offered to demonstrate the steps and effectiveness of the algorithm.

Cui Wanan; Wei Bin

2011-01-01

38

Distributional properties of stochastic shortest paths for smuggled nuclear material  

SciTech Connect

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

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

2011-01-05

39

Optimal shortest path queries in a simple polygon  

Microsoft Academic Search

Let P be a simple polygon with n sides. This paper shows how to preprocess the polygon so that, given two query points p and q inside P, the length of the shortest path inside the polygon from p to q can be found in time &Ogr;(log n). The path itself must be polygonal and can be extracted in additional

Leonidas J. Guibas; John Hershberger

1987-01-01

40

Multicast Routing in Wireless Mesh Networks: Minimum Cost Trees or Shortest Path Trees?  

Microsoft Academic Search

There exist two fundamental approaches to multicast routing: shortest path trees (SPTs) and minimum cost trees (MCTs). The SPT algorithms minimize the distance (or cost) from the sender to each receiver, whereas the MCT algorithms minimize the overall cost of the multicast tree. Due to the very large scale and unknown topology of the Internet, computing MCTs for multicast routing

Uyen Trang Nguyen; Jin Xu

2007-01-01

41

Visibility-Graph-Based Shortest-Path Geographic Routing in Sensor Networks  

Microsoft Academic Search

We study the problem of shortest-path geographic routing in a static sensor network. Existing algorithms often make routing decisions based on node information in local neighborhoods. However, it is shown by Kuhn et al. that such a design constraint results in a highly undesirable lower bound for routing performance: if a best route has length c ,t hen in the

Guang Tan; Marin Bertier; Anne-Marie Kermarrec

2009-01-01

42

Optimal Shortest Path Queries in a Simple Polygon  

Microsoft Academic Search

Abstract Let P be a simple polygon with n sides. This paper shows how to preprocess,the polygon so that, given two query points p and q inside P, the length of the shortest,path,inside the polygon($#$to q can be found,in time,O(Iogn). The path,itself must,be polygonal and can be extracted,in additional,time proportional,to the number,of turns,it makes.,The preprocessing consists of triangulation,plus a linear

Leonidas J. Guibas; John Hershberger

1989-01-01

43

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

SciTech Connect

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

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

1992-07-14

44

A Graph Search Heuristic for Shortest Distance Paths  

SciTech Connect

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

Chow, E

2005-03-24

45

Curvature-Constrained Shortest Paths in a Convex Polygon  

Microsoft Academic Search

Let be a point robot moving in the plane, whose path is con- strained to have curvature at most , and let be a convex polygon with vertices. We study the collision-free, optimal path-plann ing problem for moving between two configurations inside (a con- figuration specifies both a location and a direction of travel ). We present an time algorithm

Pankaj K. Agarwal; Therese C. Biedl; Sylvain Lazard; Steve Robbins; Subhash Suri; Sue Whitesides

2002-01-01

46

KSPTH: A Subroutine for the K Shortest Paths in a Sabotage Graph.  

National Technical Information Service (NTIS)

Finding shortest paths in a weighted graph model is one way for a safeguards analyst to locate weaknesses in a facility's barrier and alarm system. KSPTH can be used to rank sabotage paths according to path length so that the K shortest paths can be studi...

B. L. Hulme D. B. Holdridge

1977-01-01

47

Membrane Boundary Extraction Using a Circular Shortest Path Technique  

NASA Astrophysics Data System (ADS)

Membrane proteins represent over 50% of known drug targets. Accordingly, several widely used assays in the High Content Analysis area rely on quantitative measures of the translocation of proteins between intracellular organelles and the cell surface. In order to increase the sensitivity of these assays, one needs to measure the signal specifically along the membrane, requiring a precise segmentation of this compartment. Doing this manually is a very time-consuming practice, limited to an academic setting. Manual tracing of the membrane compartment also confronts us with issues of objectivity and reproducibility. In this paper, we present an approach based on a circular shortest path technique that enables us to segment the membrane compartment accurately and rapidly. This feature is illustrated using cells expressing epitope-tagged membrane proteins.

Sun, Changming; Vallotton, Pascal; Wang, Dadong; Lopez, Jamie; Ng, Yvonne; James, David

2007-11-01

48

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

PubMed

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

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

2012-10-23

49

Fast shortest path computation in time-dependent traffic networks  

Microsoft Academic Search

In agent based traffic simulations which use systematic relaxation to reach a steady state of the scenario, the performance of the routing algorithm used for finding a path from a start node to an end node in the network is crucial for the overall performance. For example, a systematic re- laxation process for a large scale scenario with about 7.5

Nicolas Lefebvre; ETH Zurich; Michael Balmer

2007-01-01

50

Shortest Paths in a Digitized Map Using a Tile-Based Data Structure,  

National Technical Information Service (NTIS)

The problem addressed here is that of finding the shortest paths between two points within a digitized map. The map contains obstacles which may not be traversed. For this reason, the problem statement is analogous to that of finding shortest paths within...

P. Holmes E. Jungert

1988-01-01

51

Wavelength Conversion in All-Optical Networks with Shortest-Path Routing  

Microsoft Academic Search

We consider all-optical networks with shortest-path routing \\u000a that use wavelength-division multiplexing\\u000a and employ wavelength conversion at specific nodes in order to maximize \\u000a their capacity usage. We present efficient algorithms for deciding whether\\u000a a placement of wavelength converters allows the network to run at maximum\\u000a capacity,\\u000a and for finding an optimal wavelength assignment when such a placement\\u000a of converters is\\u000a known.

Thomas Erlebach; Stamatis Stefanakos

2005-01-01

52

A Linear-Time Algorithm for Finding Approximate Shortest Common Superstrings  

Microsoft Academic Search

Approximate shortest common superstrings for a given setR of strings can be constructed by applying the greedy heuristics for finding a longest Hamiltonian path in the weighted graph\\u000a that represents the pairwise overlaps between the strings inR. We develop an efficient implementation of this idea using a modified Aho-Corasick string-matching automaton. The resulting\\u000a common superstring algorithm runs in timeO(n) or

Esko Ukkonen

1990-01-01

53

Tubule detection in testis images using boundary weighting and circular shortest path.  

PubMed

In studies of germ cell transplantation, measureing tubule diameters and counting cells from different populations using antibodies as markers are very important. Manual measurement of tubule sizes and cell counts is a tedious and sanity grinding work. In this paper, we propose a new boundary weighting based tubule detection method. We first enhance the linear features of the input image and detect the approximate centers of tubules. Next, a boundary weighting transform is applied to the polar transformed image of each tubule region and a circular shortest path is used for the boundary detection. Then, ellipse fitting is carried out for tubule selection and measurement. The algorithm has been tested on a dataset consisting of 20 images, each having about 20 tubules. Experiments show that the detection results of our algorithm are very close to the results obtained manually. PMID:24110438

Zhang, Chao; Sun, Changming; Davey, Rhonda; Su, Ran; Bischof, Leanne; Vallotton, Pascal; Lovell, David; Hope, Shelly; Lehnert, Sigrid; Pham, Tuan D

2013-07-01

54

Application of the Ant Colony Algorithm for the Path Planning  

Microsoft Academic Search

The paper presents the ant colony algorithm and its application for the path planning. Ant algorithms were designed on the base of the behaviour of real ant colonies. Real ants can always find the shortest way between the nest and the food so one of the most “natural” is the application of the ant colony algorithm in the path planning.

Marcin Pluci?ski

55

The shortest path and spatial decision support system implementation in the context of parcel delivery  

Microsoft Academic Search

The shortest path decision-making had been proved to be critical to a parcel delivery business. This paper first introduces a modular decision support framework, which based on the small and medium enterprise's delivery operation model. It then proposes a Demand-Scheduling-Delivering process chain incorporate the shortest path analysis and decision as its central components. A pilot decision support system for intra-city

Xintong Li; Feng Peng

2010-01-01

56

Snell's law and light traveling along the shortest path  

Microsoft Academic Search

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

Carlos Lara

2006-01-01

57

Shortest Paths in Euclidean Space with Polyhedral Obstacles.  

National Technical Information Service (NTIS)

This document considers the problem of finding a minimum length path between two points in Euclidean space which avoids a set (not necessarily convex) polyhedral obstacles; we let n denote the number of the obstacle edges and k denote the number of island...

J. H. Reif J. A. Storer

1985-01-01

58

NP-Completeness Results for All-Shortest-Path Interval Routing  

Microsoft Academic Search

\\u000a \\u000a k-Interval Routing Scheme (k-IRS) is a compact routing method that allows up to k interval labels to be assigned to an arc. A fundamental problem is to characterize the networks that admit k-IRS. Many of the problems related to single-shortest-path k-IRS have already been shown to be NP-complete. For all-shortest-path k-IRS, the characterization problem remains open for k? 1. We

Rui Wang; Francis C. M. Lau; Yan Yan Liu

2004-01-01

59

The approach for shortest paths in fire succor based on component GIS technology  

NASA Astrophysics Data System (ADS)

Fire safety is an important issue for the national economy and people's living. Efficiency and exactness of fire department succor directly relate to safety of peoples' lives and property. Many disadvantages of the traditional fire system have been emerged in practical applications. The preparation of pumpers is guided by wireless communication or wire communication, so its real-time and accurate performances are much poorer. The information about the reported fire, such as the position, disaster and map, et al., for alarm and command was processed by persons, which slows the reaction speed and delays the combat opportunity. In order to solve these disadvantages, it has an important role to construct a modern fire command center based on high technology. The construction of modern fire command center can realize the modernization and automation of fire command and management. It will play a great role in protecting safety of peoples' lives and property. The center can enhance battle ability and can reduce the direct and indirect loss of fire damage at most. With the development of science technology, Geographic Information System (GIS) has becoming a new information industry for hardware production, software development, data collection, space analysis and counseling. With the popularization of computers and the development of GIS, GIS has gained increasing broad applications for its strong functionality. Network analysis is one of the most important functions of GIS, and the most elementary and pivotal issue of network analysis is the calculation of shortest paths. The shortest paths are mostly applied to some emergent systems such as 119 fire alarms. These systems mainly require that the computation time of the optimal path should be 1-3 seconds. And during traveling, the next running path of the vehicles should be calculated in time. So the implement of the shortest paths must have a high efficiency. In this paper, the component GIS technology was applied to collect and record the data information (such as, the situation of this disaster, map and road status et al) of the reported fire firstly. The ant colony optimization was used to calculate the shortest path of fire succor secondly. The optimization results were sent to the pumpers, which can let pumpers choose the shortest paths intelligently and come to fire position with least time. The programming method for shortest paths is proposed in section 3. There are three parts in this section. The elementary framework of the proposed programming method is presented in part one. The systematic framework of GIS component is described in part two. The ant colony optimization employed is presented in part three. In section 4, a simple application instance was presented to demonstrate the proposed programming method. There are three parts in this section. The distributed Web application based on component GIS was described in part one. The optimization results without traffic constraint were presented in part two. The optimization results with traffic constraint were presented in part three. The contributions of this paper can be summarized as follows. (1) It proposed an effective approach for shortest paths in fire succor based on component GIS technology. This proposed approach can achieve the real-time decisions of shortest paths for fire succor. (2) It applied the ant colony optimization to implement the shortest path decision. The traffic information was considered in the shortest path decision using ant colony optimization. The final application instance suggests that the proposed approach is feasible, correct and valid.

Han, Jie; Zhao, Yong; Dai, K. W.

2007-08-01

60

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

NASA Astrophysics Data System (ADS)

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

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

2013-09-01

61

Comparison of k-shortest paths and maximum flow routing for network facility restoration  

Microsoft Academic Search

In the development of technologies for span failure restoration, a question arises about the restoration rerouting characteristics to be specified. In theory, maximal rerouting capacity is obtained with a maximum flow (Max Flow) criterion. However, rerouting that realizes the k-successively shortest link disjoint paths (KSP) may be faster, easier, and, in distributed implementation, more robust than a distributed counterpart for

D. Anthony Dunn; Wayne D. Grover; Mike H. MacGregor

1994-01-01

62

Heterogeneity-aware shortest path routing: flow holding time, user demand and network state  

Microsoft Academic Search

We investigate possible performance improvements by exploring heterogeneity of traffic characteristics when designing a shortest path routing scheme. First we focus on the effect of the maintenance of the link metrics for connections with different holding times. We found that by using a differentiated routing scheme with respect to connection holding times, one can enhance network performance for a range

SHANCHIEH YANG; XUN SU; GUSTAVO DE VECIANA

2001-01-01

63

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

NASA Astrophysics Data System (ADS)

In this paper we present weighted Koch networks based on classic Koch networks. A new method is used to determine the average receiving time (ART), whose key step is to write the sum of mean first-passage times (MFPTs) for all nodes to absorption at the trap located at a hub node as a recursive relation. We show that the ART exhibits a sublinear or linear dependence on network order. Thus, the weighted Koch networks are more efficient than classic Koch networks in receiving information. Moreover, average weighted shortest path (AWSP) is calculated. In the infinite network order limit, the AWSP depends on the scaling factor. The weighted Koch network grows unbounded but with the logarithm of the network size, while the weighted shortest paths stay bounded.

Dai, Meifeng; Chen, Dandan; Dong, Yujuan; Liu, Jie

2012-12-01

64

Robot Group Formations: A Dynamic Programming Approach for a Shortest Path Computation  

Microsoft Academic Search

Rigid formations of mobile robots are to be used for special missions in which the task-execution requires a tight cooperation of all units in the group so as to constrain them to keep preassigned mutual distances. In the paper an algorithm for the optimal path-planning of rigid formations of mobile robots is considered for a case in which the path

Federico Gentili; Francesco Martinelli

2000-01-01

65

A shortest-path graph kernel for estimating gene product semantic similarity  

PubMed Central

Background Existing methods for calculating semantic similarity between gene products using the Gene Ontology (GO) often rely on external resources, which are not part of the ontology. Consequently, changes in these external resources like biased term distribution caused by shifting of hot research topics, will affect the calculation of semantic similarity. One way to avoid this problem is to use semantic methods that are "intrinsic" to the ontology, i.e. independent of external knowledge. Results We present a shortest-path graph kernel (spgk) method that relies exclusively on the GO and its structure. In spgk, a gene product is represented by an induced subgraph of the GO, which consists of all the GO terms annotating it. Then a shortest-path graph kernel is used to compute the similarity between two graphs. In a comprehensive evaluation using a benchmark dataset, spgk compares favorably with other methods that depend on external resources. Compared with simUI, a method that is also intrinsic to GO, spgk achieves slightly better results on the benchmark dataset. Statistical tests show that the improvement is significant when the resolution and EC similarity correlation coefficient are used to measure the performance, but is insignificant when the Pfam similarity correlation coefficient is used. Conclusions Spgk uses a graph kernel method in polynomial time to exploit the structure of the GO to calculate semantic similarity between gene products. It provides an alternative to both methods that use external resources and "intrinsic" methods with comparable performance.

2011-01-01

66

Structural properties of invasion percolation with and without trapping: Shortest path and distributions  

NASA Astrophysics Data System (ADS)

We study several structural properties including the shortest path l between two sites separated by a Euclidean distance r of invasion percolation with trapping (TIP) and without trapping (NIP). For the trapping case we find that the mass M scales with l as M~ldl with dl=1.510+/-0.005 and l scales with r as l~rdmin with dmin=1.213+/-0.005, whereas in the nontrapping case dl=1.671+/-0.006 and dmin=1.133+/-0.005. These values further support previous results that NIP and TIP are in distinct universality classes. We also study numerically using scaling approaches the distribution N(l,r) of the lengths of the shortest paths connecting two sites at distance r in NIP and TIP. We find that it obeys a scaling form N(l,r)~rdf-1-d minf(l/rdmin). The scaling function has a power-law tail for large x values, f(x)~x-h, with a universal value of h~2 for both models within our numerical accuracy.

Schwarzer, Stefan; Havlin, Shlomo; Bunde, Armin

1999-03-01

67

Freight Network Modeling System. Volume IV. Shortest-Path Analysis and Display user's guide  

SciTech Connect

The Freight Network Modeling System (FNEM) is a general and flexible modeling system designed to have wide applicability to a variety of freight transportation analyses. The system consists of compatible network data bases, data management software, models of freight transportation, report generators, and graphics output. In many studies, a model as comprehensive as FNEM is not required. The second model, Shortest-Path Analysis and Display (SPAD), is a simpler model that optimizes routings of single shipments. The routing criteria that can be used are numerous - including minimizing cost, minimizing delay, minimizing population exposure (useful when considering shipments of hazardous materials), and minimizing accident risk. In addition to the above criteria, the routes can also be restricted to those with clearance for oversized loads or with sufficient load capabilities. SPAD can be used interactively and the routes can be displayed graphically. This volume contains a user's guide for SPAD including preprocessor programs and SPAD execution. 7 figs., 19 tabs.

Not Available

1985-04-01

68

2-D/3-D irregular shortest-path ray tracing for multiple arrivals and its applications  

NASA Astrophysics Data System (ADS)

The purpose of this study is to introduce a multistage irregular shortest-path method (ISPM) for tracking multiple seismic arrivals including any combinations of transmissions, reflections (or refractions) and mode conversions in complex 2-D/3-D layered media, incorporating irregular interfaces (or subsurface in 3-D) and velocity discontinuities. The basic principle is to first divide the model into several different layers (using irregular cells near each interface, discontinuity and the Earth's undulating surface topography) and then to apply the multistage technique to trace the multiple arrivals. It is possible to realize the multiple arrival tracking with the multistage scheme because the multiple arrivals are just different combinations or conjugations of the simple incident, transmitted, reflected (or refracted) and mode converted waves via the velocity discontinuities and the interfaces. Benchmark tests against the popular multistage fast marching method (FMM) and the multistage MSPM (modified shortest path method) are undertaken to assess the solution accuracy and the computational efficiency. The results show that the multistage ISPM is advantageous over both the multistage FMM and the multistage MSPM in both solution accuracy and CPU time. Several examples (including the Marmousi model) are used to demonstrate the viability and versatility of the multistage ISPM in heterogeneous media, even in the presence of high-velocity contrasts involving interfaces of relatively high curvature. Applications to the seismological problems, such as traveltime tomography and earthquake location, indicate that it is possible to improve the spatial resolution in traveltime tomography and solution accuracy in earthquake location if later arrival information is combined with the first arrivals.

Bai, Chao-Ying; Huang, Guo-Jiao; Zhao, Rui

2010-12-01

69

Implementation and efficiency of Moore-algorithms for the shortest route problem  

Microsoft Academic Search

In the last 15 years, a good deal of effort has been devoted to the study of the shortest route problem. More than 200 publications are known but little has been reported concerning relative efficiencies. For a long time the Dijkstra method was considered the most efficient one. Programming work, using different data structures and implementation techniques for several algorithms,

U. Pape

1974-01-01

70

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

Microsoft Academic Search

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

J. Sussmann; Guoqing Tang

1991-01-01

71

Performance Analysis of Reactive Shortest Single-path and Multipath Routing Mechanism With Load Balance  

Microsoft Academic Search

Research on multi-path routing protocols to provideimproved throughput and route resilience as compared withsingle-path routing has been explored in details in the contextof wired networks. However, multi-path routing mechanism hasnot been explored thoroughly in the domain of ad hoc networks.In this paper, we analyze and compare reactive single-path andmulti-path routing with load balance mechanisms in ad hoc networks,in terms of

Peter P. Pham; Sylvie Perreau

2003-01-01

72

Underwater path planing using fast marching algorithms  

Microsoft Academic Search

In this paper, new tools for obstacle avoidance and path planning for underwater vehicles are presented. The authors' technique, based on a level set formulation of the path planning problem, extracts optimal paths from complex and continuous environments in a complete and consistent manner. Fast marching algorithm is known to be efficient for finding cost optimal path in mobile robotics

Clément Pêtrès; Yan Pailhast; Yvan Petilloti; Dave Lanes

2005-01-01

73

Constrained shortest link-disjoint paths selection: a network programming based approach  

Microsoft Academic Search

Given a graph G with each link in the graph associated with two positive weights, cost and delay, we consider the problem of selecting a set of k link-disjoint paths from a node s to another node t such that the total cost of these paths is minimum and that the total delay of these paths is not greater than

Ying Xiao; Krishnaiyan Thulasiraman; Guoliang Xue

2006-01-01

74

On Shortest-Path All-Optical Networks without Wavelength Conversion Requirements  

Microsoft Academic Search

In all-optical networks with wavelength division multiplexing, every connection is routed along a certain path and assigned a wavelength such that no two connections use the same wavelength on the same link. For a given set P of paths (a routing), let (P) denote the minimum number of wavelengths in a valid wavelength assignment and let L(P ) denote the

Thomas Erlebach; Stamatis Stefanakos

2003-01-01

75

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

PubMed Central

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

Gallardo, Jose E.

2012-01-01

76

Conflict-free shortest-time bidirectional AGV routeing  

Microsoft Academic Search

This paper presents an efficient algorithm for finding conflict-free shortest-time routes for automated guided vehicles moving in a bidirectional flow path network. The proposed algorithm is based on Dijkstra's shortest-path method. It maintains, for each node, a list of time windows reserved by scheduled vehicles and a list of free time windows available for vehicles to be scheduled. We introduce

CHANG W. KIM; J. M. A. TANCHOCO

1991-01-01

77

Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations  

Microsoft Academic Search

We give new methods for maintaining a data structure that supports ray shooting andshortest path queries in a dynamically-changing connected planar subdivision S. Our approachis based on a new dynamic method for maintaining a balanced decomposition of a simplepolygon via geodesic triangles. We maintain such triangulations by viewing their dual treesas balanced trees. We show that rotations in these trees

Michael T. Goodrich; Roberto Tamassia

1997-01-01

78

'Mini small worlds' of shortest link paths crossing domain boundaries in an academic Web space  

Microsoft Academic Search

Summary  Combining webometric and social network analytic approaches, this study developed a methodology to sample and identify Web\\u000a links, pages, and sites that function as small-world connectors affecting short link distances along link paths between different\\u000a topical domains in an academic Web space. The data set comprised 7669 subsites harvested from 109 UK universities. A novel\\u000a corona-shaped Web graph model revealed

Lennart Björneborn

2006-01-01

79

Path Planning Algorithms for Agricultural Machines  

Microsoft Academic Search

If the field plot shape is not rectangular and if it contains obstacles, the coverage path planning problem is hard to solve for a non-omnidirectional machine. Scientists have developed several algorithms to solve this coverage path planning problem, but all of them have pros and cons. If the machines were omnidirectional and turning times were decreased to insignificant, the problem

T. Oksanen; A. Visala

2007-01-01

80

Closing of interrupted vascular segmentations: an automatic approach based on shortest paths and level sets  

NASA Astrophysics Data System (ADS)

Exact segmentations of the cerebrovascular system are the basis for several medical applications, like preoperation planning, postoperative monitoring and medical research. Several automatic methods for the extraction of the vascular system have been proposed. These automatic approaches suffer from several problems. One of the major problems are interruptions in the vascular segmentation, especially in case of small vessels represented by low intensities. These breaks are problematic for the outcome of several applications e.g. FEM-simulations and quantitative vessel analysis. In this paper we propose an automatic post-processing method to connect broken vessel segmentations. The approach proposed consists of four steps. Based on an existing vessel segmentation the 3D-skeleton is computed first and used to detect the dead ends of the segmentation. In a following step possible connections between these dead ends are computed using a graph based approach based on the vesselness parameter image. After a consistency check is performed, the detected paths are used to obtain the final segmentation using a level set approach. The method proposed was validated using a synthetic dataset as well as two clinical datasets. The evaluation of the results yielded by the method proposed based on two Time-of-Flight MRA datasets showed that in mean 45 connections between dead ends per dataset were found. A quantitative comparison with semi-automatic segmentations by medical experts using the Dice coefficient revealed that a mean improvement of 0.0229 per dataset was achieved. In summary the approach presented can considerably improve the accuracy of vascular segmentations needed for following analysis steps.

Forkert, Nils Daniel; Schmidt-Richberg, Alexander; Säring, Dennis; Illies, Till; Fiehler, Jens; Handels, Heinz

2010-03-01

81

Identification of hepatocellular carcinoma related genes with k-th shortest paths in a protein-protein interaction network.  

PubMed

Hepatocellular carcinoma (HCC) is the most common type of liver cancer worldwide and one of the deadliest cancers in Asia. But at present, effective targets for HCC clinical therapy are still limited. The "guilt by association" rule suggests that interacting proteins share the same or similar functions and hence may be involved in the same pathway. This assumption can be used to identify disease related genes from protein association networks constructed from existing PPI data. Given the close association between Hepatitis B virus and Hepatitis B which may lead to HCC, here we develop a computational method to identify hepatocellular carcinoma related genes based on k-th shortest paths in the protein-protein interaction (PPI) network (we set k = 1, 2 in this study). Finally, we found 33 genes whose p-values were less than 0.05, and most of them have been reported to be involved in HCC tumorigenesis and development. The results also provide a new reference for research into HCC oncogenesis and for development of new strategies for HCC clinical therapies. PMID:24056857

Jiang, Min; Chen, Yukang; Zhang, Yuchao; Chen, Lei; Zhang, Ning; Huang, Tao; Cai, Yu-Dong; Kong, Xiangyin

2013-10-01

82

A Path Algorithm for Constrained Estimation  

PubMed Central

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

Zhou, Hua; Lange, Kenneth

2013-01-01

83

Adaptive path planning: Algorithm and analysis  

SciTech Connect

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

Chen, Pang C.

1995-03-01

84

Adaptive path planning: Algorithm and analysis  

SciTech Connect

Path planning has to be fast to support 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 alleviate this problem, we present a learning algorithm that uses past experience to enhance 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 subgoals is learned to support faster planning. The algorithm is suitable for both stationary and incrementally-changing environments. To analyze our algorithm, we use a previously developed stochastic model that quantifies experience utility. Using this model, we characterize the situations in which the adaptive planner is useful, and provide quantitative bounds to predict its behavior. The results are demonstrated with problems in manipulator planning. Our algorithm and analysis are sufficiently general that they may also be applied to task planning or other planning domains in which experience is useful.

Chen, Pang C.

1993-03-01

85

Adaptive path planning algorithm for cooperating unmanned air vehicles  

SciTech Connect

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

Cunningham, C T; Roberts, R S

2001-02-08

86

Path planning for a mobile robot using genetic algorithms  

Microsoft Academic Search

This paper presents a new algorithm for global path planning to a goal for a mobile robot using Genetic Algorithm (GA). A genetic algorithm is used to find the optimal path for a mobile robot to move in a static environment expressed by a map with nodes and links. Locations of target and obstacles to find an optimal path are

Gihan NAGIB; W. Gharieb

2004-01-01

87

Design of the Optimal Path Algorithm for Line Track Robots  

Microsoft Academic Search

According to the path information collected,combined with the characteristics of the car body, the data of the path has been analyzed, the path optimizing algorithm for line track robots has been established, and the correctness of the algorithm has been verified in experiments in this paper. The algorithm design has some certain significance for the line track optimization of robots

Shixuan Yao; Baoliang Li; Yu Yuan; Jiyou Fei

2009-01-01

88

Tightening non-simple paths and cycles on surfaces  

Microsoft Academic Search

We describe algorithms to compute the shortest path homo- topic to a given path, or the shortest cycle freely homotopic to a given cycle, on an orientable combinatorial surface. Unlike earlier results, our algorithms do not require the input path or cycle to be simple. Given a surface with complexity n, genus g ? 2, and no boundary, we construct

Éric Colin De Verdière; Jeff Erickson

2006-01-01

89

Multi-robot moving path planning based on coevolutionary algorithm  

Microsoft Academic Search

Multi-population coevolutionary algorithm was adopted to solve multi-robot moving path planning problem. The scheme for multi-robot moving path planning based on coevolutionary algorithm was presented, which includes coding methods of the evolving individuals, the representation form of fitness function and the algorithm steps. The validity of this algorithm was validated by practical examples.

Xiaoyan Sun; Dunwei Gong

2004-01-01

90

The Path Planning for Mobile Robot Based on Voronoi Diagram  

Microsoft Academic Search

In order to get the shortest path of the mobile robot, Voronoi diagram has been introduced to the robot path planning in the paper. The paper uses the voronoi diagram method to model the work space, and obtained the global shortest path by the improved Dijkstra algorithm, besides, when dealing with the unknown static obstacles, the paper adopt one method

Huiying Dong; Wenguang Li; Jiayu Zhu; Shuo Duan

2010-01-01

91

The stable paths problem and interdomain routing  

Microsoft Academic Search

Dynamic routing protocols such as RIP and OSPF essentially implement distributed algorithms for solving the shortest paths problem. The border gateway protocol (BGP) is currently the only interdomain routing protocol deployed in the Internet. BGP does not solve a shortest paths problem since any interdomain protocol is required to allow policy-based metrics to override distance-based metrics and enable autonomous systems

Timothy G. Griffin; F. Bruce Shepherd; Gordon T. Wilfong

2002-01-01

92

Recursive Shortest Path Algorithm with Application to Density-integration of Weighted Graphs  

Microsoft Academic Search

Graph theory is increasingly commonly utilised in genetics, proteomics and neuroimaging. In such fields, the data of interest generally constitute weighted graphs. Analysis of such weighted graphs often require the integration of topological metrics with respect to the density of the graph. Here, density refers to the proportion of the number of edges present in that graph. When topological metrics

Cedric E. Ginestet; Andrew Simmons

2011-01-01

93

A constrained shortest-path energy-aware routing algorithm for wireless sensor networks  

Microsoft Academic Search

While traditional routing protocols try to minimize the end-to-end delay or maximize the throughput, most energy-aware routing protocols for wireless sensor networks try to extend the life time of the network by minimizing the energy consumption sacrificing other performance metrics. We introduce a new energy-aware routing protocol that tries to minimize the energy consumption and, at the same time, maintain

Moustafa Youssef; Mohamed Younis; Khaled Arisha

2002-01-01

94

Algorithms for 3D UAV Path Generation and Tracking  

Microsoft Academic Search

In this paper, we consider the problem of 3D path generation and tracking for unmanned air vehicles (UAVs). The proposed path generation algorithm allows us to find a path satisfying arbitrary initial and final conditions, specified in terms of position and velocity. Our method assumes that most of aircraft structural and dynamic limitations can be translated in a turn radius

G. Ambrosino; M. Ariola; U. Ciniglio; F. Corraro; A. Pironti; M. Virgilio

2006-01-01

95

An evolutionary path planning algorithm for military applications  

Microsoft Academic Search

The path planning problem for military applications is discussed, with a review of relevant literature. An evolutionary algorithm originally designed for optimizing 3-dimensional highway alignments is adapted and tested for real-time military path planning applications in a changing environment. An optimization problem is formulated to seek a path for an autonomous agent or robot between given origin and destination points.

M. K. Jha; Cheng-Chieh Chen; P. Schonfeld; S. Kikuchi

2008-01-01

96

Genetic algorithm based path planning for a mobile robot  

Microsoft Academic Search

In this paper, a novel genetic algorithm based approach to path planning of a mobile robot is proposed. The major characteristic of the proposed algorithm is that the chromosome has a variable length. The location target and obstacles are included to find a path for a mobile robot in an environment that is a 2D workplace discretized into a grid

Jianping Tu; Simon X. Yangt

2003-01-01

97

Algorithm for Low Altitude Penetration Aircraft Path Planning with Improved Ant Colony Algorithm  

Microsoft Academic Search

The ant colony algorithm is a new class of population basic algorithm. The path planning is realized by the use of ant colony algorithm when the plane executes the low altitude penetration, which provides a new method for the path planning. In the paper the traditional ant colony algorithm is improved, and measures of keeping optimization, adaptively selecting and adaptively

Wen YE; Deng-wu MA; Hong-da FAN

2005-01-01

98

An ordinary differential equation based solution path algorithm  

PubMed Central

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

Wu, Yichao

2010-01-01

99

The optimal selection of processing path based on a genetic algorithm for manufacturing processes in the machine industry  

NASA Astrophysics Data System (ADS)

The focus of this study is path selection for manufacturing processing, such as finding the shortest processing path, in an application of such a printed circuit board in the electronic industry. This paper models this kind of processing path optimization problem by application of a GA algorithm. First, the related problem of math modeling is discussed, such as coding methods, selection of fitness functions, and choice of genetic operators such as a selection operator, crossover operator, reverse operator, mutation operator and related parameters. All of these are used to build a solving model. Then related factor of genetic optimization algorithm such as initial generation, fitness evaluation, computing steps and so on was designed. The results of simulation and comparisons with practical application show that GA is feasible and valid.

Peng, Jinmin; Yan, He; Li, Taifu

2005-12-01

100

Efficient Algorithms for the Kinematics and Path Planning of Manipulator  

Microsoft Academic Search

The two basic problems of the automatic control of robotic manipulators are the kinematics and the path planning, which are the fundamental for computer controlled robots. The article presented fast and efficient algorithms for the inverse kinematics and path planning of manipulator consisting of six revolute joints. Through the control, we cause the end-effector of the manipulator to the maximum

Dequan Guo; Hui Ju; Yuqin Yao; Feng Ling; Tianxiang Li

2009-01-01

101

A Comparison of Algorithms for Path Planning of Industrial Robots  

Microsoft Academic Search

In this paper, the path planning problem for industrial robots in environ- ments with obstacles has been solved using four algorithms that implement different methodologies. Our objective is to analyze the characteristics of these algorithms. Consequently, the results (solutions) obtained with each of them are compared through the analysis of three operational parameters that are relevant to determine the qualities

Francisco Rubio; Francisco Valero; Vicente Mata

102

Skeletonization algorithm running on path-based distance maps  

Microsoft Academic Search

A new skeletonization algorithm is introduced which runs on the distance map of a digital figure, computed according to any among four commonly used path-based distance functions. The skeletonization algorithm has a number of features: it is reversible, since it detects the centres of the maximal disks; it is nearly invariant under figure rotation (when the adopted distance function provides

Gabriella Sanniti Di Baja; Edouard Thiel

1996-01-01

103

Robot Path Planning Using a Genetic Algorithm.  

National Technical Information Service (NTIS)

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

T. F. Cleghorn P. T. Baffes L. Wang

1988-01-01

104

A MULTI-PURPOSE OFF-LINE PATH PLANNER BASED ON AN A* SEARCH ALGORITHM  

Microsoft Academic Search

Efficient navigation of an autonomous mobile robot through a majority of which search for shortest euclidean-distance paths for well-defined environment requires the ability of the robot to plan robots free of nonholonomic constraints. For a broad overview of paths. An efficient and reliable planar off-line path planner has been path planning for robots see (Latombe, 1990). Deo and Pang developed

Arturo L. Rankin; Carl D. Crane

105

Self avoiding paths routing algorithm in scale-free networks  

NASA Astrophysics Data System (ADS)

In this paper, we present a new routing algorithm called ``the self avoiding paths routing algorithm.'' Its application to traffic flow in scale-free networks shows a great improvement over the so called ``efficient routing'' protocol while at the same time maintaining a relatively low average packet travel time. It has the advantage of minimizing path overlapping throughout the network in a self consistent manner with a relatively small number of iterations by maintaining an equilibrated path distribution especially among the hubs. This results in a significant shifting of the critical packet generation rate over which traffic congestion occurs, thus permitting the network to sustain more information packets in the free flow state. The performance of the algorithm is discussed both on a Barábasi-Albert network and real autonomous system network data.

Rachadi, Abdeljalil; Jedra, Mohamed; Zahid, Noureddine

2013-03-01

106

A Bat Algorithm with Mutation for UCAV Path Planning  

PubMed Central

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.

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

2012-01-01

107

Path integral hybrid Monte Carlo algorithm for correlated Bose fluids.  

PubMed

Path integral hybrid Monte Carlo (PIHMC) algorithm for strongly correlated Bose fluids has been developed. This is an extended version of our previous method [S. Miura and S. Okazaki, Chem. Phys. Lett. 308, 115 (1999)] applied to a model system consisting of noninteracting bosons. Our PIHMC method for the correlated Bose fluids is constituted of two trial moves to sample path-variables describing system coordinates along imaginary time and a permutation of particle labels giving a boundary condition with respect to imaginary time. The path-variables for a given permutation are generated by a hybrid Monte Carlo method based on path integral molecular dynamics techniques. Equations of motion for the path-variables are formulated on the basis of a collective coordinate representation of the path, staging variables, to enhance the sampling efficiency. The permutation sampling to satisfy Bose-Einstein statistics is performed using the multilevel Metropolis method developed by Ceperley and Pollock [Phys. Rev. Lett. 56, 351 (1986)]. Our PIHMC method has successfully been applied to liquid helium-4 at a state point where the system is in a superfluid phase. Parameters determining the sampling efficiency are optimized in such a way that correlation among successive PIHMC steps is minimized. PMID:15268354

Miura, Shinichi; Tanaka, Junji

2004-02-01

108

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

109

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

110

UAV online path planning based on dynamic multiobjective evolutionary algorithm  

Microsoft Academic Search

Online path planning (OPP) is the basic issue of some complex mission and is indeed a dynamic multi-objective optimization problem (DMOP). In this paper, we use an OPP scheme in the sense of model predictive control (MPC) to continuously update the environmental information for the planner. For solving the DMOP involved in the MPC-like OPP a dynamic multi-objective evolutionary algorithm

Xingguang Peng; Demin Xu; Fubin Zhang

2011-01-01

111

A Knowledge based Genetic Algorithm for Path Planning of a Mobile Robot  

Microsoft Academic Search

In this paper, a knowledge based genetic algorithm (GA) for path planning of a mobile robot is proposed, which uses problem-specific genetic algorithms for robot path planning instead of the standard GAs. The proposed knowledge based genetic algorithm incorporates the domain knowledge into its specialized operators, where some also combine a local search technique. The proposed genetic algorithm also features

Yanrong Hu; Simon X. Yang

2004-01-01

112

Novel Path Search Algorithm for Image Stitching and Advanced Texture Tiling  

Microsoft Academic Search

We propose a fast and adjustable sub-optimal path search algorithm for finding minimum error boundaries be- tween overlapping images. The algorithm may serve as an efficient alternative to traditional slow path search algorithms like the dynamical programming. We use the algorithm in combination with novel adaptive blending to stitch image regions. The technique is then exploited in a framework for

Petr Somol; Michal Haindl

2005-01-01

113

On path planning: Adaptation to the environment using Fast Marching  

Microsoft Academic Search

This paper presents a novel methodology for fast path planning based on an offline predefined skeleton of the environment by means of the Fast Marching Square method. The FM2 skeleton concept is introduced whose intuition is a set which contains the shortest paths (in terms of time) of a given environment This way, the path planning algorithm is adapted to

Javier V. Gomez; Cesar Arismendit; Santiago Garrido; Luis Moreno

2012-01-01

114

Optimal path planning for mobile robots based on intensified ant colony optimization algorithm  

Microsoft Academic Search

Optimal path planning for mobile robots plays an important role in the field of robotics. At present, there are many advanced algorithms used to solve this optimal problem. However, for those algorithms, it is very difficult to solve some path planning problems containing certain constraint conditions due to the complex background environment. Based on the intensified ant colony optimization algorithm,

Xiaoping Fan; Xiong Luo; Sheng Yi; Shengyue Yang; Heng Zhang

2003-01-01

115

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

Microsoft Academic Search

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

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

2003-01-01

116

An Improved Algorithm for Searching Local Optimal Path in Intelligent Transport System  

Microsoft Academic Search

This paper provides an improved search algorithm for optimal route planning by rebuilding the search area in intelligent transport system. The theory foundation is that the classical Dijsktra algorithm has not any directional feature during searching the optimal path, and the bidirectional Dijsktra has its own limit. Based on the analysis of the two algorithms, the new improved algorithm proposed

Zhide Liu; Jiabin Chen; Chunlei Song; Lu Ding

2008-01-01

117

Control Flow Paths Subset of Tested Program Generation Algorithm Based on LCC  

Microsoft Academic Search

(Abstract)To solve the key problem of how to calculate the effective subset of the control flow paths of the tested program, this paper proposes an algorithm for working out the subset of the whole control flow paths of the program with the help of the LCC compiler in software coverage testing. The control flow paths in the subset are based

CHEN Yu; LI Zhi-shu; JIN Hu; HE Jiang

2009-01-01

118

Cruise Missile Mission Planning: A Heuristic Algorithm for Automatic Path Generation  

Microsoft Academic Search

This manuscript presents a heuristic algorithm based on geometric concepts for the problem of finding a path composed of line segments from a given origin to a given destination in the presence of polygonal obstacles. The basic idea involves constructing circumscribing triangles around the obstacles to be avoided. Our heuristic algorithm considers paths composed primarily of line segments corresponding to

R. V. Helgason; J. L. Kennington; K. R. Lewis

2001-01-01

119

Mathematical model of best-path planning algorithms for public transportation systems  

Microsoft Academic Search

This paper presents the best-path planning algorithms for the public transport systems. This paper uses the idea of direct matrix, transfer matrix and set theory to build a mathematical model, and regards the bus lines as a set to seek their public sites in order to find best path. This paper improves the set algorithms, and uses the transfer matrix

Bi Yong; Hu Hongping

2010-01-01

120

Efficient algorithms to embed Hamiltonian Paths and Cycles in faulty crossed cubes  

Microsoft Academic Search

The crossed cube is an important variation of the hypercube. It possesses many desirable properties for interconnection networks. Hamiltonicity is a critical property in interconnection networks. In this paper, we study fault-tolerant embedding algorithms of Hamiltonian paths and cycles in crossed cubes. We provide two algorithms Hamiltonian path and Hamiltonian cycle. For any integer n ges 3, letting CQn(V, E)

Jianxi Fan; Wujun Zhou; Yuejuan Han; Guangquan Zhang

2009-01-01

121

Path Planning Based on Ant Colony Algorithm and Distributed Local Navigation for Multi-Robot Systems  

Microsoft Academic Search

This paper presents a decoupled path planning based on ant colony algorithm and distributed navigation with collision avoidance for multi-robot systems. An improved ant colony algorithm is proposed to plan a reasonable collision-free path for each mobile robot of multi-robot system in the decoupled path planning scheme in complicated static environment. The special functions are added into the regular ant

Shirong Liu; Linbo Mao; Jinshou Yu

2006-01-01

122

An efficient hierarchical optical path network design algorithm based on a traffic demand expression in a cartesian product space  

Microsoft Academic Search

We propose a hierarchical optical path network design algorithm. In order to efficiently accommodate wavelength paths in each waveband path, we define a source-destination Cartesian product space that allows the 'closeness' among wavelength paths to be assessed. By grouping 'close' wavelength paths, found by searching for clusters in the space, we iteratively create waveband paths that efficiently accommodate the wavelength

Isao Yagyu; Hiroshi Hasegawa; Ken-ichi Sato

2008-01-01

123

A path following algorithm for the graph matching problem.  

PubMed

We propose a convex-concave programming approach for the labeled weighted graph matching problem. The convex-concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices. The concave relaxation has the same global minimum as the initial graph matching problem, but the search for its global minimum is also a hard combinatorial problem. We, therefore, construct an approximation of the concave problem solution by following a solution path of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting from the convex relaxation. This method allows to easily integrate the information on graph label similarities into the optimization problem, and therefore, perform labeled weighted graph matching. The algorithm is compared with some of the best performing graph matching methods on four data sets: simulated graphs, QAPLib, retina vessel images, and handwritten Chinese characters. In all cases, the results are competitive with the state of the art. PMID:19834143

Zaslavskiy, Mikhail; Bach, Francis; Vert, Jean-Philippe

2009-12-01

124

Real-time 3D path planning for sensor-based underwater robotics vehicles in unknown environment  

Microsoft Academic Search

Studies path planning strategies on real-time 3D near-shortest path planning for sensor-based underwater robotics vehicles (URV) in an unknown environment. The unknown environment includes multiple static obstacles of arbitrary shape. Based on limited sensor vision zone and the URV attitude dynamics, a 3D near-shortest path planning algorithm is developed for the URV in an unknown environment. The control variables are

Nan Ying; Low Eicher; Wang Xunzhang; G. G. L. Seet; M. W. S. Lau

2000-01-01

125

ELASTIC NET FOR COX'S PROPORTIONAL HAZARDS MODEL WITH A SOLUTION PATH ALGORITHM  

PubMed Central

For least squares regression, Efron et al. (2004) proposed an efficient solution path algorithm, the least angle regression (LAR). They showed that a slight modification of the LAR leads to the whole LASSO solution path. Both the LAR and LASSO solution paths are piecewise linear. Recently Wu (2011) extended the LAR to generalized linear models and the quasi-likelihood method. In this work we extend the LAR further to handle Cox’s proportional hazards model. The goal is to develop a solution path algorithm for the elastic net penalty (Zou and Hastie (2005)) in Cox’s proportional hazards model. This goal is achieved in two steps. First we extend the LAR to optimizing the log partial likelihood plus a fixed small ridge term. Then we define a path modification, which leads to the solution path of the elastic net regularized log partial likelihood. Our solution path is exact and piecewise determined by ordinary differential equation systems.

Wu, Yichao

2012-01-01

126

A Knowledge Based Genetic Algorithm for Path Planning in Unstructured Mobile Robot Environments  

Microsoft Academic Search

This paper proposes a knowledge based genetic algorithm (GA) for path planning of a mobile robot in unstructured environments. The algorithm uses a unique problem representation method to represent 2-dimensional robot environments with complex obstacle layouts of arbitrary obstacle shapes. An effective evaluation method is specially developed for the proposed genetic algorithm. The evaluation method is able to accurately detect

Yanrong Hu; S. X. Yang; Li-Zhong Xu; Q.-H. Meng

2004-01-01

127

Detection of Curved Text Path Based on the Fuzzy Curve-Tracing (FCT) Algorithm  

Microsoft Academic Search

Artistic documents often contain text along curved paths. Commonly used computer algorithms for text extraction, which only deal with text along straight lines, cannot be employed to analyze these artistic documents. In this paper, we solve this problem using the fuzzy curve-tracing algorithm. In our method, the character pixels are grouped based on the fuzzy c-means algorithm to reduce the

Hong Yan

2001-01-01

128

Evaluating the Quality of Clustering Algorithms Using Cluster Path Lengths  

Microsoft Academic Search

\\u000a Many real world systems can be modeled as networks or graphs. Clustering algorithms that help us to organize and understand\\u000a these networks are usually referred to as, graph based clustering algorithms. Many algorithms exist in the literature for\\u000a clustering network data. Evaluating the quality of these clustering algorithms is an important task addressed by different\\u000a researchers. An important ingredient of

Faraz Zaidi; Daniel Archambault; Guy Melançon

2010-01-01

129

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

PubMed Central

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.

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

2010-01-01

130

A Static Environment-Based Path Planning Method by Using Genetic Algorithm  

Microsoft Academic Search

This paper proposed a genetic algorithm-based method of path planning for mobile robot in a static environment. The paper uses a simple fitness function as the evaluation standard for an individual or a path. This is able to reduce the computation consumption, but it still cannot avoid of customizing genetic operators. In most cases, thus, the optimal solution could be

Zhigang Yao; Lianyang Ma

2010-01-01

131

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

Microsoft Academic Search

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

Stavros G. Kolliopoulos; Clifford Stein

1998-01-01

132

Step-spreading map knowledge based multi-objective genetic algorithm for robot-path planning  

Microsoft Academic Search

To tackle the path planning of mobile robots, a step-spreading map (SSM) algorithm was proposed as the prior knowledge to instruct the evolutionary process of multi- objective genetic algorithm (MOGA). The time complexity of SSM is O(8 x n) and n is the scale of problem. Inspired by Pareto optimum and NSGA-II, the developed MOGA can deal the path planning

Jin Yuan; Tao Yu; Kesheng Wang; Xuemei Liu

2007-01-01

133

New Grid-Based Algorithms for Partially Observable Markov Decision Processes: Theory and Practice  

Microsoft Academic Search

We present two new algorithms for Partially Observable Markov Decision Processes (pomdps). The rst algorithm is a general grid-based algorithm for pomdps with theoret- ical optimality guarantees. The other algorithm is for the subclass of problems known as Stochastic Shortest-Path problems in belief space. Both algorithms are optimal and robust with respect to a novel robustness criterion that is also

Blai Bonet

134

New scaling algorithms for the assignment and minimum mean cycle problems  

Microsoft Academic Search

In this paper we suggest new scaling algorithms for the assignment and minimum mean cycle problems. Our assignment algorithm is based on applying scaling to a hybrid version of the recentauction algorithm of Bertsekas and the successive shortest path algorithm. The algorithm proceeds by relaxing the optimality conditions, and the amount of relaxation is successively reduced to zero. On a

James B. Orlin; Ravindra K. Ahuja

1992-01-01

135

On the Efficiency of a Prefix Path Holistic Algorithm  

NASA Astrophysics Data System (ADS)

In recent years, many approaches to XML twig pattern searching have been developed. Holistic approaches such as TwigStack are particularly significant in that they provide a powerful theoretical model for optimal processing of some query types. Holistic algorithms use various partitionings of an XML document called streaming schemes and they prove algorithm optimality depending on query characteristics.

Ba?a, Radim; Krátký, Michal

136

A path-planning algorithm for image-guided neurosurgery  

Microsoft Academic Search

. A computer algorithm for determining optimal surgical pathsin the brain is presented. The algorithm computes a cost function associatedwith each point on the outer brain boundary, which is treated asa candidate entry point. The cost function is determined partly basedon a segmentation of the patients images into gray and white matter,and partly based on a spatially transformed atlas of

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

1997-01-01

137

Introduction to Algorithms  

NSDL National Science Digital Library

This course provides an introduction to algorithms. Topics include sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; caching; and parallel computing. Selected lecture notes, video and audio lectures, and assignments with solutions are included. MIT presents OpenCourseWare as free educational material online. No registration or enrollment is required to use the materials.

Leiserson, Charles E.; Demaine, Erik D., 1981-

2010-12-28

138

Co-Expressed Gene Assessment Based on the Path Consistency Algorithm: Operon Detention in Escherichia coli  

Microsoft Academic Search

The assessment of co-expressed genes is an initial step to investigate the gene regulatory system in a microarray analysis. We designed a simple method to assess co-expressed genes from the expression profiles, based on the path consistency (PC) algorithm, which systematically infers a causal graph. The PC algorithm is simply modified for the frequent occurrence of high correlations between expression

Katsuhisa Horimoto; Shigeru Saito

2009-01-01

139

Optimal Path Planning for Autonomous Airship Based on Clonal Selection and Direct Collocation Algorithm  

Microsoft Academic Search

A novel algorithm, based on clonal selection and direct collocation theories, is introduced to solve the three-dimensional optimal path problem of airship. Firstly, the six-DOF (Degree of Freedom) nonlinear dynamic model for a special kind of airship is presented. Then, the model of novel algorithm is designed from clonal selection and direct collocation aspects respectively, and the dissipative energy function

Yu Liu; Yachen Zhang; Yueming Hu

2008-01-01

140

UCAV path planning based on Ant Colony Optimization and satisficing decision algorithm  

Microsoft Academic Search

Path planning of uninhabited combat air vehicle (UCAV) is a complicated global optimum problem. Ant colony optimization (ACO) algorithm was originally presented under the inspiration during collective behavior study results on real ant system, and it has strong robustness and easy to combine with other methods in optimization. In this paper, we propose a hybrid ACO with satisficing decision algorithm

Haibin Duan; Yaxiang Yu; Rui Zhou

2008-01-01

141

Algorithms of localization and statistics of dislocations on the path of laser beam propagation  

Microsoft Academic Search

Three algorithms of dislocation localization in the wave front of a laser beam propagating in a turbulent medium are considered in the report. The precision of algorithms is assessed and statistics of dislocations is determined in different cross-sections of the path as a function of atmospheric parameters such as Fried length and the outer scale of turbulence. The preliminary results

Lidia N. Lavrinova; Feodor Y. Kanev; Vladimir P. Lukin

2002-01-01

142

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

ERIC Educational Resources Information Center

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

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

2002-01-01

143

Algorithms for Media  

Microsoft Academic Search

Falmagne recently introduced the concept of a medium, a combinatorial object encompassing hyperplane arrangements, topological orderings, acyclic orientatio ns, and many other familiar structures. We find efficient solutions for several algorithmic problems on media: findin g short reset sequences, shortest paths, testing whether a medium has a closed orientation, and listing the states of a medium given a black-box description.

David Eppstein; Jean-Claude Falmagne

2002-01-01

144

Algorithms for Reliable Navigation and Wayfinding  

NASA Astrophysics Data System (ADS)

Wayfinding research has inspired several algorithms that compute the shortest, fastest, or even simplest paths between two locations. Current navigation systems, however, do not take into account the navigational complexity of certain intersections. A short route might involve a number of intersections that are difficult to navigate, because they offer more than one alternative to turn left or right. The navigational complexity of such an intersection may require modified instructions such as veer right. This paper, therefore, presents a reliable path algorithm that minimizes the number of complex intersections with turn ambiguities between two locations along a route. Our algorithm computes the (shortest) most reliable path, i.e., the one with the least turn ambiguities. Furthermore, we develop a variation of this algorithm that balances travel distance and navigational complexity. Simulation results show that traversing a reliable path leads to less navigational errors, which in turn reduces the average travel distance. A further advantage is that reliable paths require simpler instructions.

Haque, Shazia; Kulik, Lars; Klippel, Alexander

145

Path Planning for Unmanned Vehicles Using Ant Colony Optimization on a Dynamic Voronoi Diagram  

Microsoft Academic Search

One of the main objectives when planning paths for unmanned vehicles is to minimizing the time of arriving at the given destination while maximizing the safety of the vehicles. If the operational environment is static with perfect information, a safe and shortest path can be generated by applying a traditional optimization algorithm such as A*. However, if the environment is

Yaohang Li; Tao Dong; Marwan Bikdash; Yong-duan Song

2005-01-01

146

Multiple Objective Genetic Algorithms for Path-planning Optimization in Autonomous Mobile Robots  

Microsoft Academic Search

This paper describes the use of a genetic algorithm (GA) for the problem of offline point-to-point autonomous mobile robot path planning. The problem consists of generating “valid” paths or trajectories, for an Holonomic Robot to use to move from a starting position to a destination across a flat map of a terrain, represented by a two-dimensional grid, with obstacles and

Oscar Castillo; Leonardo Trujillo; Patricia Melin

2007-01-01

147

Hybrid hierarchical optical path network design algorithm with 2-stage ILP optimization  

NASA Astrophysics Data System (ADS)

We propose a 2-stage ILP-based design algorithm for hierarchical optical path networks that utilize hybrid-HOXCs. The hybrid-HOXC consists of an optical waveband cross-connect and an electrical cross-connect which grooms only wavelength paths. Its effectiveness is evaluated through numerical experiments. Impact of electrical/optical port cost ratio on the total network cost is also investigated.

Le, Hai-Chau; Hasegawa, Hiroshi; Sato, Ken-Ichi

2010-12-01

148

Path-planning algorithm for ships in close-range encounters  

Microsoft Academic Search

Efficient maritime navigation through obstructions at close range is still one of the many problems faced by mariners. The\\u000a increasing traffic densities and average cruise speed of ships also impede the collision avoidance process by reducing the\\u000a time available for decision making. This study develops a path-planning algorithm that determines an optimal navigation path\\u000a for ships in close-range encounters, using

CheeKuang Tam; Richard Bucknall

2010-01-01

149

Comparison of image restoration algorithms in the context of horizontal-path imaging  

NASA Astrophysics Data System (ADS)

We have looked at applying various image restoration techniques used in astronomy to the problem of imaging through horizontal-path turbulence. The input data comes from an imaging test over a 2.5km path. The point-spread function (PSF) is estimated directly from the data and supplied to the deconvolution algorithms. We show the usefulness of using this approach, together with the analytical form of the turbulent PSF due to D. Fried, for reference-less imaging scenarios.

Gladysz, Szymon; Baena Gallé, Roberto

2012-05-01

150

Faster Strongly Polynomial Minimum Cost Flow Algorithm.  

National Technical Information Service (NTIS)

We present a new strongly polynomial algorithm for the minimum cost flow problem, based on a refinement of the Edmonds-Karp scaling technique. Our algorithm solves the uncapacitated minimum cost flow problem as a sequence of O(n log n) shortest path probl...

J. B. Orlin

1989-01-01

151

Faster Strongly Polynomial Minimum Cost Flow Algorithm.  

National Technical Information Service (NTIS)

We present a new strongly polynomial algorithm for the minimum cost flow problem, based on a refinement of the Edmonds-Karp scaling technique. Our algorithm solves the uncapacitated minimum cost flow problem as a sequence of O(n log n) shortest path probl...

J. B. Orlin

1988-01-01

152

JHAV' - Floyd's Algorithm  

NSDL National Science Digital Library

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

Richard Teviotdale, Tom N.

153

Ant Colony System Algorithm for Real-Time Globally Optimal Path Planning of Mobile Robots  

Microsoft Academic Search

A novel method for the real-time globally optimal path planning of mobile robots is proposed based on the ant colony system (ACS) algorithm. This method includes three steps: the first step is utilizing the MAKLINK graph theory to establish the free space model of the mobile robot, the second step is utilizing the Dijkstra algorithm to find a sub-optimal collision-free

Guan-Zheng TAN; Huan HE; Aaron SLOMAN

2007-01-01

154

A Non-critical Path Earliest-Finish Algorithm for Interdependent Tasks in Heterogeneous Computing Environments  

Microsoft Academic Search

In recent years, many researchers have proposed several algorithms to schedule critical tasks in a homogeneous multiprocessor system for obtaining a shorter scheduling length. However, for heterogeneous computing systems, such methods may lead to lengthen the execution of other non-critical tasks. In this paper, a Non-critical Path Earliest-Finish (NPEF) scheduling algorithm for heterogeneous computing systems has been proposed to eliminate

Liang-teh Lee; Ching-wei Chen; Hung-yuan Chang; Chih-chieh Tang; Kun-chi Pan

2009-01-01

155

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

156

A Qos Routing Algorithm Based on Ant Algorithm  

Microsoft Academic Search

The requirements of routing due to multimedia applications are discussed. In order to solve the QoS constrained routing effectively and efficiently, we construct a globally optimizing ant algorithm, which is based on the ability of ants to find the shortest path between their nest and the food source during their search for food. Simulation results show that the proposed approach

Zhang Subing; Liu Zemin

2000-01-01

157

A QoS routing algorithm based on ant algorithm  

Microsoft Academic Search

In this paper, the requirements of routing due to multimedia applications are briefly discussed. In order to solve the QoS constrained routing effectively and efficiently, we construct a globally optimizing ant algorithm, which is based on the ability of ants to find the shortest path between their nest and the food source during their looking for food. Simulation results show

Zhang Subing; Liu Zemin

2001-01-01

158

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

Microsoft Academic Search

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

David Rathbun; Sean Kragelund; Anawat Pongpunwattana; Brian Capozzi

2002-01-01

159

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

PubMed

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

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

2003-01-01

160

Combination of Neural Network and SBFM Algorithm for Monitoring VOCs Distribution by Open Path FTIR Spectrometry  

Microsoft Academic Search

In this research, the combination of artificial neural network (ANN) modeling and smooth basis function minimization (SBFM) algorithm were applied to Open Path Fourier transform infrared spectroscopy (OP?FTIR) for monitoring volatile organic compounds' concentration distribution in the air. ANN was utilized to analyze the measured mixture spectra containing chloroform, methanol, and methylene chloride; Then, SBFM was used to reconstruct each

Yibo Ren; Yan Li; Baihua Yu; Junde Wang; Lanping Hu

2007-01-01

161

Path planning of an agricultural mobile robot by neural network and genetic algorithm  

Microsoft Academic Search

The purpose of this study is to develop a method that is able to create a suboptimal path of an agricultural mobile robot. This work is an attempt to apply a control technique combining a neural network (NN) and a genetic algorithm (GA). A NN is applied to describe the motion of the agricultural mobile robot as a nonlinear system

Noboru Noguchi; Hideo Terao

1997-01-01

162

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

NASA Astrophysics Data System (ADS)

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

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

2010-01-01

163

Formal language constrained path problems  

SciTech Connect

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

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

1997-07-08

164

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

NASA Astrophysics Data System (ADS)

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

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

165

An Improved Path-Based Transductive Support Vector Machines Algorithm for Blind Steganalysis Classification  

NASA Astrophysics Data System (ADS)

With the technologies of blind steganalysis becoming increasingly popular, a growing number of researchers concern in this domain. Supervised learning for classification is widely used, but this method is often time consuming and effort costing to obtain the labeled data. In this paper, an improved semi-supervised learning method: path-based transductive support vector machines (TSVM) algorithm with Mahalanobis distance is proposed for blind steganalysis classification, by using modified connectivity kernel matrix to improve the classification accuracy. Experimental results show that our proposed algorithm achieves the highest accuracy among all examined semi-supervised TSVM methods, especially for a small labeled data set.

Zhang, Xue; Zhong, Shangping

166

Simple Path Planning Algorithm for Two-Wheeled Differentially Driven (2WDD) Soccer Robots  

Microsoft Academic Search

Well designed path planning algorithms are the key factor for mov- ing robots. This paper describes a novel simple approach based on kinematics. The testing bed is a tiny two-wheeled robot. The robot's movement is specified by its translatoric velocityvR and its angular velocity!R. The kinematic approach gener- ates piecewise circular arcs based on a number of possible different sets

Gregor Novak; Martin Seyr

2004-01-01

167

A Hybrid-Coded Genetic Algorithm Based Optimisation of NonProductive Paths in CNC Machining  

Microsoft Academic Search

In order to optimise the non-productive paths in CNC machining under entry or exit constraints (such as in laser engraving\\u000a and flame cutting), a hybrid-coded genetic algorithm (HCGA) is proposed in this paper. There are two chromosomes in the HCGA.\\u000a One chromosome, called the master chromosome, uses a natural number-coded mode, and represents the sequence of productive\\u000a contours. The other

T. X. Zhong; J. C. Chen

2002-01-01

168

Extended Q-Learning Algorithm for Path-Planning of a Mobile Robot  

Microsoft Academic Search

\\u000a In this paper, we study the path planning for Khepera II mobile robot in a grid map environment using an extended Q-learning\\u000a algorithm. The extension offers an additional benefit of avoiding unnecessary computations involved to update the Q-table.\\u000a A flag variable is used to keep track of the necessary updating in the entries of the Q-table. The validation of the

Pradipta Kumar Das; Amit Konar; Ramadoss Janarthanan

2010-01-01

169

Debugging ants: How ants find the shortest route  

Microsoft Academic Search

Collective foraging in ant colonies is as remarkable in that ants are solving a distributed control and optimization task that is still not fully untravelled. Ants deposit pheromone as they travel, and paths with more pheromone are preferred by succeeding ants. Without any direct communication amongst themselves, ants quickly abandon other trails to concentrate on the shortest one. If the

Jayadeva; Sameena Shah; R. Kothari; Suresh Chandra

2011-01-01

170

PATH  

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.

171

Research on Static Global Path-Planning Algorithm of Virtual Animal in the Three-Dimensional Space  

Microsoft Academic Search

\\u000a The research on motion planning of a virtual agent is very important in computer animation, where path planning is the most\\u000a representative. In this paper we do an in-depth study about the problem of static and global path planning for three-dimensional\\u000a virtual animals in the marine environment, constructed the path planning strategy of a fast randomized algorithm. First of\\u000a all,

Di Wu; Xiao-juan Ban; Xu-mei Lei; Pan Gao; Tian Jin

172

Rotational fluctuation of molecules in quantum clusters. I. Path integral hybrid Monte Carlo algorithm.  

PubMed

In this paper, we present a path integral hybrid Monte Carlo (PIHMC) method for rotating molecules in quantum fluids. This is an extension of our PIHMC for correlated Bose fluids [S. Miura and J. Tanaka, J. Chem. Phys. 120, 2160 (2004)] to handle the molecular rotation quantum mechanically. A novel technique referred to be an effective potential of quantum rotation is introduced to incorporate the rotational degree of freedom in the path integral molecular dynamics or hybrid Monte Carlo algorithm. For a permutation move to satisfy Bose statistics, we devise a multilevel Metropolis method combined with a configurational-bias technique for efficiently sampling the permutation and the associated atomic coordinates. Then, we have applied the PIHMC to a helium-4 cluster doped with a carbonyl sulfide molecule. The effects of the quantum rotation on the solvation structure and energetics were examined. Translational and rotational fluctuations of the dopant in the superfluid cluster were also analyzed. PMID:17381207

Miura, Shinichi

2007-03-21

173

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

Microsoft Academic Search

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

174

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

Microsoft Academic Search

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

Tewolde S. Tewolde; Weihua Sheng

2008-01-01

175

A disjoint path selection scheme with shared risk link groups in GMPLS networks  

Microsoft Academic Search

This letter proposes a disjoint path selection scheme for generalized multi-protocol label switching (GMPLS) networks with shared risk link group (SRLG) constraints. It is called the weighted-SRLG (WSRLG) scheme. It treats the number of SRLG members related to a link as part of the link cost when the k-shortest path algorithm is executed. In WSRLG, a link that has many

Eiji Oki; Nobuaki Matsuura; Kohei Shiomoto; Naoaki Yamanaka

2002-01-01

176

An Algorithm to Compute Statistics of Stochastic Paths on Complex Landscapes  

NASA Astrophysics Data System (ADS)

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

Manhart, Michael; Morozov, Alexandre V.

2013-03-01

177

Optimization of the algorithms for estimating the ultrasonic attenuation along the propagation path  

PubMed Central

In this study, we perform statistical analysis on two methods used to estimate the total ultrasound attenuation along the propagation path from the surface of the transducer to a region of interest at a particular depth; namely, the spectral-fit method and the multiple-filter method. We derive mathematical equations for the bias and variance in the attenuation estimates as a function of region of interest (ROI) size, imaging system bandwidth, and number of independent Gaussian filters (for the multiple filter method). We use numerical simulations to validate the mathematical equations and compare the two algorithms. The results show that the variance in the total attenuation coefficient estimates obtained with the two methods are comparable, and that the estimates are unbiased. For the multiple filter method, the optimal number of Gaussian filters is two.

Labyed, Yassin; Bigelow, Timothy A.

2012-01-01

178

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

179

A Discrete Global Minimization Algorithm for Continuous Variational Problems  

Microsoft Academic Search

In this paper, we apply the ideas from combinatorial optimization to find globally optimal solutions to continuous variational problems. At the heart of our method is an algorithm to solve for globally optimal discrete minimal surfaces. This discrete surface problem is a natural generalization of the planar-graph shortest path problem.

Danil Kirsanov

2004-01-01

180

Worm algorithm and diagrammatic Monte Carlo: A new approach to continuous-space path integral Monte Carlo simulations  

Microsoft Academic Search

A detailed description is provided of a new worm algorithm, enabling the accurate computation of thermodynamic properties of quantum many-body systems in continuous space, at finite temperature. The algorithm is formulated within the general path integral Monte Carlo (PIMC) scheme, but also allows one to perform quantum simulations in the grand canonical ensemble, as well as to compute off-diagonal imaginary-time

M. Boninsegni; N. V. Prokof'Ev; B. V. Svistunov

2006-01-01

181

A strategy for solving static multiple-optimal-path transit network problems  

SciTech Connect

The trip making process using transit versus private automobile differs in the use of time schedules, walking paths, transfer stops, plus issues such as fare and safety. Due to these factors, many of the standard shortest path algorithms do not apply. The purpose of this study is to develop an algorithm and strategy for transit providers to find best alternatives for the user, and to demonstrate how a geographic information system can be used in the development of transit advanced traveler information system (TATIS) to meet these needs. This paper presents a short introduction to TATIS systems, some commonly used algorithms in determining the shortest and multiple paths, and a new strategy that was developed in this study which differs from standard network algorithms. The major features of this proposed algorithm are: (1) Capability of handling multiple modes of transit; (2) providing paths that include walking distances from and to the transit path as well as between transfer points; and (3) provision of multiple optimal paths to allow the user flexibility in choosing a path.

Koncz, N.; Greenfeld, J.; Mouskos, K. [New Jersey Inst. of Tech., Newark, NJ (United States). Dept. of Civil Engineering

1996-05-01

182

Optimal offline path planning of a fixed wing unmanned aerial vehicle (UAV) using an evolutionary algorithm  

Microsoft Academic Search

Path planning is the process of generating a path between an initial location and a target location that has optimal performance against specific criteria. This paper addresses the problem of offline path planning as applied to autonomous miniature fixed wing unmanned aerial vehicles (mini-UAVs). The path representation takes into account aircraft dynamics by incorporating the turn rates and velocities of

Glenn Sanders; Tapabrata Ray

2007-01-01

183

Path planning for mobile sensor platforms on a 3-D terrain using hybrid evolutionary algorithms  

Microsoft Academic Search

In this paper, a novel hybrid method for path planning problem of multiple mobile sensors on a 3-D terrain is proposed. Our method proceeds in two phases: the global path-planning phase, and the local path planning phase. The first phase constructs a connectivity graph generated by a probabilistic roadmap (PRM) method and selects the control points of sensors' paths from

Mesut Sifyan; Haluk Rahmi Topcuoglu; Murat Ermis

2010-01-01

184

Evolutionary Algorithms Refining a Heuristic: A Hybrid Method for Shared-Path Protections in WDM Networks Under SRLG Constraints  

Microsoft Academic Search

An evolutionary algorithm (EA) can be used to tune the control parameters of a construction heuristic to an opti- mization problem and generate a nearly optimal solution. This approach is in the spirit of indirect encoding EAs. Its performance relies on both the heuristic and the EA. This paper proposes a three-phase parameterized construction heuristic for the shared- path protection

Qingfu Zhang; Jianyong Sun; Gaoxi Xiao; Edward P. K. Tsang

2007-01-01

185

O(Square root of n) Complexity Reduction for the Long-Step Path-Following Algorithm for Linear Programming.  

National Technical Information Service (NTIS)

The authors present a modification of a previously published long-step path-following algorithm for the solution of the linear programming problem. Our modification uses the simple Goldstein-Armijo rule, which enables us to show that an O(Sq rt(n) reducti...

D. den Hertog C. Roos J. P. Vial

1989-01-01

186

A path-stack algorithm for optimizing dynamic regimes in a statistical hidden dynamic model of speech  

Microsoft Academic Search

In this paper we report our recent research whose goal is to improve the performance of a novel speech recognizer based on an underlying statistical hidden dynamic model of phonetic reduction in the production of conversational speech. We have developed a path-stack search algorithm which efficiently computes the likelihood of any observation utterance while optimizing the dynamic regimes in the

Jeff Z. Ma; Li Deng

2000-01-01

187

A Collision-free And Deadlock-free Path-planning Algorithm For Multiple Mobile Robots Without Mutual Communication  

Microsoft Academic Search

A bstra ct- --In this paper, we propose a good pathplanning algorithm for multiple robots without mutual communication. In this research, we first select and call one ol' the multiple robots as the target robot, and then plan a collisionfree and deadlock-free path of' the targct robot toward its goal against the other moving robots in a workspace. The other

Hiroshi Noborio

1992-01-01

188

On Algorithms for Minimum-Cost Quickest Paths with Multiple Delay-Bounds  

Microsoft Academic Search

\\u000a The quickest path problem deals with the transmission of a message of size ? from a source to a destination with the minimum end-to-end delay over a network with bandwidth and delay constraints on the\\u000a links. We adapt properties of the quickest path to solve the delay-bounded minimum-cost (DBMC) path problem that is known\\u000a to be the NP-hard. In this

Young-cheol Bang; Inki Hong; Sungchang Lee; Byungjun Ahn

2004-01-01

189

The Exact Subgraph Recoverable Robust Shortest Path Problem  

NASA Astrophysics Data System (ADS)

Passengers of a public transportation system are often forced to change their planned route due to deviation in travel times. Rerouting is mostly done by simple means such as announcements. We introduce a model, in which the passenger computes his optimal route on his mobile device in a given subnetwork according to the actual travel times. Those travel times are sent to him as soon as a delay occurs.

Büsing, Christina

190

Visibility-Polygon Search and Euclidean Shortest Paths  

Microsoft Academic Search

Consider a collection of disjoint polygons in the plane containing a total of n edges. We show how to build, in O(n2) time and space, a data structure from which in O(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the

Takao Asano; Tetsuo Asano; Leonidas J. Guibas; John Hershberger; Hiroshi Imai

1985-01-01

191

A computational study of routing algorithms for realistic transportation networks  

SciTech Connect

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

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

1998-12-01

192

Formal Language Constrained Path Problems  

Microsoft Academic Search

Given an alphabet ?, a (directed) graph G whose edges are weighted and ?-labeled, and a formal language L ? ??, the formal-language-constrained shortest\\/simple path problem con- sists of finding a shortest (simple) path p in G complying with the additional constraint that l(p) ? L. Here l(p) denotes the unique word obtained by concatenating the ?-labels of the edges

Christopher L. Barrett; Riko Jacob; Madhav V. Marathe

1998-01-01

193

Automatic navigation path generation based on two-phase adaptive region-growing algorithm for virtual angioscopy.  

PubMed

In this paper, we propose a fast and automated navigation path generation algorithm to visualize inside of carotid artery using MR angiography images. The carotid artery is one of the body regions not accessible by real optical probe but can be visualized with virtual endoscopy. By applying two-phase adaptive region-growing algorithm, the carotid artery segmentation is started at the initial seed, which is located on the initially thresholded binary image. This segmentation algorithm automatically detects the branch position with stack feature. Combining with a priori knowledge of anatomic structure of carotid artery, the detected branch position is used to separate the carotid artery into internal carotid artery and external carotid artery. A fly-through path is determined to automatically move the virtual camera based on the intersecting coordinates of two bisectors on the circumscribed quadrangle of segmented carotid artery. In consideration of the interactive rendering speed and the usability of standard graphic hardware, endoscopic view of carotid artery is generated by using surface rendering algorithm with perspective projection method. In addition, the endoscopic view is provided with ray casting algorithm for off-line navigation of carotid artery. Experiments have been conducted on both mathematical phantom and clinical data sets. This algorithm is more effective than key-framing and topological thinning method in terms of automated features and computing time. This algorithm is also applicable to generate the centerline of renal artery, coronary artery, and airway tree which has tree-like cylinder shape of organ structures in the medical imagery. PMID:16112889

Kim, Do-Yeon; Chung, Sung-Mo; Park, Jong-Won

2005-08-19

194

Algorithms for Network Interdiction and Fortification Games  

Microsoft Academic Search

This chapter explores models and algorithms applied to a class of Stackelberg games on networks. In these network interdictiongames, a network exists over which an operator wishes to execute some function, such as finding a shortest path, shipping\\u000a a maximum flow, or transmitting a minimum cost multicommodity flow. The role of the interdictor is to compromise certain network\\u000a elements before

J. Cole Smith; Churlzu Lim

195

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

NASA Astrophysics Data System (ADS)

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

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

2010-01-01

196

Algorithms for time–optimal control of CNC machines along curved tool paths  

Microsoft Academic Search

The problem of specifying the feedrate variation along a curved path, that yields minimum traversal time for a 3-axis CNC machine subject to constraints on the feasible acceleration along each axis, is addressed. In general, this time–optimal feedrate incurs “bang–bang control,” i.e., maximum acceleration\\/deceleration is demanded of at least one axis throughout the motion. For a path defined by a

Sebastian D. Timar; Rida T. Farouki; Tait S. Smith; Casey L. Boyadjieff

2005-01-01

197

Dynamic integrated path-protection algorithms in IP over WDM networks under shared-risk-link-groups constraints  

NASA Astrophysics Data System (ADS)

The Shared Risk Link Groups (SRLG) concept is an extension of physical-disjoint, e.g. link/node-disjoint. It is defined as a group of links that shore a common risk component whose failure can potentially cause the failure of all the links in the group. SRLG can be identified by a SRLG identifier. Different SRLG identifiers can be assigned to each link by network administrator in optical Traffic Engineering (TE) to satisfy connection's reliability requirement. A dependable connection can be achieved by establishing two SRLG-disjoint paths. A new dynamic integrated routing algorithm for shared path-protection based on SRLG-disjoint is presented in the paper. It provides the same level of protection against SRLG failure as dedicated path-protection scheme. Moreover it is superior to dedicated path-protection scheme in network utilization. Network performance, based on dynamic traffic with different load, is investigated via simulations. The results show that the scheme can improve the performance of the network significantly.

He, Rongxi; Li, Lemin; Wang, Sheng

2002-09-01

198

An Efficient Path Computation Model for Hierarchically Structured Topographical Road Maps  

Microsoft Academic Search

In this paper, we have developed a HiT i (Hierarchical MulTi) graph model for structuring large topographical road maps to speed up the minimum cost route computation. The HiT i graph model provides a novel approach to abstracting and structuring a topographical road map in a hierarchical fashion. We propose a new shortest path algorithm named SP AH, which utilizes

Sungwon Jung; Sakti Pramanik

2002-01-01

199

A Unified Approach to Path Problems  

Microsoft Academic Search

A general method is described for solving path problems on directed graphs. Such path problems include finding shortest paths, solving sparse systems of hnear equaUons, and carrying out global flow analysis of computer programs The method consists of two steps First, a collecUon of regular expressions representmg sets of paths m the graph Is constructed This can be done by

Robert Endre Tarjan; TAR JAN

1981-01-01

200

A comparison of model-based path control algorithms for direct-drive SCARA robots  

Microsoft Academic Search

Various advanced control strategies are applied to a direct-drive SCARA robot and studied in computer simulations. Besides computed torque control and direct adaptive control, heuristic optimal control, a new path control scheme for robotic manipulators, is included in the comparison study. PD control, the traditional robot control method, is used for generating a comparing baseline. While all schemes are applied

Günther Schmidt; Xiaoming Xu

1992-01-01

201

In search of preferential flow paths in structured porous media using a simple genetic algorithm  

Microsoft Academic Search

Fracture network and preferential flow path images from exposed outcrops of geological formations, exposed soil pedon faces, and extracted soil columns and rock cores are often used to conceptualize and construct models to predict the fate and transport of subsurface contaminants. Both the scale resolutions inherent in these observations and the upscaling methods used to obtain macroscopic flow and transport

Jin-Ping Gwo

2001-01-01

202

Stability analysis of an online algorithm for torque limited path following  

Microsoft Academic Search

A secondary controller for online time scaling of nominal high-performance trajectories has been proposed to handle path following with torques close to the limits. Such nominal reference trajectories are typically available from an offline optimization. The stability properties of a closed-loop system including a robot, a primary controller, and a new secondary controller are studied. The analysis shows that if

Ola Dahl; Lars Nielsen

1990-01-01

203

Studying Convergence of Markov Chain Monte Carlo Algorithms Using Coupled Sample Paths  

Microsoft Academic Search

I describe a simple procedure for investigating the convergence properties of Markov chain Monte Carlo sampling schemes. The procedure uses coupled chains from the same sampler, obtained by using the same sequence of random deviates for each run. By examining the distribution of the iteration at which all sample paths couple, convergence properties for the system can be established. The

Valen E. Johnson

1996-01-01

204

A New Variable-Step-Size LMS Algorithm and Its Application in FM Broadcast-Based Passive Radar MultiPath Interference Cancellation  

Microsoft Academic Search

A new variable-step-size (VSS) LMS algorithm is proposed, and its performance is analyzed. Simulation results indicate that the performance is superior to that of existing VSS algorithm. The proposed algorithm is then applied to multi-path interference (MPI) cancellation in FM broadcast-based passive radar; experiments shows over 40 dB of MPI can be cancelled and a fast convergence rate as well

Shentang Li; Hong Wan; Wenjun Huo; Zhigang Wang

2007-01-01

205

Calibration of Neural Networks Using Genetic Algorithms, with Application to Optimal Path Planning.  

National Technical Information Service (NTIS)

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

T. R. Smith G. A. Pitney D. Greenwood

1987-01-01

206

The Research on the Path Optimization of Container Truck Based on Ant Colony Algorithm and MAS  

Microsoft Academic Search

This paper applies the up-to-date intelligent simulation ant colony algorithm to dynamic container truck scheduling. It proposes to take in real-time traffic information through GPS and to solve the problem on container truck scheduling with consideration of the optimal capability of ant colony in the searching process of food resources. Meanwhile, it puts information entropy into ant colony algorithm to

Li Guang-ru; Zhi Sun

2010-01-01

207

An Island Model Based Ant System with Lookahead for the Shortest Supersequence Problem  

Microsoft Academic Search

In this paper we introduce an Ant Colony Optimisation (ACO) algorithm for the Shortest Common Supersequence (SCS) problem,\\u000a which has applications in production system planning, mechanical engineering and molecular biology. The ACO algorithm is used\\u000a to find good parameters for a heuristic for the SCS problem. An island model with several populations of ants is used for\\u000a the ACO algorithm.

René Michel; Martin Middendorf

1998-01-01

208

A SAGE Algorithm for Estimation of the Direction Power Spectrum of Individual Path Components  

Microsoft Academic Search

In this contribution, the Fisher-Bingham-5 (FB5) probability density function (pdf) is used to model the shape of the direction power spectral density function (psdf) of individual path components in the radio channel. The FB5 distribution is selected because, among all direction distributions, it maximizes the entropy under the constraints that the first and second distribution moments are specified. A SAGE

Xuefeng Yin; Lingfeng Liu; Daniel K. Nielsen; Troels Pedersen; Bernard H. Fleury

2007-01-01

209

Path planning algorithm based on sub-region for agricultural robot  

Microsoft Academic Search

This paper proposes a agricultural robot's complete coverage path-planning method based on sub-region to avoid the overabundance of turns in narrow areas. First, a given environment is divided into several sub-regions without preserves. Second, the robot finds out the covering order of subregions by transforming it into the problem of Depth-First Search (DFS), and then it can cover all sub-regions

Guoyu Zuo; Peng Zhang; Junfei Qiao

2010-01-01

210

Efficient path profiling  

Microsoft Academic Search

A path profile determines how many times each acyclic path in a routine executes. This type of profiling subsumes the more common basic block and edge profiling, which only approximate path frequencies. Path profiles have many potential uses in program performance tuning, profile-directed compilation, and software test coverage. This paper describes a new algorithm for path profiling. This simple, fast

Thomas Ball; James R. Larus

1996-01-01

211

Approximating cycles in a shortest basis of the first homology group from point data  

NASA Astrophysics Data System (ADS)

Inference of topological and geometric attributes of a hidden manifold from its point data is a fundamental problem arising in many scientific studies and engineering applications. In this paper, we present an algorithm to compute a set of cycles from a point data that presumably sample a smooth manifold M\\subset {R}^d. These cycles approximate a shortest basis of the first homology group {\\sf H}_1(M) over coefficients in the finite field {Z}_2. Previous results addressed the issue of computing the rank of the homology groups from point data, but there is no result on approximating the shortest basis of a manifold from its point sample. In arriving at our result, we also present a polynomial time algorithm for computing a shortest basis of {\\sf H}_1({ K}) for any finite simplicial complex { K} whose edges have non-negative weights.

Dey, Tamal K.; Sun, Jian; Wang, Yusu

2011-12-01

212

A novel algorithm to identifying vehicle travel path in elevated road area based on GPS trajectory data  

NASA Astrophysics Data System (ADS)

In recent years, the increasing development of traffic information collection technology based on floating car data has been recognized, which gives rise to the establishment of real-time traffic information dissemination system in many cities. However, the recent massive construction of urban elevated roads hinders the processing of corresponding GPS data and further extraction of traffic information (e.g., identifying the real travel path), as a result of the frequent transfer of vehicles between ground and elevated road travel. Consequently, an algorithm for identifying the travel road type (i.e., elevated or ground road) of vehicles is designed based on the vehicle traveling features, geometric and topological characteristics of the elevated road network, and a trajectory model proposed in the present study. To be specific, the proposed algorithm can detect the places where a vehicle enters, leaves or crosses under elevated roads. An experiment of 10 sample taxis in Shanghai, China was conducted, and the comparison of our results and results that are obtained from visual interpretation validates the proposed algorithm.

Xu, Xianrui; Li, Xiaojie; Hu, Yujie; Peng, Zhongren

2012-12-01

213

The stencil buffer sweep plane algorithm for 5-axis CNC tool path verification  

Microsoft Academic Search

A new algorithm based on the sweep plane approach to determine the machined part geometry in 5-axis machining with general APT tools is presented. Undercut and overcut can be determined. Collision detection between the toolholder, workpiece and workpiece fixture can also be detected. The subtraction of the removed material is obtained for each sweep plane by using a stencil buffer.

Erik L. J. Bohez; Nguyen Thi Hong Minh; Ben Kiatsrithanakorn; Peeraphan Natasukon; Huang Ruei-yun; Le Thanh Son

2003-01-01

214

MyTwigStack: A Holistic Twig Join Algorithm with Effective Path Merging Support  

Microsoft Academic Search

While an XML database consists of a collection of data trees, an XML query is essentially a tree pattern associated with selection predicates. Various structural join algorithms have been designed to obtain the matches of a tree pattern within an XML database, and more recently, holistic twig joins were proposed as better alternatives to structural joins. The proposed twig join

Dunren Che

2006-01-01

215

Loop-Free Hybrid Single-Path\\/Flooding Routing Algorithms with Guaranteed Delivery for Wireless Networks  

Microsoft Academic Search

In a localized routing algorithm, each node makes forwarding decisions solely based on the position of itself, its neighbors, and its destination. In distance, progress, and direction-based approaches (reported in the literature), when node A wants to send or forward message m to destination node D, it forwards m to its neighbor C which is closest to D (has best

Ivan Stojmenovic; Xu Lin

2001-01-01

216

A Novel Multiple Particle Tracking Algorithm for Noisy in Vivo Data by Minimal Path Optimization within the Spatio-Temporal Volume  

Microsoft Academic Search

Automated tracking of fluorescent particles in living cells is vital for subcellular stoichoimetry analysis. Here, a new automatic tracking algorithm is described to track multiple particles, based on minimal path optimization. After linking feature points frame-by-frame, spatio-temporal data from time-lapse microscopy are combined together to construct a transformed 3D volume. The trajectories are then generated from the minimal energy path

Quan Xue; Mark C. Leake

2009-01-01

217

Optimally computing a shortest weakly visible line segment inside a simple polygon  

Microsoft Academic Search

A simple polygon is said to be weakly internally visible from a line segment lyinginside it if every point on the boundary of the polygon is visible from some point onthe line segment. In this paper, we present an optimal linear-time algorithm for thefollowing problem: Given a simple polygon, either compute a shortest line segmentfrom which the polygon is weakly

Binay K. Bhattacharya; Gautam Das; Asish Mukhopadhyay; Giri Narasimhan

2002-01-01

218

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

219

Source selectable path diversity via routing deflections  

Microsoft Academic Search

We present the design of a routing system in which end-systems set tags to select non-shortest path routes as an alternative to explicit source routes. Routers collectively generate these routes by using tags as hints to independently deflect packets to neighbors t hat lie off the shortest-path. We show how this can be done simply, by local extensions of the

Xiaowei Yang; David Wetherall

2006-01-01

220

A Novel Near-Land Radiometer Wet Path-Delay Retrieval Algorithm: Application to the Jason2\\/OSTM Advanced Microwave Radiometer  

Microsoft Academic Search

An algorithm is developed to retrieve wet tropospheric path delay (PD) near land from a satellite microwave radiometer to improve coastal altimetry studies. Microwave radiometers are included on ocean altimetry missions to retrieve the wet PD, but their performance has been optimized for retrievals in the open ocean. Near land, the radiometer footprint contains a mixture of radiometrically warm land

Shannon Brown

2010-01-01

221

Path planning for UAVs  

Microsoft Academic Search

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

S. A. Bortoff; E. Hartford

2000-01-01

222

A coding-aware routing algorithm in satellite networks  

NASA Astrophysics Data System (ADS)

Recently, providing reliable transmission over satellite networks is still a challenging problem due to the dynamic changes of the satellite topology, the large delay and the high error rate of the satellites' links. The benefits of network coding are well understood to solve those problems above for a large class of wireless networks. In this paper, a new coding-aware routing algorithm is proposed to decrease the large delay and improve the transmission efficiency by performing network coding opportunistically instead of using network coding always or using the shortest path routing only. The theoretical analysis and simulation results show the correctness and effectiveness of the proposed algorithm.

Zhang, Li; Xiao, Song; Cai, Ning; Du, Jianchao

2012-10-01

223

A labeling algorithm for the navigation of automated guided vehicles  

SciTech Connect

Material handling is an important component of most automated manufacturing systems. AGVs are commonly employed for this function. Efficient use of the AGV system requires proper routing and scheduling of vehicular traffic. This problem is modeled as a shortest path problem with multiple time windows on arcs and at nodes of a network. A polynomial-time labeling algorithm has been developed. The algorithm has complexity O (D[sup 2]log[sub d]D), where D is the total number of time windows in the problem. The data required for the model is easy to maintain.

Huang, J.; Palekar, U.S.; Kapoor, S.G. (Univ. of Illinois, Urbana, IL (United States). Dept. of Mechanical and Industrial Engineering)

1993-08-01

224

Algorithm Engineering: Concepts and Practice  

NASA Astrophysics Data System (ADS)

Over the last years the term algorithm engineering has become wide spread synonym for experimental evaluation in the context of algorithm development. Yet it implies even more. We discuss the major weaknesses of traditional "pen and paper" algorithmics and the ever-growing gap between theory and practice in the context of modern computer hardware and real-world problem instances. We present the key ideas and concepts of the central algorithm engineering cycle that is based on a full feedback loop: It starts with the design of the algorithm, followed by the analysis, implementation, and experimental evaluation. The results of the latter can then be reused for modifications to the algorithmic design, stronger or input-specific theoretic performance guarantees, etc. We describe the individual steps of the cycle, explaining the rationale behind them and giving examples of how to conduct these steps thoughtfully. Thereby we give an introduction to current algorithmic key issues like I/O-efficient or parallel algorithms, succinct data structures, hardware-aware implementations, and others. We conclude with two especially insightful success stories—shortest path problems and text search—where the application of algorithm engineering techniques led to tremendous performance improvements compared with previous state-of-the-art approaches.

Chimani, Markus; Klein, Karsten

225

Multipath Routing Algorithm Applied to Cloud Data Center Services  

NASA Astrophysics Data System (ADS)

Cloud data center services, such as video on demand (VoD) and sensor data monitoring, have become popular. The quality of service (QoS) between a client and a cloud data center should be assured by satisfying each service's required bandwidth and delay. Multipath traffic engineering is effective for dispersing traffic flows on a network; therefore, an improved k-shortest paths first (k-SPF) algorithm is applied to these cloud data center services to satisfy their required QoS. k-SPF can create a set of multipaths between a cloud data center and all edge routers, to which client nodes are connected, within one algorithm process. Thus, k-SPF can produce k shortest simple paths between a cloud data center and every access router faster than with conventional Yen's algorithm. By using a parameter in the algorithm, k-SPF can also impartially use links on a network and shorten the average hop-count and number of necessary MPLS labels for multiple paths that comprise a multipath.

Matsuura, Hiroshi

226

Dynamic waveband switching algorithms based on the layered graph  

NASA Astrophysics Data System (ADS)

In this paper, we proposed two waveband switching algorithms: Minimal Hop Routing (MHP) and Maximal Overlapped Routing (MOP). The differences between them are the weight of link in the layered graph at the waveband and wavelength planes. In MHP algorithm, the weight of links at waveband and wavelength planes are the same, but MOP assigns lower weight to them at the waveband plane than that at the wavelength plane. We conducted extensive simulations with dynamic traffic patterns in the mesh network topology. We evaluated the performance of the proposed algorithms in terms of blocking probability and the number of OXCs port with waveband algorithms of MOP, MHP and RWA algorithm of shortest path routing (SPR). Simulation result shows that waveband algorithm has low blocking probability, and less number of ports is used.

Huang, Jun; Qiu, Shaofeng; Dengbingguang, -; Liu, Jimin

2005-10-01

227

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

228

Binary Decision Diagrams: A Mathematical Model for the Path-Related Objective Functions  

Microsoft Academic Search

This paper describes a mathematical model for all path length parameters (APL: Average Path Length, LPL: Longest Path Length, and SPL: Shortest Path Length) of Binary Decision Diagrams (BDDs). The proposed model is based on an empirical analysis of randomly generated Boolean functions. The formal core of the developed model is a unique equation for the path-related objective functions over

P. W. C. PRASAD; ALI ASSI; BRUCE MILLS

2006-01-01

229

3D Motion Planning Algorithms for Steerable Needles Using Inverse Kinematics  

PubMed Central

Steerable needles can be used in medical applications to reach targets behind sensitive or impenetrable areas. The kinematics of a steerable needle are nonholonomic and, in 2D, equivalent to a Dubins car with constant radius of curvature. In 3D, the needle can be interpreted as an airplane with constant speed and pitch rate, zero yaw, and controllable roll angle. We present a constant-time motion planning algorithm for steerable needles based on explicit geometric inverse kinematics similar to the classic Paden-Kahan subproblems. Reachability and path competitivity are analyzed using analytic comparisons with shortest path solutions for the Dubins car (for 2D) and numerical simulations (for 3D). We also present an algorithm for local path adaptation using null-space results from redundant manipulator theory. Finally, we discuss several ways to use and extend the inverse kinematics solution to generate needle paths that avoid obstacles.

Duindam, Vincent; Xu, Jijie; Alterovitz, Ron; Sastry, Shankar; Goldberg, Ken

2010-01-01

230

Towards generating diverse topologies of path tracing compliant mechanisms using a local search based multi-objective genetic algorithm procedure  

Microsoft Academic Search

A new bi-objective optimization problem is for- mulated for generating the diverse topologies of compliant mechanisms tracing a user-defined path. Motivation behind the present study is to generate the compliant mechanisms which perform the same task of tracing a prescribed trajectory near minimum-weight solution. Therefore, the constraint are imposed at each precision point representing a prescribed path for accomplishing the

Deepak Sharma; Kalyanmoy Deb; N. N. Kishore

2008-01-01

231

Path planning for a mobile robot  

Microsoft Academic Search

Two problems for path planning of a mobile robot are considered. The first problem is to find a shortest-time, collision-free path for the robot in the presence of stationary obstacles in two dimensions. The second problem is to determine a collision-free path (greedy in time) for a mobile robot in an environment of moving obstacles. The environment is modeled in

Christos Alexopoulos; Paul M. Griffin

1992-01-01

232

The Longest Shortest Fence and Sharp Poincaré-Sobolev Inequalities  

NASA Astrophysics Data System (ADS)

We prove a long standing conjecture concerning the fencing problem in the plane: among planar convex sets of given area, the disc, and only the disc, maximizes the length of the shortest area-bisecting curve. Although it may look intuitive, the result is by no means trivial since we also prove that among planar convex sets of given area the set which maximizes the length of the shortest bisecting chords is the so-called Auerbach triangle.

Esposito, L.; Ferone, V.; Kawohl, B.; Nitsch, C.; Trombetti, C.

2012-12-01

233

SP-NN: A novel neural network approach for path planning  

Microsoft Academic Search

In this paper, a neural network approach named shortest path neural networks (SP-NN) is proposed for real-time on-line path planning. Based on grid-based map and mapping this kind of map to neural networks, this proposed method is capable of generating the globally shortest path from the target position to the start position without collision with any obstacles. The dynamics of

Shuai Li; Max Q. H. Meng; Wanming Chen; Yangming Li; Zhuhong You; Yajin Zhou; Lei Sun; Huawei Liang; Kai Jiang; Qinglei Guo

2007-01-01

234

Reimann surfaces with shortest geodesic of maximal length  

Microsoft Academic Search

I describe Riemann surfaces of constant curvature -1 with the property that the length of its shortest simple closed geodesic is maximal with respect to an open neighborhood in the corresponding Teichmüller space. I give examples of such surfaces. In particular, examples are presented which are modelled upon (Euclidean) polyhedra. This problem is a non-Euclidean analogue of the well known

P. Schmutz

1993-01-01

235

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

SciTech Connect

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

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

1997-04-01

236

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

PubMed Central

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

Kaiser, Marcus; Hilgetag, Claus C

2006-01-01

237

Optimal paths for a car that goes both forwards and backwards  

Microsoft Academic Search

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

J. A. Reeds; L. A. Shepp

1990-01-01

238

IP-oriented control of unidirectional-path-switched-ring-based transport networks  

NASA Astrophysics Data System (ADS)

An important requirement in the IP-based control of time-division multiplexing (TDM) optical transport networks is to utilize the in-built protection capabilities of synchronous optical network (SONET) unidirectional path-switched rings (UPSRs) and to automate the UPSR-protected path setup in mixed mesh-ring networks. This requires modifications to existing IP signaling and routing protocols and new processing rules at the network nodes. Here we leverage IP routing and signaling and multiprotocol label switching (MPLS) fast-reroute techniques for accurately advertising UPSR ring topologies to remote nodes and dynamically establishing UPSR-protected paths across a transport network. Our proposal also makes a NUT1-like (nonpreemptible unprotected traffic) feature possible in UPSRs, which allows for efficient utilization of UPSR protection bandwidth. We achieve this by encoding UPSR-specific information in the open shortest-path-first (OSPF) link state advertisements and in signaling messages of the Resource Reservation Protocol (RSVP) with TE extensions. In addition, we modify the signaling and routing state machines at the nodes to interpret and process this information to perform UPSR topology discovery and path computation. The uniqueness of our proposals is that the algorithms and the rules specified here allow for existing IP-based protocols [such as those within the generalized MPLS (GMPLS) framework, which currently applies to mesh networks] to be efficiently adapted for this context while still achieving our objective of exploiting UPSR-protection capabilities.

Sharma, Vishal; Das, Abhimanyu; Chen, Charles

2003-03-01

239

Minimum Wheel-rotation Paths for Differential-drive Mobile Robots  

Microsoft Academic Search

The shortest paths for a mobile robot are a fundamental property of the mechanism, and may also be used as a family of primitives for mo- tion planning in the presence of obstacles. This paper characterizes shortest paths for differential-drive mobile robots, with the goal of classifying solutions in the spirit of Dubins curves and Reeds-Shepp curves for car-like robots.

Hamid Reza Chitsaz; Steven M. Lavalle; Devin J. Balkcom; Matthew T. Mason

2006-01-01

240

On path selection for traffic with bandwidth guarantees  

Microsoft Academic Search

Transmission of multimedia streams imposes a minimum-band width requirementon the path being used to ensure end-to-end Qual ity-of- Service (QoS) guarantees. While any shortest-path algorit hm can be used to select a feasible path, additional constraints th at limit resource consumption and balance the network load are neede d to achieve efficient resource utilization. We present a syst ematic evaluation

Qingming Ma; Peter Steenkiste

1997-01-01

241

Intrinsic shortest path length: a new, accurate a priori wirelength estimator  

Microsoft Academic Search

A priori wirelength estimation is concerned with predicting various wirelength characteristics before placement. In this work we propose a novel, accurate estimator of net lengths. We observe that in \\

Andrew B. Kahng; Sherief Reda

2005-01-01

242

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…

Fazlollahtabar, Hamed

2008-01-01

243

Persistence Search - A New Search Strategy for the Dynamic Shortest Path Problem.  

National Technical Information Service (NTIS)

The research reported in this paper deals with the problem of searching through an unknown terrain by a physical agent such as a robot. The unknown terrain over which the agent will travel is represented by an undirected graph. The agent has no prior know...

M. M. Mayer M. T. Shing

1991-01-01

244

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

245

The approach for shortest paths in fire succor based on component GIS technology  

Microsoft Academic Search

Fire safety is an important issue for the national economy and people's living. Efficiency and exactness of fire department succor directly relate to safety of peoples' lives and property. Many disadvantages of the traditional fire system have been emerged in practical applications. The preparation of pumpers is guided by wireless communication or wire communication, so its real-time and accurate performances

Jie Han; Yong Zhao; K. W. Dai

2007-01-01

246

Modelling spatial substructure in wildlife populations using an approximation to the shortest path Voronoi Diagram  

Microsoft Academic Search

In the field of conservation biology, accurate population models are important for managing wildlife. It has been acknowledged that spatial structure should form an integral part of such models. Advancement in the power of desktop computers has allowed biologists to construct individual-based, spatially-explicit simulation models to predict the population dynamics of species. These models take into account local interactions and

C. W. Stewart; R. van der Ree

247

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

PubMed Central

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

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

2007-01-01

248

A time slot assignment algorithm for a TDMA packet radio network  

NASA Astrophysics Data System (ADS)

An algorithm for the assignment of time slots within a Time Division Multiple Access (TDMA) scheme for an integrated voice and packet radio network is implemented in, and studied by, a computer simulation. The slot assignment scheme is applied both to a static network, where "best path' routes are held constant, and also to a network where the "best path' routes are permitted to change dynamically during the simulation as communications capability at various nodes approaches saturation. The Dijkstra algorithm is used to determine and modify "shortest distance' routes, and the sensitivity of performance to various parameters used in defining the link "distance function' is investigated. The major conclusion is that it is possible to route in a way that reduces the average energy transmitted per message without substantially decreasing the network throughput.

Tritchler, W. K.

1983-03-01

249

Sampling diffusive transition paths  

SciTech Connect

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

F. Miller III, Thomas; Predescu, Cristian

2006-10-12

250

A Flexible Reservation Algorithm for Advance Network Provisioning  

SciTech Connect

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

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

2010-04-12

251

Dispersion of nonlinear group velocity determines shortest envelope solitons  

SciTech Connect

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

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

2011-10-15

252

Automatic 3D neuron tracing using all-path pruning  

PubMed Central

Motivation: Digital reconstruction, or tracing, of 3D neuron structures is critical toward reverse engineering the wiring and functions of a brain. However, despite a number of existing studies, this task is still challenging, especially when a 3D microscopic image has low signal-to-noise ratio (SNR) and fragmented neuron segments. Published work can handle these hard situations only by introducing global prior information, such as where a neurite segment starts and terminates. However, manual incorporation of such global information can be very time consuming. Thus, a completely automatic approach for these hard situations is highly desirable. Results: We have developed an automatic graph algorithm, called the all-path pruning (APP), to trace the 3D structure of a neuron. To avoid potential mis-tracing of some parts of a neuron, an APP first produces an initial over-reconstruction, by tracing the optimal geodesic shortest path from the seed location to every possible destination voxel/pixel location in the image. Since the initial reconstruction contains all the possible paths and thus could contain redundant structural components (SC), we simplify the entire reconstruction without compromising its connectedness by pruning the redundant structural elements, using a new maximal-covering minimal-redundant (MCMR) subgraph algorithm. We show that MCMR has a linear computational complexity and will converge. We examined the performance of our method using challenging 3D neuronal image datasets of model organisms (e.g. fruit fly). Availability: The software is available upon request. We plan to eventually release the software as a plugin of the V3D-Neuron package at http://penglab.janelia.org/proj/v3d. Contact: pengh@janelia.hhmi.org

Peng, Hanchuan; Long, Fuhui; Myers, Gene

2011-01-01

253

Hybridisations Of Simulated Annealing And Modified Simplex Algorithms On A Path Of Steepest Ascent With Multi-Response For Optimal Parameter Settings Of ACO  

NASA Astrophysics Data System (ADS)

Many entrepreneurs face to extreme conditions for instances; costs, quality, sales and services. Moreover, technology has always been intertwined with our demands. Then almost manufacturers or assembling lines adopt it and come out with more complicated process inevitably. At this stage, products and service improvement need to be shifted from competitors with sustainability. So, a simulated process optimisation is an alternative way for solving huge and complex problems. Metaheuristics are sequential processes that perform exploration and exploitation in the solution space aiming to efficiently find near optimal solutions with natural intelligence as a source of inspiration. One of the most well-known metaheuristics is called Ant Colony Optimisation, ACO. This paper is conducted to give an aid in complicatedness of using ACO in terms of its parameters: number of iterations, ants and moves. Proper levels of these parameters are analysed on eight noisy continuous non-linear continuous response surfaces. Considering the solution space in a specified region, some surfaces contain global optimum and multiple local optimums and some are with a curved ridge. ACO parameters are determined through hybridisations of Modified Simplex and Simulated Annealing methods on the path of Steepest Ascent, SAM. SAM was introduced to recommend preferable levels of ACO parameters via statistically significant regression analysis and Taguchi's signal to noise ratio. Other performance achievements include minimax and mean squared error measures. A series of computational experiments using each algorithm were conducted. Experimental results were analysed in terms of mean, design points and best so far solutions. It was found that results obtained from a hybridisation with stochastic procedures of Simulated Annealing method were better than that using Modified Simplex algorithm. However, the average execution time of experimental runs and number of design points using hybridisations were longer than those using a single method when compared. Finally they stated a recommendation of proper level settings of ACO parameters for all eight functions that can be used as a guideline for future applications of ACO. This is to promote ease of use of ACO in real life problems.

Luangpaiboon, P.

2009-10-01

254

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

PubMed Central

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

Jan, Shau Shiun; Lin, Yu Hsiang

2011-01-01

255

Integrated flight path planning system and flight control system for unmanned helicopters.  

PubMed

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-07-28

256

A star recognition method based on the Adaptive Ant Colony algorithm for star sensors.  

PubMed

A new star recognition method based on the Adaptive Ant Colony (AAC) algorithm has been developed to increase the star recognition speed and success rate for star sensors. This method draws circles, with the center of each one being a bright star point and the radius being a special angular distance, and uses the parallel processing ability of the AAC algorithm to calculate the angular distance of any pair of star points in the circle. The angular distance of two star points in the circle is solved as the path of the AAC algorithm, and the path optimization feature of the AAC is employed to search for the optimal (shortest) path in the circle. This optimal path is used to recognize the stellar map and enhance the recognition success rate and speed. The experimental results show that when the position error is about 50?, the identification success rate of this method is 98% while the Delaunay identification method is only 94%. The identification time of this method is up to 50 ms. PMID:22294908

Quan, Wei; Fang, Jiancheng

2010-03-10

257

A Star Recognition Method Based on the Adaptive Ant Colony Algorithm for Star Sensors  

PubMed Central

A new star recognition method based on the Adaptive Ant Colony (AAC) algorithm has been developed to increase the star recognition speed and success rate for star sensors. This method draws circles, with the center of each one being a bright star point and the radius being a special angular distance, and uses the parallel processing ability of the AAC algorithm to calculate the angular distance of any pair of star points in the circle. The angular distance of two star points in the circle is solved as the path of the AAC algorithm, and the path optimization feature of the AAC is employed to search for the optimal (shortest) path in the circle. This optimal path is used to recognize the stellar map and enhance the recognition success rate and speed. The experimental results show that when the position error is about 50?, the identification success rate of this method is 98% while the Delaunay identification method is only 94%. The identification time of this method is up to 50 ms.

Quan, Wei; Fang, Jiancheng

2010-01-01

258

Tornado Paths  

NSDL National Science Digital Library

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

Samson, Perry; Michigan, University O.

259

Empirical Evaluation of Distributed Mutual Exclusion Algorithms  

Microsoft Academic Search

In this paper, we evaluated various distributed mutual exclusion algorithms on the IBM SP2 machine and the Intel iPSC\\/860 system. The empirical results are compared in terms of such criteria as the number of message exchanges and the response time. Our results indicate that the Star algorithm (2) achieves the shortest response time in most cases among all the algorithms

Shiwa S. Fu; Nian-feng Tzeng; Zhiyuan Li

1997-01-01

260

Removing False Paths from Combinational Modules 1  

Microsoft Academic Search

The existence of false paths complicates the task of accurate tim- ing analysis significantly. A technique to remove false paths from a combinational circuit without degrading its performance h as a prac- tical value since topological timing analysis is then good e nough to estimate the performance of false-path-free circuits accu rately. One can think of the KMS algorithm (1)

Yuji Kukimoto; Robert K. Brayton

261

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

262

Identification of biochemical network modules based on shortest retroactive distances.  

PubMed

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-11-10

263

Path Sensitization in Critical Path Problem  

Microsoft Academic Search

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

Hsi-chuan Chen; David Hung-chang Du

1991-01-01

264

A critical examination of stoichiometric and path-finding approaches to metabolic pathways.  

PubMed

Advances in the field of genomics have enabled computational analysis of metabolic pathways at the genome scale. Singular attention has been devoted in the literature to stoichiometric approaches, and path-finding approaches, to metabolic pathways. Stoichiometric approaches make use of reaction stoichiometry when trying to determine metabolic pathways. Stoichiometric approaches involve elementary flux modes and extreme pathways. In contrast, path-finding approaches propose an alternative view based on graph theory in which reaction stoichiometry is not considered. Path-finding approaches use shortest path and k-shortest path concepts. In this article we give a critical overview of the theory, applications and key research challenges of stoichiometric and path-finding approaches to metabolic pathways. PMID:18436574

Planes, Francisco J; Beasley, John E

2008-04-24

265

Traffic optimization in railroad networks using an algorithm mimicking an amoeba-like organism, Physarum plasmodium.  

PubMed

Traffic optimization of railroad networks was considered using an algorithm that was biologically inspired by an amoeba-like organism, plasmodium of the true slime mold, Physarum polycephalum. The organism developed a transportation network consisting of a tubular structure to transport protoplasm. It was reported that plasmodium can find the shortest path interconnecting multiple food sites during an adaptation process (Nakagaki et al., 2001. Biophys. Chem. 92, 47-52). By mimicking the adaptation process a path finding algorithm was developed by Tero et al. (2007). In this paper, the algorithm is newly modified for applications of traffic distribution optimization in transportation networks of infrastructure such as railroads under the constraint that the network topology is given. Application of the algorithm to a railroad in metropolitan Tokyo, Japan is demonstrated. The results are evaluated using three performance functions related to cost, traveling efficiency, and network weakness. The traffic distribution suggests that the modified Physarum algorithm balances the performances under a certain parameter range, indicating a biological process. PMID:21620930

Watanabe, Shin; Tero, Atsushi; Takamatsu, Atsuko; Nakagaki, Toshiyuki

2011-05-19

266

A routing protocol and routing algorithm for space communication  

NASA Astrophysics Data System (ADS)

The proposed research is a development a routing protocol for space that creates an infrastructure which enables routers on board spacecrafts to calculate near optimum routing tables ahead of time and on-demand when network changes occur. Our routing protocol for space communication, Space Open Shortest Path First (SOSPF), divides the routing domain (e.g., our solar system) into areas within areas which provides an orderly fashion of transmitting routing information throughout the routing domain. The concept of areas within SOSPF allows routing information of one area to be hidden within that area. In addition, since the trajectory of space crafts are either predictable (e.g., satellite constellation around Earth), preset (e.g., the International Space Station), or set on demand (e.g., a space shuttle), a router on board those spacecrafts calculates the time intervals where spacecrafts are in direct view with the calculating router and the propagation delays to those spacecrafts using the location of those spacecrafts and the local transmission capabilities. Then, those calculated values are dispersed throughout the routing domain. Also, this dissertation presents a routing algorithm which allows routers on board spacecrafts to use the received routing information (i.e., the time intervals and the propagation delay) to compute the routing table. This routing algorithm can compute shortest delay paths over conventional concurrent-link as well as intermittent-links using a store-and-forward communication scheme. Furthermore, this dissertation presents routing performance of this routing protocol in real space scenarios and shows how the SOSPF routing domain stays stable after link failures as the routing domain diameter grows to the end of our solar system.

Bantan, Nouman

267

Implementation of the spline method for mobile robot path control  

Microsoft Academic Search

This paper presents an implementation of a Spline Curve Algorithm in a mobile robot path-planning domain. This method is based on a continuous path mapped between two points. The path can easily be updated and modified as the robot moves. This feature makes the algorithm to be suitable for dynamic control as in the case of multiple mobile robots operating

Halit Eren; Chun Che Fung; Jeromy Evans

1999-01-01

268

Multiobjective evolutionary path planning via fuzzy tournament selection  

Microsoft Academic Search

The paper introduces a new selection algorithm that can be used for evolutionary path planning systems. This new selection algorithm combines fuzzy inference along with tournament selection to select candidate paths (CPs) to be parents based on: (1) the Euclidean distance from origin to destination, (2) the sum of the changes in the slope of a path, and (3) the

Gerry Dozier; Shaun Mccullough; Abdollah Homaifar; Eddie Tunstel; Loretta Moore

1998-01-01

269

Adaptive tool path planning applied in manufacturing optimization  

Microsoft Academic Search

Paper describes research done on algorithms for the generation of gouge-free nonisoparametric tool paths across surface plane segments obtained through triangulation partitioning. Along with contiguous trajectory sequences, adaptive tool path planning introduces partially discontinuous tool trajectories. Algorithm achieves the necessary trajectory continuity by the insertion of the auxiliary tool-orientation trajectories. The tool passes over the path gaps are accomplished through

J. Radej; L. Budin; Z. Mihajlovic

2004-01-01

270

A New Operating System Scheduling Algorithm  

NASA Astrophysics Data System (ADS)

The paper compares several kinds scheduling algorithm,which include First-Come,First-Served,Shortest-Job (process)-First, Highest Response Ratio Next. Each algorithm has some advantages or disadvantages.In order to take all the factors,such as first come job,shortest job,longest job,highest respones ratio job,and etc,the paper put forward a new operating system scheduling algorithm median-time slice-Highest Response Ratio Next, the method was proved to be feasible and effective after tested the five process sequence.

Nie, Bin; Du, Jianqiang; Xu, Guoliang; Liu, Hongning; Yu, Riyue; Wen, Quan

271

A Genetic Robot Path Planner with Fuzzy Logic Adaptation  

Microsoft Academic Search

The paper develops a combined genetic algorithm and fuzzy logic approach to path planning for a mobile robot operating in rough environments. Path planning consists of a description of the environment using a fuzzy logic framework, and a two-stage planner. A global planner determines the path that optimizes a combination of terrain roughness and path curvature. A local planner uses

Mahmoud Tarokh

2007-01-01

272

Applications of Path Compression on Balanced Trees  

Microsoft Academic Search

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

273

VIPER: an efficient vigorously sensitizable path extractor  

Microsoft Academic Search

Fast and correct timing verification is a critical issue in VLSI design. Several tim-ing verification algorithms have been proposed in the last few years. However, due to the huge computation time needed to eliminate false paths, existing algorithms have difficulty in performing timing verification for large circuits. This paper presents an efficient timing verification algorithm, with a new sensitization criterion,

Hoon Chang; Jacob A. Abraham

1993-01-01

274

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

Microsoft Academic Search

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

Vadim Lyubashevsky; Daniele Micciancio

2009-01-01

275

Soft computing algorithms for intelligent control of a mobile robot for service use: Part 2: Path planning, navigation and technology operations  

Microsoft Academic Search

The arrangement principles and design methodology on soft computing for complex control framework of AI control system in\\u000a Part 1 of this paper are developed. The basis of this methodology is computer simulation of dynamics for mechanical robotic\\u000a system with the help of qualitative physics and search for possible solutions by genetic algorithms (GA). In Part 2 optimal\\u000a solutions for

Takayuki Tanaka; Junji Ohwi; Ludmila V. Litvintseva; Kazuo Yamafuji; Sergei V. Ulyanov

1997-01-01

276

New robust algorithm for tracking cells in videos of Drosophila morphogenesis based on finding an ideal path in segmented spatio-temporal cellular structures.  

PubMed

In this paper, we present a novel algorithm for tracking cells in time lapse confocal microscopy movie of a Drosophila epithelial tissue during pupal morphogenesis. We consider a 2D + time video as a 3D static image, where frames are stacked atop each other, and using a spatio-temporal segmentation algorithm we obtain information about spatio-temporal 3D tubes representing evolutions of cells. The main idea for tracking is the usage of two distance functions--first one from the cells in the initial frame and second one from segmented boundaries. We track the cells backwards in time. The first distance function attracts the subsequently constructed cell trajectories to the cells in the initial frame and the second one forces them to be close to centerlines of the segmented tubular structures. This makes our tracking algorithm robust against noise and missing spatio-temporal boundaries. This approach can be generalized to a 3D + time video analysis, where spatio-temporal tubes are 4D objects. PMID:22255854

Bellaïche, Yohanns; Bosveld, Floris; Graner, François; Mikula, Karol; Remesíková, Mariana; Smísek, Michal

2011-01-01

277

Term Paths  

NSDL National Science Digital Library

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

Cynthia Ann Radle (McCullough High School REV)

1995-06-30

278

Routing and scheduling of hazardous materials shipments: algorithmic approaches to managing spent nuclear fuel transport  

SciTech Connect

Much controversy surrounds government regulation of routing and scheduling of Hazardous Materials Transportation (HMT). Increases in operating costs must be balanced against expected benefits from local HMT bans and curfews when promulgating or preempting HMT regulations. Algorithmic approaches for evaluating HMT routing and scheduling regulatory policy are described. A review of current US HMT regulatory policy is presented to provide a context for the analysis. Next, a multiobjective shortest path algorithm to find the set of efficient routes under conflicting objectives is presented. This algorithm generates all efficient routes under any partial ordering in a single pass through the network. Also, scheduling algorithms are presented to estimate the travel time delay due to HMT curfews along a route. Algorithms are presented assuming either deterministic or stochastic travel times between curfew cities and also possible rerouting to avoid such cities. These algorithms are applied to the case study of US highway transport of spent nuclear fuel from reactors to permanent repositories. Two data sets were used. One data set included the US Interstate Highway System (IHS) network with reactor locations, possible repository sites, and 150 heavily populated areas (HPAs). The other data set contained estimates of the population residing with 0.5 miles of the IHS and the Eastern US. Curfew delay is dramatically reduced by optimally scheduling departure times unless inter-HPA travel times are highly uncertain. Rerouting shipments to avoid HPAs is a less efficient approach to reducing delay.

Cox, R.G.

1984-01-01

279

Joint path and resource selection for OBS grids with adaptive offset based QoS mechanism  

Microsoft Academic Search

In this paper, we first propose a joint resource and path selection algorithm for optical burst switched grids. We show that path switching and network-aware resource selection can reduce burst loss probability and average completion time of grid jobs compared to the algorithms that are separately selecting paths and grid resources. In addition to joint resource and path selection, we

Mehmet Koseoglu; Ezhan Karasan

2007-01-01

280

Multicast Routing Algorithm for Nodal Load Balancing  

Microsoft Academic Search

The authors propose two multicast routing algorithms which distribute copy operation of packets over all nodes along the multicast path: a link-added type algorithm and a loop-constructed type algorithm. Both algorithms, at first, derive an approximate solution for minimum cast path, and then improve the solution to prevent concentration of packet copy operation at one switching node at a little

Hideki Tode; Yasuharu Sakai; Miki Yamamoto; Hiromi Okada; Yoshikazu Tezuka

1992-01-01

281

Automatic Navigation Algorithm in Virtual Complex Indoor Scenes  

Microsoft Academic Search

To meet the demand for efficient automatic navigation in virtual complex indoor scenes, this paper presents an automatic navigation algorithm. The algorithm uses Dijkstra algorithm for path planning on complex indoor scenes graph, and uses the adaptive vector length algorithm for Bezier curve control point to smooth the path. The paper indicates that path planning in indoor scene is a

Zeng Hong; Zhang Jundong; Jiang Ruizheng; Feng Jinhong

2011-01-01

282

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

283

THE PATH-PARTITION PROBLEM IN BIPARTITE DISTANCE-HEREDITARY GRAPHS  

Microsoft Academic Search

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

Hong-Gwa Yeh; Gerard J. Chang

1998-01-01

284

The BACK algorithm for sequential test generation  

Microsoft Academic Search

A test-generation algorithm called the BACK algorithm is proposed for sequential test generation. The BACK algorithm is a modified D-algorithm. Instead of forward fault propagation to generate sensitized paths, the BACK algorithm creates the sensitized paths backwards by justifying the required sensitized values. The BACK algorithm not only is easier to implement but also requires less run-time memory than the

Wu-Tung Cheng

1988-01-01

285

Path Generation and Tracking in 3-D for UAVs  

Microsoft Academic Search

In this brief, we consider the problem of 3-D path generation and tracking for unmanned air vehicles (UAVs). The proposed path generation algorithm allows us to find a path satisfying arbitrary initial and final conditions, specified in terms of position and velocity. Our method assumes that aircraft structural and dynamic limitations can be translated in a turn radius constraint; therefore,

G. Ambrosino; M. Ariola; U. Ciniglio; F. Corraro; E. De Lellis; A. Pironti

2009-01-01

286

Integrated path planning and dynamic steering control for autonomous vehicles  

Microsoft Academic Search

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

287

Integrated Path Planning and ynamic Steering Control for Autonomous Vehicles  

Microsoft Academic Search

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

288

An improved path planning approach based on Particle Swarm Optimization  

Microsoft Academic Search

In this paper, an improved path planning scheme based on Particle Swarm Optimization and Ferguson Splines is proposed. Firstly, a string of Ferguson Splines are used to describe a path for a mobile robot, and the path planning problem is then equivalent to the optimization of parameters of particular cubic Ferguson splines. Secondly, an improved Particle Swarm Optimization Algorithm, which

Wu Xianxiang; Ming Yan; Wang Juan

2011-01-01

289

Shortest Route Models for the Allocation of Inspection Effort on a Production Line  

Microsoft Academic Search

Two shortest route models for determining where to allocate inspection effort on a production line are developed for the cases where this effort is unlimited or limited in its availability. A production line is defined as an ordered sequence of production stages, each stage consisting of a manufacturing operation followed by a potential inspection station. Items flow through the line

Leon S. White

1969-01-01

290

The shortest processing time first (SPTF) dispatch rule and some variants in semiconductor manufacturing  

Microsoft Academic Search

Looking for appropriate dispatch rules for semiconductor fabrication facilities (wafer fabs), practitioners often intend to use the Shortest Processing Time First (SPTF) rule because it is said to reduce cycle times. In our study, we show, however, that this positive effect on cycle times can be achieved in single machine systems but not necessarily in complete wafer fabs. In addition,

Oliver Rose

2001-01-01

291

A Global Approach to Path Planning for Redundant Manipulators  

Microsoft Academic Search

An approach to the path planning of redundant manipulators is presented. The path planning problem is posed as a finite-time nonlinear control problem which can be solved by a Newton-Raphson type algorithm. This technique is capable of handling various goal task definitions, as well as incorporating both joint and task space constraints. The algorithm shows promising results in planning joint

Sanjeev Seereeram; John T. Wen

1993-01-01

292

A New Multiple Path Search Technique for Residual Vector Quantizers  

Microsoft Academic Search

Multiple path searching can provide varying degrees of joint search optimization of residual vector quantizer encoder stages. A short coming of the conventional multiple path M-search algorithm, however, is that joint search optimization of encoder stages is limited to consecutive stages. A new iterated multipath (IM)-search algorithm is introduced that is not subject to any particular ordering of the residual

Christopher F. Barnes

1994-01-01

293

Apple Harvesting Robot Picking Path Planning and Simulation  

Microsoft Academic Search

For an apple harvesting robot, the efficiency of harvesting mainly depends on picking path planning. To find the best route, this article studied ant colony algorithm, and presented an improved method in picking path optimization. In this athletics methods of picking, with binocular cameras, the coordinates of ripe apples were obtained, the improved ant colony algorithm was used to obtain

Yuan Yanwei; Zhang Xiaochao; Zhao Huaping

2009-01-01

294

Optimal path planning with obstacle avoidance for autonomous surveying  

Microsoft Academic Search

In order to perform surveying with an autonomous vehicle, a path must often be designed for geometrically complex boundaries, while also accounting for mapped obstacles. In this paper, several algorithms that solve different aspects of the problem are presented. Together, the algorithms generate a path with the following characteristics: (a) it completely covers a field given its respective corner points,

David W. Hodo; David M. Bevly; John Y. Hung; Scott Millhouse; Bob Selfridge

2010-01-01

295

Structural Factoring Approach for Analyzing Stochastic Networks.  

National Technical Information Service (NTIS)

The problem of finding the distribution of the shortest path length through a stochastic network is investigated. A general algorithm for determining the exact distribution of the shortest path length is developed based on the concept of conditional facto...

K. J. Hayhurst D. R. Shier

1991-01-01

296

Tool-path generation for Z-constant contour machining  

Microsoft Academic Search

For the Z-constant contour machining, a tool-path generation procedure is presented. The suggested procedure consists of two parts; (1) calculating the contours (tool-path-elements) by slicing the CL-surface with horizontal planes and (2) generating a tool-path by linking the contours. For the slicing algorithm, two algorithms are suggested, one is to slice a triangular mesh and the other is for a

Sang C. Park

2003-01-01

297

Steered transition path sampling.  

PubMed

We introduce a path sampling method for obtaining statistical properties of an arbitrary stochastic dynamics. The method works by decomposing a trajectory in time, estimating the probability of satisfying a progress constraint, modifying the dynamics based on that probability, and then reweighting to calculate averages. Because the progress constraint can be formulated in terms of occurrences of events within time intervals, the method is particularly well suited for controlling the sampling of currents of dynamic events. We demonstrate the method for calculating transition probabilities in barrier crossing problems and survival probabilities in strongly diffusive systems with absorbing states, which are difficult to treat by shooting. We discuss the relation of the algorithm to other methods. PMID:22779577

Guttenberg, Nicholas; Dinner, Aaron R; Weare, Jonathan

2012-06-21

298

Steered transition path sampling  

NASA Astrophysics Data System (ADS)

We introduce a path sampling method for obtaining statistical properties of an arbitrary stochastic dynamics. The method works by decomposing a trajectory in time, estimating the probability of satisfying a progress constraint, modifying the dynamics based on that probability, and then reweighting to calculate averages. Because the progress constraint can be formulated in terms of occurrences of events within time intervals, the method is particularly well suited for controlling the sampling of currents of dynamic events. We demonstrate the method for calculating transition probabilities in barrier crossing problems and survival probabilities in strongly diffusive systems with absorbing states, which are difficult to treat by shooting. We discuss the relation of the algorithm to other methods.

Guttenberg, Nicholas; Dinner, Aaron R.; Weare, Jonathan

2012-06-01

299

Flight Path Displays.  

National Technical Information Service (NTIS)

Aircraft display technology has advanced to the state where the flight path display, an integrated format on which both the vertical and horizontal path are graphically represented, is feasible. This report researches efforts made to design flight paths f...

D. A. Warner

1979-01-01

300

Maximum Flux Transition Paths of Conformational Change.  

PubMed

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

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

2010-08-10

301

Analysis of a Bloom Filter Algorithm via the Supermarket Model  

Microsoft Academic Search

This paper deals with the problem of identifying elephants in the Internet Traffic. The aim is to analyze a new adaptive algorithm based on a Bloom Filter. This algorithm uses a so-called min-rule which can be described as in the supermarket model. This model consists of joining the shortest queue among d queues selected at random in a large number

Yousra Chabchoub; Christine Fricker; Hanene Mohamed

2009-01-01

302

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

303

Translational and structural analysis of the shortest legume ENOD40 gene in Lupinus luteus  

Microsoft Academic Search

Two early nodulin 40 (enod40) genes, ENOD40-1, the shortest legume ENOD40 gene, and ENOD40-2, were isolated from Lupinus luteus, a legume with indeterminate nodules. Both genes were expressed at similar levels during symbiosis with nitrogen-fixing bacteria. ENOD40 phylog- eny clustered the L. luteus genes with legumes forming determinate nodules and revealed pep- tide similarities. The ENOD40-1 small ORF A fused

Jan Podkowinski; Agnieszka Zmienko; Blazena Florek; Pawel Wojciechowski; Agnieszka Rybarczyk; Jan Wrzesinski; Jerzy Ciesiolka; Jacek Blazewicz; Adam Kondorosi; Martin Crespi; Andrzej Legocki

2009-01-01

304

The prediction of radio-path characteristics  

NASA Astrophysics Data System (ADS)

The paper examines algorithms for the long-term prediction of radio-path characteristics in the ionosphere, the main characteristic being the MUF at a given distance. The proposed approach is based on long-term memories called DATA BANKS. Attention is given to the characteritics of the various banks, including the BANK OF CITIES, the BANK OF RADIO PATHS, the REFERENCE DATA BANK, and the OUTPUT DATA BANK.

Gitina, G. M.; Kalinin, Iu. K.

305

An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems  

Microsoft Academic Search

A novel algorithm for servicing soft deadline aperiodic tasks in a real-time system in which hard deadline periodic tasks are scheduled using a fixed priority algorithm is presented. This algorithm is proved to be optimal in the sense that it provides the shortest aperiodic response time among all possible aperiodic service methods. Simulation studies show that it offers substantial performance

John P. Lehoczkyt; S. Ramos-thuel

1992-01-01

306

Unbiased sampling of lattice Hamilton path ensembles.  

PubMed

Hamilton paths, or Hamiltonian paths, are walks on a lattice which visit each site exactly once. They have been proposed as models of globular proteins and of compact polymers. A previously published algorithm [Mansfield, Macromolecules 27, 5924 (1994)] for sampling Hamilton paths on simple square and simple cubic lattices is tested for bias and for efficiency. Because the algorithm is a Metropolis Monte Carlo technique obviously satisfying detailed balance, we need only demonstrate ergodicity to ensure unbiased sampling. Two different tests for ergodicity (exact enumeration on small lattices, nonexhaustive enumeration on larger lattices) demonstrate ergodicity unequivocally for small lattices and provide strong support for ergodicity on larger lattices. Two other sampling algorithms [Ramakrishnan et al., J. Chem. Phys. 103, 7592 (1995); Lua et al., Polymer 45, 717 (2004)] are both known to produce biases on both 2x2x2 and 3x3x3 lattices, but it is shown here that the current algorithm gives unbiased sampling on these same lattices. Successive Hamilton paths are strongly correlated, so that many iterations are required between statistically independent samples. Rules for estimating the number of iterations needed to dissipate these correlations are given. However, the iteration time is so fast that the efficiency is still very good except on extremely large lattices. For example, even on lattices of total size 10x10x10 we are able to generate tens of thousands of uncorrelated Hamilton paths per hour of CPU time. PMID:17059235

Mansfield, Marc L

2006-10-21

307

Unbiased sampling of lattice Hamilton path ensembles  

NASA Astrophysics Data System (ADS)

Hamilton paths, or Hamiltonian paths, are walks on a lattice which visit each site exactly once. They have been proposed as models of globular proteins and of compact polymers. A previously published algorithm [Mansfield, Macromolecules 27, 5924 (1994)] for sampling Hamilton paths on simple square and simple cubic lattices is tested for bias and for efficiency. Because the algorithm is a Metropolis Monte Carlo technique obviously satisfying detailed balance, we need only demonstrate ergodicity to ensure unbiased sampling. Two different tests for ergodicity (exact enumeration on small lattices, nonexhaustive enumeration on larger lattices) demonstrate ergodicity unequivocally for small lattices and provide strong support for ergodicity on larger lattices. Two other sampling algorithms [Ramakrishnan et al., J. Chem. Phys. 103, 7592 (1995); Lua et al., Polymer 45, 717 (2004)] are both known to produce biases on both 2×2×2 and 3×3×3 lattices, but it is shown here that the current algorithm gives unbiased sampling on these same lattices. Successive Hamilton paths are strongly correlated, so that many iterations are required between statistically independent samples. Rules for estimating the number of iterations needed to dissipate these correlations are given. However, the iteration time is so fast that the efficiency is still very good except on extremely large lattices. For example, even on lattices of total size 10×10×10 we are able to generate tens of thousands of uncorrelated Hamilton paths per hour of CPU time.

Mansfield, Marc L.

2006-10-01

308

Quickest Paths for Different Network Router Mechanisms  

SciTech Connect

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

Rao, NSV

2000-10-16

309

An Optimal Control-Based Formulation to Determine Natural Locomotor Paths for Humanoid Robots  

Microsoft Academic Search

In this paper we explore the underlying principles of natural locomotion path generation of human beings. The knowledge of these principles is useful to implement biologically inspired path planning algorithms on a humanoid robot. By 'locomotion path' we denote the motion of the robot as a whole in the plane. The key to our approach is to formulate the path

Katja Mombaur; Jean-Paul Laumond; Eiichi Yoshida

2010-01-01

310

Practical path planning among movable obstacles  

SciTech Connect

Path planning among movable obstacles is a practical problem that is in need of a solution. In this paper an efficient heuristic algorithm that uses a generate-and-test paradigm: a good'' candidate path is hypothesized by a global planner and subsequently verified by a local planner. In the process of formalizing the problem, we also present a technique for modeling object interactions through contact. Our algorithm has been tested on a variety of examples, and was able to generate solutions within 10 seconds. 5 figs., 27 refs.

Chen, Pang C.; Hwang, Yong K.

1990-09-05

311

Adaptive path planning for flexible manufacturing  

SciTech Connect

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

Chen, Pang C.

1994-08-01

312

2-D shape blending: an intrinsic solution to the vertex path problem  

Microsoft Academic Search

This paper presents an algorithm for determiningthe paths along which corresponding vertices travel in a 2-D shape blending. Rather than considering the vertex paths explicitly, the algorithm defines the inter- mediate shapes by interpolating the intrinsic definitions of the initial and final shapes. The algorithm produces shape blends which gener- ally are more satisfactory than those produced using linear or

Thomas W. Sederberg; Peisheng Gao; Guojin Wang; Hong Mu

1993-01-01

313

DISCUSS: Critical Path Analysis  

NSDL National Science Digital Library

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

Hunt, Neville; Baker, Barrie

2009-04-23

314

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

Microsoft Academic Search

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

Yu-kwong Kwok; Ishfaq Ahmad

1996-01-01

315

An exploratory look at supermarket shopping paths  

Microsoft Academic Search

We present analyses of an extraordinary new dataset that reveals the path taken by individual shoppers in an actual grocery store, as provided by RFID (radio frequency identification) tags located on their shopping carts. The analysis is performed using a multivariate clustering algorithm not yet seen in the marketing literature that is able to handle data sets with unique (and

Jeffrey S. Larson; Eric T. Bradlow; Peter S. Fader

2005-01-01

316

Graph Minors .XIII. The Disjoint Paths Problem  

Microsoft Academic Search

We describe an algorithm, which for fixed k ? 0 has running time O(|V(G)|3), to solve the following problem: given a graph G and k pairs of vertices of G, decide if there are k mutually vertex-disjoint paths of G joining the pairs.

Neil Robertson; Paul D. Seymour

1995-01-01

317

The Outsider interruption algorithm  

SciTech Connect

The Outsider Analysis (Outsider) module is part of the Analytic System and Software for Evaluation of Safeguards and Security (ASSESS). Outsider and the ASSESS Facility Descriptor (Facility) module together supercede the Systematic Analysis of Vulnerability to Intrusion (SAVI) PC software package. Outsider calculates P(I), the probability that outsiders are interrupted during an attack on a facility by security forces at the facility, and P(W), the probability of security system win. SAVI exhaustively examines every possible path to find the ten most vulnerable paths. Exhaustive search is adequate if the number of paths to examine is small, but moderately complex facilities can have millions of paths, making exhaustive search too slow for practical purposes. Outsider has two new algorithms that generate paths in order of vulnerability, finishing in a fraction of the time required by SAVI. The new Outsider algorithms make containment analysis easier for analysts than ever before. We describe the new algorithms and show how much better they perform than the SAVI exhaustive search algorithm. 6 refs., 5 figs., 2 tabs.

Snell, M.; Bingham, B.

1989-01-01

318

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

319

Construction Robot Path-Planning for Earthwork Operations  

Microsoft Academic Search

Abstract: In developing an intelligent mobile construction robot, a navigation system that can provide an effective and efficient path-planning algorithm is a very important element. The purpose of a path-planning method for a mobile construction robot is to find a continuous collision-free path from the initial position of the construction robot to its target position. This paper presents an improved

Sung-Keun Kim; Jeffrey S. Russell

2003-01-01

320

A simple robot paths planning based on Quadtree  

Microsoft Academic Search

Based on traditional methods, according with practical application conditions, and the special structure of Quadtree, this paper gives a practical method of paths planning for the further expansion of Quadtree in the field of paths planning, except for segmentation obstacles. The experimental and simulation results demonstrate that the algorithm described in the text could be able to find all the

Fule Wangl; Changle Zhou; H. de Garis

2010-01-01

321

Ridge-valley Path Planning for 3D Terrains  

Microsoft Academic Search

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

322

On the Joint Path Lengths Distribution in Random Binary Trees  

Microsoft Academic Search

During the 10th Seminar on Analysis of Algorithms, MSRI, Berkeley, June 2004, Knuth posed the problem of analyzing the left and the right path length in a random binary trees. In particular, Knuth asked about properties of the generating function of the joint distribution of the left and the right path lengths. In this paper, we mostly focus on the

Charles Knessl; Wojciech Szpankowski

2005-01-01

323

Visibility line based methods for UAV path planning  

Microsoft Academic Search

This paper addresses path planning algorithms for an uninhabited aerial vehicle (UAV) based on visibility lines (VL) method for real time applications. VL has been chosen because it provides a solution with optimal path length i.e. minimal distance travelled from starting point to target point. However, as known, the main problem with VL is that the computational burdensome grows exponentially

Rosli Omar; Da-Wei Gu

2009-01-01

324

Conflict-free AGV Routing in a Bidirectional Path Layout  

Microsoft Academic Search

AGV systems are now becoming widely used in automatic material handling systems. One of the issues arisin g in applications is routing. This paper presents a bi-directional path layout an d an algorithm for routing AGVs without conflicts. Mathematical relationships among certain key parameters of path and vehicle are derived to minim ize the space requirements of the layout. The

QIU Ling; HSU Wen-Jing

325

Locating algorithm being needless to harbor based on the quality in wireless sensor networks  

NASA Astrophysics Data System (ADS)

From locating techniques in the wireless sensors networks two groups based on harbor and without it can be referred to. Firstly, the harbor nodes distribute the local information in the network and through that the average distance between two groups or the average length of a step is identified. Non-harbor nodes know the shortest path as the number of steps to each of the harbors and determine their distance to the harbors by understanding this average step length and using this estimation compute their location distance. Firstly, the network nodes are clustered. Each harbor is a cluster head and the cluster members using information derived from this cluster head begin locating. This process starts by the nodes located in the common field between two clusters. Although algorithm comparability based on harbor is increased by the nodes clustering, but the algorithm precise and efficiency is still dependent on the number of harbor nodes. Using harbor in all of the conditions causes its usage limitation in the wireless sensor networks. Regarding the algorithms without needing to harbor, algorithm is the first case. This algorithm has invented a new method to make a local graph in the network which is applicable in computing the relative features of nodes. Firstly, each node makes a graph with its own axis. Then the general graph of network is made and each node changes its coordinates by using an algorithm. Because of the current limitations in the trigonometry method used in this algorithm, the computed coordinates are not reliable and face difficulties in many cases. The other algorithms being needless to harbor try to use another methods instead of trigonometry methods in locating. For instance, among these methods, those ones based on graph drawing or mass and coil algorithms can be referred to. These kinds of algorithms take much time and use a lot of energy. In order to upgrade the algorithm results quality and prevent the fault distribution, we define a secondary parameter called the computed location accuracy. This parameter indicates location accuracy and can be a value between zero and one.

Sharifi, Mirali; Tousi, Fatemeh; Kazimov, Tofiq

2011-12-01

326

Attention trees and semantic paths  

NASA Astrophysics Data System (ADS)

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

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

2007-03-01

327

RGBCA-genetic bee colony algorithm for travelling salesman problem  

Microsoft Academic Search

Challenge of finding the shortest route visiting each member of a collection of locations and returning to starting point is an NP-hard problem. It is also known as Traveling salesman problem, TSP is specific problem of combinatorial optimization studied in computer science and mathematical applications. In our work we present a hybrid version of Evolutionary algorithm to solve TSP problem.

Vikas singh; Ritu Tiwari; Deepak Singh; Anupam Shukla

2011-01-01

328

The Fuzzy Based Compact Genetic Algorithm for Online TSP  

Microsoft Academic Search

In this paper, we extend the definition of the common TSP and propose the online TSP, whose purpose is to find the shortest time of visiting all cities while considering the traffic conditions. We also propose a fuzzy based compact genetic algorithm (FCGA) for online TSPs. The basic idea of FCGA is to adapt the size of population simulated of

Li Shugang

2009-01-01

329

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

SciTech Connect

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

330

A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental Study  

Microsoft Academic Search

Hannenhalli and Pevzner gave the é rst polynomial-time algorithm for computing the inver- sion distance between two signed permutations, as part of the larger task of determining the shortest sequence of inversions needed to transform one permutation into the other. Their algorithm (restricted to distance calculation) proceeds in two stages: in the é rst stage, the overlap graph induced by

David A. Bader; Bernard M. E. Moret; Mi Yan

2001-01-01

331

Variational nature, integration, and properties of Newton reaction path  

NASA Astrophysics Data System (ADS)

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.

Bofill, Josep Maria; Quapp, Wolfgang

2011-02-01

332

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

PubMed

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

333

The SunPath  

NSDL National Science Digital Library

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

University, Australian N.

334

Visualizing Paths in Context  

Microsoft Academic Search

Data about movement through a space is increasingly becoming available for capture and analysis. In many applications, this data is captured or modeled as transitions between a small number of areas of interests, or a finite set of states, and these transitions constitute paths in the space. Similarities and differences between paths are of great importance to such analyses, but

Fabio Pellacini; Lori Lorigo; Geri Gay

2006-01-01

335

Finding Disjoint Paths in Expanders Deterministically and Online  

Microsoft Academic Search

We describe a deterministic, polynomial time algorithm for nding edge-disjoint paths connect- ing given pairs of vertices in an expander. Specically, the input of the algorithm is a suciently strong d-regular expander G on n vertices, and a sequence of pairs si;ti, (1 i r) of vertices, where r = ( ndlog d log n ), and no vertex appears

Noga Alon; Michael R. Capalbo

2007-01-01

336

Towards real implementations of dynamic robust routing exploiting path diversity  

Microsoft Academic Search

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

Luca Muscariello; Diego Perino; Bruno Nardelli

2009-01-01

337

Dynamic path planning in sensor-based terrain acquisition  

Microsoft Academic Search

The terrain acquisition problem is formulated as that of continuous motion planning, and no constraints are imposed on obstacle geometry. Two algorithms are described for acquiring planar terrains with obstacles of arbitrary shape. Estimates of the algorithm performance are derived as upper bounds on the lengths of generated paths

V. J. Lumelsky; S. Mukhopadhyay; K. Sun

1990-01-01

338

Agricultural robot path tracking based on predictable path  

Microsoft Academic Search

In order to realize the path tracking of agricultural robot in complex farmland environment and improve its speed and accuracy, a kind of agricultural robot path tracking method based predictable path was put forward in this paper. The definition of predictable path and fitting were presented, the positioning principles and methods were described in detail. The implementation method of path

Chi Gao; Yougang Su; Hui Ma

2010-01-01

339

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

Microsoft Academic Search

In this paper, a path tracking algorithm is proposed to compensate path deviation due to torque bound. For this, a disturbance observer is applied to each joint of an n degrees of freedom manipulator to obtain a simple equivalent robot dynamics (SERD) being represented as an n independent double integrator system. For an arbitrary trajectory generated for a given path

K. S. Eom; I. H. Suh; W. K. Chung

1997-01-01

340

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

Microsoft Academic Search

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

Larry McMurchie; Carl Ebeling

1995-01-01

341

Distributed path planning for connectivity under uncertainty by ant colony optimization  

Microsoft Academic Search

Movement and allocation of network resources for a system of communicating agents are usually optimized independently. Path planning under kinematic restrictions and obstacle avoidance provides a set of paths for the agents, and given the paths, it is then the job of network design algorithms to allocate communication resources to ensure a satisfactory rate of information exchange. In this paper,

Alex Fridman; Steven Weber; Vijay Kumar; Moshe Kam

2008-01-01

342

TATOO: an industrial timing analyzer with false path elimination and test pattern generation  

Microsoft Academic Search

TATOO is an industrial interactive timing analysis system evolved from recently developed false path elimination algorithms. These have been extended to perform more complex searches that facilitate the rapid survey of a network. An automatic test pattern generation mechanism which exercises the statically sensitizable paths has been developed. This forms a direct link to an electrical simulator. The critical path

Jacques Benkoski; Ronald B. Stewart

1991-01-01

343

A simple and adaptive on-line path planning system for a UAV  

Microsoft Academic Search

This paper presents a guidance algorithm for an unmanned aerial vehicle (UAV). It combines a nonlinear lateral guidance control law, originally designed for UAVs tracking circles for mid-air rendezvous, with a new simple adaptive path planning algorithm. Preflight path planning only consists of storing a few way points guiding the aircraft to its targets. The paper presents an efficient way

G. Ducard; K. C. Kulling; H. P. Geering

2007-01-01

344

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

Microsoft Academic Search

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

345

Path integral description of light transport in tissues  

NASA Astrophysics Data System (ADS)

The early photons that arrive at a collector through a large thickness of tissue have potential for imaging internal organ structure, function, and status with improved image resolution relative to late arriving photons which have been diffusely scattered. Calculation of early photon arrival at a collector after transport through large tissue thicknesses is difficult, yet a comparison of predicted versus measured transmission is at the heart of imaging algorithms. The path integral description of light transport offers an approach toward such calculations. The method describes the movement of photons as particles undergoing collisions in a scattering medium based on the Brownian motion formalism of Feynman and Hibbs. This paper presents a basic introduction to the path integral description of photon transport and discusses the constrained classical path for describing the most probable path of a photon and the unconstrained classical path for describing the group path of an ensemble of photons.

Jacques, Steven L.; Wang, Xujing

1997-08-01

346

Path lengths, correlations, and centrality in temporal networks  

NASA Astrophysics Data System (ADS)

In temporal networks, where nodes interact via sequences of temporary events, information or resources can only flow through paths that follow the time ordering of events. Such temporal paths play a crucial role in dynamic processes. However, since networks have so far been usually considered static or quasistatic, the properties of temporal paths are not yet well understood. Building on a definition and algorithmic implementation of the average temporal distance between nodes, we study temporal paths in empirical networks of human communication and air transport. Although temporal distances correlate with static graph distances, there is a large spread, and nodes that appear close from the static network view may be connected via slow paths or not at all. Differences between static and temporal properties are further highlighted in studies of the temporal closeness centrality. In addition, correlations and heterogeneities in the underlying event sequences affect temporal path lengths, increasing temporal distances in communication networks and decreasing them in the air transport network.

Pan, Raj Kumar; Saramäki, Jari

2011-07-01

347

Quickest Paths for Different Network Router Mechanisms  

SciTech Connect

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

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

2000-06-01

348

Transition-path sampling of -hairpin folding  

NASA Astrophysics Data System (ADS)

We examine the dynamical folding pathways of the C-terminal -hairpin of protein G-B1 in explicit solvent at room temperature by means of a transition-path sampling algorithm. In agreement with previous free-energy calculations, the resulting path ensembles reveal a folding mechanism in which the hydrophobic residues collapse first followed by backbone hydrogen-bond formation, starting with the hydrogen bonds inside the hydrophobic core. In addition, the path ensembles contain information on the folding kinetics, including solvent motion. Using the recently developed transition interface sampling technique, we calculate the rate constant for unfolding of the protein fragment and find it to be in reasonable agreement with experiments. The results support the validation of using all-atom force fields to study protein folding.

Bolhuis, Peter G.

2003-10-01

349

Path-summation waveforms  

NASA Astrophysics Data System (ADS)

In this paper, we examine an efficient, practical method to calculate approximate, finite-frequency waveforms for the early signals from a point source in 3-D acoustic media with smoothly varying velocity and constant density. In analogy to the use of Feynman path integrals in quantum physics, we obtain an approximate waveform solution for the scalar wave equation by a Monte Carlo summation of elementary signals over a representative sample of all possible paths between a source and observation point. The elementary signal is formed from the convolution of the source time function with a time derivative of the Green's function for the homogeneous problem. For each path, this elementary signal is summed into a time series at a traveltime obtained from an integral of slowness along the path. The constructive and destructive interference of these signals produces the approximate waveform response for the range of traveltimes covered by the sampled paths. We justify the path-summation technique for a smooth medium using a heuristic construction involving the Helmholtz-Kirchhoff integral theorem. The technique can be applied to smooth, but strongly varying and complicated velocity structures. The approximate waveform includes geometrical spreading, focusing, defocusing and phase changes, but does not fully account for multiple scattering. We compare path-summation waveforms with the exact solution for a 3-D geometry involving a low-velocity spherical inclusion, and with finite-difference waveforms for a 2-D structure with realistic, complicated velocity variations. In contrast to geometrical-ray methods, the path-summation approach reproduces finite-frequency wave phenomena such as diffraction and does not exhibit singular behaviour. Relative to the finite-difference numerical method, the path-summation approach requires insignificant computer memory and, depending on the number of waveforms required, up to one to two orders of magnitude less computing time. The sampled paths and associated traveltimes produced by the path summation give a relation between the medium and the signal on the waveform that is not available with finite-difference and finite-element methods. Furthermore, the speed and accuracy of the path-summation method may be sufficient to allow 3-D waveform inversion using stochastic, non-linear, global search methods.

Lomax, Anthony

1999-09-01

350

An attempt of microwave CT system which discriminates the transmission path by means of time domain measurement.  

PubMed

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

351

Path integral learning of multidimensional movement trajectories  

NASA Astrophysics Data System (ADS)

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

André, Joa~o.; Santos, Cristina; Costa, Lino

2013-10-01

352

Tortuous path chemical preconcentrator  

SciTech Connect

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

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

2010-09-21

353

A proof of convergence for Ant algorithms  

Microsoft Academic Search

A proof of convergence for Ant algorithms is developed. Ant algorithms were modeled as branching random processes: the branching random walk and branching Wiener process to derive rates of birth and death of ant paths. Substitution is then carried out in birth-death processes, which proves that a stable distribution is surely reached. This indicates that Ant algorithms converge with probability

Amr Badr; Ahmed Fahmy

2004-01-01

354

Follow the Paths  

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.

355

Path integrals and parastatistics  

NASA Astrophysics Data System (ADS)

The propagator and corresponding path integral for a system of identical particles obeying parastatistics are derived. It is found that the statistical weights of topological sectors of the path integral for parafermions and parabosons are simply related through multiplication by the parity of the permutation of the final positions of the particles. Appropriate generalizations of statistics are proposed obeying unitarity and factorizability (strong cluster decomposition). The realization of simple maximal occupancy (Gentile) statistics is shown to require ghost states.

Polychronakos, Alexios P.

1996-02-01

356

PathFinder Science  

NSDL National Science Digital Library

PathFinder Science contains research projects about water conservation, tardigrades, a winter bird survey, ozone, ultraviolet light and DNA, global warming, spot removal, lichens, stream monitoring, amphibian biomonitoring, and particulate monitoring. Free registration to the PathFinder Science Network offers the opportunity to be a part of the listserv, upload collaborative project data or publish research work. There are tools and tips to help students publish their research on the web.

357

Real-time generation and control of cutter path for 5-axis CNC machining  

Microsoft Academic Search

This paper presents a new approach to real-time generation and control of the cutter path for 5-axis machining applications. The cutter path generation method comprises real-time algorithms for cutter-contact path interpolation, cutter offsetting, and coordinate conversion. In addition, a global feedback loop is closed by the CNC interpolator so as to augment the controlled accuracy in practical cutter path generation.

Chih-Ching Lo

1999-01-01

358

Multipath Binomial Congestion Control Algorithms  

NASA Astrophysics Data System (ADS)

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

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

359

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

360

Image-based path planning for automated virtual colonoscopy navigation  

NASA Astrophysics Data System (ADS)

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

Hong, Wei

2008-04-01

361

Adaptive path planning in changing environments  

SciTech Connect

Path planning needs to be fast to facilitate real-time robot programming. Unfortunately, current planning techniques are still too slow to be effective, as they often require several minutes, if not hours of computation. To overcome this difficulty, we present an adaptive algorithm that uses previous 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 extends our previous work for stationary environments in two directions: For minor environmental change, an object-attached experience abstraction scheme is introduced to increase the flexibility of the learned experience; for major environmental change, an on-demand experience repair scheme is also introduced to retain those experiences that remain valid and useful. In addition to presenting this algorithm, we identify three other variants with different repair strategies. To compare these algorithms, we develop an analytic model to compare the costs and benefits of the corresponding repair processes. Using this model, we formalize the concept of incremental change, and prove the optimality of our proposed algorithm under such change. Empirically, we also characterize the performance curve of each variant, confirm our theoretical optimality results, and demonstrate the practicality of our algorithm.

Chen, Pang C.

1993-10-01

362

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

NASA Astrophysics Data System (ADS)

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

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

2013-03-01

363

Adaptive robot path planning in changing environments  

SciTech Connect

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

Chen, P.C.

1994-08-01

364

Paths in the minimally weighted path model are incompatible with Schramm-Loewner evolution  

NASA Astrophysics Data System (ADS)

We study numerically the geometrical properties of minimally weighted paths that appear in the minimally weighted path (MWP) model on two-dimensional lattices assuming a combination of periodic and free boundary conditions (BCs). Each realization of the disorder consists of a random fraction (1-?) of bonds with unit strength and a fraction ? of bond strengths drawn from a Gaussian distribution with zero mean and unit width. For each such sample, a path is forced to span the lattice along the direction with the free BCs. The path and a set of negatively weighted loops form a ground state. A ground state on such a lattice can be determined performing a nontrivial transformation of the original graph and applying sophisticated matching algorithms. Here we examine whether the geometrical properties of the paths are in accordance with the predictions of the Schramm-Loewner evolution (SLE). Measuring the fractal dimension, considering the winding angle statistics, and reviewing Schramm's left passage formula indicate that the paths cannot be described in terms of SLE.

Norrenbrock, C.; Melchert, O.; Hartmann, A. K.

2013-03-01

365

Optimal flow path design of unidirectional AGV systems  

Microsoft Academic Search

This paper describes an alternative formulation of the AGV flow path layout (FPL) problem which was first formulated by Gaskins and Tanchoco (1987) as a zero-one integer programming problem. A computationally efficient procedure is proposed which is based on the branch-and-bound technique. An algorithm for satisfying the reachability condition for nodes in the AGV flow path network is also presented.

MOSHE KASPI; J. M. A. TANCHOCO

1990-01-01

366

Real-time path-based surface detail  

Microsoft Academic Search

We present a GPU algorithm to render path-based 3D surface detail in real-time. Our method models these features using a vector representation that is efficiently stored in two textures. First texture is used to specify the position of the features, while the second texture contains their paths, profiles and material information. A fragment shader is then proposed to evaluate this

Carles Bosch; Gustavo Patow

2010-01-01

367

Quickest Paths, Straight Skeletons, and the City Voronoi Diagram  

Microsoft Academic Search

The city Voronoi diagram is induced by quickest paths in the L 1plane, made faster by an isothetic transportation network. We investigate the rich geometric and algorithmic properties of city Voronoi diagrams, and report on their use in processing quickest-path queries. In doing so, we revisit the fact that not every Voronoi-type diagram has interpretations in both the distance model

Oswin Aichholzer; Franz Aurenhammer; Belén Palop

2004-01-01

368

Quickest paths, straight skeletons, and the city Voronoi diagram  

Microsoft Academic Search

The city Voronoi diagram is induced by quickest paths, in the L 1 plane speeded up by an isothetic transportation network. We investigate the rich geometric and algorithmic properties of city Voronoi diagrams, and report on their use in processing quickest-path queries.In doing so, we revisit the fact that not every Voronoi-type diagram has interpretations in both the distance model

Oswin Aichholzer; Franz Aurenhammer; Belén Palop

2002-01-01

369

Folding Arbitrary 3D Shapes with Space-Filling Chain Robots: Folded Configuration Design as 3D Hamiltonian Path through Target Solid  

Microsoft Academic Search

We propose a method for arbitrary 3D shape formation by folding chains of hinged polyhedra. This paper presents an incremental algorithm for finding a space filling curve, a Hamiltonian path, within a 3D solid. The algorithm is a bottom up approach that starts with minimal local paths connecting small clusters of neighboring constituent poly- hedra and incrementally merges neighboring paths

J. Bachrach; V. Zykov; S. Griffith

370

VDSPT: A Sensor-Actor Coordination Protocol for Wireless Sensor and Actor Network Based on Voronoi Diagram and Shortest Path Tree  

Microsoft Academic Search

Wireless sensor and actor network refers to a group of sensors and actors, which gather information in detection area and perform appropriate actions upon the event area, respectively. Just as in wireless sensor network (WSN), one of the most important objectives of designing coordination protocols in WSAN is to decrease energy consumption and prolong network lifetime. This paper proposes a

Zhicheng Dai; Bingwen Wang; Zhi Li; An Yin

2009-01-01

371

The optomechanical design of AquEYE, an instrument for astrophysics on its shortest timescales at the Asiago Observatory  

NASA Astrophysics Data System (ADS)

This paper describes the ultra-fast photometer AquEYE (the Asiago Quantum Eye) being built for the 182 cm telescope at Cima Ekar, as a prototype for the QuantEYE instrument studied for the ESO OWL. In a way similar to what has been proposed for Quanteye, Aqueye isolates a single object at the center of the telescope field of view, and divides the telescope pupil in four parts. Each sub-pupil is then focused on a Single Photon Avalanche Photodiode capable to tag the arrival time of each photon to better than 50 picoseconds. The counts are acquired via a Time to Digital Converter board and stored in four separate memories. Both in-line and off-line algorithms will be available for data analysis. The designed optical non-imaging solution concentrates all the light collected inside a 3 arcsec field on the 50 micrometer detector square area. Different filters can be inserted in the 4 different optical paths. It is foreseen to utilize the instrument on several different astrophysical problems characterized by rapid variability, including occultations by the Moon, asteroids and KBOs, and extrasolar planet transits.

Barbieri, C.; Naletto, G.; Occhipinti, T.; Tamburini, F.; Giro, E.; D'Onofrio, M.; Sain, E.; Zaccariotto, M.

372

Path efficiency of ant foraging trails in an artificial network.  

PubMed

In this paper we present an individual-based model describing the foraging behavior of ants moving in an artificial network of tunnels in which several interconnected paths can be used to reach a single food source. Ants lay a trail pheromone while moving in the network and this pheromone acts as a system of mass recruitment that attracts other ants in the network. The rules implemented in the model are based on measures of the decisions taken by ants at tunnel bifurcations during real experiments. The collective choice of the ants is estimated by measuring their probability to take a given path in the network. Overall, we found a good agreement between the results of the simulations and those of the experiments, showing that simple behavioral rules can lead ants to find the shortest paths in the network. The match between the experiments and the model, however, was better for nestbound than for outbound ants. A sensitivity study of the model suggests that the bias observed in the choice of the ants at asymmetrical bifurcations is a key behavior to reproduce the collective choice observed in the experiments. PMID:16199059

Vittori, Karla; Talbot, Grégoire; Gautrais, Jacques; Fourcassié, Vincent; Araújo, Aluizio F R; Theraulaz, Guy

2005-09-30

373

Metabolic isotopomer labeling systems. Part III: path tracing.  

PubMed

Isotope labeling systems (ILSs) are sets of balance equations that quantitatively describe the distribution of isotopic tracers in metabolic networks. The solution of ILSs, i.e., the calculation of isotopic labeling distributions (mostly in steady state) is the fundamental computational step of (13)C metabolic flux analysis (MFA). Aiming at a deeper analytical understanding of ILSs a new approach for solving ILSs is developed. It is based on the straightforward idea of tracing labeled molecules through the metabolic network. The new approach allows to calculate the label distribution in isotopic tracer experiments in an analytical way that directly reflects the underlying network structure. The theory of path tracing is formally developed by introducing regular expressions for representing all possible paths through the labeling network. These expressions are generated by classical path tracing algorithms, e.g. by the Kleene algorithm. As a central theoretical result, a framework for proving the correctness of such path tracing algorithms in their application to ILSs is developed. Finally, by mapping path expressions to algebraic expressions, the solution of an ILS is computed. As an offspring of the developed theory, the relation between path tracing and former approaches for ILS solution is worked out and several consequences for the numerical solution and analysis of ILSs and - more general - compartmental systems used in pharmaco-kinetic modeling will be sketched. PMID:23507460

Wiechert, Wolfgang; Nöh, Katharina; Weitzel, Michael

2013-03-16

374

Path integral for the loop representation of lattice gauge theories  

SciTech Connect

We show how the Hamiltonian lattice {ital loop} {ital representation} can be cast straightforwardly in the path integral formalism. The procedure is general for any gauge theory. Here we present in detail the simplest case: pure compact QED. The lattice loop path integral approach allows us to knit together the power of statistical algorithms with the transparency of the gauge-invariant loop description. The results produced by numerical simulations with the loop classical action for different lattice models are discussed. We also analyze the lattice path integral in terms of loops for the non-Abelian theory. {copyright} {ital 1996 The American Physical Society.}

Aroca, J.M. [Departament de Matematiques, Universitat Politecnica de Catalunya, Gran Capita, s/n Mod C-3 Campus Nord, 08034 Barcelona (Spain); Fort, H.; Gambini, R. [Instituto de Fisica, Facultad de Ciencias, Tristan Narvaja 1674, 11200 Montevideo (Uruguay)

1996-12-01

375

Efficient Intensity Map Splitting Algorithms for Intensity-Modulated Radiation Therapy.  

PubMed

In this paper, we study several interesting intensity map splitting (IMSp) problems that arise in Intensity-Modulated Radiation Therapy (IMRT), a state-of-the-art radiation therapy technique for cancer treatments. In current clinical practice, a multi-leaf collimator (MLC) with a maximum leaf spread is used to deliver the prescribed intensity maps (IMs). However, the maximum leaf spread of an MLC may require that a large intensity map be split into several abutting sub-IMs each being delivered separately, which results in prolonged treatment time. Few IM splitting techniques reported in the literature have addressed the issue of treatment delivery efficiency for large IMs. We develop a unified approach for solving the IMSp problems while minimizing the total beam-on time in various settings. Our basic idea is to formulate the IMSp problem as computing a k-link shortest path in a directed acyclic graph. We carefully characterize the intrinsic structures of the graph, yielding efficient algorithms for the IMSp problems. PMID:19043618

Wu, Xiaodong

2008-01-31

376

Privacy-Preserving Relationship Path Discovery in Social Networks  

NASA Astrophysics Data System (ADS)

As social networks sites continue to proliferate and are being used for an increasing variety of purposes, the privacy risks raised by the full access of social networking sites over user data become uncomfortable. A decentralized social network would help alleviate this problem, but offering the functionalities of social networking sites is a distributed manner is a challenging problem. In this paper, we provide techniques to instantiate one of the core functionalities of social networks: discovery of paths between individuals. Our algorithm preserves the privacy of relationship information, and can operate offline during the path discovery phase. We simulate our algorithm on real social network topologies.

Mezzour, Ghita; Perrig, Adrian; Gligor, Virgil; Papadimitratos, Panos

377

The traffic equilibrium problem with nonadditive path costs  

SciTech Connect

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

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

1995-08-21

378

Variability in quasar broad absorption line outflows - III. What happens on the shortest time-scales?  

NASA Astrophysics Data System (ADS)

Broad absorption lines (BALs) in quasar spectra are prominent signatures of high-velocity outflows, which might be present in all quasars and could be a major contributor to feedback to galaxy evolution. Studying the variability in these BALs allows us to further our understanding of the structure, evolution and basic physical properties of the outflows. This is the third paper in a series on a monitoring programme of 24 luminous BAL quasars at redshifts 1.2 < z < 2.9. We focus here on the time-scales of variability in C IV ?1549 BALs in our full multi-epoch sample, which covers time-scales from 0.02 to 8.7 yr in the quasar rest frame. Our sample contains up to 13 epochs of data per quasar, with an average of seven epochs per quasar. We find that both the incidence and the amplitude of variability are greater across longer time-scales. Part of our monitoring programme specifically targeted half of these BAL quasars at rest-frame time-scales ?2 months. This revealed variability down to the shortest time-scales we probe (8-10 d). Observed variations in only portions of BAL troughs or in lines that are optically thick suggest that at least some of these changes are caused by clouds (or some type of outflow substructures) moving across our lines of sight. In this crossing cloud scenario, the variability times constrain both the crossing speeds and the absorber locations. Specific results also depend on the emission and absorption geometries. We consider a range of geometries and use Keplerian rotational speeds to derive a general relationship between the variability times, crossing speeds and outflow locations. Typical variability times of the order of ˜1 yr indicate crossing speeds of a few thousand km s-1 and radial distances ˜1 pc from the central black hole. However, the most rapid BAL changes occurring in 8-10 d require crossing speeds of 17 000-84 000 km s-1 and radial distances of only 0.001-0.02 pc. These speeds are similar to or greater than the observed radial outflow speeds, and the inferred locations are within the nominal radius of the broad emission-line region.

Capellupo, D. M.; Hamann, F.; Shields, J. C.; Halpern, J. P.; Barlow, T. A.

2013-03-01

379

Following the Path  

ERIC Educational Resources Information Center

This article profiles Diane Stanley, an author and illustrator of children's books. Although she was studying to be a medical illustrator in graduate school, Stanley's path changed when she got married and had children. As she was raising her children, she became increasingly enamored of the colorful children's books she would check out of the…

Rodia, Becky

2004-01-01

380

Paths of Innovation  

Microsoft Academic Search

In 1903 the Wright brothers' airplane travelled a couple of hundred yards. Today fleets of streamlined jets transport millions of people each day to cities worldwide. Between discovery and application, between invention and widespread use, there is a world of innovation, of tinkering, improvement and adaptation. This is the world David Mowery and Nathan Rosenberg map out in Paths of

David C. Mowery; Nathan Rosenberg

381

Intrusion Path Analysis.  

National Technical Information Service (NTIS)

The design and implementation of an Intrusion Path Analysis (IPA) function came about as a result of the upgrades to the security systems at the Savannah River Site (SRS), near Aiken, South Carolina. The stated requirements for IPA were broad, leaving opp...

R. D. Hardwick

1989-01-01

382

(Intrusion Path Analysis)  

Microsoft Academic Search

The design and implementation of an Intrusion Path Analysis (IPA) function came about as a result of the upgrades to the security systems at the Savannah River Site (SRS), near Aiken, South Carolina. The stated requirements for IPA were broad, leaving opportunity for creative freedom during design and development. The essential elements were that it: be based on alarm and

Hardwick

1989-01-01

383

Paths to Remarriage  

Microsoft Academic Search

High divorce rates and the traditionally discrepant ages at death for husbands and wives indicate a need for a more complete understanding of the paths to remarriage in contemporary America. This study uses data from the U.S. Bureau of the Census' Current Population Survey to examine the extent and timing of remarriage, social factors associated with remarriage, and the impact

Graham B. Spanier; Paul C. Glick

1980-01-01

384

Path to the Profession  

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

385

Automatic sulcal line extraction on cortical surfaces using geodesic path density maps.  

PubMed

We present here a method that is designed to automatically extract sulcal lines on the mesh of any cortical surface. The method is based on the definition of a new function, the Geodesic Path Density Map (GPDM), within each sulcal basin (i.e. regions with a negative mean curvature). GPDM indicates at each vertex the likelihood that a shortest path between any two points of the basins boundary goes through that vertex. If the distance used to compute shortest path is anisotropic and constrained by a geometric information such as the depth, the GPDM indicates the likelihood that a vertex belongs to the sulcal line in the basin. An automatic GPDM adaptive thresholding procedure is proposed and sulcal lines are then defined. The process has been validated on a set of 25 subjects by comparing results to the manual segmentation from an expert and showed an average error below 2mm. It is also compared to our previous reference method in the context of inter-subject cortical surface registration and shows an significant improvement in performance. PMID:22521478

Le Troter, A; Auzias, G; Coulon, O

2012-04-14

386

Automatic tool path generation for finish machining  

SciTech Connect

A system for automatic tool path generation was developed at Sandia National Laboratories for finish machining operations. The system consists of a commercially available 5-axis milling machine controlled by Sandia developed software. This system was used to remove overspray on cast turbine blades. A laser-based, structured-light sensor, mounted on a tool holder, is used to collect 3D data points around the surface of the turbine blade. Using the digitized model of the blade, a tool path is generated which will drive a 0.375 inch diameter CBN grinding pin around the tip of the blade. A fuzzified digital filter was developed to properly eliminate false sensor readings caused by burrs, holes and overspray. The digital filter was found to successfully generate the correct tool path for a blade with intentionally scanned holes and defects. The fuzzified filter improved the computation efficiency by a factor of 25. For application to general parts, an adaptive scanning algorithm was developed and presented with simulation results. A right pyramid and an ellipsoid were scanned successfully with the adaptive algorithm.

Kwok, Kwan S.; Loucks, C.S.; Driessen, B.J.

1997-03-01

387

Tom Thumb Algorithm for Planning Simple Vehicle Motions.  

National Technical Information Service (NTIS)

In this report, an algorithm for planning smooth collision-free paths, together with the velocities along that path, is presented. In this algorithm a search technique, which uses a heuristic rule to guide the search process, is applied. We will use inter...

J. M. Nauta

1994-01-01

388

A polynomial time algorithm for optimal routing around a rectangle  

Microsoft Academic Search

In this paper we present an algorithm for a special case of wire routing. Given a rectangular circuit component on a planar surface with terminals around its boundary, the algorithm finds an optimal set of paths in the plane connecting specified pairs of terminals. The paths are restricted to lie on the outside of the component and must consist of

Andrea S. LaPaugh

1980-01-01

389

Efficiently finding the minimum free energy path from steepest descent path.  

PubMed

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

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

2013-04-28

390

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

391

A METRIC-BASED APPROACH TO 2D TOOL-PATH OPTIMIZATION FOR HIGH-SPEED MACHINING  

Microsoft Academic Search

Conventional tool-path generation strategies are readily available to generate geometrically feasible trajectories. Such approaches seldom take into consideration physical process concerns or dynamic system limitations. In the present work, an approach for improving a geometrically feasible tool-path trajectory based on quantifiable process metrics is developed. Two specific measures of toolpath quality are incorporated into the iterative improvement algorithm: instantaneous path

Hongcheng Wang; Peter Jang; James A. Stori

392

Consideration of obstacle danger level in path planning using A* and Fast-Marching optimisation: comparative study  

Microsoft Academic Search

Obstacle danger level is taken into consideration in path planning using fractional potential maps. This paper describes the two optimisation methods tested: the A* algorithm and the Fast-Marching technique. The e4ciency ofthe two approaches is illustrated and compared through a vehicle path planning application in a 5xed obstacle environment. A ? is a heuristically ordered research algorithm and is complete

Pierre Melchior; B. Orsoni; Olivier Lavialle; A. Poty; Alain Oustaloup

2003-01-01

393

Path Planning for Complete Coverage with Agricultural Machines  

Microsoft Academic Search

The problem of planning reference trajectories for agricultural machines is considered. A path planning algorithm to perform\\u000a various kinds of farm-works is described. The case of convex fields is first considered. A direction of work being given,\\u000a the algorithm determines the turning areas and selects a trajectory which guarantees the complete field coverage while minimizing\\u000a overlapping. The method is extended

Michel Taïx; Philippe Souères; Helene Frayssinet; Lionel Cordesses

2003-01-01

394

A Renormalized Rough Path over Fractional Brownian Motion  

NASA Astrophysics Data System (ADS)

We construct in this article a rough path over fractional Brownian motion with arbitrary Hurst index by (i) using the Fourier normal ordering algorithm introduced in (Unterberger, Commun Math Phy 298(1):1-36, 2010) to reduce the problem to that of regularizing tree iterated integrals and (ii) applying the Bogolioubov-Parasiuk-Hepp-Zimmermann (BPHZ) renormalization algorithm to Feynman diagrams representing tree iterated integrals.

Unterberger, Jérémie

2013-06-01

395

Ant colony search algorithms for optimal polygonal approximation of plane curves  

Microsoft Academic Search

This paper presents a new polygonal approximation method using ant colony search algorithm. The problem is represented by a directed graph such that the objective of the original problem becomes to find the shortest closed circuit on the graph under the problem-specific constraints. A number of artificial ants are distributed on the graph and communicate with one another through the

Peng-yeng Yin

2003-01-01

396

Exact train pathing  

Microsoft Academic Search

Suppose we are given a schedule of train movements over a rail network into which a new train is to be included. The origin\\u000a and the destination are specified for the new train; it is required that a schedule (including the path) be determined for\\u000a it so as to minimize the time taken without affecting the schedules for the old

Viswanath Nagarajan; Abhiram G. Ranade

2008-01-01

397

Adaptive Fast Path Architecture  

Microsoft Academic Search

Adaptive Fast Path Architecture (AFPA) is a software architecture that dramatically improves the efficiency, and therefore the capacity, of Web and other network servers. The architecture includes a RAM-based cache that serves static content and a reverse proxy that can distribute requests for dynamic content to multiple servers. These two mechanisms are combined using a ?exible layer-7 (content-based) routing facility.

Elbert C. Hu; Philippe Joubert; Robert B. King; Jason D. Lavoie; John M. Tracey

2001-01-01

398

PATHS groundwater hydrologic model  

SciTech Connect

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

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

1980-04-01

399

Demonstration of scan path optimization in proton therapy  

SciTech Connect

A three-dimensional (3D) intensity modulated proton therapy treatment plan to be delivered by magnetic scanning may comprise thousands of discrete beam positions. This research presents the minimization of the total scan path length by application of a fast simulated annealing (FSA) optimization algorithm. Treatment plans for clinical prostate and head and neck cases were sequenced for continuous raster scanning in two ways, and the resulting scan path lengths were compared: (1) A simple back-and-forth, top-to-bottom (zigzag) succession, and (2) an optimized path produced as a solution of the FSA algorithm. Using a first approximation of the scanning dynamics, the delivery times for the scan sequences before and after path optimization were calculated for comparison. In these clinical examples, the FSA optimization shortened the total scan path length for the 3D target volumes by approximately 13%-56%. The number of extraneous spilled particles was correspondingly reduced by about 13%-54% due to the more efficient scanning maps that eliminated multiple crossings through regions of zero fluence. The relative decrease in delivery time due to path length minimization was estimated to be less than 1%, due to both a high scanning speed and time requirements that could not be altered by optimization (e.g., time required to change the beam energy). In a preliminary consideration of application to rescanning techniques, the decrease in delivery time was estimated to be 4%-20%.

Kang, Joanne H.; Wilkens, Jan J.; Oelfke, Uwe [Department of Medical Physics in Radiation Oncology, German Cancer Research Center (DKFZ), Im Neuenheimer Feld 280, 69120 Heidelberg (Germany)

2007-09-15

400

Kinematic path planning for space-based robotics  

NASA Astrophysics Data System (ADS)

Future space robotics tasks require manipulators of significant dexterity, achievable through kinematic redundancy and modular reconfigurability, but with a corresponding complexity of motion planning. Existing research aims for full autonomy and completeness, at the expense of efficiency, generality or even user friendliness. Commercial simulators require user-taught joint paths-a significant burden for assembly tasks subject to collision avoidance, kinematic and dynamic constraints. Our research has developed a Kinematic Path Planning (KPP) algorithm which bridges the gap between research and industry to produce a powerful and useful product. KPP consists of three key components: path-space iterative search, probabilistic refinement, and an operator guidance interface. The KPP algorithm has been successfully applied to the SSRMS for PMA relocation and dual-arm truss assembly tasks. Other KPP capabilities include Cartesian path following, hybrid Cartesian endpoint/intermediate via-point planning, redundancy resolution and path optimization. KPP incorporates supervisory (operator) input at any detail to influence the solution, yielding desirable/predictable paths for multi-jointed arms, avoiding obstacles and obeying manipulator limits. This software will eventually form a marketable robotic planner suitable for commercialization in conjunction with existing robotic CAD/CAM packages.

Seereeram, Sanjeev; Wen, John T.

1998-01-01

401

Comparison of the speeds of three convolution algorithms  

SciTech Connect

The speeds of three computer algorithms suitable for use in three-dimensional radiotherapy planning codes were compared. Two of the algorithms are based on ray-tracing methods, the first algorithm uses a fast ray-tracing procedure directly and the second employs a table lookup procedure; the table was originally calculated by ray tracing. The third algorithm was a convolution procedure using the fast Fourier transform. Benchmark programs were written to compare the fundamental running speeds of the three algorithms operating on three-dimensional arrays of various sizes. The convolution procedure employing the three-dimensional fast Fourier transform had the shortest running times on a VAX/750 (Digital Equipment Corp.) computer. We concluded that this algorithm holds significant potential for practical three-dimensional dose calculations.

Boyer, A.L.; Wackwitz, R.; Mok, E.C.

1988-03-01

402

Adaptive path control of a manipulator with visual information  

Microsoft Academic Search

A picture of a scene is used to extract information for an adaptive control algorithm. The object of interest is first located by means of a classifier. The position and orientation of the object are determined from a binary picture. The desired path which the gripper of the manipulator is to follow is specified by discrete points, first is the

A. J. Koivo; R. Lewczyk; T.-H. Chiu

1984-01-01

403

PULRP: Path Unaware Layered Routing Protocol for Underwater Sensor Networks  

Microsoft Academic Search

We propose a path unaware layered routing protocol (PULRP) for dense underwater 3D sensor networks. An uplink transmission is considered, where a set of underwater sensor nodes report events to the sink node. PURLP algorithm consists of two phases. In the first phase (layering phase), a layering structure is presented which is a set of concentric spheres, around a sink

Sarath Gopi; Kannan Kannan; Deepthi Chander; Uday B. Desai; S. N. Merchant

2008-01-01

404

Predictive Control of a Diesel Engine Air Path  

Microsoft Academic Search

This brief addresses the model-based control of the air path of diesel engines in terms of an optimal control problem with input constraints which can be solved using model predictive algorithms. A multilinear model identified from data and a switched controller design are used to cope with the nonlinearity of the engine. Experimental results on a production engine confirm that

Peter Ortner; Luigi del Re

2007-01-01

405

Economic Path Scheduling for Mobile Agent System on Computer Network  

NASA Astrophysics Data System (ADS)

Mobile agent technology has a lot of gains to offer network-centric applications. The technology promises to be very suitable for narrow-bandwidth networks by reducing network latency and allowing transparent per-to-per computing. Multi-agent technology had been proposed for many network-centric applications with little or no path scheduling algorithms. This paper describes the need for path scheduling algorithms for agents in multi-agent systems. Traveling salesman problem (TSP) scheme is used to model ordered agents and the unordered agents schedule their path based on random distribution. The two types of agents were modeled and simulated based on bandwidth usage and response time as performance metrics. Our simulation results shows that ordered agents have superior performance against unordered agents. The ordered agents exhibit lower bandwidth usage and higher response time.

Olajubu, E. A.

406

Properties of an adaptive feedback equalization algorithm.  

PubMed

This paper describes a new approach to feedback equalization for hearing aids. The method involves the use of an adaptive algorithm that estimates and tracks the characteristic of the hearing aid feedback path. The algorithm is described and the results of simulation studies and bench testing are presented. PMID:8263831

Engebretson, A M; French-St George, M

1993-01-01

407

Path concentration profile reconstruction of optical remote sensing measurements using polynomial curve fitting procedures  

Microsoft Academic Search

Open path Fourier transform infrared (OP-FTIR) spectroscopy is one of several optical remote sensing (ORS) techniques that can identify and quantify many air pollutants. These instruments provide path-integrated measurements along the scanning beam path. There is a growing interest in gaining spatial resolution from ORS through innovative multiple-beam configurations and mathematical algorithms. In this study, we explored the use of

Chang-fu Wu; Michael G. Yost; Ram A. Hashmonay; Ming-Yi Tsai

2003-01-01

408

Portage and Path Dependence*  

PubMed Central

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.

Bleakley, Hoyt; Lin, Jeffrey

2012-01-01

409

Byrds Flight Path  

NSDL National Science Digital Library

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

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

1999-11-08

410

Semiclassical Ehrenfest paths  

NASA Astrophysics Data System (ADS)

Trajectories are a central concept in our understanding of classical phenomena and also in rationalizing quantum mechanical effects. In this work we provide a way to determine semiclassical paths, approximations to quantum averages in phase space, directly from classical trajectories. We avoid the need of intermediate steps, like particular solutions to the Schroedinger equation or numerical integration in phase space by considering the system to be initially in a coherent state and by assuming that its early dynamics is governed by the Heller semiclassical approximation. Our result is valid for short propagation times only, but gives non-trivial information on the quantum-classical transition.

Liberalquino, Rafael; Parisio, Fernando

2013-08-01

411

The Path of Pollution  

NSDL National Science Digital Library

This lesson plan has students follow the path of pollution from the Chernobyl nuclear accident. They will name and locate countries to which radiation traveled and describe how air pollution moves from one area to another. In addition they will compare the chronological sequence of radiation travel with geographic distribution. Provided are: essential elements, objective, focus, a list of materials, background information, procedure, and ideas for extension and evaluation. Links provide the history of the accident and the data required to complete the investigation.

412

The California PATH Database  

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

413

From transition paths to transition states and rate coefficients.  

PubMed

Transition states are defined as points in configuration space with the highest probability that trajectories passing through them are reactive (i.e., form transition paths between reactants and products). In the high-friction (diffusive) limit of Langevin dynamics, the resulting ensemble of transition states is shown to coincide with the separatrix formed by points of equal commitment (or splitting) probabilities for reaching the product and reactant regions. Transition states according to the new criterion can be identified directly from equilibrium trajectories, or indirectly by calculating probability densities in the equilibrium and transition-path ensembles using umbrella and transition-path sampling, respectively. An algorithm is proposed to calculate rate coefficients from the transition-path and equilibrium ensembles by estimating the frequency of transitions between reactants and products. PMID:15267886

Hummer, Gerhard

2004-01-01

414

FPGA-based tool path computation: An application for shoe last machining on CNC lathes  

Microsoft Academic Search

Tool path generation is one of the most complex problems in computer aided manufacturing. Although some efficient strategies have been developed, most of them are only useful for standard machining. The algorithm called Virtual Digitizing computes the tool path by means of a virtually digitized model of the surface and a geometry specification of the tool and its motion, so

Antonio Jimeno; José Luis Sánchez; Higinio Mora Mora; Jerónimo Mora Pascual; Juan Manuel García Chamizo

2006-01-01

415

A model and strategy for train pathing with choice of lines, platforms, and routes  

Microsoft Academic Search

Train pathing is concerned with assigning trains and train times for a set of rail links, stations stops, etc., so as to meet a system of constraints on headways, trip times, dwell times, etc. while minimizing delays or costs and meeting travel demands. In a previous paper we presented a model, algorithms, and strategy for pathing trains of different speeds

Malachy Carey

1994-01-01

416

Analysis of propagation path for location of base-station in the microcell CDMA mobile communications  

Microsoft Academic Search

In microcell mobile communication, we analyze the propagation path which can accurately and rapidly interpret mobile communication propagation in an urban environment, when the subscriber service is based on the urban main road. To find the appropriate BS location in an urban street, we suggest a simplified algorithm to interpret the propagation path and a propagation prediction model which can

Sun-Kuk Noh; Chang-Gyun Park

2004-01-01

417

Evolutionary path planning for autonomous underwater vehicles in a variable ocean  

Microsoft Academic Search

This paper proposes a genetic algorithm (GA) for path planning of an autonomous underwater vehicle in an ocean environment characterized by strong currents and enhanced space-time variability. The goal is to find a safe path that takes the vehicle from its starting location to a mission-specified destination, minimizing the energy cost. The GA includes novel genetic operators that ensure the

Alberto Alvarez; Andrea Caiti; Reiner Onken

2004-01-01

418

Binary Trees, Left and Right Paths, WKB Expansions, and Painleve Transcendents  

Microsoft Academic Search

During the 10th Seminar on Analysis of Algorithms, MSRI, Berkeley, June 2004, Knuth posed the problem of analyzing the left and the right path length in a random binary trees. In particular, Knuth asked about properties of the generating function of the joint distribution of the left and the right path lengths. In this paper, we mostly focus on the

Charles Knessl; Wojciech Szpankowski

419

Comparison of Two Fitness Functions for GA-Based Path-Oriented Test Data Generation  

Microsoft Academic Search

Automatic path-oriented test data generation is not only a crucial problem but also a hot issue in the research area of software testing today. As a robust metaheuritstic search method in complex spaces, genetic algorithm (GA) has been used to path-oriented test data generation since 1992 and outperforms other approaches. A fitness function based on branch distance (BDBFF) and another

Yong Chen; Yong Zhong; Tingting Shi; Jingyong Liu

2009-01-01

420

Real-time path planning for Aerial robot in real environments  

Microsoft Academic Search

The problem of real-time path planning in actual environments is challenging. This paper presents a realtime planning algorithm using image processing techniques for navigating a Aerial robot in known irregular environments. It includes two steps. The proposed strategy, based on the generation of a novel search space, finds a suboptimal rough path as an initial condition by constructing and searching

Liting Wu; Yuan Tian; Yiping Yang

2009-01-01

421

Flatness-based vehicle online path following with time-varying constraints of dynamics  

Microsoft Academic Search

In this paper, we consider the vehicle online path following under structure environment as object of our researching. By using the rolling method, a trajectory gen- eration method based on flatness and a local path planning algorithm are proposed according to the characters of structure environment. In order to satisfy feasibility and safety, time- varying dynamics constraints are taken into

Cong Yanfeng; Yu Zaitao; Chen Hong; Oliver Sawodny

2011-01-01

422

A model of ant colony and immune network and its application in path planning  

Microsoft Academic Search

Inspired by related mechanisms of ant colony and idiotypic network hypothesis, a model of ant colony and immune network is proposed to solve the problem of path planning in a complex environment. The mechanism of stimulation and suppression between antigen and antibody is used to find the path, which solves the complex environment modeling of ant colony algorithm, and improves

Mingxin Yuan; Sunan Wang; Pengkun Li

2008-01-01

423

Path planning and tracking for Agricultural master-slave robot system  

Microsoft Academic Search

This paper proposes a path planning and tracking algorithm for Agricultural master-slave robot system. The robot system based on the algorithm can be applied to harvesting, tillage, planting and cultivating. The task of master is to cover the entire field by complete coverage path-planning method based on sub-region. At the same time, the master accomplishes the work such as harvesting,

Peng Zhang; Junfei Qiao; Hengyi Zhang

2010-01-01

424

Photodeactivation paths in norbornadiene.  

PubMed

The first high level ab initio quantum-chemical calculations of potential energy surfaces (PESs) for low-lying singlet excited states of norbornadiene in the gas phase are presented. The optimization of the stationary points (minima and conical intersections) and the recalculation of the energies were performed using the multireference configuration interaction with singles (MR-CIS) and the multiconfigurational second-order perturbation (CASPT2) methods, respectively. It was shown that the crossing between valence V2 and Rydberg R1 states close to the Franck-Condon (FC) point permits an easy population switch between these states. Also, a new deactivation path in which the doubly excited state with (?3)(2) configuration (DE) has a prominent role in photodeactivation from the R1 state due to the R1/DE and the DE/V1 conical intersections very close to the R1 and DE minima, respectively, was proposed. Subsequent deactivation from the V1 to the ground state goes through an Olivucci-Robb-type conical intersection that adopts a rhombic distorted geometry. The deactivation path has negligible barriers, thereby making ultrafast radiationless decay to the ground state possible. PMID:23553256

Antol, Ivana

2013-04-03

425

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

NASA Astrophysics Data System (ADS)

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

Wen, Bo; Shenai, Ramakrishna; Sivalingam, Krishna

2005-09-01

426

Simulation and validation of subsurface lateral flow paths in an agricultural landscape  

NASA Astrophysics Data System (ADS)

The importance of soil water flow paths to the transport of nutrients and contaminants has long been recognized. However, effective means of detecting subsurface flow paths in a large landscape is still lacking. The flow direction and accumulation algorithm in GIS hydrologic modeling is a cost effective way to simulate potential flow paths over a large area. This study tested this algorithm for simulating lateral flow paths at three interfaces in soil profiles in a 19.5-ha agricultural landscape in central Pennsylvania, USA. These interfaces were (1) the surface plowed layers (Ap1 and Ap2 horizons) interface, (2) the interface with subsoil clay layer where clay content increased to over 40%, and (3) soil-bedrock interface. The simulated flow paths were validated through soil hydrologic monitoring, geophysical surveys, and observable soil morphological features. The results confirmed that subsurface lateral flow occurred at the interfaces with the clay layer and the underlying bedrock. At these two interfaces, the soils on the simulated flow paths were closer to saturation and showed more temporally unstable moisture dynamics than those off the simulated flow paths. Apparent electrical conductivity in the soil on the simulated flow paths was elevated and temporally unstable as compared to those outside the simulated paths. The soil cores collected from the simulated flow paths showed significantly higher Mn contents at these interfaces than those away from the simulated paths. These results suggest that (1) the algorithm is useful in simulating possible subsurface lateral flow paths if used appropriately with sufficiently detailed digital elevation model; (2) repeated electromagnetic surveys can reflect the temporal change of soil water storage and thus is an indicator of soil water movement over the landscape; and (3) observable Mn content in soil profiles can be used as a simple indicator of water flow paths in soils and over the landscape.

Zhu, Q.; Lin, H. S.

2009-04-01

427

pathChirp: Efficient Available Bandwidth Estimation for Network Paths  

SciTech Connect

This paper presents pathChirp, a new active probing tool for estimating the available bandwidth on a communication network path. Based on the concept of ''self-induced congestion,'' pathChirp features an exponential flight pattern of probes we call a chirp. Packet chips offer several significant advantages over current probing schemes based on packet pairs or packet trains. By rapidly increasing the probing rate within each chirp, pathChirp obtains a rich set of information from which to dynamically estimate the available bandwidth. Since it uses only packet interarrival times for estimation, pathChirp does not require synchronous nor highly stable clocks at the sender and receiver. We test pathChirp with simulations and Internet experiments and find that it provides good estimates of the available bandwidth while using only a fraction of the number of probe bytes that current state-of-the-art techniques use.

Cottrell, Les

2003-04-30

428

Efficient capacity sharing for path protection in meshed optical networks  

NASA Astrophysics Data System (ADS)

Efficient resource management in meshed optical networks is critical for supporting differentiated services, such as network restoration, in a cost-competitive manner. We propose and study several alternatives for dynamic and distributed selection of primary and protection paths. The focus is on algorithms where the bandwidth can be shared efficiently among protection paths, although other alternatives are considered as well. The routing algorithm and link cost function are based on a Markov decision-process framework. In particular, we use this framework to justify the link cost structure for primary and shared bandwidth. We also propose and study several options for describing the link state, which in turn determines the link cost, with the objective of minimizing the amount of data to be advertised without sacrificing performance. The proposed solutions can be implemented without changing the existing set of protocols. The numerical results show performance and cost savings for the different algorithm options.

Dziong, Zbigniew; Nagarajan, Ramesh

2004-03-01

429

pathChirp: Efficient Available Bandwidth Estimation for Network Paths  

Microsoft Academic Search

This paper presents pathChirp, a new active probing tool for estimating the available bandwidth on a communication network path. Based on the concept of ''self-induced congestion,'' pathChirp features an exponential flight pattern of probes we call a chirp. Packet chips offer several significant advantages over current probing schemes based on packet pairs or packet trains. By rapidly increasing the probing

Les

2003-01-01

430

Critical Path-Based Thread Placement for NUMA Systems  

SciTech Connect

Multicore multiprocessors use a 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 algorithms and a runtime system that optimize the execution of OpenMP applications on NUMA architectures. By collecting information from hardware counters, the runtime system directs thread placement and reduces performance penalties by minimizing the critical path of OpenMP parallel regions. The runtime system uses a scalable algorithm that derives placement decisions with negligible overhead. We evaluate our algorithms and runtime system with four NPB applications implemented in OpenMP. On average the algorithms achieve between 8.13% and 25.68% performance improvement compared to the default Linux thread placement scheme. The algorithms miss the optimal thread placement in only 8.9% of the cases.

Su, C Y; Li, D; Nikolopoulos, D S; Grove, M; Cameron, K; de Supinski, B R

2011-11-01

431

A Fast Taboo Search Algorithm for the Job Shop Problem  

Microsoft Academic Search

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

432

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

Microsoft Academic Search

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

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

2008-01-01

433

Measurements of direct path and folded path optical scintillation path weightings  

NASA Astrophysics Data System (ADS)

A theoretical prediction by Dr. Avihu Ze'evi of the relative contribution to the optical scintillation by different points along the path was described by a weight function for direct and exact folded path spherical wave sources. In an effort to verify this prediction a turbulence chamber was built to allow a controlled turbulence source to be moved and measured at different path positions in conjunction with scintillation measurements. The experimental results follow Dr. Ze'evi's general pattern but both sources are less weighted at the detector end than predicted and the folded path is more heavily weighted at the target end than predicted.

Costantine, A. G.

1983-06-01

434

A Differential Tree Approach to Price Path-Dependent American Options using Malliavin Calculus  

NASA Astrophysics Data System (ADS)

We propose a recursive schemes to calculate backward the values of conditional expectations of functions of path values of Brownian motion. This scheme is based on the Clark-Ocone formula in discrete time. We suggest an algorithm based on our scheme to effectively calculate the price of American options on securities with path-dependent payoffs. For problems where the path-dependence comes only from the path-dependence of the state variables our method is less subject to the curse of dimensionality observed in all other methods.

Schellhorn, Henry; Morris, Hedley

2009-05-01

435

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

PubMed Central

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.

Fernando, Chrisantha; Vasas, Vera; Szathmary, Eors; Husbands, Phil

2011-01-01

436

Genetic Algorithms  

Microsoft Academic Search

In this chapter we describe the basics of Genetic Algorithms and how they can be used to train Artificial Neural Networks.\\u000a Supervised training of Multilayer Perceptrons for classification problems is considered. We also explain how the Genetic Algorithm\\u000a can be hybridized with other algorithms and present two hybrids between it and two classical algorithms for the neural network\\u000a training: Backpropagation

Enrique Alba; Francisco Chicano

437

Path Diversity Aware Interdomain Routing  

Microsoft Academic Search

Abstract—As the Internet becomes the critical information infrastructure for both personal and business applications, fast and reliable routing protocols need to be designed to maintain the performance of those applications in the presence of failures. Today’s interdomain routing protocol, BGP, is known to be slow in reacting and recovering from network failures. Increasing path diversity by advertising multiple paths is

Feng Wang; Lixin Gao

2009-01-01

438

Fracture paths and ultrananocrystalline diamond  

Microsoft Academic Search

We use the simulated fracture of ultrananocrystalline diamond (UNCD) to illustrate how different fracture paths can result in different predictions of system properties. At zero temperature, the system is unable to explore the potential energy surface far from the fracture path being investigated. This can result in misleading predictions for the mechanical properties of UNCD. In non-zero temperature simulations, the

Jeffrey T. Paci; Lipeng Sun; Ted Belytschko; George C. Schatz

2005-01-01

439

Path Analysis: A Brief Introduction.  

ERIC Educational Resources Information Center

Path analysis is presented as a technique that can be used to test on a priori model based on a theoretical conceptualization involving a network of selected variables. This being an introductory source, no previous knowledge of path analysis is assumed, although some understanding of the fundamentals of multiple regression analysis might be…

Carducci, Bernardo J.

440

Obstacle avoidance and path planning  

Microsoft Academic Search

Outlines the state-of-the-art in obstacle avoidance and path planning for industrial robots that is practical on the current generation of computer hardware. Describes practical vehicle planners and planning for manipulators. Summarizes that obstacle avoidance and path planning are techniques with differing goals. Sonar is the standard method of obstacle avoidance systems which is largely limited by the reliability of the

Stephen Cameron

1994-01-01

441

Performance of Path-Planning Agents in an Agent-Based Distillation  

Microsoft Academic Search

Existing agent-based distillation systems (ABDs)- such as MANA, CROCADILE, or SOCRATES - use quite simple algorithms for controlling the motion of an entity. This paper examines an alt ernate, and more sophisticated, approach to determining agent motion. A path-planning algorithm is implemented within the context of the CROCADILE agents and its performance quantified according to a number of parameters. The

Lam Thu Bui; Michael Barlow

2003-01-01

442

Algorithm Engineering  

Microsoft Academic Search

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

443

Using the ACO algorithm for path searches in social networks  

Microsoft Academic Search

One of the most important types of applications currently being used to share knowledge across the Internet are social networks.\\u000a In addition to their use in social, professional and organizational spheres, social networks are also frequently utilized\\u000a by researchers in the social sciences, particularly in anthropology and social psychology. In order to obtain information\\u000a related to a particular social network,

Jessica Rivero; Dolores Cuadra; Javier Calle; Pedro Isasi

444

Path planning for multiple Unmanned Aerial Vehicles using genetic algorithms  

Microsoft Academic Search

In the future, autonomous Unmanned Aerial Vehicles (UAVs) need to work in teams to share information and coordinate activities. The private sector and government agencies have implemented UAVs for home-land security, reconnaissance, surveillance, data collection, urban planning, and geometrics engineering. Significant research is in progress to support the decision-making process for a Multi-Agent System (MAS) consisting of multiple UAVs. This

Howard Li; Yi Fu; Khalid Elgazzar; Liam Paull

2009-01-01

445

Vehicle Path Planning for Complete Field Coverage Using Genetic Algorithms  

Microsoft Academic Search

In farming operations, one of the fundamental issues facing a farmer is the cost of running the farm. If the equipment the farmer is using can be made more efficient, the cost of farming will be reduced. One way of making agricultural equipment more efficient is to develop automated or autonomous functions for the equipment. One of the fundamental tasks

A. E. F. Ryerson; Q. Zhang

2007-01-01

446

Path lengths, correlations, and centrality in temporal networks.  

PubMed

In temporal networks, where nodes interact via sequences of temporary events, information or resources can only flow through paths that follow the time ordering of events. Such temporal paths play a crucial role in dynamic processes. However, since networks have so far been usually considered static or quasistatic, the properties of temporal paths are not yet well understood. Building on a definition and algorithmic implementation of the average temporal distance between nodes, we study temporal paths in empirical networks of human communication and air transport. Although temporal distances correlate with static graph distances, there is a large spread, and nodes that appear close from the static network view may be connected via slow paths or not at all. Differences between static and temporal properties are further highlighted in studies of the temporal closeness centrality. In addition, correlations and heterogeneities in the underlying event sequences affect temporal path lengths, increasing temporal distances in communication networks and decreasing them in the air transport network. PMID:21867255

Pan, Raj Kumar; Saramäki, Jari

2011-07-18

447

Daylighting design overlays for equidistant sun-path projections  

SciTech Connect

Projections of the Sun's daily and seasonal paths frequently are used to solve building design problems involving site obstructions and shading of fenestration. In the United States, equidistant projections are perhaps the most widely used (compared to other sunpath projections) because of the commercial availability of a complete set of sun-path diagrams for a range of useful latitudes. This paper describes the development of a set of overlays designed for use with sun-path projections to predict illumination on any building surface throughout the year for standard climatological conditions. Illumination is calculated for clear and overcast skies and for direct sunlight using algorithms recommended by the Commission Internationale de l'Eclairage (CIE). Values for illumination incident upon the surface, as well as transmitted through single and double glazing, can be calculated. Similar overlays for solar radiation are being developed.

Selkowitz, S.

1981-08-01

448

Efficient computation paths for the systematic analysis of sensitivities  

NASA Astrophysics Data System (ADS)

A systematic sensitivity analysis requires computing the model on all points of a multi-dimensional grid covering the domain of interest, defined by the ranges of variability of the inputs.The issues to efficiently perform such analyses on algebraic models are handling solution failures within and close to the feasible region and minimizing the total iteration count. Scanning the domain in the obvious order is sub-optimal in terms of total iterations and is likely to cause many solution failures.The problem of choosing a better order can be translated geometrically into finding Hamiltonian paths on certain grid graphs.This work proposes two paths, one based on a mixed-radix Gray code and the other, a quasi-spiral path, produced by a novel heuristic algorithm. Some simple, easy-to-visualize examples are presented, followed by performance results for the quasi-spiral algorithm and the practical application of the different paths in a process simulation tool.

Greppi, Paolo; Arato, Elisabetta

2013-01-01

449

Path following control system for a tanker ship model  

Microsoft Academic Search

A two-dimensional path following control system for autonomous marine surface vessels is presented. The guidance system is obtained through a way-point guidance scheme based on line-of-sight projection algorithm and the speed controller is achieved through state feedback linearization. A new approach concerning the calculation of a dynamic line-of-sight vector norm is presented which main idea is to improve the speed

Lúcia Moreira; Thor I. Fossen; C. Guedes Soares

2007-01-01

450

ROBUSTNESS ASSESSMENT OF ADAPTIVE FDI SYSTEM FOR ENGINE AIR PATH  

Microsoft Academic Search

Robustness assessment is important for every newly developed method. This paper presents robustness assessment of a new adaptive on-board fault diagnosis algorithm for the air-path of spark ignition (SI) engines. The method uses a radial basis function (RBF) neural network to classify pre-defined possible faults from engine measurements, reporting fault occurrence as well as the type and size of a

M. S. SANGHA; D. L. YU; J. B. GOMM

451

Evaluation Techniques for Generalized Path Pattern Queries on XML Data  

Microsoft Academic Search

Finding the occurrences of structural patterns in XML data is a key operation in XML query processing. Existing algorithms\\u000a for this operation focus almost exclusively on path patterns or tree patterns. Current applications of XML require querying\\u000a of data whose structure is complex or is not fully known to the user, or integrating XML data sources with different structures.\\u000a These

Xiaoying Wu; Dimitri Theodoratos; Stefanos Souldatos; Theodore Dalamagas; Timos K. Sellis

2010-01-01

452

Computation of paths for rays in nonuniformly heated solids  

SciTech Connect

This paper presents a general algorithm for the numerical construction of ultrasonic ray paths in a medium having an arbitrary variation of sound velocity with the coordinates. By using it, systematic errors are revealed when determining the coordinates of flaws while inspecting welded joints during the welding process owing to the effects of refraction. Multipass automatic welding of massive products such as a housing for equipment in a nuclear power station is discussed.

Tsvetyanskii, V.L.; Mandel', A.M.

1986-01-01

453

Continuous Steepest Descent Path for Traversing Non-convex Regions  

Microsoft Academic Search

This paper revisits the ideas of seeking unconstrained minima by following a continuous steepest descent path (CSDP). We are especially interested in the merits of such an ap- proach in regions where the objective function is non-convex and Newton-like methods become ineffective. The paper combines ODE-trajectory following with trust-region ideas to give an algorithm which performs curvilinear searches on each

S. Beddiaf

2009-01-01

454

An introduction to critical paths.  

PubMed

A critical path defines the optimal sequencing and timing of interventions by physicians, nurses, and other staff for a particular diagnosis or procedure. Critical paths are developed through collaborative efforts of physicians, nurses, pharmacists, and others to improve the quality and value of patient care. They are designed to minimize delays and resource utilization and to maximize quality of care. Critical paths have been shown to reduce variation in the care provided, facilitate expected outcomes, reduce delays, reduce length of stay, and improve cost-effectiveness. The approach and goals of critical paths are consistent with those of total quality management (TQM) and can be an important part of an organization's TQM process. PMID:15739581

Coffey, Richard J; Richards, Janet S; Remmert, Carl S; LeRoy, Sarah S; Schoville, Rhonda R; Baldwin, Phyllis J

455

Squeezed States and Path Integrals.  

National Technical Information Service (NTIS)

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

I. Daubechies J. R. Klauder

1992-01-01

456

Real Time Path Integral Methods  

Microsoft Academic Search

An efficient methodology has been developed for simulating the long-time dynamics of quantum dissipative processes modeled in terms of a system coupled to a multidimensional harmonic bath. The starting point is expression of the path integral in terms of a quasi-adiabatic propagator which allows large time increments. The resulting quasi-adiabatic propagator path integral is evaluated on a system-specific discrete variable

Nancy Makri

1998-01-01

457

The Shortest Period sdB Plus White Dwarf Binary CD-30 11223 (GALEX J1411-3053)  

NASA Astrophysics Data System (ADS)

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 2/M ? >~ 0.77) assuming a canonical mass for the hot subdwarf (0.48 M ?), although a white dwarf mass as low as 0.75 M ? is allowable by postulating a subdwarf mass as low as 0.44 M ?. The amplitude of ellipsoidal variations and a high rotation velocity imposed a high-inclination to the system (i >~ 68°) and, possibly, observable secondary transits (i >~ 74°). At the lowest permissible inclination and assuming a subdwarf mass of ~0.48 M ?, the total mass of the system reaches the Chandrasekhar mass limit at 1.35 M ? and would exceed it for a subdwarf mass above 0.48 M ?. 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 ?30 Myr. Based on observations made with ESO telescopes at the La Silla Paranal Observatory under program IDs 83.D-0540, 85.D-0866, and 089.D-0864.

Vennes, S.; Kawka, A.; O'Toole, S. J.; Németh, P.; Burton, D.

2012-11-01

458

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

459

An element-failure algorithm for dynamic crack propagation in general directions  

Microsoft Academic Search

An algorithm is presented for the finite element analysis of dynamic elastic–plastic fracture mechanics. The algorithm allows crack propagation in any direction, but does not require remeshing or the definition of new contact surfaces. This is achieved by tracking the path of the crack tip and failing the elements crossed by the path such that they can no longer sustain

S. R. Beissel; G. R. Johnson; C. H. Popelar

1998-01-01

460

Locally optimal decomposition for autonomous obstacle avoidance with the Tunnel-MILP algorithm  

Microsoft Academic Search

The Tunnel-MILP algorithm is a three stage path planning method for 2-D environments that relies on the iden- tification of a sequence of convex polygons to form an obstacle free tunnel through which to plan a dynamically feasible path. This work investigates two aspects of the algorithm. First, a greedy cut method is proposed for improved decomposition of the environment,

Michael P. Vitus; Steven L. Waslander; Claire J. Tomlin

2008-01-01

461

Heuristically optimal path scanning for high-speed multiphoton circuit imaging  

PubMed Central

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.

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

2011-01-01

462

Fuzzy Least-Congested Path Routing and Improved Remote-Path Routing based on Hierarchical Information in WDM Networks  

Microsoft Academic Search

Although routing schemes based on global knowledge make most optimal routing decisions, they will occupy many resources to keep the state information of the network up-to-date. In this work, we describe a fuzzy least-congested path (FLCP) routing algorithm based on hierarchical information. Simulation shows that the blocking probability using FLCP is very near to the blocking probability using the least-congested

Gang Yu; Anshi Xu

2004-01-01

463

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

Microsoft Academic Search

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

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

2011-01-01

464

Process Variation Aware Transistor Sizing for Load Balance of Multiple Paths in Dynamic CMOS for Timing Optimization  

Microsoft Academic Search

The complexity in timing optimization of high- performance microprocessors has been increasing with the number of channel-connected transistors in various paths of dynamic CMOS circuits and the rising magnitude of process variations in nanometer CMOS process. In this paper, a process variation aware transistor sizing algorithm for dynamic CMOS circuits while considering the Load Balance of Multiple Paths (LBMP) is

Kumar Yelamarthi; Chien-in Henry Chen

2008-01-01

465

Paths, Trees and Cycles in Tournaments  

Microsoft Academic Search

We survey results on paths, trees and cycles in tournaments. The main subjects are hamiltonian paths and cycles, vertex and arc disjoint paths with prescribed endvertices, arc-pancyclicity, oriented paths, trees and cycles in tour- naments. Several unsolved problems are included.

Jørgen Bang-Jensen; Gregory Gutin

466

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

SciTech Connect

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

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

2012-11-01

467

Generalized Nets as Tools for Modeling of the Ant Colony Optimization Algorithms  

Microsoft Academic Search

\\u000a Ant Colony Optimization (ACO) has been used successfully to solve hard combinatorial optimization problems. This metaheuristic\\u000a method is inspired by the foraging behavior of ant colonies, which manage to establish the shortest routes to feeding sources\\u000a and back. We discuss some possibilities for describing of the ACO algorithms by Generalized Nets (GNs), that help us deeply\\u000a to understand the processes

Stefka Fidanova; Krassimir Atanassov

2009-01-01

468

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

NASA Astrophysics Data System (ADS)

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

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

469

Path selection in disaster response management based on Q-learning  

Microsoft Academic Search

Suitable rescue path selection is very important to rescue lives and reduce the loss of disasters, and has been a key issue\\u000a in the field of disaster response management. In this paper, we present a path selection algorithm based on Q-learning for\\u000a disaster response applications. We assume that a rescue team is an agent, which is operating in a dynamic

Zhao-Pin Su; Jian-Guo Jiang; Chang-Yong Liang; Guo-Fu Zhang

2011-01-01

470

Propagation Path Analysis for Location Selection of Base-Station in the Microcell Mobile Communications  

Microsoft Academic Search

\\u000a In microcell mobile communication using cellular method, we analyze propagation path which can accurately and rapidly interpret\\u000a mobile communication propagation environment in urban, when subscriber service is done based on the main road in urban.  In\\u000a this paper, to appropriate location of BS in urban street, we suggest a simplified algorithm to interpret a propagation path\\u000a and a propagation prediction

Sun-kuk Noh; Dong-you Choi; Chang-kyun Park

2005-01-01

471

Tubular Structure Segmentation Based on Minimal Path Method and Anisotropic Enhancement  

Microsoft Academic Search

We present a new interactive method for tubular structure extraction. The main application and motivation for this work is\\u000a vessel tracking in 2D and 3D images. The basic tools are minimal paths solved using the fast marching algorithm. This allows\\u000a interactive tools for the physician by clicking on a small number of points in order to obtain a minimal path

Fethallah Benmansour; Laurent D. Cohen

2011-01-01

472

Two additive-constrained path selection in the presence of inaccurate state information  

Microsoft Academic Search

In this paper, we study quality-of-service (QoS) routing, particularly two additive-constrained path problem, in the presence of inaccurate state information. We formulate this problem as most-probable two-additive-constrained path (MP-TACP) problem. To solve it, we follow a probabilistic approach and propose an algorithm called MP-TACPA. In general, MP-TACPA uses pre- and on-demand computation along with both linear and nonlinear search techniques.

Yanxing Zheng; Turgay Korkmaz; Wanhua Dou

2005-01-01

473

Coverage path planning for harbour seabed surveys using an autonomous underwater vehicle  

Microsoft Academic Search

This paper considers offline algorithms for pre-mission path planning to achieve coverage of the seabed of a complex but well-characterised planar area using an autonomous underwater vehicle fitted with side-looking sonar. The vehicle can swim over terrain at constant altitude, but must follow a path constructed from straight line segments. Imagery collected during turns is not used. This paper discusses

Cheng Fang; Stuart Anstee

2010-01-01

474

Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation  

Microsoft Academic Search

In this paper we present a modular interprocedural pointer analysis algorithm based on access-paths for C programs. We argue that access paths can reduce the overhead of representing context-sensitive transfer functions and effectively distinguish non-recursive heap objects. And when the modular analysis paradigm is used together with other techniques to handle type casts and function pointers, we are able to

Ben-Chung Cheng; Wen-mei W. Hwu

2000-01-01

475

Bandwidth-delay based routing algorithms  

Microsoft Academic Search

Multimedia applications often require guaranteed quality of service and resource reservation, which has raised a number of challenging technical issues for routing. We consider two new routing algorithms based on bandwidth and delay metrics. The implications of routing metrics on path computation are examined and the rationales behind the selection of bandwidth and delay metrics are discussed. Two new routing

Zheng Wang; Jon Crowcroft

1995-01-01

476

Datagram Routing Algorithm for LEO Satellite Networks  

Microsoft Academic Search

Satellite networks provide global coverage andsupport a wide range of services. Low Earth Orbit (LEO)satellites provide short round trip delays and are becomingincreasingly important. One of the challenges in LEOsatellite networks is the development of specialized and efficientrouting algorithms. In this work, a datagram routingalgorithm for LEO satellite networks is introduced. The algorithmgenerates minimum propagation delay paths. Theperformance of the

Eylem Ekici; Ian F. Akyildiz; Michael D. Bender

2000-01-01

477

Algorithm Analysis.  

National Technical Information Service (NTIS)

This report lists known problems associated with fix estimation and emitter identification. In many cases a list of known errors associated with the algorithm itself is appended. Finally, MARC described its simulation model is described. Keywords: Fix est...

M. W. Rennie J. Onghre

1983-01-01

478

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

479

On the general false path problem in timing analysis  

Microsoft Academic Search

The false path problem is often referred to as the problem of detecting the longest sensitizable path (A path which is not a false path is a sensitizable path). The term “false path” is not clearly defined. In this paper, we first give a clear and precise definition of a false path. Then the general false path problem is formulated.

David Hung-Chang Du; S. H. Yen; Subbarao Ghanta

1989-01-01

480

Computing Geodesic Paths on Manifolds  

Microsoft Academic Search

The Fast Marching Method is a numerical algorithm for solving the Eikonal equation on a rectangular orthogonal mesh in O(MlogM) steps, where M is the total number of grid points. In this paper we extend the Fast Marching Method to triangulated domains with the same computational complexity. As an application, we provide an optimal time algorithm for computing the geodesic

R. Kimmel; J. A. Sethian

1998-01-01

481

Hierarchical Encoded Path Views for Path Query Processing: An Optimal Model and Its Performance Evaluation  

Microsoft Academic Search

Efficient path computation is essential for applications such as intelligent transportation systems (ITS) and network routing. In ITS navigation systems, many path requests can be submitted over the same, typically huge, transportation network within a small time window. While path precomputation (path view) would provide an efficient path query response, it raises three problems which must be addressed: 1) precomputed

Ning Jing; Yun-wu Huang; Elke A. Rundensteiner

1998-01-01

482

An Adaptive Ant Colony Algorithm Based on Equilibrium of Distribution  

Microsoft Academic Search

To settle the contradictory between convergence speed and precocity and stagnation in ant colony algorithm, an adaptive ant colony algorithm, which is based on the equilibrium of the ant distribution, is presented. By dynamically adjusting the influence of each ant to the trail information updating and the selected probabilities of the paths according to the equilibrium of the ant distribution,

CHEN Ling; SHEN Jie; QIN Ling; CHEN Hong-Jian

483

An Efficient Algorithm for Shielding Electromagnetic Topological Diagram  

Microsoft Academic Search

An electromagnetic topology method used to analyze interactions between electronic systems and electromagnetic environment is presented. Combining electromagnetic topology model with the graph theory, an efficient algorithm is obtained. The algorithm can find out all the paths which have a lower shielding coefficient than the given threshold K in the shielding electromagnetic topological diagram.

Yongfeng Wang; Chengda Yu; Chaowei Zhang

2010-01-01

484

Polynomial time algorithm for hop constrained QoS routing  

NASA Astrophysics Data System (ADS)

The basis of a QoS-based routing algorithm is a dynamic network dependent cost function that is used to find the optimal or at least a feasible route across the network. However, all QoS-based routing algorithms suffer from a major drawback. The cost function at the core of the algorithms identifies segments of the network where resources are ample and exploits them to the benefit of connections that would otherwise cross a congested portion of the network. Thus, the algorithms consume more resources than Minimum Hop routing would do when the network traffic is non-stationary and heavy. QoS-based routing, thus, wastes resources and performs poorly compared with Minimum Hop routing in the event of congestion. The crux of the discussion is that whatever is gained at low or medium network loads, is offset at high network loads. What is required is a resilient algorithm that either allows the migration of a QoS-based routing algorithm to a Minimum Hop algorithm at high loads or an algorithm that merges Minimum Hop and QoS characteristics. The study opts for the latter approach and proposes and exhibits a hop constrained QoS routing algorithm that outperforms traditional QoS routing algorithms during simulation. This routing technique is based on an approximation algorithm that solves the hop constrained routing problem. The algorithm is derived from a dynamic programming FPAS scheme and finds the shortest walk for a single source destination pair in a graph with restricted number of hops when all the edge costs are non-negative. Simulated results demonstrate that routing technique based on the algorithm is robust to changes in the traffic pattern and consistently outperforms other QoS based routing techniques under heavy load conditions.

Verma, Shekhar; Saxena, Anil K.

2003-08-01

485

Career Paths of Academic Deans.  

ERIC Educational Resources Information Center

|This paper examines various career paths leading to deanship and considers the implications of the findings for women and minorities who aspire to this position. The paper is part of a larger study of academic deanship conducted by the Center for Academic Leadership at Washington State University between October 1996 and January 1997. Data for…

Wolverton, Mimi; Gonzales, Mary Jo

486

Employer Resource Manual. Project Path.  

ERIC Educational Resources Information Center

|Project Path at Illinois' College of DuPage was established to provide pre-employment training and career counseling for disabled students. To encourage the integration of qualified individuals with disabilities into the workplace, the project compiled this resource manual for area businesses, providing tips for interacting with disabled people…

Kane, Karen R.; Del George, Eve

487

Complexity of Path Forming Games.  

National Technical Information Service (NTIS)

For a number of two player games where players alternately choose the next vertex of a simple or elementary path in a graph, the authors considers the problem to determine whether for a given game instance there is a winning strategy for the first player....

H. L. Bodlaender

1989-01-01

488

Alternative Nuclear Paths To 2050  

Microsoft Academic Search

he circumstances surrounding nuclear power worldwide and the importance that may be given to issues affecting its future development point toward very different alternative paths over the next 50 years. Economic deregulation, lack of competitiveness in some countries, negative public perception and concerns about waste issues suggest that nuclear power might decrease progressively with a potential phase-out of the technology

Ivan Vera; Evelyne Bertel; Geoffrey Stevens

489

Thinking on the Write Path  

ERIC Educational Resources Information Center

The present paper underscores the importance of the cognitive orientation of English as a Foreign Language (EFL) students in their success in writing courses. A few suggestions are made as to how EFL teachers can put their students on the right cognitive path in their writings.

Salmani-Nodoushan, Mohammad Ali

2007-01-01

490

Beam wander experiments: terrestrial path  

Microsoft Academic Search

We report on a set of measurements made in December 2005 by researchers from the University of Central Florida, SPAWAR's Innovative Science and Technology Experiment Facility (ISTEF), Harris Corporation, NASA Kennedy Space Center, and Northrop Grumman. The experiments were conducted on the Shuttle Landing Facility (SLF) at Kennedy Space Center (KSC) over terrestrial paths of 1, 2, and 5 km.

R. L. Phillips; L. C. Andrews; J. Stryjewski; B. Griffis; M. Borbath; D. Galus; G. Burdge; K. Green; C. Kim; D. Stack; C. Harkrider; D. Wayne; D. Hand; J. Kiriazes

2006-01-01

491

Perceived Shrinkage of Motion Paths  

ERIC Educational Resources Information Center

|We show that human observers strongly underestimate a linear or circular trajectory that a luminous spot follows in the dark. At slow speeds, observers are relatively accurate, but, as the speed increases, the size of the path is progressively underestimated, by up to 35%. The underestimation imposes little memory load and does not require…

Sinico, Michele; Parovel, Giulia; Casco, Clara; Anstis, Stuart

2009-01-01

492

The path to adaptive microsystems  

Microsoft Academic Search

Scaling trends in microsystems are discussed frequently in the technical community, providing a short-term perspective on the future of integrated microsystems. This paper looks beyond the leading edge of technological development, focusing on new microsystem design paradigms that move far beyond today's systems based on static components. We introduce the concept of Adaptive Microsystems and outline a path to realizing

John C. Zolper; Michael J. Biercuk

2006-01-01

493

Estimating surface flow paths on a digital elevation model using a triangular facet network  

NASA Astrophysics Data System (ADS)

This study attempts to develop a method for the simulation of surface flow paths on a digital elevation model (DEM). The objective is to use a facet-based algorithm to estimate the surface flow paths on a raster DEM. A grid DEM was used to create a triangular facet network (TFN) over which the surface flow paths were determined. Since each facet in the network has a constant slope and aspect, the estimations of, for example, flow direction and divergence/convergence are less complicated compared to traditional raster-based solutions. Experiments were undertaken by estimating the specific catchment area (SCA) over a number of mathematical surfaces, as well as on a real-world DEM. Comparisons were made between the derived SCA by the TFN algorithm with some algorithms reported in the literature. The results show that the TFN algorithm produced the closest outcomes to the theoretical values of the SCA compared with other algorithms, deriving more consistent outcomes and being less influenced by surface shapes. The real-world DEM test also shows that the TFN was capable of modeling flow distribution without noticeable "artifacts," and its ability of tracking flow paths makes it an appropriate platform for dynamic surface flow simulation.

Zhou, Qiming; Pilesjö, Petter; Chen, Yumin

2011-07-01

494

Collision-free path planning for a diamond-shaped robot using two-dimensional cellular automata  

Microsoft Academic Search

This paper presents a new parallel algorithm for collision-free path planning of a diamond-shaped robot among arbitrarily shaped obstacles, which are represented as a discrete image, and its implementation in VLSI. The proposed algorithm is based on a retraction of free space onto the Voronoi diagram, which is constructed through the time evolution of cellular automata, after an initial phase

Panagiotis G. Tzionas; Adonios Thanailakis; Philippos G. Tsalides

1997-01-01

495

A rebuilt clone elastic net algorithm for traveling salesman problem  

Microsoft Academic Search

In this paper, we analyze the relationships between solution qualities and the number of initial dynamic points in elastic net algorithm, and propose a rebuilt clone elastic network algorithm(ReBCEN) for traveling salesman problem(TSP) according to the analysis results. For solving traveling salesman problem, firstly our algorithm initializes less dynamic points to produce a general accessing path of solution which is

Gang Yang; Junyan Yi; Xiaofeng Meng

2010-01-01

496

A Linear Kernel for Co-Path/Cycle Packing  

NASA Astrophysics Data System (ADS)

Bounded-Degree Vertex Deletion is a fundamental problem in graph theory that has new applications in computational biology. In this paper, we address a special case of Bounded-Degree Vertex Deletion, the Co-Path/Cycle Packing problem, which asks to delete as few vertices as possible such that the graph of the remaining (residual) vertices is composed of disjoint paths and simple cycles. The problem falls into the well-known class of 'node-deletion problems with hereditary properties', is hence NP-complete and unlikely to admit a polynomial time approximation algorithm with approximation factor smaller than 2. In the framework of parameterized complexity, we present a kernelization algorithm that produces a kernel with at most 37k vertices, improving on the super-linear kernel of Fellows et al.'s general theorem for Bounded-Degree Vertex Deletion. Using this kernel,and the method of bounded search trees, we devise an FPT algorithm that runs in time O *(3.24 k ). On the negative side, we show that the problem is APX-hard and unlikely to have a kernel smaller than 2k by a reduction from Vertex Cover.

Chen, Zhi-Zhong; Fellows, Michael; Fu, Bin; Jiang, Haitao; Liu, Yang; Wang, Lusheng; Zhu, Binhai