Note: This page contains sample records for the topic shortest path problems 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

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

2

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

3

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

4

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

5

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

6

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

7

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

8

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

9

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

10

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

11

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

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

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

14

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

15

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

16

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

17

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

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

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

20

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

21

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

22

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

23

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

24

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

25

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

26

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

27

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

28

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

29

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

30

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

31

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

32

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

33

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

34

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

35

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

36

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

37

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

38

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

39

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

40

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

41

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

42

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

43

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

44

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

45

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

46

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

47

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

48

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

49

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

50

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

51

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

52

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

53

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

54

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

55

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

56

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

57

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

58

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

59

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

60

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

61

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

62

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

63

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

64

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

65

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

66

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

67

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

68

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

69

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

70

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

71

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

72

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

73

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

74

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

75

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

76

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

77

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

78

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

79

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

80

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

81

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

82

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

83

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

84

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

85

'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

86

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

87

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

88

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

89

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

90

Intersection Crossing Path Crashes: Problem Size Assessment and Statistical Description.  

National Technical Information Service (NTIS)

This document presents problem size assessments and statistical crash descriptions for intersection crossing path (ICP) crashes. The principal data source is the 1991 General Estimates System (GES). ICP crashes are potential target crashes of various conv...

J. S. Wang R. R. Knipling

1994-01-01

91

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

92

Path Difference Learning for Guitar Fingering Problem  

Microsoft Academic Search

In this paper we address the problem of mapping guitar music score into one of possible alternative fingering sequences on the fretboard grid. We use dynamic programming (DP) to model the decision process of a guitarist choosing the optimal fingering sequence. To estimate the DP cost functions based on examples of guitar fingering transcriptions (tablatures) we developed an original method

Aleksander Radisavljevic; Peter Driessen

93

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

94

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

95

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

96

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

97

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

98

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

99

Detecting equivalent mutants and the feasible path problem  

Microsoft Academic Search

Mutation testing is a technique for testing software units that has great potential for improving the quality of testing, and thereby increasing our ability to assure the high reliability of critical software. The paper presents a technique that uses mathematical constraints to automatically detect equivalent mutant programs. The paper also describes how the approach is used for the feasible path

A. Jefferson Offutt; Jie Pan

1996-01-01

100

A general approximation technique for constrained forest problems  

Microsoft Academic Search

We present a general approximation technique for a large class of graph problems. Our technique mostly applies to problems of covering, at minimum cost, the vertices of a graph with trees, cycles or paths satisfying certain requirements. In particular, many basic combinatorial optimization problems fit in this framework, including the shortest path, minimum spanning tree, minimum-weight perfect matching, traveling salesman

Michel X. Goemans; David P. Williamson

1992-01-01

101

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

102

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.

103

Path-following and augmented Lagrangian methods for contact problems in linear elasticity  

NASA Astrophysics Data System (ADS)

A certain regularization technique for contact problems leads to a family of problems that can be solved efficiently using infinite-dimensional semismooth Newton methods, or in this case equivalently, primal-dual active set strategies. We present two procedures that use a sequence of regularized problems to obtain the solution of the original contact problem: first-order augmented Lagrangian, and path-following methods. The first strategy is based on a multiplier-update, while path-following with respect to the regularization parameter uses theoretical results about the path-value function to increase the regularization parameter appropriately. Comprehensive numerical tests investigate the performance of the proposed strategies for both a 2D as well as a 3D contact problem.

Stadler, Georg

2007-06-01

104

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

105

Planning paths to multiple targets: memory involvement and planning heuristics in spatial problem solving  

Microsoft Academic Search

For large numbers of targets, path planning is a complex and computationally expensive task. Humans, however, usually solve\\u000a such tasks quickly and efficiently. We present experiments studying human path planning performance and the cognitive processes\\u000a and heuristics involved. Twenty-five places were arranged on a regular grid in a large room. Participants were repeatedly\\u000a asked to solve traveling salesman problems (TSP),

J. M. Wiener; N. N. Ehbauer; H. A. Mallot

2009-01-01

106

An Analysis of the Elastic Net Approach to the Traveling Salesman Problem  

Microsoft Academic Search

This paper analyzes the elastic net approach (Durbin and Willshaw 1987) to the traveling salesman problem of finding the shortest path through a set of cities. The elastic net approach jointly minimizes the length of an arbitrary path in the plane and the distance between the path points and the cities. The tradeoff between these two requirements is controlled by

Richard Durbin; Richard Szeliski; Alan Yuille

1989-01-01

107

Solving a Class of Spatial Reasoning Problems: Minimal-Cost Path Planning in the Cartesian Plane.  

National Technical Information Service (NTIS)

This work presents an algorithm to solve a two-dimensional weighted-region problem that requires finding the least-cost regions. Such regions have a constant cost rate per unit distance accrued by paths passing through them. Conventional graph search appl...

R. F. Richbourg

1987-01-01

108

Search Path Mapping: A Versatile Approach for Visualizing Problem-Solving Behavior.  

ERIC Educational Resources Information Center

|Computer-based problem-solving examinations in immunology generate graphic representations of students' search paths, allowing evaluation of how organized and focused their knowledge is, how well their organization relates to critical concepts in immunology, where major misconceptions exist, and whether proper knowledge links exist between…

Stevens, Ronald H.

1991-01-01

109

A Path Analysis of Social Problem-Solving as a Predictor of White Racial Identity  

ERIC Educational Resources Information Center

This study examined (a) whether a developmental model or a model in which all subscales' measurement errors are correlated best explains the relationships among White racial identity (WRI) statuses, and (b) social problem-solving (SPS) skills as a predictor of WRI. Path analysis was conducted with a sample of 255 White undergraduate students from…

Carr, Amanda G.; Caskie, Grace I. L.

2010-01-01

110

Two-Point Boundary Value Problems for Curves: The Case of Minimum Free Energy Paths corrected  

Microsoft Academic Search

The calculation of a minimum free energy path can be considered as a two-point boundary value problem. It is, however, nonstandard in a number of respects, which are detailed here. In particular, (i) the cost of a function evaluation depends on the location of the previous evaluation, and (ii) the value of a function will contain random noise of controllable

Robert D. Skeel

111

Search Path Mapping: A Versatile Approach for Visualizing Problem-Solving Behavior.  

ERIC Educational Resources Information Center

Computer-based problem-solving examinations in immunology generate graphic representations of students' search paths, allowing evaluation of how organized and focused their knowledge is, how well their organization relates to critical concepts in immunology, where major misconceptions exist, and whether proper knowledge links exist between content…

Stevens, Ronald H.

1991-01-01

112

Constrained Graph Optimization: Interdiction and Preservation Problems  

SciTech Connect

The maximum flow, shortest path, and maximum matching problems are a set of basic graph problems that are critical in theoretical computer science and applications. Constrained graph optimization, a variation of these basic graph problems involving modification of the underlying graph, is equally important but sometimes significantly harder. In particular, one can explore these optimization problems with additional cost constraints. In the preservation case, the optimizer has a budget to preserve vertices or edges of a graph, preventing them from being deleted. The optimizer wants to find the best set of preserved edges/vertices in which the cost constraints are satisfied and the basic graph problems are optimized. For example, in shortest path preservation, the optimizer wants to find a set of edges/vertices within which the shortest path between two predetermined points is smallest. In interdiction problems, one deletes vertices or edges from the graph with a particular cost in order to impede the basic graph problems as much as possible (for example, delete edges/vertices to maximize the shortest path between two predetermined vertices). Applications of preservation problems include optimal road maintenance, power grid maintenance, and job scheduling, while interdiction problems are related to drug trafficking prevention, network stability assessment, and counterterrorism. Computational hardness results are presented, along with heuristic methods for approximating solutions to the matching interdiction problem. Also, efficient algorithms are presented for special cases of graphs, including on planar graphs. The graphs in many of the listed applications are planar, so these algorithms have important practical implications.

Schild, Aaron V [Los Alamos National Laboratory

2012-07-30

113

Home-delivered Problem Adaptation Therapy (PATH) for Depressed, Cognitively Impaired, Disabled Elders: A Preliminary Study  

PubMed Central

Objectives This preliminary study examines the efficacy of 12-week home-delivered Problem Adaptation Therapy (PATH) vs. home-delivered Supportive Therapy (ST) in reducing depression and disability in 30 depressed, cognitively impaired, disabled older adults. Design A 12-week randomized clinical trial. Research assistants were unaware of the participants' randomization status. Assessments were conducted at baseline, 6 and 12 weeks. Setting Weill Cornell - Advanced Center for Interventions and Services Research (ACISR). Participants Thirty elders with major depression, cognitive impairment, and disability were recruited through advertisement and the Home-Delivered Meals Program of the Westchester County Department of Senior Programs and Services. Intervention PATH is a home-delivered intervention designed to reduce depression and disability in depressed, cognitively impaired, disabled elders. PATH is based on Problem Solving Therapy (PST) and integrates environmental adaptation and caregiver participation. PATH is consistent with Lawton's ecological model of adaptive functioning in aging. Measurements Depression and disability were measured with Hamilton Depression Rating Scale – 24 items and Sheehan Disability Scale, respectively. Client Satisfaction Questionnaire was used to assess patient satisfaction with treatment. Results Mixed-effects model analyses revealed that PATH was more efficacious than ST in reducing depression and disability at 12 weeks. Participants in both treatment groups were satisfied with treatment. Conclusions This preliminary study suggests that PATH is well accepted and efficacious in depressed elders with major depression, cognitive impairment, and disability. Because this population may not adequately respond to antidepressant medication treatment, PATH may provide relief to many patients who would otherwise remain depressed and suffer.

Kiosses, Dimitris N.; Arean, Patricia A.; Teri, Linda; Alexopoulos, George S.

2010-01-01

114

A Parametric Critical Path Problem and an Application for Cyclic Scheduling  

Microsoft Academic Search

The paper addresses a problem of finding critical paths in PERT networks (digraphs) with variable arc lengths depending on a parameter. By equipping the Bellman-Ford label-correcting algorithm with variable vectorial labels depending on the parameter, we derive its version that solves the problem in O(mn2) time, for all possible parameter values (where m stands for the number of arcs, and

Eugene Levner; Vladimir Kats

1998-01-01

115

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

116

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

117

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

118

A General Approximation Technique for Constrained Forest Problems  

Microsoft Academic Search

Abstract.,We present,a general approximation technique for a large class of graph problems.,Our technique mostly applies to problems of covering, at minimum cost, the vertices ofa graph with trees, cycles, or paths satisfying certain requirements. In particular, many basic combinatorial optimization problems fit in this framework, including the shortest path, minimum-cost spanning tree, minimum-weight perfect matching, traveling salesman, and Steiner tree,problems.

Michel X. Goemans; David P. Williamson

1995-01-01

119

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

120

Transfer matrix approach to the structural block diagonal decoupling problem  

Microsoft Academic Search

The block diagonal decoupling problem for structured systems is treated using the transfer matrix approach. An associated graph, which displays the internal structure of the system (invariant and interconnection), is used to establish necessary and sufficient conditions for the solution of the problem. These conditions are expressed in the graph in terms of shortest input-output paths, which are related to

A. BELMEHDI

1994-01-01

121

Solving Capacitated Vehicle Routing Problem Using DNA-based Computation  

Microsoft Academic Search

The vehicle routing problem is one of the most challenging optimization tasks involved in searching optimal route sets in operational research. The objective of solving capacitated vehicle routing problem (CVRP) is to identify a set of shortest paths for a fleet of individual vehicles with fixed capacity from a central depot that serve all customer demand. This study describes a

Chung-Wei Yeh

2009-01-01

122

Unified approach to fuzzy graph problems  

Microsoft Academic Search

We present a taxonomy of fuzzy graphs that treats fuzziness in vertex existence, edge existence, edge connectivity, and edge weight. Within that framework, we formulate some standard graph-theoretic problems (shortest paths and minimum cut) for fuzzy graphs using a uni\\

M. Blue; B. Bush; J. Puckett

2002-01-01

123

Solution to the variation problem for information path functional of a controlled random process  

NASA Astrophysics Data System (ADS)

The paper introduces a new approach to dynamic modeling, using the variation principle, applied to a functional on trajectories of a controlled random process, and its connection to the process' information functional. In [V.S. Lerner, Dynamic approximation of a random information functional, J. Math. Anal. Appl. 327 (1) (2007) 494-514, available online 5-24-06], we presented the information path functional with the Lagrangian, determined by the parameters of a controlled stochastic equation. In this paper, the solution to the path functional's variation problem provides both a dynamic model of a random process and the model's optimal control, which allows us to build a two-level information model with a random process at the microlevel and a dynamic process at the macrolevel. A wide class of random objects, modeled by the Markov diffusion process and a common structure of the process' information functional, leads to a universal information structure of the dynamic model, which is specified and identified on a particular object with the applied optimal control functions. The developed mathematical formalism, based on classical methods, is aimed toward the solution of problems identification, combined with an optimal control synthesis, which is practically implemented and also demonstrated in the paper's example.

Lerner, Vladimir S.

2007-10-01

124

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

125

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

126

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

127

Role of Self-Efficacy and Self-Concept Beliefs in Mathematical Problem Solving: A Path Analysis  

Microsoft Academic Search

Path analysis was used to test the predictive and mediational role of self-efficacy beliefs in mathematical problem solving. Results revealed that math self-efficacy was more predictive of problem solving than was math self-concept, perceived usefulness of mathematics, prior experience with mathematics, or gender (N = 350). Self-efficacy also mediated the effect of gender and prior experience on self-concept, perceived usefulness,

Frank Pajares; M. David Miller

1994-01-01

128

Role of self-efficacy and self-concept beliefs in mathematical problem solving: A path analysis  

Microsoft Academic Search

Path analysis was used to test the predictive and mediational role of self-efficacy beliefs in mathematical problem solving. Results revealed that math self-efficacy was more predictive of problem solving than was math self-concept, perceived usefulness of mathematics, prior experi- ence with mathematics, or gender (N = 350). Self-efficacy also mediated the effect of gender and prior experience on self-concept, perceived

Frank Pajares; M. David Miller

1994-01-01

129

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

130

Optimal Synthesis of the Asymmetric Sinistral\\/Dextral Markov–Dubins Problem  

Microsoft Academic Search

We consider a variation of the classical Markov–Dubins problem dealing with curvature-constrained, shortest paths in the plane\\u000a with prescribed initial and terminal positions and tangents, when the lower and upper bounds of the curvature of the path\\u000a are not necessarily equal. The motivation for this problem stems from vehicle navigation applications, when a vehicle may\\u000a be biased in taking turns

Efstathios Bakolas; Panagiotis Tsiotras

2011-01-01

131

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

132

REAL-TIME CONTROL OF AN AUTONOMOUS VEHICLE : A NEURAL NETWORK APPROACH TO THE PATH FOLLOWING PROBLEM  

Microsoft Academic Search

A neural-network based approach to the control of non-linear dynamical systems such as wheeled mobile robots is presented. A general framework for the training of neural controllers is outlined, and applied to the lateral control of a vehicle for the path following and trajectory servoing problems. Simulation as well as experimental results on a four-wheel drive vehicle equipped with actuators

Isabelle Rivals; Léon Personnaz; Gérard Dreyfus; Daniel Canas

1993-01-01

133

Hooke's Atom in an Arbitrary External Electric Field: Analytical Solutions of Two-Electron Problem by Path Integral Approach  

NASA Astrophysics Data System (ADS)

By using the path integral approach, we investigate the problem of Hooke's atom (two electrons interacting with Coulomb potential in an external harmonic-oscillator potential) in an arbitrary time-dependent electric field. For a certain infinite set of discrete oscillator frequencies, we obtain the analytical solutions. The ground state polarization of the atom is then calculated. The same result is also obtained through linear response theory.

Cai, Liang; Zhang, Ping; Yang, Tao; Pan, Xiao-Yin

2011-04-01

134

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

135

Lagrangian duality applied to the vehicle routing problem with time windows  

Microsoft Academic Search

This paper considers the vehicle routing problem with time windows, where the service of each customer must start within a specified time interval. We consider the Lagrangian relaxation of the constraint set requiring that each customer must be served by exactly one vehicle yielding a constrained shortest path subproblem. We present a stabilized cutting-plane algorithm within the framework of linear

Brian Kallehauge; Jesper Larsen; Oli B. G. Madsen

2006-01-01

136

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

137

On Traveling Salesperson Problems for Dubins’ vehicle: stochastic and dynamic environments  

Microsoft Academic Search

In this paper we propose some novel planning and routing strategies for Dubins’ vehicle, i.e., for a nonholonomic vehicle moving along paths with bounded curvature, without reversing direction. First, we study a stochastic version of the Traveling Salesperson Problem (TSP): given n targets randomly sampled from a uniform distribution in a rectangle, what is the shortest Dubins'tour through the targets

Ketan Savla; Francesco Bullo; Emilio Frazzoli

2005-01-01

138

A Comparison of Heuristic and Human Performance on Open Versions of the Traveling Salesperson Problem  

Microsoft Academic Search

We compared the performance of three heuristics with that of subjects on variants of a well-known combinatorial optimization task, the Traveling Salesperson Problem (TSP). The present task consisted of finding the shortest path through an array of points from one side of the array to the other. Like the standard TSP, the task is computationally intractable and, as with the

James N. MacGregor; Edward P. Chronicle; Thomas C. Ormerod

2006-01-01

139

Flight simulation investigations for the problem of flyability of noise optimal approach and takeoff paths  

NASA Astrophysics Data System (ADS)

Noise reduction during takeoff and landing of the A 300 B Airbus was studied using flight simulation. Operational aspects such as flyability and safety were emphasized. The investigations were limited to aircraft control in the vertical path plane, since the extension to the horizontal path control can only be made for a real airport and its surroundings. Noise emission parameters included noise frequency, direction and thrust dependence of propulsion system noise emission, aircraft spatial position, air damping as a function of noise frequency, air temperature and relative humidity as a function of flight height, and soil damping. The results show that reductions of the noise in the neighborhood of airports are possible, compared to the usual takeoff and landing methods (IATA steep takeoff method, low drag low power approach method).

Friedel, R.

1983-10-01

140

Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem  

Microsoft Academic Search

Searching for a goal is a central and extensively studied problem in computer science. Inclassical searching problems, the cost of a search function is simply the number of queries madeto an oracle that knows the position of the goal. In many robotics problems, as well as inproblems from other areas, we want to charge a cost proportional to the distance

Ming-Yang Kao; John H. Reif; Stephen R. Tate

1993-01-01

141

On the dynamic Markov-Dubins problem: From path planning in robotics and biolocomotion to computational anatomy  

NASA Astrophysics Data System (ADS)

Andrei Andreyevich Markov proposed in 1889 the problem (solved by Dubins in 1957) of finding the twice continuously differentiable (arc length parameterized) curve with bounded curvature, of minimum length, connecting two unit vectors at two arbitrary points in the plane. In this note we consider the following variant, which we call the dynamic Markov-Dubins problem (dM-D): to find the time-optimal C 2 trajectory connecting two velocity vectors having possibly different norms. The control is given by a force whose norm is bounded. The acceleration may have a tangential component, and corners are allowed, provided the velocity vanishes there. We show that for almost all the two vectors boundary value conditions, the optimization problem has a smooth solution. We suggest some research directions for the dM-D problem on Riemannian manifolds, in particular we would like to know what happens if the underlying geodesic problem is completely integrable. Path planning in robotics and aviation should be the usual applications, and we suggest a pursuit problem in biolocomotion. Finally, we suggest a somewhat unexpected application to "dynamic imaging science". Short time processes (in medicine and biology, in environment sciences, geophysics, even social sciences?) can be thought as tangent vectors. The time needed to connect two processes via a dynamic Markov-Dubins problem provides a notion of distance. Statistical methods could then be employed for classification purposes using a training set.

Castro, Alex Lúcio; Koiller, Jair

2013-01-01

142

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

143

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

144

Magnetic field fluctuation geometry as a possible solution to the proton mean free path discrepancy problem  

NASA Astrophysics Data System (ADS)

Phenomenological values of the mean free path of solar energetic protons in the solar wind are compared to the values derived from measurements of the interplanetary magnetic fields by a standard quasilinear theory (QLT) for a slab geometry of the fields. For strongly scattering events the quality of QLT decreases systematically if the angle between the directions of the mean magnetic field and the solar wind velocity increases. We show that this surprising result can be interpreted as evidence for magnetic fluctuations with oblique wave number vectors, i.e. for field geometries differing from the slab model. We compare results from the standard slab model with those from three models with more complicated fluctuation geometries. Best results are obtained for a model with a 2D component of the fluctuations and for one with radially oriented wave vectors.

Jaekel, U.; Wanner, W.; Schlickeiser, R.; Wibberenz, G.

1994-11-01

145

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

146

Paths to literacy and numeracy problems: evidence from two British birth cohorts  

Microsoft Academic Search

Background:To test a life course model linking circumstances of origin to self-reported literacy and numeracy problems in midlife, and to investigate the effects in this model of changing social circumstances in two post-war cohorts.Methods:Based on data from men and women in the British 1946 and 1958 birth cohorts, we used the relative index of inequality and logistical regression to test

M Richards; C Power; A Sacker

2009-01-01

147

Single Vehicle Scheduling Problems on Path\\/Tree\\/Cycle Networks with Release and Handling Times  

Microsoft Academic Search

In this paper, we consider the single vehicle scheduling problem (SVSP) on networks. Each job, located at some node, has a\\u000a release time and a handling time. The vehicle starts from a node (depot), processes all the jobs, and then returns back to\\u000a the depot. The processing of a job cannot be started before its release time, and its handling

Binay K. Bhattacharya; Paz Carmi; Yuzhuang Hu; Qiaosheng Shi

2008-01-01

148

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

149

The Role of Youth Problem Behaviors in the Path From Child Abuse and Neglect to Prostitution: A Prospective Examination  

PubMed Central

Behaviors beginning in childhood or adolescence may mediate the relationship between childhood maltreatment and involvement in prostitution. This paper examines five potential mediators: early sexual initiation, running away, juvenile crime, school problems, and early drug use. Using a prospective cohort design, abused and neglected children (ages 0–11) with cases processed during 1967–1971 were matched with non-abused, non-neglected children and followed into young adulthood. Data are from in-person interviews at approximate age 29 and arrest records through 1994. Structural Equation Modeling tested path models. Results indicated that victims of child abuse and neglect were at increased risk for all problem behaviors, except drug use. In the full model, only early sexual initiation remained significant as a mediator in the pathway from child abuse and neglect to prostitution. Findings were generally consistent for physical and sexual abuse and neglect. These findings suggest that interventions to reduce problem behaviors among maltreated children may also reduce their risk for prostitution later in life.

Wilson, Helen W.; Widom, Cathy Spatz

2009-01-01

150

Level set and Fat Fast Marching Method for normal and dynamic path planning of pursuit-evasion problem  

Microsoft Academic Search

This paper proposes a modified version of the Fast Marching Method (FMM), called Fat Fast Marching Method (FFMM), which produces a much more accurate path than the path generated by the original FMM with the approximated ODE solution. Given a complicated environment which has a long optimal path and a very large maximum cost value that results in high gradients,

Cheng-Yuan Wu; Jing-Sin Liu

2010-01-01

151

From parent to child to parent…: paths in and out of problem behavior.  

PubMed

This study used data from the NICHD Study of Early Child Care and Youth Development to examine relations between parenting, self-control and externalizing behavior from early childhood to mid-adolescence (N?=?956; 49.9 % male). Results indicated that maternal sensitivity, parental harshness and productive activity are related to externalizing problems but that patterns of relations change from early childhood to middle childhood to adolescence, with evidence suggesting that externalizing behavior influences parenting more than the reverse from middle childhood onward. Self-control measured during early adolescence partially mediated relations between maternal sensitivity and adolescent-reported externalizing behavior. Parental monitoring during adolescence was also related to externalizing behavior at age 15. Monitoring partially mediated the relation between externalizing behavior in early adolescence and externalizing at age 15. PMID:23135289

Bradley, Robert H; Corwyn, Robert

2013-05-01

152

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

153

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

154

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

155

A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints  

Microsoft Academic Search

In this paper, we present a new class of polynomial length formulations for the asymmetric traveling salesman problem (ATSP) by lifting an ordered path-based model using logical restrictions in concert with the Reformulation–Linearization Technique (RLT). We show that a relaxed version of this formulation is equivalent to a flow-based ATSP model, which in turn is tighter than the formulation based

Hanif D. Sherali; Subhash C. Sarin; Pei-fang Tsai

2006-01-01

156

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

157

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

158

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

159

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

160

Fast marching methods for the continuous traveling salesman problem.  

PubMed

We consider a problem in which we are given a domain, a cost function which depends on position at each point in the domain, and a subset of points ("cities") in the domain. The goal is to determine the cheapest closed path that visits each city in the domain once. This can be thought of as a version of the traveling salesman problem, in which an underlying known metric determines the cost of moving through each point of the domain, but in which the actual shortest path between cities is unknown at the outset. We describe algorithms for both a heuristic and an optimal solution to this problem. The complexity of the heuristic algorithm is at worst case M.N log N, where M is the number of cities, and N the size of the computational mesh used to approximate the solutions to the shortest paths problems. The average runtime of the heuristic algorithm is linear in the number of cities and O(N log N) in the size N of the mesh. PMID:17220271

Andrews, June; Sethian, J A

2007-01-12

161

Fast marching methods for the continuous traveling salesman problem  

SciTech Connect

We consider a problem in which we are given a domain, a cost function which depends on position at each point in the domain, and a subset of points ('cities') in the domain. The goal is to determine the cheapest closed path that visits each city in the domain once. This can be thought of as a version of the Traveling Salesman Problem, in which an underlying known metric determines the cost of moving through each point of the domain, but in which the actual shortest path between cities is unknown at the outset. We describe algorithms for both a heuristic and an optimal solution to this problem. The order of the heuristic algorithm is at worst case M * N logN, where M is the number of cities, and N the size of the computational mesh used to approximate the solutions to the shortest paths problems. The average runtime of the heuristic algorithm is linear in the number of cities and O(N log N) in the size N of the mesh.

Andrews, J.; Sethian, J.A.

2008-12-01

162

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

163

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

164

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

165

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

166

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

167

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

168

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

169

A wavepacket — path integral method for curve-crossing problems: application to resonance Raman spectra and photodissociation cross sections  

NASA Astrophysics Data System (ADS)

A multidimensional Gaussian wavepacket dynamics — path integral method (GWD-PI) is utilized to study time evolution on two nonadiabatically coupled anharmonic potential energy surfaces. The proposed technique relies on single surface propagations in which the nuclear coordinate wavepacket hops from one potential surface to the other at selected times. Appropriate sequences of hopping times are considered and the output wavepackets associated with each sequence are summed coherently. Good agreement is obtained between GWD-PI and exact quantum dynamics for a two-dimensional model of photodissociation, even in the case of strong and spatially dependent nonadiabatic coupling.

Cárdenas, A. E.; Coalson, R. D.

1997-01-01

170

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

171

Steiner's Problem in Graphs and Its Implications.  

National Technical Information Service (NTIS)

A graph theoretic version of Steiner's problem in plane geometry is described. An approach for solving the problem, related to Melzak's solution to Steiner's problem, is presented. The problems of finding shortest route and minimal spanning tree in graphs...

S. L. Hakimi

1970-01-01

172

The Role of Youth Problem Behaviors in the Path from Child Abuse and Neglect to Prostitution: A Prospective Examination  

ERIC Educational Resources Information Center

|Behaviors beginning in childhood or adolescence may mediate the relationship between childhood maltreatment and involvement in prostitution. This paper examines 5 potential mediators: early sexual initiation, running away, juvenile crime, school problems, and early drug use. Using a prospective cohort design, abused and neglected children (ages…

Wilson, Helen W.; Widom, Cathy Spatz

2010-01-01

173

The Role of Youth Problem Behaviors in the Path from Child Abuse and Neglect to Prostitution: A Prospective Examination  

ERIC Educational Resources Information Center

Behaviors beginning in childhood or adolescence may mediate the relationship between childhood maltreatment and involvement in prostitution. This paper examines 5 potential mediators: early sexual initiation, running away, juvenile crime, school problems, and early drug use. Using a prospective cohort design, abused and neglected children (ages…

Wilson, Helen W.; Widom, Cathy Spatz

2010-01-01

174

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

175

Open path measurements of carbon dioxide and water vapor under foggy conditions - technical problems, approaches and effects on flux measurements and budget calculations  

NASA Astrophysics Data System (ADS)

To estimate carbon dioxide or water vapor fluxes with the Eddy Covariance method high quality data sets are necessary. Under foggy conditions this is challenging, because open path measurements are influenced by the water droplets that cross the measurement path as well as deposit on the windows of the optical path. For the LI-7500 the deposition of droplets on the window results in an intensity reduction of the infrared beam. To keep the strength of the infrared beam under these conditions, the energy is increased. A measure for the increased energy is given by the AGC value (Automatic Gain Control). Up to a AGC threshold value of 70 % the data from the LI-7500 is assumed to be of good quality (personal communication with LICOR). Due to fog deposition on the windows, the AGC value rises above 70 % and stays there until the fog disappears and the water on the windows evaporates. To gain better data quality during foggy conditions, a blower system was developed that blows the deposited water droplets off the window. The system is triggered if the AGC value rises above 70 %. Then a pneumatic jack will lift the blower system towards the LI-7500 and the water-droplets get blown off with compressed air. After the AGC value drops below 70 %, the pneumatic jack will move back to the idle position. Using this technique showed that not only the fog droplets on the window causing significant problems to the measurement, but also the fog droplets inside the measurement path. Under conditions of very dense fog the measured values of carbon dioxide can get unrealistically high, and for water vapor, negative values can be observed even if the AGC value is below 70 %. The negative values can be explained by the scatter of the infrared beam on the fog droplets. It is assumed, that different types of fog droplet spectra are causing the various error patterns observed. For high quality flux measurements, not only the AGC threshold value of 70 % is important, but also the fluctuation of the AGC value in a flux averaging interval. Such AGC value fluctuations can cause severe jumps in the concentration measurements that can hardly be corrected for. Results of fog effects on the LI-7500 performance and its consequences for flux measurements and budget calculations will be presented.

El-Madany, T.; Griessbaum, F.; Maneke, F.; Chu, H.-S.; Wu, C.-C.; Chang, S. C.; Hsia, Y.-J.; Juang, J.-Y.; Klemm, O.

2010-07-01

176

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.

177

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

178

The Discrete Geodesic Problem  

Microsoft Academic Search

We present an algorithm for determining the shortest path between a source and a destination on an arbitrary (possibly nonconvex) polyhedral surface. The path is constrained to lie on the surface, and distances are measured according to the Euclidean metric. Our algorithm runs in time O(n log n) and requires O(n2) space, where n is the number ofedges ofthe surface.

Joseph S. B. Mitchell; David M. Mount; Christos H. Papadimitriou

1987-01-01

179

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

180

OSL—optimal single-loop guide paths for AGVS  

Microsoft Academic Search

This study deals with the Automated Guided Vehicle System guide path design problem. We suggest a single closed loop guide path layout configuration as an alternative to conventional but more complex guide path designs. The benefits of using a simple guide path versus more complicated guide paths are discussed. A procedure for designing an optimal single loop guide path for

J. M. A. TANCHOCOf; DAVID SINRIECH

1992-01-01

181

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

182

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

183

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

184

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

185

Randomized path coloring on binary trees  

Microsoft Academic Search

Motivated by the problem of WDM routing in all-optical networks, we study the following NP-hard problem. We are given a directed binary tree T and a set R of directed paths on T. We wish to assign colors to paths of R, in such way that no two paths that share a directed arc of T are assigned the same

Vincenzo Auletta; Ioannis Caragiannis; Christos Kaklamanis; Pino Persiano

2002-01-01

186

Media Streaming With Network Diversity Research indicates opportunities for improving media quality, in networks like the Internet with multiple paths, but also poses new coding, scheduling, routing, and path-computation problems  

Microsoft Academic Search

Today's packet networks including the Internet offer an intrinsic diversity for media distribution in terms of available network paths and servers or information sources. Novel communication infrastructures such as ad hoc or wireless mesh networks use network diversity to extend their reach at low cost. Diversity can bring interesting benefits in supporting resource greedy applications such as media streaming services,

Pascal Frossard; Juan Carlos de Martin; M. Reha Civanlar

187

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

188

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

189

Combinatorial expressions of the solutions to initial value problems of the discrete and ultradiscrete Toda molecules  

NASA Astrophysics Data System (ADS)

Combinatorial expressions are presented of the solutions to initial value problems of the discrete and ultradiscrete Toda molecules. For the discrete Toda molecule, a subtraction-free expression of the solution is derived in terms of non-intersecting paths, for which two results in combinatorics, Flajolet’s interpretation of continued fractions and Gessel–Viennot’s lemma on determinants, are applied. By ultradiscretizing the subtraction-free expression, the solution to the ultradiscrete Toda molecule is obtained. It is finally shown that the initial value problem of the ultradiscrete Toda molecule is exactly solved in terms of shortest paths on a specific graph. The behavior of the solution is also investigated in comparison with the box–ball system.

Kamioka, Shuhei; Takagaki, Tomoaki

2013-09-01

190

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

191

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

192

Lateral Path Controller Design for Autonomous Airship  

Microsoft Academic Search

According to the path control problem for unmanned autonomous airship, the lateral path mathematic model was introduced based on the scheme of control system and a kind of lateral path design method of autonomous airship is proposed based on fuzzy logic and adaptive sliding mode control (ASMC). The movement model and dynamic model of autonomous airship is derived from considering

Guo Jian-guo; Zhou Jun

2010-01-01

193

The Travelling Salesman Problem  

NSDL National Science Digital Library

The Traveling Salesman Problem is one of the most intensively studied problems in computational mathematics. These pages are devoted to the history, applications, and current research of this challenge of finding the shortest route visiting each member of a collection of locations and returning to your starting point.

Cook, William

194

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

195

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

196

Randomized path coloring on binary trees  

Microsoft Academic Search

Motivated by the problem of WDM routing in all-optical networks, we study the following NP-hard problem. We are given a di- rected binary tree T and a set R of directed paths on T.W e wish to assign colors to paths in R, in such a way that no two paths that share ad irected arc ofT are assigned the

Vincenzo Auletta; Ioannis Caragiannis; Christos Kaklamanis; Pino Persiano

2000-01-01

197

Complete coverage path planning in an agricultural environment  

Microsoft Academic Search

The problem of finding a collision-free path through a region has garnered a lot of research over the years. One branch of this is the problem of finding a path that completely covers a region. Solutions to the complete coverage path planning problem have applications in many different areas, such as search and rescue, automotive painting, and agriculture. In many

Theresa Marie Driscoll

2011-01-01

198

Time optimal paths for high speed maneuvering  

SciTech Connect

Recent theoretical results have completely solved the problem of determining the minimum length path for a vehicle with a minimum turning radius moving from an initial configuration to a final configuration. Time optimal paths for a constant speed vehicle are a subset of the minimum length paths. This paper uses the Pontryagin maximum principle to find time optimal paths for a constant speed vehicle. The time optimal paths consist of sequences of axes of circles and straight lines. The maximum principle introduces concepts (dual variables, bang-bang solutions, singular solutions, and transversality conditions) that provide important insight into the nature of the time optimal paths. We explore the properties of the optimal paths and present some experimental results for a mobile robot following an optimal path.

Reister, D.B.; Lenhart, S.M.

1993-01-01

199

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

200

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

201

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

202

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

203

Path instability of a rising bubble.  

PubMed

We model the problem of path instability of a rising bubble by considering the bubble as a spheroidal body of fixed shape, and we solve numerically the coupled fluid-body problem. Numerical results show that this model exhibits path instability for large enough values of the control parameters. The corresponding characteristics of the zigzag and spiral paths are in good agreement with experimental observations. Analysis of the vorticity field behind the bubble reveals that a wake instability leading to a double threaded wake is the primary cause of the path instability. PMID:11800955

Mougin, Guillaume; Magnaudet, Jacques

2001-12-19

204

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

205

Rotorcraft path following control for extended flight envelope coverage  

Microsoft Academic Search

This paper addresses the problem of steering a quadrotor vehicle along a predefined path. The problem is formulated so as to dynamically prescribe an adequate time evolution along the path and simultaneously bound the effect of position errors on the actuation. The proposed solution consists of a nonlinear state feedback controller for thrust and torque actuations combined with a path

David Cabecinhas; Rita Cunha; Carlos Silvestre

2009-01-01

206

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

207

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

208

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

209

Paths in m-ary interval trees  

Microsoft Academic Search

We introduce the m-ary interval tree, a random structure that underlies interval division and simultaneous parking problems. Certain significant paths in the m-ary interval trees are considered. When appropriately normed, the length of these paths are shown to converge in distribution to a normal random variable. The work extends the study of incomplete binary interval trees in Itoh and Mahmoud

Mehri Javanian; Hosam M. Mahmoud; Mohammad Vahidi-asl

2004-01-01

210

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

211

Quantifying Kinetic Paths of Protein Folding  

PubMed Central

We propose a new approach to activated protein folding dynamics via a diffusive path integral framework. The important issues of kinetic paths in this situation can be directly addressed. This leads to the identification of the kinetic paths of the activated folding process, and provides a direct tool and language for the theoretical and experimental community to understand the problem better. The kinetic paths giving the dominant contributions to the long-time folding activation dynamics can be quantitatively determined. These are shown to be the instanton paths. The contributions of these instanton paths to the kinetics lead to the “bell-like” shape folding rate dependence on temperature, which is in good agreement with folding kinetic experiments and simulations. The connections to other approaches as well as the experiments of the protein folding kinetics are discussed.

Wang, Jin; Zhang, Kun; Lu, Hongyang; Wang, Erkang

2005-01-01

212

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

213

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

214

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

215

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

216

A Note on the Assortment Problem  

Microsoft Academic Search

Wieslaw Sadowski [Sadowski, W. 1959. A few remarks on the assortment problem. Management Sci. 6 (1, October).] has proposed a dynamic programming approach to the solution of the assortment problem by showing its equivalence to the shortest route problem and using Bellman's algorithm [Bellman, R. 1957. Dynamic Programming. Princeton, University Press, New Jersey.]. In this paper we offer an alternative

Charles R. Frank Jr.

1965-01-01

217

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

218

Planning High-quality Paths and Corridors Amidst Obstacles  

Microsoft Academic Search

The motion-planning problem, involving the computation of a collision-free path for a moving entity amidst obstacles, is a central problem in fields like Robotics and Game Design. In this paper we study the problem of planning high-quality paths. A high-quality path should have some desirable properties: it should be short and avoid long detours, and at the same time it

Ron Wein; Jur P. Van Den Berg; Dan Halperin

2008-01-01

219

Coordinated Path-Following Control for a Group of Underactuated Surface Vessels  

Microsoft Academic Search

This paper addresses the problem of coordinating a group of underactuated ships along given paths (path following) while holding a desired intership formation pattern. The solution to this problem unfolds into two basic subproblems. In the first step, a path-following controller is derived to force each underactuated ship to follow a reference path subject to constant disturbances induced by wave,

Jawhar Ghommam; FaÏÇal Mnif

2009-01-01

220

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

221

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

222

A new approach to CNC tool path generation  

Microsoft Academic Search

The feedrate is one of the most important factors to machining efficiency and quality. Current methods for tool path generation adopt a constant velocity along the cutter location path and do not satisfy the desired feedrate along the sculptured surface. This paper presents a new approach to tool path generation so as to cope with this problem. Methods based on

Chih-ching Lo

1998-01-01

223

Empirical Sampling of Path Sets for Local Area Motion Planning  

Microsoft Academic Search

Summary. We consider the problem of online planning for a mobile robot among obstacles, where it is impractical to test all possible future paths. One approach is for the runtime task to test some subset of the possible paths and select a path that does not collide with obstacles while advancing the robot toward its goal. Performance depends on the

Ross A. Knepper; Matthew T. Mason

2008-01-01

224

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

225

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

226

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

227

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

228

Curvature-constrained directional-cost paths in the plane  

Microsoft Academic Search

This paper looks at the problem of finding the minimum cost curvature-constrained path between two directed points where the\\u000a cost at every point along the path depends on the instantaneous direction. This generalises the results obtained by Dubins\\u000a for curvature-constrained paths of minimum length, commonly referred to as Dubins paths. We conclude that if the reciprocal\\u000a of the directional-cost function

Alan J. Chang; Marcus Brazil; J. Hyam Rubinstein; Doreen A. Thomas

2012-01-01

229

Breakdown of the Coherent State Path Integral: Two Simple Examples  

SciTech Connect

We show how the time-continuous coherent state path integral breaks down for both the single-site Bose-Hubbard model and the spin-path integral. Specifically, when the Hamiltonian is quadratic in a generator of the algebra used to construct coherent states, the path integral fails to produce correct results following from an operator approach. As suggested by previous authors, we note that the problems do not arise in the time-discretized version of the path integral.

Wilson, Justin H.; Galitski, Victor [Joint Quantum Institute and Condensed Matter Theory Center, Department of Physics, University of Maryland, College Park, Maryland 20742-4111 (United States)

2011-03-18

230

On Yen's Path Logic for Petri Nets  

NASA Astrophysics Data System (ADS)

In [13], Yen defines a class of formulas for paths in Petri nets and claims that its satisfiability problem is expspace-complete. In this paper, we show that in fact the satisfiability problem for this class of formulas is as hard as the reachability problem for Petri nets. Moreover, we salvage almost all of Yen’s results by defining a fragment of this class of formulas for which the satisfiability problem is expspace-complete by adapting his proof.

Atig, Mohamed Faouzi; Habermehl, Peter

231

Flight Path Control Equipment for Producing Curved Flight Path Profiles with Microwave Landing Systems.  

National Technical Information Service (NTIS)

The characteristics of a flight path control instrument for producing curved approach profiles and guidance along these profiles are presented. For safety reasons, steep noise abatement approaches must be flown along curved profiles. The problems of flyab...

G. Schaenzer

1974-01-01

232

Problem Stabilization  

PubMed Central

Background Public health nurse (PHN) home visiting programs have been widely employed to improve life course trajectories for high risk mothers. Home visiting programs are often lengthy, during which PHNs simultaneously address multiple problems using diverse interventions over several client encounters. To manage PHN caseloads it is critical to understand the trajectory of client improvement and the optimal duration or services. PHN documentation data enable intervention trajectory research for specific client problems. A new metric called problem stabilization is proposed for evaluating interim improvement during PHN home visiting. Problem stabilization is an intervention pattern for a client problem that is characterized by co-occurring actions (i.e. teaching, guidance, and counseling; treatments and procedures; case management; and/or surveillance) during a client encounter; followed by surveillance actions only for that problem during a subsequent client encounter. The purpose of the study was to investigate problem stabilization during home visiting services for high risk mothers. Methods A retrospective cohort was created using family home visiting intervention documentation data from a local Midwest public health agency over a six year period (2000–2005). The data set consisted of Omaha System interventions for 720 high risk mothers. Analysis was conducted using descriptive statistics and Kaplan Meier curves. Results On average 30.1% of the time, client problems stabilized before discharge. Stabilization patterns differed by problem. Time to stabilization was longest for Caretaking/parenting and Antepartum/postpartum problems, and shortest for Residence and Mental health problems. Conclusions Problem stabilization, a proposed intermediate outcome of PHN home visiting care, appears to be meaningful in describing client response to PHN intervention. This metric is an example of meaningful use of structured clinical electronic health record data for program evaluation and clinical decision support.

Monsen, K.A.; Farri, O.; McNaughton, D.B.; Savik, Kay

2011-01-01

233

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

234

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

235

Robust real-time NURBS path interpolators  

Microsoft Academic Search

In a review of the real-time non-uniform rational B-splines (NURBS) path interpolation method in CNC controllers, it was found that none of the NURBS interpolators described in the literature has the necessary robustness against an extreme knot distribution. The problems begin with the calculation of the total length of the NURBS path: most interpolators handle knots as a global curve

W. T. Lei; S. B. Wang

2009-01-01

236

On the Limits of Nonapproximability of Lattice Problems  

Microsoft Academic Search

We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of n, of optimization problems in integer lattices, specifically, the closest vector problem (CVP) and the shortest vector problem (SVP). These interactive proofs are for the coNP direction; that is, we give an interactive protocol showing that a vector is far from the lattice

Oded Goldreich; Shafi Goldwasser

2000-01-01

237

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

238

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

239

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.

240

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

241

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

242

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

243

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

244

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

245

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

246

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

247

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

248

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.

249

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

250

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.

251

Robot path planning and control in a cluttered workplace  

Microsoft Academic Search

A multi-level planning strategy is used, which computes, from the geometry of workspace, a `road map' involving a set of suggested paths in the form of a searchable network. Then the path planning problem is reduced to selecting a path from the road map which will ensure collision-free tracking. Guidance of robotic manipulators along the collision-free trajectory requires close tracking

A. Denker; O. Kaynak

1993-01-01

252

Pricing of American Path-Dependent Contingent Claims  

Microsoft Academic Search

We consider the problem of pricing path-dependent contingent claims. Classically, this problemcan be cast into the Black-Scholes valuation framework through inclusion of the path-dependentvariables into the state space. This leads to solving a degenerate advection-diffusion PartialDifferential Equation (PDE). Standard Finite Difference (FD) methods are known to be inadequatefor solving such degenerate PDE. Hence, path-dependent European claims are typicallypriced through Monte-Carlo...

J Er Ome Barraquand; Jer Ome Barraquand; Thierry Pudet

1994-01-01

253

On-line time-optimal path tracking for robots  

Microsoft Academic Search

This paper focuses on time-optimal path tracking, which involves planning of robot motions along prescribed geo- metric paths. Starting from a discretized convex reformulation of time-optimal path tracking problems, a log-barrier based batch solution method is presented which allows to rapidly obtain an approximate solution with smooth actuator torques. Based on this batch method, a recursive variant is derived for

Diederik Verscheure; Moritz Diehl; Joris De Schutter; Jan Swevers

2009-01-01

254

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

255

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

256

Parallel Path Planning with Multiple Evasion Strategies  

Microsoft Academic Search

Probabilistic path planning driven by a potential eld is a well established technique and has been successfully ex- ploited to solve complex problems arising in a variety of domains. However, planners implementing this approach are rather inecient in dealing with certain types of lo- cal minima occurring in the potential eld, especially those characterized by deep or large attraction basins.

Stefano Caselli; Monica Reggiani; Roberto Sbravati

2002-01-01

257

Scanning path optimization for ultrasound surgery  

Microsoft Academic Search

One of the problems in ultrasound surgery is the long treatment times when large tumour volumes are sonicated. Large tumours are usually treated by scanning the tumour volume using a sequence of individual focus points. During the scanning, it is possible that surrounding healthy tissue suffers from undesired temperature rise. The selection of the scanning path so that the tumour

Matti Malinenyx; Tomi Huttunen; Jari P. Kaipio; Kullervo Hynynen

2005-01-01

258

Air Path Estimation on Diesel HCCI Engine  

Microsoft Academic Search

In this paper, we address the problem of air path variables estimation for an HCCI engine. Two observers are pro- posed. Both rely on physical assumptions on the com- bustion, but use different sensors. After proving conver- gence in the two cases, we carry out comparisons based on simulation results. We stress the impact of two particu- lar additional sensors

J. Chauvin; N. Petit; P. Rouchon; C. Vigild; Ford Forschungszentrum Aachen

2006-01-01

259

Intelligent path prediction for vehicular travel  

Microsoft Academic Search

This thesis presents a methodology for intelligent path prediction, predicting the motion of an observed vehicle by reasoning about the actions taken by the operator of the vehicle. The thesis considers only the problem of tracking a vehicle performing a transit mission, a mission that proceeds from a start location to a goal location guided by an intelligent planning criterion.

James Alan Krozel

1992-01-01

260

Flux Control in Networks of Diffusion Paths  

SciTech Connect

A class of optimization problems in networks of intersecting diffusion domains of a special form of thin paths has been considered. The system of equations describing stationary solutions is equivalent to an electrical circuit built of intersecting conductors. The solution of an optimization problem has been obtained and extended to the analogous electrical circuit. The interest in this network arises from, among other applications, an application to wave-particle diffusion through resonant interactions in plasma.

A. I. Zhmoginov and N. J. Fisch

2009-07-08

261

Integrated assignment and path planning  

NASA Astrophysics Data System (ADS)

A surge of interest in unmanned systems has exposed many new and challenging research problems across many fields of engineering and mathematics. These systems have the potential of transforming our society by replacing dangerous and dirty jobs with networks of moving machines. This vision is fundamentally separate from the modern view of robotics in that sophisticated behavior is realizable not by increasing individual vehicle complexity, but instead through collaborative teaming that relies on collective perception, abstraction, decision making, and manipulation. Obvious examples where collective robotics will make an impact include planetary exploration, space structure assembly, remote and undersea mining, hazardous material handling and clean-up, and search and rescue. Nonetheless, the phenomenon driving this technology trend is the increasing reliance of the US military on unmanned vehicles, specifically, aircraft. Only a few years ago, following years of resistance to the use of unmanned systems, the military and civilian leadership in the United States reversed itself and have recently demonstrated surprisingly broad acceptance of increasingly pervasive use of unmanned platforms in defense surveillance, and even attack. However, as rapidly as unmanned systems have gained acceptance, the defense research community has discovered the technical pitfalls that lie ahead, especially for operating collective groups of unmanned platforms. A great deal of talent and energy has been devoted to solving these technical problems, which tend to fall into two categories: resource allocation of vehicles to objectives, and path planning of vehicle trajectories. An extensive amount of research has been conducted in each direction, yet, surprisingly, very little work has considered the integrated problem of assignment and path planning. This dissertation presents a framework for studying integrated assignment and path planning and then moves on to suggest an exact mathematical model and solution techniques. The approach adopted is based upon the very flexible New Product Development model but also blends many features from other approaches. Solution methods using branch and bound and construction heuristics are developed and tested on several example problems, including a military scenario featuring unmanned air vehicles.

Murphey, Robert A.

262

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

263

Toward Efficient Trajectory Planning: The Path-Velocity Decomposition  

Microsoft Academic Search

We present a novel approach to solving the trajectory plan ning problem (TPP) in time-varying environments. The es sence of our approach lies in a heuristic but natural decom position of TPP into two subproblems: (1) planning a path to avoid collision with static obstacles and (2) planning the velocity along the path to avoid collision with moving obsta cles.

Kamal Kant; Steven W. Zucker

1986-01-01

264

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

265

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

266

Existence and construction of edge disjoint paths on expander graphs  

Microsoft Academic Search

Given an expander graph G = (V, E) and a set of q disjoint pairs of vertices in V , we are interested in finding for each pair (ai, bi), a path connecting ai to bi, such that the set of q paths so found is edge-disjoint. (For general graphs the related decision problem is NP- complete.) We prove sufficient

Andrei Z. Broder; Alan M. Friezet; Eli Upfal

1992-01-01

267

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

268

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

269

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

270

Robot Path Planning in Unknown Environments Using Particle Swarm Optimization  

Microsoft Academic Search

We propose a method of robot path planning in unknown environments based on particle swarm optimization in this paper. We firstly transform the problem of robot path planning into a minimization one, and then define the fitness of a particle based on the positions of the target and the obstacles in the environment. The positions of globally best particle in

Li Lu; Dunwei Gong

2008-01-01

271

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

272

Minimal entropy probability paths between genome families.  

PubMed

We develop a metric for probability distributions with applications to biological sequence analysis. Our distance metric is obtained by minimizing a functional defined on the class of paths over probability measures on N categories. The underlying mathematical theory is connected to a constrained problem in the calculus of variations. The solution presented is a numerical solution, which approximates the true solution in a set of cases called rich paths where none of the components of the path is zero. The functional to be minimized is motivated by entropy considerations, reflecting the idea that nature might efficiently carry out mutations of genome sequences in such a way that the increase in entropy involved in transformation is as small as possible. We characterize sequences by frequency profiles or probability vectors, in the case of DNA where N is 4 and the components of the probability vector are the frequency of occurrence of each of the bases A, C, G and T. Given two probability vectors a and b, we define a distance function based as the infimum of path integrals of the entropy function H( p) over all admissible paths p(t), 0 < or = t< or =1, with p(t) a probability vector such that p(0)=a and p(1)=b. If the probability paths p(t) are parameterized as y(s) in terms of arc length s and the optimal path is smooth with arc length L, then smooth and "rich" optimal probability paths may be numerically estimated by a hybrid method of iterating Newton's method on solutions of a two point boundary value problem, with unknown distance L between the abscissas, for the Euler-Lagrange equations resulting from a multiplier rule for the constrained optimization problem together with linear regression to improve the arc length estimate L. Matlab code for these numerical methods is provided which works only for "rich" optimal probability vectors. These methods motivate a definition of an elementary distance function which is easier and faster to calculate, works on non-rich vectors, does not involve variational theory and does not involve differential equations, but is a better approximation of the minimal entropy path distance than the distance //b-a//(2). We compute minimal entropy distance matrices for examples of DNA myostatin genes and amino-acid sequences across several species. Output tree dendograms for our minimal entropy metric are compared with dendograms based on BLAST and BLAST identity scores. PMID:15133624

Ahlbrandt, Calvin; Benson, Gary; Casey, William

2003-12-02

273

Optimal path planning for unmanned air vehicles with kinematic and tactical constraints  

Microsoft Academic Search

We consider a class of 2D optimal path-planning problems for unmanned air vehicles (UAVs) with kinematic and tactical constraints. The existence of an optimal path class satisfying the UAV kinematic constraints and vector calculus are exploited to reduce this class of optimal path-planning problems to a parameter optimization problem. Illustrative tactical constraints arising in target touring and obstacle avoidance problems

Guang Yang; Vikram Kapila

2002-01-01

274

Path planning for everday robotics with SANDROS  

SciTech Connect

We discuss the integration of the SANDROS path planner into a general robot simulation and control package with the inclusion of a fast geometry engine for distance calculations. This creates a single system that allows the path to be computed, simulated, and then executed on the physical robot. The architecture and usage procedures are presented. Also, we present examples of its usage in typical environments found in our organization. The resulting system is as easy to use as the general simulation system (which is in common use here) and is fast enough (example problems are solved in seconds) to be used interactively on an everyday basis.

Watterberg, P.; Xavier, P. [Sandia National Labs., Albuquerque, NM (United States); Hwang, Y. [Korea Inst. of Science and Technology, Seoul (Korea, Republic of)

1997-02-01

275

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

276

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

277

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

278

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

279

(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

280

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

281

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

282

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

283

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

284

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

285

Path planning and the topology of configuration space  

SciTech Connect

This work considers the path planning problem for planar revolute manipulators operating in a workspace of polygonal obstacles. This problem is solved by determining the topological characteristics of obstacles in configuration space, thereby determining where feasible paths can be found. A collision-free path is then calculated by using the mathematical description of the boundaries of only those configuration space obstacles with which collisions are possible. The key to this technique is a simple test for determining whether two disjoint obstacles are connected in configuration space. This test allows the path planner to restrict its calculations to regions in which collision-free paths are guaranteed a priori, thus avoiding unnecessary computations and resulting in an efficient implementations. Typical timing results for environments consisting of four polyhedral obstacles comprised of a total of 27 vertices are on the order of 22 ms on a SPARC-IPC workstation.

Maciejewski, A.A.; Fox, J.J. [Purdue Univ., West Lafayette, IN (United States). School of Electrical Engineering

1993-08-01

286

Perfect discretization of reparametrization invariant path integrals  

NASA Astrophysics Data System (ADS)

To obtain a well-defined path integral one often employs discretizations. In the case of gravity and reparametrization-invariant systems, the latter of which we consider here as a toy example, discretizations generically break diffeomorphism and reparametrization symmetry, respectively. This has severe implications, as these symmetries determine the dynamics of the corresponding system. Indeed we will show that a discretized path integral with reparametrization-invariance is necessarily also discretization independent and therefore uniquely determined by the corresponding continuum quantum mechanical propagator. We use this insight to develop an iterative method for constructing such a discretized path integral, akin to a Wilsonian RG flow. This allows us to address the problem of discretization ambiguities and of an anomaly-free path integral measure for such systems. The latter is needed to obtain a path integral, that can act as a projector onto the physical states, satisfying the quantum constraints. We will comment on implications for discrete quantum gravity models, such as spin foams.

Bahr, Benjamin; Dittrich, Bianca; Steinhaus, Sebastian

2011-05-01

287

Path analysis in genetic epidemiology: a critique.  

PubMed Central

Path analysis, a form of general linear structural equation models, is used in studies of human genetics data to discern genetic, environmental, and cultural factors contributing to familial resemblance. It postulates a set of linear and additive parametric relationships between phenotypes and genetic and cultural variables and then essentially uses the assumption of multivariate normality to estimate and perform tests of hypothesis on parameters. Such an approach has been advocated for the analysis of genetic epidemiological data by D. C. Rao, N. Morton, C. R. Cloninger, L. J. Eaves, and W. E. Nance, among others. This paper reviews and evaluates the formulations, assumptions, methodological procedures, interpretations, and applications of path analysis. To give perspective, we begin with a discussion of path analysis as it occurs in the form of general linear causal models in several disciplines of the social sciences. Several specific path analysis models applied to lipoprotein concentrations, IQ, and twin data are then reviewed to keep the presentation self-contained. The bulk of the critical discussion that follows is directed toward the following four facets of path analysis: (1) coherence of model specification and applicability to data; (2) plausibility of modeling assumptions; (3) interpretability and utility of the model; and (4) validity of statistical and computational procedures. In the concluding section, a brief discussion of the problem of appropriate model selection is presented, followed by a number of suggestions of essentially model-free alternative methods of use in the treatment of complex structured data such as occurs in genetic epidemiology.

Karlin, S; Cameron, E C; Chakraborty, R

1983-01-01

288

Scatter Search and Path Relinking: Advances and Applications  

Microsoft Academic Search

Scatter search (SS) is a population-based method that has recently been shown to yield promising outcomes for solving combinatorial and nonlinear optimization problems. Based on formulations originally proposed in the 1960s for combining decision rules and problem constraints, SS uses strategies for combining solution vectors that have proved effective in a variety of problem settings. Path relinking (PR) has been

Fred Glover; Manuel Laguna; Rafael Marti

289

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

290

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

291

A temporal intermediate stimulus problem.  

PubMed

Pigeons discriminated the serial position of a target duration among a sequence of 3 stimulus durations; the specific duration sequences changed across trials. In different conditions, the target duration was the shortest, intermediate, or longest duration in the sequence. Conditions involved a series of transitions in which new duration sequences were added to the stimulus set, providing an assessment of transfer. Pigeons learned and transferred the discrimination when the target was the shortest or longest duration. When, however, the target was the intermediate duration, the birds had great difficulty learning the task and exhibited little transfer to novel sequences. These findings are similar to those observed with nontemporal stimuli in a classic discrimination task, the intermediate stimulus problem. They provide an extension of work on relational timing to a more complex situation. PMID:9805788

Fetterman, J G

1998-10-01

292

Establish The Special Virtual Manipulator Model for Mobile Robot Obstacle Avoidance and Path Planning  

Microsoft Academic Search

This paper presents a new modeling method for mobile robot obstacle avoidance problem and multi-robot system path planning problem. In this paper, we study the inner relationship between the manipulator structure and the mobile robot obstacle avoidance and path planning. We demonstrate that the mobile robot obstacle avoiding problem can be simplified into the manipulator structure construction, based on the

Xiaowei Cao; Hanxu Sun; Qingxuan Jia

2007-01-01

293

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

294

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

295

Research on path planning method of multi mobile robot in dynamic environment  

Microsoft Academic Search

A path planning structure based on hierarchical idea was adopted in this paper. In this structure, the global path planning is done firstly by the robot and the local online adjusting is done afterward. This kind of structure can debase the calculation complexity of path planning. Then, aiming at the problem of local motion planning, a conflict-resolution strategy based on

Linan Zu; Lingling Chen; Zuojun Liu; Peng Yang

2008-01-01

296

Finding rectilinear least cost paths in the presence of convex polygonal congested regions  

Microsoft Academic Search

This paper considers the problem of finding the least cost rectilinear distance path in the presence of convex polygonal congested regions. We demonstrate that there are a finite, though exponential number of potential staircase least cost paths between a specified pair of origin-destination points. An upper bound for the number of entry\\/exit points of a rectilinear path between two points

Avijit Sarkar; Rajan Batta; Rakesh Nagi

2009-01-01

297

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.

298

A path integral approach to agent planning  

Microsoft Academic Search

Control theory is a mathematical description of how to act optimally to gain future rewards. In this paper We discuss a class of non-linear stochastic control problems that can be ecien tly solved using a path integral. In this control for- malism, the central concept of cost-to-go or value function becomes a free energy and methods and concepts from sta-

Hilbert J. Kappen; Wim Wiegerinck; B. van den Broek

299

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

300

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

301

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

302

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.

303

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

304

Recursive log-barrier method for on-line time-optimal robot path tracking  

Microsoft Academic Search

This paper focuses on time-optimal robot path tracking and develops an approximate, log-barrier batch solution method to rapidly solve discretized, convexly reformuled path tracking problems. Based on this batch solution method, which results in smooth actuator torques, a recursive variant is derived for on-line path tracking. The results and trade-offs in calculation time, delay and path duration are compared for

Diederik Verscheure; Moritz Diehl; Joris De Schutter; Jan Swevers

2009-01-01

305

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

306

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

307

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

308

Path Flow Estimation Using Time Varying Coefficient State Space Model  

NASA Astrophysics Data System (ADS)

The dynamic path flow information is very crucial in the field of transportation operation and management, i.e., dynamic traffic assignment, scheduling plan, and signal timing. Time-dependent path information, which is important in many aspects, is nearly impossible to be obtained. Consequently, researchers have been seeking estimation methods for deriving valuable path flow information from less expensive traffic data, primarily link traffic counts of surveillance systems. This investigation considers a path flow estimation problem involving the time varying coefficient state space model, Gibbs sampler, and Kalman filter. Numerical examples with part of a real network of the Taipei Mass Rapid Transit with real O-D matrices is demonstrated to address the accuracy of proposed model. Results of this study show that this time-varying coefficient state space model is very effective in the estimation of path flow compared to time-invariant model.

Jou, Yow-Jen; Lan, Chien-Lun

2009-08-01

309

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

310

Path instability of a rising bubble  

NASA Astrophysics Data System (ADS)

Path instability of a rising bubble is studied by carrying out DNS around a freely moving ellipsoidal bubble with a prescribed aspect ratio. The flow field is obtained by solving the full Navier-Stokes equations and the velocity and rotation rate of the bubble are found by solving the Kirchhoff equations in a form suitable to vortical flows. The problem has two control parameters, ie the aspect ratio K and the Galileo number Ga. Beyond a certain critical value K(Ga) or Ga(K), the path of the bubble first bifurcates towards a plane zigzag whose geometrical characteristics are in good agreement with experimental observations. Detailed examination reveals that the transition to the zigzag path occurs through a supercritical Hopf bifurcation when K is set fixed, while it occurs through a more complex process when Ga is set fixed. Ultimately, the zigzag degenerates into a fully helical trajectory, as observed in experiments. Examining the vorticity field reveals a one-to-one correspondance between the topology of the wake and the nature of the path. The competition between creation of vorticity at the bubble surface and evacuation in the wake allows us to propose a consistent scenario for explaining physically the observed transitions.

Magnaudet, Jacques; Mougin, Guillaume

2001-11-01

311

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

312

Use of a Colony of Cooperating Agents and MAPLE To Solve the Traveling Salesman Problem.  

ERIC Educational Resources Information Center

|This paper reviews an approach for finding optimal solutions to the traveling salesman problem, a well-known problem in combinational optimization, and describes implementing the approach using the MAPLE computer algebra system. The method employed in this approach to the problem is similar to the way ant colonies manage to establish shortest

Guerrieri, Bruno

313

Optimization of the time-dependent traveling salesman problem with Monte Carlo methods  

Microsoft Academic Search

A problem often considered in operations research and computational physics is the traveling salesman problem, in which a traveling salesperson has to find the shortest closed tour between a certain set of cities. This problem has been extended to more realistic scenarios, e.g., the ``real'' traveling salesperson has to take rush hours into consideration. We will show how this extended

Johannes Bentner; Günter Bauer; Gustav M. Obermair; Ingo Morgenstern; Johannes Schneider

2001-01-01

314

Vehicle Scheduling Problem for the Single-Depot Based on Genetic Algorithms  

Microsoft Academic Search

Vehicle scheduling problem is a common problem in trucking industry. Because of the existence of a large number of constraints, it is difficult to obtain the optimal solution. This issue has been an NP difficult problem. In this paper, we will both establish bi-objective vehicle scheduling model with the goal that shortest vehicle Run and least number of vehicles and

Chun-qiu Xu; Hua Xuan; Bing Li; Fang-fang Su

2010-01-01

315

Reaction Path Optimization with Holonomic Constraints and Kinetic Energy Potentials  

SciTech Connect

Two methods are developed to enhance the stability, efficiency, and robustness of reaction path optimization using a chain of replicas. First, distances between replicas are kept equal during path optimization via holonomic constraints. Finding a reaction path is, thus, transformed into a constrained optimization problem. This approach avoids force projections for finding minimum energy paths (MEPs), and fast-converging schemes such as quasi-Newton methods can be readily applied. Second, we define a new objective function - the total Hamiltonian - for reaction path optimization, by combining the kinetic energy potential of each replica with its potential energy function. Minimizing the total Hamiltonian of a chain determines a minimum Hamiltonian path (MHP). If the distances between replicas are kept equal and a consistent force constant is used, then the kinetic energy potentials of all replicas have the same value. The MHP in this case is the most probable isokinetic path. Our results indicate that low-temperature kinetic energy potentials (<5 K) can be used to prevent the development of kinks during path optimization and can significantly reduce the required steps of minimization by 2-3 times without causing noticeable differences between a MHP and MEP. These methods are applied to three test cases, the C?eq-to-Cax isomerization of an alanine dipeptide, the ?C?- to-¹C? transition of an ?-D-glucopyranose, and the helix-to-sheet transition of a GNNQQNY heptapeptide. By applying the methods developed in this work, convergence of reaction path optimization can be achieved for these complex transitions, involving full atomic details and a large number of replicas (>100). For the case of helix-to-sheet transition, we identify pathways whose energy barriers are consistent with experimental measurements. Further, we develop a method based on the work energy theorem to quantify the accuracy of reaction paths and to determine whether the atoms used to define a path are enough to provide quantitative estimation of energy barriers.

Brokaw, Jason B.; Haas, Kevin R.; Chu, Jhih-wei

2009-08-11

316

Universal conditions for exact path integration in neural systems.  

PubMed

Animals are capable of navigation even in the absence of prominent landmark cues. This behavioral demonstration of path integration is supported by the discovery of place cells and other neurons that show path-invariant response properties even in the dark. That is, under suitable conditions, the activity of these neurons depends primarily on the spatial location of the animal regardless of which trajectory it followed to reach that position. Although many models of path integration have been proposed, no known single theoretical framework can formally accommodate their diverse computational mechanisms. Here we derive a set of necessary and sufficient conditions for a general class of systems that performs exact path integration. These conditions include multiplicative modulation by velocity inputs and a path-invariance condition that limits the structure of connections in the underlying neural network. In particular, for a linear system to satisfy the path-invariance condition, the effective synaptic weight matrices under different velocities must commute. Our theory subsumes several existing exact path integration models as special cases. We use entorhinal grid cells as an example to demonstrate that our framework can provide useful guidance for finding unexpected solutions to the path integration problem. This framework may help constrain future experimental and modeling studies pertaining to a broad class of neural integration systems. PMID:22493275

Issa, John B; Zhang, Kechen

2012-04-09

317

Universal conditions for exact path integration in neural systems  

PubMed Central

Animals are capable of navigation even in the absence of prominent landmark cues. This behavioral demonstration of path integration is supported by the discovery of place cells and other neurons that show path-invariant response properties even in the dark. That is, under suitable conditions, the activity of these neurons depends primarily on the spatial location of the animal regardless of which trajectory it followed to reach that position. Although many models of path integration have been proposed, no known single theoretical framework can formally accommodate their diverse computational mechanisms. Here we derive a set of necessary and sufficient conditions for a general class of systems that performs exact path integration. These conditions include multiplicative modulation by velocity inputs and a path-invariance condition that limits the structure of connections in the underlying neural network. In particular, for a linear system to satisfy the path-invariance condition, the effective synaptic weight matrices under different velocities must commute. Our theory subsumes several existing exact path integration models as special cases. We use entorhinal grid cells as an example to demonstrate that our framework can provide useful guidance for finding unexpected solutions to the path integration problem. This framework may help constrain future experimental and modeling studies pertaining to a broad class of neural integration systems.

Issa, John B.; Zhang, Kechen

2012-01-01

318

New potential functions for mobile robot path planning  

Microsoft Academic Search

Abstract—This paper first describes the problem of goals nonreachable with obstacles nearby when using potential field methods for mobile robot path planning. Then, new repulsive potential functions are presented by taking the relative distance between the robot and the goal into considera- tion, which ensures that the goal position is the global minimum of the total potential. Index Terms—GNRON problem,

S. S. Ge; Y. J. Cui

2000-01-01

319

Constructs of highly effective heat transport paths by bionic optimization  

Microsoft Academic Search

The optimization approach based on the biological evolution principle is used to construct the heat transport paths for volume-to-point\\u000a problem. The transport paths are constructed by inserting high conductivity materials in the heat conduction domain where\\u000a uniform or nonuniform heat sources exist. In the bionic optimization process, the optimal constructs of the high conductivity\\u000a material are obtained by numerically simulating

Xinguang Cheng; Zhixin Li; Zengyuan Guo

2003-01-01

320

PathMiner: predicting metabolic pathways by heuristic search  

Microsoft Academic Search

Motivation: Automated methods for biochemical pathway inference are becoming increasingly important for understand- ing biological processes in living and synthetic systems. With the availability of data on complete genomes and increasing information about enzyme-catalyzed biochemistry it is becom- ing feasible to approach this problem computationally. In this paper we present PathMiner, a system for automatic metabolic pathway inference. PathMiner predicts

D. C. Mcshan; S. Rao; Imran Shah

2003-01-01

321

Transparent virtual optical code\\/wavelength path network  

Microsoft Academic Search

The concept of a virtual optical code\\/wavelength path (VOCP\\/VWP) is introduced within the transport layer of the network. A potential solution to wavelength path (WP) allocation problems that may limit the expansion of WDM-based transport on mul-networks is demonstrated by employing optical code division multiplexing (OCDM). Key technologies of the VOC\\/VWP concept are both optical code and wavelength conversions. A

Hideyuki Sotobayashi; Wataru Chujo; Ken-ichi Kitayama

2002-01-01

322

Teaching of Critical Path Networks Using Software Packages  

Microsoft Academic Search

The aim of this paper is to review a published paper, ‘Using computer software packages to enhance the teaching of Engineering\\u000a Management Science: Part 1 -Critical path networks’. Excel in Microsoft Office 2007 was discovered to be able to solve critical\\u000a path network problems with some programming. The capabilities of the two previously evaluated packages, Microsoft Project\\u000a 2007 and Quantitative

H. Ku

2009-01-01

323

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

324

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

325

Parallel Traveling Salesman Problem  

NSDL National Science Digital Library

The traveling salesman problem is a classic optimization problem in which one seeks to minimize the path taken by a salesman in traveling between N cities, where the salesman stops at each city one and only one time, never retracing his/her route. This implementation is designed to run on UNIX systems with X-Windows, and includes parallelization using MPI.

Joiner, David; Hassinger, Jonathan

326

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

327

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

328

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

329

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

330

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

331

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

332

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.

333

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

334

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

335

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

336

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

337

DICOM involving XML path-tag  

NASA Astrophysics Data System (ADS)

Digital Imaging and Communications in Medicine (DICOM) is a standard for handling, storing, printing, and transmitting information in medical imaging. XML (Extensible Markup Language) is a set of rules for encoding documents in machine-readable form which has become more and more popular. The combination of these two is very necessary and promising. Using XML tags instead of numeric labels in DICOM files will effectively increase the readability and enhance the clear hierarchical structure of DICOM files. However, due to the fact that the XML tags rely heavily on the orders of the tags, the strong data dependency has a lot of influence on the flexibility of inserting and exchanging data. In order to improve the extensibility and sharing of DICOM files, this paper introduces XML Path-Tag to DICOM. When a DICOM file is converted to XML format, adding simple Path-Tag into the DICOM file in place of complex tags will keep the flexibility of a DICOM file while inserting data elements and give full play to the advantages of the structure and readability of an XML file. Our method can solve the weak readability problem of DICOM files and the tedious work of inserting data into an XML file. In addition, we set up a conversion engine that can transform among traditional DICOM files, XML-DCM and XML-DCM files involving XML Path-Tag efficiently.

Zeng, Qiang; Yao, Zhihong; Liu, Lei

2011-03-01

338

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

339

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

340

Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs  

Microsoft Academic Search

A Hamiltonian path of a graph G is a simple path that contains each vertex of G exactly once. A Hamiltonian cycle of a graph is a simple cycle with the same property. The Hamiltonian path (resp. cycle) problem involves testing whether a Hamiltonian path (resp. cycle) exists in a graph. The 1HP (resp. 2HP) problem is to determine whether

Ruo-wei Hung; Maw-shang Chang

2005-01-01

341

Extensions of TOPSIS for multi-objective large-scale nonlinear programming problems  

Microsoft Academic Search

In this paper, we focus on multi-objective large-scale nonlinear programming (MOLSNLP) problems with block angular structure. We extend technique for order preference by similarity ideal solution (TOPSIS) approach to solve (MOLSNLP) problems. Compromise (TOPSIS) control minimizes the measure of distance, providing that the closest solution should have the shortest distance from the positive ideal solution (PIS) as well as the

Mahmoud A. Abo-sinna; Azza H. Amer

2005-01-01

342

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

343

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

344

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

345

The flow-refueling location problem for alternative-fuel vehicles  

Microsoft Academic Search

Beginning with Hodgson (Geogr.Anal.22(1990) 270), several researchers have been developing a new kind of location-allocation model for “flow capturing.” Instead of locating central facilities to serve demand at fixed points in space, their models aim to serve demand consisting of origin-destination flows along their shortest paths. This paper extends flow-capturing models to optimal location of refueling facilities for alternative-fuel (alt-fuel)

Michael Kuby; Seow Lim

2005-01-01

346

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

347

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

348

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

349

Seismic refraction analysis: the path forward  

USGS Publications Warehouse

Seismic Refraction Methods: Unleashing the Potential and Understanding the Limitations; Tucson, Arizona, 29 March 2012 A workshop focused on seismic refraction methods took place on 29 May 2012, associated with the 2012 Symposium on the Application of Geophysics to Engineering and Environmental Problems. This workshop was convened to assess the current state of the science and discuss paths forward, with a primary focus on near-surface problems but with an eye on all applications. The agenda included talks on these topics from a number of experts interspersed with discussion and a dedicated discussion period to finish the day. Discussion proved lively at times, and workshop participants delved into many topics central to seismic refraction work.

Haines, Seth S.; Zelt, Colin; Doll, William

2012-01-01

350

Enhancing Corridor Maps for Real-Time Path Planning in Virtual Environments  

Microsoft Academic Search

A central problem in interactive virtual environments is planning high-quality paths for characters avoiding obstacles in the environment. Current applications require a path planner that is fast (to ensure real-time interaction with the environment) and flexible (to avoid local hazards). In addition, paths need to be natural, i.e. smooth and short. To satisfy these requirements, we need an adequate representation

Roland Geraerts; Mark H. Overmars

2008-01-01

351

Direct path interference suppression in bistatic system: DTV based radar  

Microsoft Academic Search

Over the past 20 years, bistatic radar has been an emerging technology. One of the major problems in continuous wave bistatic radar is the direct path interference (DPI). The reflected signal from the target is received at the background of this interference; the target would be buried under the sidelobes of the DPI in the receiver circuit. The conventional solution

Rajesh Saini; M. Cherniakov; V. Lenive

2003-01-01

352

Complete Path Planning for Closed Kinematic Chains with Spherical Joints  

Microsoft Academic Search

We study the path planning problem, without obstacles, for closed kinematic chains with n links connected by spherical joints in space or revolute joints in the plane. The configuration space of such systems is a real algebraic variety whose structure is fully deter- mined using techniques from algebraic geometry and differential topology. This structure is then exploited to design a

Jeffrey Coates Trinkle; Richard James Milgram

2002-01-01

353

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

354

Provably Correct High-level Timing Analysis Without Path Sensitization  

Microsoft Academic Search

This paper addresses the problem of true delay estimation during high level design. The existing delay estimation techniques ei- ther estimate the topological delay of the circuit which may be pes- simistic, or use gate-level timing analysis for calculating the true de- lay, which may be prohibitively expensive. We show that the paths in the implementation of a behavioral spec-

Subhrajit Bhattacharya; Sujit Dey; Franc Brglez

1994-01-01

355

QoS routing via multiple paths using bandwidth reservation.  

National Technical Information Service (NTIS)

The authors address the problem of computing a multipath, consisting of possibly overlapping paths, to transmit data from the source node s to the destination node d over a computer network while ensuring deterministic bounds on end-to-end delay or delive...

N. S. V. Rao S. G. Batsell

1997-01-01

356

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

357

Divide and conquer evolutionary TSP solution for vehicle path planning  

Microsoft Academic Search

The problem of robotic area coverage is applicable to many domains, such as search, agriculture, cleaning, and machine tooling. The robotic area coverage task is concerned with moving a vehicle with an effector, or sensor, through the task space such that the sensor passes over every point in the space. For covering complex areas, back and forth paths are inadequate.

Ryan J. Meuth; Donald C. Wunsch

2008-01-01

358

A Predictive Controller for Autonomous Vehicle Path Tracking  

Microsoft Academic Search

This paper presents a model predictive controller (MPC) structure for solving the path-tracking problem of terrestrial autonomous vehicles. To achieve the desired performance during high-speed driving, the controller architecture considers both the kinematic and the dynamic control in a cascade structure. Our study contains a comparative study between two kinematic linear predictive control strategies: The first strategy is based on

Guilherme V. Raffo; Guilherme K. Gomes; Julio E. Normey-Rico; Christian Roberto Kelber; Leandro B. Becker

2009-01-01

359

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

360

Path planning for data assimilation in mobile environmental monitoring systems  

Microsoft Academic Search

By combining a low-order model of forecast errors, the extended Kalman filter, and classical continuous optimization, we develop an integrated methodology for planning mobile sensor paths to sample continuous fields. Agent trajectories are developed that specifically take into account the fact that data collected will be used for near real-time assimilation with large predictive models. This aspect of the problem

Franz S. Hover

2009-01-01

361

Maximum distributions of bridges of noncolliding Brownian paths  

NASA Astrophysics Data System (ADS)

One-dimensional Brownian motion starting from the origin at time t=0 , conditioned to return to the origin at time t=1 and to stay positive during time interval 0paths attained in the time interval t?(0,1) are studied to characterize the statistics of random patterns of the repulsive paths on the spatiotemporal plane. For the outermost path, the distribution function of maximum value is exactly determined for general N . We show that the present N -path system of noncolliding Bessel bridges is realized as the positive-eigenvalue process of the 2N×2N matrix-valued Brownian bridge in the symmetry class C. Using this fact, computer simulations are performed and numerical results on the N dependence of the maximum-value distributions of the inner paths are reported. The present work demonstrates that the extreme-value problems of noncolliding paths are related to random matrix theory, the representation theory of symmetry, and number theory.

Kobayashi, Naoki; Izumi, Minami; Katori, Makoto

2008-11-01

362

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

363

Deriving multiple near-optimal solutions to deterministic reservoir operation problems  

NASA Astrophysics Data System (ADS)

Even deterministic reservoir operation problems with a single objective function may have multiple near-optimal solutions (MNOS) whose objective values are equal or sufficiently close to the optimum. MNOS is valuable for practical reservoir operation decisions because having a set of alternatives from which to choose allows reservoir operators to explore multiple options whereas the traditional algorithm that produces a single optimum does not offer them this flexibility. This paper presents three methods: the near-shortest paths (NSP) method, the genetic algorithm (GA) method, and the Markov chain Monte Carlo (MCMC) method, to explore the MNOS. These methods, all of which require a long computation time, find MNOS using different approaches. To reduce the computation time, a narrower subspace, namely a near-optimal space (NOSP, described by the maximum and minimum bounds of MNOS) is derived. By confining the MNOS search within the NOSP, the computation time of the three methods is reduced. The proposed methods are validated with a test function before they are examined with case studies of both a single reservoir (the Three Gorges Reservoir in China) and a multireservoir system (the Qing River Cascade Reservoirs in China). It is found that MNOS exists for the deterministic reservoir operation problems. When comparing the three methods, the NSP method is unsuitable for large-scale problems but provides a benchmark to which solutions of small- and medium-scale problems can be compared. The GA method can produce some MNOS but is not very efficient in terms of the computation time. Finally, the MCMC method performs best in terms of goodness-of-fit to the benchmark and computation time, since it yields a wide variety of MNOS based on all retained intermediate results as potential MNOS. Two case studies demonstrate that the MNOS identified in this study are useful for real-world reservoir operation, such as the identification of important operation time periods and tradeoffs among objectives in multipurpose reservoirs.

Liu, Pan; Cai, Ximing; Guo, Shenglian

2011-08-01

364

One-dimensional Gromov minimal filling problem  

NASA Astrophysics Data System (ADS)

The paper is devoted to a new branch in the theory of one-dimensional variational problems with branching extremals, the investigation of one-dimensional minimal fillings introduced by the authors. On the one hand, this problem is a one-dimensional version of a generalization of Gromov's minimal fillings problem to the case of stratified manifolds. On the other hand, this problem is interesting in itself and also can be considered as a generalization of another classical problem, the Steiner problem on the construction of a shortest network connecting a given set of terminals. Besides the statement of the problem, we discuss several properties of the minimal fillings and state several conjectures. Bibliography: 38 titles.

Ivanov, Alexandr O.; Tuzhilin, Alexey A.

2012-05-01

365

Cooperative path planning for multiple UAVs in dynamic and uncertain environments  

Microsoft Academic Search

This paper addresses the problem of cooperative path planning for a fleet of unmanned aerial vehicles (UAVs). The paths are optimized to account for uncertainty\\/adversaries in the environment by modeling the probability of UAV loss. The approach extends prior work by coupling the failure probabilities for each UAV to the selected missions for all other UAVs. In order to maximize

John S. Bellingham; Michael Tillerson; Mehdi Alighanbari

2002-01-01

366

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

367

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

368

Study on time divided double optical paths ultraviolet fluorescence for concentration measuring of sulfur dioxide  

Microsoft Academic Search

The research on the detection of sulfur dioxide concentration in flue-gas is a hot topic all the time. Based on the analysis of the measuring principles for the sulfur dioxide concentration using ultraviolet fluorescence method, one new measuring method using time-divided double optical paths is proposed. This method overcomes the problems of cross sensitivity and background noise in single path

Shanpo Nian; Caixia Hou; Lei Chen; Ruikun Gong; Guangxiang Zhang; Yansong Tian

2010-01-01

369

Optimal path planning in a constant wind with a bounded turning rate  

Microsoft Academic Search

In this paper, we explore the problem of generating the optimal time path from an initial position and orientation to a flnal position and orientation in the two-dimensional plane for an aircraft with a bounded turning radius in the presence of a constant wind. Following the work of Boissonnat, we show using the Minimum Principle that the opti- mal path

Timothy G. McGee; Stephen Spry; J. Karl Hedrick

370

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

371

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

372

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

373

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

374

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

375

Adaptive Fastest Path Computation on a Road Network: A Traffic Mining Approach  

Microsoft Academic Search

E-cient fastest path computation in the presence of varying speed conditions on a large scale road network is an essential problem in modern navigation systems. Factors afiecting road speed, such as weather, time of day, and vehicle type, need to be considered in order to select fast routes that match current driving conditions. Most existing systems compute fastest paths based

Hector Gonzalez; Jiawei Han; Xiaolei Li; Margaret Myslinska; John Paul Sondag

2007-01-01

376

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

377

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

378

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

379

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

380

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

381

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

382

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

383

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

384

Path Tracking Control Problem Formulation of an LHD Loader  

Microsoft Academic Search

Load-haul-dump units (LHD) are loader-type vehicles that arefre quently employed in the underground mines for transfer of ore from the loading point to ore pass. Because they have to travel in the relatively narrow and restricted underground galleries, they have less height and are narrower than the ordinary mechanical loaders that are used in construction work. Furthermore, they are articu

Ahmad Hemami; Vladimir Polotski

1998-01-01

385

The time-dependent traveling salesman problem  

NASA Astrophysics Data System (ADS)

A problem often considered in Operations Research and Computational Physics is the traveling salesman problem, in which a traveling salesperson has to find the shortest closed tour between a given set of cities touching each city exactly once. The distances between the single nodes are known to the traveling salesperson. An extension of this problem is the time-dependent traveling salesman problem, in which these distances vary in time. I will show how this more complex problem is treated with physical optimization algorithms like simulated annealing. I will present results for the problem of the 127 beergardens in the area of Augsburg, in which I define a traffic zone in which traffic jams occur in the afternoon.

Schneider, Johannes

2002-11-01

386

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.

387

Application of the transmissibility concept in transfer path analysis  

NASA Astrophysics Data System (ADS)

In recent years, there has been a renewed interest in developing faster and simpler transfer path analysis (TPA) methods. A dominant class of these new approaches, often referred to as Operational Path Analyses (OPA), is designed to achieve this goal by using only operational data in conjunction with the application of the transmissibility concept. Despite the reduction in measurement time and complexity, these suffer from a number of limitations, such as problems related to the estimation of transmissibility, or the unreliability of the results due to cross-coupling between path inputs, etc., which makes them prone to errors. Some of these only apply to one specific method, while others are common to all transmissibility based approaches. The goal of this paper is to identify and describe these limitations and point out the potential dangers of applying such methods without taking these into account.

Gajdatsy, P.; Janssens, K.; Desmet, Wim; van der Auweraer, H.

2010-10-01

388

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

389

Representational momentum for a spiral path.  

PubMed

When a ball is shot through a spiral tube at high speed, the ball emerges in a straight path tangent to the ball's point of departure from the tube. However, past research has shown that many Ss believe the ball follows a curved pathway. In the 3 experiments described in this article, a ball traveling through a spiral tube was animated on a computer graphics screen. Ss' memory distortions for positions of the ball along each of 3 pathways were measured using a representational momentum paradigm. Retention interval was varied across the 3 experiments. The results from the 3 experiments reported here replicate retention interval results previously reported for representational momentum effects, and they suggest that the representational pathway of a ball exiting a spiral tube is spiral in shape. These findings may shed some light on why people have demonstrated naiveté on the spiral tube problem in past research. PMID:8064255

Freyd, J J; Jones, K T

1994-07-01

390

Path Planning for UAVs Under Communication Constraints Using SPLAT! and MILP  

Microsoft Academic Search

We will in this paper address the problem of offline path planning for Unmanned Aerial Vehicles (UAVs). Our goal is to find\\u000a paths that meet mission objectives, are safe with respect to collision and grounding, fuel efficient and satisfy criteria\\u000a for communication. Due to the many nonconvex constraints of the problem, Mixed Integer Linear Programming (MILP) will be used\\u000a in

Esten Ingar Grøtli; Tor Arne Johansen

391

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

392

Static and dynamic path selection on expander graphs (preliminary version): a random walk approach  

Microsoft Academic Search

This paper addresses the problem of virtual circuit switching in bounded degree expander graphs. We study the static and dynamic versions of this problem. Our solutions are baaed on the rapidly mixing properties of random walks on expander graphs. In the static version of the problem an algorithm is required to route a path between each of K pairs of

Andrei Z. Broder; Alan M. Friezet; Eli Upfalt

1997-01-01

393

Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach  

Microsoft Academic Search

This paper addresses the problem of virtual circuit switch- ing in bounded degree expander graphs. We study the static and dynamic versions of this problem. Our so- lutions are baaed on the rapidly mixing properties of random walks on expander graphs. In the static version of the problem an algorithm is required to route a path between each of K

Andrei Z. Broder; Alan M. Friezet; Eli Upfalt

394

Facilities layout design optimization with single loop material flow path configuration  

Microsoft Academic Search

Here we formulate the facilities layout design optimization problem for a single loop material flow path configuration. Because of the NP-bard nature of the overall search space, we employ a genetic approach to sample the decomposed search spaces. In addition we analyse the following features of the problem: (1) we estimate lower bounds for the unidirectional flow problem along the

P. BANERJEE; Y. ZHOU

1995-01-01

395

NASA: a path dependent organization  

Microsoft Academic Search

Mission agencies like NASA are complex systems, connecting people with science and technology to accomplish the desired tasks. Path dependence can help explain why NASA and other mission agencies often sacrifice long-term capabilities for short-term survival. The National Aeronautics and Space Act of 1958, followed by President Kennedy’s challenge, catapulted NASA to the moon, encouraged human exploration, and sped up

David Bruggeman

2002-01-01

396

A New Hybrid Iterated Local Search for the Open Vehicle Routing Problem  

Microsoft Academic Search

Open vehicle routing problem (OVRP) aims to design a set of open vehicle routes with the least number of vehicles and the shortest total travel time, for serving a set of geographically distributed customers with known coordinates and demands. In this paper, a new hybrid iterated local search algorithm IVND is proposed for solving the OVRP. The IVND integrates a

Ping Chen; Youli Qu; Houkuan Huang; Xingye Dong

2008-01-01

397

The double travelling salesman problem with multiple stacks - Formulation and heuristic solution approaches  

Microsoft Academic Search

This paper introduces the double travelling salesman problem with multiple stacks and presents four different metaheuristic approaches to its solution. The double TSP with multiple stacks is concerned with determining the shortest route performing pickups and deliveries in two separated networks (one for pickups and one for deliveries) using only one container. Repacking is not allowed, instead each item can

Hanne L. Petersen; Oli B. G. Madsen

2009-01-01

398

A NEURO-FUZZY APPROACH TO MODEL DISPATCHING RULES FOR THE PARALLEL MACHINE SCHEDULING PROBLEM  

Microsoft Academic Search

This paper deals with the modelling of four different dispatching rules applied to the identical parallel machine scheduling problem with the objective of minimizing makespan, by using Artificial Neural Networks (ANNs). The dispatching rules considered in this study are: Earliest Due Date (EDD), Minimum Slack (MS), Shortest Processing Time (SPT) and Critical Ratio (CR). The main purpose of the study

Derya Eren Akyol; G. Mirac Bayhan

399

Accelerating cleanup: Paths to closure  

SciTech Connect

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

Edwards, C.

1998-06-30

400

Path integral on star graph  

NASA Astrophysics Data System (ADS)

In this paper we study path integral for a single spinless particle on a star graph with N edges, whose vertex is known to be described by U(N) family of boundary conditions. After carefully studying the free particle case, both at the critical and off-critical levels, we propose a new path integral formulation that correctly captures all the scale-invariant subfamily of boundary conditions realized at fixed points of boundary renormalization group flow. Our proposal is based on the folding trick, which maps a scalar-valued wave function on star graph to an N-component vector-valued wave function on half-line. All the parameters of scale-invariant subfamily of boundary conditions are encoded into the momentum independent weight factors, which appear to be associated with the two distinct path classes on half-line that form the cyclic group Z2. We show that, when bulk interactions are edge-independent, these weight factors are generally given by an N-dimensional unitary representation of Z2. Generalization to momentum dependent weight factors and applications to worldline formalism are briefly discussed.

Ohya, Satoshi

2012-06-01

401

Multiple Paths to Encephalization and Technical Civilizations  

NASA Astrophysics Data System (ADS)

We propose consideration of at least two possible evolutionary paths for the emergence of intelligent life with the potential for technical civilization. The first is the path via encephalization of homeothermic animals; the second is the path to swarm intelligence of so-called superorganisms, in particular the social insects. The path to each appears to be facilitated by environmental change: homeothermic animals by decreased climatic temperature and for swarm intelligence by increased oxygen levels.

Schwartzman, David; Middendorf, George

2011-12-01

402

Quantifying the Causes of Path Inflation  

Microsoft Academic Search

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

Neil Spring; Ratul Mahajan; Thomas Anderson

2003-01-01

403

Chip layout optimization using critical path weighting  

Microsoft Academic Search

A chip layout procedure for optimizing the performance of critical timing paths in a synchronous digital circuit is presented. The procedure uses the path analysis data produced by a static timing analysis program to generate weights for critical nets on clock and data paths. These weights are then used to bias automatic placement and routing in the layout program. This

A. E. Dunlop; V. D. Agrawal; D. N. Deutsch; M. F. Jukl; P. Kozak; M. Wiesel

1984-01-01

404

Chip layout optimization using critical path weighting  

Microsoft Academic Search

A chip layout procedure for optimizing the performance of critical timing paths in a synchronous digital circuit is presented. The procedure uses the path analysis data produced by a static timing analysis program to generate weights for critical nets on clock and data paths. These weights are then used to bias automatic placement and routing in the layout program. This

A. E. Dunlop; V. D. Agrawal; D. N. Deutsch; M. F. Jukl; P. Kazak

1988-01-01

405

Multilinear decomposition of human walking paths  

Microsoft Academic Search

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

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

2010-01-01

406

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

407

Single machine scheduling problems with position-dependent processing times  

Microsoft Academic Search

We consider single machine scheduling problems in which the processing time of a job depends on its position in a processing\\u000a sequence. The objectives are to minimize the weighted sum of completion times, to minimize the maximum lateness and to minimize\\u000a the number of tardy jobs. For some special cases, we prove that the weighted shortest processing time (WSPT) rule,

Ji-Bo Wang; Li-Yan Wang; Dan Wang; Xiao-Yuan Wang; Wen-Jun Gao; Na Yin

2009-01-01

408

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

Microsoft Academic Search

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

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

1997-01-01

409

Preserving Topology Confidentiality in Inter-Domain Path Computation Using a Path-Key-Based Mechanism  

Microsoft Academic Search

Multiprotocol Label Switching (MPLS) and Generalized MPLS (GMPLS) Traffic Engineering (TE) Label Switched Paths (LSPs) may be computed by Path Computation Elements (PCEs). Where the TE LSP crosses multiple domains, such as Autonomous Systems (ASes), the path may be computed by multiple PCEs that cooperate, with each responsible for computing a segment of the path. However, in some cases (e.g.,

A. Farrel

410

Diffusion Path Theorems for Ternary Diffusion Couples  

NASA Astrophysics Data System (ADS)

A review is given of 17 theorems concerning diffusion paths in ternary diffusion couples published by Kirkaldy and Brown in 1963. An additional 11 theorems are given herein that were taken from work published on diffusion paths after that time. The new theorems are concerned primarily with diffusion paths that result from crossing multiple-phase regions in an interdiffusion zone. The theorems describe a method for classifying microstructural boundaries between the regions and a catalog of diffusion path features that are unique to each type of boundary. In addition, a proposal is given for how to plot diffusion paths in quaternary and higher order systems.

Morral, John E.

2012-10-01

411

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

412

Evaluation of guidewire path reproducibility  

PubMed Central

The number of minimally invasive vascular interventions is increasing. In these interventions, a variety of devices are directed to and placed at the site of intervention. The device used in almost all of these interventions is the guidewire, acting as a monorail for all devices which are delivered to the intervention site. However, even with the guidewire in place, clinicians still experience difficulties during the interventions. As a first step toward understanding these difficulties and facilitating guidewire and device guidance, we have investigated the reproducibility of the final paths of the guidewire in vessel phantom models on different factors: user, materials and geometry. Three vessel phantoms (vessel diameters ?4 mm) were constructed having tortuousity similar to the internal carotid artery from silicon tubing and encased in Sylgard elastomer. Several trained users repeatedly passed two guidewires of different flexibility through the phantoms under pulsatile flow conditions. After the guidewire had been placed, rotational c-arm image sequences were acquired (9 in. II mode, 0.185 mm pixel size), and the phantom and guidewire were reconstructed (5123, 0.288 mm voxel size). The reconstructed volumes were aligned. The centerlines of the guidewire and the phantom vessel were then determined using region-growing techniques. Guidewire paths appear similar across users but not across materials. The average root mean square difference of the repeated placement was 0.17±0.02 mm (plastic-coated guidewire), 0.73±0.55 mm (steel guidewire) and 1.15±0.65 mm (steel versus plastic-coated). For a given guidewire, these results indicate that the guidewire path is relatively reproducible in shape and position.

Schafer, Sebastian; Hoffmann, Kenneth R.; Noel, Peter B.; Ionita, Ciprian N.; Dmochowski, Jacek

2008-01-01

413

Evaluation of guidewire path reproducibility.  

PubMed

The number of minimally invasive vascular interventions is increasing. In these interventions, a variety of devices are directed to and placed at the site of intervention. The device used in almost all of these interventions is the guidewire, acting as a monorail for all devices which are delivered to the intervention site. However, even with the guidewire in place, clinicians still experience difficulties during the interventions. As a first step toward understanding these difficulties and facilitating guidewire and device guidance, we have investigated the reproducibility of the final paths of the guidewire in vessel phantom models on different factors: user, materials and geometry. Three vessel phantoms (vessel diameters approximately 4 mm) were constructed having tortuousity similar to the internal carotid artery from silicon tubing and encased in Sylgard elastomer. Several trained users repeatedly passed two guidewires of different flexibility through the phantoms under pulsatile flow conditions. After the guidewire had been placed, rotational c-arm image sequences were acquired (9 in. II mode, 0.185 mm pixel size), and the phantom and guidewire were reconstructed (512(3), 0.288 mm voxel size). The reconstructed volumes were aligned. The centerlines of the guidewire and the phantom vessel were then determined using region-growing techniques. Guidewire paths appear similar across users but not across materials. The average root mean square difference of the repeated placement was 0.17 +/- 0.02 mm (plastic-coated guidewire), 0.73 +/- 0.55 mm (steel guidewire) and 1.15 +/- 0.65 mm (steel versus plastic-coated). For a given guidewire, these results indicate that the guidewire path is relatively reproducible in shape and position. PMID:18561663

Schafer, Sebastian; Hoffmann, Kenneth R; Noël, Peter B; Ionita, Ciprian N; Dmochowski, Jacek

2008-05-01

414

A gain-scheduling approach for airship path-tracking  

Microsoft Academic Search

In this chapter a gain scheduled optimal controller is designed to solve the path-tracking problem of an airship. The control\\u000a law is obtained from a coupled linear model of the airship that allows to control the longitudinal and lateral motions simultaneously.\\u000a Due to the importance of taking into account wind effects, which are rather important due to the airship large

Alexandra Moutinho; José Raul Azinheira

2006-01-01

415

A path to integration in an academic health science center.  

PubMed Central

This article describes a networking and integration strategy in use at the University of Michigan Medical Center. This strategy builds upon the existing technology base and is designed to provide a roadmap that will direct short-term development along a productive, long-term path. It offers a way to permit the short-term development of incremental solutions to current problems while at the same time maximizing the likelihood that these incremental efforts can be recycled into a more comprehensive approach.

Panko, W. B.; Wilson, W.

1992-01-01

416

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

417

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

418

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

419

Limited-path-length entanglement percolation in quantum complex networks  

NASA Astrophysics Data System (ADS)

We study entanglement distribution in quantum complex networks where nodes are connected by bipartite entangled states. These networks are characterized by a complex structure, which dramatically affects how information is transmitted through them. For pure quantum state links, quantum networks exhibit a remarkable feature absent in classical networks: it is possible to effectively rewire the network by performing local operations on the nodes. We propose a family of such quantum operations that decrease the entanglement percolation threshold of the network and increase the size of the giant connected component. We provide analytic results for complex networks with an arbitrary (uncorrelated) degree distribution. These results are in good agreement with numerical simulations, which also show enhancement in correlated and real-world networks. The proposed quantum preprocessing strategies are not robust in the presence of noise. However, even when the links consist of (noisy) mixed-state links, one can send quantum information through a connecting path with a fidelity that decreases with the path length. In this noisy scenario, complex networks offer a clear advantage over regular lattices, namely, the fact that two arbitrary nodes can be connected through a relatively small number of steps, known as the small-world effect. We calculate the probability that two arbitrary nodes in the network can successfully communicate with a fidelity above a given threshold. This amounts to working out the classical problem of percolation with a limited path length. We find that this probability can be significant even for paths limited to few connections and that the results for standard (unlimited) percolation are soon recovered if the path length exceeds by a finite amount the average path length, which in complex networks generally scales logarithmically with the size of the network.

Cuquet, Martí; Calsamiglia, John

2011-03-01

420

[Botulinum toxin: the misguided path].  

PubMed

Botulinum toxin is widely used and has become a popular mass phenomenon in aesthetic medicine. Considerable scientific data concerning the biopsychosocial impact of botulinum toxin use have become available. The bidirectional interaction of mimic and emotion, described as the facial feedback hypothesis, is particularly influenced, as is mimicry. Furthermore, botulinum toxin can cause dysfunction of face harmony including false laughing or the "frozen face". As a result, complex psychosocial disturbances can occur and may affect social interaction and cause flattening of affect. Thus one must ask whether in the future botulinum toxin will continue to be employed in aesthetic dermatology or perhaps be regarded as a misguided path. PMID:23636411

Harth, W

2013-06-01

421

Paths to adolescent parenthood: implications for prevention.  

PubMed Central

Adolescent pregnancy and parenthood are increasingly common today and pose many problems for both the individual persons involved and society as a whole. For programs to address these issues successfully, factors associated with unintended pregnancy and resulting parenthood must first be identified and understood. This paper is a review of current research on the factors associated with the four steps leading to an adolescent becoming a parent. Being an adolescent parent requires taking a particular path at four crossroads: becoming sexually active, not using or incorrectly using contraceptives, carrying rather than aborting a pregnancy, and parenting rather than placing a child for adoption. Much research in the last 15 years has explored adolescent childbearing, but many studies only compared adolescent parents to nonparents to reach conclusions about differences in these groups. This review focuses on recent studies that explore the four processes, or crossroads, separately and it excludes studies that generalize and overlap these processes. Factors that influence adolescent behavior at multiple points on the path to parenthood indicate areas particularly relevant for preventive intervention. For instance, boyfriends exert influence at all four crossroads. Sexual activity and contraceptive use increase with longevity of relationships, yet closer relationships are less often associated with raising a child. Better general communication skills, and particularly an increased ability to discuss sexuality, increases use of contraceptives, and low educational and occupational aspirations appear to influence each successive turn toward parenthood. This summary of current research serves to highlight those individual, family, dyadic, and social factors that exert great impact on adolescent parenthood by influencing young people at each of the four crossroads. These factors suggest potentially effective points for intervention to reduce the incidence of adolescent parenthood. However, poverty, unemployment, and racism also play central roles in early intercourse and childbearing, and any attempt at fundamental change must take these forces into account.

Flick, L H

1986-01-01

422

Path integration: effect of curved path complexity and sensory system on blindfolded walking.  

PubMed

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

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

2012-07-27

423

Beyond centrality—classifying topological significance using backup efficiency and alternative paths  

NASA Astrophysics Data System (ADS)

In complex networks characterized by broad degree distribution, node significance is often associated with its degree or with centrality metrics which relate to its reachability and shortest paths passing through it. Such measures do not consider availability of efficient backup of the node and thus often fail to capture its contribution to the functionality and resilience of the network operation. In this paper, we suggest the quality of backup (QoB) and alternative path centrality (APC) measures as complementary methods which enable analysis of node significance in a manner which considers backup. We examine the theoretical significance of these measures and use them to classify nodes in social interaction networks and in the Internet AS (autonomous system) graph while applying the valley-free routing restrictions which reflect the economic relationships between the AS nodes in the Internet. We show that both node degree and node centrality are not necessarily evidence of its significance. In particular, we show that social structures do not necessarily depend on highly central nodes and that medium degree nodes with medium centrality measure prove to be crucial for efficient routing in the Internet AS graph. Partial results presented in this paper also appear in the IFIP NETWORKING 2007 Conference.

Shavitt, Yuval; Singer, Yaron

2007-08-01

424

Challenge in Flow Path Delineation and Modification: SECUREarth Initiative  

NASA Astrophysics Data System (ADS)

After decades of studies, our knowledge about subsurface flow paths has large uncertainty and our capability to enhance or reduce formation permeability is inefficient and rudimentary. This is the case for fossil energy production, in environment remediation, in greenhouse gas sequestration, in nuclear waste disposal, in geothermal heat extraction, and in groundwater management. Fluid imaging, in addition to rock structure imaging, is needed to enhance petroleum extraction, to isolate contaminant plumes, and to prevent leakage from storage reservoirs. Flow focusing from surface to depth must be quantified to determine the flow path magnitude and spacing in order to determine the degrees of dissolution and transport of emplaced wastes. These diverse problems have common goals: either to isolate or to enhance subsurface fluid movement. It is crucial to identify the common features from different problems and refocus our efforts to delineate and then to manipulate flow paths. Geochemical engineering and geomicrobiological engineering need to combine laboratory studies, field experiments, and modeling approaches to verify and validate our understanding and to design solutions. An initiative SECUREarth is being developed to rally the scientists and engineers from national laboratories, universities, and industry to address key critical bottlenecks that prevent significant progress in solving common subsurface issues. SECUREarth is aimed to develop cross-cutting, multi-disciplinary approaches for solving urgent energy and environment problems in the earth, in order to achieve quantum leaps and breakthroughs in earth science and technology.

Bodvarsson, G. S.; Majer, E. L.; Wang, J. S.; Colwell, F.; Redden, G.

2005-12-01

425

A path integral approach to data assimilation in stochastic nonlinear systems  

NASA Astrophysics Data System (ADS)

In this dissertation the problem of data assimilation in stochastic nonlinear systems is formulated using path integrals. Each path represents a time evolution of the model states, and the time independent model parameters. In the path integral, every possible path is integrated over with each path weighted by P(X?Y) ? exp[--A 0(X,Y)], where A0(X,Y ) is the action, which quantifies how likely it is that the given path X was actually realized in the experiment which produced the observed time series Y. The goal of data assimilation is to combine information from a measurement time series with a dynamical model to make statistical estimates or predictions of model states and parameters. Both the measurements and the dynamical model may be noisy, and this fact is incorporated by using a probabilistic formulation for P(X?Y), the posterior path distribution conditioned on the observed time series. With an expression for P(X?Y) it is possible to express expectation values, conditioned upon the observations, of any function of the path as a path integral over all possible paths. The path integrals can then be numerically approximated using a Markov chain Monte Carlo method such as the Metropolis method. This method is discussed and applied to two example systems: the Colpitts oscillator circuit, and the Lorenz 96 toy atmosphere model. By studying the characteristics of the action as a function of the path, properties of the data assimilation problem can be deduced. For instance, if the surface in path space defined by the action is rough with many local minima with similar values of action, then the data assimilation problem is not well-defined. If more observations are made which rule out regions of path space that were previously likely, then the surface may become smoother with a single minimum. By examining the shape of the action, the question of how many measurements are needed to fully reconstruct the model state can be answered. It is also important to examine the shape of the action in the vicinity of the global minimum to find the level of uncertainty in state and parameter estimates. These ideas are illustrated with the Lorenz 96 system as an example.

Quinn, John C.

426

Optimum gradient of mountain paths.  

PubMed

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

Minetti, A E

1995-11-01

427

From Restricted Path Consistency to Max-Restricted Path Consistency  

Microsoft Academic Search

There is no need to show the importance of the filtering techniques to solve constraint satisfaction problems i.e. to find values for problem variables subject to constraints that specify which combinations of values are consistent. They can be used during a preprocessing step to remove once and for all some local inconsistencies, or during the search to efficiently prune the

Romuald Debruyne; Christian Bessière

1997-01-01

428

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

429

Path Integral for Dirac Particle in Plane Wave Field  

NASA Astrophysics Data System (ADS)

The problem of a relativistic spinning particle in interaction with an electromagnetic plane wave field is treated via path integrals. The dynamics of the spin of the particle is described using the supersymmetric action proposed by Fradkin and Gitman. The problem has been solved by using two identities, one bosonic and the other fermionic, which are related directly to the classical equations of motion. The exact expression of the relative Green's function is given and the result agrees with those of the literature. Further, the suitably normalized wave functions are also extracted.

Zeggari, S.; Boudjedaa, T.; Chetouani, L.

430

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

431

Path tracking control of a manipulator with passive joints  

Microsoft Academic Search

A method is proposed of path tracking control of a manipulator with passive joints, i.e. having no actuators. A desired path is geometrically specified in operational space. The position of the manipulator is controlled to follow the desired path. In this method, a path coordinate system based on the desired path is defined in operational space. The path coordinates consist

Hirohiko ARAI; Kazuo TANIE; Susumu TACHI

1991-01-01

432

Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph  

Microsoft Academic Search

^SSTnXcr. Gwen a graph G = (V, E) and four verttces s~, tx, s~, and t2, the problem of finding two disjoint paths, P~ from s~ to tt and P2 from s2 to t2, is considered This problem may arise as a transportation network problem and m printed clrcmts routing The relations between several vemons of the problem are discussed

Y. Shiloach; Y. Perl

1978-01-01

433

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

434

Sequential path entanglement for quantum metrology.  

PubMed

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

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

2013-01-01

435

Sequential Path Entanglement for Quantum Metrology  

NASA Astrophysics Data System (ADS)

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

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

2013-05-01

436

Semiclassical series from path integrals  

SciTech Connect

We derive the semiclassical series for the partition function in Quantum Statistical Mechanics (QSM) from its path integral representation. Each term of the series is obtained explicitly from the (real) minima of the classical action. The method yields a simple derivation of the exact result for the harmonic oscillator, and an accurate estimate of ground-state energy and specific heat for a single-well quartic anharmonic oscillator. As QSM can be regarded as finite temperature field theory at a point, we make use of the field-theoretic language of Feynman diagrams to illustrate the non-perturbative character of the series: it contains all powers of ({Dirac_h}/2{pi}) and graphs with any number of loops; the usual perturbative series corresponds to a subset of the diagrams of the semiclassical series. We comment on the application of our results to other potentials, to correlation functions and to field theories in higher dimensions.

Carvalho, C. A. A. de; Cavalcanti, R. M. [Instituto de Fisica, Universidade Federal do Rio de Janeiro, Cx. Postal 68528, CEP 21945-970, Rio de Janeiro, RJ (Brazil); Institute for Theoretical Physics, University of California, Santa Barbara, California 93106-4030 (United States)

1999-07-13

437

The path to adaptive microsystems  

NASA Astrophysics Data System (ADS)

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 these systems-on-a-chip. The role of DARPA in advancing future components and systems research is discussed, and specific DARPA efforts enabling and producing adaptive microsystems are presented. In particular, we discuss efforts underway in the DARPA Microsystems Technology Office (MTO) including programs in novel circuit architectures (3DIC), adaptive imaging and sensing (AFPA, VISA, MONTAGE, A-to-I) and reconfigurable RF/Microwave devices (SMART, TFAST, IRFFE).

Zolper, John C.; Biercuk, Michael J.

2006-06-01

438

Slant path atmospheric extinction measurements  

NASA Astrophysics Data System (ADS)

A commercial Fourier transform spectrometer is being used to collect 0.06/cm 2-14-micron slant path atmospheric spectra using the sun as the source of radiation. Using a Lambert plot approach, 10-15 spectra are collected at different air masses. The logarithm of the intensity versus air mass is used to calculate the extinctance for the atmosphere at arbitrary frequencies within the bandwidth. Over the past three years, spectra have been collected on over 120 days at White Sands Missile Range, NM. Up to a factor of ten variation in the atmospheric extinction is observed at many CO2 laser frequencies which correlate with atmospheric water vapor measurements. Variations in the atmospheric extinction for DF frequencies are smaller and do not correlate with the water vapor measurements.

Gutman, W. M.; Hanley, S. T.; Walters, D. L.

1981-01-01

439

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

440

ANALYSIS OF CROSSING PATH CRASH COUNTERMEASURE SYSTEMS  

Microsoft Academic Search

This paper summarizes the results of an analysis of promising countermeasure systems for crossing path crashes, and thus provides a foundation for setting research priorities under the United States (U.S.) Department of Transportation's Intelligent Vehicle Initiative. Crossing path crashes involve one moving vehicle cutting across the path of another, which amounted to 1.72 million police-reported crashes in the U.S. based

Wassim G. Najm; Jonathan A. Koopmann; David L. Smith

441

Optimizing Regular Path Expressions Using Graph Schemas  

Microsoft Academic Search

Several languages, such as LOREL and UnQL, support querying of semi-structured data. Others, such as WebSQL and WebLog, query Web sites. All these languages model data as labeled graphs and use regular path expressions to express queries that traverse arbitrary paths in graphs. Naive execution of path expressions is inefficient, however, because it often requires exhaustive graph search. We describe

Mary F. Fernandez; Dan Suciu

1998-01-01

442

Applications of Visible Light Path Laser Projector  

Microsoft Academic Search

We proposed and developed a method to visualize the light path of a laser with jetting mists along light axis of a laser pointer.\\u000a The estimation accuracy for the position of a laser spot occluded behind an object was improved when the light path of the\\u000a laser was visualized. In this paper, we propose visible light path laser projector (VLLP)

Nobuchika Sakata; Shu Okamoto; Shogo Nishida

2009-01-01

443

Possible connection between the optimal path and flow in percolation clusters  

NASA Astrophysics Data System (ADS)

We study the behavior of the optimal path between two sites separated by a distance r on a d -dimensional lattice of linear size L with weight assigned to each site. We focus on the strong disorder limit, i.e., when the weight of a single site dominates the sum of the weights along each path. We calculate the probability distribution P(?opt?r,L) of the optimal path length ?opt , and find for r?L a power-law decay with ?opt , characterized by exponent gopt . We determine the scaling form of P(?opt?r,L) in two- and three-dimensional lattices. To test the conjecture that the optimal paths in strong disorder and flow in percolation clusters belong to the same universality class, we study the tracer path length ?tr of tracers inside percolation through their probability distribution P(?tr?r,L) . We find that, because the optimal path is not constrained to belong to a percolation cluster, the two problems are different. However, by constraining the optimal paths to remain inside the percolation clusters in analogy to tracers in percolation, the two problems exhibit similar scaling properties.

López, Eduardo; Buldyrev, Sergey V.; Braunstein, Lidia A.; Havlin, Shlomo; Stanley, H. Eugene

2005-11-01

444

Simultaneous computation of seismic slowness paths and the traveltime field in anisotropic media  

NASA Astrophysics Data System (ADS)

This paper presents a novel system for computing seismic slowness paths and the traveltime field simultaneously in anisotropic media, in which the ray path concept is replaced with the concept of slowness paths. Like ray paths in isotropic media, slowness paths are orthogonal to the wave fronts in anisotropic media. The novelty of the proposed system relies on the explicit normal constraint that slowness vectors are perpendicular to wave fronts. While the system finds the positions of sequential wave fronts with a constant time interval, samples of consecutive wave fronts represent slowness paths which are normal to wave fronts and follow phase velocities in anisotropic media. The simultaneous calculation can remove any shadow zones where paths might fail to emerge by path-tracing and meanwhile avoid the instability problem in conventional eikonal-equation solution for traveltimes. While any differential discontinuity (such as cusps in a wave front) causes numerical instability, it is dealt with by a least-squares smoothing strategy along the wave front. The feasibility is demonstrated using numerical examples from simple to realistic anisotropic models.

Wang, Yanghua

2013-11-01

445

A Direct Path Interference Cancellation Approach to Passive Radar Based on FM Radio transmitter  

Microsoft Academic Search

Target detection by non-cooperative illuminator is a research hotspot in electronic warfare field, with four countering' potential advantages. One of the major problems in bistatic radars with continuous waves is the direct path interference (DPI). The conventional solution to this problem is to use an adaptive antenna by steering null towards the interference. Unfortunately the null depth obtained by this

Zhu Jiabing; Tao Liang; Hong Yi

2006-01-01

446

Combining Search and Analogical Reasoning in Path Planning from Road Maps  

Microsoft Academic Search

Path planning from road maps is a task that may involve multiple goal interactions and multiple ways of achieving a goal. This prob- lem is recognized as a difficult problem solv- ing task. In this domain it is particularly in- teresting to explore learning techniques that can improve the problem solver's efficiency both at plan generation and plan execution. We

Karen Haigh; Manuela Veloso

1993-01-01

447

Ensuring critical event sequences in high integrity software by applying path expressions  

SciTech Connect

The goal of this work is to extend the use of existing path expression theory and methodologies to ensure that critical software event sequences are maintained even in the face of malevolent attacks and harsh or unstable operating environments. This will be accomplished by providing dynamic fault management measures directly to the software developer and to their varied development environments. This paper discusses the perceived problems, a brief overview of path expressions, and the author`s proposed extension areas. The authors discuss how the traditional path expression usage and implementation differs from the intended usage and implementation.

Kidd, M.E.C.

1996-07-01

448

Ensuring critical event sequences in high consequence computer based systems as inspired by path expressions  

SciTech Connect

The goal of our work is to provide a high level of confidence that critical software driven event sequences are maintained in the face of hardware failures, malevolent attacks and harsh or unstable operating environments. This will be accomplished by providing dynamic fault management measures directly to the software developer and to their varied development environments. The methodology employed here is inspired by previous work in path expressions. This paper discusses the perceived problems, a brief overview of path expressions, the proposed methods, and a discussion of the differences between the proposed methods and traditional path expression usage and implementation.

Kidd, M.E.C.

1997-02-01

449

Perturbative or Path-Integral Approach versus Operator-Formalism Approach  

NASA Astrophysics Data System (ADS)

In conformal-gauge two-dimensional quantum gravity, the solution obtained using the perturbative or path-integral approach is compared with that obtained using the operator-formalism approach. The treatments of the anomaly problem in the two approaches are different. This difference is found to be essentially caused by the fact that the perturbative or path-integral approach is based on the T*-product (covariantized T-product), which generally violates field equations. Indeed, this fact induces some extra one-loop Feynman diagrams, which would not exist unless a nonzero contribution arose from a zero field. Some demerits of the path-integral approach are explicitly demonstrated.

Abe, M.; Nakanishi, N.

1999-12-01

450

Preventive Intervention for School-Age Deaf Children: The PATHS Curriculum  

Microsoft Academic Search

This study examined the effectiveness of the PATHS (Pro- moting Alternative THinking Strategies) Curriculum on the social, cognitive, and behavioral status of elementary school- age deaf children. PATHS, a school-based preventive in- tervention model, was designed to improve children's self- control, emotional understanding, and problem-solving skills. The intervention field trial included a quasi-experime ntal, wait-list control design involving 57 children

Mark T. Greenberg

1998-01-01

451

Treewidth and Path-width of Comparability Graphs of interval Orders  

Microsoft Academic Search

The problem to decide whether the tree-width of a comparability graph is less than k is NP-complete, if k is part of the input. We prove that the tree-width of comparability graphs of interval orders can be determined in linear time and that it equals the path-width of the graph. Our proof is constructive, i.e., we give an explicit path

Renate Garbe

1994-01-01

452

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

453

Elastic Optical Path Network Architecture: Framework for Spectrally-Efficient and Scalable Future Optical Networks  

NASA Astrophysics Data System (ADS)

This paper presents an elastic optical path network architecture as a novel networking framework to address the looming capacity crunch problem in internet protocol (IP) and optical networks. The basic idea is to introduce elasticity and adaptation into the optical domain to yield spectrally-efficient optical path accommodation, heightened network scalability through IP traffic offloading to the elastic optical layer, and enhanced survivability for serious disasters.

Jinno, Masahiko; Takara, Hidehiko; Sone, Yoshiaki; Yonenaga, Kazushige; Hirano, Akira

454

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

455

Triple RRTs: An Effective Method for Path Planning in Narrow Passages  

Microsoft Academic Search

Although Rapidly-exploring Random Trees (RRTs) have been successfully applied in path planning of robots with many degrees of freedom under non-holonomic and differential constraints, rapidly identifying and passing through narrow passages in a robot's configuration space remains a challenge for RRTs-based planners. This paper presents a novel two-stage approach to address the problem of multi-d.o.f. robot path planning in high-dimensional

Wei Wang; Xin Xu; Yan Li; Jinze Song; Hangen He

2010-01-01

456

Polynomial Time Approximations for MultiPath Routing with Bandwidth and Delay Constraints  

Microsoft Academic Search

ó In this paper, we study the problem of multi-path routing with bandwidth and delay constraints, which arises in applications for video delivery over bandwidth-limited networks. Assume that each link in the network has a bandwidth and a delay. For a given source-destination pair and a bandwidth requirement, we want to nd a set of source to destination paths such

Satyajayant Misra; Guoliang Xue; Dejun Yang

2009-01-01

457

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

458

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

459

A HYBRID LAGRANGEAN HEURISTIC WITH GRASP AND PATH-RELINKING FOR SET K-COVERING  

Microsoft Academic Search

The set k-covering problem is an extension of the set covering pro- blem, in which each object has to be covered at least k times. We describe a GRASP with path-relinking heuristic for its solution, as well as the template of a family of Lagrangean heuristics. The hybrid GRASP Lagrangean heuristic employs the GRASP with path-relinking heuristic using modified costs

LUCIANA S. PESSOA; MAURICIO G. C. RESENDE; CELSO C. RIBEIRO

460

Obstacle Bypassing in Optimal Ship Routing Using Simulated Annealing  

SciTech Connect

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

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

2008-11-06

461

Validation of the reaction thermodynamics associated with NaSc(BH4)4 from first-principles calculations: Detecting metastable paths and identifying the minimum free energy path  

NASA Astrophysics Data System (ADS)

A critical drawback with first-principles thermodynamic calculations is the absence of the vibrational and entropic contributions to the prediction of reaction mechanisms, which could conclusively show that the predicted reaction mechanism might be not the most stable reaction path. This study focused on providing an answer to this problem by examining possible metastable paths for five reactant mixtures whose reaction mechanisms were previously predicted using first-principles thermodynamic calculations. The aim of this study was to find a minimum free energy path among all the possible paths of each reactant mixture. This effort provided the clear conclusion that the original reaction paths predicted from first-principles thermodynamic calculations were the most stable reaction paths at an appropriate H2 pressure range for all cases. An additional examination associated with density functional theory uncertainty suggests how the ambiguity of reaction mechanisms predicted based on thermodynamic calculations should be understood and dealt with.

Kim, Ki Chul

2012-08-01

462

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

463

GRASP for set packing problems  

Microsoft Academic Search

The principles of the Greedy Randomized Adaptative Search Procedure (GRASP) metaheuristic are instantiated for the set packing problem. We investigated several construction phases, and evaluated improvements based on advanced strategies. These improvements include a self-tuning procedure (using reactive GRASP), an intensification procedure (using path relinking) and a procedure involving the diversification of the selection (using a learning process). Two sets

Xavier Delorme; Xavier Gandibleux; Joaquin Rodriguez

2004-01-01

464

Path planning and path tracking control of unmanned ground vehicles (UGVs)  

Microsoft Academic Search

Unmanned ground vehicles (UGVs) will be playing increasingly important role in the future battlefields. How to automatically guide and control UGVs under varying environment conditions represents a challenging issue. This paper presents a novel approach to achieving path planning and path tracking of UGVs under dynamic environments. We apply the topology theory to find the optimal path given any starting

Liguo Weng; D. Y. Song

2005-01-01

465

Vacuum stress and closed paths in rectangles, pistons and pistols  

NASA Astrophysics Data System (ADS)

Rectangular cavities are solvable models that nevertheless touch on many of the controversial or mysterious aspects of the vacuum energy of quantum fields. This paper is a thorough study of the two-dimensional scalar field in a rectangle by the method of images, or closed classical (or optical) paths, which is exact in this case. For each point r and each specularly reflecting path beginning and ending at r, we provide formulae for all components of the stress tensor T??(r), for all values of the curvature coupling constant ? and all values of an ultraviolet cutoff parameter. Arbitrary combinations of Dirichlet and Neumann conditions on the four sides can be treated. The total energy is also investigated, path by path. These results are used in an attempt to clarify the physical reality of the repulsive (outward) force on the sides of the box predicted by calculations that neglect both boundary divergences and the exterior of the box. Previous authors have studied 'piston' geometries that avoid these problems and have found the force to be attractive. We consider a 'pistol' geometry that comes closer to the original problem of a box with a movable lid. We find again an attractive force, although its origin and detailed behavior are somewhat different from the piston case. However, the pistol (and the piston) model can be criticized for extending idealized boundary conditions into short distances where they are physically implausible. Therefore, it is of interest to see whether leaving the ultraviolet cutoff finite yields results that are more plausible. We then find that the force depends strongly on a geometrical parameter; it can be made repulsive, but only by forcing that parameter into the regime where the model is least convincing physically.

Fulling, S. A.; Kaplan, L.; Kirsten, K.; Liu, Z. H.; Milton, K. A.

2009-04-01

466

Path-Goal Theory of Leadership.  

National Technical Information Service (NTIS)

The paper reviews the path-goal theory of leadership. This theory states that a leader's behavior is important for good performance as a function of its impact on subordinates' perceptions of paths to goals and the attractiveness of the goals. When leader...

R. J. House T. R. Mitchell

1975-01-01

467

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

468

Ray path deviation in a nonhemispherical dome  

Microsoft Academic Search

A calculation is presented for meridional rays of the ray path deviation in a conformal dome in which both the shape of the inner and outer surfaces are specified in detail so as to examine under what conditions the ray path deviation might be minimized by independently adjusting the shape of the inner surface. Specific results are given for the

Richard I. Joseph; Michael E. Thomas

2001-01-01

469

Adaptively Ubiquitous Learning in Campus Math Path  

ERIC Educational Resources Information Center

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

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

2012-01-01

470

Modeling Robot Path Planning with CD  

Microsoft Academic Search

Robotic systems are usually built as independent a gents that collaborate to accomplish a specific task. Analysis of robot path planning consists of route plan- ning and path generation. We will show how to apply the Cell-DEVS formalism and the CD++ toolkit for these tasks. We present a Cell -DEVS model for route planning, which, based on the obstacles, finds

Gabriel A. Wainer

2006-01-01

471

Hausdorff Dimension of Operator Stable Sample Paths  

Microsoft Academic Search

The Hausdorff dimension of the sample paths of a stochastic process with stationary independent operator stable increments is computed. With probability one, every sample path has the same dimension, depending on the real parts of the eigenvalues of the operator stable exponent.

Peter Becker-Kern; Mark M. Meerschaert; Hans-Peter Scheffler

2003-01-01

472

Bounding the error of path loss models  

Microsoft Academic Search

In this paper we analyze the efficacy of basic path loss models at predicting median path loss in urban environments. We attempt to bound the practical error of these models and look at how they may hinder practical wireless applications, and in particular dynamic spectrum access networks. This analysis is made using a large set of measurements from production networks

Caleb Phillips; Douglas Sicker; Dirk Grunwald

2011-01-01

473

Diversion path analysis handbook. Volume I. Methodology  

Microsoft Academic Search

Diversion Path Analysis (DPA) is a procedure for analyzing internal controls of a facility in order to identify vulnerabilities to successful diversion of material by an adversary. The internal covert threat is addressed but the results are also applicable to the external overt threat. The diversion paths are identified. Complexity parameters include records alteration or falsification, multiple removals of sub-threshold

M. D. K. Maltese; K. E. Goodwin; J. C. Schleter

1976-01-01

474

Judgments of path, not heading, guide locomotion.  

PubMed

To steer a course through the world, people are almost entirely dependent on visual information, of which a key component is optic flow. In many models of locomotion, heading is described as the fundamental control variable; however, it has also been shown that fixating points along or near one's future path could be the basis of an efficient control solution. Here, the authors aim to establish how well observers can pinpoint instantaneous heading and path, by measuring their accuracy when looking at these features while traveling along straight and curved paths. The results showed that observers could identify both heading and path accurately (approximately 3 degrees ) when traveling along straight paths, but on curved paths they were more accurate at identifying a point on their future path (approximately 5 degrees ) than indicating their instantaneous heading (approximately 13 degrees ). Furthermore, whereas participants could track changes in the tightness of their path, they were unable to accurately track the rate of change of heading. In light of these results, the authors suggest it is unlikely that heading is primarily used by the visual system to support active steering. PMID:16478328

Wilkie, Richard M; Wann, John P

2006-02-01

475

Reducing power with dynamic critical path information  

Microsoft Academic Search

Recent research has shown that dynamic information regarding instruction criticality can be used to increase microprocessor performance. Critical path information can also be used in processors to achieve a better balance of power and performance. This paper uses the output of a dynamic critical path predictor to decrease the power consumption of key portions of the processor without incurring a

John S. Seng; Eric S. Tune; Dean M. Tullsen

2001-01-01

476

Analysis of probabilistic roadmaps for path planning  

Microsoft Academic Search

We provide an analysis of a path planning method which uses probabilistic roadmaps. This method has proven very successful in practice, but the theoretical understanding of its performance is still limited. Assuming that a path ? exists between two configurations a and b of the robot, we study the dependence of the failure probability to connect a and b, on:

Lydia E. Kavraki; Mihail N. Kolountzakis; Jean-claude Latombe

1998-01-01

477

Path Integrals in Lattice Quantum Chromodynamics  

NASA Astrophysics Data System (ADS)

I discuss the use of path integrals to study strong-interaction physics from first principles. The underlying theory is cast into path integrals which are evaluated numerically using Monte Carlo methods on a space-time lattice. Examples are given in progress made in nuclear physics.

Lee, F. X.

2008-11-01

478

Fatigue failure paths for offshore platform inspection  

Microsoft Academic Search

A closed- form, reliability-based procedure is developed to identify fatigue failure paths of offshore structures and assess the notional probability of system failure through these paths. The procedure utilizes the Miners rule node fatigue failure reliability model developed by Wirsching. Effects of load redistribution following the fatigue failure of a node on the time to failure of remaining unfailed nodes

Demir I. Karsan; Ashok Kumar

1990-01-01

479

The path dependence of deformation texture development  

SciTech Connect

It is demonstrated for the case of three different strain paths, all of which end up with the same, elongated specimen shape, that the texture developed during straining is path dependent. This is true both for experiments on aluminum polycrystals and for simulations using the LApp code.

Takeshita, T.; Kocks, U.F.; Wenk, H.R.

1987-01-01

480

Evaluation of Calcine Disposition Path Forward  

SciTech Connect

This document describes an evaluation of the baseline and two alternative disposition paths for the final disposition of the calcine wastes stored at the Idaho Nuclear Technology and Engineering Center at the Idaho National Engineering and Environmental Laboratory. The pathways are evaluated against a prescribed set of criteria and a recommendation is made for the path forward.

Birrer, S.A.; Heiser, M.B.

2003-02-26

481

Evaluation of Calcine Disposition - Path Forward  

SciTech Connect

This document describes an evaluation of the baseline and two alternative disposition paths for the final disposition of the calcine wastes stored at the Idaho Nuclear Technology and Engineering Center at the Idaho National Engineering and Environmental Laboratory. The pathways are evaluated against a prescribed set of criteria and a recommendation is made for the path forward.

Steve Birrer

2003-02-01

482

White Noise Path Integrals in Stochastic Neurodynamics  

NASA Astrophysics Data System (ADS)

The white noise path integral approach is used in stochastic modeling of neural activity, where the primary dynamical variables are the relative membrane potentials, while information on transmembrane ionic currents is contained in the drift coefficient. The white noise path integral allows a natural framework and can be evaluated explicitly to yield a closed form for the conditional probability density.

Carpio-Bernido, M. Victoria; Bernido, Christopher C.

2008-06-01

483

Bergman Kernel from Path Integral  

NASA Astrophysics Data System (ADS)

We rederive the expansion of the Bergman kernel on Kähler manifolds developed by Tian, Yau, Zelditch, Lu and Catlin, using path integral and perturbation theory, and generalize it to supersymmetric quantum mechanics. One physics interpretation of this result is as an expansion of the projector of wave functions on the lowest Landau level, in the special case that the magnetic field is proportional to the Kähler form. This is relevant for the quantum Hall effect in curved space, and for its higher dimensional generalizations. Other applications include the theory of coherent states, the study of balanced metrics, noncommutative field theory, and a conjecture on metrics in black hole backgrounds discussed in [24]. We give a short overview of these various topics. From a conceptual point of view, this expansion is noteworthy as it is a geometric expansion, somewhat similar to the DeWitt-Seeley-Gilkey et al short time expansion for the heat kernel, but in this case describing the long time limit, without depending on supersymmetry.

Douglas, Michael R.; Klevtsov, Semyon

2010-01-01

484

Dynamics of dielectric breakdown paths.  

PubMed

We investigate the dynamics and geometry of dielectric breakdown paths of needle defects of arbitrary residual resistivity in an otherwise homogeneous medium using a time-dependent electrical-circuit model. The circuit model consists of a semi-infinite lattice of capacitors in parallel with resistors that break down to a lower (residual) resistance. The breakdown occurs if the local field across a resistor exceeds a critical value for a breakdown delay time. We consider cases where the initial resistance is infinite or finite and where the residual resistance is finite or zero. We consider the model for the case where the applied field reaches the critical value adiabatically. We find that, as in the quasistatic case, the breakdown grows either one dimensionally or spreads with a fractal dimension (bifurcates) depending on the values of residual resistance and breakdown delay time. Also, we find that the propagation velocity of the needle oscillates spontaneously. We give the phase diagram for bifurcation and oscillations. We derive a simplified recursive map approximation to explain this behavior. PMID:16241371

Boksiner, Jeffrey; Leath, P L

2003-06-27

485

Path integral for inflationary perturbations  

NASA Astrophysics Data System (ADS)

The quantum theory of cosmological perturbations in single-field inflation is formulated in terms of a path integral. Starting from a canonical formulation, we show how the free propagators can be obtained from the well-known gauge-invariant quadratic action for scalar and tensor perturbations, and determine the interactions to arbitrary order. This approach does not require the explicit solution of the energy and momentum constraints, a novel feature which simplifies the determination of the interaction vertices. The constraints and the necessary imposition of gauge conditions is reflected in the appearance of various commuting and anticommuting auxiliary fields in the action. These auxiliary fields are not propagating physical degrees of freedom but need to be included in internal lines and loops in a diagrammatic expansion. To illustrate the formalism we discuss the tree-level three-point and four-point functions of the inflaton perturbations, reproducing the results already obtained by the methods used in the current literature. Loop calculations are left for future work.

Prokopec, Tomislav; Rigopoulos, Gerasimos

2010-07-01

486

The Path of Human Evolution  

NASA Astrophysics Data System (ADS)

A complex series of evolutionary steps, contingent upon a dynamic environmental context and a long biological heritage, have led to the ascent of Homo sapiens as a dominant component of the modern biosphere. In a field where missing links still abound and new discoveries regularly overturn theoretical paradigms, our understanding of the path of human evolution has made tremendous advances in recent years. Two major trends characterize the development of the hominin clade subsequent to its origins with the advent of upright bipedalism in the Late Miocene of Africa. One is a diversification into two prominent morphological branches, each with a series of 'twigs' representing evolutionary experimentation at the species or subspecies level. The second important trend, which in its earliest manifestations cannot clearly be ascribed to one or the other branch, is the behavioral complexity of an increasing reliance on technology to expand upon limited inherent morphological specializations and to buffer the organism from its environment. This technological dependence is directly associated with the expansion of hominin range outside Africa by the genus Homo, and is accelerated in the sole extant form Homo sapiens through the last 100 Ka. There are interesting correlates between the evolutionary and behavioral patterns seen in the hominin clade and environmental dynamics of the Neogene. In particular, the tempo of morphological and behavioral innovation may be tracking major events in Neogene climatic development as well as reflecting intervals of variability or stability. Major improvements in analytical techniques, coupled with important new collections and a growing body of contextual data are now making possible the integration of global, regional and local environmental archives with an improved biological understanding of the hominin clade to address questions of coincidence and causality.

Feibel, C. S.

2004-12-01

487

Balance Problems  

MedlinePLUS

... often, it could be a sign of a balance problem. Balance problems can make you feel unsteady or as ... fall-related injuries, such as hip fracture. Some balance problems are due to problems in the inner ...

488

Steering Chiral Swimmers along Noisy Helical Paths  

NASA Astrophysics Data System (ADS)

Chemotaxis along helical paths towards a target releasing a chemoattractant is found in sperm cells and many microorganisms. We discuss the stochastic differential geometry of the noisy helical swimming path of a chiral swimmer. A chiral swimmer equipped with a simple feedback system can navigate in a concentration gradient of chemoattractant. We derive an effective equation for the alignment of helical paths with a concentration gradient which is related to the alignment of a dipole in an external field and discuss the chemotaxis index.

Friedrich, Benjamin M.; Jülicher, Frank

2009-08-01

489

The (1+1) Dimensional Dirac Equation With Pseudoscalar Potentials: Path Integral Treatment  

NASA Astrophysics Data System (ADS)

The supersymetric path integrals in solving the problem of relativistic spinning particle interacting with pseudoscalar potentials is examined. The relative propagator is presented by means of path integral, where the spin degrees of freedom are described by odd Grassmannian variables and the gauge invariant part of the effective action has a form similar to the standard pseudoclassical action given by Berezin and Marinov. After integrating over fermionic variables (Grassmannian variables), the problem is reduced to a nonrelativistic one with an effective supersymetric potential. Some explicit examples are considered, where we have extracted the energy spectrum of the electron and the wave functions.

Haouat, S.; Chetouani, L.

2007-06-01

490

Environment induced time arrow and the Closed Time Path method  

NASA Astrophysics Data System (ADS)

It is shown in the framework of a harmonic system that the thermodynamical time arrow is induced by the environmental initial conditions in a manner similar to spontaneous symmetry breaking. The Closed Time Path formalism is introduced in classical mechanics to handle Green functions for initial condition problems by the action principle, in a systematic manner. The application of this scheme for quantum systems shows the common dynamical origin of the thermodynamical and the quantum time arrows. It is furthermore conjectured that the quantum-classical transition is strongly coupled.

Polonyi, Janos

2013-06-01

491

Iterative summation of path integrals for nonequilibrium molecular quantum transport  

NASA Astrophysics Data System (ADS)

We formulate and apply a nonperturbative numerical approach to the nonequilibrium current I(V) through a voltage-biased molecular conductor. We focus on a single electronic level coupled to an unequilibrated vibration mode (Anderson-Holstein model), which can be mapped to an effective three-state problem. Performing an iterative summation of real-time path integral (ISPI) expressions, we accurately reproduce known analytical results in three different limits. We then study the crossover regime between those limits and show that the Franck-Condon blockade persists in the quantum-coherent low-temperature limit, with a nonequilibrium smearing of step features in the IV curve.

Hützen, R.; Weiss, S.; Thorwart, M.; Egger, R.

2012-03-01

492

Smart random walkers: the cost of knowing the path.  

PubMed

In this work we study the problem of targeting signals in networks using entropy information measurements to quantify the cost of targeting. We introduce a penalization rule that imposes a restriction on the long paths and therefore focuses the signal to the target. By this scheme we go continuously from fully random walkers to walkers biased to the target. We found that the optimal degree of penalization is mainly determined by the topology of the network. By analyzing several examples, we have found that a small amount of penalization reduces considerably the typical walk length, and from this we conclude that a network can be efficiently navigated with restricted information. PMID:23005381

Perotti, Juan I; Billoni, Orlando V

2012-07-19

493

Yang-Mills equations and parallel propagation on closed paths  

SciTech Connect

A new variable for Yang-Mills theory is introduced. This variable, denoted by H, is the differential holonomy operator, i.e., the variation of the holonomy operator associated with a variation of a specific set of closed paths in Minkowski space. The main purpose of this paper is to show how the vacuum Yang-Mills equations can be restated as relatively simple equations for H. We will present two separate approaches to this problem. The first is a global approach involving Stokes's theorem and global regularity whereas the second uses purely local arguments. The self-dual non-Abelian case and Maxwell case are considered as particular examples.

Kozameh, C.N.; Newman, E.T.

1985-02-15

494

Middle path for electricity options and sustainable development.  

National Technical Information Service (NTIS)

In a landmark article in Foreign Affairs in October 1976, Amory Lovins presented his vision of two vastly different and seemingly irreconcilable paths that energy provision might take into the future. One path was a ''hard'' path, characterized by extensi...

J. I. Mills J. S. Herring

1994-01-01

495

A chemist building paths to cell biology.  

PubMed

Galileo is reported to have stated, "Measure what is measurable and make measurable what is not so." My group's trajectory in cell biology has closely followed this philosophy, although it took some searching to find this path. PMID:24174456

Weibel, Douglas B

2013-11-01

496

UV Laser Long-Path Absorption Spectroscopy.  

National Technical Information Service (NTIS)

Long path Differential Optical Absorption Spectroscopy (DOAS) using a picosecond UV laser as a light source was developed in our institute. Tropospheric OH radicals are measured by their rotational absorption lines around 308 nm. The spectra are obtained ...

H. Dorn T. Brauers R. Neuroth

1994-01-01

497

Diversion Path Analysis Handbook. Volume I. Methodology.  

National Technical Information Service (NTIS)

Diversion Path Analysis (DPA) is a procedure for analyzing internal controls of a facility in order to identify vulnerabilities to successful diversion of material by an adversary. The internal covert threat is addressed but the results are also applicabl...

M. D. K. Maltese K. E. Goodwin J. C. Schleter

1976-01-01

498

Path integration while ignoring irrelevant movement.  

PubMed

Participants attempted to return to the origin of travel after following an outbound path by locomotion on foot (Experiments 1-3) or in a virtual visual environment (Experiment 4). Critical conditions interrupted the outbound path with verbal distraction or irrelevant, to-be-ignored movements. Irrelevant movement, real or virtual, had greater effects than verbal or cognitive distraction, indicating inability to ignore displacement during path integration. Effects of the irrelevant movement's direction (backward vs. rightward) and location (1st vs. 2nd leg of path) indicated that participants encoded a configural representation of the pathway and then cognitively compensated for the movement, producing errors directly related to the demands of compensation. An encoding-error model fit to the data indicated that backward movement produced downward rescaling, whereas movement that led to implied rotation (rightward on 2nd leg) produced distortions of shape and scale. PMID:10682296

May, M; Klatzky, R L

2000-01-01

499

Expedite Departure Path (EDP) Operational Concept.  

National Technical Information Service (NTIS)

This document describes the operational concept for the Expedite Departure Path (EDP) tool. EDP is part of the Center-TRACON Automation System (CTAS). CTAS provides computer intelligence for planning and controlling arrival and departure traffic within se...

C. W. Johnson D. R. Isaacson K. K. Lee

1999-01-01

500

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.