Sample records for shortest path problems

  1. Shortest Path Algorithm What is the Shortest Path Problem?

    E-print Network

    Razak, Saquib

    at vertex B: The resulting vertex-weighted graph is: #12;Data structures required · The implementation. · The method returns a vertex-weighted Digraph from which the shortest path from s to any vertex can be found;What is the shortest path problem? · In an edge-weighted graph, the weight of an edge measures the cost

  2. Shortest Path Problems on a Polyhedral Surface

    Microsoft Academic Search

    Atlas F. Cook; Carola Wenk

    2009-01-01

    We develop algorithms to compute edge sequences, Voronoi diagrams, shortest path maps, the Fréchet distance, and the diameter for a polyhedral surface. Dis- tances on the surface are measured either by the length of a Euclidean shortest path or by link distance.

  3. Running Time Analysis of ACO Systems for Shortest Path Problems

    NASA Astrophysics Data System (ADS)

    Horoba, Christian; Sudholt, Dirk

    Ant Colony Optimization (ACO) is inspired by the ability of ant colonies to find shortest paths between their nest and a food source. We analyze the running time of different ACO systems for shortest path problems. First, we improve running time bounds by Attiratanasunthron and Fakcharoenphol [Information Processing Letters, 105(3):88-92, 2008] for single-destination shortest paths and extend their results for acyclic graphs to arbitrary graphs. Our upper bound is asymptotically tight for large evaporation factors, holds with high probability, and transfers to the all-pairs shortest paths problem. There, a simple mechanism for exchanging information between ants with different destinations yields a significant improvement. Our results indicate that ACO is the best known metaheuristic for the all-pairs shortest paths problem.

  4. Sensitivity Analysis for Shortest Path Problems and Maximum Capacity Path Problems in Undirected Graphs

    E-print Network

    Ramaswamy, Ramkumar

    2004-12-10

    This paper addresses sensitivity analysis questions concerning the shortest path problem and the maximum capacity path problem in an undirected network. For both problems, we determine the maximum and ...

  5. OBSTACLE-AVOIDING SIMILARITY METRICS AND SHORTEST PATH PROBLEMS

    E-print Network

    Texas at San Antonio, University of

    -AVOIDING SIMILARITY METRICS AND SHORTEST PATH PROBLEMS Atlas F. Cook IV, Ph.D. The University of Texas at San Antonio COMMITTEE: ________________________________________ Carola Wenk, Ph.D., Chair ________________________________________ Tom Bylander, Ph.D. ________________________________________ José Iovino, Ph.D

  6. An Improved Physarum polycephalum Algorithm for the Shortest Path Problem

    PubMed Central

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

    2014-01-01

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

  7. An Effective Evolutionary Approach for Bicriteria Shortest Path Routing Problems

    NASA Astrophysics Data System (ADS)

    Lin, Lin; Gen, Mitsuo

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

  8. Quantum algorithms for shortest paths problems in structured instances

    E-print Network

    Aran Nayebi; Virginia Vassilevska Williams

    2014-10-23

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

  9. Computing almost shortest paths

    Microsoft Academic Search

    Michael Elkin

    2005-01-01

    We study the s-sources almost shortest paths(abbreviated s-ASP) problem. Given an unweightedgraph G = (V,E),and a subset S ? Vof s nodes, the goal is to compute almostshortest paths between all the pairs of nodes S× V. We devise an algorithm withrunning timeO(∣E∣n?+ s ·n1 + ?)for this problem that computes the pathsPu,wfor all pairs (u,w) ?S × V such

  10. Self-organization and solution of shortest-path optimization problems with memristive networks

    E-print Network

    Pershin, Yuriy V

    2013-01-01

    We show that memristive networks-namely networks of resistors with memory-can efficiently solve shortest-path optimization problems. Indeed, the presence of memory (time non-locality) promotes self organization of the network into the shortest possible path(s). We introduce a network entropy function to characterize the self-organized evolution, show the solution of the shortest-path problem and demonstrate the healing property of the solution path. Finally, we provide an algorithm to solve the traveling salesman problem. Similar considerations apply to networks of memcapacitors and meminductors, and networks with memory in various dimensions.

  11. Geometric Shortest Path Containers

    Microsoft Academic Search

    Dorothea Wagner; Thomas Willhalm; Christos Zaroliagis

    2004-01-01

    In this paper, we consider Dijkstra's algorithm for the single source single target shortest path problem in large sparse graphs. The goal is to reduce the response time for on-line queries by using precomputed information. Due to the size of the graph, preprocessing space requirements can be only linear in the number of nodes. We assume that a layout of

  12. A Faster Algorithm for the Single Source Shortest Path Problem with Few Distinct Positive Lengths

    E-print Network

    Orlin, James B.

    In this paper, we propose an efficient method for implementing Dijkstra's algorithm for the Single Source Shortest Path Problem (SSSPP) in a graph whose edges have positive length, and where there are few distinct edge ...

  13. A New GPU-based Approach to the Shortest Path Problem

    E-print Network

    Llanos, Diego R.

    . Llanos, and Arturo Gonzalez-Escribano Dept. Inform´atica, Universidad de Valladolid, Spain. {hector|yuri.torresA New GPU-based Approach to the Shortest Path Problem Hector Ortega-Arranz, Yuri Torres, Diego R

  14. An Evaluation of Potentials of Genetic Algorithm in Shortest Path Problem

    NASA Astrophysics Data System (ADS)

    Hassany Pazooky, S.; Rahmatollahi Namin, Sh; Soleymani, A.; Samadzadegan, F.

    2009-04-01

    One of the most typical issues considered in combinatorial systems in transportation networks, is the shortest path problem. In such networks, routing has a significant impact on the network's performance. Due to natural complexity in transportation networks and strong impact of routing in different fields of decision making, such as traffic management and vehicle routing problem (VRP), appropriate solutions to solve this problem are crucial to be determined. During last years, in order to solve the shortest path problem, different solutions are proposed. These techniques are divided into two categories of classic and evolutionary approaches. Two well-known classic algorithms are Dijkstra and A*. Dijkstra is known as a robust, but time consuming algorithm in finding the shortest path problem. A* is also another algorithm very similar to Dijkstra, less robust but with a higher performance. On the other hand, Genetic algorithms are introduced as most applicable evolutionary algorithms. Genetic Algorithm uses a parallel search method in several parts of the domain and is not trapped in local optimums. In this paper, the potentiality of Genetic algorithm for finding the shortest path is evaluated by making a comparison between this algorithm and classic algorithms (Dijkstra and A*). Evaluation of the potential of these techniques on a transportation network in an urban area shows that due to the problem of classic methods in their small search space, GA had a better performance in finding the shortest path.

  15. The Bellman-Ford algorithm Most basic shortest-paths algorithm for the shortest-path problem

    E-print Network

    Bai, Zhaojun

    the "lightest" or "closest" vertex in V - S to insert into S #12;The SSSP in DAG DAG: can have negative-weight negative-weight edges Compute d[v] and [v] for all v V d[v] = (s, v): the shortest-path weight from the source s to v. [v]: the parent (predecessor) of v. Return TRUE if no negative-weight cycles reachable

  16. Dynamic Shortest Paths Containers

    Microsoft Academic Search

    Dorothea Wagner; Thomas Willhalm; Christos D. Zaroliagis

    2004-01-01

    Using a set of geometric containers to speed up shortest path queries in a weighted graph has been proven a useful tool for dealing with large sparse graphs. Given a layout of a graph G = (V; E), we store, for each edge (u; v) 2 E, the bounding box of all nodes t 2 V for which a shortest

  17. A Bio-Inspired Method for the Constrained Shortest Path Problem

    PubMed Central

    Wang, Hongping; Lu, Xi; Wang, Qing

    2014-01-01

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

  18. Shortest Path Discovery Problems: A Framework, Algorithms and Experimental Results

    E-print Network

    Szepesvari, Csaba

    with execution like in real-time search, etc. Recently there has been a growing interest in incremental search assumptions made on the underlying search graph one gets fundamentally different problem types: the graph may of estimates of the cost- to-go function like in heuristic search, or the search might be interleaved

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

    SciTech Connect

    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

    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.

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

    SciTech Connect

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

    1989-04-01

    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.

  1. Enhanced Genetic Algorithm approach for Solving Dynamic Shortest Path Routing Problems using Immigrants and Memory Schemes

    E-print Network

    Nair, T R Gopalakrishnan; Yashoda, M B

    2011-01-01

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

  2. Shortest Paths in Euclidean Graphs

    Microsoft Academic Search

    Robert Sedgewick; Jeffrey Scott Vitter

    1986-01-01

    We analyze a simple method for finding shortest paths inEuclidean graphs (where vertices are points in a Euclidean space and edge weights are Euclidean distances between points). For many graph\\u000a models, the average running time of the algorithm to find the shortest path between a specified pair of vertices in a graph\\u000a withV vertices andE edges is shown to beO(V)

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

    E-print Network

    Yang, Shengxiang

    ) problem has been well addressed using intelligent optimization techniques, e.g., artificial neural, they will be effective in fixed infrastructure wireless or wired networks. But, they exhibit unacceptably high Networks Hui Cheng, Shengxiang Yang Member, IEEE Abstract-- In recent years, the static shortest path (SP

  4. A temporal ant colony optimization approach to the shortest path problem in dynamic scale-free networks

    NASA Astrophysics Data System (ADS)

    Yu, Feng; Li, Yanjun; Wu, Tie-Jun

    2010-02-01

    A large number of networks in the real world have a scale-free structure, and the parameters of the networks change stochastically with time. Searching for the shortest paths in a scale-free dynamic and stochastic network is not only necessary for the estimation of the statistical characteristics such as the average shortest path length of the network, but also challenges the traditional concepts related to the “shortest path” of a network and the design of path searching strategies. In this paper, the concept of shortest path is defined on the basis of a scale-free dynamic and stochastic network model, and a temporal ant colony optimization (TACO) algorithm is proposed for searching for the shortest paths in the network. The convergence and the setup for some important parameters of the TACO algorithm are discussed through theoretical analysis and computer simulations, validating the effectiveness of the proposed algorithm.

  5. Circular Shortest Path on Regular Grids

    Microsoft Academic Search

    Changming Sun; Stefano Pallottino Csiro

    2002-01-01

    Shortest path algorithms have been used for a number of applications such as crack detection, road orlinear feature extraction on images. There are applications where the starting and ending positionsof the shortest path needs to be constrained. In this paper, we presents several new algorithms forthe extraction of a circular shortest path within an image such that the starting and

  6. Symbolic Shortest Path Planning

    E-print Network

    Morik, Katharina

    efficiency, the paper analyzes the locality for weighted problem graphs and show that it matches the duplicate detection scope in best-first search graphs. Cost-optimal plans for compiled competition benchmark breadth- first to best-first search graphs. We show how to combine a set of disjoint weighted symbolic

  7. An edge-wise linear shortest path algorithm for non negative weighted undirected graphs

    Microsoft Academic Search

    Muhammad Aasim Qureshi; Mohd Fadzil Hassan; Sohail Safdar; Rehan Akbar; Rabia Sammi

    2009-01-01

    In most of the shortest path problems like vehicle routing problems and network routing problems, we only need an efficient path between two points---source and destination, and it is not necessary to calculate the shortest path from source to all other nodes. This paper concentrates on this very idea and presents an algorithm for calculating shortest path for nonnegative weighted

  8. Dynamic Shortest Paths Containers Dorothea Wagnera,1

    E-print Network

    Zaroliagis, Christos D.

    of nodes. In [17], angular sectors were introduced to speed up the processing of such shortest path queries of Patras, 26500 Patras, Greece Abstract Using a set of geometric containers to speed up shortest path is quite large (though sparse), and hence space requirements are only acceptable to be linear in the number

  9. Shortest path and Schramm-Loewner Evolution

    NASA Astrophysics Data System (ADS)

    Posé, N.; Schrenk, K. J.; Araújo, N. A. M.; Herrmann, H. J.

    2014-06-01

    We numerically show that the statistical properties of the shortest path on critical percolation clusters are consistent with the ones predicted for Schramm-Loewner evolution (SLE) curves for ? = 1.04 +/- 0.02. The shortest path results from a global optimization process. To identify it, one needs to explore an entire area. Establishing a relation with SLE permits to generate curves statistically equivalent to the shortest path from a Brownian motion. We numerically analyze the winding angle, the left passage probability, and the driving function of the shortest path and compare them to the distributions predicted for SLE curves with the same fractal dimension. The consistency with SLE opens the possibility of using a solid theoretical framework to describe the shortest path and it raises relevant questions regarding conformal invariance and domain Markov properties, which we also discuss.

  10. Shortest path and Schramm-Loewner Evolution

    PubMed Central

    Posé, N.; Schrenk, K. J.; Araújo, N. A. M.; Herrmann, H. J.

    2014-01-01

    We numerically show that the statistical properties of the shortest path on critical percolation clusters are consistent with the ones predicted for Schramm-Loewner evolution (SLE) curves for ? = 1.04 ± 0.02. The shortest path results from a global optimization process. To identify it, one needs to explore an entire area. Establishing a relation with SLE permits to generate curves statistically equivalent to the shortest path from a Brownian motion. We numerically analyze the winding angle, the left passage probability, and the driving function of the shortest path and compare them to the distributions predicted for SLE curves with the same fractal dimension. The consistency with SLE opens the possibility of using a solid theoretical framework to describe the shortest path and it raises relevant questions regarding conformal invariance and domain Markov properties, which we also discuss. PMID:24975019

  11. Shortest path and Schramm-Loewner evolution.

    PubMed

    Posé, N; Schrenk, K J; Araújo, N A M; Herrmann, H J

    2014-01-01

    We numerically show that the statistical properties of the shortest path on critical percolation clusters are consistent with the ones predicted for Schramm-Loewner evolution (SLE) curves for ? = 1.04 ± 0.02. The shortest path results from a global optimization process. To identify it, one needs to explore an entire area. Establishing a relation with SLE permits to generate curves statistically equivalent to the shortest path from a Brownian motion. We numerically analyze the winding angle, the left passage probability, and the driving function of the shortest path and compare them to the distributions predicted for SLE curves with the same fractal dimension. The consistency with SLE opens the possibility of using a solid theoretical framework to describe the shortest path and it raises relevant questions regarding conformal invariance and domain Markov properties, which we also discuss. PMID:24975019

  12. 122 IEEE COMMUNICATIONS LETTERS, VOL. 8, NO. 2, FEBRUARY 2004 Finding All Hops Shortest Paths

    E-print Network

    Ansari, Nirwan

    122 IEEE COMMUNICATIONS LETTERS, VOL. 8, NO. 2, FEBRUARY 2004 Finding All Hops Shortest Paths Gang a new problem referred to as the All Hops Shortest Paths (AHSP) problem. The AHSP problem involves selecting, for all hop counts, the shortest paths from a given source to any other node in a network. We

  13. Implicit Routing And Shortest Path Information

    Microsoft Academic Search

    Evangelos Kranakis; Danny Krizanc; Jorge Urrutia

    1995-01-01

    )Evangelos Kranakisy(kranakis@scs.carleton.ca)Danny Krizancy(krizanc@scs.carleton.ca)Jorge Urrutiazy(jorge@csi.uottawa.ca)AbstractWe study the problem of constructing graphs from shortest path information(complete or partial). Consider graphs with labeled verticesand edges. Given a collection V of vertices and for each u 2 V a positiveinteger d(u), and a family F u = fF u;i : i ! d(u)g of subsets of Vconstruct a graph such that for each u

  14. Analysis of Algorithms Problem Set no. 3 --Dynamic All-Pairs Shortest Paths

    E-print Network

    Zwick, Uri

    of the graph. Show that there can be at most O(zn2) locally historical paths passing through a given vertex v. Guidance: Showing that there are at most O(zn2) such paths that start or end at v is relatively straightforward. The harder part of the proof is showing that there only O(zn2) locally historical paths having v

  15. Highway Hierarchies Hasten Exact Shortest Path Queries

    Microsoft Academic Search

    Peter Sanders; Dominik Schultes

    2005-01-01

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

  16. Distributional properties of stochastic shortest paths for smuggled nuclear material

    SciTech Connect

    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

    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.

  17. The Multiple Choice Elementary Constrained Shortest Path Problem Karen Smilowitz Guangming Zhang

    E-print Network

    Smilowitz, Karen

    Problem (VRP) and variations of the VRP, including the Pickup and Delivery Problem; see, for example the linear relaxation of the VRP at the nodes of the branch-and-price tree by considering a reduced subset

  18. The Multiple Choice Elementary Constrained Shortest Path Problem Karen Smilowitz Guangming Zhang

    E-print Network

    Hazen, Gordon

    to solve the Vehicle Routing Problem (VRP) and variations of the VRP, including the Pickup and Delivery®ort required to solve the linear relaxation of the VRP at the nodes of the branch-and-price tree by considering

  19. Shortest Path Computation with No Information Leakage

    E-print Network

    Mouratidis, Kyriakos

    2012-01-01

    Shortest path computation is one of the most common queries in location-based services (LBSs). Although particularly useful, such queries raise serious privacy concerns. Exposing to a (potentially untrusted) LBS the client's position and her destination may reveal personal information, such as social habits, health condition, shopping preferences, lifestyle choices, etc. The only existing method for privacy-preserving shortest path computation follows the obfuscation paradigm; it prevents the LBS from inferring the source and destination of the query with a probability higher than a threshold. This implies, however, that the LBS still deduces some information (albeit not exact) about the client's location and her destination. In this paper we aim at strong privacy, where the adversary learns nothing about the shortest path query. We achieve this via established private information retrieval techniques, which we treat as black-box building blocks. Experiments on real, large-scale road networks assess the pract...

  20. A near linear shortest path algorithm for weighted undirected graphs

    Microsoft Academic Search

    Muhammad Aasim Qureshi; Mohd Fadzil Hassan; Sohail Safdar; Rehan Akbar

    2011-01-01

    This paper presents an algorithm for Shortest Path Tree (SPT) problem. The presented algorithm is an improvement over a previously published work of the authors. The effort is put in to improve the running\\/execution time of the SPT problem. Introduced improvement is simple and easy to incorporate in to the existing algorithm. This algorithm uses Depth First Search (DFS) like

  1. Shortest Paths in Microseconds Rachit Agarwal

    E-print Network

    , the goal is to minimize latency while maintaining feasible memory requirements. We present ASAP, a system that achieves this goal by exploiting the structure of social networks. ASAP preprocesses a given network edges, ASAP computes a shortest path for most node pairs in less than 49 microseconds per pair. ASAP

  2. Optimal Distributed All Pairs Shortest Paths

    E-print Network

    Optimal Distributed All Pairs Shortest Paths ETH Zurich ­ Distributed Computing Group Stephan Holzer ETH Zürich Roger Wattenhofer ETH Zürich #12;Distributed network Graph G of n nodes 2 4 5 1 3 #12;Distributed network Graph G of n nodes 2 4 5 1 3 Unique IDs #12;Distributed network Graph G of n nodes 2 4 5 1

  3. Accumulative competition neural network for shortest path tree computation

    Microsoft Academic Search

    Ji-Yang Dong; Wen-Jun Wang; Jun-Ying Zhang

    2003-01-01

    Shortest path tree (SPT) computation is an important combinatorial optimization problem with numerous applications. A novel neural network model called accumulative competition neural network (ACNN) is proposed in this paper to compute the SPT in a given weighted graph. Comparing with the other neural network based search algorithms, the algorithm presented here features in much less number of neurons needed,

  4. Inverse shortest path algorithms in protected UMTS access networks

    Microsoft Academic Search

    István Gódor; János Harmatos; Alpár Jüttner

    2005-01-01

    In this paper, the application questions of OSPF (Open Shortest Path First) routing protocols in the all{IP based protected UMTS (Universal Mobile Telecommunications System) access networks is inves- tigated. The basic problem here is how the OSPF administrative weights should be adjusted in an ade- quate way, resulting near{optimal overall network per- formance both in nominal network operation and in

  5. Report SYCON91-10 SHORTEST PATHS FOR THE REEDS-SHEPP CAR

    E-print Network

    Sussmann, Hector

    Report SYCON­91-10 SHORTEST PATHS FOR THE REEDS-SHEPP CAR: A WORKED OUT EXAMPLE OF THE USE the shortest paths for a model of a car that can move forwards and backwards. This problem was discussed to derive some of the properties of the minimum paths of the Reeds-Shepp car, cf. [7]. 2 This author's work

  6. Pomelo: accurate and decentralized shortest-path distance estimation in social graphs

    Microsoft Academic Search

    Zhuo Chen; Yang Chen; Cong Ding; Beixing Deng; Xing Li

    2011-01-01

    Computing the shortest-path distances between nodes is a key problem in analyzing social graphs. Traditional methods like breadth-first search (BFS) do not scale well with graph size. Recently, a Graph Coordinate System, called Orion, has been proposed to estimate shortest-path distances in a scalable way. Orion uses a landmark-based approach, which does not take account of the shortest-path distances between

  7. Goal Directed Shortest Path Queries Using Precomputed Cluster Distances

    E-print Network

    Matijevic, Domagoj

    of starting and end point as well as the length of the shortest connection between each pair of clusters[v] algorithm removes the closest node u, settles Dijkstra's algorithm for shortest path queries can be accelerated by using precomputed shortest path

  8. An Experimental Study of a Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances

    E-print Network

    Bader, David A.

    shortest path problem with non-negative edge weights (NSSP) on large- scale graphs using the -stepping with competitive sequential algorithms, for low-diameter sparse graphs. For instance, -stepping on a directed scaleAn Experimental Study of a Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances

  9. Multiple Object Tracking Using the Shortest Path Faster Association Algorithm

    PubMed Central

    Liu, Heping; Liu, Huaping; Yang, Bin

    2014-01-01

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

  10. Shortest paths synthesis for a car-like robot

    Microsoft Academic Search

    P. Soueres; J.-P. Laumond

    1996-01-01

    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

  11. Parallel Shortest Path Algorithms for Solving Large-Scale Instances

    Microsoft Academic Search

    Kamesh Madduri; David A. Bader; Jonathan W. Berry; Bruce A. Hendrickson

    We present an experimental study of parallel algorithms for solving the single source shortest path problem with non-negative edge weights (NSSP) on large-scale graphs. We implement Meyer and Sander's ?-stepping algorithm and report performance re- sults on the Cray MTA-2, a multithreaded parallel architecture. The MTA-2 is a high-end shared memory system offering two unique features that aid the efficient

  12. Reliability Theory Model and Expected Life Shortest Path in Stochastic and Time-Dependent Networks

    Microsoft Academic Search

    Guo-zhen Tan; Xiang-fu Xia; Wen Gao

    2003-01-01

    We consider the priori expected shortest path problem from a single origin to a single destination for each departure time\\u000a in stochastic and time-dependent networks. Such problem requires more than standard shortest path techniques. First, we transform\\u000a this problem into the problem of systemic reliability, and identify a weaker consistent reliability condition that insures\\u000a the validity of generalized dynamic-programming method

  13. A shortest path algorithm for mobile satellite communication network

    Microsoft Academic Search

    Zhang Tao; Zhang Jun; Liu Zhong Kan

    2005-01-01

    Mobile satellite network is a special time-varying network. Some classical network theories used in the current terrestrial networks, such as the shortest path algorithm, cannot be applied to it availably. In this paper, based on the proposed model of mobile satellite network, the classical shortest path algorithm of fixed topological network, such as the Dijkstra algorithm, is proved to be

  14. All Pairs Shortest Paths for Graphs with Small Integer Length Edges

    Microsoft Academic Search

    Zvi Galil; Oded Margalit

    1997-01-01

    The authors have solved the all pairs shortest distances (APSD) problem for graphs with integer edge lengths. Our algorithm is subcubic for edge lengths of small (?M) absolute value. In this paper we show how to transform these algorithms to solve the all pairs shortest paths (APSP), in the same time complexity, up to a polylogarithmic factor. Forn=|V| the number

  15. Using shortest path to discover criminal community

    E-print Network

    Magalingam, Pritheega; Rao, Asha

    2015-01-01

    Extracting communities using existing community detection algorithms yields dense sub-networks that are difficult to analyse. Extracting a smaller sample that embodies the relationships of a list of suspects is an important part of the beginning of an investigation. In this paper, we present the efficacy of our shortest paths network search algorithm (SPNSA) that begins with an "algorithm feed", a small subset of nodes of particular interest, and builds an investigative sub-network. The algorithm feed may consist of known criminals or suspects, or persons of influence. This sets our approach apart from existing community detection algorithms. We apply the SPNSA on the Enron Dataset of e-mail communications starting with those convicted of money laundering in relation to the collapse of Enron as the algorithm feed. The algorithm produces sparse and small sub-networks that could feasibly identify a list of persons and relationships to be further investigated. In contrast, we show that identifying sub-networks o...

  16. ON THE ACCELERATION OF SHORTEST PATH CALCULATIONS IN TRANSPORTATION NETWORKS

    SciTech Connect

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

    2007-01-08

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

  17. Shortest Path Refinement for Motion Estimation from Tagged MR Images

    PubMed Central

    Liu, Xiaofeng; Prince, Jerry L.

    2013-01-01

    Magnetic resonance tagging makes it possible to measure the motion of tissues such as muscles in the heart and tongue. The harmonic phase (HARP) method largely automates the process of tracking points within tagged MR images, permitting many motion properties to be computed. However, HARP tracking can yield erroneous motion estimates due to: (1) large deformations between image frames; (2) through-plane motion; and (3) tissue boundaries. Methods that incorporate the spatial continuity of motion—so-called refinement or floodfilling methods—have previously been reported to reduce tracking errors. This paper presents a new refinement method based on shortest path computations. The method uses a graph representation of the image and seeks an optimal tracking order from a specified seed to each point in the image by solving a single source shortest path problem. This minimizes the potential errors for those path dependent solutions that are found in other refinement methods. In addition to this, tracking in the presence of through-plane motion is improved by introducing synthetic tags at the reference time (when the tissue is not deformed). Experimental results on both tongue and cardiac images show that the proposed method can track the whole tissue more robustly and is also computationally efficient. PMID:20304720

  18. Shortest Path Games: Computational Complexity of Solution Concepts

    E-print Network

    Amsterdam, University of

    Shortest Path Games: Computational Complexity of Solution Concepts MSc Thesis (Afstudeerscriptie 9 2.1 Coalitional Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Concepts for Coalitional Games . . . . . . . . . . . . . . . . . . . . . . . 12 2.3.1 Power Indices

  19. Two Phase Shortest Path Algorithm for Nonnegative Weighted Undirected Graphs

    Microsoft Academic Search

    Muhammad Aasim Qureshi; Mohd Fadzil Hassan; Sohail Safdar; Rehan Akbar

    2010-01-01

    Abstract-Breadth First Search (BFS) can calculate the shortest path for un-weighted graphs very efficiently but when it comes to non-negative weighted graphs it fails at a point when a successor updates a predecessor. Such nodes are being referred as Culprit nodes in this research. These Culprit nodes are the ones that cause error in shortest path in an algorithm that

  20. Shortest path algorithm with pre-calculated single link failure recovery for non-negative weighted undirected graphs

    Microsoft Academic Search

    Muhammad Aasim Qureshi; Mohd Fadzil Hassan; Sohail Safdar; Rehan Akbar; Rabia Sammi

    2010-01-01

    Shortest path and related problems have been a very hot topic for researchers since Dijekstra devised his first shortest path algorithm. In transportation and communication routing, during the execution of system, failure of any link needs robust and most effective recovery. In such problems we need some recovery mechanism and\\/or plan for the continuation of the process with minimum or

  1. A O(E) Time Shortest Path Algorithm For Non Negative Weighted Undirected Graphs

    E-print Network

    Qureshi, Muhammad Aasim; Safdar, Sohail; Akbar, Rehan

    2009-01-01

    In most of the shortest path problems like vehicle routing problems and network routing problems, we only need an efficient path between two points source and destination, and it is not necessary to calculate the shortest path from source to all other nodes. This paper concentrates on this very idea and presents an algorithm for calculating shortest path for (i) nonnegative weighted undirected graphs (ii) unweighted undirected graphs. The algorithm completes its execution in O(E) for all graphs except few in which longer path (in terms of number of edges) from source to some node makes it best selection for that node. The main advantage of the algorithms is its simplicity and it does not need complex data structures for implementations.

  2. An Experimental Study of a Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances

    E-print Network

    Hutter, Frank

    of the single source short- est path problem with non-negative edge weights (NSSP) on large-scale graphs using with competitive sequential algorithms, for low-diameter sparse graphs. For instance, -stepping on a directed scaleAn Experimental Study of a Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances

  3. Traffic-engineering-aware shortest-path routing and its application in IP-over-WDM networks [Invited

    NASA Astrophysics Data System (ADS)

    Lee, Youngseok; Mukherjee, Biswanath

    2004-03-01

    Single shortest-path routing is known to perform poorly for Internet traffic engineering (TE) where the typical optimization objective is to minimize the maximum link load. Splitting traffic uniformly over equal-cost multiple shortest paths in open shortest path first and intermediate system-intermediate system protocols does not always minimize the maximum link load when multiple paths are not carefully selected for the global traffic demand matrix. However, a TE-aware shortest path among all the equal-cost multiple shortest paths between each ingress-egress pair can be selected such that the maximum link load is significantly reduced. IP routers can use the globally optimal TE-aware shortest path without any change to existing routing protocols and without any serious configuration overhead. While calculating TE-aware shortest paths, the destination-based forwarding constraint at a node should be satisfied, because an IP router will forward a packet to the next hop toward the destination by looking up the destination prefix. We present a mathematical problem formulation for finding a set of TE-aware shortest paths for the given network as an integer linear program, and we propose a simple heuristic for solving large instances of the problem. Then we explore the usage of our proposed algorithm for the integrated TE method in IP-over-WDM networks. The proposed algorithm is evaluated through simulations in IP networks as well as in IP-over-WDM networks.

  4. IE 170 Laboratory 8: Shortest Paths Drs. T.K. Ralphs and R.T. Berger

    E-print Network

    Ralphs, Ted

    and generality of graph search in solving many important problems. 3. Understand the importance of object-oriented design and code re-use. 4. Understand the importance of and application of the shortest path problem. 1.4 Design and Analysis In this lab, you will recycle source code from two previous labs to implement

  5. Materialization Trade-Offs in Hierarchical Shortest Path Algorithms

    Microsoft Academic Search

    Shashi Shekhar; Andrew Fetterer; Bjajesh Goyal

    1997-01-01

    Materialization and hierarchical routing algorithms are becoming important tools in querying databases for the shortest paths in time-critical applications like Intelligent Transportation Systems (ITS), due to the growing size of their spatial graph databases [16]. A hierarchical routing algorithm decomposes the original graph into a set of fragment graphs and a boundary graph which summarizes the fragment graphs. A fully

  6. Finding Shortest Path for Developed Cognitive Map Using Medial Axis

    E-print Network

    Farhan, Hazim A; Al-Ghazi, Suhaib I

    2011-01-01

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

  7. Distributed Shortest Paths Algorithms (Extended Abstract)

    E-print Network

    Rao, Satish

    is an orientation of G(V, E), i.e. (i + j) E i? implies that (i - j) E E. Those problems appear to be fairly basic communication net- work. For the problem of Breadth First Search, the best previously known algorithms required is the diameter.) This constitutes a major step towards achieving the lower bounds, which are 0(E) communication

  8. Edge Congestion of Shortest Path Systems for All-to-All Communication

    Microsoft Academic Search

    Charles M. Fiduccia; Paul J. Hedrick

    1997-01-01

    The problem of choosing a static shortest-path system that minimizes maximum edge congestion in a network is studied. Bounds based on parameters, such as diameter, bisection width, and average distance, are derived and conditions for producing uniform congestion on all edges are explored. Trees are shown to have maximum congestion on edges that are incident to a centroid node. Cartesian

  9. Stochastic Shortest Path MDPs with Dead Ends Andrey Kolobov Mausam Daniel S. Weld

    E-print Network

    Mausam

    , weld}@cs.washington.edu Dept of Computer Science and Engineering University of Washington Seattle, USAStochastic Shortest Path MDPs with Dead Ends Andrey Kolobov Mausam Daniel S. Weld {akolobov, mausam with in many real-world planning problems, be it sending a rover on Mars or navigating a robot in a building

  10. Approximating shortest paths on a convex polytope in three dimensions

    Microsoft Academic Search

    Pankaj K. Agarwal; Sariel Har-Peled; Micha Sharir; Kasturi R. Varadarajan

    1997-01-01

    Given a convex polytope P withn faces in R3, points s,t?6P, and a parameter 0e?1, we present an algorithm that constructs a path on6P from s tot whose length is at most1+edPs,t, where dPs,t is the length of the shortest path betweens andt on 6P. The algorithm runs in Onlog1\\/e+1\\/e3 time, and is relatively simple. The running time isOn+1\\/e3 if

  11. Finding Shortest Paths on Terrains by Killing Two Birds with One Stone

    E-print Network

    Wong, Raymond Chi-Wing

    ) of the terrain via shortest terrain paths. Other applications include robot path planning for unmanned vehicles. Such queries all rely on an important operation, that of finding shortest surface distances. However, shortest surface dis- tance computation is very time consuming. We propose techniques that enable efficient

  12. Modeling shortest path selection of the ant Linepithema humile using psychophysical theory and realistic parameter values.

    PubMed

    von Thienen, Wolfhard; Metzler, Dirk; Witte, Volker

    2015-05-01

    The emergence of self-organizing behavior in ants has been modeled in various theoretical approaches in the past decades. One model explains experimental observations in which Argentine ants (Linepithema humile) selected the shorter of two alternative paths from their nest to a food source (shortest path experiments). This model serves as an important example for the emergence of collective behavior and self-organization in biological systems. In addition, it inspired the development of computer algorithms for optimization problems called ant colony optimization (ACO). In the model, a choice function describing how ants react to different pheromone concentrations is fundamental. However, the parameters of the choice function were not deduced experimentally but freely adapted so that the model fitted the observations of the shortest path experiments. Thus, important knowledge was lacking about crucial model assumptions. A recent study on the Argentine ant provided this information by measuring the response of the ants to varying pheromone concentrations. In said study, the above mentioned choice function was fitted to the experimental data and its parameters were deduced. In addition, a psychometric function was fitted to the data and its parameters deduced. Based on these findings, it is possible to test the shortest path model by applying realistic parameter values. Here we present the results of such tests using Monte Carlo simulations of shortest path experiments with Argentine ants. We compare the choice function and the psychometric function, both with parameter values deduced from the above-mentioned experiments. Our results show that by applying the psychometric function, the shortest path experiments can be explained satisfactorily by the model. The study represents the first example of how psychophysical theory can be used to understand and model collective foraging behavior of ants based on trail pheromones. These findings may be important for other models of pheromone guided ant behavior and might inspire improved ACO algorithms. PMID:25769943

  13. An Efficient Shortest Triangle Paths Algorithm Applied to Multi-camera Self-calibration

    Microsoft Academic Search

    Ferid Bajramovic; Marcel Brückner; Joachim Denzler

    We propose a novel minimum uncertainty approach to relative pose selection for multi-camera self-calibration. We show how\\u000a this discrete global optimization problem can be expressed as a shortest triangle paths problem. For the latter, we present\\u000a an efficient algorithm and prove its correctness. It has several advantages compared to a similar approach of Vergés-Llahí,\\u000a Moldovan and Wada. In quantitative experiments

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

    J. Sussmann; Guoqing Tang

    1991-01-01

    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

  15. Algorithms for the Shortest and Closest Lattice Vector Problems

    E-print Network

    Hanrot, Guillaume

    Algorithms for the Shortest and Closest Lattice Vector Problems Guillaume Hanrot and Xavier Pujol of the art solvers of the Shortest and Closest Lattice Vector Problems in the Euclidean norm. We recall the three main families of algorithms for these problems, namely the algo- rithm by Micciancio and Voulgaris

  16. Backbones and borders from shortest-path trees

    NASA Astrophysics Data System (ADS)

    Grady, Daniel; Thiemann, Christian; Brockmann, Dirk

    2011-03-01

    One of the most important tasks in complex network research is to distinguish between vertices and edges that are topologically essential and those that are not. To this end, a variety of vertex and edge centrality measures have been introduced, ranging from measuring local properties (degree, strength) to quantities that depend on the global structure of the graph (betweenness). Here we introduce a novel technique based on the family of shortest-path trees, which is applicable to strongly heterogeneous networks. This approach can identify significant edges in the network, distinct from conventional edge betweenness, and these edges make up a network backbone relevant to dynamical processes that evolve on such networks. We will show that important network structures can be extracted by investigating the similarity and differences of shortest-path trees and show that tree dissimilarity in combination with hierarchical clustering can identify communities in heterogeneous networks more successfully than ordinary reciprocal-weight distance measures. We demonstrate the success of this technique on complex multi-scale mobility networks.

  17. A new approach to shortest paths on networks based on the quantum bosonic mechanism

    NASA Astrophysics Data System (ADS)

    Jiang, Xin; Wang, Hailong; Tang, Shaoting; Ma, Lili; Zhang, Zhanli; Zheng, Zhiming

    2011-01-01

    This paper presents quantum bosonic shortest path searching (QBSPS), a natural, practical and highly heuristic physical algorithm for reasoning about the recognition of network structure via quantum dynamics. QBSPS is based on an Anderson-like itinerant bosonic system in which a boson's Green function is used as a navigation pointer for one to accurately approach the terminals. QBSPS is demonstrated by rigorous mathematical and physical proofs and plenty of simulations, showing how it can be used as a greedy routing to seek the shortest path between different locations. In methodology, it is an interesting and new algorithm rooted in the quantum mechanism other than combinatorics. In practice, for the all-pairs shortest-path problem in a random scale-free network with N vertices, QBSPS runs in O(?(N) ln ln N) time. In application, we suggest that the corresponding experimental realizations are feasible by considering path searching in quantum optical communication networks; in this situation, the method performs a pure local search on networks without requiring the global structure that is necessary for current graph algorithms.

  18. Membrane Boundary Extraction Using a Circular Shortest Path Technique

    NASA Astrophysics Data System (ADS)

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

    2007-11-01

    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.

  19. Pomelo: Accurate and Decentralized Shortest-path Distance Estimation in Social Graphs

    E-print Network

    Hong, Jason I.

    Pomelo: Accurate and Decentralized Shortest-path Distance Estimation in Social Graphs Zhuo Chen1 the graph structure well. In this paper, we propose Pomelo, which calculates the graph coordinates in a decentralized manner. Every node in Pomelo computes its shortest-path distances to both nearby neighbors

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

    E-print Network

    Mitchell, Joseph S.B.

    orientation" metric, yielding an O(n log n ) approximation algorithm for finding Euclidean shortest pathsAn Optimal Algorithm for L1 Shortest Paths Among Obstacles in the Plane (Draft) Joseph S. B 11794-3600 jsbm@ams.sunysb.edu Abstract We present an optimal (n log n) algorithm for determining

  1. Using Edge-Valued Decision Diagrams for Symbolic Generation of Shortest Paths

    Microsoft Academic Search

    Gianfranco Ciardo; Radu Siminiceanu

    2002-01-01

    We present a new method for the symbolic construction of shortest paths in reachability graphs. Our algorithm relies on a variant of edge{valued decision diagrams that supports ecien t xed{p oint it- erations for the joint computation of both the reachable states and their distance from the initial states. Once the distance function is known, a shortest path from an

  2. Formal language constrained path problems

    SciTech Connect

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

    1997-07-08

    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.

  3. Color texture classification using shortest paths in graphs.

    PubMed

    de Mesquita Sa Junior, Jarbas Joaci; Cortez, Paulo Cesar; Backes, Andre Ricardo

    2014-09-01

    Color textures are among the most important visual attributes in image analysis. This paper presents a novel method to analyze color textures by modeling a color image as a graph in two different and complementary manners (each color channel separately and the three color channels altogether) and by obtaining statistical moments from the shortest paths between specific vertices of this graph. Such an approach allows to create a set of feature vectors, which were extracted from VisTex, USPTex, and TC00013 color texture databases. The best classification results were 99.07%, 96.85%, and 91.54% (LDA with leave-one-out), 87.62%, 66.71%, and 88.06% (1NN with holdout), and 98.62%, 96.16%, and 91.34% (LDA with holdout) of success rate (percentage of samples correctly classified) for these three databases, respectively. These results prove that the proposed approach is a powerful tool for color texture analysis to be explored. PMID:24988594

  4. Shortest Traversal Path of n Circles in Layered Manufacturing Applications

    Microsoft Academic Search

    Chang-chien Chou; Yu-kumg Chen; Shuo-yan Chou

    2007-01-01

    Layered manufacturing in rapid prototyping is to fabricate prototype by using a laser beam to trace the cross-sectional contours of a product layer by layer. Such cross-sections of geometrical objects differ by layers and generally have more than one continuous contour in each layer. In an attempt to facilitate an efficient approach for path planning, the problem is simplified by

  5. PHA*: Finding the Shortest Path with A* in An Unknown Physical Environment

    E-print Network

    Ben-Yair, A; Kraus, S; Netanyahu, N; Stern, R; 10.1613/jair.1373

    2011-01-01

    We address the problem of finding the shortest path between two points in an unknown real physical environment, where a traveling agent must move around in the environment to explore unknown territory. We introduce the Physical-A* algorithm (PHA*) for solving this problem. PHA* expands all the mandatory nodes that A* would expand and returns the shortest path between the two points. However, due to the physical nature of the problem, the complexity of the algorithm is measured by the traveling effort of the moving agent and not by the number of generated nodes, as in standard A*. PHA* is presented as a two-level algorithm, such that its high level, A*, chooses the next node to be expanded and its low level directs the agent to that node in order to explore it. We present a number of variations for both the high-level and low-level procedures and evaluate their performance theoretically and experimentally. We show that the travel cost of our best variation is fairly close to the optimal travel cost, assuming t...

  6. Shortest-path and hot-potato routing on unbuffered 2-D tori

    Microsoft Academic Search

    Miltos D. Grammatikakis; Miro Kraetzl; Eric Fleury

    1997-01-01

    We probabilistically model dynamic routing on unbuffered 2-dimensional tori. We consider shortest-path routing with packet loss and retransmissions versus a newly proposed all-link busy (ALB) hot-potato routing strategy with packet deflections. Computations of the sustained packet generating rate, node throughput, and average packet latency indicate that the proposed ALB strategy is a much better alternative to a shortest-path routing on

  7. Fast Point-to-Point Shortest Path Computations with Arc-Flags

    Microsoft Academic Search

    Moritz Hilger; Rolf H. Mohring; Heiko Schilling

    2006-01-01

    In this paper, we conduct a detailed study of the arc-flag approach introduced in (Lau97, Lau04). Arc-flags are a modification of Dijkstra's algorithm to accel erate point-to-point (p2p) shortest path computa- tions. The usage of arc-flags avoids exploring unnecessary p aths during shortest path query computations. We present two improvements of the original arc-flag method tha t reduce the pre-calculation

  8. Robust constrained shortest path problems under budgeted ...

    E-print Network

    2014-09-12

    The proposed solution approaches have been coded in JAVA and our numerical experiments have been carried out on an Intel(R) Core(TM) i7 CPU M 620, 2.67 GHz, 4 ..... Robust discrete optimization and its applications, volume 14. Springer

  9. Traffic-engineering-aware shortest-path routing and its application in IP-over-WDM networks [Invited

    Microsoft Academic Search

    Youngseok Lee; Biswanath Mukherjee

    2004-01-01

    Single shortest-path routing is known to perform poorly for Internet traffic engineering (TE) where the typical optimization objective is to minimize the maximum link load. Splitting traffic uniformly over equal-cost multiple shortest paths in open shortest path first and intermediate system-intermediate system protocols does not always minimize the maximum link load when multiple paths are not carefully selected for the

  10. Traffic Grooming Based on Shortest Path in Optical WDM Mesh Networks

    E-print Network

    Lee, Tae-Jin

    propose Shortest-path First Traffic grooming(SFT) algo- rithm. The comprehensive computer simulation shows-path First Traffic grooming (SFT) algorithm in objective to maximize the network throughput and to minimize together and carried. According to the computer simulation, the SFT algorithm achieves 14% improved

  11. Traveling salesman path problems

    E-print Network

    Lam, Fumei

    2005-01-01

    In the Traveling Salesman Path Problem, we are given a set of cities, traveling costs between city pairs and fixed source and destination cities. The objective is to find a minimum cost path from the source to destination ...

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

    NASA Astrophysics Data System (ADS)

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

    2007-06-01

    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.

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

    E-print Network

    Imai, Hiroshi

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

  14. Spatial interpolation of fine particulate matter concentrations using the shortest wind-field path distance.

    PubMed

    Li, Longxiang; Gong, Jianhua; Zhou, Jieping

    2014-01-01

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

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

    PubMed Central

    Li, Longxiang; Gong, Jianhua; Zhou, Jieping

    2014-01-01

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

  16. Disambiguating Road Names in Text Route Descriptions using Exact-All-Hop Shortest Path Algorithm

    E-print Network

    Klippel, Alexander

    Disambiguating Road Names in Text Route Descriptions using Exact-All-Hop Shortest Path Algorithm issues involved, road name disambiguation is the most important, because one road name can refer to more than one road. Compared with traditional toponym (place name) disambiguation, the challenges

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

    E-print Network

    Levinson, David M.

    (10). Zhu, Shanjiang, David Levinson and Henry Liu, Measuring Winners and Losers from New I 35W Mississippi (67%) #12;#12;Diversity in Commute Route (Source: Zhu and Levinson 2010b) #12;Conclusions · MajorityDo People Use the Shortest Path? Empirical Test of Wardrop's First Principle Shanjiang Zhu, Ph

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

    E-print Network

    2011-03-15

    algorithm-specific details of the computational experiments and presents computational results ... Figure 1 displays a visualization of a pricing problem and its solution. ...... European Journal of Operational Research, 100:180–191, 1997.

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

    PubMed

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

    2014-10-22

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

  20. Transitive functional annotation by shortest-path analysis of gene expression data

    PubMed Central

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

    2002-01-01

    Current methods for the functional analysis of microarray gene expression data make the implicit assumption that genes with similar expression profiles have similar functions in cells. However, among genes involved in the same biological pathway, not all gene pairs show high expression similarity. Here, we propose that transitive expression similarity among genes can be used as an important attribute to link genes of the same biological pathway. Based on large-scale yeast microarray expression data, we use the shortest-path analysis to identify transitive genes between two given genes from the same biological process. We find that not only functionally related genes with correlated expression profiles are identified but also those without. In the latter case, we compare our method to hierarchical clustering, and show that our method can reveal functional relationships among genes in a more precise manner. Finally, we show that our method can be used to reliably predict the function of unknown genes from known genes lying on the same shortest path. We assigned functions for 146 yeast genes that are considered as unknown by the Saccharomyces Genome Database and by the Yeast Proteome Database. These genes constitute around 5% of the unknown yeast ORFome. PMID:12196633

  1. Scaling of average weighted shortest path and average receiving time on weighted hierarchical networks

    NASA Astrophysics Data System (ADS)

    Sun, Yu; Dai, Meifeng; Xi, Lifeng

    Recent work on the networks has focused on the weighted hierarchical networks that are significantly different from the un-weighted hierarchical networks. In this paper we study a family of weighted hierarchical networks which are recursively defined from an initial uncompleted graph, in which the weights of edges have been assigned to different values with certain scale. Firstly, we study analytically the average weighted shortest path (AWSP) on the weighted hierarchical networks. Using a recursive method, we determine explicitly the AWSP. The obtained rigorous solution shows that the networks grow unbounded but with the logarithm of the network size, while the weighted shortest paths stay bounded. Then, depending on a biased random walk, we research the mean first-passage time (MFPT) between a hub node and any peripheral node. Finally, we deduce the analytical expression of the average of MFPTs for a random walker originating from any node to first visit to a hub node, which is named as the average receiving time (ART). The obtained result shows that ART is bounded or grows sublinearly with the network order relating to the number of initial nodes and the weighted factor or grows quadratically with the iteration.

  2. Identification of Age-Related Macular Degeneration Related Genes by Applying Shortest Path Algorithm in Protein-Protein Interaction Network

    PubMed Central

    Zhang, Jian; Jiang, Min; Yuan, Fei; Feng, Kai-Yan; Cai, Yu-Dong; Xu, Xun; Chen, Lei

    2013-01-01

    This study attempted to find novel age-related macular degeneration (AMD) related genes based on 36 known AMD genes. The well-known shortest path algorithm, Dijkstra's algorithm, was applied to find the shortest path connecting each pair of known AMD related genes in protein-protein interaction (PPI) network. The genes occurring in any shortest path were considered as candidate AMD related genes. As a result, 125 novel AMD genes were predicted. The further analysis based on betweenness and permutation test indicates that there are 10 genes involved in the formation or development of AMD and may be the actual AMD related genes with high probability. We hope that this contribution would promote the study of age-related macular degeneration and discovery of novel effective treatments. PMID:24455700

  3. The tomography of human mobility -- what do shortest-path trees reveal?

    NASA Astrophysics Data System (ADS)

    Grady, Daniel; Thiemann, Christian; Brockmann, Dirk

    2010-03-01

    Similar to illustrating the anatomy of organs using pictures of tissue slices taken at various depths, we construct shortest-path trees of different nodes to create a tomogram of large-scale mobility networks. This tomography allows us to measure global properties of the system conditioned on a reference location in the network to gain a fuller characterization of a node. Using this technqiue, we discovered a new symmetry that characterizes a large class of mobility networks. Furthermore, introducing the notion of tree similarity, we devised a new technique for clustering nodes with similar topological footprint, yielding a new, unique and efficient method for community identification in these networks and extracting their topological backbone. We applied these methods to a multi-scale human mobility network obtained from the dollar-bill-tracking site wheresgoerge.com and to the U.S. and world-wide air transportation network.

  4. 2-D\\/3-D multiply transmitted, converted and reflected arrivals in complex layered media with the modified shortest path method

    Microsoft Academic Search

    Chao-Ying Bai; Xiao-Ping Tang; Rui Zhao

    2009-01-01

    Grid-cell based schemes for tracing seismic arrivals, such as the finite difference eikonal equation solver or the shortest path method (SPM), are conventionally confined to locating first arrivals only. However, later arrivals are numerous and sometimes of greater amplitude than the first arrivals, making them valuable information, with the potential to be used for precise earthquake location, high-resolution seismic tomography,

  5. Technical note: Quantification of neurocranial shape variation using the shortest paths connecting pairs of anatomical landmarks.

    PubMed

    Morita, Yusuke; Ogihara, Naomichi; Kanai, Takashi; Suzuki, Hiromasa

    2013-08-01

    Three-dimensional geometric morphometric techniques have been widely used in quantitative comparisons of craniofacial morphology in humans and nonhuman primates. However, few anatomical landmarks can actually be defined on the neurocranium. In this study, an alternative method is proposed for defining semi-landmarks on neurocranial surfaces for use in detailed analysis of cranial shape. Specifically, midsagittal, nuchal, and temporal lines were approximated using Bezier curves and equally spaced points along each of the curves were defined as semi-landmarks. The shortest paths connecting pairs of anatomical landmarks as well as semi-landmarks were then calculated in order to represent the surface morphology between landmarks using equally spaced points along the paths. To evaluate the efficacy of this method, the previously outlined technique was used in morphological analysis of sexual dimorphism in modern Japanese crania. The study sample comprised 22 specimens that were used to generate 110 anatomical semi-landmarks, which were used in geometric morphometric analysis. Although variations due to sexual dimorphism in human crania are very small, differences could be identified using the proposed landmark placement, which demonstrated the efficacy of the proposed method. PMID:23868177

  6. A novel method for dendritic spines detection based on directional morphological filter and shortest path.

    PubMed

    Su, Ran; Sun, Changming; Zhang, Chao; Pham, Tuan D

    2014-12-01

    Dendritic spines are tiny membranous protrusions from neuron's dendrites. They play a very important role in the nervous system. A number of mental diseases such as Alzheimer's disease and mental retardation are revealed to have close relations with spine morphologies or spine number changes. Spines have various shapes, and spine images are often not of good quality; hence it is very challenging to detect spines in neuron images. This paper presents a novel pipeline to detect dendritic spines in 2D maximum intensity projection (MIP) images and a new dendrite backbone extraction method is developed in the pipeline. The strategy for the backbone extraction approach is that it iteratively refines the extraction result based on directional morphological filtering and improved Hessian filtering until a satisfactory extraction result is obtained. A shortest path method is applied along a backbone to extract the boundary of the dendrites. Spines are then segmented from the dendrites outside the extracted boundary. Touching spines will be split using a marker-controlled watershed algorithm. We present the results of our algorithm on real images and compare our algorithm with two other spine detection methods. The results show that the proposed approach can detect dendrites and spines more accurately. Measurements and classification of spines are also made in this paper. PMID:25155696

  7. A polynomial-time algorithm for computing a shortest path of bounded curvature amidst moderate obstacles

    E-print Network

    Paris-Sud XI, Université de

    example of a non-holonomic robot is that of a car : assuming 1As we will see below, the optimal path-holonomic robot motion plan- ning 2, 3, 13, 15, 16, 17, 18, 19, 20, 24, 25]. A robot is said to be non wheels of the car is always tangent to the car axis. Though the problem considered in this paper is one

  8. Complexity of path discovery game problems

    Microsoft Academic Search

    Hiroaki Tohyama; Akeo Adachi

    2000-01-01

    In this paper path discovery games are introduced, and complexity of the game problems is studied. It is shown that the path discovery game problem played on directed graphs is PSPACE-complete, and the path discovery game problem played on undirected graphs is in the class SSPACE(nlogn). Moreover, it is shown that the acyclic path discovery game problems played on directed

  9. Shortest-route formulation of mixed-model assembly line balancing problem

    Microsoft Academic Search

    Erdal Erel; Hadi Gökçen

    1999-01-01

    A shortest-route formulation of the mixed-model assembly line balancing problem is presented. Common tasks across models are assumed to exist and these tasks are performed in the same stations. The formulation is based on an algorithm which solves the single-model version of the problem. The mixed-model system is transformed into a single-model system with a combined precedence diagram. The model

  10. Shortest paths for differential drive robots under visibility and sensor constraints

    Microsoft Academic Search

    Jean-Bernard Hayet; Rafael Murrieta-Cid

    Abstract—This article revisits the problem,of planning,short- est paths in terms of distance in the plane (i.e., not in time) for the differential drive robot (DDR) in the absence,of obstacles. We complete,the existing works,by explaining,and,deepening the remarks,made,recently in the literature [10] that exhibited more,cases that what,was,thought,until then. Motivated by that work, we show that there cannot be more than 4-word trajectories

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

    NASA Astrophysics Data System (ADS)

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

    2010-03-01

    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.

  12. Curvature-Constrained Shortest Paths in a Convex Polygon (Extended Abstract)

    E-print Network

    Paris-Sud XI, Université de

    naturally when the point robot models a real-world robot with a mini- mum turning radius; see for example Therese Biedl Sylvain Lazard Steve Robbins§ Subhash Suri¶ Sue Whitesides Abstract Let B be a point robot in robotics, involves planning a collision-free path for a robot moving amid obstacles, and has been widely

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

    Microsoft Academic Search

    Lennart Björneborn

    2006-01-01

    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

  14. All-Pairs Almost Shortest Paths Ausarbeitung des Vortrags von Martin Holzer

    E-print Network

    Brandes, Ulrik

    Grafen. Wird nun die Bedingung der Exaktheit dieser Distanzen etwas aufgeweicht und ein einseiti- ger und das APASP-Problem f¨ur einen Grafen mit einem ein- seitigen additiven Fehler von maximal k l-Emulator zu einem ungewichteten Grafen einen gewichteten Grafen mit derselben Knotenmenge so, dass die Distanz

  15. Geometric SpeedUp Techniques for Finding Shortest Paths in Large Sparse Graphs

    Microsoft Academic Search

    Dorothea Wagner; Thomas Willhalm

    2003-01-01

    In this paper, we consider Dijkstra's algorithm for the single source single target shortestpaths problem in large sparse graphs. The goal is to reduce the response time for onlinequeries by using precomputed information. For the result of the preprocessing, we admit atmost linear space. We assume that a layout of the graph is given. From this layout, in thepreprocessing, we

  16. Relative Improvement by Alternative Solutions for Classes of Simple Shortest Path Problems

    E-print Network

    with Uncertain Data -- Part I: Strings of Pearls Gn with Unbiased Perturbations l l l l l l l l s s s s s s s 3 3 of this section we introduce the considered model in detail: the graph model (string of pearls Gn) and an unbiased.1 The Model We consider the following graph model: Definition 1.1 (string of pearls Gn) Consider a weighted

  17. Relative Improvement by Alternative Solutions for Classes of Simple Shortest Path Problems

    E-print Network

    with Uncertain Data -- Part II: Strings of Pearls Gn,r with Biased Perturbations l l l l l l l l the considered models in detail: the graph model (string of pearls Gn,r) and two different biased perturbation. We finish with conclusions in Section 5. 1.1 The Models Definition 1.1 (string of pearls Gn

  18. The All-Pair Shortest-Path Problem in Shared-Memory Heterogeneous Systems

    E-print Network

    Llanos, Diego R.

    -Arranz, Yuri Torres, Diego R. Llanos, Ph.D., and Arturo Gonzalez-Escribano, Ph.D. Departamento de Inform, ed.). By Hector Ortega-Arranz, Yuri Torres, Diego R. Llanos and Arturo Gonzalez-Escribano Copyright c

  19. Path optimization using sub-Riemannian manifolds with applications to astrodynamics

    E-print Network

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

    2011-01-01

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

  20. Identification of Influenza A/H7N9 Virus Infection-Related Human Genes Based on Shortest Paths in a Virus-Human Protein Interaction Network

    PubMed Central

    Huang, Tao; Cai, Yu-Dong

    2014-01-01

    The recently emerging Influenza A/H7N9 virus is reported to be able to infect humans and cause mortality. However, viral and host factors associated with the infection are poorly understood. It is suggested by the “guilt by association” rule that interacting proteins share the same or similar functions and hence may be involved in the same pathway. In this study, we developed a computational method to identify Influenza A/H7N9 virus infection-related human genes based on this rule from the shortest paths in a virus-human protein interaction network. Finally, we screened out the most significant 20 human genes, which could be the potential infection related genes, providing guidelines for further experimental validation. Analysis of the 20 genes showed that they were enriched in protein binding, saccharide or polysaccharide metabolism related pathways and oxidative phosphorylation pathways. We also compared the results with those from human rhinovirus (HRV) and respiratory syncytial virus (RSV) by the same method. It was indicated that saccharide or polysaccharide metabolism related pathways might be especially associated with the H7N9 infection. These results could shed some light on the understanding of the virus infection mechanism, providing basis for future experimental biology studies and for the development of effective strategies for H7N9 clinical therapies. PMID:24955349

  1. Solving a Hamiltonian Path Problem with a bacterial computer

    Microsoft Academic Search

    Jordan Baumgardner; Karen Acker; Oyinade Adefuye; Samuel Thomas Crowley; Will DeLoache; James O Dickson; Andrew T Martens; Nickolaus Morton; Michelle Ritter; Amber Shoecraft; Jessica Treece; Matthew Unzicker; Amanda Valencia; Mike Waters; A Malcolm Campbell; Laurie J Heyer; Jeffrey L Poet; Todd T Eckdahl

    2009-01-01

    BACKGROUND: The Hamiltonian Path Problem asks whether there is a route in a directed graph from a beginning node to an ending node, visiting each node exactly once. The Hamiltonian Path Problem is NP complete, achieving surprising computational complexity with modest increases in size. This challenge has inspired researchers to broaden the definition of a computer. DNA computers have been

  2. The Longest Path Problem Is Polynomial on Interval Graphs

    NASA Astrophysics Data System (ADS)

    Ioannidou, Kyriaki; Mertzios, George B.; Nikolopoulos, Stavros D.

    The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamiltonian path problem. Motivated by the work of Uehara and Uno in [20], where they left the longest path problem open for the class of interval graphs, in this paper we show that the problem can be solved in polynomial time on interval graphs. The proposed algorithm runs in O(n 4) time, where n is the number of vertices of the input graph, and bases on a dynamic programming approach.

  3. The Complexity of Two Graph Orientation Problems

    Microsoft Academic Search

    N. Eggemann; S. D. Noble

    2010-01-01

    We consider two orientation problems in a graph, namely the minimization of the sum of all the shortest path lengths and the minimization of the diameter. We show that it is NP-complete to decide whether a graph has an orientation such that the sum of all the shortest paths lengths is at most an integer specified in the input. The

  4. Path problems in generalized stars, complete graphs, and brick wall graphs

    Microsoft Academic Search

    Thomas Erlebach; Danica Vukadinovic

    2006-01-01

    Path problems such as the maximum edge-disjoint paths problem, the path coloring problem, and the maximum path coloring problem are relevant for resource allocation in communication networks, in particular all-optical networks. In this paper, it is shown that maximum path coloring can be solved optimally in polynomial time for bidirected generalized stars, even in the weighted case. Furthermore, the maximum

  5. The traffic equilibrium problem with nonadditive path costs

    SciTech Connect

    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

    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.

  6. Pokemon Cards and the Shortest Common Superstring

    Microsoft Academic Search

    Mark Stamp; Austin E Stamp

    2003-01-01

    Evidence is presented that certain sequences of Pokemon cards are determined by selecting consecutive elements from a longer sequence. We then consider the problem of recovering the shortest common superstring (SCS), i.e., the shortest string that contains each of the Pokemon card sequences as a consecutive substring. The SCS problem arises in many applications, most notably in DNA sequencing.

  7. The optimal path-matching problem

    SciTech Connect

    Cunningham, W.H.; Geelen, J.F. [Univ. of Waterloo, Ontario (Canada)

    1996-12-31

    We describe a common generalization of the weighted matching problem and the weighted matroid intersection problem. In this context we present results implying the polynomial-time solvability of the two problems. We also use our results to give the first strongly polynomial separation algorithm for the convex hull of matchable sets of a graph, and the first polynomial-time algorithm to compute the rank of a certain matrix of indeterminates. Our algorithmic results are based on polyhedral characterizations, and on the equivalence of separation and optimization.

  8. Historical Traffic-Tolerant Paths in Road Networks Pui Hang Li Man Lung Yiu

    E-print Network

    Yiu, Man Lung

    paths that mini- mize the aggregate (historical) travel time. Unlike the shortest path problem, the TTP problem has a combinatorial search space that renders the optimal solution expensive to compute. We demonstrate the effectiveness of TTP paths and the efficiency of our proposed algorithms. Categories

  9. Adleman[1] 1994 DNA Hamiltonian Path Problem , DNA

    E-print Network

    1. Adleman[1] 1994 DNA Hamiltonian Path Problem , DNA DNA [2]. DNA DNA , . , , 2 , DNA 4 . DNA 4 A(Adenine), C(Cytosine), G(Guanine), T(Thymine) 2 4 . , . 1 mole 6x10 23 DNA DNA . , . DNA NP-complete [1, 2], [2

  10. Solving a Hamiltonian Path Problem with a bacterial computer

    PubMed Central

    Baumgardner, Jordan; Acker, Karen; Adefuye, Oyinade; Crowley, Samuel Thomas; DeLoache, Will; Dickson, James O; Heard, Lane; Martens, Andrew T; Morton, Nickolaus; Ritter, Michelle; Shoecraft, Amber; Treece, Jessica; Unzicker, Matthew; Valencia, Amanda; Waters, Mike; Campbell, A Malcolm; Heyer, Laurie J; Poet, Jeffrey L; Eckdahl, Todd T

    2009-01-01

    Background The Hamiltonian Path Problem asks whether there is a route in a directed graph from a beginning node to an ending node, visiting each node exactly once. The Hamiltonian Path Problem is NP complete, achieving surprising computational complexity with modest increases in size. This challenge has inspired researchers to broaden the definition of a computer. DNA computers have been developed that solve NP complete problems. Bacterial computers can be programmed by constructing genetic circuits to execute an algorithm that is responsive to the environment and whose result can be observed. Each bacterium can examine a solution to a mathematical problem and billions of them can explore billions of possible solutions. Bacterial computers can be automated, made responsive to selection, and reproduce themselves so that more processing capacity is applied to problems over time. Results We programmed bacteria with a genetic circuit that enables them to evaluate all possible paths in a directed graph in order to find a Hamiltonian path. We encoded a three node directed graph as DNA segments that were autonomously shuffled randomly inside bacteria by a Hin/hixC recombination system we previously adapted from Salmonella typhimurium for use in Escherichia coli. We represented nodes in the graph as linked halves of two different genes encoding red or green fluorescent proteins. Bacterial populations displayed phenotypes that reflected random ordering of edges in the graph. Individual bacterial clones that found a Hamiltonian path reported their success by fluorescing both red and green, resulting in yellow colonies. We used DNA sequencing to verify that the yellow phenotype resulted from genotypes that represented Hamiltonian path solutions, demonstrating that our bacterial computer functioned as expected. Conclusion We successfully designed, constructed, and tested a bacterial computer capable of finding a Hamiltonian path in a three node directed graph. This proof-of-concept experiment demonstrates that bacterial computing is a new way to address NP-complete problems using the inherent advantages of genetic systems. The results of our experiments also validate synthetic biology as a valuable approach to biological engineering. We designed and constructed basic parts, devices, and systems using synthetic biology principles of standardization and abstraction. PMID:19630940

  11. A methodology for predicting minimum travel paths using real-time traffic network data

    E-print Network

    Liu, Chang

    1991-01-01

    , existing traffic simulation and optimization models have been reviewed, and appropriate models have been chosen to predict link travel time and fuel consumption. Link-node types of mathematical networks have been established, and minimum travel distance... Integration of ATMS with ADIS Traffic Data Fusion For Link Time Prediction . . NETWORK ANALYSIS Shortest Path Problem Shortest Path with Fixed-Charges Problem . . STUDY DESIGN REVIEW OF EXISTING TRAFFIC MODELS PASSER II-87 PASSER III-88 TRANSYT-7F...

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

    NASA Astrophysics Data System (ADS)

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

    2012-08-01

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

  13. Prizing on Paths: A PTAS for the Highway Problem

    E-print Network

    Grandoni, Fabrizio

    2010-01-01

    In the highway problem, we are given an n-edge line graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the tolls), the highway owner collects from each driver the weight of the associated path, when it does not exceed the budget of the driver, and zero otherwise. The goal is choosing weights so as to maximize the profit. A lot of research has been devoted to this apparently simple problem. The highway problem was shown to be strongly NP-hard only recently [Elbassioni,Raman,Ray-'09]. The best-known approximation is O(\\log n/\\log\\log n) [Gamzu,Segev-'10], which improves on the previous-best O(\\log n) approximation [Balcan,Blum-'06]. In this paper we present a PTAS for the highway problem, hence closing the complexity status of the problem. Our result is based on a novel randomized dissection approach, which has some points in common with Arora's quadtree dissection for Euclidean network design [Arora-'98]. The basic idea is enclosing the ...

  14. A Specific Genetic Algorithm for Optimum Path Planning in Intelligent Transportation System

    Microsoft Academic Search

    Qing Li; Guangjun Liu; Wei Zhang; Cailu Zhao; Yixin Yin; Zhiliang Wang

    2006-01-01

    A specific genetic algorithm is proposed in this paper for optimum path planning. Operations such as encoding, crossover and mutation are tailored to fit optimum path planning. Simulation results show that the specific genetic algorithm has advantages such as rapid calculation speed and high probability of optimal solution. It is a new approach for solving shortest path problems in practical

  15. Worst-Case Analysis of Network Design Problem Heuristics

    E-print Network

    Wong, Richard T.

    The Optimal Network problem (as defined by Scott [16]) consists of selecting a subset of arcs that minimizes the sum of the shortest paths between all nodes subject to a budget constraint. This paper considers the worst-case ...

  16. Journal of Artificial Intelligence Research 21 (2004) 631670 Submitted 9/03; published 6/04 PHA*: Finding the Shortest Path with A* in An Unknown

    E-print Network

    Felner, Ariel

    2004-01-01

    Journal of Artificial Intelligence Research 21 (2004) 631­670 Submitted 9/03; published 6/04 PHA unknown territory. We introduce the Physical­A* algorithm (PHA*) for solving this problem. PHA* expands by the traveling effort of the moving agent and not by the number of generated nodes, as in standard A*. PHA

  17. Vision-based path planning with obstacle avoidance for mobile robots using linear matrix inequalities

    Microsoft Academic Search

    Weifeng Huang; Anan Osothsilp; Farzad Pourboghrat

    2010-01-01

    In this paper, a vision-based obstacle avoiding path generation problem is considered for autonomous mobile robots under a top-view workspace. The collision-free path planning problem is converted to a convex optimization problem that can be solved numerically using linear matrix inequalities (LMI). A new optimal (shortest) path cost formulation is given for LMI optimization using a novel Line of Sight

  18. Energy-efficient Paths in Radio Networks Rene Beier1

    E-print Network

    Matijevic, Domagoj

    Introduction The shortest-path problem is one of the fundamental problems which has been studied for a long, Cp is a node-dependent offset cost and |pq| denotes the Euclidean distance between p and q. For every in wireless networking. In recent years wireless network technology has gained tremendous importance

  19. Solving the Longest Simple Path Problem with Constraint-Based Techniques

    E-print Network

    Deville, Yves

    an undi- rected weighted graph G = (V,E), the problem consists of finding the longest simple path (i for solving this problem. We show that our techniques give competitive results on different kinds of graphs the longest simple path on a given arbitrary undirected weighted graph. Given an undirected weighted graph G

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

    Microsoft Academic Search

    Stavros G. Kolliopoulos; Clifford Stein

    1998-01-01

    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.

  1. Traffic engineering approach to path selection in optical burst switching networks

    NASA Astrophysics Data System (ADS)

    Teng, Jing; Rouskas, George N.

    2005-11-01

    It is usually assumed that optical burst switching (OBS) networks use the shortest path routing along with next-hop burst forwarding. The shortest path routing minimizes delay and optimizes utilization of resources, however, it often causes certain links to become congested while others remain underutilized. In a bufferless OBS network in which burst drop probability is the primary metric of interest, the existence of a few highly congested links could lead to unacceptable performance for the entire network. We take a traffic engineering approach to path selection in OBS networks with the objective of balancing the traffic across the network links to reduce congestion and to improve overall performance. We present an approximate integer linear optimization problem as well as a simple integer relaxation heuristic to solve the problem efficiently for large networks. Numerical results demonstrate that our approach is effective in reducing the network-wide burst drop probability, in many cases significantly, over the shortest path routing.

  2. Algorithms for an Unmanned Vehicle Path Planning Problem 

    E-print Network

    Qin, Jianglei

    2013-06-25

    Unmanned Vehicles (UVs) have been significantly utilized in military and civil applications over the last decade. Path-planning of UVs plays an important role in effectively using the available resources such as the UVs and sensors as efficiently...

  3. Solving the broken link problem in Walden's Paths 

    E-print Network

    Dalal, Zubin Jamshed

    2004-09-30

    is augmented with information in the form of an annotation. The annotation can include comments about the page, important areas of the page to focus on, additional reference materials and anything else that the author of the path believes will assist... in the assimilation of information contained on the page. The Walden?s Paths tool was originally built for use in the K-12 school environment by teachers, who desire to collect, organize and annotate information available on the Internet...

  4. Integrating analogical mapping and general problem solving: the path-mapping theory

    Microsoft Academic Search

    Dario D. Salvucci; John R. Anderson

    2001-01-01

    This article describes the path-mapping theory of how humans integrate analogical mapping and general problem solving. The theory posits that humans represent analogs with declarative roles, map analogs by lower-level retrieval of analogous role paths, and coordinate mappings with higher-level organizational knowledge. Implemented in the ACT-R cognitive architecture, the path-mapping theory enables models of analogical mapping behavior to incorporate and

  5. System reliability for quickest path problems under time threshold and budget

    Microsoft Academic Search

    Yi-Kuei Lin

    2010-01-01

    Many studies on hardware framework and routing policy are devoted to reducing the transmission time for a computer network. The quickest path problem thus arises to find a path which sends a given amount of data from the source to the sink such that the transmission time is minimized. More specifically, the capacity of each arc in the network is

  6. Path following algorithm for the graph matching problem

    Microsoft Academic Search

    Mikhail Zaslavskiy; Francis Bach; Jean-Philippe Vert

    2008-01-01

    Abstract 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

  7. A Path Following Algorithm for the Graph Matching Problem

    Microsoft Academic Search

    Mikhail Zaslavskiy; Francis R. Bach; Jean-philippe Vert

    2009-01-01

    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.

  8. Constraint Reformulation and a Lagrangian Relaxationbased Solution Algorithm for a Least Expected Time Path Problem

    E-print Network

    Zhou, Xuesong

    Time Path Problem Lixing Yang State Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong for continuous link travel times through variance and other statistics (e.g., Fu and Rilett 1998; Sun, Gu

  9. Local Pruning for Information Dissemination in Dynamic Networks for Solving the Idempotent Semiring Algebraic Path Problem

    E-print Network

    Baras, John S.

    Algebraic Path Problem Kiran K. Somasundaram and John S. Baras Abstract-- We present a method, inspired from networks, broadcasting Kiran K. Somasundaram and John S. Baras are with the Institute for Systems Research

  10. Approximation Algorithms and Heuristics for a 2-depot, Heterogeneous Hamiltonian Path Problem

    E-print Network

    Doshi, Riddhi Rajeev

    2011-10-21

    APPROXIMATION ALGORITHMS AND HEURISTICS FOR A 2-DEPOT, HETEROGENOUS HAMILTONIAN PATH PROBLEM A Thesis by RIDDHI RAJEEV DOSHI Submitted to the Office of Graduate Studies of Texas A&M University in partial fulfillment of the requirements... for the degree of MASTER OF SCIENCE August 2010 Major Subject: Mechanical Engineering APPROXIMATION ALGORITHMS AND HEURISTICS FOR A 2-DEPOT, HETEROGENOUS HAMILTONIAN PATH PROBLEM A Thesis by RIDDHI RAJEEV DOSHI Submitted to the Office of Graduate Studies...

  11. A study of altitude and flight path angle dynamics for a singularly perturbed fuel optimization problem

    NASA Technical Reports Server (NTRS)

    Price, D. B.; Gracey, C.

    1983-01-01

    This short paper will demonstrate that the separation of altitude and flight path angle dynamics using singular perturbation techniques for a transport fuel optimization problem results in an unacceptable oscillation in altitude. A technique for damping this oscillation by adding a penalty term to the cost function for the optimization problem will be discussed. This technique will be compared with a different approach that linearizes the altitude and flight path angle boundary layers.

  12. Constrained Graph Optimization: Interdiction and Preservation Problems

    SciTech Connect

    Schild, Aaron V [Los Alamos National Laboratory

    2012-07-30

    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.

  13. Solving the empty space problem in robot path planning by mathematical morphology 1

    E-print Network

    Roerdink, Jos B.T.M.

    , say a robot or a car, moving in a space (called `work space') with obstacles. The problem falls apartSolving the empty space problem in robot path planning by mathematical morphology 1 J into two distinct subproblems [3]. First, the empty­space problem: find the allowed states of the robot 1

  14. A PATH RELINKING APPROACH FOR THE GENERALIZED ASSIGNMENT PROBLEM

    Microsoft Academic Search

    M. Yagiura; T. Ibaraki; F. Glover

    2002-01-01

    The generalized assignment problem is a classical combina- torial optimization problem known to be NP-hard. It can model a variety of real world applications in location, allocation, ma- chine assignment, and supply chains. Researchers have studied the problem since the late 1960s, and computer codes for practi- cal applications emerged in the early 1970s. We propose a new algorithm for

  15. PATH

    SciTech Connect

    Su, S.D.; Baylor, K.J.; Engholm, B.A. (CEGA Corporation, San Diego, CA (United States))

    1987-05-01

    PATH is a highly flexible shielding code utilizing the common point-kernel integration technique primarily for treating gamma radiation from reactors, radioactive components and from complex piping systems. Major features of the code include complex geometry capability, various source options, extensive data library, simple but flexible input and well-organized output format.

  16. Traveling Salesperson Problems for the Dubins Vehicle

    Microsoft Academic Search

    Ketan Savla; Emilio Frazzoli; Francesco Bullo

    2008-01-01

    In this paper, we study minimum-time motion planning and routing problems for the Dubins vehicle, i.e., a nonholonomic vehicle that is constrained to move along planar paths of bounded curvature, without reversing direction. Motivated by autonomous aerial vehicle applications, we consider the traveling salesperson problem for the Dubins vehicle (DTSP): given n points on a plane, what is the shortest

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

  18. Combining a Probabilistic Sampling Technique and Simple Heuristics to solve the Dynamic Path Planning Problem

    E-print Network

    Barriga, Nicolas A; Solar, Mauricio

    2009-01-01

    Probabilistic sampling methods have become very popular to solve single-shot path planning problems. Rapidly-exploring Random Trees (RRTs) in particular have been shown to be very efficient in solving high dimensional problems. Even though several RRT variants have been proposed to tackle the dynamic replanning problem, these methods only perform well in environments with infrequent changes. This paper addresses the dynamic path planning problem by combining simple techniques in a multi-stage probabilistic algorithm. This algorithm uses RRTs as an initial solution, informed local search to fix unfeasible paths and a simple greedy optimizer. The algorithm is capable of recognizing when the local search is stuck, and subsequently restart the RRT. We show that this combination of simple techniques provides better responses to a highly dynamic environment than the dynamic RRT variants.

  19. Path Integral Approach to Reaction in Complex Environment:. a Bottleneck Problem

    Microsoft Academic Search

    V. Sa-Yakanit; S. Boribarn

    2001-01-01

    The path integral method for handling the polaron problem, as developed by Feynman [1], is applied to the problem of the rate of reaction of a system coupled to a complex environment consisting of an infinite set of oscillators. After eliminating the harmonic oscillator degrees of freedom, an effective action containing a reaction coordinate coupled to the non-local harmonic oscillator,

  20. Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems

    Microsoft Academic Search

    R. Ravi; Amitabh Sinha

    2004-01-01

    We study the design of approximation algorithms for stoch- astic combinatorial optimization problems. We formulate the problems in the framework of two-stage stochastic optimization, and provide nearly tight approximations. Our problems range from the simple (shortest path, vertex cover, bin packing) to complex (facility location, set cover), and contain representatives with different approximation ratios. The approximation ratio of the stochastic

  1. Relaxed Tours and Path Ejections for the Traveling Salesman Problem

    Microsoft Academic Search

    César Rego

    1996-01-01

    We describe an edge based ejection chain method to generate compoundneighborhood structures for the Traveling Salesman Problem. These neighborhoodstructures enclose a special substructure which is not necessarilya Hamiltonian tour. Instead the neighborhood components are linked togetherto compose successive levels of an ejection chain, and coordinated bya suitable reference structure to generate compound moves with outstandingproprieties. More precisely, such a substructure

  2. A Path Following Algorithm for the Graph Matching Problem

    E-print Network

    Bach, Francis

    of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting graphs, QAPLib, retina vessel images, and handwritten Chinese characters. In all cases, the results, gradient methods, machine learning, classification, image processing. Ç 1 INTRODUCTION THE graph matching

  3. Algorithms for an Unmanned Vehicle Path Planning Problem

    E-print Network

    Qin, Jianglei

    2013-06-25

    -degree for each vertex in the graph except the root. Here is the constraint, The last constraint makes sure that there?s only one arc out of root o. Now we get the integer program for the quota problem, which is as below, fij k j?V ? = f jik j... this constraint: x e e?? (S ) ? + zN N ?S ? ? 1 S ? V \\{o} To ensure that there is at most one subset N that satisfies zN = 1, we add a second constraint: zN N?V \\{o} ? ? 1 Noting that because of the second term of the objective function...

  4. Restoration by Path Concatenation: Fast Recovery of MPLS Paths

    E-print Network

    Bremler-Barr, Anat

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

  5. Restoration by Path Concatenation: Fast Recovery of MPLS Paths

    E-print Network

    Kaplan, Haim

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

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

    ERIC Educational Resources Information Center

    Stevens, Ronald H.

    1991-01-01

    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…

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

    ERIC Educational Resources Information Center

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

    2010-01-01

    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…

  8. Path Difference Learning for Guitar Fingering Problem Aleksander Radisavljevic and Peter Driessen

    E-print Network

    Driessen, Peter F.

    music notation evolved to include occasional fingering information such as fret number or finger label tablatures (Harris, 1999), (OLGA, 2004). Since this learning procedure seeks to minimize the differencePath Difference Learning for Guitar Fingering Problem Aleksander Radisavljevic and Peter Driessen

  9. The evolution of DNA computing: nature's solution to a path problem

    Microsoft Academic Search

    Laura F. Landweber

    1998-01-01

    How do cells and nature “compute”? They read and “rewrite” DNA all the time, by processes that modify sequence at the DNA or RNA level. Adleman (1994) reported an elegant solution to a seven city directed Hamiltonian path problem using DNA. This launched the new field of DNA computers, which in four years has become an international focus. However, unknown

  10. Root-cause analysis of SAN performance problems: an I\\/O path affine search approach

    Microsoft Academic Search

    David Breitgand; Ealan Henis; Edya Ladan-mozes; Onn Shehory; Elena Yerushalmi

    2005-01-01

    We present a novel algorithm, called IPASS, for root cause analysis of performance prob- lems in Storage Area Networks (SANs). The algorithm uses configuration information available in a typical SAN to construct I\\/O paths, that connect between consumers and providers of the storage resources. When a performance problem is reported for a storage consumer in the SAN, IPASS uses the

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

    PubMed Central

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

    2010-01-01

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

  12. High-order path-integral Monte Carlo methods for solving quantum dot problems.

    PubMed

    Chin, Siu A

    2015-03-01

    The conventional second-order path-integral Monte Carlo method is plagued with the sign problem in solving many-fermion systems. This is due to the large number of antisymmetric free-fermion propagators that are needed to extract the ground state wave function at large imaginary time. In this work we show that optimized fourth-order path-integral Monte Carlo methods, which use no more than five free-fermion propagators, can yield accurate quantum dot energies for up to 20 polarized electrons with the use of the Hamiltonian energy estimator. PMID:25871047

  13. Flows with Unit Path Capacities and Related Packing and Covering Problems

    E-print Network

    Nabben, Reinhard

    of flow sent along path P P: max P P xP min aA u(a)ya + P P zP s.t. P a xP u(a) a A (1) s.t. zP + aP yaFlows with Unit Path Capacities and Related Packing and Covering Problems Maren Martens1 and Martin and Fulkerson in the 1950s, network flow theory is one of the most important and most active areas of research

  14. The complexity of two graph orientation problems

    Microsoft Academic Search

    Nicole Eggemannand; Steven D. Noble

    2010-01-01

    We consider two orientation problems in a graph, namely the minimization of the sum of all the shortest path lengths and the minimization of the diameter. Our main result is that for each positive integer k, there is a linear-time algorithm that decides for a planar graph G whether there is an orientation for which the diameter is at most

  15. CS 105: Algorithms (Grad) Solving Shortest Superstring via Set Cover

    E-print Network

    Chakrabarti, Amit

    CS 105: Algorithms (Grad) Solving Shortest Superstring via Set Cover Khanh Do Ba Feb 24, 2005 1 Recap: Minimum Set Cover Recall the (Weighted) Set Cover problem, defined as follows. Set Cover Problem. First, the algorithm is as follows. Algorithm 1: GreedySetCover(X, F) C - 1 U - X2 while U = do3 Find

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

    NASA Astrophysics Data System (ADS)

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

    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.

  17. Metabolic PathFinding: inferring relevant pathways in biochemical networks.

    PubMed

    Croes, Didier; Couche, Fabian; Wodak, Shoshana J; van Helden, Jacques

    2005-07-01

    Our knowledge of metabolism can be represented as a network comprising several thousands of nodes (compounds and reactions). Several groups applied graph theory to analyse the topological properties of this network and to infer metabolic pathways by path finding. This is, however, not straightforward, with a major problem caused by traversing irrelevant shortcuts through highly connected nodes, which correspond to pool metabolites and co-factors (e.g. H2O, NADP and H+). In this study, we present a web server implementing two simple approaches, which circumvent this problem, thereby improving the relevance of the inferred pathways. In the simplest approach, the shortest path is computed, while filtering out the selection of highly connected compounds. In the second approach, the shortest path is computed on the weighted metabolic graph where each compound is assigned a weight equal to its connectivity in the network. This approach significantly increases the accuracy of the inferred pathways, enabling the correct inference of relatively long pathways (e.g. with as many as eight intermediate reactions). Available options include the calculation of the k-shortest paths between two specified seed nodes (either compounds or reactions). Multiple requests can be submitted in a queue. Results are returned by email, in textual as well as graphical formats (available in http://www.scmbb.ulb.ac.be/pathfinding/). PMID:15980483

  18. Development of a potential field estimator for a path-planning application using neural networks 

    E-print Network

    Smith, Darin William

    1997-01-01

    . . . . . . . . . . . b. Attractive and Repulsive Potentials B. Operational Space Approach . 1. Shortest Path Computation . a. Graph Theory b. Methodology for the SSRMS Problem . BACK-PROPAGATION ARTIFICIAL NEURAL NETWORK THEORY A. IvIotivation . 1. Fuzzy Logic 2... advantages and disadvantages with respe&t to the others. 1. Fuzzy Logic The particular problem being studied is known as a classilication problem. Harral has developed an aircraft situation recognizer using fuzzy logi&:l5). The situation rccognizer...

  19. A non–interior predictor–corrector path following algorithm for the monotone linear complementarity problem

    Microsoft Academic Search

    Jim Burke; Song Xu

    2000-01-01

    .   We present a predictor–corrector non–interior path following algorithm for the monotone linear complementarity problem based\\u000a on Chen–Harker–Kanzow–Smale smoothing techniques. Although the method is modeled on the interior point predictor–corrector\\u000a strategies, it is the first instance of a non–interior point predictor–corrector algorithm. The algorithm is shown to be both\\u000a globally linearly convergent and locally quadratically convergent under standard hypotheses. The

  20. Finding the dominant energy transmission paths in statistical energy analysis

    NASA Astrophysics Data System (ADS)

    Guasch, Oriol; Aragonès, Àngels

    2011-05-01

    A key issue for noise, vibration and harshness purposes, when modelling the vibroacoustic behaviour of a system, is that of determining how energy is transmitted from a given source, where external energy is being input, to a target where energy is to be reduced. In many situations of practical interest, a high percentage of the transmitted energy is driven by a limited set of dominant paths. For instance, this is at the core of the existence of transmission loss regulations between dwellings. In this work, it is shown that in the case of a system modelled with statistical energy analysis (SEA), the problem of ranking dominant paths can be posed as a variation of the so-called K shortest path problem in graph theory. An algorithm for the latter is then modified and adapted to obtain the sorted set of K dominant energy transmission paths in a SEA model. A numerical example to show its potential for practical applications is included.

  1. Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem

    Microsoft Academic Search

    Andreas T. Ernst; Mohan Krishnamoorthy

    1998-01-01

    In this paper new MILP formulations for the multiple allocation p-hub median problem are presented. These require fewer variables and constraints than those traditionally used in the literature. An efficient heuristic algorithm, based on shortest paths, is described. LP based solution methods as well as an explicit enumeration algorithm are developed to obtain exact solutions. Computational results are presented for

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

    Microsoft Academic Search

    Ketan Savla; Francesco Bullo; Emilio Frazzoli

    2005-01-01

    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

  3. CS 533: Computational Geometry Computational geometry addresses data structures and algorithms for solving geometric problems.

    E-print Network

    Heller, Barbara

    Geographic Information Systems, Graphics, Robotics, Numerical methods, Bio-Informatics etc. Consider, common problems include ray-shooting to determine the first object in the line of sight, space Shortest paths with applications in Robotics BSP-trees and applications in graphics. Edited March 2006

  4. Proximity Problems and the Voronoi Diagram an a Rectilinear Plane with Rectangular Obstacles

    Microsoft Academic Search

    Sumanta Guha; Ichiro Suzuki

    1993-01-01

    We consider the following four problems for a set S of k points on a plane, equipped with the rectilinear metric and containing a set R of n disjoint rectangular obstacles (so that distance is measured by a shortest rectilinear path avoiding obstacles in R): (a) find a closest pair of points in S, (b) find a nearest neighbor for

  5. Proximity Problems for Points on a Rectilinear Plane with Rectangular Obstacles

    Microsoft Academic Search

    S. Guha; I. Suzuki

    1997-01-01

    We consider the following four problems for a set S of k points on a plane, equippedwith the rectilinear metric and containing a set R of n disjoint rectangular obstacles (sothat distance is measured by a shortest rectilinear path avoiding obstacles in R): (a) finda closest pair of points in S, (b) find a nearest neighbor for each point in

  6. Multi-objective stochastic path planning 

    E-print Network

    Dasgupta, Sumantra

    2009-05-15

    of multiple objectives and stochastic edge parameters. 2. Identify candidate constraints where clustering based multi-level programming can be applied to eliminate infeasible edges. 3. Provide an exact O (V.E) algorithm for building redundant shortest paths. 4...

  7. Finding the Shortest Hamiltonian Circuit of Selected Places in Penang Using a Generic Bee Colony Optimization Framework

    Microsoft Academic Search

    Li-Pei Wong; Malcolm Yoke Hean Low; Chin Soon Chong

    2011-01-01

    Identifying the shortest Hamiltonian circuit is a task which appears in various types of industrial and logistics applications. It is a NP-hard problem (1). This paper intends to find the shortest Hamiltonian circuit of the selected 68 towns\\/cities in Penang state, Malaysia using the generic Bee Colony Optimization (BCO) framework (2). The proposed BCO framework realizes computationally the foraging process

  8. Multiple paths extraction in images using a constrained expanded trellis.

    PubMed

    Sun, Changming; Appleton, Ben

    2005-12-01

    Single shortest path extraction algorithms have been used in a number of areas such as network flow and image analysis. In image analysis, shortest path techniques can be used for object boundary detection, crack detection, or stereo disparity estimation. Sometimes one needs to find multiple paths as opposed to a single path in a network or an image where the paths must satisfy certain constraints. In this paper, we propose a new algorithm to extract multiple paths simultaneously within an image using a constrained expanded trellis (CET) for feature extraction and object segmentation. We also give a number of application examples for our multiple paths extraction algorithm. PMID:16355660

  9. Visibility-Polygon Search and Euclidean Shortest Paths

    Microsoft Academic Search

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

    1985-01-01

    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

  10. Watershed Cuts: Thinnings, Shortest Path Forests, and Topological Watersheds

    Microsoft Academic Search

    Jean Cousty; Gilles Bertrand; Laurent Najman; Michel Couprie

    2010-01-01

    We recently introduced watershed cuts, a notion of watershed in edge-weighted graphs. In this paper, our main contribution is a thinning paradigm from which we derive three algorithmic watershed cut strategies: The first one is well suited to parallel implementations, the second one leads to a flexible linear-time sequential implementation, whereas the third one links the watershed cuts and the

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

    Microsoft Academic Search

    Frank Pajares; M. David Miller

    1994-01-01

    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,

  12. The capacitated multiple allocation hub location problem: Formulations and algorithms

    Microsoft Academic Search

    Jamie Ebery; Mohan Krishnamoorthy; Andreas T. Ernst; Natashia Boland

    2000-01-01

    In this paper we consider and present formulations and solution approaches for the capacitated multiple allocation hub location problem. We present a new mixed integer linear programming formulation for the problem. We also construct an efficient heuristic algorithm, using shortest paths. We incorporate the upper bound obtained from this heuristic in a linear-programming-based branch-and-bound solution procedure. We present the results

  13. The Complexity of Two Graph Orientation Problems

    E-print Network

    Eggemann, N

    2010-01-01

    We consider two orientation problems in a graph, namely the minimization of the sum of all the shortest path lengths and the minimization of the diameter. We show that it is NP-complete to decide whether a graph has an orientation such that the sum of all the shortest paths lengths is at most an integer specified in the input. The proof is a short reduction from a result of Chv\\'atal and Thomassen showing that it is NP-complete to decide whether a graph can be oriented so that its diameter is at most 2. In contrast, for each positive integer k, we describe a linear-time algorithm that decides for a planar graph G whether there is an orientation for which the diameter is at most k. We also extend this result from planar graphs to any minor-closed family not containing all apex graphs.

  14. On Dirac-Coulomb problem in (2+1) dimensional space-time and path integral quantization

    SciTech Connect

    Haouat, S. [L.P.Th, Departement de physique, Universite de Jijel, BP 98, Ouled Aissa, Jijel 18000 (Algeria); Chetouani, L. [Departement de Physique, Faculte de Sciences, Universite Mentouri, Route Ain El-Bey, Constantine 25000 (Algeria)

    2012-06-15

    The problem of Dirac particle interacting with Coulomb potential in (2+1) dimensions is formulated in the framework of super-symmetric path integrals where the spin degrees of freedom are described by odd Grassmannian variables. The relative propagator is expressed through Cartesian coordinates in a Hamiltonian form by the use of an adequate transformation. The passage to the polar coordinates permitted us to calculate the fixed energy Green's function and to extract bound states and associating wave functions.

  15. Using An Efficient Collision Detector In The Solution Of The Find-Path Problem Of Industrial Robots

    NASA Astrophysics Data System (ADS)

    Sawatzky, G.; El-Zorkany, H.

    1985-12-01

    In this paper an efficient approach to collision detection is proposed. Its incorporation in two approaches for the solution of the find-path problem is also presented. Collision detector is based on representing objects by a hierarchy of bounding spheres. Features of the collision detector are that computation time depends on the proximity of the objects and that the method concentrates its efforts on the parts of objects most likely to have geometric interference as determined by collision information. The use of this representation for collision detection in two approaches for the solution of the find-path problem, namely a generate and test approach and a free space representation based approach, are presented. The paper is organized as follows. First, a review of the literature is given. Second, details of the collision detector and its incorporation in a solution for the find-path problem are presented. Third, the implementation of this approach on a LISP machine and the preliminary performance tests performed using a PUMA 560 robot are discussed. Finally, conclusions and potential extensions are outlined.

  16. Efficient Algorithms for Shortest Partial Seeds in Words

    E-print Network

    Lonardi, Stefano

    Efficient Algorithms for Shortest Partial Seeds in Words Tomasz Kociumaka1 , Solon P. Pissis2 Algorithms for Shortest Partial Seeds in Words 1/16 #12;Periodicity and quasiperiodicity Periodicity. Wale Efficient Algorithms for Shortest Partial Seeds in Words 2/16 #12;Periodicity and quasiperiodicity

  17. A path-following interior-point algorithm for linear and quadratic problems

    SciTech Connect

    Wright, S.J.

    1993-12-01

    We describe an algorithm for the monotone linear complementarity problem that converges for many positive, not necessarily feasible, starting point and exhibits polynomial complexity if some additional assumptions are made on the starting point. If the problem has a strictly complementary solution, the method converges subquadratically. We show that the algorithm and its convergence extend readily to the mixed monotone linear complementarity problem and, hence, to all the usual formulations of the linear programming and convex quadratic programming problems.

  18. Optimal parallel algorithms for problems modeled by a family of intervals

    NASA Technical Reports Server (NTRS)

    Olariu, Stephan; Schwing, James L.; Zhang, Jingyuan

    1992-01-01

    A family of intervals on the real line provides a natural model for a vast number of scheduling and VLSI problems. Recently, a number of parallel algorithms to solve a variety of practical problems on such a family of intervals have been proposed in the literature. Computational tools are developed, and it is shown how they can be used for the purpose of devising cost-optimal parallel algorithms for a number of interval-related problems including finding a largest subset of pairwise nonoverlapping intervals, a minimum dominating subset of intervals, along with algorithms to compute the shortest path between a pair of intervals and, based on the shortest path, a parallel algorithm to find the center of the family of intervals. More precisely, with an arbitrary family of n intervals as input, all algorithms run in O(log n) time using O(n) processors in the EREW-PRAM model of computation.

  19. A Particle Swarm Optimization Algorithm with Path Relinking for the Location Routing Problem

    Microsoft Academic Search

    Yannis Marinakis; Magdalene Marinaki

    2008-01-01

    This paper introduces a new hybrid algorithmic nature inspired approach based on particle swarm optimization, for solving\\u000a successfully one of the most popular logistics management problems, the location routing problem (LRP). The proposed algorithm\\u000a for the solution of the location routing problem, the hybrid particle swarm optimization (HybPSO-LRP), combines a particle\\u000a swarm optimization (PSO) algorithm, the multiple phase neighborhood search

  20. Information spread of emergency events: path searching on social networks.

    PubMed

    Dai, Weihui; Hu, Hongzhi; Wu, Tunan; Dai, Yonghui

    2014-01-01

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

  1. A sample path approach for solving the ground-holding policy problem in air traffic control

    Microsoft Academic Search

    Christos G. Panayiotou; Christos G. Cassandras

    1999-01-01

    We address the ground-holding problem in air traffic control and propose two techniques that can be used to dynamically solve this problem. The first is motivated by the kanban control policy extensively used in manufacturing systems to reduce the work-in-process inventory, while the second one uses finite perturbation analysis (FPA) for discrete-event systems. We show that the latter leads to

  2. Path Planning Algorithm for Vehicles Based on Time-dependent Optimization Criterion

    Microsoft Academic Search

    Qing Li; Sijiang Xie; Xinhai Tong; Guangjun Liu

    2007-01-01

    A specialized genetic algorithm is proposed in this paper for path planning of vehicles based on time-dependent optimization criterion. A variable signal encoding scheme is adopted to represent the path and a particular fitness function is investigated for time-dependent shortest path planning. Domain heuristic knowledge based crossover, mutation and deletion operators are also specifically designed to fit the vehicle path

  3. Path Analysis Model of Aptitude-Instruction Associations Over Time on Achievement in Solving Percent Problems.

    ERIC Educational Resources Information Center

    Maher, Carolyn A.; De Stefano, Frank V.

    The study examined whether embedding the linear equations and ratio and proportion strategies used to solve percent problems in the higher-order structures of proportional logic and group properties would aid achievement. Thus, it examined the interaction in differences in understanding fundamental structures in mathematics, and instruction…

  4. GRASP AND PATH RELINKING FOR THE MAX-MIN DIVERSITY PROBLEM

    E-print Network

    Resende, Mauricio G. C.

    in recent years. The former, also known as the maximum diversity problem (MDP) has been studied in Glover et (MMDP), both exact (Erkut, 1990) and heuristic approaches, such as simulated annealing (Kincaid, 1992), tabu search (Kincaid, 1992), and GRASP (Ghosh, 1996) have been proposed. Because of the flat landscape

  5. A Well-Balanced Path-Integral f-Wave Method for Hyperbolic Problems with Source Terms

    PubMed Central

    2014-01-01

    Systems of hyperbolic partial differential equations with source terms (balance laws) arise in many applications where it is important to compute accurate time-dependent solutions modeling small perturbations of equilibrium solutions in which the source terms balance the hyperbolic part. The f-wave version of the wave-propagation algorithm is one approach, but requires the use of a particular averaged value of the source terms at each cell interface in order to be “well balanced” and exactly maintain steady states. A general approach to choosing this average is developed using the theory of path conservative methods. A scalar advection equation with a decay or growth term is introduced as a model problem for numerical experiments. PMID:24563581

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

    PubMed

    Wilson, Helen W; Widom, Cathy Spatz

    2010-01-01

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

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

    PubMed Central

    Wilson, Helen W.; Widom, Cathy Spatz

    2009-01-01

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

  8. Path-integral-expanded-ensemble Monte Carlo method in treatment of the sign problem for fermions

    NASA Astrophysics Data System (ADS)

    Voznesenskiy, M. A.; Vorontsov-Velyaminov, P. N.; Lyubartsev, A. P.

    2009-12-01

    Expanded-ensemble Monte Carlo method with Wang-Landau algorithm was used for calculations of the ratio of partition functions for classes of permutations in the problem of several interacting quantum particles (fermions) in an external field. Simulations for systems consisting of 2 up to 7 interacting particles in harmonic or Coulombic field were performed. The presented approach allows one to carry out calculations for low enough temperatures that makes it possible to extract data for the ground-state energy and low-temperature thermodynamics.

  9. From Parent to Child to Parent…: Paths In and Out of Problem Behavior

    PubMed Central

    Bradley, Robert H.; Corwyn, Robert

    2014-01-01

    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

  10. Minimal Realizations of Linear Systems: The "Shortest Basis" Approach

    E-print Network

    Forney, G. David, Jr.

    Given a discrete-time linear system C, a shortest basis for C is a set of linearly independent generators for C with the least possible lengths. A basis B is a shortest basis if and only if it has the predictable span ...

  11. Encoding user motion preferences in harmonic function path planning

    Microsoft Academic Search

    Giles D'silva; Manfred Huber

    2009-01-01

    Humans have unique motion preferences when pursuing a given task. These motion preferences could be expressed as moving in a straight line, following the wall, avoiding sharp turns, avoiding damp surfaces or choosing the shortest path. While it would be very useful for a range of applications to allow robot systems or artificial agents to generate paths with similar specific

  12. A new graph model and algorithms for consistent superstring problems

    PubMed Central

    Na, Joong Chae; Cho, Sukhyeun; Choi, Siwon; Kim, Jin Wook; Park, Kunsoo; Sim, Jeong Seop

    2014-01-01

    Problems related to string inclusion and non-inclusion have been vigorously studied in diverse fields such as data compression, molecular biology and computer security. Given a finite set of positive strings and a finite set of negative strings , a string ? is a consistent superstring if every positive string is a substring of ? and no negative string is a substring of ?. The shortest (resp. longest) consistent superstring problem is to find a string ? that is the shortest (resp. longest) among all the consistent superstrings for the given sets of strings. In this paper, we first propose a new graph model for consistent superstrings for given and . In our graph model, the set of strings represented by paths satisfying some conditions is the same as the set of consistent superstrings for and . We also present algorithms for the shortest and the longest consistent superstring problems. Our algorithms solve the consistent superstring problems for all cases, including cases that are not considered in previous work. Moreover, our algorithms solve in polynomial time the consistent superstring problems for more cases than the previous algorithms. For the polynomially solvable cases, our algorithms are more efficient than the previous ones. PMID:24751868

  13. Fast marching methods for the continuous traveling salesman problem

    SciTech Connect

    Andrews, J.; Sethian, J.A.

    2008-12-01

    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.

  14. Incremental Multi-Scale Search Algorithm for Dynamic Path Planning With Low Worst-Case Complexity.

    PubMed

    Lu, Yibiao; Huo, Xiaoming; Arslan, Oktay; Tsiotras, Panagiotis

    2011-06-16

    Path-planning (equivalently, path-finding) problems are fundamental in many applications, such as transportation, VLSI design, robot navigation, and many more. In this paper, we consider dynamic shortest path-planning problems on a graph with a single endpoint pair and with potentially changing edge weights over time. Several algorithms exist in the literature that solve this problem, notably among them the Lifelong Planning A(?) (LPA(?)) algorithm. The LPA(?) algorithm is an incremental search algorithm that replans the path when there are changes in the environment. In numerical experiments, however, it was observed that the performance of LPA(?) is sensitive in the number of vertex expansions required to update the graph when an edge weight value changes or when a vertex is added or deleted. Although, in most cases, the classical LPA(?) requires a relatively small number of updates, in some other cases the amount of work required by the LPA(?) to find the optimal path can be overwhelming. To address this issue, in this paper, we propose an extension of the baseline LPA(?) algorithm, by making efficient use of a multiscale representation of the environment. This multiscale representation allows one to quickly localize the changed edges, and subsequently update the priority queue efficiently. This incremental multiscale LPA(?) ( m-LPA(?) for short) algorithm leads to an improvement both in terms of robustness and computational complexity-in the worst case-when compared to the classical LPA(?). Numerical experiments validate the aforementioned claims. PMID:21690015

  15. Solving shortest and closest vector problems: The decomposition approach

    E-print Network

    as a modified sieving algorithm for which the vectors of the intermediate sets lie in overlattices or translated of an overlattice. The complexity analysis relies on the Gaussian heuristic. This heuristic is backed by experiments the exact solution are at least exponential in the dimension of the lattice. These algorithms also serve

  16. Optimal paths for a car that goes both forwards and backwards

    Microsoft Academic Search

    J. A. Reeds; L. A. Shepp

    1990-01-01

    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?

  17. Finding a least hop(s) path subject to multiple additive constraints Gang Cheng, Nirwan Ansari*

    E-print Network

    Ansari, Nirwan

    Finding a least hop(s) path subject to multiple additive constraints Gang Cheng, Nirwan Ansari referred to as the least hop(s) multiple additively constrained path (LHMACP) selection, which is NP of computing All Hops k-shortest Paths (AHKP) between a source and a destination. Through extensive analysis

  18. On path selection for traffic with bandwidth guarantees

    Microsoft Academic Search

    Qingming Ma; Peter Steenkiste

    1997-01-01

    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

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

    NASA Astrophysics Data System (ADS)

    Mohanty, Prases K.; Parhi, Dayal R.

    2014-12-01

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

  20. Minimum Wheel-Rotation Paths for Differential-Drive Mobile Hamidreza Chitsaz

    E-print Network

    LaValle, Steven M.

    , with the goal of classifying solutions in the spirit of Dubins curves and Reeds-Shepp curves for car-like robotsMinimum Wheel-Rotation Paths for Differential-Drive Mobile Robots Hamidreza Chitsaz , Steven M. LaValle, Devin J. Balkcom, and Matthew T. Mason August 7, 2007 Abstract The shortest paths for a mobile robot

  1. A GENETIC ALGORITHM FOR THE WEIGHT SETTING PROBLEM ...

    E-print Network

    2001-10-09

    Oct 9, 2001 ... Interior Gateway Protocols (IGP) are used within the AS, while. Exterior ... router knows the complete topology, each router can compute all needed shortest paths [4]. .... Lin and Wang [20] present a completely different ap-.

  2. A Proficient Path Selection for Wireless Ad Hoc Routing Protocol

    Microsoft Academic Search

    A. N. Al-Khwildi; H. S. Al-Raweshidy

    2006-01-01

    Usually, routing protocols which are based on link-state information such as (OSPF, OLSR, and FSR) compute the shortest routes to each reachable destination using a path-selection algorithm like Dijkstra's algorithm or the Bellman-Ford algorithm. However, in an on-demand link-state routing protocol, there is no need to know the path to every other node. Accordingly, when a node chooses a next

  3. A new approach to the maximum flow problem

    Microsoft Academic Search

    Andrew V. Goldberg; Robert Endre Tarjan

    1986-01-01

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

  4. Solving nonlinear multicommodity flow problems with the analytic center cutting plane method

    SciTech Connect

    Goffin, J.L.; Gondzio, J.; Sarkissian, R.; Vial, J.P.

    1994-12-31

    A talk deals with nonlinear multicommodity flow problems with convex costs. A decomposition method is proposed to solve them. The approach applies a potential reduction algorithm to (approximately) solve the master problem and a column generation technique defining a sequence of primal linear programming problems. Each subproblem consists in finding a minimum cost flow between an origin and a destination node on an uncapacited network. It is thus formulated as a shortest path problem and it is solved with the Dijkstra`s d-heap algorithm. An experimental implementation is described that takes full advantage of the supersparsity of the network in the linear algebra operations. Computational results show high efficiency of the approach on (known from the literature) nondifferentiable problems, real-life large scale France Telecom problem and other large scale randomly generated problems (sized up to 1000 arcs and 4000 commodities).

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

    ERIC Educational Resources Information Center

    Wilson, Helen W.; Widom, Cathy Spatz

    2010-01-01

    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…

  6. The development of an interactive microcomputer-based system to analyze linear network optimization problems 

    E-print Network

    Fowler, John Welsh

    1986-01-01

    by: Donald R. Smith (Co-Chairman of Committee) Don T. Phillips (Co-Chairman of Committee) Sa ie V. eppar (Member) Ga (Memb r) Le n . B an (Interim Head of Department) May 1986 ABSTRACT The Development of an Interactive Microcomputer-based... nodes or only examining the shortest path between the source node and user specified nodes. 15 2. l. 1 Example Problem: Planning a Trip Assume an individual who lives in College Station, Texas is planning a trip to Dallas, Texas and wants to find...

  7. Convergent Duality for the Traveling Salesman Problem

    E-print Network

    Shapiro, Jeremy F., 1939-

    A constructive method is presented for optimizing exactly the Traveling Salesman Problem as a sequence of shortest route problems. The method combines group theoretic and Lagrangean relaxation constructions. Key Words: ...

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

    E-print Network

    Yang, Shengxiang

    .g., artificial neural networks, genetic algo- rithms (GAs), particle swarm optimization, etc. However intelligence techniques, e.g., artificial neural networks (ANNs) [2], genetic algorithms (GAs) [3, they will be effective in fixed infrastructure wireless or wired networks. But, they exhibit unacceptably high com

  9. All-Pairs Shortest Paths for Unweighted Undirected Graphs in o(mn) Time

    E-print Network

    Chan, Timothy M.

    well-known examples of log-factor speedup was Arlazarov et al.'s (a.k.a. the \\four-Russians") algorithm with n vertices and m edges. We present new algorithms with the following running times: 8 log n) if m > n log n log log log n O(mn log log n= log n) if m > n log log n O(n 2 log 2 log n= log n

  10. On designing a shortest-path-based cache replacement in a transcoding proxy

    Microsoft Academic Search

    Hao-ping Hung; Ming-syan Chen

    2009-01-01

    The technology advance in network has accelerated the development of multimedia applications over the wired and wireless communication.\\u000a To alleviate network congestion and to reduce latency and workload on multimedia servers, the concept of multimedia proxy\\u000a has been proposed to cache popular contents. Caching the data objects can relieve the bandwidth demand on the external network,\\u000a and reduce the average

  11. Shortest path adjusted similarity metrics for resolving boundary perturbations in scaffold images for tissue engineering

    NASA Astrophysics Data System (ADS)

    Rajagopalan, Srinivasan; Robb, Richard

    2006-03-01

    The degree of match between the delineation result produced by a segmentation technique and the ground truth can be assessed using robust "presence-absence" resemblance measures. Previously, we had investigated and introduced an exhaustive list of similarity indices for assessing multiple segmentation techniques. However, these measures are highly sensitive to even minor boundary perturbations which imminently manifest in the segmentations of random biphasic spaces reminiscent of the stochastic pore-solid distributions in the tissue engineering scaffolds. This paper investigates the ideas adapted from ecology to emphasize global resemblances and ignore minor local dissimilarities. It uses concepts from graph theory to perform controlled local mutations in order to maximize the similarities. The effect of this adjustment is investigated on a comprehensive list (forty nine) of similarity indices sensitive to the over- and under- estimation errors associated with image delineation tasks.

  12. Shortest Average Routing Path-Based d-hop Clustering in wireless sensor networks

    Microsoft Academic Search

    Ailian Jiangl; Weili Wu; Keming Xie; Donghyun Kirn; Wei Wang

    2010-01-01

    In the paper, we propose a new d-hop Clustering method for a clustering-based multi-hop routing scheme in large-scale wireless sensor network. d-hop clustering means that each cluster contains all nodes that are at distance at most d-hops from the clusterhead, so that the number of clusters can be getting smaller to make it possible to guarantee the combined system performances

  13. Tornado Paths

    NSDL National Science Digital Library

    Perry Samson

    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.

  14. Disjoint Paths in Densely Embedded Graphs

    Microsoft Academic Search

    Jon M. Kleinberg; Eva Tardoss

    1995-01-01

    We consider the following maximum disjoint paths problem (mdpp). We are given a large network, and pairs of nodes that wish to communicate over paths through the network — the goal is to simultaneously connect as many of these pairs as possible in such a way that no two communication paths share an edge in the network. This classical problem

  15. Complexity analysis of pipeline mapping problems in distributed heterogeneous networks

    SciTech Connect

    Lin, Ying [University of Tennessee, Knoxville (UTK); Wu, Qishi [ORNL; Zhu, Mengxia [ORNL; Rao, Nageswara S [ORNL

    2009-04-01

    Largescale scientific applications require using various system resources to execute complex computing pipelines in distributed networks to support collaborative research. System resources are typically shared in the Internet or over dedicated connections based on their location, availability, capability, and capacity. Optimizing the network performance of computing pipelines in such distributed environments is critical to the success of these applications. We consider two types of largescale distributed applications: (1) interactive applications where a single dataset is sequentially processed along a pipeline; and (2) streaming applications where a series of datasets continuously flow through a pipeline. The computing pipelines of these applications consist of a number of modules executed in a linear order in network environments with heterogeneous resources under different constraints. Our goal is to find an efficient mapping scheme that allocates the modules of a pipeline to network nodes for minimum endtoend delay or maximum frame rate. We formulate the pipeline mappings in distributed environments as optimization problems and categorize them into six classes with different optimization goals and mapping constraints: (1) Minimum Endtoend Delay with No Node Reuse (MEDNNR), (2) Minimum Endtoend Delay with Contiguous Node Reuse (MEDCNR), (3) Minimum Endtoend Delay with Arbitrary Node Reuse (MEDANR), (4) Maximum Frame Rate with No Node Reuse or Share (MFRNNRS), (5) Maximum Frame Rate with Contiguous Node Reuse and Share (MFRCNRS), and (6) Maximum Frame Rate with Arbitrary Node Reuse and Share (MFRANRS). Here, 'contiguous node reuse' means that multiple contiguous modules along the pipeline may run on the same node and 'arbitrary node reuse' imposes no restriction on node reuse. Note that in interactive applications, a node can be reused but its resource is not shared. We prove that MEDANR is polynomially solvable and the rest are NP-complete. MEDANR, where either contiguous or noncontiguous modules in the pipeline can be mapped onto the same node, is essentially the Maximum n-hop Shortest Path problem, and can be solved using a dynamic programming method. In MEDNNR and MFRNNRS, any network node can be used only once, which requires selecting the same number of nodes for onetoone onto mapping. We show its NP-completeness by reducing from the Hamiltonian Path problem. Node reuse is allowed in MEDCNR, MFRCNRS and MFRANRS, which are similar to the Maximum n-hop Shortest Path problem that considers resource sharing. We prove their NP-completeness by reducing from the Disjoint-Connecting-Path Problem and Widest path with the Linear Capacity Constraints problem, respectively.

  16. Air vehicle path planning

    Microsoft Academic Search

    Jeffrey Michael Hebert

    2001-01-01

    This dissertation explores optimal path planning for air vehicles. An air vehicle exposed to illumination by a tracking radar is considered and the problem of determining an optimal planar trajectory connecting two prespecified points is addressed. An analytic solution yielding the trajectory minimizing the received radar energy reflected from the target is derived using the Calculus of Variations. Additionally, the

  17. Bicriteria network design problems

    SciTech Connect

    Marathe, M.V.; Ravi, R.; Sundaram, R.; Ravi, S.S.; Rosenkrantz, D.J.; Hunt, H.B. III

    1994-12-31

    We study several bicriteria network design problems phrased as follows: given an undirected graph and two minimization objectives with a budget specified on one objective, find a subgraph satisfying certain connectivity requirements that minimizes the second objective subject to the budget on the first. Define an ({alpha}, {beta})-approximation algorithm as a polynomial-time algorithm that produces a solution in which the first objective value is at most {alpha} times the budget, and the second objective value is at most {alpha} times the minimum cost of a network obeying the budget oil the first objective. We, present the first approximation algorithms for bicriteria problems obtained by combining classical minimization objectives such as the total edge cost of the network, the diameter of the network and a weighted generalization of the maximum degree of any node in the network. We first develop some formalism related to bicriteria problems that leads to a clean way to state bicriteria approximation results. Secondly, when the two objectives are similar but only differ based on the cost function under which they are computed we present a general parametric search technique that yields approximation algorithms by reducing the problem to one of minimizing a single objective of the same type. Thirdly, we present an O(log n, log n)-approximation algorithm for finding a diameter-constrained minimum cost spanning tree of an undirected graph on n nodes generalizing the notion of shallow, light trees and light approximate shortest-path trees that have been studied before. Finally, for the class of treewidth-bounded graphs, we provide pseudopolynomial-time algorithms for a number of bicriteria problems using dynamic programming. These pseudopolynomial-time algorithms can be converted to fully polynomial-time approximation schemes using a scaling technique.

  18. Path detection in video surveillance

    Microsoft Academic Search

    Dimitrios Makris; Tim Ellis

    2002-01-01

    This paper addresses the problem of automatically extracting frequently used pedestrian pathways from video sequences of natural outdoor scenes. Path models are learnt from the accumulation of trajectory data over long time periods, and can be used to augment the classification of subseq uent track data. In particular, labelled paths provide an efficient means for compressing the trajectory data for

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

    E-print Network

    Goodrich, Michael A.

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

  20. Counting paths in digraphs

    SciTech Connect

    Sullivan, Blair D [ORNL; Seymour, Dr. Paul Douglas [Princeton University

    2010-01-01

    Say a digraph is k-free if it has no directed cycles of length at most k, for k {element_of} Z{sup +}. Thomasse conjectured that the number of induced 3-vertex directed paths in a simple 2-free digraph on n vertices is at most (n-1)n(n+1)/15. We present an unpublished result of Bondy proving there are at most 2n{sup 3}/25 such paths, and prove that for the class of circular interval digraphs, an upper bound of n{sup 3}/16 holds. We also study the problem of bounding the number of (non-induced) 4-vertex paths in 3-free digraphs. We show an upper bound of 4n{sup 4}/75 using Bondy's result for Thomasse's conjecture.

  1. An efficient dynamic system for real-time robot-path planning

    Microsoft Academic Search

    Allan R. Willms; Simon X. Yang

    2006-01-01

    This paper presents a simple yet efficient dynamic-programming (DP) shortest path algorithm for real-time collision-free robot-path planning applicable to situations in which targets and barriers are permitted to move. The algorithm works in real time and requires no prior knowledge of target or barrier movements. In the case that the barriers are stationary, this paper proves that this algorithm always

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

    Microsoft Academic Search

    Eiji Oki; Nobuaki Matsuura; Kohei Shiomoto; Naoaki Yamanaka

    2002-01-01

    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

  3. Scripted documents: a hypermedia path mechanism

    Microsoft Academic Search

    Polle T. ZelIweger

    1989-01-01

    The concept of a path, or ordered traversal of some links in a hypertext, has been a part of the hypertext notion from its early formation. Although paths can help to solve two major problems with hypertext systems, namely user disorientation and high cognitive overhead for users, their value has not been recognized. Paths can also provide the backbone for

  4. The shortest modulation period Blazhko RR Lyrae star: SS Cnc

    E-print Network

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

    2006-03-20

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

  5. Term Paths

    NSDL National Science Digital Library

    Cynthia Ann Radle (McCullough High School REV)

    1995-06-30

    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.

  6. Trajectory Generation and Path Planning for Autonomous Aerobots

    NASA Technical Reports Server (NTRS)

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

    2007-01-01

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

  7. Calculating Least Risk Paths in 3d Indoor Space

    NASA Astrophysics Data System (ADS)

    Vanclooster, A.; De Maeyer, Ph.; Fack, V.; Van de Weghe, N.

    2013-08-01

    Over the last couple of years, research on indoor environments has gained a fresh impetus; more specifically applications that support navigation and wayfinding have become one of the booming industries. Indoor navigation research currently covers the technological aspect of indoor positioning and the modelling of indoor space. The algorithmic development to support navigation has so far been left mostly untouched, as most applications mainly rely on adapting Dijkstra's shortest path algorithm to an indoor network. However, alternative algorithms for outdoor navigation have been proposed adding a more cognitive notion to the calculated paths and as such adhering to the natural wayfinding behaviour (e.g. simplest paths, least risk paths). These algorithms are currently restricted to outdoor applications. The need for indoor cognitive algorithms is highlighted by a more challenged navigation and orientation due to the specific indoor structure (e.g. fragmentation, less visibility, confined areas…). As such, the clarity and easiness of route instructions is of paramount importance when distributing indoor routes. A shortest or fastest path indoors not necessarily aligns with the cognitive mapping of the building. Therefore, the aim of this research is to extend those richer cognitive algorithms to three-dimensional indoor environments. More specifically for this paper, we will focus on the application of the least risk path algorithm of Grum (2005) to an indoor space. The algorithm as proposed by Grum (2005) is duplicated and tested in a complex multi-storey building. The results of several least risk path calculations are compared to the shortest paths in indoor environments in terms of total length, improvement in route description complexity and number of turns. Several scenarios are tested in this comparison: paths covering a single floor, paths crossing several building wings and/or floors. Adjustments to the algorithm are proposed to be more aligned to the specific structure of indoor environments (e.g. no turn restrictions, restricted usage of rooms, vertical movement) and common wayfinding strategies indoors. In a later stage, other cognitive algorithms will be implemented and tested in both an indoor and combined indoor-outdoor setting, in an effort to improve the overall user experience during navigation in indoor environments.

  8. Acyclic orientations with path constraints

    Microsoft Academic Search

    Rosa M. V. Figueiredo; Valmir C. Barbosa; Nelson Maculan; Cid C. Souza

    2005-01-01

    Many well-known combinatorial optimization problems can be stated over the set of acyclic orientations of an undirected graph. For example, acyclic orientations with certain diameter constraints are closely related to the optimal solutions of the vertex coloring and frequency assignment problems. In this paper we introduce a linear programming formulation of acyclic orientations with path constraints, and discuss its use

  9. Air vehicle path planning

    NASA Astrophysics Data System (ADS)

    Hebert, Jeffrey Michael

    This dissertation explores optimal path planning for air vehicles. An air vehicle exposed to illumination by a tracking radar is considered and the problem of determining an optimal planar trajectory connecting two prespecified points is addressed. An analytic solution yielding the trajectory minimizing the received radar energy reflected from the target is derived using the Calculus of Variations. Additionally, the related problem of an air vehicle tracked by a passive sensor is also solved. Using the insights gained from the single air vehicle radar exposure minimization problem, a hierarchical cooperative control law is formulated to determine the optimal trajectories that minimize the cumulative exposure of multiple air vehicles during a rendezvous maneuver. The problem of one air vehicle minimizing exposure to multiple radars is also addressed using a variational approach, as well as a sub-optimal minmax argument. Local and global optimality issues are explored. A novel decision criterion is developed determining the geometric conditions dictating when it is preferable to go between or around two radars. Lastly, an optimal minimum time control law is obtained for the target identification and classification mission of an autonomous air vehicle. This work demonstrates that an awareness of the consequences of embracing sub-optimal and non-globally optimal solutions for optimization problems, such as air vehicle path planning, is essential.

  10. Obstacle Avoidance Algorithm for Mobile Robot Running on the Planned Path Gao ChengMing, Ohya Akihisa, Yuta Shin'ichi (Univ. of Tsukuba)

    E-print Network

    Ohya, Akihisa

    Transform [2][3] (Fig.1) Fig.1 Obstacle plot 2.2 Fig.2 ( ) (Fig.2) #12;Fig.2 Obstacle judgment 2.3 Distance Transform 0 (Fig.3) ( ) 4 1 (Fig.3) Fig.3 Distance Transform 4 +1 1 ( +5) (Fig.4) Fig.3 Path generation (the same weight) Fig.4 Path generation (different weights) 2.4 (Fig.5) Fig.5 #12;Fig.5 Shortest path

  11. Time optimal paths for high speed maneuvering

    SciTech Connect

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

    1993-01-01

    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.

  12. PathExpander: Architectural Support for Increasing the Path Coverage of Dynamic Bug Detection #

    E-print Network

    Zhou, Yuanyuan

    PathExpander: Architectural Support for Increasing the Path Coverage of Dynamic Bug Detection,pinzhou,liuwei,yyzhou,torrellas}@cs.uiuc.edu Abstract Dynamic software bug detection tools are commonly used be­ cause they leverage run­time information. However, they suffer from a fundamental limitation, the Path Coverage Problem: they detect bugs

  13. PathExpander: Architectural Support for Increasing the Path Coverage of Dynamic Bug Detection

    E-print Network

    Torrellas, Josep

    PathExpander: Architectural Support for Increasing the Path Coverage of Dynamic Bug Detection Shan,pinzhou,liuwei,yyzhou,torrellas}@cs.uiuc.edu Abstract Dynamic software bug detection tools are commonly used be- cause they leverage run-time information. However, they suffer from a fundamental limitation, the Path Coverage Problem: they detect bugs

  14. Best-path planning for public transportation systems

    Microsoft Academic Search

    Chao-Lin Liu

    2002-01-01

    The author examines methods for a special class of path planning problems in which the routes are constrained. General search algorithms assume that we can move around in the traffic network freely, so they extend the partial paths from the very last location to each of its neighbors to form more partial paths. The best partial paths are then selected

  15. Advanced path interpolation in high performance motion control systems

    Microsoft Academic Search

    Dongjun Zhang; Zexiang Li; Shuang Cong; Hong Wu

    2010-01-01

    In the path following motion control system, the reference tool path of the machine tool is geometric curves predetermined by applications. The reference motion command for servo control system is generated based on the geometric tool path and the feedrate. The command generation module is called path interpolation. It is a classical problem in the motion control system. However, a

  16. Ray Paths

    NSDL National Science Digital Library

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

  17. Technical Reports on Mathematical and Computing Sciences: TRC209 title: Hausdor Dimension and the Stochastic Traveling Salesman Problem

    Microsoft Academic Search

    Hayato Takahashi

    The traveling salesman problem is a problem of finding the shortest tour through given points. In 1959, Beardwood, Halton, and Hammersley studied asymptotic length of the shortest tour through points on Euclidean space. In particular they described the optimal tour length with Euclidean dimension for the case that points are distributed with respect to Lebesgue absolutely continuous measure. In this

  18. The parameterized Steiner problem and the singular Plateau problem via energy

    Microsoft Academic Search

    Chikako Mese; Sumio Yamada

    The Steiner problem is the problem of finding the shortest network connecting a given set of points. By the singular Plateau Problem, we will mean the problem of finding an area-minimizing surface (or a set of surfaces adjoined so that it is homeomorphic to a 2-complex) spanning a graph. In this paper, we study the parametric versions of the Steiner

  19. Spare Capacity Assignment in Telecom Networks Using Path Restoration

    Microsoft Academic Search

    Jeyakesavan Veerasamy; S. Venkatesant; Jay C. Shah

    1995-01-01

    Path restoration scheme can be used in augmentingexisting telecommunication networks with adequatespare capacity to achieve a desired level of protectionagainst link failures. Path restoration planning correspondsto the multi--commodity flow problem, whichis computationally hard. In this paper, we present thedetails of an approximation scheme for the path basedrestoration planning problem and an implementation.We then compare the performance of link and pathrestoration

  20. Experiments determining best paths for testing computer program predicates

    Microsoft Academic Search

    Lee J. White; Prabhat N. Sahay

    1985-01-01

    Zeil has developed a vector space measure which indicates those paths which best detect errors in a selected program predicate. This measure has to be applied to a set of paths post hoc, and so the problem is to heuristically characterize those paths which will provide maximal test information about the selected predicate; the problem of selecting the optimal set

  1. Thermoalgebras and path integral

    NASA Astrophysics Data System (ADS)

    Khanna, F. C.; Malbouisson, A. P. C.; Malbouisson, J. M. C.; Santana, A. E.

    2009-09-01

    Using a representation for Lie groups closely associated with thermal problems, we derive the algebraic rules of the real-time formalism for thermal quantum field theories, the so-called thermo-field dynamics (TFD), including the tilde conjugation rules for interacting fields. These thermo-group representations provide a unified view of different approaches for finite-temperature quantum fields in terms of a symmetry group. On these grounds, a path integral formalism is constructed, using Bogoliubov transformations, for bosons, fermions and non-abelian gauge fields. The generalization of the results for quantum fields in (S1)d×R topology is addressed.

  2. Mechanics of the crack path formation

    NASA Technical Reports Server (NTRS)

    Rubinstein, Asher A.

    1991-01-01

    A detailed analysis of experimentally obtained curvilinear crack path trajectories formed in a heterogeneous stress field is presented. Experimental crack path trajectories were used as data for the numerical simulations, recreating the actual stress field governing the development of the crack path. Thus, the current theories of crack curving and kinking could be examined by comparing them with the actual stress field parameters as they develop along the experimentally observed crack path. The experimental curvilinear crack path trajectories were formed in the tensile specimens with a hole positioned in the vicinity of a potential crack path. The numerical simulation, based on the solution of equivalent boundary value problems with the possible perturbations of the crack path, is presented.

  3. Mechanics of the crack path formation

    NASA Technical Reports Server (NTRS)

    Rubinstein, Asher A.

    1989-01-01

    A detailed analysis of experimentally obtained curvilinear crack path trajectories formed in a heterogeneous stress field is presented. Experimental crack path trajectories were used as data for numerical simulations, recreating the actual stress field governing the development of the crack path. Thus, the current theories of crack curving and kinking could be examined by comparing them with the actual stress field parameters as they develop along the experimentally observed crack path. The experimental curvilinear crack path trajectories were formed in the tensile specimens with a hole positioned in the vicinity of a potential crack path. The numerical simulation, based on the solution of equivalent boundary value problems with the possible perturbations of the crack path, is presented here.

  4. PROBLEMS

    Microsoft Academic Search

    Philippe Geuzaine; Kristoer van der Zee; Charbel Farhat

    A methodology for designing formally second-order time-accurate and yet loosely coupled partitioned procedures for the solution of nonlinear fluid-structure interac- tion (FSI) problems is presented. Its key components are a fluid time-integrator that is provably second-order time-accurate on moving grids, the midpoint rule for advancing in time the solution of the structural dynamics equations of motion, a second-order structure predictor

  5. Adaptive path A priori path

    E-print Network

    Illinois at Chicago, University of

    Problem statement Assumptions We know the probabilistic distributions of travel times on all roads statement Assumptions We know the probabilistic distributions of travel times on all roads Literature (cont.) Reliability-based Maximizes the probability of realizing a travel time equal to or less

  6. Visualization of Ant Pheromone Based Path Following

    E-print Network

    Sutherland, Benjamin T.

    2010-07-14

    This thesis develops a simulation and visualization of a path finding algorithm based on ant pheromone paths created in 3D space. The simulation is useful as a demonstration of a heuristic approach to NP-complete problems and as an educational tool...

  7. Acyclic Orientations with Path Constraints

    Microsoft Academic Search

    Rosa M. V. Figueiredo; Valmir C. Barbosa; Nelson Maculan; Cid C. de Souza

    2008-01-01

    Many well-known combinatorial optimization problems can be stated over the\\u000aset of acyclic orientations of an undirected graph. For example, acyclic\\u000aorientations with certain diameter constraints are closely related to the\\u000aoptimal solutions of the vertex coloring and frequency assignment problems. In\\u000athis paper we introduce a linear programming formulation of acyclic\\u000aorientations with path constraints, and discuss its use

  8. Application research of ground shortest path based on GIS in the Emergency Rescue Information Management System for airport airside

    Microsoft Academic Search

    Chen Xin; Xiucheng Guo; Dongtao Fan

    2011-01-01

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

  9. The shortest path computation in MOSPF protocol using an annealed Hopfield neural network with a new cooling schedule

    Microsoft Academic Search

    Jzau-sheng Lin; Mingshou Liu; Nen-fu Huang

    2000-01-01

    Many network services, such as video conferencing and video on demand, have popularly used the multimedia communications. The attached hosts\\/routers are required to transmit data as multicasting in most multimedia applications. In order to provide an efficient data routing, routers must provide multicast capability. In this paper, a new cooling schedule in Hopfield neural network with annealing strategy is proposed

  10. Abstract--Path protection requires finding a working path and a protection path that are link disjoint. In this paper, we

    E-print Network

    Jue, Jason P.

    Abstract-- Path protection requires finding a working path and a protection path that are link disjoint. In this paper, we consider the dynamic lightpath protection problem in WDM mesh networks under-disjoint lightpaths on a single wavelength; however, such algorithms fail if the working and protection lightpaths

  11. Abstract--Path protection requires finding a working path and a protection path that are link disjoint. In this paper, we

    E-print Network

    Jue, Jason P.

    Abstract-- Path protection requires finding a working path and a protection path that are link disjoint. In this paper, we consider the dynamic lightpath protection problem in WDM mesh networks where-- Optical network, lightpath protection, shared risk link group, risk disjoint, integer linear program (ILP

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

    Microsoft Academic Search

    Tewolde S. Tewolde; Weihua Sheng

    2008-01-01

    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

  13. CS 105: Algorithms (Grad) Set Cover and Application to Shortest Superstring

    E-print Network

    Chakrabarti, Amit

    CS 105: Algorithms (Grad) Set Cover and Application to Shortest Superstring Valika K. Wan & Khanh Do Ba Feb 21-24, 2005 1 Approximating Set Cover 1.1 Definition An Instance (X, F) of the set-covering a minimum size subset C F whose members cover all of X. X = SC S (1) The cost of the set-covering

  14. On the ideal of the shortest vectors in the Leech lattice and other lattices

    E-print Network

    Martin, Bill

    On the ideal of the shortest vectors in the Leech lattice and other lattices William J. Martin, E7, E8, 24 (the Leech lattice) and determine for each: (i) the smallest degree of a non to cometric association schemes. 1 Introduction The Leech lattice 24 is well-studied in several mathematical

  15. Zone-Based Shortest Positioning Time First Scheduling for MEMS-Based Storage Devices

    E-print Network

    Miller, Ethan L.

    Zone-Based Shortest Positioning Time First Scheduling for MEMS-Based Storage Devices Bo Hong, Scott. MEMS-based storage devices use orthog- onal magnetic or physical recording techniques and thou- sands of simultaneously active MEMS-based read-write tips to provide high-density low-latency non-volatile storage

  16. Finding a Shortest Diagonal of a Simple Polygon in Linear John Hershberger

    E-print Network

    ­known, for instance, that a closest pair among n points in the plane can be found in O(n log n) time for finding a closest pair of vertices in a simple polygon---observe that a shortest diagonal is defined by a closest pair of vertices satisfying an additional visibility constraint. 1 #12; 1 Introduction Closest

  17. The Theory of Networks and Management Science. Part I

    Microsoft Academic Search

    Salah E. Elmaghraby

    1970-01-01

    An expository treatment of three network models most often encountered in Management Science applications: (i) The Shortest Path Problems, (ii) Flow Networks, and (iii) Activity Networks. In the first problem are discussed the shortest path between two specified nodes; the shortest distance matrix; as well as the special case of directed acyclic networks. In the second problem, a brief exposition

  18. On a Multiproduct Assembly Line-Balancing Problem

    Microsoft Academic Search

    Stephen D. Roberts; Carlos D. Villa

    1970-01-01

    A multiproduct assembly line-balancing problem is presented. The problem is formulated as a linear integer programming problem for which zero-one programming is applicable. A reformulation based on finding the shortest route in a finite direct network is developed, and an example problem is solved. Directions for future research is indicated.

  19. On the Generation of Nearly Optimal, Planar Paths of Bounded Curvature and Bounded Curvature Gradient

    E-print Network

    Tsiotras, Panagiotis

    is a generalization of the Dubins problem to account for more realistic vehicle dynamics. The problem is solved. First, the generated path should be compatible to the vehicle dynamics, and second, the path should is the total length of the path, whereas the vehicle's dynamics may be incorporated into the path generation

  20. Vertex Covering by Weighted Paths on Trees and its Subtree Variation

    Microsoft Academic Search

    Omar Haider Chowdhury; Debasis Roy; Shamim Ashik; Abul Kashem Mia

    Given a tree and a set of weighted paths in that tree, the problem involves flnding a minimum weighted subset of paths that covers all the vertices of the tree where each vertex is covered by a bounded number of paths, is scrutinized in this paper. This problem is referred to as the vertex covering by weighted paths on trees.

  1. The mixture problem in computer mapping of terrain: Improved techniques for establishing spectral signature, atmospheric path radiance, and transmittance. [in Colorado

    NASA Technical Reports Server (NTRS)

    Smedes, H. W.; Hulstrom, R. L.; Ranson, K. J.

    1975-01-01

    The results of LANDSAT and Skylab research programs on the effects of the atmosphere on computer mapping of terrain include: (1) the concept of a ground truth map needs to be drastically revised; (2) the concept of training areas and test areas is not as simple as generally thought because of the problem of pixels that represent a mixture of terrain classes; (3) this mixture problem needs to be more widely recognized and dealt with by techniques of calculating spectral signatures of mixed classes, or by other methods; (4) atmospheric effects should be considered in computer mapping of terrain and in monitoring changes; and (5) terrain features may be used as calibration panels on the ground, from which atmospheric conditions can be determined and monitored. Results are presented of a test area in mountainous terrain of south-central Colorado for which an initial classification was made using simulated mixture-class spectral signatures and actual LANDSAT-1-MSS data.

  2. Phase Diagram of Optimal Paths

    E-print Network

    Alex Hansen; Janos Kertesz

    2004-02-17

    We show that choosing appropriate distributions of the randomness, the search for optimal paths links diverse problems of disordered media like directed percolation, invasion percolation, directed and non-directed spanning polymers. We also introduce a simple and efficient algorithm, which solves the d-dimensional model numerically in order N^(1+d_f/d) steps where d_f is the fractal dimension of the path. Using extensive simulations in two dimensions we identify the phase boundaries of the directed polymer universality class. A new strong-disorder phase occurs where the optimum paths are self-affine with parameter-dependent scaling exponents. Furthermore, the phase diagram contains directed and non-directed percolation as well as the directed random walk models at specific points and lines.

  3. A new approach to CNC tool path generation

    Microsoft Academic Search

    Chih-ching Lo

    1998-01-01

    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

  4. By-passing the sign-problem in Fermion Path Integral Monte Carlo simulations by use of high-order propagators

    NASA Astrophysics Data System (ADS)

    Chin, Siu A.

    2014-03-01

    The sign-problem in PIMC simulations of non-relativistic fermions increases in serverity with the number of fermions and the number of beads (or time-slices) of the simulation. A large of number of beads is usually needed, because the conventional primitive propagator is only second-order and the usual thermodynamic energy-estimator converges very slowly from below with the total imaginary time. The Hamiltonian energy-estimator, while more complicated to evaluate, is a variational upper-bound and converges much faster with the total imaginary time, thereby requiring fewer beads. This work shows that when the Hamiltonian estimator is used in conjunction with fourth-order propagators with optimizable parameters, the ground state energies of 2D parabolic quantum-dots with approximately 10 completely polarized electrons can be obtain with ONLY 3-5 beads, before the onset of severe sign problems. This work was made possible by NPRP GRANT #5-674-1-114 from the Qatar National Research Fund (a member of Qatar Foundation). The statements made herein are solely the responsibility of the author.

  5. Path planning for UAVs

    Microsoft Academic Search

    S. A. Bortoff; E. Hartford

    2000-01-01

    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

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

    E-print Network

    Hall, Sharon J.

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

  7. On the near-optimality of the shortest-latency-time-first drum scheduling discipline

    Microsoft Academic Search

    Harold S. Stone; Samuel H. Fuller

    1973-01-01

    For computer systems in which it is practical to determine the instantaneous drum position, a popular discipline for determining the sequence in which the records are to be accessed is the so-called shortest-latency-time-first, SLTF, discipline. When a collection of varying-length records is to be accessed from specified drum positions, it is known that the SLTF discipline does not necessarily minimize

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

    Microsoft Academic Search

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

    2009-01-01

    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

  9. Path layout on tree networks: Bounds in different label switching models

    E-print Network

    Epstein, Leah

    Path layout on tree networks: Bounds in different label switching models Anat Bremler-Barr Leah Epstein Abstract Path Layout is a fundamental graph problem in label switching protocols. This problem protocol standardized recently by the IETF. Path layout is essentially the problem of reducing the size

  10. Approximate analysis of a fault-tolerant join-the-shortest-queue policy Guangzhi Li Gianfranco Ciardo

    E-print Network

    Ciardo, Gianfranco

    Ciardo Department of Computer Science College of William and Mary Williamsburg, VA 23187-8795, USA {gli, ciardo}@cs.wm.edu Abstract In distributed or multi-processor systems, the join the shortest queue (JSQ

  11. Algorithms for Multiple Vehicle Routing Problems

    E-print Network

    Bae, Jung Yun

    2014-06-02

    is a multiple depot, multiple terminal, Hamiltonian Path problem. Given multiple vehicles starting at distinct depots, a set of targets and terminal locations, the objective of this problem is to find a vertex-disjoint path for each vehicle...

  12. Optimal path planning in Rapid Prototyping based on genetic algorithm

    Microsoft Academic Search

    Yang Weidong

    2009-01-01

    One of important researches in rapid prototyping (RP) is to optimize the path planning which affects the efficiency and building quality of RP system. But it is very difficult to solve its optimization by traditional methods. Genetic algorithms (GAs) are excellent approaches to solving these complex problems in optimization with difficult constraints. The classic path-planning optimization problem has been shown

  13. Short and Robust Communication Paths in Dynamic Wireless Networks

    Microsoft Academic Search

    Yoann Pigné; Frédéric Guinand

    2010-01-01

    \\u000a We consider the problem of finding and maintaining communication paths in wireless mobile ad hoc networks (MANET). We consider\\u000a this problem as a bi-objective problem when trying to minimize both the length of the constructed paths and the number link\\u000a reconnections. We propose two centralized algorithms that help analyse the problem from a dynamic graph point of view. These\\u000a algorithms

  14. Generic Equations for Constructing Smooth Paths Along Circles and Tangent Lines With Application to Airport Ground Paths

    NASA Technical Reports Server (NTRS)

    Barker, L. Keith

    1998-01-01

    The primary purpose of this publication is to develop a mathematical model to describe smooth paths along any combination of circles and tangent lines. Two consecutive circles in a path are either tangent (externally or internally) or they appear on the same (lateral) or opposite (transverse) sides of a connecting tangent line. A path may start or end on either a segment or circle. The approach is to use mathematics common to robotics to design the path as a multilink manipulator. This approach allows a hierarchical view of the problem and keeps the notation manageable. A user simply specifies a few parameters to configure a path. Necessary and sufficient conditions automatically ensure the consistency of the inputs for a smooth path. Two example runway exit paths are given, and an angle to go assists in knowing when to switch from one path element to the next.

  15. Distributed Resolution of a Trajectory Optimization Problem on a MEMS-based Reconfigurable Modular Surface

    E-print Network

    Ingrand, François

    Fig. 1). Blocks move on the surface via electro-permanent magnet technology. Parts are moved on top in a micro-electro-mechanical based modular surface context. The method computes the shortest path between. Self-reconfigurable systems [2-4] made of small Micro-Electro-Mechanical Systems (MEMS) modules can

  16. Cooperative optimal path planning for herding problems

    E-print Network

    Lu, Zhenyu

    2009-05-15

    . As one can see, when w1 = 0 and w2 = 1, the flnal time is removed from the performance index. This corresponds to an efiort optimal case. When w1 = 1 and w2 = 0, the control efiort is not penalized, and any solution with respect to J becomes a time... requirement to change the weight) to penalize the third term. For our example, we choose the initial conditions to be: [xe1(t0);ye1(t0)] = [2:8;4:1], [xe2(t0);ye2(t0)] = [3:5;3:5], [xe3(t0);ye3(t0)] = [3:1;3:7], [xp1(t0);yp1(t0)] = [5;5:6] and [xp2(t0);yp2(t0...

  17. Configuration Path Integral Monte Carlo

    NASA Astrophysics Data System (ADS)

    Bonitz, Michael; Schoof, Tim; Groth, Simon; Filinov, Alexei; Hochstuhl, David

    2011-10-01

    A novel path integral Monte Carlo (PIMC) approach for correlated many-particle systems with arbitrary pair interaction in continuous space at low temperatures is presented. It is based on a representation of the N-particle density operator in a basis of (anti-)symmetrized N-particle states (``configurations'' of occupation numbers). The path integral is transformed into a sum over trajectories with the same topology and, finally, the limit of M to infinity, (M is the number of high-temperature factors), is analytically performed. This yields exact expressions for the thermodynamic quantities and allows to perform efficient simulations for fermions at low temperature and weak to moderate coupling. Our method is applicable to dense quantum plasmas in the regime of strong degeneracy where conventional PIMC, e.g., fails due to the fermion sign problem. This work is supported by the Deutsche Forschungsgemeinschaft.

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

    Microsoft Academic Search

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

    2009-01-01

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

  19. Tool path integration for spray forming processes using a genetic algorithm

    Microsoft Academic Search

    Weihua Sheng; Girma Tewolde; Heping Chen

    2005-01-01

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

  20. Automatic tracking of neuro vascular tree paths

    NASA Astrophysics Data System (ADS)

    Suryanarayanan, S.; Gopinath, A.; Mallya, Y.; Shriram, K. S.; Joshi, M.

    2006-03-01

    3-D analysis of blood vessels from volumetric CT and MR datasets has many applications ranging from examination of pathologies such as aneurysm and calcification to measurement of cross-sections for therapy planning. Segmentation of the vascular structures followed by tracking is an important processing step towards automating the 3-D vessel analysis workflow. This paper demonstrates a fast and automated algorithm for tracking the major arterial structures that have been previously segmented. Our algorithm uses anatomical knowledge to identify the start and end points in the vessel structure that allows automation. Voxel coding scheme is used to code every voxel in the vessel based on its geodesic distance from the start point. A shortest path based iterative region growing is used to extract the vessel tracks that are subsequently smoothed using an active contour method. The algorithm also has the ability to automatically detect bifurcation points of major arteries. Results are shown for tracking the major arteries such as the common carotid, internal carotid, vertebrals, and arteries coming off the Circle of Willis across multiple cases with various data related and pathological challenges from 7 CTA cases and 2 MR Time of Flight (TOF) cases.

  1. Tortuous path chemical preconcentrator

    DOEpatents

    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

    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.

  2. Path Integration in Desert Ants, Cataglyphis fortis

    Microsoft Academic Search

    Martin Muller; Rudiger Wehner

    1988-01-01

    Foraging desert ants, Cataglyphis fortis, continually keep track of their own positions relative to home--i.e., integrate their tortuous outbound routes and return home along straight (inbound) routes. By experimentally manipulating the ants' outbound trajectories we show that the ants solve this path integration problem not by performing a true vector summation (as a human navigator does) but by employing a

  3. Applications of Path Compression on Balanced Trees

    Microsoft Academic Search

    Robert Endre Tarjan

    1979-01-01

    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

  4. Crack path prediction near an elliptical inclusion

    Microsoft Academic Search

    E. M. Patton; M. H. Santare

    1993-01-01

    A technique is presented which will predict the path of a naturally growing crack where the stress field can be modeled as two-dimensional. The Green function for an arbitrarily oriented edge dislocation interacting with a rigid inclusion (or void) is used in an integral formulation of the elasticity problem. The technique uses a boundary integral approach to solve for the

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

  6. Multi-Level Indoor Path Planning Method

    NASA Astrophysics Data System (ADS)

    Xiong, Q.; Zhu, Q.; Zlatanova, S.; Du, Z.; Zhang, Y.; Zeng, L.

    2015-05-01

    Indoor navigation is increasingly widespread in complex indoor environments, and indoor path planning is the most important part of indoor navigation. Path planning generally refers to finding the most suitable path connecting two locations, while avoiding collision with obstacles. However, it is a fundamental problem, especially for 3D complex building model. A common way to solve the issue in some applications has been approached in a number of relevant literature, which primarily operates on 2D drawings or building layouts, possibly with few attached attributes for obstacles. Although several digital building models in the format of 3D CAD have been used for path planning, they usually contain only geometric information while losing abundant semantic information of building components (e.g. types and attributes of building components and their simple relationships). Therefore, it becomes important to develop a reliable method that can enhance application of path planning by combining both geometric and semantic information of building components. This paper introduces a method that support 3D indoor path planning with semantic information.

  7. Real-time Path Planning for Navigation in Unknown Environment

    Microsoft Academic Search

    Tao Ruan Wan; H. Chen; Rae A. Earnshaw

    2003-01-01

    Real-time path planning is a challenging task that has many applications in the fields of AI, moving robots, virtual reality, agent behavior simulation, and action games. The various approaches for path planning have different criteria that have to be met, resulting in a number of algorithms for solutions to specific problems. In this paper, we introduce our approach and recent

  8. Haldane's Lungs: A Case Study in Path Analysis.

    ERIC Educational Resources Information Center

    McDonald, Roderick P.

    1997-01-01

    Structural equation modelling is becoming increasingly popular in education. This article examines and compares a number of alternative assumptions governing nondirected paths in structural equation models without latent variables vis-a-vis a data set on lung ventilation. Some problems with the conventional procedures in path analysis are pointed…

  9. Domain mapping as an expeditionary strategy for fast path planning

    Microsoft Academic Search

    Anil B. Suryawanshi; Milind B. Joshi; Bhaskar Dasgupta; Arpan Biswas

    2003-01-01

    In this paper, a new approach to path planning in static configuration space is presented. This also includes the problem of finding a path in the presence of obstacles. The method proceeds in two phases: a domain mapping phase and a query phase. In the domain mapping, the region is mapped onto a chosen convex region. For implementation in 2-D

  10. Toward Efficient Trajectory Planning: The Path-Velocity Decomposition

    Microsoft Academic Search

    Kamal Kant; Steven W. Zucker

    1986-01-01

    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.

  11. Safe Receding Horizon Path Planning for Autonomous Vehicles

    E-print Network

    How, Jonathan P.

    Safe Receding Horizon Path Planning for Autonomous Vehicles Tom Schouwenaars Eric Feron Jonathan to a safe mode, by maintaining a feasible path to a predefined safe state at each time step. 1 Introduction. It has been proven that the motion planning problem is intrinsically NP-hard [1]. Namely, the space

  12. VISCOSITY SOLUTIONS OF FULLY NONLINEAR ELLIPTIC PATH DEPENDENT PDES

    E-print Network

    Paris-Sud XI, Université de

    VISCOSITY SOLUTIONS OF FULLY NONLINEAR ELLIPTIC PATH DEPENDENT PDES ZHENJIE REN Abstract, inspired by [3], we define the viscosity solution, by using the nonlinear expectation. The paper contains , that for any bounded viscosity subsolution u1 and Key words and phrases. Path dependent PDEs, Dirichlet problem

  13. Path Protection in WDM Networks with Quality of Transmission Limitations

    E-print Network

    Varvarigo, Emmanouel "Manos"

    Path Protection in WDM Networks with Quality of Transmission Limitations Abstract-- We consider path protection in the routing and wavelength assignment (RWA) problem for impairment constrained WDM by accounting for physical layer impairments. The backup lightpath may either be activated (1+1 protection

  14. Algorithms for Computing QoS Paths with Restoration

    E-print Network

    Sprintson, Alexander

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

  15. Path Planning and Motion Coordination in Multiple Mobile Robot Teams

    E-print Network

    Parker, Lynne E.

    Path Planning and Motion Coordination in Multiple Mobile Robot Teams Lynne E. Parker Department is a robot that can perform tasks in unstructured environments with minimal human guidance. Planned path coordination addresses the problem of how teams of autonomous mobile robots can share the same workspace while

  16. Flux Control in Networks of Diffusion Paths

    SciTech Connect

    A. I. Zhmoginov and N. J. Fisch

    2009-07-08

    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.

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

    NASA Astrophysics Data System (ADS)

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

    2009-12-01

    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.

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

    E-print Network

    Mullally, F; Thompson, Susan E; Lupton, Robert

    2009-01-01

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

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

    SciTech Connect

    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

    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.

  20. From (2,3)-Motzkin Paths to Schröder Paths

    NASA Astrophysics Data System (ADS)

    Yan, Sherry H. F.

    2007-08-01

    In this paper, we provide a bijection between the set of restricted (2,3)-Motzkin paths of length n and the set of Schroder paths of semilength n. Furthermore, we give a one-to-one correspondence between the set of (2,3)-Motzkin paths of length n and the set of little Schroder paths of semilength n+1. By applying the bijections, we get the enumerations of Schroder paths according to the statistics "number of udd's" and "number of hd's".

  1. Minimal entropy probability paths between genome families.

    PubMed

    Ahlbrandt, Calvin; Benson, Gary; Casey, William

    2004-05-01

    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

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

    Microsoft Academic Search

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

    2001-01-01

    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

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

    ERIC Educational Resources Information Center

    Guerrieri, Bruno

    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

  4. Minimum energy path planning for ad hoc networks

    E-print Network

    Chen, Danjie

    2005-01-01

    We introduce the problem of finding a path for a mobile node traveling from a source to a destination while communicating with at least one node from a set of stationary nodes in such a way that minimizes the transmission ...

  5. Path planning of Autonomous Underwater Vehicles for adaptive sampling

    E-print Network

    Yilmaz, Namik Kemal, 1975-

    2006-01-01

    This thesis develops new methods for path planning of Autonomous Underwater Vehicles for adaptive sampling. The problem is approached in an optimization framework and two methods are developed to solve it based on Mixed ...

  6. Human-Automation Path Planning Optimization and Decision Support

    E-print Network

    Cummings, M.L.

    2011-01-01

    Path planning is a problem encountered in multiple domains, including unmanned vehicle control, air traffic control, and future exploration missions to the Moon and Mars. Due to the voluminous and complex nature of the ...

  7. Stochastic Evolutionary Algorithms for Planning Robot Paths

    NASA Technical Reports Server (NTRS)

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

    2006-01-01

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

  8. Parallel RRT-based path planning for selective disassembly planning

    Microsoft Academic Search

    Iker Aguinaga; Diego Borro; Luis Matey

    2008-01-01

    The planning of disassembly sequences requires the identification of the extraction trajectories of the different parts or\\u000a assemblies. The failure to find these trajectories can make a planner fail to generate correct sequences or not evaluate potential\\u000a solutions. In this paper, we analyze the disassembly path-planning problem, its relation to the general path-planning problem\\u000a and the main differences between both

  9. Path integral control and state-dependent feedback

    NASA Astrophysics Data System (ADS)

    Thijssen, Sep; Kappen, H. J.

    2015-03-01

    In this paper we address the problem of computing state-dependent feedback controls for path integral control problems. To this end we generalize the path integral control formula and utilize this to construct parametrized state-dependent feedback controllers. In addition, we show a relation between control and importance sampling: Better control, in terms of control cost, yields more efficient importance sampling, in terms of effective sample size. The optimal control provides a zero-variance estimate.

  10. Planning a Dynamic Trajectory via Path Finding in Discretized Phase Space

    Microsoft Academic Search

    Helge Ritter; Klaus Schulten

    1986-01-01

    The control of dynamical systems under constraints on the the controlling force can require long term trajectory preplanning to avoid entering dead ends in phase space. To handle such problems in a flexible way we suggest to formulate them as a path finding problem on a suitably discretized version of the phase space of the system. This path finding problem

  11. Quickest Paths for Different Network Router Mechanisms

    SciTech Connect

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

    2000-06-01

    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.

  12. Approximate path seeking for statistical iterative reconstruction

    NASA Astrophysics Data System (ADS)

    Wu, Meng; Yang, Qiao; Maier, Andreas; Fahrig, Rebecca

    2015-03-01

    Statistical iterative reconstruction (IR) techniques have demonstrated many advantages in X-ray CT reconstruction. The statistical iterative reconstruction approach is often modeled as an optimization problem including a data fitting function and a penalty function. The tuning parameter values that regulate the strength of the penalty function are critical for achieving good reconstruction results. However, appropriate tuning parameter values that are suitable for the scan protocols and imaging tasks are often difficult to choose. In this work, we propose a path seeking algorithm that is capable of generating a series of IR images with different strengths of the penalty function. The path seeking algorithm uses the ratio of the gradients of the data fitting function and the penalty function to select pixels for small fixed size updates. We describe the path seeking algorithm for penalized weighted least squares (PWLS) with a Huber penalty function in both the directions of increasing and decreasing tuning parameter value. Simulations using the XCAT phantom show the proposed method produces path images that are very similar to the IR images that are computed via direct optimization. The root-mean- squared-error of one path image generated by the proposed method relative to full iterative reconstruction is about 6 HU for the entire image and 10 HU for a small region. Different path seeking directions, increment sizes and updating percentages of the path seeking algorithm are compared in simulations. The proposed method may reduce the dependence on selection of good tuning parameter values by instead generating multiple IR images, without significantly increasing the computational load.

  13. Sparsed potential-PCNN for real time path planning and indoor navigation scheme for mobile robots

    Microsoft Academic Search

    S. U. Ahmed; U. A. Malik; K. F. Iqbal; Y. Ayaz; F. Kunwar

    2011-01-01

    One of the main problems associated with mobile intelligent agents is path planning. Numerous approaches have been presented for path planning of mobile robots. One of the most efficient methods is Pulse Coupled Neural Network (PCNN). This paper presents a novel approach we call the Sparsed Potential PCNN method for real time path planning for mobile robots. In the proposed

  14. Evolving ant colony system for optimizing path planning in mobile robots

    Microsoft Academic Search

    Beatriz A. Garro; Humberto Sossa; Roberto A. Vázquez

    2007-01-01

    Path planning is one of the problems in robotics. It consists on automatically determine a path from an initial position of the robot to its final position. In this paper we propose a variant of the ant colony system (ACO) applied to optimize the path that a robot can follow to reach its target destination. We also propose to evolve

  15. A Distributed Multi-commodity Flow Approximation Algorithm for Path Restoration

    E-print Network

    Venkatesan, S.

    A Distributed Multi-commodity Flow Approximation Algorithm for Path Restoration S algorithm specif- ically tailored for path restoration, which is an important problem in building survivable telecommunication backbone networks. Path-based restoration schemes are known their for high restora- tion

  16. Path-following control of a mobile robot in the presence of actuator constraints

    Microsoft Academic Search

    Nobutaka Wada; Shingo Tagami; Masami Saeki

    2007-01-01

    In this paper, we present a control law for a non-holonomic mobile robot that achieves path following. In the path-following problem, the objective is to control the angular velocity of the robot so that the robot tracks a given reference trajectory. In this paper, we propose a control law that achieves path following in the presence of a constraint on

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

    Microsoft Academic Search

    Larry McMurchie; Carl Ebeling

    1995-01-01

    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

  18. Path to the Profession

    ERIC Educational Resources Information Center

    Coleman, Toni

    2012-01-01

    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

  19. Asynchronous Data Path Models

    Microsoft Academic Search

    Danil Sokolov; Ivan Poliakov; Alexandre Yakovlev

    2007-01-01

    A token-based model for asynchronous data path is formally defined and three token game semantics, spread token, antitoken and counterflow, are introduced. These semantics are studied and their advantages and drawbacks are highlighted. For analysis and comparison a software tool is developed which integrates these models into a consistent framework. The models are verified by mapping them into Petri nets

  20. DNA Computing Hamiltonian path

    E-print Network

    Hagiya, Masami

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

  1. Universitat Bielefeld Technische Fakultat

    E-print Network

    Moeller, Ralf

    in grid-based applications . . . . . . . . 12 2.2.1 Tracing of the shortest path in the potential vector . . . . . . . . . . . . . . . . . . . . 6 1.3 Mapping of binary map nodes on reconfigurable hardware . . . . 6 1.4 Applications of grid of the problems in mobile robotics is navigation and path planning on maps. An approach to finding a shortest path

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

    Microsoft Academic Search

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

    2009-01-01

    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

  3. What is a MISR path?

    Atmospheric Science Data Center

    2014-12-08

    ... every 233 revolutions around the Earth, it is natural to name each of these different trajectories or paths. For MISR, the path is the generic name (actually the numeric label) of all orbits that observe the same areas ...

  4. Bike path Schools Bike friendly

    E-print Network

    Crews, Stephen

    Bike path Schools Parks Greenways Bike lane Bike friendly Bike path on sidewalk (uphill only a left turn, merge with motor vehicle traffic well in advance of the intersection. When bicycle paths stopping distance in inclement weather. Use a backpack or bike bag to carry items. Reasons to Bike

  5. Autonomous ground vehicle path tracking

    Microsoft Academic Search

    Jeff Wit; Carl D. Crane III; David G. Armstrong II

    2004-01-01

    Autonomous ground vehicle navigation requires the integration of many technologies such as path planning, position and orientation sensing, vehicle control, and obstacle avoidance. The work presented here focuses on the control of a nonholonomic ground vehicle as it tracks a given path. A new path tracking technique called ''vector pursuit'' is presented. This new technique is based on the theory

  6. An Integer Programming Algorithm for Routing Optimization in IP Networks

    Microsoft Academic Search

    Andreas Bley

    2008-01-01

    Most data networks nowadays use shortest path protocols to route the traffic. Given administrative routing lengths for the\\u000a links of the network, all data packets are sent along shortest paths with respect to these lengths from their source to their\\u000a destination.\\u000a \\u000a In this paper, we present an integer programming algorithm for the minimum congestion unsplittable shortest path routing problem,\\u000a which

  7. An Integer Programming Algorithm for Routing Optimization in IP Networks

    Microsoft Academic Search

    Andreas Bley

    2011-01-01

    Most data networks nowadays use shortest path protocols to route the traffic. Given administrative routing lengths for the\\u000a links of the network, all data packets are sent along shortest paths with respect to these lengths from their source to their\\u000a destination.\\u000a \\u000a \\u000a In this paper, we present an integer programming algorithm for the minimum congestion unsplittable shortest path routing problem,\\u000a which

  8. Algorithms and Sensors for Small Robot Path Following

    NASA Technical Reports Server (NTRS)

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

    2002-01-01

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

  9. Parallel Traveling Salesman Problem

    NSDL National Science Digital Library

    David Joiner

    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.

  10. Partial charge transfer in the shortest possible metallofullerene peapod, La@C82 ?[11]cycloparaphenylene.

    PubMed

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

    2014-10-27

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

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

    NASA Astrophysics Data System (ADS)

    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

    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.

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

    NASA Astrophysics Data System (ADS)

    Schlindwein, W.; Baptista, R.

    2014-10-01

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

  13. Solar path: how soon

    Microsoft Academic Search

    M. Meinel; A. Meinel

    1978-01-01

    The Meinels, in analyzing solar-energy prospects, point out that those involved in trying to make the solar option a reality still face many problems that are often lost in the enthusiasm of solar proponents. Scientists have not found solutions to the basic problems of unreliable sunshine and the high capital costs of solar equipment. The problems also include unreliable components,

  14. Performance Analysis of Path Planning Techniques Based on Potential Fields

    Microsoft Academic Search

    Marcelo O. Silva; Willian C. Silva; Roseli A. F. Romero

    2010-01-01

    Path planning is a research sub area of robotic which aims to solve the problem of conducting a robot from a specific position to a goal position in a given environment. The environment can be static or dynamic. This problem is considered complex when more than one robot is considered in a dynamic environment and it is necessary to control

  15. Fractional quantum mechanics and Lévy path integrals

    NASA Astrophysics Data System (ADS)

    Laskin, Nikolai

    2000-04-01

    A new extension of a fractality concept in quantum physics has been developed. The path integrals over the Lévy paths are defined and fractional quantum and statistical mechanics have been developed via new fractional path integrals approach. A fractional generalization of the Schrödinger equation has been found. The new relation between the energy and the momentum of non-relativistic fractional quantum-mechanical particle has been established. We have derived a free particle quantum-mechanical kernel using Fox's H-function. The equation for the fractional plane wave function has been obtained. As a physical application of the developed fQM we have proposed a new fractional approach to the QCD problem of quarkonium. A fractional generalization of the motion equation for the density matrix has been found. The density matrix of a free particle has been expressed in term of the Fox's H-function. We also discuss the relationships between fractional and the well-known Feynman path integral approaches to quantum and statistical mechanics.

  16. Quad-rotor flight path energy optimization

    NASA Astrophysics Data System (ADS)

    Kemper, Edward

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

  17. Finding Two Disjoint Paths in a Network with Normalized alpha+-MIN-SUM Objective Function

    Microsoft Academic Search

    Bing Yang; S. Q. Zheng; Enyue Lu

    2005-01-01

    Given a number with , a graph and two nodes and in , we consider the problem of finding two disjoint paths and from to such that with is minimized. The paths may be node-disjoint or edge-disjoint, and the network may be directed or undi- rected. This problem has applications in reliable com- munication. We show that all four versions

  18. REAL-TIME PATH PLANNING IN UNKNOWN ENVIRONMENTS USING A VIRTUAL HILL

    Microsoft Academic Search

    Min Gyu Park; Min Cheol Lee; Kwon Son

    The artificial potential field based path planning has been most wisely used for local path planning because it provides simple and efficient motion planners for practical purposes. However, this approach has a local minimum problem which can trap a robot before reaching its goal. The local minimum problem is sometimes inevitable when a mobile robot moves in unknown environments, because

  19. Drilling path optimization by the particle swarm optimization algorithm with global convergence characteristics

    Microsoft Academic Search

    Guang-Yu Zhu; Wei-Bo Zhang

    2008-01-01

    Drilling path optimization is one of the key problems in holes-machining. This paper presents a new approach to solve the drilling path optimization problem belonging to discrete space, based on the particle swarm optimization (PSO) algorithm. Since the standard PSO algorithm is not guaranteed to be global convergent or local convergent, based on the mathematical model, the algorithm is improved

  20. JAVA PathFinder

    NASA Technical Reports Server (NTRS)

    Mehhtz, Peter

    2005-01-01

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

  1. Corrections to the continuous time semiclassical coherent state path integral

    NASA Astrophysics Data System (ADS)

    Yanay, Y.; Mueller, E. J.

    2015-04-01

    By returning to the underlying discrete time formalism, we relate spurious results in coherent state semiclassical path integral calculations, i.e. those involving quadratic fluctuations about classical paths, to the high frequency structure of their propagators. We show how to modify the standard expressions for thermodynamic quantities to yield correct results. These expressions are relevant to a broad range of physical problems, from the thermodynamics of Bose lattice gases to the dynamics of spin systems.

  2. Constructs of highly effective heat transport paths by bionic optimization

    Microsoft Academic Search

    Xinguang Cheng; Zhixin Li; Zengyuan Guo

    2003-01-01

    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

  3. pathChirp: Efficient Available Bandwidth Estimation for Network Paths

    SciTech Connect

    Cottrell, Les

    2003-04-30

    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.

  4. Two arm robot path planning in a static environment using polytopes and string stretching. Thesis

    NASA Technical Reports Server (NTRS)

    Schima, Francis J., III

    1990-01-01

    The two arm robot path planning problem has been analyzed and reduced into components to be simplified. This thesis examines one component in which two Puma-560 robot arms are simultaneously holding a single object. The problem is to find a path between two points around obstacles which is relatively fast and minimizes the distance. The thesis involves creating a structure on which to form an advanced path planning algorithm which could ideally find the optimum path. An actual path planning method is implemented which is simple though effective in most common situations. Given the limits of computer technology, a 'good' path is currently found. Objects in the workspace are modeled with polytopes. These are used because they can be used for rapid collision detection and still provide a representation which is adequate for path planning.

  5. Path-tracking of a tractor-trailer vehicle along rectilinear and circular paths: a Lyapunov-based approach

    Microsoft Academic Search

    Alessandro Astolfi; Paolo Bolzern; Arturo Locatelli

    2004-01-01

    The problem of asymptotic stabilization for straight and cir- cular forward\\/backward motions of a tractor-trailer system is addressed using Lyapunov techniques. Smooth, bounded, nonlinear control laws achieving asymptotic stability along the desired path are designed, and explicit bounds on the region of attraction are provided. The problem of asymptotic controllability with bounded control is also addressed.

  6. A Flight Examination of Operating Problems of V/STOL Aircraft in STOL-Type Landing and Approach

    NASA Technical Reports Server (NTRS)

    Innis, Robert C.; Quigley, Hervey C.

    1961-01-01

    A flight investigation has been conducted using a large twin-engine cargo aircraft to isolate the problems associated with operating propeller-driven aircraft in the STOL speed range where appreciable engine power is used to augment aerodynamic lift. The problems considered would also be representative of those of a large overloaded VTOL aircraft operating in an STOL manner with comparable thrust-to-weight ratios. The study showed that operation at low approach speeds was compromised by the necessity of maintaining high thrust to generate high lift and yet achieving the low lift-drag ratios needed for steep descents. The useable range of airspeed and flight path angle was limited by the pilot's demand for a positive climb margin at the approach speed, a suitable stall margin, and a control and/or performance margin for one engine inoperative. The optimum approach angle over an obstacle was found to be a compromise between obtaining the shortest air distance and the lowest touchdown velocity. In order to realize the greatest low-speed potential from STOL designs, the stability and control characteristics must be satisfactory.

  7. Internet's critical path horizon

    NASA Astrophysics Data System (ADS)

    Valverde, S.; Solé, R. V.

    2004-03-01

    Internet is known to display a highly heterogeneous structure and complex fluctuations in its traffic dynamics. Congestion seems to be an inevitable result of user's behavior coupled to the network dynamics and it effects should be minimized by choosing appropriate routing strategies. But what are the requirements of routing depth in order to optimize the traffic flow? In this paper we analyse the behavior of Internet traffic with a topologically realistic spatial structure as described in a previous study [S.-H. Yook et al., Proc. Natl Acad. Sci. USA 99, 13382 (2002)]. The model involves self-regulation of packet generation and different levels of routing depth. It is shown that it reproduces the relevant key, statistical features of Internet's traffic. Moreover, we also report the existence of a critical path horizon defining a transition from low-efficient traffic to highly efficient flow. This transition is actually a direct consequence of the web's small world architecture exploited by the routing algorithm. Once routing tables reach the network diameter, the traffic experiences a sudden transition from a low-efficient to a highly-efficient behavior. It is conjectured that routing policies might have spontaneously reached such a compromise in a distributed manner. Internet would thus be operating close to such critical path horizon.

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

    PubMed Central

    Jan, Shau Shiun; Lin, Yu Hsiang

    2011-01-01

    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

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

    PubMed

    Jan, Shau Shiun; Lin, Yu Hsiang

    2011-01-01

    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

  10. Collaborative Authoring of Walden's Paths

    E-print Network

    Li, Yuanling

    2012-10-19

    COLLABORATIVE AUTHORING OF WALDEN’S PATHS A Thesis by YUANLING LI Submitted to the Office of Graduate Studies of Texas A&M University in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE... August 2012 Major Subject: Computer Science Collaborative Authoring of Walden’s Paths Copyright 2012 Yuanling Li COLLABORATIVE AUTHORING OF WALDEN’S PATHS A Thesis by YUANLING LI...

  11. Interactive cutting path analysis programs

    NASA Technical Reports Server (NTRS)

    Weiner, J. M.; Williams, D. S.; Colley, S. R.

    1975-01-01

    The operation of numerically controlled machine tools is interactively simulated. Four programs were developed to graphically display the cutting paths for a Monarch lathe, Cintimatic mill, Strippit sheet metal punch, and the wiring path for a Standard wire wrap machine. These programs are run on a IMLAC PDS-ID graphic display system under the DOS-3 disk operating system. The cutting path analysis programs accept input via both paper tape and disk file.

  12. Path planning for virtual bronchoscopy.

    PubMed

    Negahdar, Mohamadreza; Ahmadian, Alireza; Navab, Nassir; Firouznia, Kavous

    2006-01-01

    We have developed an automated path planning method, which enables virtual bronchoscopic 3D multidetector computed tomography (MDCT) image analysis and follow on image-guided bronchoscopy. The method fundamentals are novel combination of distance transformation and snake-based models. The computation time of our algorithm is faster than similar works and there were no missing or false branches in the final path of airways. The planned path is suitable for quantitative airway analysis and smooth virtual navigation. PMID:17946384

  13. Handbook of Feynman Path Integrals

    NASA Astrophysics Data System (ADS)

    Grosche, Christian, Steiner, Frank

    The Handbook of Feynman Path Integrals appears just fifty years after Richard Feynman published his pioneering paper in 1948 entitled "Space-Time Approach to Non-Relativistic Quantum Mechanics", in which he introduced his new formulation of quantum mechanics in terms of path integrals. The book presents for the first time a comprehensive table of Feynman path integrals together with an extensive list of references; it will serve the reader as a thorough introduction to the theory of path integrals. As a reference book, it is unique in its scope and will be essential for many physicists, chemists and mathematicians working in different areas of research.

  14. 757 Path Loss Measurements

    NASA Technical Reports Server (NTRS)

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

    2005-01-01

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

  15. One-dimensional Gromov minimal filling problem

    SciTech Connect

    Ivanov, Alexandr O; Tuzhilin, Alexey A

    2012-05-31

    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.

  16. Approximating the Generalized Minimum Manhattan Network Problem

    E-print Network

    Kobourov, Stephen G.

    Approximating the Generalized Minimum Manhattan Network Problem Aparna Das1 , Krzysztof Fleszar2¨urzburg, Germany Abstract. We consider the generalized minimum Manhattan network problem (GMMN). The input-length rectilinear network that connects every pair in R by a Manhattan path, that is, a path of axis-parallel line

  17. A Large Family of Multi-path Dual Congestion Control Algorithms

    E-print Network

    Liu, Ying; Xu, Ke; Shen, Meng; Zhong, Yifeng

    2011-01-01

    The goal of traffic management is efficiently utilizing network resources via adapting of source sending rates and routes selection. Traditionally, this problem is formulated into a utilization maximization problem. The single-path routing scheme fails to react to instantaneous network congestion. Multi-path routing schemes thus have been proposed aiming at improving network efficiency. Unfortunately, the natural optimization problem to consider is concave but not strictly concave. It thus brings a huge challenge to design stable multi-path congestion control algorithms. In this paper, we propose a generalized multi-path utility maximization model to consider the problem of routes selection and flow control, and derive a family of multi-path dual congestion control algorithms. We show that the proposed algorithms are stable in the absence of delays. We also derive decentralized and scalable sufficient conditions for a particular scheme when propagation delays exist in networks. Simulations are implemented usi...

  18. Using Runtime Paths for Macroanalysis

    Microsoft Academic Search

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

    2003-01-01

    We introduce macroanalysis, an approach used to infer the high-level properties of dynamic, distributed systems, and an indispensable tool when faced with tasks where lo- cal context and individual component details are insuffi- cient. We present a new methodology, runtime path anal- ysis, where paths are traced through software components and then aggregated to understand global system behav- ior via

  19. Path Analysis: A Brief Introduction.

    ERIC Educational Resources Information Center

    Carducci, Bernardo J.

    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…

  20. Optimal Path to a Laser Fusion Energy Power Plant

    NASA Astrophysics Data System (ADS)

    Bodner, Stephen

    2013-10-01

    There was a decision in the mid 1990s to attempt ignition using indirect-drive targets. It is now obvious that this decision was unjustified. The target design was too geometrically complex, too inefficient, and too far above plasma instability thresholds. By that same time, the mid 1990s, there had also been major advances in the direct-drive target concept. It also was not yet ready for a major test. Now, finally, because of significant advances in target designs, laser-target experiments, and laser development, the direct-drive fusion concept is ready for significant enhancements in funding, on the path to commercial fusion energy. There are two laser contenders. A KrF laser is attractive because of its shortest wavelength, broad bandwidth, and superb beam uniformity. A frequency-converted DPSSL has the disadvantage of inherently narrow bandwidth and longer wavelength, but by combining many beams in parallel one might be able to produce at the target the equivalent of an ultra-broad bandwidth. One or both of these lasers may also meet all of the engineering and economic requirements for a reactor. It is time to further develop and evaluate these two lasers as rep-rate systems, in preparation for a future high-gain fusion test.

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

    NASA Astrophysics Data System (ADS)

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

    2013-06-01

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

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

    NASA Astrophysics Data System (ADS)

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

    2014-01-01

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

  3. Reasoning with Temporal Logic on Truncated Paths

    E-print Network

    Francalanza, Adrian

    Reasoning with Temporal Logic on Truncated Paths Cindy Eisner1 Dana Fisman1,2 John Havlicek3 Yoad of reasoning with linear temporal logic on truncated paths. A truncated path is a path which is finite for reasoning about truncated paths, and analyze its characteristics. 1 Introduction Traditional ltl semantics

  4. Mobile transporter path planning using a genetic algorithm approach

    NASA Technical Reports Server (NTRS)

    Baffes, Paul; Wang, Lui

    1988-01-01

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

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

    E-print Network

    Mousavi, Mohammad

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

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

    E-print Network

    Mousavi, Mohammad

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

  7. An expert path through a thermo maze

    NASA Astrophysics Data System (ADS)

    Kustusch, Mary Bridget; Roundy, David; Dray, Tevian; Manogue, Corinne

    2013-01-01

    Several studies in recent years have demonstrated that upper-division students struggle with partial derivatives and the complicated chain rules ubiquitous in thermodynamics. We asked several experts (primarily faculty who teach thermodynamics) to solve a challenging and novel thermodynamics problem in order to understand how they navigate through this maze. What we found was a tremendous variety in solution strategies and sense-making tools, both within and between individuals. This case study focuses on one particular expert: his solution paths, use of sense-making tools, and comparison of different approaches.

  8. Inferring a Graph from Path Frequency

    E-print Network

    Lonardi, Stefano

    s. K: level (>0) : alphabet f2 #12;8 Problem 1 Ex) ={a,b}, K=2, v=(vaa,vab,vba,vbb)=(1,1,0,2) f2 s which, if it exists, satisfies fK(s) = v, otherwise "no solution." |s|=(vaa+vab+vba+vbb)+(K-1 a Eulerian path Ex.2) K=3, v=(vaaa,vaab,vaba,vabb,vbaa,vbab,vbba,vbbb)=(1,1,0,1,1,1,2,1) Ex.1) K=2, v=(vaa,vab

  9. Crack path prediction near an elliptical inclusion

    NASA Astrophysics Data System (ADS)

    Patton, E. M.; Santare, M. H.

    1993-01-01

    A technique is presented which will predict the path of a naturally growing crack where the stress field can be modeled as two-dimensional. The Green function for an arbitrarily oriented edge dislocation interacting with a rigid inclusion (or void) is used in an integral formulation of the elasticity problem. The technique uses a boundary integral approach to solve for the dislocation density along an arbitrarily shaped crack interacting with a rigid elliptical inclusion or void. The crack path is parameterized as a cubic spline, and a first order perturbation solution is employed to account for the generally curvilinear nature of the crack. The singular integrals are solved using a numerical technique which describes the distribution of dislocations along the crack as a piecewise quadratic polynomial to transform the integral equations into algebraic equations well suited to a matrix-type solution. Results of each step of the analysis have been verified with previously published results, and with experimental results of a crack propagating near an open circular hole. New results are also presented as paths of cracks interacting with inclusions of differing ellipticity ratios and at different orientations with respect to the initial crack.

  10. A bat algorithm with mutation for UCAV path planning.

    PubMed

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

    2012-01-01

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

  11. British Pathe Newsreels Online

    NSDL National Science Digital Library

    2002-01-01

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

  12. Reconfigurable data path processor

    NASA Technical Reports Server (NTRS)

    Donohoe, Gregory (Inventor)

    2005-01-01

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

  13. Heuristic optimization of the scanning path of particle therapy beams.

    PubMed

    Pardo, J; Donetti, M; Bourhaleb, F; Ansarinejad, A; Attili, A; Cirio, R; Garella, M A; Giordanengo, S; Givehchi, N; La Rosa, A; Marchetto, F; Monaco, V; Pecka, A; Peroni, C; Russo, G; Sacchi, R

    2009-06-01

    Quasidiscrete scanning is a delivery strategy for proton and ion beam therapy in which the beam is turned off when a slice is finished and a new energy must be set but not during the scanning between consecutive spots. Different scanning paths lead to different dose distributions due to the contribution of the unintended transit dose between spots. In this work an algorithm to optimize the scanning path for quasidiscrete scanned beams is presented. The classical simulated annealing algorithm is used. It is a heuristic algorithm frequently used in combinatorial optimization problems, which allows us to obtain nearly optimal solutions in acceptable running times. A study focused on the best choice of operational parameters on which the algorithm performance depends is presented. The convergence properties of the algorithm have been further improved by using the next-neighbor algorithm to generate the starting paths. Scanning paths for two clinical treatments have been optimized. The optimized paths are found to be shorter than the back-and-forth, top-to-bottom (zigzag) paths generally provided by the treatment planning systems. The gamma method has been applied to quantify the improvement achieved on the dose distribution. Results show a reduction of the transit dose when the optimized paths are used. The benefit is clear especially when the fluence per spot is low, as in the case of repainting. The minimization of the transit dose can potentially allow the use of higher beam intensities, thus decreasing the treatment time. The algorithm implemented for this work can optimize efficiently the scanning path of quasidiscrete scanned particle beams. Optimized scanning paths decrease the transit dose and lead to better dose distributions. PMID:19610293

  14. Pathways with PathWhiz

    PubMed Central

    Pon, Allison; Jewison, Timothy; Su, Yilu; Liang, Yongjie; Knox, Craig; Maciejewski, Adam; Wilson, Michael; Wishart, David S.

    2015-01-01

    PathWhiz (http://smpdb.ca/pathwhiz) is a web server designed to create colourful, visually pleasing and biologically accurate pathway diagrams that are both machine-readable and interactive. As a web server, PathWhiz is accessible from almost any place and compatible with essentially any operating system. It also houses a public library of pathways and pathway components that can be easily viewed and expanded upon by its users. PathWhiz allows users to readily generate biologically complex pathways by using a specially designed drawing palette to quickly render metabolites (including automated structure generation), proteins (including quaternary structures, covalent modifications and cofactors), nucleic acids, membranes, subcellular structures, cells, tissues and organs. Both small-molecule and protein/gene pathways can be constructed by combining multiple pathway processes such as reactions, interactions, binding events and transport activities. PathWhiz's pathway replication and propagation functions allow for existing pathways to be used to create new pathways or for existing pathways to be automatically propagated across species. PathWhiz pathways can be saved in BioPAX, SBGN-ML and SBML data exchange formats, as well as PNG, PWML, HTML image map or SVG images that can be viewed offline or explored using PathWhiz's interactive viewer. PathWhiz has been used to generate over 700 pathway diagrams for a number of popular databases including HMDB, DrugBank and SMPDB. PMID:25934797

  15. A Note on the Traveling Preacher Problem S andor P. Fekete

    E-print Network

    Fekete, Sándor P.

    In this paper, we consider a problem of cost allocations for shortest roundtrips. Given a weighted graph G = (V; E), we are to #12;nd a subset S #18; V with a maximum weight core element for the Traveling Preacher are called \\games"; while Competitive Game Theory studies the strategies of con ict, Cooperative Game Theory

  16. Real-Time Edge Follow: A New Paradigm to Real-Time Path Search

    Microsoft Academic Search

    Cagatay Undeger; Faruk Polat; Ziya Ipekkan

    2001-01-01

    Path searching and mission planning are challenging problems in many domains such as war games, robotics, military mission planning, computer-generated forces, etc. The objective of this study is to develop a real-time path- planning algorithm to accomplish specified missions on large landscapes. For that purpose, a real-time goal- directed path search algorithm, Real-Time Edge Follow (RTEF), which can work on

  17. A matrix-based approach to searching colored paths in a weighted colored multidigraph

    Microsoft Academic Search

    Haiyan Xu; Kevin W. Li; D. Marc Kilgour; Keith W. Hipel

    2009-01-01

    An algebraic approach to finding all edge-weighted-colored paths within a weighted colored multidigraph is developed. Generally, the adjacency matrix represents a simple digraph and determines all paths between any two vertices, and is not readily extendable to colored multidigraphs. To bridge the gap, a conversion function is proposed to transform the original problem of searching edge-colored paths in a colored

  18. An Evolutionary Artificial Potential Field Algorithm for Dynamic Path Planning of Mobile Robot

    Microsoft Academic Search

    Qixin Cao; Yanwen Huang; Jingliang Zhou

    2006-01-01

    The artificial potential field (APF) method is widely used for autonomous mobile robot path-planning due to its simplicity and mathematical elegance. However, most researches are focused on solving the path-planning problem in a stationary environment, where both targets and obstacles are stationary. This paper proposes a new APF method for path-planning of mobile robots in a dynamic environment where the

  19. Learning for informative path planning

    E-print Network

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

    2008-01-01

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

  20. COMPUTER SCIENCE: MISCONCEPTIONS, CAREER PATHS

    E-print Network

    Hristidis, Vagelis

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

  1. An introduction to critical paths.

    PubMed

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

    2005-01-01

    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

  2. Scattering theory with path integrals

    SciTech Connect

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

    2014-03-15

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

  3. On the design of path delay fault testable combinational circuits

    Microsoft Academic Search

    Ankan K. Pramanick; Sudhakar M. Reddy

    1990-01-01

    A theoretical framework for investigating the design for the path-delay-fault testability problem is provided. Necessary and sufficient conditions for the existence of general robust tests in a multioutput, multilevel circuit are given. The conditions for the existence of a more restricted class of robust tests are derived from those for general robust tests. A design procedure is given for the

  4. Path tracking control of robot manipulators via the VSS approach

    Microsoft Academic Search

    YONG-DUAN SONG; WEI-BING GAO

    1991-01-01

    The path tracking control problem is considered for a robot manipulator subject to parameter uncertainty and external disturbance. By using the theory of variable structure systems (VSS) and taking advantage of the important property of the robot dynamics, a new control strategy is proposed in which both parameter uncertainty and external disturbance can easily be taken into account. It is

  5. On Probabilistic Completeness and Expected Complexity of Probabilistic Path Planning

    E-print Network

    Utrecht, Universiteit

    robots. Planners for car- like robots that can move both forwards and backwards as well as robots fast robot path planners for a wide variety of problems, involving, e.g., high degree of freedom articulated robots, nonholonomic robots, and multiple robots. In this paper we go into theoretical aspects

  6. Tool path planning for compound surfaces in spray forming processes

    Microsoft Academic Search

    Weihua Sheng; Heping Chen; Ning Xi; Yifan Chen

    2005-01-01

    Spray forming is an emerging manufacturing process. The automated tool planning for this process is a nontrivial problem, especially for geometry-complicated parts consisting of multiple freeform surfaces. Existing tool planning approaches are not able to deal with this kind of compound surface. This paper proposes a tool-path planning approach which optimizes the tool motion performance and the thickness uniformity. There

  7. Path Finding with the Sweep-Line Method using

    E-print Network

    Mailund, Thomas

    in external storage during the state space exploration and gives the same reduction in peak memory usage on-the- y during state space exploration and support path #12;nding by relying on a depth-#12;rst. With these methods, states are written to disk during state space exploration to free up main memory. A main problem

  8. Diffusion in a potential field: Path-integral approach

    Microsoft Academic Search

    V. F. Baibuz; V. Yu. Zitserman; A. N. Drozdov

    1984-01-01

    Within the framework of the path-integral formalism we develop a simple method to solve the Fokker-Planck diffusion problems in a potential field, including the decay of an unstable state. Unlike previous approaches, it yields a unified treatment of all time regimes, and is legitimate for any value of the diffusion coefficient. An attractive feature of our method is that it

  9. Slope Accuracy and Path Planning on Compressed Terrain

    E-print Network

    Varela, Carlos

    Slope Accuracy and Path Planning on Compressed Terrain W. Randolph Franklin1 , Daniel M Tracy1 it is qualitatively different #12;2 Franklin, Tracy, Andrade, Muckell, Inanc, Xie and Cutler from the older data to correlate the real world with the computer model. The problem resides in the computer model's lack of high

  10. Information Flow Testing The Third Path towards Confidentiality Guarantee

    E-print Network

    Paris-Sud XI, Université de

    Information Flow Testing The Third Path towards Confidentiality Guarantee Gurvan Le Guernic1,2, 1 confidentiality of secret information manipulated by a program. Noninterference verifi- cation mechanisms systems, interest in security has increased. This paper deals with the problem of confidentiality, more

  11. Best Mitigation Paths To Effectively Reduce Earth's Orbital Debris

    NASA Technical Reports Server (NTRS)

    Wiegman, Bruce M.

    2009-01-01

    This slide presentation reviews some ways to reduce the problem posed by debris in orbit around the Earth. It reviews the orbital debris environment, the near-term needs to minimize the Kessler syndrome, also known as collisional cascading, a survey of active orbital debris mitigation strategies, the best paths to actively remove orbital debris, and technologies that are required for active debris mitigation.

  12. Optimal capacity placement for path restoration in mesh survivable networks

    Microsoft Academic Search

    R. R. Iraschko; M. H. MacGregor; W. D. Grover

    1996-01-01

    The total capacity required by a transport network to satisfy demand and protect it from failures contributes significantly to its cost. Previously the spare capacity of a network with a given set of working span sizes has been optimized to facilitate span restoration. Path restorable networks can, however, be even more efficient by defining the restoration problem from an end

  13. Quantum Mechanics: Sum Over Paths

    NSDL National Science Digital Library

    Taylor, Edwin F.

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

  14. Follow this path to pollution prevention

    SciTech Connect

    Dyer, J.A.; Mulholland, K.L. [E.I. du Pont de Nemours and Co. (United States)

    1998-01-01

    Processes that minimize the amount of waste generated at the source are the most economical. Even in existing facilities, waste generation can be reduced by more than 30% on average, while at the same time lowering operating costs and new capital investment. This article charts a path to an effective pollution prevention (P{sup 2}) program, with particular emphasis on reducing waste generation in existing manufacturing facilities. It is based on a proven methodology used within the DuPont Co., and can be applied to both large- and small-scale problems. An example illustrates both the how-to of a pollution prevention program, as well as some of the tools and techniques available to tackle waste generation problems by looking inside the pipes and vessels.

  15. Coordinated path-following of multiple underactuated autonomous vehicles with bidirectional communication constraints

    E-print Network

    Hespanha, João Pedro

    Coordinated path-following of multiple underactuated autonomous vehicles with bidirectional autonomous vehicles along given spatial paths, while holding a desired inter-vehicle formation pattern in the problem of coordi- nated motion control of multiple autonomous vehicles. The types of applications

  16. Coordinated path-following control of multiple underactuated autonomous vehicles in the presence of communication failures

    E-print Network

    Sontag, Eduardo

    Coordinated path-following control of multiple underactuated autonomous vehicles in the presence autonomous vehicles along given spatial paths, while holding a desired inter-vehicle formation pattern spawned widespread interest in the problem of coordi- nated motion control of multiple autonomous vehicles

  17. Lookahead Pathology in Real-Time Path-Finding Vadim Bulitko (bulitko@ualberta.ca)

    E-print Network

    Lu?trek, Mitja

    Lookahead Pathology in Real-Time Path-Finding Vadim Bulitko (bulitko@ualberta.ca) University to produce better actions · Sometimes the opposite is true: pathology Setting · Path-finding in grid world of pathology: number of lookahead depths where error is larger than at the previous depth · 1,000 problems (map

  18. Lookahead Pathology in Real-Time Path-Finding Mitja Lustrek (mitja.lustrek@ijs.si)

    E-print Network

    Lu?trek, Mitja

    Lookahead Pathology in Real-Time Path-Finding Mitja Lustrek (mitja.lustrek@ijs.si) Jozef Stefan to produce better actions · Sometimes the opposite is true: pathology Setting · Path-finding in grid world of pathology: number of lookahead depths where error is larger than at the previous depth · 1,000 problems (map

  19. Coordinated Path Planning for Multiple Robots Petr Svestka, Mark H. Overmars

    E-print Network

    Utrecht, Universiteit

    for retrieving multi-robot paths. We have applied the method to car-like robots, and simulation results are presented which show that problems involving up to 5 car-like robots in complex environments are solved: Simulation of 3 car-like robots moving in a cluttered environment. for retrieval of coordinated paths. We

  20. Obstacle-avoidance Path Planning for Soccer Robots Using Particle Swarm Optimization

    Microsoft Academic Search

    Li Wang; Yushu Liu; Hongbin Deng; Yuanqing Xu

    2006-01-01

    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 optimization problem. In this paper a dynamic obstacle-avoidance path planning approach for soccer robot based on particle swarm optimization is presented considering the shape of robot. The mathematical model has been build and a

  1. Path Planning Based on Biphasic Ant Colony Algorithm and Fuzzy Control in Dynamic Environment

    Microsoft Academic Search

    Cai Wenbin; Zhu Qingbao; Hu Jun

    2010-01-01

    This paper presents a simple yet efficient dynamic path planning algorithm based on biphasic ant colony algorithm with fuzzy control in the environment with some dynamic obstacles. A global optimal path is planned by using the Biphasic ACO (BACO) searching algorithm without consideration of any dynamic obstacles to solve the problem of local optimization. On that basis, the fuzzy control

  2. A Smooth Path Tracking Algorithm for Wheeled Mobile Robots with Dynamic Constraints

    Microsoft Academic Search

    Kyoung Chul Koh; Hyung Suck Cho

    1999-01-01

    In order to avoid wheel slippage or mechanical damage during the mobile robot navigation, it is necessary tosmoothly change driving velocity or direction of the mobile robot. This means that dynamic constraints of the mobile robotshould be considered in the design of path tracking algorithm. In the study, a path tracking problem is formulated asfollowing a virtual target vehicle which

  3. Calculation of minimal capacity vectors through k minimal paths under budget and time constraints

    Microsoft Academic Search

    Yi-kuei Lin

    2010-01-01

    Reducing the transmission time is an important issue for a flow network to transmit a given amount of data from the source to the sink. The quickest path problem thus arises to find a single path with minimum transmission time. More specifically, the capacity of each arc is assumed to be deterministic. However, in many real-life networks such as computer

  4. Stochastic flow networks via multiple paths under time threshold and budget constraint

    Microsoft Academic Search

    Yi-Kuei Lin

    2011-01-01

    This paper extends the quickest path problem to a stochastic flow network in which the capacity of each arc is variable. We mainly evaluate the system reliability that d units of data can be sent from the source to the sink under both time threshold T and budget B. In particular, the data are transmitted through multiple disjoint minimal paths

  5. Optimal Pair of Minimal Paths Under Both Time and Budget Constraints

    Microsoft Academic Search

    Yi-Kuei Lin

    2009-01-01

    The quickest path (QP) problem is to find a path which sends a given amount of data from the source to the sink such that the transmission time is minimized. Two attributes are involved, namely, the capacity and the lead time. The capacity of each arc is assumed to be deterministic. However, in many real-life flow networks such as computer

  6. Cooperative path planning for multiple UAVs in dynamic and uncertain environments

    Microsoft Academic Search

    John S. Bellingham; Michael Tillerson; Mehdi Alighanbari

    2002-01-01

    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

  7. Preview path based real-time fuzzy navigation algorithm for mobile robot

    Microsoft Academic Search

    Guoyang Li; Yingying Wu; Wei Wei

    2008-01-01

    The problem of goal-oriented obstacle avoidance for mobile robot in unknown environment is studied. By imitating the preview navigation behavior of human, the paper proposed a novel real-time fuzzy navigation algorithm for mobile robot., Firstly, the preview path was estimated based on the current scenario. The objective orientation of robot was calculated by synthesizing preview path tracking and obstacle avoidance.

  8. All-Pairs Bottleneck Paths in Vertex Weighted Graphs Asaf Shapira

    E-print Network

    Yuster, Raphael

    All-Pairs Bottleneck Paths in Vertex Weighted Graphs Asaf Shapira Raphael Yuster Uri Zwick on its vertices. The bottleneck weight, or the capacity, of a path is the smallest weight of a vertex edge or vertex weights, the algorithm presented for APBP problem works for arbitrary large vertex

  9. Joint Path and Wavelength Selection Using Q-learning in Optical Burst Switching Networks

    Microsoft Academic Search

    T. Venkatesh; Y. V. Kiran; C. Siva Ram Murthy

    2009-01-01

    Contention losses which usually do not indicate congestion is a major issue that hinders the deployment of optical burst switching (OBS) networks. Development of efficient path and wavelength selection algorithms is crucial to minimize the burst loss probability (BLP) in OBS networks. In this paper, we handle path selection and wavelength selection in a joint fashion. We formulate the problem

  10. Paving the Critical Path: How can Clinical Pharmacology Help Achieve the Vision?

    Microsoft Academic Search

    L J Lesko

    2007-01-01

    It has been almost 3 years since the launch of the FDA critical path initiative following the publication of the paper “Innovation or Stagnation: Challenges and Opportunities on the Critical Path of New Medical Product Development.” The initiative was intended to create an urgency with the drug development enterprise to address the so-called “productivity problem” in modern drug development. Clinical

  11. Smoothing of mixed complementarity problems

    SciTech Connect

    Gabriel, S.A.; More, J.J. [Argonne National Lab., IL (United States). Mathematics and Computer Science Div.

    1995-09-01

    The authors introduce a smoothing approach to the mixed complementarity problem, and study the limiting behavior of a path defined by approximate minimizers of a nonlinear least squares problem. The main result guarantees that, under a mild regularity condition, limit points of the iterates are solutions to the mixed complementarity problem. The analysis is applicable to a wide variety of algorithms suitable for large-scale mixed complementarity problems.

  12. Handbook for the estimation of microwave propagation effects: Link calculations for earth-space paths (path loss and noise estimation)

    Microsoft Academic Search

    R. K. Crane; D. W. Blood

    1979-01-01

    A single model for a standard of comparison for other models when dealing with rain attenuation problems in system design and experimentation is proposed. Refinements to the Global Rain Production Model are incorporated. Path loss and noise estimation procedures as the basic input to systems design for earth-to-space microwave links operating at frequencies from 1 to 300 GHz are provided.

  13. Experimental Validation of the Distributed Shortest-Distance Rendezvous Algorithm on a Low-Cost Robot Platform

    E-print Network

    Parikh, Kush Jay

    2013-01-01

    follow. The driver only sends information and never receivesclient receives information from the driver (not necessarydriver is omitted in this experiment) .23 4.2 (b) The neighbor topology (direction of arrow represents the path of information

  14. On hallucinated garden paths UC San Diego

    E-print Network

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

  15. Cooperative organic mine avoidance path planning

    Microsoft Academic Search

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

    2005-01-01

    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

  16. Graphs and Paths Page 1 Introduction

    E-print Network

    Allan, Vicki H.

    ? For example: I want to travel every bike path in Logan (assuming they had any ) but I don't want to everGraphs and Paths Page 1 Chapter 9 Graphs Introduction What are some characteristics of a binary travel on the same path twice. Can I begin at my home, visit every path, and then return? The data

  17. The path of kyosei.

    PubMed

    Kaku, R

    1997-01-01

    Many global companies believe they have a moral duty to respond to the world's problems but are unsure how to do that and still pursue a reasonable profit for their shareholders. Ryuzaburo Kaku, honorary chairman of Canon, the Japanese technology company, suggests that companies consider kyosei, a business credo that he defines as a "spirit of cooperation" in which individuals and organizations work together for the common good. Kyosei, Kaku claims, has helped Canon make a significant and positive impact on many world problems as the company has grown to become one of the world's preeminent innovators and manufacturers of technology. The implementation of kyosei can be divided into five stages, with each stage building on the preceding one. In the first stage, companies must work to secure a predictable stream of profits and to establish strong market positions. From this foundation, they move on to the second stage, in which managers and workers resolve to cooperate with each other, recognizing that both groups are vital to the company's success. In the third stage, this sense of cooperation is extended beyond the company to encompass customers, suppliers, community groups, and even competitors. At the fourth stage, a company takes the cooperative spirit beyond national boundaries and addresses some of the global imbalances that plague the world. In the fifth stage, which companies rarely achieve, a company urges its national government to work toward rectifying global imbalances. For each stage, Kaku provides detailed examples from Cannon's own experience in putting the ideas of kyosei into practice. PMID:10168336

  18. Solving the Curriculum Sequencing Problem with DNA Computing Approach

    ERIC Educational Resources Information Center

    Debbah, Amina; Ben Ali, Yamina Mohamed

    2014-01-01

    In the e-learning systems, a learning path is known as a sequence of learning materials linked to each others to help learners achieving their learning goals. As it is impossible to have the same learning path that suits different learners, the Curriculum Sequencing problem (CS) consists of the generation of a personalized learning path for each…

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

    E-print Network

    Kulling, Karl Christian

    2009-01-01

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

  20. Asymptotically-optimal path planning for manipulation using incremental sampling-based algorithms

    E-print Network

    Perez, Alejandro Tomas

    A desirable property of path planning for robotic manipulation is the ability to identify solutions in a sufficiently short amount of time to be usable. This is particularly challenging for the manipulation problem due to ...

  1. A ``cellular neuronal'' approach to optimization problems

    NASA Astrophysics Data System (ADS)

    Duane, Gregory S.

    2009-09-01

    The Hopfield-Tank [J. J. Hopfield and D. W. Tank, Biol. Cybern. 52, 141 (1985)] recurrent neural network architecture for the traveling salesman problem is generalized to a fully interconnected "cellular" neural network of regular oscillators. Tours are defined by synchronization patterns, allowing the simultaneous representation of all cyclic permutations of a given tour. The network converges to local optima some of which correspond to shortest-distance tours, as can be shown analytically in a stationary phase approximation. Simulated annealing is required for global optimization, but the stochastic element might be replaced by chaotic intermittency in a further generalization of the architecture to a network of chaotic oscillators.

  2. Light transport on path-space manifolds

    NASA Astrophysics Data System (ADS)

    Jakob, Wenzel Alban

    The pervasive use of computer-generated graphics in our society has led to strict demands on their visual realism. Generally, users of rendering software want their images to look, in various ways, "real", which has been a key driving force towards methods that are based on the physics of light transport. Until recently, industrial practice has relied on a different set of methods that had comparatively little rigorous grounding in physics---but within the last decade, advances in rendering methods and computing power have come together to create a sudden and dramatic shift, in which physics-based methods that were formerly thought impractical have become the standard tool. As a consequence, considerable attention is now devoted towards making these methods as robust as possible. In this context, robustness refers to an algorithm's ability to process arbitrary input without large increases of the rendering time or degradation of the output image. One particularly challenging aspect of robustness entails simulating the precise interaction of light with all the materials that comprise the input scene. This dissertation focuses on one specific group of materials that has fundamentally been the most important source of difficulties in this process. Specular materials, such as glass windows, mirrors or smooth coatings (e.g. on finished wood), account for a significant percentage of the objects that surround us every day. It is perhaps surprising, then, that it is not well-understood how they can be accommodated within the theoretical framework that underlies some of the most sophisticated rendering methods available today. Many of these methods operate using a theoretical framework known as path space integration. But this framework makes no provisions for specular materials: to date, it is not clear how to write down a path space integral involving something as simple as a piece of glass. Although implementations can in practice still render these materials by side-stepping limitations of the theory, they often suffer from unusably slow convergence; improvements to this situation have been hampered by the lack of a thorough theoretical understanding. We address these problems by developing a new theory of path-space light transport which, for the first time, cleanly incorporates specular scattering into the standard framework. Most of the results obtained in the analysis of the ideally smooth case can also be generalized to rendering of glossy materials and volumetric scattering so that this dissertation also provides a powerful new set of tools for dealing with them. The basis of our approach is that each specular material interaction locally collapses the dimension of the space of light paths so that all relevant paths lie on a submanifold of path space. We analyze the high-dimensional differential geometry of this submanifold and use the resulting information to construct an algorithm that is able to "walk" around on it using a simple and efficient equation-solving iteration. This manifold walking algorithm then constitutes the key operation of a new type of Markov Chain Monte Carlo (MCMC) rendering method that computes lighting through very general families of paths that can involve arbitrary combinations of specular, near-specular, glossy, and diffuse surface interactions as well as isotropic or highly anisotropic volume scattering. We demonstrate our implementation on a range of challenging scenes and evaluate it against previous methods.

  3. A rapid path planner for autonomous ground vehicle using section collision detection

    Microsoft Academic Search

    Zhe Leng; Min-zhou Dong; Gang-qi Dong; Jie Yan

    2009-01-01

    Rapid path planner plays an important role in autonomous ground vehicle (AGV) operation. Depending on the non-holonomic kinematics\\u000a constraints of AGV, its path planning problem is discussed. Since rapidly-exploring random tree (RRT) can directly take non-holonomic\\u000a constraints into consideration, it is selected to solve this problem. By applying extra constraints on the movement, the generation\\u000a of new configuration in RRT

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

    NASA Astrophysics Data System (ADS)

    Jung, Dongwon

    2007-12-01

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

  5. Aircraft Engine Gas Path Diagnostic Methods: Public Benchmarking Results

    NASA Technical Reports Server (NTRS)

    Simon, Donald L.; Borguet, Sebastien; Leonard, Olivier; Zhang, Xiaodong (Frank)

    2013-01-01

    Recent technology reviews have identified the need for objective assessments of aircraft engine health management (EHM) technologies. To help address this issue, a gas path diagnostic benchmark problem has been created and made publicly available. This software tool, referred to as the Propulsion Diagnostic Method Evaluation Strategy (ProDiMES), has been constructed based on feedback provided by the aircraft EHM community. It provides a standard benchmark problem enabling users to develop, evaluate and compare diagnostic methods. This paper will present an overview of ProDiMES along with a description of four gas path diagnostic methods developed and applied to the problem. These methods, which include analytical and empirical diagnostic techniques, will be described and associated blind-test-case metric results will be presented and compared. Lessons learned along with recommendations for improving the public benchmarking processes will also be presented and discussed.

  6. The Path Ahead

    NASA Astrophysics Data System (ADS)

    Tuszynski, Jack A.; Woolf, Nancy

    This chapter provides an introduction to the rest of the book, which has a multidisciplinary approach to the physics of consciousness. We summarize the various contributions and present our own point of view, which is that there are some deficiencies in defining higher-order consciousness in strict terms of classic physics. We favor a proposal that considers some aspects of quantum-mechanical operations among molecules involved with neurotransmission and mechanical transport of synaptic proteins. In our view, the wiring of the brain is not as complex, and certainly not as integrated, as commonly assumed. Instead, the wiring pattern redundantly obeys a few general principles focused on high resolution rather than crossmodal integration. Basing cognitive functions, such as higher-order consciousness, solely on electrophysiological responses in neural networks thus wired may not suffice. On the other hand, coherent quantum computing, executed by tubulins, the protein subunits of microtubules, may exert en masse influences over the transport of many receptor and scaffolding proteins to various activated synapses, thereby accounting for the unity of conscious experience. We discuss the potential problems of quantum computing, such as decoherence, and also present counterarguments, as well as recent empirical results consistent with the notion that quantum computing in the interiors of neurons, in particular, within the interiors of dendrites may indeed be possible.

  7. Evaluation of steam path audits

    SciTech Connect

    Caudill, M.B. [Tri-State Generation and Transmission Association, Inc., Montrose, CO (United States); Griebenow, R.D. [SAIC, Huntersville, NC (United States)

    1995-06-01

    Tri-State Generation and Transmission association is the operating agent for the 1350 megawatt Craig Generating Station, located in northwestern Colorado. Tri-State has recently incorporated turbine steam path audits into their aggressive performance improvement program. The intent of the audits are to quantify and attain the most cost effective increase in turbine performance as a result of a major outage. Valuable information about performance losses in the turbine has been obtained from steam path audits conducted on the three Craig Units. However, accurate audit results often depend on the quality of measurements and the experience of the auditor. Without a second method to verify the results of a steam path audit, repairs might be performed on a non-cost effective basis, or significant performance degradations might be overlooked. In addition, an inaccurate audit may lead to erroneous expectations for performance improvements resulting from the maintenance performed during the outage.

  8. Obstacle Bypassing in Optimal Ship Routing Using Simulated Annealing

    SciTech Connect

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

    2008-11-06

    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.

  9. Multiple paths in complex tasks

    NASA Technical Reports Server (NTRS)

    Galanter, Eugene; Wiegand, Thomas; Mark, Gloria

    1987-01-01

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

  10. Path Integral Monte Carlo Methods for Fermions

    NASA Astrophysics Data System (ADS)

    Ethan, Ethan; Dubois, Jonathan; Ceperley, David

    2014-03-01

    In general, Quantum Monte Carlo methods suffer from a sign problem when simulating fermionic systems. This causes the efficiency of a simulation to decrease exponentially with the number of particles and inverse temperature. To circumvent this issue, a nodal constraint is often implemented, restricting the Monte Carlo procedure from sampling paths that cause the many-body density matrix to change sign. Unfortunately, this high-dimensional nodal surface is not a priori known unless the system is exactly solvable, resulting in uncontrolled errors. We will discuss two possible routes to extend the applicability of finite-temperatue path integral Monte Carlo. First we extend the regime where signful simulations are possible through a novel permutation sampling scheme. Afterwards, we discuss a method to variationally improve the nodal surface by minimizing a free energy during simulation. Applications of these methods will include both free and interacting electron gases, concluding with discussion concerning extension to inhomogeneous systems. Support from DOE DE-FG52-09NA29456, DE-AC52-07NA27344, LLNL LDRD 10- ERD-058, and the Lawrence Scholar program.

  11. Matrix Multiply-Add in Min-plus Algebra on a Short-vector SIMD Processor of Cell\\/B.E

    Microsoft Academic Search

    Kazuya Matsumoto; Stanislav G. Sedukhin

    2010-01-01

    It is well-known that the all-pairs shortest paths problem has a similar algorithmic characteristic to the classical matrix-matrix multiply-add (MMA) problem, one of the differences between the two problems is in the underlying algebra: the matrix multiply-add uses linear (+, ×)-algebra whereas the all-pairs shortest paths problem uses (min, +)-algebra. This paper presents an implementation of 64×64 matrix multiply-add kernel

  12. Better approximation bounds for the network and Euclidean Steiner tree problems

    Microsoft Academic Search

    Alexander Zelikovsky

    1995-01-01

    The network and Euclidean Steiner tree problems require a shortest tree spanninga given vertex subset within a network G = (V; E; d) and Euclidean plane, respectively.For these problems, we present a series of heuristics finding approximate Steiner tree withperformance guarantee coming arbitrary close to 1+ln2 1:693 and 1+ln2p3 1:1438,respectively. The best previously known corresponding values are close to 1.746

  13. UV laser long-path absorption spectroscopy

    NASA Technical Reports Server (NTRS)

    Dorn, Hans-Peter; Brauers, Theo; Neuroth, Rudolf

    1994-01-01

    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 using a high resolution spectrograph. The detection system has been improved over the formerly used optomechanical scanning device by application of a photodiode array which increased the observed spectral range by a factor of 6 and which utilizes the light much more effectively leading to a considerable reduction of the measurement time. This technique provides direct measurements of OH because the signal is given by the product of the absorption coefficient and the OH concentration along the light path according to Lambert-Beers law. No calibration is needed. Since the integrated absorption coefficient is well known the accuracy of the measurement essentially depends on the extent to which the OH absorption pattern can be detected in the spectra. No interference by self generated OH radicals in the detection lightpath has been observed. The large bandwidth (greater than 0.15 nm) and the high spectral resolution (1.5 pm) allows absolute determination of interferences by other trace gas absorptions. The measurement error is directly accessible from the absorption-signal to baseline-noise ratio in the spectra. The applicability of the method strongly depends on visibility. Elevated concentrations of aerosols lead to considerable attenuation of the laser light which reduces the S/N-ratio. In the moderately polluted air of Julich, where we performed a number of OH measurement spectra. In addition absorption features of unidentified species were frequently detected. A quantitative deconvolution even of the known species is not easy to achieve and can leave residual structures in the spectra. Thus interferences usually increase the noise and deteriorate the OH detection sensitivity. Using diode arrays for sensitive absorption measurements some specific problems of those detectors have to be solved experimentally (i.e. fixed pattern noise, dark signal noise, nonuniform efficiency of individual elements, spatial sensitivity variations). In order to improve the low spatial resolution we performed laboratory studies using a multiple reflection cell to convert the long path technique to a real in situ point measurement. Under the conditions of field experiments in Julich residual absorbance signals at present are about 1.5x10(exp -4) corresponding to an OH detection sensitivity of 2x10(exp 6) OH/cm(exp 3) using a light path of 5.8 km. Total integration times for one measurement point vary between a few minutes and an hour.

  14. Alternative Nuclear Paths To 2050

    Microsoft Academic Search

    Ivan Vera; Evelyne Bertel; Geoffrey Stevens

    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

  15. NPRE at Illinois Three Paths

    E-print Network

    Gilbert, Matthew

    NPRE at Illinois Three Paths Students choose from three concentrations: · Plasma and Fusion · Power,312,815 Research Facilities · Beckman Institute (beckman.illinois.edu) · Center for Plasma-Material Interactions (cpmi.illinois.edu) · Institute for Genomic Biology (igb.illinois.edu) · Micro and Nanotechnology

  16. Moldovan employment relations: “path dependency”?

    Microsoft Academic Search

    Claudio Morrison; Richard Croucher

    2010-01-01

    Purpose – The paper aims to examine the theory that trade unions' functions in a transitional economy are characterised by “path dependency”. Design\\/methodology\\/approach – The research is based on case studies of employment relations in enterprises operating in Moldova. The approach is realist (critical materialism). An ethnographic approach is taken to analysing social relations in three locally and foreign-owned companies

  17. Noncommutative Geometry and Path Integrals

    Microsoft Academic Search

    Mikhail Kapranov

    2006-01-01

    \\u000a We argue that there should exist a “noncommutative Fourier transform” which should identify functions of noncommutative variables\\u000a (say, of matrices of indeterminate size) and ordinary functions or measures on the space of paths. Some examples are considered.

  18. WHEELCHAIR NEGOTIABLE PATHS ACCESSIBLE ENTRANCE

    E-print Network

    Huang, Jianyu

    NEGOTIABLE PATHS ACCESSIBLE ENTRANCE ACCESSIBLE PARKING SPACE ELEVATOR ACCESS KEY PPUBLIC PARKING BUS STOP ENTRANCE ACCESSIBLE PARKING SPACE ELEVATOR ACCESS KEY PPUBLIC PARKING BUS STOP (EAGLE ESCORT) BLUE LIGHT SPACE ELEVATOR ACCESS KEY PPUBLIC PARKING BUS STOP (EAGLE ESCORT) BLUE LIGHT EMERGENCY PHONE #12

  19. Magnetic Refocussing of Electron Paths

    Microsoft Academic Search

    W. E. Stephens

    1934-01-01

    A general method of magnetic direction refocussing, i.e., the refocussing of slightly divergent electron paths in a uniform magnetic field, has been found, of which the familiar 180° refocussing is a particular case. If we use a wedge-shaped magnetic field, whose lines of force are perpendicular to the plane of motion of an electron beam, the field being produced by

  20. SSME propellant path leak detection

    NASA Technical Reports Server (NTRS)

    Crawford, Roger; Shohadaee, Ahmad Ali

    1989-01-01

    The complicated high-pressure cycle of the space shuttle main engine (SSME) propellant path provides many opportunities for external propellant path leaks while the engine is running. This mode of engine failure may be detected and analyzed with sufficient speed to save critical engine test hardware from destruction. The leaks indicate hardware failures which will damage or destroy an engine if undetected; therefore, detection of both cryogenic and hot gas leaks is the objective of this investigation. The primary objective of this phase of the investigation is the experimental validation of techniques for detecting and analyzing propellant path external leaks which have a high probability of occurring on the SSME. The selection of candidate detection methods requires a good analytic model for leak plumes which would develop from external leaks and an understanding of radiation transfer through the leak plume. One advanced propellant path leak detection technique is obtained by using state-of-the-art technology infrared (IR) thermal imaging systems combined with computer, digital image processing, and expert systems for the engine protection. The feasibility of IR leak plume detection is evaluated on subscale simulated laboratory plumes to determine sensitivity, signal to noise, and general suitability for the application.

  1. Optimized Fermion Path Integral Monte Carlo

    NASA Astrophysics Data System (ADS)

    Khairallah, Saad; Draeger, Erik; Shumway, John

    2011-03-01

    We present the latest developments in a new path integral Monte Carlo method for continuum fermions. The new formalism uses the maximum entropy principle to map the approximated density matrix to an effective bosonic problem. Verification and performance results are presented for both free electrons and compressed hydrogen, showing accurate results with a substantial performance gain over reference slice fPIMC, particularly at lower temperatures where ergodicity issues can significantly impact sampling efficiency. The limiting approximations in the method are identified and discussed, and suggest the need for improved nodal models. This work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under Contract DE-AC52-07NA27344.

  2. An O(ND) Difference Algorithm and Its Variations

    Microsoft Academic Search

    Eugene W. Myers

    1986-01-01

    The problems of findinga longest common subsequence of two sequences A and B and a shortest edit script for transforming A into B have long been known to be dual problems. In this paper, they are shown to be equivalent to finding a shortest\\/longest path in an edit graph. Using this perspective, a simple O(ND) time and space algorithm is

  3. Sampling-based algorithms for optimal path planning problems

    E-print Network

    Karaman, Sertac

    2012-01-01

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

  4. Path-Integral Approach to Problems in Quantum Optics 

    E-print Network

    Hillery, M.; Zubairy, M. Suhail

    1982-01-01

    an interrelated 'cycle' that once started and controlled in the proper direction is almost self-building in improvement. Energy conservation is the driving force to create additive progress involving system flexibility, process integration, and less energy...

  5. Robust Path Planning and Feedback Design Under Stochastic Uncertainty

    NASA Technical Reports Server (NTRS)

    Blackmore, Lars

    2008-01-01

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

  6. Overexpression of the shortest isoform of histone demethylase LSD1 primes hematopoietic stem cells for malignant transformation.

    PubMed

    Wada, Taeko; Koyama, Daisuke; Kikuchi, Jiro; Honda, Hiroaki; Furukawa, Yusuke

    2015-06-11

    Recent investigations indicate that epigenetic regulators act at the initial step of myeloid leukemogenesis by forming preleukemic hematopoietic stem cells (HSCs), which possess the increased self-renewal potential but retain multidifferentiation ability, and synergize with genetic abnormalities in later stages to develop full-blown acute myeloid leukemias. However, it is still unknown whether this theory is applicable to other malignancies. In this study, we demonstrate that lysine-specific demethylase 1 (LSD1) overexpression is a founder abnormality for the development of T-cell lymphoblastic leukemia/lymphoma (T-LBL) using LSD1 transgenic mice. LSD1 expression is tightly regulated via alternative splicing and transcriptional repression in HSCs and is altered in most leukemias, especially T-LBL. Overexpression of the shortest isoform of LSD1, which is specifically repressed in quiescent HSCs and demethylates histone H3K9 more efficiently than other isoforms, increases self-renewal potential via upregulation of the HoxA family but retains multidifferentiation ability with a skewed differentiation to T-cell lineages at transcriptome levels in HSCs. Transgenic mice overexpressing LSD1 in HSCs did not show obvious abnormalities but developed T-LBL at very high frequency after ?-irradiation. LSD1 overexpression appears to be the first hit in T-cell leukemogenesis and provides an insight into novel strategies for early diagnosis and effective treatment of the disease. PMID:25904247

  7. Diffusion weighted imaging-based maximum density path analysis and classification of Alzheimer's disease.

    PubMed

    Nir, Talia M; Villalon-Reina, Julio E; Prasad, Gautam; Jahanshad, Neda; Joshi, Shantanu H; Toga, Arthur W; Bernstein, Matt A; Jack, Clifford R; Weiner, Michael W; Thompson, Paul M

    2015-01-01

    Characterizing brain changes in Alzheimer's disease (AD) is important for patient prognosis and for assessing brain deterioration in clinical trials. In this diffusion weighted imaging study, we used a new fiber-tract modeling method to investigate white matter integrity in 50 elderly controls (CTL), 113 people with mild cognitive impairment, and 37 AD patients. After clustering tractography using a region-of-interest atlas, we used a shortest path graph search through each bundle's fiber density map to derive maximum density paths (MDPs), which we registered across subjects. We calculated the fractional anisotropy (FA) and mean diffusivity (MD) along all MDPs and found significant MD and FA differences between AD patients and CTL subjects, as well as MD differences between CTL and late mild cognitive impairment subjects. MD and FA were also associated with widely used clinical scores. As an MDP is a compact low-dimensional representation of white matter organization, we tested the utility of diffusion tensor imaging measures along these MDPs as features for support vector machine based classification of AD. PMID:25444597

  8. Residues crucial for maintaining short paths in network communication mediate signaling in proteins.

    PubMed

    del Sol, Antonio; Fujihashi, Hirotomo; Amoros, Dolors; Nussinov, Ruth

    2006-01-01

    Here, we represent protein structures as residue interacting networks, which are assumed to involve a permanent flow of information between amino acids. By removal of nodes from the protein network, we identify fold centrally conserved residues, which are crucial for sustaining the shortest pathways and thus play key roles in long-range interactions. Analysis of seven protein families (myoglobins, G-protein-coupled receptors, the trypsin class of serine proteases, hemoglobins, oligosaccharide phosphorylases, nuclear receptor ligand-binding domains and retroviral proteases) confirms that experimentally many of these residues are important for allosteric communication. The agreement between the centrally conserved residues, which are key in preserving short path lengths, and residues experimentally suggested to mediate signaling further illustrates that topology plays an important role in network communication. Protein folds have evolved under constraints imposed by function. To maintain function, protein structures need to be robust to mutational events. On the other hand, robustness is accompanied by an extreme sensitivity at some crucial sites. Thus, here we propose that centrally conserved residues, whose removal increases the characteristic path length in protein networks, may relate to the system fragility. PMID:16738564

  9. Routing Optimization in Optical Burst Switching Networks: a Multi-path Routing Approach

    NASA Astrophysics Data System (ADS)

    Klinkowski, Miros?aw; Marciniak, Marian; Pióro, Micha?

    This chapter concerns routing optimization in optical burst switching (OBS) networks. OBS is a photonic network technology aiming at efficient transport of IP traffic. OBS architectures are in general bufferless and therefore sensitive to burst congestion. An overall burst loss probability (BLP) which adequately represents the congestion state of the entire network is the primary metric of interest in an OBS network. The network congestion can be reduced by using proper routing. We consider multi-path source routing and aim at optimal distribution of traffic over the network. In this context, we study three network loss models, a well-known loss model of an OBS network and two original approximate models. Since the objective function of each model is nonlinear, either linear programming formulations with piecewise linear approximations of this function or nonlinear optimization gradient methods can be used. The presented solution is based on nonlinear optimization; for this purpose we provide the formulas for calculation of partial derivatives. The main goal of this chapter is to show that the use of approximate models allows us to speed up significantly the optimization procedure without losing much accuracy. Moreover we show that our method effectively distributes the traffic over the network, and the overall BLP can be reduced compared with both shortest path routing and alternative routing.

  10. The Symmetric Quadratic Traveling Salesman Problem

    E-print Network

    problem. Applying this strengthening to subtour elimi- nation constraints gives rise to facet defining-TSP) introduced by Aggarwal et. al. [3] which is used for the optimization of robot paths with respect

  11. Path perception during rotation: influence of instructions, depth range, and dot density

    NASA Technical Reports Server (NTRS)

    Li, Li; Warren, William H Jr

    2004-01-01

    How do observers perceive their direction of self-motion when traveling on a straight path while their eyes are rotating? Our previous findings suggest that information from retinal flow and extra-retinal information about eye movements are each sufficient to solve this problem for both perception and active control of self-motion [Vision Res. 40 (2000) 3873; Psych. Sci. 13 (2002) 485]. In this paper, using displays depicting translation with simulated eye rotation, we investigated how task variables such as instructions, depth range, and dot density influenced the visual system's reliance on retinal vs. extra-retinal information for path perception during rotation. We found that path errors were small when observers expected to travel on a straight path or with neutral instructions, but errors increased markedly when observers expected to travel on a curved path. Increasing depth range or dot density did not improve path judgments. We conclude that the expectation of the shape of an upcoming path can influence the interpretation of the ambiguous retinal flow. A large depth range and dense motion parallax are not essential for accurate path perception during rotation, but reference objects and a large field of view appear to improve path judgments.

  12. Model for Delay Faults Based upon Paths

    Microsoft Academic Search

    Gordon L. Smith

    1985-01-01

    Delay testing of combinational logic in a clocked environment is analyzed. A model based upon paths is introduced for delay faults. Any path with a total delay exceeding the clock interval is called a \\

  13. Path-Based Failure and Evolution Management

    Microsoft Academic Search

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

    2004-01-01

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

  14. Electron Inelastic-Mean-Free-Path Database

    National Institute of Standards and Technology Data Gateway

    SRD 71 NIST Electron Inelastic-Mean-Free-Path Database (PC database, no charge)   This database provides values of electron inelastic mean free paths (IMFPs) for use in quantitative surface analyses by AES and XPS.

  15. Path integral Monte Carlo and the electron gas

    NASA Astrophysics Data System (ADS)

    Brown, Ethan W.

    Path integral Monte Carlo is a proven method for accurately simulating quantum mechanical systems at finite-temperature. By stochastically sampling Feynman's path integral representation of the quantum many-body density matrix, path integral Monte Carlo includes non-perturbative effects like thermal fluctuations and particle correlations in a natural way. Over the past 30 years, path integral Monte Carlo has been successfully employed to study the low density electron gas, high-pressure hydrogen, and superfluid helium. For systems where the role of Fermi statistics is important, however, traditional path integral Monte Carlo simulations have an exponentially decreasing efficiency with decreased temperature and increased system size. In this thesis, we work towards improving this efficiency, both through approximate and exact methods, as specifically applied to the homogeneous electron gas. We begin with a brief overview of the current state of atomic simulations at finite-temperature before we delve into a pedagogical review of the path integral Monte Carlo method. We then spend some time discussing the one major issue preventing exact simulation of Fermi systems, the sign problem. Afterwards, we introduce a way to circumvent the sign problem in PIMC simulations through a fixed-node constraint. We then apply this method to the homogeneous electron gas at a large swatch of densities and temperatures in order to map out the warm-dense matter regime. The electron gas can be a representative model for a host of real systems, from simple medals to stellar interiors. However, its most common use is as input into density functional theory. To this end, we aim to build an accurate representation of the electron gas from the ground state to the classical limit and examine its use in finite-temperature density functional formulations. The latter half of this thesis focuses on possible routes beyond the fixed-node approximation. As a first step, we utilize the variational principle inherent in the path integral Monte Carlo method to optimize the nodal surface. By using a ansatz resembling a free particle density matrix, we make a unique connection between a nodal effective mass and the traditional effective mass of many-body quantum theory. We then propose and test several alternate nodal ansatzes and apply them to single atomic systems. Finally, we propose a method to tackle the sign problem head on, by leveraging the relatively simple structure of permutation space. Using this method, we find we can perform exact simulations this of the electron gas and 3He that were previously impossible.

  16. Path Planning for Autonomous Underwater Vehicles

    Microsoft Academic Search

    Clément Pêtrès; Yan Pailhas; Pedro Patrón; Yvan R. Petillot; Jonathan Evans

    2007-01-01

    Efficient path planning algorithms are a crucial issue for modern autonomous underwater vehicles. Classical path planning algorithms in artificial intelligence are not designed to deal with wide continuous environments prone to currents. We present a novel Fast Marching based approach to address the following issues. First, we develop an algorithm we call FM* to efficiently extract a continuous path from

  17. Quantifying the Causes of Path Inflation

    Microsoft Academic Search

    Neil Spring; Ratul Mahajan; Thomas Anderson

    2003-01-01

    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

  18. Continuous Path Planning with Multiple Constraints

    E-print Network

    Mitchell, Ian

    paths for unmanned aerial vehicles through enviroments with varying levels of threat. Paths an algorithm which generates paths whose costs lie on the Pareto optimal surface for each possible destina destination can be rapidly evaluated. To handle constraints, we sample the Pareto optimal surface looking

  19. Path and Trajectory Diversity Theory and Algorithms

    E-print Network

    Branicky, Michael S.

    Path and Trajectory Diversity Theory and Algorithms Ross A. Knepper International Conference. Kuffner #12;R.A. Knepper Path and Trajectory Diversity 2 Applications [Knepper and Mason, ISER, 2008][Lau and Trajectory Diversity 3 Not all path sets are created equal Introduction Conclusion

  20. 14 CFR 25.111 - Takeoff path.

    Code of Federal Regulations, 2011 CFR

    2011-01-01

    ...surface to the end of the takeoff path. (d) The takeoff path must be determined by a continuous demonstrated takeoff or by synthesis from segments. If the takeoff path is determined by the segmental method— (1) The segments must be clearly...

  1. Removing False Paths from Combinational Modules 1

    Microsoft Academic Search

    Yuji Kukimoto; Robert K. Brayton

    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)

  2. Chip layout optimization using critical path weighting

    Microsoft Academic Search

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

    1984-01-01

    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

  3. Chip layout optimization using critical path weighting

    Microsoft Academic Search

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

    1988-01-01

    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

  4. Squeezed states and path integrals

    NASA Technical Reports Server (NTRS)

    Daubechies, Ingrid; Klauder, John R.

    1992-01-01

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

  5. Lévy flights over quantum paths

    NASA Astrophysics Data System (ADS)

    Laskin, Nick

    2007-02-01

    An impact of integration over the paths of the Lévy flights on the quantum mechanical kernel has been studied. Analytical expression for a free particle kernel has been obtained in terms of the Fox H-function. A new equation for the kernel of a particle in the box has been found. New general results include the well known quantum formulae for a free particle kernel and particle in box kernel.

  6. Path-Planning for RTS Games Based on Potential Fields

    Microsoft Academic Search

    Renato Silveira; Leonardo Fischer; José Antônio Salini Ferreira; Edson Prestes e Silva Jr.; Luciana Porcher Nedel

    2010-01-01

    \\u000a Many games, in particular RTS games, are populated by synthetic humanoid actors that act as autonomous agents. The navigation\\u000a of these agents is yet a challenge if the problem involves finding a precise route in a virtual world (path-planning), and\\u000a moving realistically according to its own personality, intentions and mood (motion planning). In this paper we present several\\u000a complementary approaches

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

    Microsoft Academic Search

    A. Farrel

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

  8. Round-the-clock homing behavior of a subsocial shield bug, Parastrachia japonensis (Heteroptera: Parastrachiidae), using path integration.

    PubMed

    Hironaka, Mantaro; Tojo, Sumio; Nomakuchi, Shintaro; Filippi, Lisa; Hariyama, Takahiko

    2007-06-01

    Females of the subsocial shield bug, Parastrachia japonensis (Parastrachiidae), are central-place foragers, collecting drupes for their young from nearby host trees by walking along the forest floor both during the day and at night. Because burrows are often some distance from the drupe-shedding tree, the bugs must repeatedly leave their burrows, search for drupes, and return to the burrows. After a bug leaves its burrow, it searches arduously until it encounters a drupe. When a drupe is obtained, the bug always takes the shortest route back to its burrow. It has been clarified that this bug utilizes path integration during diurnal provisioning excursions. In this paper, we examined nocturnal behavior and some parameters of the path integration utilized by P. japonensis. There were no observable differences between day and night in the patterns of foraging and direct-homing behavior. When the bug was displaced to another position during the day or night, it always walked straight toward the fictive burrow, the site where the burrow should be if it had been displaced along with the bug, and then displayed searching behavior in the vicinity of the fictive burrow. The distance of the straight run corresponded accurately with a straight line between the burrow and the place where the bug obtained the drupe. These results indicate that P. japonensis orients toward the burrow using path integration both during diurnal and nocturnal provisioning behavior. PMID:17867854

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

    SciTech Connect

    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

    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.

  10. Arithmetic area for m planar Brownian paths

    NASA Astrophysics Data System (ADS)

    Desbois, Jean; Ouvry, Stéphane

    2012-05-01

    We pursue the analysis made in Desbois and Ouvry (2011 J. Stat. Mech. P05024) on the arithmetic area enclosed by m closed Brownian paths. We pay particular attention to the random variable Sn1, n2,..., nm(m), which is the arithmetic area of the set of points, also called winding sectors, enclosed n1 times by path 1, n2 times by path 2,..., and nm times by path m. Various results are obtained in the asymptotic limit m\\to \\infty . A key observation is that, since the paths are independent, one can use in the m-path case the SLE information, valid in the one-path case, on the zero-winding sectors arithmetic area.

  11. Inquiry-based learning templates for creating online educational paths 

    E-print Network

    Davis, Sarah Alice

    2006-10-30

    (with annotation enlarged)............................................. 49 9 Second Stop in Density Path (with annotation enlarged) ........................................ 49 10 Third Stop in Density Path..........................................................................................50 11 Fourth Stop in Density Path..................................................................................... 50 12 Last Stop in Density Path (with annotation enlarged)............................................. 50 13 Opening...

  12. Graphs and Matroids Weighted in a Bounded Incline Algebra

    PubMed Central

    Lu, Ling-Xia; Zhang, Bei

    2014-01-01

    Firstly, for a graph weighted in a bounded incline algebra (or called a dioid), a longest path problem (LPP, for short) is presented, which can be considered the uniform approach to the famous shortest path problem, the widest path problem, and the most reliable path problem. The solutions for LPP and related algorithms are given. Secondly, for a matroid weighted in a linear matroid, the maximum independent set problem is studied. PMID:25126607

  13. Graphs and matroids weighted in a bounded incline algebra.

    PubMed

    Lu, Ling-Xia; Zhang, Bei

    2014-01-01

    Firstly, for a graph weighted in a bounded incline algebra (or called a dioid), a longest path problem (LPP, for short) is presented, which can be considered the uniform approach to the famous shortest path problem, the widest path problem, and the most reliable path problem. The solutions for LPP and related algorithms are given. Secondly, for a matroid weighted in a linear matroid, the maximum independent set problem is studied. PMID:25126607

  14. Regularization Paths for Generalized Linear Models via Coordinate Descent

    PubMed Central

    Friedman, Jerome; Hastie, Trevor; Tibshirani, Rob

    2010-01-01

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

  15. Domains of bosonic Functional integrals and some applications to the mathematical physics of path integrals and String Theory

    E-print Network

    Luiz. C. L. Botelho

    2012-07-02

    By means of the Minlos Theorem on support of cylindrical measures on vectorial topological spaces, we present several results on the rigorous definitions of Euclidean path integrals and applications to some problems on non-linear diffusion, nonlinear wave propagations and covariant Polyakov"s path Integrals yielding news results on the subject as well.

  16. ISE 536{Fall03: Linear Programming and Extensions November 24, 2003 Lecture 22: IPM, Path Following Methods

    E-print Network

    Ordóñez, Fernando

    ISE 536{Fall03: Linear Programming and Extensions November 24, 2003 Lecture 22: IPM, Path Following Path Following IPM To solve (P ) min c t x s:t: Ax = b x #21; 0 we consider the modi#12;ed problem (P

  17. A Multi-stage Probabilistic Algorithm for Dynamic Path-Planning

    E-print Network

    Barriga, Nicolas A

    2009-01-01

    Probabilistic sampling methods have become very popular to solve single-shot path planning problems. Rapidly-exploring Random Trees (RRTs) in particular have been shown to be efficient in solving high dimensional problems. Even though several RRT variants have been proposed for dynamic replanning, these methods only perform well in environments with infrequent changes. This paper addresses the dynamic path planning problem by combining simple techniques in a multi-stage probabilistic algorithm. This algorithm uses RRTs for initial planning and informed local search for navigation. We show that this combination of simple techniques provides better responses to highly dynamic environments than the RRT extensions.

  18. Robust Flight Path Determination for Mars Precision Landing Using Genetic Algorithms

    NASA Technical Reports Server (NTRS)

    Bayard, David S.; Kohen, Hamid

    1997-01-01

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

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

    PubMed Central

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

    2010-01-01

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

  20. The Geometrical Representation of Path Planning Leo Dorst, Indur Mandhyan, Karen Trovato

    E-print Network

    Dorst, Leo

    is briefly discussed. Applications of the theory to mo­ tion planning for a robot arm, a maneuvering car Movers' Problem [17] and the motion of robot arms [11], as well as more recent problems such as car ma framework for path planning, illustrated by examples for a robot, a parking car, and a simplified Rubik