Shortest viable path algorithm in multimodal networks
Angelica Lozano; Giovanni Storchi
2001-01-01
We consider an approach using label correcting techniques to find the shortest viable path from an origin to a destination, in a multimodal transportation network. A path is called viable if its sequence of modes is feasible with respect to a set of constraints. We present an ad hoc modification of the Chronological Algorithm to solve the multimodal shortest viable
An improved Physarum polycephalum algorithm for the shortest path problem.
Zhang, Xiaoge; Wang, Qing; Adamatzky, Andrew; Chan, Felix T S; Mahadevan, Sankaran; Deng, Yong
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
An Improved Physarum polycephalum Algorithm for the Shortest Path Problem
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
Copyright 2000, Kevin Wayne 1 Dijkstra's Shortest Path Algorithm
Kosecka, Jana
14 0 S = { s, 2, 3, 6, 7 } PQ = { 4, 5, t } X X X 44 X 35X 59 XX51 X 34 X 33X 32 14 Dijkstra, 7 } PQ = { 4, 5, t } X X X 44 X 35X 59 XX51 X 34 delmin X 33X 32 24 15 Dijkstra's Shortest Path = { 4, t } X X X 44 X 35X 59 XX51 X 34 24 X50 X45 X 33X 32 16 Dijkstra's Shortest Path Algorithm s 3
Modeling wildfire propagation with Delaunay triangulation and shortest path algorithms
Smith, J. MacGregor
Modeling wildfire propagation with Delaunay triangulation and shortest path algorithms Alexander In this paper, a methodology for modeling surface wildfire propagation through a complex landscape is presented, wildfire modeling 1 Introduction During the years 2000-2004, the National Interagency Fire Center (NIFC
Parallel Shortest Path Algorithms for Solving Large-Scale Instances
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
Multiple Object Tracking Using the Shortest Path Faster Association Algorithm
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
An improved bio-inspired algorithm for the directed shortest path problem.
Zhang, Xiaoge; Zhang, Yajuan; Deng, Yong
2014-12-01
Because most networks are intrinsically directed, the directed shortest path problem has been one of the fundamental issues in network optimization. In this paper, a novel algorithm for finding the shortest path in directed networks is proposed. It extends a bio-inspired path finding model of Physarum polycephalum, which is designed only for undirected networks, by adopting analog circuit analysis. Illustrative examples are given to show the effectiveness of the proposed algorithm in finding the directed shortest path. PMID:25405318
A Shortest Path Based Path Planning Algorithm for Nonholonomic Mobile Robots
Kaichun Jiang; Lakmal D. Seneviratne; S. W. E. Earles
1999-01-01
A path planning algorithm for a mobile robot subject to nonholonomic constraints is presented. The algorithmemploys a global- local strategy, and solves the problem in the 2D workspace of the robot, without generating the complexconfiguration space. Firstly, a visibility graph is constructed for finding a collision-free shortest path for a point. Secondly,the path for a point is evaluated to find
Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs
Valerie King
1999-01-01
This paper presents the first fully dynamic algorithms for maintaining all-pairs shortest paths in digraphs with posi- tive integer weights less than . For approximate shortest paths with an error factor of 2 , for any positive con- stant , the amortized update time is 2 log2 log log ; for an error factor of 1 the amortized update time
Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths
Michael L. Fredman; Dan E. Willard
1990-01-01
The fusion tree method is extended to develop a linear-time algorithm for the minimum spanning tree problem and an O(m +n log n\\/log log n) implementation of Dijkstra's shortest-path algorithm for a graph with n vertices and m edges. The shortest-path algorithm surpasses information-theoretic limitations. The extension of the fusion tree method involves the development of a new data structure,
A Faster Algorithm for the Single Source Shortest Path Problem with Few Distinct Positive Lengths
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 ...
Soft-decision Decoding of Block Codes using the k Shortest Paths Algorithm
Ismail Shakeel; Alex Grant
2006-01-01
In this paper, we develop a soft-decision decoding algorithm for block codes using the k shortest paths algorithm. The performance of this algorithm is investigated and compared with other decoding schemes. The results show the proposed algorithm gives large gains over the generalised minimum distance (GMD) decoding algorithm and algebraic hard-decision decoding. Further, the proposed algorithm achieves near-MLD performance for
Lanthier, Mark
.g., water, rock, forest). Considering weighted metrics however increases the run-time of algorithms consid-of-the-art Beowulf cluster with gigabit interconnect and a shared-memory architecture, SunFire. 1 Introduction algorithms for realistic shortest path problems are either very complex and/or have very large time and space
: A Directed On-The-Fly Algorithm for Finding the k Shortest Paths
Reiterer, Harald
K : A Directed On-The-Fly Algorithm for Finding the k Shortest Paths Husain Aljazzar and Stefan prominent algorithm for solving this problem, K has two advan- tages. First, K performs on-the-fly, which. Application domain examples for KSP problems include computer chess, sequence alignment and probabilistic
a Shortest Path Algorithm for a Network with Various Fuzzy Arc Lengths
NASA Astrophysics Data System (ADS)
Tajdin, Ali; Mahdavi, Iraj; Mahdavi-Amiri, Nezam; Sadeghpour-Gildeh, Bahram; hadighi, Rofideh
2010-06-01
We are concerned with the design of a model and an algorithm for computing a shortest path in a network having various types of fuzzy arc lengths. First, we develop a new technique for the addition of various fuzzy numbers in a path using ? -cuts. Then, we propose a regression model for obtaining membership function for the considered addition. Finally, we present a dynamic programming method for finding a shortest path in the network. An example is worked out to illustrate the applicability of the proposed approach.
Shortest Paths in Digraphs of Small Part I: Sequential Algorithms
weight path between them, while a distance query only asks for the weight of such a path. This approach preprocessing time). Recently, in 17], the distance query time is improved to O( (n)), where (n) is the inverse Abstract We consider the problem of preprocessing an n-vertex digraph with real edge weights so
An Improved Ant Colony Algorithm for the Shortest Path Problem in Time-Dependent Networks
NASA Astrophysics Data System (ADS)
Chang, Qing; Liu, Yongqiang; Xiong, Huagang
Research of the shortest path problem in time-dependent networks has important practical value. An improved pheromone update strategy suitable for time-dependent networks was proposed. Under this strategy, the residual pheromone of each road can accurately reflect the change of weighted value of each road. An improved selection strategy between adjacent cities was used to compute the cities' transfer probabilities, as a result, the amount of calculation is greatly reduced. To avoid the algorithm converging to the local optimal solution, the ant colony algorithm was combined with genetic algorithm. In this way, the solutions after each traversal were used as the initial species to carry out single-point crossover. An improved ant colony algorithm for the shortest path problem in time-dependent networks based on these improved strategies was presented. The simulation results show that the improved algorithm has greater probability to get the global optimal solution, and the convergence rate of algorithm is better than traditional ant colony algorithm.
Parallel shortest augmenting path algorithm for the assignment problem. Technical report
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.
NASA Astrophysics Data System (ADS)
Schafer, Sebastian; Singh, Vikas; Hoffmann, Kenneth R.; Noël, Peter B.; Xu, Jinhui
2007-03-01
Endovascular interventional procedures are being used more frequently in cardiovascular surgery. Unfortunately, procedural failure, e.g., vessel dissection, may occur and is often related to improper guidewire and/or device selection. To support the surgeon's decision process and because of the importance of the guidewire in positioning devices, we propose a method to determine the guidewire path prior to insertion using a model of its elastic potential energy coupled with a representative graph construction. The 3D vessel centerline and sizes are determined for a specified vessel. Points in planes perpendicular to the vessel centerline are generated. For each pair of consecutive planes, a vector set is generated which joins all points in these planes. We construct a graph representing these vector sets as nodes. The nodes representing adjacent vector sets are joined by edges with weights calculated as a function of the angle between the corresponding vectors (nodes). The optimal path through this weighted directed graph is then determined using shortest path algorithms, such as topological sort based shortest path algorithm or Dijkstra's algorithm. Volumetric data of an internal carotid artery phantom (Ø 3.5mm) were acquired. Several independent guidewire (Ø 0.4mm) placements were performed, and the 3D paths were determined using rotational angiography. The average RMS distance between the actual and the average simulated guidewire path was 0.7mm; the computation time to determine the path was 3 seconds. The ability to predict the guidewire path inside vessels may facilitate calculation of vessel-branch access and force estimation on devices and the vessel wall.
Physarum can compute shortest paths.
Bonifaci, Vincenzo; Mehlhorn, Kurt; Varma, Girish
2012-09-21
Physarum polycephalum is a slime mold that is apparently able to solve shortest path problems. A mathematical model has been proposed by Tero et al. (Journal of Theoretical Biology, 244, 2007, pp. 553-564) to describe the feedback mechanism used by the slime mold to adapt its tubular channels while foraging two food sources s(0) and s(1). We prove that, under this model, the mass of the mold will eventually converge to the shortest s(0)-s(1) path of the network that the mold lies on, independently of the structure of the network or of the initial mass distribution. This matches the experimental observations by Tero et al. and can be seen as an example of a "natural algorithm", that is, an algorithm developed by evolution over millions of years. PMID:22732274
Identification of Novel Thyroid Cancer-Related Genes and Chemicals Using Shortest Path Algorithm
Zhang, Peiwei; Li, Li-Peng; He, Yi-Chun; Gao, Ru-jian; Gao, Yu-Fei
2015-01-01
Thyroid cancer is a typical endocrine malignancy. In the past three decades, the continued growth of its incidence has made it urgent to design effective treatments to treat this disease. To this end, it is necessary to uncover the mechanism underlying this disease. Identification of thyroid cancer-related genes and chemicals is helpful to understand the mechanism of thyroid cancer. In this study, we generalized some previous methods to discover both disease genes and chemicals. The method was based on shortest path algorithm and applied to discover novel thyroid cancer-related genes and chemicals. The analysis of the final obtained genes and chemicals suggests that some of them are crucial to the formation and development of thyroid cancer. It is indicated that the proposed method is effective for the discovery of novel disease genes and chemicals.
Floats, Integers, and Single Source Shortest Paths
Mikkel Thorup
2000-01-01
Floats are ugly, but to everyone but theoretical computer scientists, they are the real thing. A linear time algorithm is presented for the undirected single-source shortest paths problem with nonnegative floating point weights.
Balancing minimum spanning and shortest path trees
Samir Khuller; Balaji Raghavacharit; Neal E. Young
1993-01-01
This paper give a simple linear-time algorithm that, given a weighted\\u000adigraph, finds a spanning tree that simultaneously approximates a shortest-path\\u000atree and a minimum spanning tree. The algorithm provides a continuous\\u000atrade-off: given the two trees and epsilon > 0, the algorithm returns a\\u000aspanning tree in which the distance between any vertex and the root of the\\u000ashortest-path
2014-09-19
Sep 19, 2014 ... Institute of Public Economics, University of Graz, ... s, t ? V . The aim of Shortest Path Game is to find a directed path from s to t in the following .... Assigning arbitrary but fixed numbers to each vertex in the beginning,. e.g. 1,...
Balancing Minimum Spanning Trees and Shortest-Path Trees
Samir Khuller; Balaji Raghavachari; Neal E. Young
1995-01-01
We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous tradeoff: given the two trees and a 7 > 0, the algorithm returns a spanning tree in which the distance between any vertex and the root of the shortest-path tree is at most 1
Floats, Integers, and Single Source Shortest Paths
Mikkel Thorup
1998-01-01
Floats are ugly, but to everyone but theoretical computer scientists, they are thereal thing. A linear time algorithm is presented for the undirected single source shortestpaths problem with positive floating point weights.1 IntroductionThe technical goal of this paper is to present a linear time solution to the undirected singlesource shortest paths problem (USSSP) where the weights are positive floating points,
Exact Geodesics and Shortest Paths on Polyhedral Surfaces
Mukund Balasubramanian; Jonathan R. Polimeni; Eric L. Schwartz
2009-01-01
We present two algorithms for computing distances along convex and non-convex polyhedral surfaces. The first algorithm computes exact minimal-geodesic distances and the second algorithm combines these distances to compute exact shortest-path distances along the surface. Both algorithms have been extended to compute the exact minimal-geodesic paths and shortest paths. These algorithms have been implemented and validated on surfaces for which
Guoliang Xue
2000-01-01
In the QoS shortest path problem, we want to find a path connecting two given vertices u and v to minimize path cost subject to the constraint that the path weight is no greater than a given bound. In the QoS minimum spanning tree problem, we want to find a spanning tree to minimize tree cost subject to the constraint
Balancing Minimum Spanning Trees and Shortest-Path Trees
Samir Khuller; Penn State
1993-01-01
We give a simple algorithm to find a spanning tree that simultaneously approxi- mates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous trade-off: given the two trees and a > 0, the algorithm returns a span- ning tree in which the distance between any vertex and the root of the shortest-path tree is at most
Shortest path and Schramm-Loewner Evolution
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
Using shortest path to discover criminal community
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...
Balancing Minimum Spanning Trees and ShortestPath Trees
Khuller, Samir
Balancing Minimum Spanning Trees and ShortestÂPath Trees Samir Khuller \\Lambda University and a minimum spanning tree. The algorithm provides a continuous tradeÂoff: given the two trees and a fl ? 0 is at most 1 + p 2=fl times the weight of a minimum spanning tree. Our algorithm runs in linear time
Yanfang Deng; Hengqing Tong; Xiedong Zhang
2010-01-01
The shortest path algorithm is critical for dynamic traffic assignment and for the realization of route guidance in intelligent transportation systems (ITS). In this paper, a hybrid Particle Swarm Optimization (PSO) algorithm combined fluid neural network (FNN) to search for the shortest path in stochastic traffic networks is introduced. The algorithm overcomes the weight coefficient symmetry restrictions of the traditional
Finding Shortest Path for Developed Cognitive Map Using Medial Axis
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...
Approximate Shortest Path Queries Using Voronoi Duals
NASA Astrophysics Data System (ADS)
Honiden, Shinichi; Houle, Michael E.; Sommer, Christian; Wolff, Martin
We propose an approximation method to answer point-to-point shortest path queries in undirected edge-weighted graphs, based on random sampling and Voronoi duals. We compute a simplification of the graph by selecting nodes independently at random with probability p. Edges are generated as the Voronoi dual of the original graph, using the selected nodes as Voronoi sites. This overlay graph allows for fast computation of approximate shortest paths for general, undirected graphs. The time-quality tradeoff decision can be made at query time. We provide bounds on the approximation ratio of the path lengths as well as experimental results. The theoretical worst-case approximation ratio is bounded by a logarithmic factor. Experiments show that our approximation method based on Voronoi duals has extremely fast preprocessing time and efficiently computes reasonably short paths.
Undirected single-source shortest paths with positive integer weights in linear time
Mikkel Thorup
1999-01-01
The single-source shortest paths problem (SSSP) is one of the classic problems in algorithmic graph theory: given a positively weighted graph G with a source vertex s, find the shortest path from s to all other vertices in the graph.Since 1959, all theoretical developments in SSSP for general directed and undirected graphs have been based on Dijkstra's algorithm, visiting the
Shortest Path Queries in Digraphs of Small Treewidth
Shiva Chaudhuri; Christos D. Zaroliagis
1995-01-01
We consider the problem of preprocessing an n-vertex di- graph with real edge weights so that subsequent queries for the shortest path or distance between any two vertices can be e-ciently answered. We give algorithms that depend on the treewidth of the input graph. When the treewidth is a constant, our algorithms can answer distance queries in O(fi(n)) time after
Shortest paths in the Tower of Hanoi graph and finite automata
Dan Romik
2003-01-01
We present efficient algorithms for constructing a shortest path be- tween two states in the Tower of Hanoi graph, and for computing the length of the shortest path. The key element is a finite-state machine which decides, after examining on the average only 63 38 ? 1.66 of the largest discs, whether the largest disc will be moved once or
Shortest path in complete bipartite digraph problem and it applications
He, Xin [State Univ. of New York, Buffalo, NY (United States); Chen, Zhi-Zhong [Tokyo Denki Univ., Saitama (Japan)
1997-06-01
We introduce the shortest path in complete bipartite digraph (SPCB) problem: Given a weighted complete bipartite digraph G = (X, Y, E) with X = (x{sub 0},{hor_ellipsis}, Xn) and Y = (y{sub 0},{hor_ellipsis},y{sub m}), find a shortest path from x{sub 0} to x{sub n} in G. For arbitrary weights, the problem needs at least {Omega}(nm) time to solve. We show if the weight matrices are concave, the problem can be solved in O(n + m log n) time. As applications, we discuss the traveling salesman problem for points on a convex polygon and the minimum latency tour problem for points on a straight line. The known algorithms for both problems require {Theta}(n{sup 2}) time. Using our SPCB algorithm, we show they can be solved in O(n log n) time. These results solve two open questions.
Shortest Paths, Soap Films, and Minimal Surfaces
NSDL National Science Digital Library
Dorff, Michael
2012-10-10
You know you're in for a real treat when a lecture starts off with "I just happen to have with me today this bucket filled with soap solution, water, and some glycerin." That happens to be the opening line from a talk given by Professor Michael Dorff at the Mathematical Association of America (MAA). Dorff's talk was quite hands-on and it included a number of skeletal Zometool creations and deconstructed Slinkies, among other items. The title of the talk was "Shortest Paths, Soap Films, and Minimal Surfaces" and it is available here in its entirety. In the lecture, Dorff talks (and demonstrates) the shortest distance between four points, neighborhood accessibility, and a number of fascinating topics.
Self-organization and solution of shortest-path optimization problems with memristive networks
NASA Astrophysics Data System (ADS)
Pershin, Yuriy V.; Di Ventra, Massimiliano
2013-07-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 nonlocality) 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.
Competition for Shortest Paths on Sparse Graphs
NASA Astrophysics Data System (ADS)
Yeung, Chi Ho; Saad, David
2012-05-01
Optimal paths connecting randomly selected network nodes and fixed routers are studied analytically in the presence of a nonlinear overlap cost that penalizes congestion. Routing becomes more difficult as the number of selected nodes increases and exhibits ergodicity breaking in the case of multiple routers. The ground state of such systems reveals nonmonotonic complex behaviors in average path length and algorithmic convergence, depending on the network topology, and densities of communicating nodes and routers. A distributed linearly scalable routing algorithm is also devised.
Shortest paths synthesis for a car-like robot
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
ON THE ACCELERATION OF SHORTEST PATH CALCULATIONS IN TRANSPORTATION NETWORKS
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.
Traffic Grooming Based on Shortest Path in Optical WDM Mesh Networks
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
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.
Dynamic shortest path association for multiple object tracking in video sequence
NASA Astrophysics Data System (ADS)
Xi, Zhenghao; Liu, Heping; Liu, Huaping; Zheng, Yang
2015-01-01
Persistently tracking multiple objects in cluttered environments is very challenging. We present a tracking association approach based on the shortest path faster algorithm. We first formulate the multiple object tracking as an integer programming problem of the flow network. Under this framework, the integer assumption is relaxed to a standard linear programming problem. Therefore, the global optimal solution can quickly be obtained using the fast dynamic shortest path algorithm, which highlights the dynamic programming characteristic of the shortest path, thus faster, algorithm. The proposed method avoids the difficulties of integer programming; more importantly, it has a lower worst-case complexity than competing methods but a better tracking accuracy and robustness in complex environments. Simulation results show that our proposed algorithm takes less time than other methods and can operate in real time.
Deng, Jing
between two people. There have been many algorithms addressing the shortest path analytics. For example such as the massive Facebook graph. Extensive applications of such shortest-path analytics are naturally expected two users are on social networks as well as how fast/far any interesting post from one user can reach
Distributional properties of stochastic shortest paths for smuggled nuclear material
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.
Multicast Routing in Wireless Mesh Networks: Minimum Cost Trees or Shortest Path Trees?
Uyen Trang Nguyen; Jin Xu
2007-01-01
There exist two fundamental approaches to multicast routing: shortest path trees (SPTs) and minimum cost trees (MCTs). The SPT algorithms minimize the distance (or cost) from the sender to each receiver, whereas the MCT algorithms minimize the overall cost of the multicast tree. Due to the very large scale and unknown topology of the Internet, computing MCTs for multicast routing
Influence of the link weight structure on the shortest path
NASA Astrophysics Data System (ADS)
van Mieghem, Piet; van Langen, Stijn
2005-05-01
The shortest path tree rooted at a source to all other nodes is investigated in a graph with polynomial link weights tunable by the power exponent ? . By varying ? , different types of shortest path trees, in short ? trees, appear. Especially, the ??0 regime that corresponds to heavily fluctuating link weights possesses a peculiar type of tree. The most important properties of this ??0 tree are derived in the asymptotic limit for large N . The application of the theoretical insights to real networks (such as the Internet) are discussed: steering flow by adjusting link weights (traffic engineering), sensitivity of link weights and modeling of the network by ? trees.
Ramaswamy, Ramkumar
2004-04-30
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 minimum weights that ...
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 ...
: Heuristics-Guided, On-the-Fly k Shortest Paths Husain Aljazzar and Stefan Leue
Leue, Stefan
K : Heuristics-Guided, On-the-Fly k Shortest Paths Search Husain Aljazzar and Stefan Leue to current KSP algorithms. First, K performs on-the-fly, which means that it does not require the graph examples for KSP problems in- clude logistics, finance analysis, scheduling, sequence alignment, networking
Shortest-Path Kernels on Graphs
Karsten M. Borgwardt; Hans-peter Kriegel
2005-01-01
Data mining algorithms are facing the challenge to deal with an increasing number of complex objects. For graph data, a whole toolbox of data mining algorithms becomes available by defining a kernel function on instances of graphs. Graph kernels based on walks, subtrees and cycles in graphs have been proposed so far. As a general problem, these kernels are either
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
The d-edge shortest-path problem for a Monge graph
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.
A Bio-Inspired Method for the Constrained Shortest Path Problem
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
A Graph Search Heuristic for Shortest Distance Paths
Chow, E
2005-03-24
This paper presents a heuristic for guiding A* search for finding the shortest distance path between two vertices in a connected, undirected, and explicitly stored graph. The heuristic requires a small amount of data to be stored at each vertex. The heuristic has application to quickly detecting relationships between two vertices in a large information or knowledge network. We compare the performance of this heuristic with breadth-first search on graphs with various topological properties. The results show that one or more orders of magnitude improvement in the number of vertices expanded is possible for large graphs, including Poisson random graphs.
The shortest time and/or the shortest path strategies in a CA FF pedestrian dynamics model
Ekaterina Kirik; Tat'yana Yurgel'yan; Dmitriy Krouglov
2009-06-23
This paper deals with a mathematical model of a pedestrian movement. A stochastic cellular automata (CA) approach is used here. The Floor Field (FF) model is a basis model. FF models imply that virtual people follow the shortest path strategy. But people are followed by a strategy of the shortest time as well. This paper is focused on how to mathematically formalize and implement to a model these features of the pedestrian movement. Some results of a simulation are presented.
Damage detection via shortest-path network sampling
NASA Astrophysics Data System (ADS)
Ciulla, Fabio; Perra, Nicola; Baronchelli, Andrea; Vespignani, Alessandro
2014-05-01
Large networked systems are constantly exposed to local damages and failures that can alter their functionality. The knowledge of the structure of these systems is, however, often derived through sampling strategies whose effectiveness at damage detection has not been thoroughly investigated so far. Here, we study the performance of shortest-path sampling for damage detection in large-scale networks. We define appropriate metrics to characterize the sampling process before and after the damage, providing statistical estimates for the status of nodes (damaged, not damaged). The proposed methodology is flexible and allows tuning the trade-off between the accuracy of the damage detection and the number of probes used to sample the network. We test and measure the efficiency of our approach considering both synthetic and real networks data. Remarkably, in all of the systems studied, the number of correctly identified damaged nodes exceeds the number of false positives, allowing us to uncover the damage precisely.
Semi-Dynamic Shortest Paths and Breadth-First Search in Digraphs
Paolo Giulio Franciosa; Daniele Frigioni; Roberto Giaccio
1997-01-01
We show how to maintain a shortest path tree of a general directed graph G with unit edge weights and n vertices, during a sequence of edge deletions or a sequence of edge insertions, in O(n) amortized time per operation using linear space. Distance queries can be answered in constant time, while shortest path queries can be answered in time
Time depending shortest-path problems with applications to railway networks
K. Nachtigall
1995-01-01
In this paper the shortest path problem in a time depending transit network is discussed. A usual approach in public transport is to compute the shortest path for every possible starting time separately by the use of a modified Dijkstra procedure. Here a label correcting method is used to calculate the desired transit function for all starting times with one
Color texture classification using shortest paths in graphs.
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
A minimum resource neural network framework for solving multiconstraint shortest path problems.
Zhang, Junying; Zhao, Xiaoxue; He, Xiaotao
2014-08-01
Characterized by using minimum hard (structural) and soft (computational) resources, a novel parameter-free minimal resource neural network (MRNN) framework is proposed for solving a wide range of single-source shortest path (SP) problems for various graph types. The problems are the k-shortest time path problems with any combination of three constraints: time, hop, and label constraints, and the graphs can be directed, undirected, or bidirected with symmetric and/or asymmetric traversal time, which can be real and time dependent. Isomorphic to the graph where the SP is to be sought, the network is activated by generating autowave at source neuron and the autowave travels automatically along the paths with the speed of a hop in an iteration. Properties of the network are studied, algorithms are presented, and computation complexity is analyzed. The framework guarantees globally optimal solutions of a series of problems during the iteration process of the network, which provides insight into why even the SP is still too long to be satisfied. The network facilitates very large scale integrated circuit implementation and adapt to very large scale problems due to its massively parallel processing and minimum resource utilization. When implemented in a sequentially processing computer, experiments on synthetic graphs, road maps of cities of the USA, and vehicle routing with time windows indicate that the MRNN is especially efficient for large scale sparse graphs and even dense graphs with some constraints, e.g., the CPU time taken and the iteration number used for the road maps of cities of the USA is even less than ? 2% and 0.5% that of the Dijkstra's algorithm. PMID:25050952
An overview of constraint-based path selection algorithms for QoS routing
Fernando Kuipers; Piet Van Mieghem; T. Korkmaz; M. Krunz
2002-01-01
Constraint-based path selection aims at identifying a path that satisfies a set of quality of service (QoS) constraints. In general, this problem is known to be NP-complete, leading to the proposal of many heuristic algorithms. We provide an overview of these algorithms, focusing on restricted shortest path and multi-constrained path algorithms.
Discrete Approximation to Continuous Anisotropic Shortest-Path Problem
Hespanha, JoÃ£o Pedro
Probability that some UAV will be detected along path on time interval [0, T]: Probability of jth UAV being-Risk Path Planning for Groups of UAVs James Riehl JoÃ£o Hespanha INFORMS Meeting November 6, 2007 #12;start point ? Cost may depend on Â· duration of path Â· fuel consumed along path Â· probability of detection
Snell's law and light traveling along the shortest path
Carlos Lara
2006-01-01
the problem to be analyzed follows: Given a starting point s, an ending point t and a set of n Weighted Faces (or regions) in a 2-dimensional space, find the best path from s to t, where the length of the path is defined as the weighted sum of the Euclidean length of the sub paths inside each region. Let
NASA Astrophysics Data System (ADS)
Huang, Guo-Jiao; Bai, Chao-Ying; Greenhalgh, Stewart
2013-09-01
The traditional grid/cell-based wavefront expansion algorithms, such as the shortest path algorithm, can only find the first arrivals or multiply reflected (or mode converted) waves transmitted from subsurface interfaces, but cannot calculate the other later reflections/conversions having a minimax time path. In order to overcome the above limitations, we introduce the concept of a stationary minimax time path of Fermat's Principle into the multistage irregular shortest path method. Here we extend it from Cartesian coordinates for a flat earth model to global ray tracing of multiple phases in a 3-D complex spherical earth model. The ray tracing results for 49 different kinds of crustal, mantle and core phases show that the maximum absolute traveltime error is less than 0.12 s and the average absolute traveltime error is within 0.09 s when compared with the AK135 theoretical traveltime tables for a 1-D reference model. Numerical tests in terms of computational accuracy and CPU time consumption indicate that the new scheme is an accurate, efficient and a practical way to perform 3-D multiphase arrival tracking in regional or global traveltime tomography.
Geodesics and Shortest Paths Approach in Pedestrian Motions
Rascle, Michel
of optimal paths for visitors of French national parks [12] ... and for Rascle by previous works on mesh, no conservation of momentum etc ... The aim is simply to propose one optimization principle which might govern
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.
Distance formula and shortest paths for the (n, k)-star graphs
Eddie Cheng; Jerrold W. Grossman; László Lipták; Ke Qiu; Zhizhang Shen
2010-01-01
The class of (n,k)-star graphs is a generalization of the class of star graphs. Thus a distance formula for the first class implies one for the second. In this paper, we show that the converse is also true. Another important concept is the number of shortest paths between two vertices. This problem has been solved for the star graphs. We
SUBMITTED TO IEEE PAMI, 2008 1 Watershed cuts: thinnings, shortest-path forests and
Paris-Sud XI, UniversitÃ© de
and diffusion tensor images. Index Terms-- Watershed, thinning, minimum spanning forest, shortest-path forest. The digital image is seen as a topographic surface: the gray level becomes the elevation, the basins and valleys of the topographic surface correspond to dark areas, whereas the mountains and crest lines
Transitive Functional Annotation by Shortest-path Analysis of Gene Expression Data
Xianghong Zhou; Ming-Chih J. Kao; Wing Hung Wong
2002-01-01
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
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
Shortest Path Stochastic Control for Hybrid Electric Vehicles , J.W. Grizzle2
Grizzle, Jessy W.
1 of 28 Shortest Path Stochastic Control for Hybrid Electric Vehicles Ed Tate1 , J.W. Grizzle2 , Huei Peng3 Abstract: When a Hybrid Electric Vehicle (HEV) is certified for emissions and fuel economy this is the Hybrid Electric Vehicle (HEV) which consists of an electric powertrain coupled to a conventional
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
, Germany 2Center for Infrastructure, Sustainable Transportation and Urban Planning, Indian InstituteEnhanced Shortest Path Computation for Multiagent-based Intermodal Transport Planning in Dynamic,humi,herzog}@tzi.de,sitharam@civil.iisc.ernet.in Keywords: Multiagent-based Simulation Abstract: This paper addresses improved urban mobility using
NASA Astrophysics Data System (ADS)
Kröger, Martin
2005-06-01
We present an algorithm which returns a shortest path and related number of entanglements for a given configuration of a polymeric system in 2 or 3 dimensions. Rubinstein and Helfand, and later Everaers et al. introduced a concept to extract primitive paths for dense polymeric melts made of linear chains (a multiple disconnected multibead 'path'), where each primitive path is defined as a path connecting the (space-fixed) ends of a polymer under the constraint of non-interpenetration (excluded volume) between primitive paths of different chains, such that the multiple disconnected path fulfills a minimization criterion. The present algorithm uses geometrical operations and provides a—model independent—efficient approximate solution to this challenging problem. Primitive paths are treated as 'infinitely' thin (we further allow for finite thickness to model excluded volume), and tensionless lines rather than multibead chains, excluded volume is taken into account without a force law. The present implementation allows to construct a shortest multiple disconnected path (SP) for 2D systems (polymeric chain within spherical obstacles) and an optimal SP for 3D systems (collection of polymeric chains). The number of entanglements is then simply obtained from the SP as either the number of interior kinks, or from the average length of a line segment. Further, information about structure and potentially also the dynamics of entanglements is immediately available from the SP. We apply the method to study the 'concentration' dependence of the degree of entanglement in phantom chain systems. Program summaryTitle of program:Z Catalogue number:ADVG Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADVG Program obtainable from: CPC Program Library, Queen's University of Belfast, N. Ireland Computer for which the program is designed and others on which it has been tested: Silicon Graphics (Irix), Sun (Solaris), PC (Linux) Operating systems or monitors under which the program has been tested: UNIX, Linux Program language used: USANSI Fortran 77 and Fortran 90 Memory required to execute with typical data: 1 MByte No. of lines in distributed program, including test data, etc.: 10 660 No. of bytes in distributed program, including test data, etc.: 119 551 Distribution formet:tar.gz Nature of physical problem: The problem is to obtain primitive paths substantiating a shortest multiple disconnected path (SP) for a given polymer configuration (chains of particles, with or without additional single particles as obstacles for the 2D case). Primitive paths are here defined as in [M. Rubinstein, E. Helfand, J. Chem. Phys. 82 (1985) 2477; R. Everaers, S.K. Sukumaran, G.S. Grest, C. Svaneborg, A. Sivasubramanian, K. Kremer, Science 303 (2004) 823] as the shortest line (path) respecting 'topological' constraints (from neighboring polymers or point obstacles) between ends of polymers. There is a unique solution for the 2D case. For the 3D case it is unique if we construct a primitive path of a single chain embedded within fixed line obstacles [J.S.B. Mitchell, Geometric shortest paths and network optimization, in: J.-R. Sack, J. Urrutia (Eds.), Handbook of Computational Geometry, Elsevier, Amsterdam, 2000, pp. 633-701]. For a large 3D configuration made of several chains, short is meant to be the Euclidean shortest multiple disconnected path (SP) where primitive paths are constructed for all chains simultaneously. While the latter problem, in general, does not possess a unique solution, the algorithm must return a locally optimal solution, robust against minor displacements of the disconnected path and chain re-labeling. The problem is solved if the number of kinks (or entanglements Z), explicitly deduced from the SP, is quite insensitive to the exact conformation of the SP which allows to estimate Z with a small error. Efficient method of solution: Primitive paths are constructed from the given polymer configuration (a non-shortest multiple disconnected path, including obstacles, if present) by first replacing each polymer contour by a line wi
Solution Methods for the Multi-trip Elementary Shortest Path ...
2011-03-15
Constraints (3) require that the vehicle should enter and leave a customer ..... Instead of searching a node in an ordered list of nodes from 1 to |I|+2, we choose the ..... Algorithm 2P-CS with U = 12 outperforms the other variants in terms of the.
Geometric Containers for Efficient Shortest-Path Computation
Zaroliagis, Christos D.
Theory]: Graph algorithms, Network prob- lems; G.2.3 [Applications]: Traffic information systems; F.2 efficiently best routes or optimal itineraries in traffic infor- mation systems is to reduce the search space structures, created during a preprocess- ing phase, of size linear (i.e., optimal) to the size of the graph
k-Link Rectilinear Shortest Paths Among Rectilinear Obstacles in the Plane Valentin Polishchuk
]. More efficient algorithms, running in nearly linear time, are known for optimal paths in a "combined]. In rectilinear polygonal domains, efficient algorithms are known for the bi-criteria path problem that com- bines], which has been applied successfully to solving many optimal path problems in geometry. Since our new
Scaling of average receiving time and average weighted shortest path on weighted Koch networks
NASA Astrophysics Data System (ADS)
Dai, Meifeng; Chen, Dandan; Dong, Yujuan; Liu, Jie
2012-12-01
In this paper we present weighted Koch networks based on classic Koch networks. A new method is used to determine the average receiving time (ART), whose key step is to write the sum of mean first-passage times (MFPTs) for all nodes to absorption at the trap located at a hub node as a recursive relation. We show that the ART exhibits a sublinear or linear dependence on network order. Thus, the weighted Koch networks are more efficient than classic Koch networks in receiving information. Moreover, average weighted shortest path (AWSP) is calculated. In the infinite network order limit, the AWSP depends on the scaling factor. The weighted Koch network grows unbounded but with the logarithm of the network size, while the weighted shortest paths stay bounded.
Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation
Wu, Lingkun; Deng, Dingxiong; Cong, Gao; Zhu, Andy Diwen; Zhou, Shuigeng
2012-01-01
Computing the shortest path between two given locations in a road network is an important problem that finds applications in various map services and commercial navigation products. The state-of-the-art solutions for the problem can be divided into two categories: spatial-coherence-based methods and vertex-importance-based approaches. The two categories of techniques, however, have not been compared systematically under the same experimental framework, as they were developed from two independent lines of research that do not refer to each other. This renders it difficult for a practitioner to decide which technique should be adopted for a specific application. Furthermore, the experimental evaluation of the existing techniques, as presented in previous work, falls short in several aspects. Some methods were tested only on small road networks with up to one hundred thousand vertices; some approaches were evaluated using distance queries (instead of shortest path queries), namely, queries that ask only for the ...
Modeling the average shortest-path length in growth of word-adjacency networks
NASA Astrophysics Data System (ADS)
Kulig, Andrzej; Dro?d?, Stanis?aw; Kwapie?, Jaros?aw; O?wiÈ©cimka, Pawe?
2015-03-01
We investigate properties of evolving linguistic networks defined by the word-adjacency relation. Such networks belong to the category of networks with accelerated growth but their shortest-path length appears to reveal the network size dependence of different functional form than the ones known so far. We thus compare the networks created from literary texts with their artificial substitutes based on different variants of the Dorogovtsev-Mendes model and observe that none of them is able to properly simulate the novel asymptotics of the shortest-path length. Then, we identify the local chainlike linear growth induced by grammar and style as a missing element in this model and extend it by incorporating such effects. It is in this way that a satisfactory agreement with the empirical result is obtained.
A motion planning algorithm for smooth paths of bounded curvature and curvature derivative
G. Parlangeli; L. Ostuni; L. Mancarella; G. Indiveri
2009-01-01
This paper proposes an algorithm for planning Cinfin paths with bound curvature and curvature derivative linking two fixed (initial and final) configurations and passing through a given number of intermediate via-points. The proposed solution is derived solving an optimization problem such that a smooth curve of bounded curvature and curvature derivative approximates Dubin's shortest paths. The effectiveness of such strategy
Challenging of path planning algorithms for autonomous robot in known environment
NASA Astrophysics Data System (ADS)
Farah, R. N.; Irwan, N.; Zuraida, Raja Lailatul; Shaharum, Umairah; Hanafi@Omar, Hafiz Mohd
2014-06-01
Most of the mobile robot path planning is estimated to reach its predetermined aim through the shortest path and avoiding the obstacles. This paper is a survey on path planning algorithms of various current research and existing system of Unmanned Ground Vehicles (UGV) where their challenging issues to be intelligent autonomous robot. The focuses are some short reviews on individual papers for UGV in the known environment. Methods and algorithms in path planning for the autonomous robot had been discussed. From the reviews, we obtained that the algorithms proposed are appropriate for some cases such as single or multiple obstacles, static or movement obstacle and optimal shortest path. This paper also describes some pros and cons for every reviewed paper toward algorithms improvement for further work.
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
Vasco N. G. J. Soares; Joel J. P. C. Rodrigues; Farid Farahmand
Vehicular Delay-Tolerant Network (VDTN) appears as a particular application of the Delay-Tolerant Network (DTN) concept to transit networks. In this paper we analyze the use of a VDTN to provide asynchronous Internet access on a rural remote region scenario. Through simulation we evaluate the impact of a shortest path based movement model on the performance of four DTN routing protocols
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
NASA Astrophysics Data System (ADS)
Wu, Zikai; Hou, Baoyu; Zhang, Hongjuan; Jin, Feng
2014-04-01
Deterministic network models have been attractive media for discussing dynamical processes' dependence on network structural features. On the other hand, the heterogeneity of weights affect dynamical processes taking place on networks. In this paper, we present a family of weighted expanded Koch networks based on Koch networks. They originate from a r-polygon, and each node of current generation produces m r-polygons including the node and whose weighted edges are scaled by factor w in subsequent evolutionary step. We derive closed-form expressions for average weighted shortest path length (AWSP). In large network, AWSP stays bounded with network order growing (0 < w < 1). Then, we focus on a special random walks and trapping issue on the networks. In more detail, we calculate exactly the average receiving time (ART). ART exhibits a sub-linear dependence on network order (0 < w < 1), which implies that nontrivial weighted expanded Koch networks are more efficient than un-weighted expanded Koch networks in receiving information. Besides, efficiency of receiving information at hub nodes is also dependent on parameters m and r. These findings may pave the way for controlling information transportation on general weighted networks.
Analyzing the applicability of the least risk path algorithm in indoor space
NASA Astrophysics Data System (ADS)
Vanclooster, A.; Viaene, P.; Van de Weghe, N.; Fack, V.; De Maeyer, Ph.
2013-11-01
Over the last couple of years, applications that support navigation and wayfinding in indoor environments have become one of the booming industries. However, the algorithmic support for indoor navigation has so far been left mostly untouched, as most applications mainly rely on adapting Dijkstra's shortest path algorithm to an indoor network. In outdoor space, several alternative algorithms have been proposed adding a more cognitive notion to the calculated paths and as such adhering to the natural wayfinding behavior (e.g. simplest paths, least risk paths). 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…). 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-story building. Several analyses compare shortest and least risk paths in indoor and in outdoor space. The results of these analyses indicate that the current outdoor least risk path algorithm does not calculate less risky paths compared to its shortest paths. In some cases, worse routes have been suggested. Adjustments to the original algorithm are proposed to be more aligned to the specific structure of indoor environments. 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.
Interior point path following algorithms
Gonzaga, C.C.
1994-12-31
In the last few years the research on interior point methods for linear programming has been dominated by the study of primal-dual algorithms. Most of these methods are easily extended to monotone linear complementarity problems, preserving the convergence properties. In this talk we concentrate mostly on the basic techniques used for following the primal-dual central path associated with a monotone horizontal LCP. The emphasis is on feasible interior point methods, but we also describe the main techniques for dealing with infeasible starting points. We define the central path and construct homotopy methods for following it, with iterations based on the application of Newton`s method. We show how these Newton steps are combinations of two special directions, the affine-scaling and the centering direction, and describe how this fact can be used to generate large step methods with low polynomial bounds and superlinear rates of convergence.
Ant Colony Algorithm for Multiple-Depot Vehicle Routing Problem with Shortest Finish Time
NASA Astrophysics Data System (ADS)
Ma, Jianhua; Yuan, Jie
The objective of the multiple-depot vehicle routing problem (MDVRP) is to shorten the finish time, in the emergency management and special delivery research. In this paper, an ant colony algorithm for multiple-depot vehicle routing problem with shortest finish time (FTMDVRP) is studied. We discuss the concept and framework of FTMDVRP. The methods of making use of improved split algorithm to divide cars for given customer sequence is presented. We use the max flow algorithm allocate cars to each depot. Our experimental results confirm that our approach is effective in multiple-depot vehicle routing.
Design of Elevator Group Control System Simulation Platform Based on Shortest Distance Algorithm
Wang Chuansheng; Chen Chunping
2010-01-01
From the perspective of the characteristics of the elevator group control system, this paper selects the shortest distance algorithm as a scheduling strategy, and constructs elevator running model. On this basis, this paper uses VC++6.0 as development platform, by adding SQL server database as the background, using multi-threaded, dynamic allocation of memory and other technology to build an elevator group
Zhu, Xiaoyan
2007-04-25
RCSP into an unconstrained shortest path problem (SPP) and then solves the resulting SPP after new values of dual variables are used to update objective function coefficients (i.e., reduced costs) at each iteration. Network reduction techniques...
Efficient Processing of Which-Edge Questions on Shortest Path Queries
Zhu, Kenny Q.
path queries on a graph. This problem has important applications in logistics, urban planning, and net path queries have a wide range of applications in logistics, urban planning, and network planning domains, too. In urban planning where the road network is modeled as a graph, one may ask "(Q3): which
Liu, Lei; Cai, Yu-Dong; Chou, Kuo-Chen
2012-01-01
One of the most important and challenging problems in biomedicine and genomics is how to identify the disease genes. In this study, we developed a computational method to identify colorectal cancer-related genes based on (i) the gene expression profiles, and (ii) the shortest path analysis of functional protein association networks. The former has been used to select differentially expressed genes as disease genes for quite a long time, while the latter has been widely used to study the mechanism of diseases. With the existing protein-protein interaction data from STRING (Search Tool for the Retrieval of Interacting Genes), a weighted functional protein association network was constructed. By means of the mRMR (Maximum Relevance Minimum Redundancy) approach, six genes were identified that can distinguish the colorectal tumors and normal adjacent colonic tissues from their gene expression profiles. Meanwhile, according to the shortest path approach, we further found an additional 35 genes, of which some have been reported to be relevant to colorectal cancer and some are very likely to be relevant to it. Interestingly, the genes we identified from both the gene expression profiles and the functional protein association network have more cancer genes than the genes identified from the gene expression profiles alone. Besides, these genes also had greater functional similarity with the reported colorectal cancer genes than the genes identified from the gene expression profiles alone. All these indicate that our method as presented in this paper is quite promising. The method may become a useful tool, or at least plays a complementary role to the existing method, for identifying colorectal cancer genes. It has not escaped our notice that the method can be applied to identify the genes of other diseases as well. PMID:22496748
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.
Path planning for autonomous UAV via vibrational genetic algorithm
Y. Volkan Pehlivanoglu; Oktay Baysal; Abdurrahman Hacioglu
2007-01-01
Purpose – It is aimed to provide an efficient algorithm for path planning in guidance of autonomous unmanned aerial vehicle (UAV) through 3D terrain environments. Design\\/methodology\\/approach – As a stochastic search method, vibrational genetic algorithm (VGA) is improved and used to accelerate the algorithm for path planning. Findings – Using VGA, an efficient path planning algorithm for autonomous UAV was
A Path Algorithm for Constrained Estimation
Zhou, Hua; Lange, Kenneth
2013-01-01
Many least-square problems involve affine equality and inequality constraints. Although there are a variety of methods for solving such problems, most statisticians find constrained estimation challenging. The current article proposes a new path-following algorithm for quadratic programming that replaces hard constraints by what are called exact penalties. Similar penalties arise in l1 regularization in model selection. In the regularization setting, penalties encapsulate prior knowledge, and penalized parameter estimates represent a trade-off between the observed data and the prior knowledge. Classical penalty methods of optimization, such as the quadratic penalty method, solve a sequence of unconstrained problems that put greater and greater stress on meeting the constraints. In the limit as the penalty constant tends to ?, one recovers the constrained solution. In the exact penalty method, squared penalties!are replaced by absolute value penalties, and the solution is recovered for a finite value of the penalty constant. The exact path-following method starts at the unconstrained solution and follows the solution path as the penalty constant increases. In the process, the solution path hits, slides along, and exits from the various constraints. Path following in Lasso penalized regression, in contrast, starts with a large value of the penalty constant and works its way downward. In both settings, inspection of the entire solution path is revealing. Just as with the Lasso and generalized Lasso, it is possible to plot the effective degrees of freedom along the solution path. For a strictly convex quadratic program, the exact penalty algorithm can be framed entirely in terms of the sweep operator of regression analysis. A few well-chosen examples illustrate the mechanics and potential of path following. This article has supplementary materials available online. PMID:24039382
Adaptive path planning: Algorithm and analysis
Chen, Pang C.
1995-03-01
To address the need for a fast path planner, we present a learning algorithm that improves path planning by using past experience to enhance future performance. The algorithm relies on an existing path planner to provide solutions difficult tasks. From these solutions, an evolving sparse work of useful robot configurations is learned to support faster planning. More generally, the algorithm provides a framework in which a slow but effective planner may be improved both cost-wise and capability-wise by a faster but less effective planner coupled with experience. We analyze algorithm by formalizing the concept of improvability and deriving conditions under which a planner can be improved within the framework. The analysis is based on two stochastic models, one pessimistic (on task complexity), the other randomized (on experience utility). Using these models, we derive quantitative bounds to predict the learning behavior. We use these estimation tools to characterize the situations in which the algorithm is useful and to provide bounds on the training time. In particular, we show how to predict the maximum achievable speedup. Additionally, our analysis techniques are elementary and should be useful for studying other types of probabilistic learning as well.
Adaptive path planning: Algorithm and analysis
Chen, Pang C.
1993-03-01
Path planning has to be fast to support real-time robot programming. Unfortunately, current planning techniques are still too slow to be effective, as they often require several minutes, if not hours of computation. To alleviate this problem, we present a learning algorithm that uses past experience to enhance future performance. The algorithm relies on an existing path planner to provide solutions to difficult tasks. From these solutions, an evolving sparse network of useful subgoals is learned to support faster planning. The algorithm is suitable for both stationary and incrementally-changing environments. To analyze our algorithm, we use a previously developed stochastic model that quantifies experience utility. Using this model, we characterize the situations in which the adaptive planner is useful, and provide quantitative bounds to predict its behavior. The results are demonstrated with problems in manipulator planning. Our algorithm and analysis are sufficiently general that they may also be applied to task planning or other planning domains in which experience is useful.
An Analytical Continuous-Curvature Path-Smoothing Algorithm
Kwangjin Yang; Salah Sukkarieh
2010-01-01
An efficient and analytical continuous-curvature path-smoothing algorithm, which fits an ordered sequence of waypoints generated by an obstacle-avoidance path planner, is proposed. The algorithm is based upon parametric cubic Be?zier curves; thus, it is inherently closed-form in its expression, and the algorithm only requires the maximum curvature to be defined. The algorithm is, thus, computational efficient and easy to implement.
Opportunities to parallelize path planning algorithms for autonomous underwater vehicles
Mike Eichhorn; Ulrich Kremer
2011-01-01
This paper discusses opportunities to parallelize graph based path planning algorithms in a time varying environment. Parallel architectures have become commonplace, requiring algorithm to be parallelized for efficient execution. An additional focal point of this paper is the inclusion of inaccuracies in path planning as a result of forecast error variance, accuracy of calculation in the cost functions and a
Exact Algorithms for the Canadian Traveller Problem on Paths and Trees
Karger, David
2008-01-28
The Canadian Traveller problem is a stochastic shortest paths problem in which one learns the cost of an edge only when arriving at one of its endpoints. The goal is to find an adaptive policy (adjusting as one learns more ...
On Shortest Random Walks under Adversarial Uncertainty
Vladimir Marbukh
Finding shortest feasible paths in a weighted graph has numerous applications including admission and routing in communication networks. This paper discusses a game theoretic framework intended to incorporate a concept of path stability into the process of shortest path selection. Route stability is an important issue in a wire-line and especially in wireless network due to node mobility as well
PCB Drill Path Optimization by Combinatorial Cuckoo Search Algorithm
Lim, Wei Chen Esmonde; Kanagaraj, G.; Ponnambalam, S. G.
2014-01-01
Optimization of drill path can lead to significant reduction in machining time which directly improves productivity of manufacturing systems. In a batch production of a large number of items to be drilled such as printed circuit boards (PCB), the travel time of the drilling device is a significant portion of the overall manufacturing process. To increase PCB manufacturing productivity and to reduce production costs, a good option is to minimize the drill path route using an optimization algorithm. This paper reports a combinatorial cuckoo search algorithm for solving drill path optimization problem. The performance of the proposed algorithm is tested and verified with three case studies from the literature. The computational experience conducted in this research indicates that the proposed algorithm is capable of efficiently finding the optimal path for PCB holes drilling process. PMID:24707198
SPECIAL ISSUE PAPER Efficient camera path planning algorithm for human
Chen, Sheng-Wei
SPECIAL ISSUE PAPER Efficient camera path planning algorithm for human motion overview I-Cheng Yeh1., Tainan, Taiwan ABSTRACT Camera path planning for character motions is a fundamental and important computationally expensive and infeasible for interactive applications. In this paper, we propose an efficient
Numer. Math. 44, 111-126 (1984) Applications of Shortest Path Algorithms
Schneider, Hans
several points of view. At one extreme some papers concentrate on theoretical characterizations, e.g. [12J of us in [10, 11J and is there applied in the consideration of asymmetric scalings: A' = XA Y. In [11J a corresponding result on asym- metric scalings, see [19, Sect. 3]. The asymmetric formulation of some of our
Extracting contours of oval-shaped objects by Hough transform and minimal path algorithms
NASA Astrophysics Data System (ADS)
Tleis, Mohamed; Verbeek, Fons J.
2014-04-01
Circular and oval-like objects are very common in cell and micro biology. These objects need to be analyzed, and to that end, digitized images from the microscope are used so as to come to an automated analysis pipeline. It is essential to detect all the objects in an image as well as to extract the exact contour of each individual object. In this manner it becomes possible to perform measurements on these objects, i.e. shape and texture features. Our measurement objective is achieved by probing contour detection through dynamic programming. In this paper we describe a method that uses Hough transform and two minimal path algorithms to detect contours of (ovoid-like) objects. These algorithms are based on an existing grey-weighted distance transform and a new algorithm to extract the circular shortest path in an image. The methods are tested on an artificial dataset of a 1000 images, with an F1-score of 0.972. In a case study with yeast cells, contours from our methods were compared with another solution using Pratt's figure of merit. Results indicate that our methods were more precise based on a comparison with a ground-truth dataset. As far as yeast cells are concerned, the segmentation and measurement results enable, in future work, to retrieve information from different developmental stages of the cell using complex features.
Optimized Monte Carlo Path Generation using Genetic Algorithms
F. Suykens; Y. D. Willems
In this technical report we present a new method for optimizing the generation of paths in Monte Carlo global illumination rendering algorithms. Ray tracing, particle tracing, and bidirectional ray tracing all use random walks to estimate various fluxes in the scene. The probability density functions neces- sary to generate these random walks are optimized using a genetic algorithm, such that
Finding Smallest Paths in Rectilinear Polygons on a Hypercube Multiprocessor
Zhang, Richard "Hao"
Finding Smallest Paths in Rectilinear Polygons on a Hypercube Multiprocessor Afonso Ferreira techniques for designing geometric algorithms for the (sharedÂmemory) PRAM model of parallel computation (e that is simultaneously a shortest path with respect to the L 1 metric, and a straightest path (i.e., minimum link path
978-1-4244-7265-9/10/$26.00 c 2010 IEEE Conditional Shortest Path Routing in
Varela, Carlos
the conventional intermeeting time as the link metric. I. INTRODUCTION Routing in delay tolerant networks (DTN in DTN's. Therefore, the routing problem is still an active research area in DTN's [1]. Routing algorithms in DTN's utilize a paradigm called store-carry-and-forward. When a node receives a message from
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
Zhang, Ning; Jiang, Min; 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
Autonomous routing algorithms for networks with wide-spread failures
Modiano, Eytan H.
We study end-to-end delay performance of different routing algorithms in networks with random failures. Specifically, we compare delay performances of differential backlog (DB) and shortest path (SP) routing algorithms and ...
Algorithms for Constrained Route Planning in Road Networks
Rice, Michael Norris
2013-01-01
the ALT algorithm, the heuristic potential function servesalgorithm is based on the concepts of A ? [62] search, which uses a potential functionpotential function to estimate the shortest path cost to the target. The ALT algorithm
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.
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.
Path Planning Algorithms for Autonomous Border Patrol Vehicles
NASA Astrophysics Data System (ADS)
Lau, George Tin Lam
This thesis presents an online path planning algorithm developed for unmanned vehicles in charge of autonomous border patrol. In this Pursuit-Evasion game, the unmanned vehicle is required to capture multiple trespassers on its own before any of them reach a target safe house where they are safe from capture. The problem formulation is based on Isaacs' Target Guarding problem, but extended to the case of multiple evaders. The proposed path planning method is based on Rapidly-exploring random trees (RRT) and is capable of producing trajectories within several seconds to capture 2 or 3 evaders. Simulations are carried out to demonstrate that the resulting trajectories approach the optimal solution produced by a nonlinear programming-based numerical optimal control solver. Experiments are also conducted on unmanned ground vehicles to show the feasibility of implementing the proposed online path planning algorithm on physical applications.
A bat algorithm with mutation for UCAV path planning.
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
Path Planning Algorithms for the Adaptive Sensor Fleet
NASA Technical Reports Server (NTRS)
Stoneking, Eric; Hosler, Jeff
2005-01-01
The Adaptive Sensor Fleet (ASF) is a general purpose fleet management and planning system being developed by NASA in coordination with NOAA. The current mission of ASF is to provide the capability for autonomous cooperative survey and sampling of dynamic oceanographic phenomena such as current systems and algae blooms. Each ASF vessel is a software model that represents a real world platform that carries a variety of sensors. The OASIS platform will provide the first physical vessel, outfitted with the systems and payloads necessary to execute the oceanographic observations described in this paper. The ASF architecture is being designed for extensibility to accommodate heterogenous fleet elements, and is not limited to using the OASIS platform to acquire data. This paper describes the path planning algorithms developed for the acquisition phase of a typical ASF task. Given a polygonal target region to be surveyed, the region is subdivided according to the number of vessels in the fleet. The subdivision algorithm seeks a solution in which all subregions have equal area and minimum mean radius. Once the subregions are defined, a dynamic programming method is used to find a minimum-time path for each vessel from its initial position to its assigned region. This path plan includes the effects of water currents as well as avoidance of known obstacles. A fleet-level planning algorithm then shuffles the individual vessel assignments to find the overall solution which puts all vessels in their assigned regions in the minimum time. This shuffle algorithm may be described as a process of elimination on the sorted list of permutations of a cost matrix. All these path planning algorithms are facilitated by discretizing the region of interest onto a hexagonal tiling.
Analysis of the contact graph routing algorithm: Bounding interplanetary paths
NASA Astrophysics Data System (ADS)
Birrane, Edward; Burleigh, Scott; Kasch, Niels
2012-06-01
Interplanetary communication networks comprise orbiters, deep-space relays, and stations on planetary surfaces. These networks must overcome node mobility, constrained resources, and significant propagation delays. Opportunities for wireless contact rely on calculating transmit and receive opportunities, but the Euclidean-distance diameter of these networks (measured in light-seconds and light-minutes) precludes node discovery and contact negotiation. Propagation delay may be larger than the line-of-sight contact between nodes. For example, Mars and Earth orbiters may be separated by up to 20.8 min of signal propagation time. Such spacecraft may never share line-of-sight, but may uni-directionally communicate if one orbiter knows the other's future position. The Contact Graph Routing (CGR) approach is a family of algorithms presented to solve the messaging problem of interplanetary communications. These algorithms exploit networks where nodes exhibit deterministic mobility. For CGR, mobility and bandwidth information is pre-configured throughout the network allowing nodes to construct transmit opportunities. Once constructed, routing algorithms operate on this contact graph to build an efficient path through the network. The interpretation of the contact graph, and the construction of a bounded approximate path, is critically important for adoption in operational systems. Brute force approaches, while effective in small networks, are computationally expensive and will not scale. Methods of inferring cycles or other librations within the graph are difficult to detect and will guide the practical implementation of any routing algorithm. This paper presents a mathematical analysis of a multi-destination contact graph algorithm (MD-CGR), demonstrates that it is NP-complete, and proposes realistic constraints that make the problem solvable in polynomial time, as is the case with the originally proposed CGR algorithm. An analysis of path construction to complement hop-by-hop forwarding is presented as the CGR-EB algorithm. Future work is proposed to handle the presence of dynamic changes to the network, as produced by congestion, link disruption, and errors in the contact graph. We conclude that pre-computation, and thus CGR style algorithms, is the only efficient method of routing in a multi-node, multi-path interplanetary network and that algorithmic analysis is the key to its implementation in operational systems.
Path planning algorithms for assembly sequence planning. [in robot kinematics
NASA Technical Reports Server (NTRS)
Krishnan, S. S.; Sanderson, Arthur C.
1991-01-01
Planning for manipulation in complex environments often requires reasoning about the geometric and mechanical constraints which are posed by the task. In planning assembly operations, the automatic generation of operations sequences depends on the geometric feasibility of paths which permit parts to be joined into subassemblies. Feasible locations and collision-free paths must be present for part motions, robot and grasping motions, and fixtures. This paper describes an approach to reasoning about the feasibility of straight-line paths among three-dimensional polyhedral parts using an algebra of polyhedral cones. A second method recasts the feasibility conditions as constraints in a nonlinear optimization framework. Both algorithms have been implemented and results are presented.
On Models of Nonlinear Evolution Paths in Adiabatic Quantum Algorithms
NASA Astrophysics Data System (ADS)
Sun, Jie; Lu, Song-Feng; Samuel, L. Braunstein
2013-01-01
In this paper, we study two different nonlinear interpolating paths in adiabatic evolution algorithms for solving a particular class of quantum search problems where both the initial and final Hamiltonian are one-dimensional projector Hamiltonians on the corresponding ground state. If the overlap between the initial state and final state of the quantum system is not equal to zero, both of these models can provide a constant time speedup over the usual adiabatic algorithms by increasing some another corresponding “complexity". But when the initial state has a zero overlap with the solution state in the problem, the second model leads to an infinite time complexity of the algorithm for whatever interpolating functions being applied while the first one can still provide a constant running time. However, inspired by a related reference, a variant of the first model can be constructed which also fails for the problem when the overlap is exactly equal to zero if we want to make up the “intrinsic" fault of the second model — an increase in energy. Two concrete theorems are given to serve as explanations why neither of these two models can improve the usual adiabatic evolution algorithms for the phenomenon above. These just tell us what should be noted when using certain nonlinear evolution paths in adiabatic quantum algorithms for some special kind of problems.
Algorithm Plans Collision-Free Path for Robotic Manipulator
NASA Technical Reports Server (NTRS)
Backes, Paul; Diaz-Calderon, Antonio
2007-01-01
An algorithm has been developed to enable a computer aboard a robot to autonomously plan the path of the manipulator arm of the robot to avoid collisions between the arm and any obstacle, which could be another part of the robot or an external object in the vicinity of the robot. In simplified terms, the algorithm generates trial path segments and tests each segment for potential collisions in an iterative process that ends when a sequence of collision-free segments reaches from the starting point to the destination. The main advantage of this algorithm, relative to prior such algorithms, is computational efficiency: the algorithm is designed to make minimal demands upon the limited computational resources available aboard a robot. This path-planning algorithm utilizes a modified version of the collision-detection method described in "Improved Collision-Detection Method for Robotic Manipulator" (NPO-30356), NASA Tech Briefs, Vol. 27, No. 3 (June 2003), page 72. The method involves utilization of mathematical models of the robot constructed prior to operation and similar models of external objects constructed automatically from sensory data acquired during operation. This method incorporates a previously developed method, known in the art as the method of oriented bounding boxes (OBBs), in which an object is represented approximately, for computational purposes, by a box that encloses its outer boundary. Because many parts of a robotic manipulator are cylindrical, the OBB method has been extended in this method to enable the approximate representation of cylindrical parts by use of octagonal or other multiple-OBB assemblies denoted oriented bounding prisms (OBPs). A multiresolution OBB/OBP representation of the robot and its manipulator arm and a multiresolution OBB representation of external objects (including terrain) are constructed and used in a process in which collisions at successively finer resolutions are detected through computational detection of overlaps between the corresponding OBB and OBP models. For computational efficiency, the process is started at the coarsest resolution and stopped as soon as possible, preferably before reaching the finest resolution. At the coarsest resolution, there is a single OBB enclosing all relevant external objects and a single OBB enclosing the entire robot. At the next finer level of resolution, the coarsest-resolution OBB is divided into two OBBs, and so forth. If no collision is detected at the coarsest resolution, then there is no need for further computation to detect collisions. If a collision is detected at the coarsest resolution, then tests for collisions are performed at the next finer level of resolution. This process is continued to successively finer resolutions until either no more collisions are detected or the finest resolution is reached.
Microwave radiometer measurements at Liquid water path algorithm development and accuracy
Reading, University of
1 Microwave radiometer measurements at Chilbolton Liquid water path algorithm development the atmosphere 1.3Liquid water path retrieval 2. MICROWAVE RADIOMETERS. 2.1Radiometer description. 2.2 Radiometer calibration. 3. LIQUID WATER PATH RETRIEVAL ALGORITHM. 3.1 Relationship between radiometer output
Precise flight-path control using a predictive algorithm
NASA Technical Reports Server (NTRS)
Hess, R. A.; Jung, Y. C.
1991-01-01
Generalized predictive control describes an algorithm for the control of dynamic systems in which a control input is generated that minimizes a quadratic cost function consisting of a weighted sum of errors between desired and predicted future system output and future predicted control increments. The output predictions are obtained from an internal model of the plant dynamics. A design technique is discussed for applying the single-input/single-output generalized predictive control algorithm to a problem of longitudinal/vertical terrain-following flight of a rotorcraft. By using the generalized predictive control technique to provide inputs to a classically designed stability and control augmentation system, it is demonstrated that a robust flight-path control system can be created that exhibits excellent tracking performance.
An analysis of 3D particle path integration algorithms
Darmofal, D.L. [Texas A & M Univ., College Station, TX (United States)] [Texas A & M Univ., College Station, TX (United States); Haimes, R. [MIT, Cambridge, MA (United States)] [MIT, Cambridge, MA (United States)
1996-01-01
Several techniques for the numerical integration of particle paths in steady and unsteady vector (velocity) fields are analyzed. Most of the analysis applies to unsteady vector fields, however, some results apply to steady vector field integration. Multistep, multistage, and some hybrid schemes are considered. It is shown that due to initialization errors, many unsteady particle path integration schemes are limited to third-order accuracy in time. Multistage schemes require at least three times more internal data storage than multistep schemes of equal order. However, for timesteps within the stability bounds, multistage schemes are generally more accurate. A linearized analysis shows that the stability of these integration algorithms are determined by the eigenvalues of the local velocity tensor. Thus, the accuracy and stability of the methods are interpreted with concepts typically used in critical point theory. This paper shows how integration schemes can lead to erroneous classification of critical points when the timestep is finite and fixed. For steady velocity fields, we demonstrate that timesteps outside of the relative stability region can lead to similar integration errors. From this analysis, guidelines for accurate timestep sizing are suggested for both steady and unsteady flows. In particular, using simulation data for the unsteady flow around a tapered cylinder, we show that accurate particle path integration requires timesteps which are at most on the order of the physical timescale of the flow.
A Distributed Algorithm for Constructing a Minimum Diameter Spanning Tree
Paris-Sud XI, UniversitÃ© de
A Distributed Algorithm for Constructing a Minimum Diameter Spanning Tree Marc Bui a Franck Butelle|) message complexity. Keywords: Spanning trees; Minimum diameter spanning trees; Shortest paths; Shortest propagation over a spanning tree is naturally achieved by reducing the diameter to a minimum. The use
Path Design and Control Algorithms for Articulated Mobile Robots Ulf Andersson, Kent Mrozek
Lunds Universitet
Path Design and Control Algorithms for Articulated Mobile Robots Ulf Andersson, Kent Mrozek Q mobile robots. The X4Y4 curve and a control algorithm for an articulated mobile robot following an X4Y4 for real-world mobile robots. Ill-designed curves on a path can cause large guidance errors, and also
Zixing Cai; Zhihong Peng
2002-01-01
In this paper, path planning of cooperative multi-mobile robot systems, an example of multi-agent systems, is discussed with the proposal of a novel Cooperative Coevolutionary Adaptive Genetic Algorithm (CCAGA). At the same time, for such genetic algorithms based path planning, a novel fixed-length decimal encoding mechanism for paths of each mobile robot is also proposed. Such cooperative coevolutionary adaptive genetic
NASA Technical Reports Server (NTRS)
Izumi, K. H.; Thompson, J. L.; Groce, J. L.; Schwab, R. W.
1986-01-01
The design requirements for a 4D path definition algorithm are described. These requirements were developed for the NASA ATOPS as an extension of the Local Flow Management/Profile Descent algorithm. They specify the processing flow, functional and data architectures, and system input requirements, and recommended the addition of a broad path revision (reinitialization) function capability. The document also summarizes algorithm design enhancements and the implementation status of the algorithm on an in-house PDP-11/70 computer. Finally, the requirements for the pilot-computer interfaces, the lateral path processor, and guidance and steering function are described.
Musicant, Dave
programming. Project: Dialogue system to query a course registration database via voice commands. Combines recognition with software integration and database programming. Project: Web search engine. Combines ideas from database systems, artificial intelligence, and networking. Integrates theoretical ideas from graph
A path following algorithm for the graph matching problem.
Zaslavskiy, Mikhail; Bach, Francis; Vert, Jean-Philippe
2009-12-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. The concave relaxation has the same global minimum as the initial graph matching problem, but the search for its global minimum is also a hard combinatorial problem. We, therefore, construct an approximation of the concave problem solution by following a solution path of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting from the convex relaxation. This method allows to easily integrate the information on graph label similarities into the optimization problem, and therefore, perform labeled weighted graph matching. The algorithm is compared with some of the best performing graph matching methods on four data sets: simulated graphs, QAPLib, retina vessel images, and handwritten Chinese characters. In all cases, the results are competitive with the state of the art. PMID:19834143
A Generic Path Algorithm for Regularized Statistical Estimation
Zhou, Hua; Wu, Yichao
2014-01-01
Regularization is widely used in statistics and machine learning to prevent overfitting and gear solution towards prior information. In general, a regularized estimation problem minimizes the sum of a loss function and a penalty term. The penalty term is usually weighted by a tuning parameter and encourages certain constraints on the parameters to be estimated. Particular choices of constraints lead to the popular lasso, fused-lasso, and other generalized ?1 penalized regression methods. In this article we follow a recent idea by Wu (2011, 2012) and propose an exact path solver based on ordinary differential equations (EPSODE) that works for any convex loss function and can deal with generalized ?1 penalties as well as more complicated regularization such as inequality constraints encountered in shape-restricted regressions and nonparametric density estimation. Non-asymptotic error bounds for the equality regularized estimates are derived. In practice, the EPSODE can be coupled with AIC, BIC, Cp or cross-validation to select an optimal tuning parameter, or provides a convenient model space for performing model averaging or aggregation. Our applications to generalized ?1 regularized generalized linear models, shape-restricted regressions, Gaussian graphical models, and nonparametric density estimation showcase the potential of the EPSODE algorithm. PMID:25242834
Robust three-dimensional best-path phase-unwrapping algorithm that avoids singularity loops.
Abdul-Rahman, Hussein; Arevalillo-Herráez, Miguel; Gdeisat, Munther; Burton, David; Lalor, Michael; Lilley, Francis; Moore, Christopher; Sheltraw, Daniel; Qudeisat, Mohammed
2009-08-10
In this paper we propose a novel hybrid three-dimensional phase-unwrapping algorithm, which we refer to here as the three-dimensional best-path avoiding singularity loops (3DBPASL) algorithm. This algorithm combines the advantages and avoids the drawbacks of two well-known 3D phase-unwrapping algorithms, namely, the 3D phase-unwrapping noise-immune technique and the 3D phase-unwrapping best-path technique. The hybrid technique presented here is more robust than its predecessors since it not only follows a discrete unwrapping path depending on a 3D quality map, but it also avoids any singularity loops that may occur in the unwrapping path. Simulation and experimental results have shown that the proposed algorithm outperforms its parent techniques in terms of reliability and robustness. PMID:19668273
Y. Volkan Pehlivanoglu
A new optimization algorithm called multi-frequency vibrational genetic algorithm (mVGA) that can be used to solve the path planning problems of autonomous unmanned aerial vehicles (UAVs) is significantly improved. The algorithm emphasizes a new mutation application strategy and diversity variety such as the global random and the local random diversity. Clustering method and Voronoi diagram concepts are used within the
A relaxed primal-dual path-following algorithm for linear programming
Tsung-Min Hwang; Chih-Hung Lin; Wen-Wei Lin; Shu-Cherng Fang
1996-01-01
In this paper, we provide an easily satisfied relaxation condition for the primaldual interior path-following algorithm to solve linear programming problems. It is shown that the relaxed algorithm preserves the property of polynomial-time convergence. The computational results obtained by implementing two versions of the relaxed algorithm with slight modifications clearly demonstrate the potential in reducing computational efforts.
NSDL National Science Digital Library
Demaine, Erik D., 1981-
This course provides an introduction to algorithms. Topics include sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; caching; and parallel computing. Selected lecture notes, video and audio lectures, and assignments with solutions are included. MIT presents OpenCourseWare as free educational material online. No registration or enrollment is required to use the materials.
The Path-of-Probability Algorithm for Steering and Feedback Control of Flexible Needles
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
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 ...
An Algorithm for Measurement and Detection of Path Cheating in Virtual Environments
Ottawa, University of
with the traditional video and PC game industry, online games offer much more diversity in types of games, more for peer-to-peer online games. The algorithm finds the requested path through the active participation as the recalculation is performed by the controller. KeywordsÂMMOG; online games; cheating; path finding; peer
Traffic Grooming in Path, Star, and Tree Networks: Complexity, Bounds, and Algorithms
Dutta, Rudra
Traffic Grooming in Path, Star, and Tree Networks: Complexity, Bounds, and Algorithms Rudra Dutta of Computer Science, North Carolina State University, Raleigh, NC 1. INTRODUCTION In wavelength division consider the problem of traffic grooming in path, star, and tree networks, which are useful topologies
An Analysis of 3D Particle Path Integration Algorithms D.L. Darmofal
Peraire, Jaime
An Analysis of 3ÂD Particle Path Integration Algorithms D.L. Darmofal Research Fellow Aerospace paths in steady and unsteady vector (velocity) fields are analyzed. Most of the analysis applies to unsteady vector fields, however, some results apply to steady vector field integration. MultiÂstep, multi
Algorithms for Reliable Navigation and Wayfinding
NASA Astrophysics Data System (ADS)
Haque, Shazia; Kulik, Lars; Klippel, Alexander
Wayfinding research has inspired several algorithms that compute the shortest, fastest, or even simplest paths between two locations. Current navigation systems, however, do not take into account the navigational complexity of certain intersections. A short route might involve a number of intersections that are difficult to navigate, because they offer more than one alternative to turn left or right. The navigational complexity of such an intersection may require modified instructions such as veer right. This paper, therefore, presents a reliable path algorithm that minimizes the number of complex intersections with turn ambiguities between two locations along a route. Our algorithm computes the (shortest) most reliable path, i.e., the one with the least turn ambiguities. Furthermore, we develop a variation of this algorithm that balances travel distance and navigational complexity. Simulation results show that traversing a reliable path leads to less navigational errors, which in turn reduces the average travel distance. A further advantage is that reliable paths require simpler instructions.
ERIC Educational Resources Information Center
Boker, Steven M.; McArdle, J. J.; Neale, Michael
2002-01-01
Presents an algorithm for the production of a graphical diagram from a matrix formula in such a way that its components are logically and hierarchically arranged. The algorithm, which relies on the matrix equations of J. McArdle and R. McDonald (1984), calculates the individual path components of expected covariance between variables and…
Path planning using a hybrid evolutionary algorithm based on tree structure encoding.
Ju, Ming-Yi; Wang, Siao-En; Guo, Jian-Horn
2014-01-01
A hybrid evolutionary algorithm using scalable encoding method for path planning is proposed in this paper. The scalable representation is based on binary tree structure encoding. To solve the problem of hybrid genetic algorithm and particle swarm optimization, the "dummy node" is added into the binary trees to deal with the different lengths of representations. The experimental results show that the proposed hybrid method demonstrates using fewer turning points than traditional evolutionary algorithms to generate shorter collision-free paths for mobile robot navigation. PMID:24971389
Path Planning Using a Hybrid Evolutionary Algorithm Based on Tree Structure Encoding
Wang, Siao-En; Guo, Jian-Horn
2014-01-01
A hybrid evolutionary algorithm using scalable encoding method for path planning is proposed in this paper. The scalable representation is based on binary tree structure encoding. To solve the problem of hybrid genetic algorithm and particle swarm optimization, the “dummy node” is added into the binary trees to deal with the different lengths of representations. The experimental results show that the proposed hybrid method demonstrates using fewer turning points than traditional evolutionary algorithms to generate shorter collision-free paths for mobile robot navigation. PMID:24971389
An algorithm using length-r paths to approximate subgraph isomorphism
Fred W. Depiero; David K. Krout
2003-01-01
The 'LeRP' algorithm approximates subgraph isomorphism for attributed graphs based on counts of Length-R Paths. The algorithm provides a good approximation to the maximal isomorphic subgraph. The basic approach of the LeRP algorithm differs fundamentally from other methods. When comparing structural similarity LeRP uses a neighborhood of nodes that varies in size dynamically. This approach provides sufficient evidence of similarity
ECS 222B: Advanced Algorithms Spring Quarter2010 Lecture Notes April 20, 2010
California at Davis, University of
, shortest A-Path Algorithm Given a flow network G that also has arc costs w(i, j), we want to find a min the cheapest (shortest with respect to w(i, j) A-path in the residual graph and augmenting along it. In general, the residual graph will have negative arcs (either from negative w(i, j) values, or from back edges whose
NSDL National Science Digital Library
Richard Teviotdale, Tom Naps
Visualization of Floyd's all-pairs shortest paths algorithm. Includes dynamically highlighted pseudo code. Associated HTML page contains an algorithm description, pseudo code, and example trace, and discussion of efficiency analysis. The AV is set up as a series of 'slides' in one pane, and pseudocode in the adjacent pane. As the user steps through the 'slides', the associated pseudocode is highlighted. Occasional questions pop up for the user to answer. In addition to coloration for the graph as the algorithm progresses, there is a 2D array showing the algorithm's currently computed shortest distances. The explanation pages are a pretty good supplement to the AV (and vice versa). Students might still have a little bit of difficulty understanding the concept of the 'k paths', and there is no reference to dynamic programming, which would be helpful. Recommended as lecture aide, standalone, self-study suppliment to tutorial or lecture.
NASA Astrophysics Data System (ADS)
Ringle, Christian M.; Sarstedt, Marko; Schlittgen, Rainer
When applying structural equation modeling methods, such as partial least squares (PLS) path modeling, in empirical studies, the assumption that the data have been collected from a single homogeneous population is often unrealistic. Unobserved heterogeneity in the PLS estimates on the aggregate data level may result in misleading interpretations. Finite mixture partial least squares (FIMIX-PLS) and PLS genetic algorithm segmentation (PLS-GAS) allow the classification of data in variance-based structural equation modeling. This research presents an initial application and comparison of these two methods in a computational experiment in respect of a path model which includes multiple endogenous latent variables. The results of this analysis reveal particular advantages and disadvantages of the approaches. This study further substantiates the effectiveness of FIMIX-PLS and PLS-GAS and provides researchers and practitioners with additional information they need to proficiently evaluate their PLS path modeling results by applying a systematic means of analysis. If significant heterogeneity were to be uncovered by the procedures, the analysis may result in group-specific path modeling outcomes, thus allowing further differentiated and more precise conclusions to be formed.
Overview of Constraint-Based Path Selection Algorithms for QoS Routing
Kuipers, Fernando A.
Overview of Constraint-Based Path Selection Algorithms for QoS Routing F.A. Kuipers, Delft at identifying a path that satisÞes a set of quality-of- service (QoS) constraints. In general, this problem-service (QoS) based networking frameworks (e.g., IntServ, DiffServ, MPLS). One of the key issues in all
Genetic Algorithm-Based Test Data Generation for Multiple Paths via Individual Sharing
Gong, Dunwei
2014-01-01
The application of genetic algorithms in automatically generating test data has aroused broad concerns and obtained delightful achievements in recent years. However, the efficiency of genetic algorithm-based test data generation for path testing needs to be further improved. In this paper, we establish a mathematical model of generating test data for multiple paths coverage. Then, a multipopulation genetic algorithm with individual sharing is presented to solve the established model. We not only analyzed the performance of the proposed method theoretically, but also applied it to various programs under test. The experimental results show that the proposed method can improve the efficiency of generating test data for many paths' coverage significantly. PMID:25691894
Jiun-Hau Wei; Jing-Sin Liu
2010-01-01
As a continuing work on G3-continuous path planning for nonholonomic wheeled unicycle-type nonholo-nomic mobile robot in the predefined static environment, this paper accounts for a multi-objective path optimization problem that directly incorporates the objectives of simultaneously minimizes the total path length and the maximum curvature along the path. Using easily customized variable-length Island-based Parallel Genetic Algorithm (IPGA) as a path
A hybrid metaheuristic DE/CS algorithm for UCAV three-dimension path planning.
Wang, Gaige; Guo, Lihong; Duan, Hong; Wang, Heqi; Liu, Luo; Shao, Mingzhen
2012-01-01
Three-dimension path planning for uninhabited combat air vehicle (UCAV) is a complicated high-dimension optimization problem, which primarily centralizes on optimizing the flight route considering the different kinds of constrains under complicated battle field environments. A new hybrid metaheuristic differential evolution (DE) and cuckoo search (CS) algorithm is proposed to solve the UCAV three-dimension path planning problem. DE is applied to optimize the process of selecting cuckoos of the improved CS model during the process of cuckoo updating in nest. The cuckoos can act as an agent in searching the optimal UCAV path. And then, the UCAV can find the safe path by connecting the chosen nodes of the coordinates while avoiding the threat areas and costing minimum fuel. This new approach can accelerate the global convergence speed while preserving the strong robustness of the basic CS. The realization procedure for this hybrid metaheuristic approach DE/CS is also presented. In order to make the optimized UCAV path more feasible, the B-Spline curve is adopted for smoothing the path. To prove the performance of this proposed hybrid metaheuristic method, it is compared with basic CS algorithm. The experiment shows that the proposed approach is more effective and feasible in UCAV three-dimension path planning than the basic CS model. PMID:23193383
A Hybrid Metaheuristic DE/CS Algorithm for UCAV Three-Dimension Path Planning
Wang, Gaige; Guo, Lihong; Duan, Hong; Wang, Heqi; Liu, Luo; Shao, Mingzhen
2012-01-01
Three-dimension path planning for uninhabited combat air vehicle (UCAV) is a complicated high-dimension optimization problem, which primarily centralizes on optimizing the flight route considering the different kinds of constrains under complicated battle field environments. A new hybrid metaheuristic differential evolution (DE) and cuckoo search (CS) algorithm is proposed to solve the UCAV three-dimension path planning problem. DE is applied to optimize the process of selecting cuckoos of the improved CS model during the process of cuckoo updating in nest. The cuckoos can act as an agent in searching the optimal UCAV path. And then, the UCAV can find the safe path by connecting the chosen nodes of the coordinates while avoiding the threat areas and costing minimum fuel. This new approach can accelerate the global convergence speed while preserving the strong robustness of the basic CS. The realization procedure for this hybrid metaheuristic approach DE/CS is also presented. In order to make the optimized UCAV path more feasible, the B-Spline curve is adopted for smoothing the path. To prove the performance of this proposed hybrid metaheuristic method, it is compared with basic CS algorithm. The experiment shows that the proposed approach is more effective and feasible in UCAV three-dimension path planning than the basic CS model. PMID:23193383
A New Path-Following Algorithm for Nonlinear P? Complementarity ...
2005-06-16
was later generalized to monotone NCPs by Andersen and Ye [2]. ... However, it remains to be seen whether their model can be applied to P? or ...... It is also of interest to see how the behavior of the algorithm changes as ? varies. To ensure
Formal language constrained path problems
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.
Scalable shortest paths browsing on land surface
Songhua Xing; Cyrus Shahabi
2010-01-01
The growing popularity of online Earth visualization tools and geo-realistic games and the availability of high resolution terrain data have motivated a new class of queries to the interests of the GIS and spatial database community: spatial queries (e.g., kNN) over land surface. However, the fundamental challenges that restrict the applicability of these studies to real world applications are the
Optimal Distributed All Pairs Shortest Paths
nodes Diameter of this network? #12;Â· Spanning Tree Â Broadcasting, Aggregation, etc Â· Minimum Spanning #12;Â· Spanning Tree Â Broadcasting, Aggregation, etc Â· Minimum Spanning Tree Â Efficient broadcasting;Â· Spanning Tree Â Broadcasting, Aggregation, etc Â· Minimum Spanning Tree Â Efficient broadcasting, etc
Querying Approximate Shortest Paths in Anisotropic Regions
Vigneron, Antoine
face of this subdivision are measured by a possibly asymmetric convex distance function whose unit disk is contained in a concentric unit Euclidean disk, and contains a concentric Euclidean disk with radius 1 in the faces of the subdivision are measured using possibly asymmetric convex distance functions. This model
Querying Approximate Shortest Paths in Anisotropic Regions
Cheng, Siu-Wing
of this subdivision are measured by a possibly asymmetric convex distance function whose unit disk is contained in a concentric unit Euclidean disk, and contains a concentric Euclidean disk with radius 1/. Different convex using possibly asymmetric convex distance functions. This model covers the Euclidean case and other non
An LP decoding algorithm based on primal path-following interior point method
Tadashi Wadayama
2009-01-01
The paper presents an implementation of LP decoding algorithm based on the primal path-following interior point method. Numerical examples show some behaviors of an LP decoder based on the exact interior point method. It is shown that very accurate solution can be obtained after 40-50 iterations of the outer loop of the interior point method. Complexity analysis on the proposed
Evolutionary algorithm based offline/online path planner for UAV navigation.
Nikolos, I K; Valavanis, K P; Tsourveloudis, N C; Kostaras, A N
2003-01-01
An evolutionary algorithm based framework, a combination of modified breeder genetic algorithms incorporating characteristics of classic genetic algorithms, is utilized to design an offline/online path planner for unmanned aerial vehicles (UAVs) autonomous navigation. The path planner calculates a curved path line with desired characteristics in a three-dimensional (3-D) rough terrain environment, represented using B-spline curves, with the coordinates of its control points being the evolutionary algorithm artificial chromosome genes. Given a 3-D rough environment and assuming flight envelope restrictions, two problems are solved: i) UAV navigation using an offline planner in a known environment, and, ii) UAV navigation using an online planner in a completely unknown environment. The offline planner produces a single B-Spline curve that connects the starting and target points with a predefined initial direction. The online planner, based on the offline one, is given on-board radar readings which gradually produces a smooth 3-D trajectory aiming at reaching a predetermined target in an unknown environment; the produced trajectory consists of smaller B-spline curves smoothly connected with each other. Both planners have been tested under different scenarios, and they have been proven effective in guiding an UAV to its final destination, providing near-optimal curved paths quickly and efficiently. PMID:18238242
NASA Astrophysics Data System (ADS)
Popat, Kris; Greene, Daniel H.; Romberg, Justin K.; Bloomberg, Dan S.
2000-12-01
Beginning with an observed document image and a model of how the image has been degraded, Document Image Decoding recognizes printed text by attempting to find a most probable path through a hypothesized Markov source. The incorporation of linguistic constraints, which are expressed by a sequential predictive probabilistic language model, can improve recognition accuracy significantly in the case of moderately to severely corrupted documents. Two methods of incorporating linguistic constraints in the best-path search are described, analyzed and compared. The first, called the iterated complete path algorithm, involves iteratively rescoring complete paths using conditional language model probability distributions of increasing order, expanding state only as necessary with each iteration. A property of this approach is that it results in a solution that is exactly optimal with respect to the specified source, degradation, and language models; no approximation is necessary. The second approach considered is the Stack algorithm, which is often used in speech recognition and in the decoding of convolutional codes. Experimental results are presented in which text line images that have been corrupted in a known way are recognized using both the ICP and Stack algorithms. This controlled experimental setting preserves many of the essential features and challenges of real text line decoding, while highlighting the important algorithmic issues.
AUTONOMOUS ROBOT NAVIGATION USING A GENETIC ALGORITHM WITH AN EFFICIENT GENOTYPE ADITIA HERMANU
Wainwright, Roger L.
1 AUTONOMOUS ROBOT NAVIGATION USING A GENETIC ALGORITHM WITH AN EFFICIENT GENOTYPE STRUCTURE ADITIA & Computer Sciences Tulsa, Oklahoma ABSTRACT The goal for real-time mobile robots is to travel the shortest robots to plan this path without the need for human intervention. The path- planning problem has been
May. 2, 2013 BBM 202 -ALGORITHMS
Erdem, Erkut
May. 2, 2013 BBM 202 - ALGORITHMS MINIMUM SPANNING TREES, SHORTEST PATH DEPT. OF COMPUTER of G is a subgraph T that is connected and acyclic. Goal. Find a min weight spanning tree. Minimum. Find a min weight spanning tree. Minimum spanning tree not connected 23 10 21 14 24 16 4 18 9 7 11 8 5
A path planning algorithm for lane-following-based autonomous mobile robot navigation
NASA Astrophysics Data System (ADS)
Aljeroudi, Yazan; Paulik, Mark; Krishnan, Mohan; Luo, Chaomin
2010-01-01
In this paper we address the problem of autonomous robot navigation in a "roadway" type environment, where the robot has to drive forward on a defined path that could be impeded by the presence of obstacles. The specific context is the Autonomous Challenge of the Intelligent Ground Vehicle Competition (www.igvc.org). The task of the path planner is to ensure that the robot follows the path without turning back, as can happen in switchbacks, and/or leaving the course, as can happen in dashed or single lane line situations. A multi-behavior path planning algorithm is proposed. The first behavior determines a goal using a center of gravity (CoG) computation from the results of image processing techniques designed to extract lane lines. The second behavior is based on developing a sense of the current "general direction" of the contours of the course. This is gauged based on the immediate path history of the robot. An adaptive-weight-based fusion of the two behaviors is used to generate the best overall direction. This multi-behavior path planning strategy has been evaluated successfully in a Player/Stage simulation environment and subsequently implemented in the 2009 IGVC. The details of our experience will be presented at the conference.
Calibration of neural networks using genetic algorithms, with application to optimal path planning
NASA Technical Reports Server (NTRS)
Smith, Terence R.; Pitney, Gilbert A.; Greenwood, Daniel
1987-01-01
Genetic algorithms (GA) are used to search the synaptic weight space of artificial neural systems (ANS) for weight vectors that optimize some network performance function. GAs do not suffer from some of the architectural constraints involved with other techniques and it is straightforward to incorporate terms into the performance function concerning the metastructure of the ANS. Hence GAs offer a remarkably general approach to calibrating ANS. GAs are applied to the problem of calibrating an ANS that finds optimal paths over a given surface. This problem involves training an ANS on a relatively small set of paths and then examining whether the calibrated ANS is able to find good paths between arbitrary start and end points on the surface.
An energy efficient scatternet formation algorithm for Bluetooth-based sensor networks
Sain Saginbekov; Ibrahim Korpeoglu
2005-01-01
In this paper, we propose an energy-efficient scatternet formation algorithm for Bluetooth based sensor networks. The algorithm is based on first computing a shortest path tree from the base station to all sensor nodes and then solving the degree constraint problem so that the degree of each node in the network is not greater than seven, which is a Bluetooth
An Energy-Ecien t Scatternet Formation Algorithm for Bluetooth-Based Sensor Networks
Sain Saginbekov; Ibrahim Korpeoglu
2004-01-01
In this paper, we propose an energy-ecient scatternet formation algorithm for Bluetooth based sensor networks. The algorithm is based on rst computing a shortest path tree from the base sta- tion to all sensor nodes and then solving the de- gree constraint problem so that the degree of each node in the network is not greater than seven, which is
Application of GA, PSO, and ACO algorithms to path planning of autonomous underwater vehicles
NASA Astrophysics Data System (ADS)
Aghababa, Mohammad Pourmahmood; Amrollahi, Mohammad Hossein; Borjkhani, Mehdi
2012-09-01
In this paper, an underwater vehicle was modeled with six dimensional nonlinear equations of motion, controlled by DC motors in all degrees of freedom. Near-optimal trajectories in an energetic environment for underwater vehicles were computed using a numerical solution of a nonlinear optimal control problem (NOCP). An energy performance index as a cost function, which should be minimized, was defined. The resulting problem was a two-point boundary value problem (TPBVP). A genetic algorithm (GA), particle swarm optimization (PSO), and ant colony optimization (ACO) algorithms were applied to solve the resulting TPBVP. Applying an Euler-Lagrange equation to the NOCP, a conjugate gradient penalty method was also adopted to solve the TPBVP. The problem of energetic environments, involving some energy sources, was discussed. Some near-optimal paths were found using a GA, PSO, and ACO algorithms. Finally, the problem of collision avoidance in an energetic environment was also taken into account.
Dayong Zhou; Victor E. Debrunner
2007-01-01
Active noise control (ANC) has been widely applied in industry to reduce environmental noise and equipment vibrations. Most available control algorithms require the identification of the secondary path, which increases the control system complexity, contributes to an increased residual noise power, and can even cause the control system to fail if the identified secondary path is not sufficiently close to
NASA Astrophysics Data System (ADS)
Zhang, Jie; Lv, Chunhui; Zhao, Yongli; Chen, Bowen; Li, Xin; Huang, Shanguo; Gu, Wanyi
2012-12-01
In this paper, to decrease the traffic loss caused by multiple link failures, we consider the correlated risk among different connection requests when both the primary and backup paths are routed and assigned spectrum. Therefore, a novel shared-path protection algorithm is developed, named shared-path protection algorithm with correlated risk (SPP_CR), in flexible bandwidth optical networks. Based on the correlated risk, the routing can be diverse and the sharing in backup spectral resource will be restricted by SPP_CR algorithm, then the dropped traffic caused by simultaneous multiple failures between primary and backup path can be efficiently decreased. Simulation results show that, SPP_CR algorithm (i) achieves the higher successful service ratio (SSR) than traditional shared-path protection (SPP), shared-path protection with dynamic load balancing (SPP_DLB) and dedicated path protection (DPP); (ii) makes a better tradeoff in blocking probability, protection ratio (PR), average frequency slots consumed (AFSC) and redundancy ratio (RR) than SPP, SPP_DLB and DPP algorithms.
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.
Path planning strategies for autonomous ground vehicles
NASA Astrophysics Data System (ADS)
Gifford, Kevin Kent
Several key issues involved with the planning and executing of optimally generated paths for autonomous vehicles are addressed. Two new path planning algorithms are developed, and examined, which effectively minimize replanning as unmapped hazards are encountered. The individual algorithms are compared via extensive simulation. The search strategy results are implemented and tested using the University of Colorado's autonomous vehicle test-bed, RoboCar, and results show the advantages of solving the single-destination all-paths problem for autonomous vehicle path planning. Both path planners implement a graph search methodology incorporating dynamic programming that solves the single-destination shortest-paths problem. Algorithm 1, termed DP for dynamic programming, searches a state space where each state represents a potential vehicle location in a breadth-first fashion expanding from the goal to all potential start locations in the state space. Algorithm 2, termed DP*, couples the heuristic search power of the well-known A* search procedure (Nilsson-80) with the dynamic programming principle applied to graph searching to efficiently make use of overlapping subproblems. DP* is the primary research contribution of the work contained within this thesis. The advantage of solving the single-destination shortest-paths problem is that the entire terrain map is solved in terms of reaching a specified goal. Therefore, if the robot is diverted from the pre-planned path, an alternative path is already computed. The search algorithms are extended to include a probabilistic approach using empirical loss functions to incorporate terrain map uncertainties into the path considering terrain planning process. The results show the importance of considering terrain uncertainty. If the map representation ignores uncertainty by marking any area with less than perfect confidence as unpassable or assigns it the worst case rating, then the paths are longer than intuitively necessary. A hierarchical software control architecture is introduced that uses as the main guidance function an arbitration-based scheme which is able to efficiently and robustly integrate disparate sensor data. The flexibility provided by such an architecture allows for very easy integration of any type of environmental sensing device into the path planning algorithm.
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.
NASA Astrophysics Data System (ADS)
Berry, R. James; Griffiths, Peter R.
1998-06-01
Open-path Fourier transform infrared (OP/FT-IR) spectrometry is susceptible to interferences, especially those due to atmospheric water and carbon dioxide. To overcome these interferences, multivariate techniques such as classical least squares (CLS) and partial least squares (PLS) regression are used. The CLS method is very sensitive to variations in the background and the presence of lines due to water and carbon dioxide in the spectrum, and usually requires calculations to be made over small spectral windows to minimize these effects. The windows are usually chosen by the user and can reflect the user's bias. We have used a heuristic program called a genetic algorithm to select spectral windows that are independent of user bias and often yield results 2-4 times better than the generally accepted method of spectral window selection. We have also investigated the use of spectral window selection by a genetic algorithm for PLS using much larger spectral windows and found it to be advantageous.
NASA Astrophysics Data System (ADS)
Liu, Bing-Yi; Wang, Jun-Yang; Liu, Zhi-Shen
2014-11-01
Spaceborne integrated path differential absorption (IPDA) lidar is an active-detection system which is able to perform global CO2 measurement with high accuracy of 1ppmv at day and night over ground and clouds. To evaluate the detection performance of the system, simulation of the ground return signal and retrieval algorithm for CO2 concentration are presented in this paper. Ground return signals of spaceborne IPDA lidar under various ground surface reflectivity and atmospheric aerosol optical depths are simulated using given system parameters, standard atmosphere profiles and HITRAN database, which can be used as reference for determining system parameters. The simulated signals are further applied to the research on retrieval algorithm for CO2 concentration. The column-weighted dry air mixing ratio of CO2 denoted by XCO2 is obtained. As the deviations of XCO2 between the initial values for simulation and the results from retrieval algorithm are within the expected error ranges, it is proved that the simulation and retrieval algorithm are reliable.
Li, Bai; Gong, Li-gang; Yang, Wen-lun
2014-01-01
Unmanned combat aerial vehicles (UCAVs) have been of great interest to military organizations throughout the world due to their outstanding capabilities to operate in dangerous or hazardous environments. UCAV path planning aims to obtain an optimal flight route with the threats and constraints in the combat field well considered. In this work, a novel artificial bee colony (ABC) algorithm improved by a balance-evolution strategy (BES) is applied in this optimization scheme. In this new algorithm, convergence information during the iteration is fully utilized to manipulate the exploration/exploitation accuracy and to pursue a balance between local exploitation and global exploration capabilities. Simulation results confirm that BE-ABC algorithm is more competent for the UCAV path planning scheme than the conventional ABC algorithm and two other state-of-the-art modified ABC algorithms. PMID:24790555
Gong, Li-gang; Yang, Wen-lun
2014-01-01
Unmanned combat aerial vehicles (UCAVs) have been of great interest to military organizations throughout the world due to their outstanding capabilities to operate in dangerous or hazardous environments. UCAV path planning aims to obtain an optimal flight route with the threats and constraints in the combat field well considered. In this work, a novel artificial bee colony (ABC) algorithm improved by a balance-evolution strategy (BES) is applied in this optimization scheme. In this new algorithm, convergence information during the iteration is fully utilized to manipulate the exploration/exploitation accuracy and to pursue a balance between local exploitation and global exploration capabilities. Simulation results confirm that BE-ABC algorithm is more competent for the UCAV path planning scheme than the conventional ABC algorithm and two other state-of-the-art modified ABC algorithms. PMID:24790555
Herráez, Miguel Arevallilo; Burton, David R; Lalor, Michael J; Gdeisat, Munther A
2002-12-10
We describe what is to our knowledge a novel technique for phase unwrapping. Several algorithms based on unwrapping the most-reliable pixels first have been proposed. These were restricted to continuous paths and were subject to difficulties in defining a starting pixel. The technique described here uses a different type of reliability function and does not follow a continuous path to perform the unwrapping operation. The technique is explained in detail and illustrated with a number of examples. PMID:12502301
Robot Path Integration in Manufacturing Processes: Genetic Algorithm Versus Ant Colony Optimization
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
A Hierarchical Path View Model for Path Finding in Intelligent Transportation Systems
Yun-Wu Huang; Ning Jing; ELKE A. RUNDENSTEINER
1997-01-01
Effective path finding has been identified as an important requirement for dynamic route guidance in Intelligent Transportation Systems (ITS). Path finding is most efficient if the all-pair (shortest) paths are precomputed because path search requires only simple lookups of the precomputed path views. Such an approach however incurs path view maintenance (computation and update) and storage costs which can be
Er. Waghoo Parvez
This paper presents a review to the path planning optimization problem using genetic algorithm as a tool. Path planning is a term used in robotics for the process of detailing a task into discrete motions. It is aimed at enabling robots with capabilities of automatically deciding and executing a sequence motion in order to achieve a task without collision with other objects in a given environment. Genetic algorithms are considered as a search process used in computing to find exact or an approximate solution for optimization and search problems. There are also termed as global search heuristics. These techniques are inspired by evolutionary biology such as inheritance mutation, selection and cross over.
NASA Technical Reports Server (NTRS)
Longendorfer, B. A.
1976-01-01
The construction of an autonomous roving vehicle requires the development of complex data-acquisition and processing systems, which determine the path along which the vehicle travels. Thus, a vehicle must possess algorithms which can (1) reliably detect obstacles by processing sensor data, (2) maintain a constantly updated model of its surroundings, and (3) direct its immediate actions to further a long range plan. The first function consisted of obstacle recognition. Obstacles may be identified by the use of edge detection techniques. Therefore, the Kalman Filter was implemented as part of a large scale computer simulation of the Mars Rover. The second function consisted of modeling the environment. The obstacle must be reconstructed from its edges, and the vast amount of data must be organized in a readily retrievable form. Therefore, a Terrain Modeller was developed which assembled and maintained a rectangular grid map of the planet. The third function consisted of directing the vehicle's actions.
An Algorithm to Compute Statistics of Stochastic Paths on Complex Landscapes
NASA Astrophysics Data System (ADS)
Manhart, Michael; Morozov, Alexandre V.
2013-03-01
Many systems in physics, chemistry, and biology can be modeled as a random walk on a network subject to a potential landscape. There is great interest in understanding the statistical properties of pathways on these landscapes, especially their times, lengths, and distributions in space. The complexity of the networks and landscapes arising in many models makes them difficult to solve by traditional analytical and computational tools. Moreover, standard methods do not always provide the most relevant information for characterizing these pathways. We develop an explicitly path-based formalism for studying these problems, which we implement using a numerical dynamic programming algorithm. It is especially well-suited to studying first-passage problems and rare transitions between metastable states. This method is valid for arbitrary networks and landscapes, as well as semi-Markovian processes with non-exponential waiting-time distributions. We explore this method on a variety of simple models including regular lattices, fractals, and protein sequence evolution.
Bowen, J. [National Univ. of Ireland, Cork (Ireland); Dozier, G. [North Carolina A& T State Univ., Greensboro, NC (United States)
1996-12-31
This paper introduces a hybrid evolutionary hill-climbing algorithm that quickly solves (Constraint Satisfaction Problems (CSPs)). This hybrid uses opportunistic arc and path revision in an interleaved fashion to reduce the size of the search space and to realize when to quit if a CSP is based on an inconsistent constraint network. This hybrid outperforms a well known hill-climbing algorithm, the Iterative Descent Method, on a test suite of 750 randomly generated CSPs.
Linear approximation of shortest superstrings
Avrim Blum; Tao Jiang; Ming Li; John Tromp; Mihalis Yannakakis
1994-01-01
We consider the following problem: given a collection of strings s1,…, sm, find the shortest string s such that each si appears as a substring (a consecutive block) of s. Although this problem is known to be NP-hard, a simple greedy procedure appears to do quite well and is routinely used in DNA sequencing and data compression practice, namely: repeatedly
Localization Algorithm with On-line Path Loss Estimation and Node Selection
Bel, Albert; Vicario, José López; Seco-Granados, Gonzalo
2011-01-01
RSS-based localization is considered a low-complexity algorithm with respect to other range techniques such as TOA or AOA. The accuracy of RSS methods depends on the suitability of the propagation models used for the actual propagation conditions. In indoor environments, in particular, it is very difficult to obtain a good propagation model. For that reason, we present a cooperative localization algorithm that dynamically estimates the path loss exponent by using RSS measurements. Since the energy consumption is a key point in sensor networks, we propose a node selection mechanism to limit the number of neighbours of a given node that are used for positioning purposes. Moreover, the selection mechanism is also useful to discard bad links that could negatively affect the performance accuracy. As a result, we derive a practical solution tailored to the strict requirements of sensor networks in terms of complexity, size and cost. We present results based on both computer simulations and real experiments with the Crossbow MICA2 motes showing that the proposed scheme offers a good trade-off in terms of position accuracy and energy efficiency. PMID:22163992
Multi-Objective Path Selection Model and Algorithm for Emergency Evacuation
Yuan Yuan; Dingwei Wang
2007-01-01
Evacuation planning is one of the most important aspects of emergency management. Path selection is one of the fundamental problems in evacuation planning. A multi-objective mathematical model is presented for path selection in emergency evacuation. The two objectives of the model are to minimize the total travel time along a path and to minimize the path complexity respectively. Taking into
Object location using path separators
Ittai Abraham; Cyril Gavoille
2006-01-01
We study a novel separator property called k-path separa- ble. Roughly speaking, a k-path separable graph can be re- cursively separated into smaller components by sequentially removing k shortest paths. Our main result is that every minor free weighted graph is k-path separable. We then show that k-path separable graphs can be used to solve sev- eral object location problems:
A computational study of routing algorithms for realistic transportation networks
Jacob, R.; Marathe, M.V.; Nagel, K.
1998-12-01
The authors carry out an experimental analysis of a number of shortest path (routing) algorithms investigated in the context of the TRANSIMS (Transportation Analysis and Simulation System) project. The main focus of the paper is to study how various heuristic and exact solutions, associated data structures affected the computational performance of the software developed especially for realistic transportation networks. For this purpose the authors have used Dallas Fort-Worth road network with very high degree of resolution. The following general results are obtained: (1) they discuss and experimentally analyze various one-one shortest path algorithms, which include classical exact algorithms studied in the literature as well as heuristic solutions that are designed to take into account the geometric structure of the input instances; (2) they describe a number of extensions to the basic shortest path algorithm. These extensions were primarily motivated by practical problems arising in TRANSIMS and ITS (Intelligent Transportation Systems) related technologies. Extensions discussed include--(i) time dependent networks, (ii) multi-modal networks, (iii) networks with public transportation and associated schedules. Computational results are provided to empirically compare the efficiency of various algorithms. The studies indicate that a modified Dijkstra`s algorithm is computationally fast and an excellent candidate for use in various transportation planning applications as well as ITS related technologies.
NASA Astrophysics Data System (ADS)
Phanthong, Thanapong; Maki, Toshihiro; Ura, Tamaki; Sakamaki, Takashi; Aiyarak, Pattara
2014-03-01
This paper describes path re-planning techniques and underwater obstacle avoidance for unmanned surface vehicle (USV) based on multi-beam forward looking sonar (FLS). Near-optimal paths in static and dynamic environments with underwater obstacles are computed using a numerical solution procedure based on an A* algorithm. The USV is modeled with a circular shape in 2 degrees of freedom (surge and yaw). In this paper, two-dimensional (2-D) underwater obstacle avoidance and the robust real-time path re-planning technique for actual USV using multi-beam FLS are developed. Our real-time path re-planning algorithm has been tested to regenerate the optimal path for several updated frames in the field of view of the sonar with a proper update frequency of the FLS. The performance of the proposed method was verified through simulations, and sea experiments. For simulations, the USV model can avoid both a single stationary obstacle, multiple stationary obstacles and moving obstacles with the near-optimal trajectory that are performed both in the vehicle and the world reference frame. For sea experiments, the proposed method for an underwater obstacle avoidance system is implemented with a USV test platform. The actual USV is automatically controlled and succeeded in its real-time avoidance against the stationary undersea obstacle in the field of view of the FLS together with the Global Positioning System (GPS) of the USV.
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.
Improvement of phase diversity algorithm for non-common path calibration in extreme AO context
NASA Astrophysics Data System (ADS)
Robert, Clélia; Fusco, Thierry; Sauvage, Jean-François; Mugnier, Laurent
2008-07-01
Exoplanet direct imaging with a ground-based telescope needs a very high performance adaptive optics (AO) system, so-called eXtreme AO (XAO), a coronagraph device, and a smart imaging process. One limitation of AO system in operation remains the Non Common Path Aberrations (NCPA). To achieve the ultimate XAO performance, these aberrations have to be measured with a dedicated wavefront sensor placed in the imaging camera focal plane, and then pre-compensated using the AO closed loop process. In any events, the pre-compensation should minimize the aberrations at the coronagraph focal plane mask. An efficient way for the NCPA measurement is the phase diversity technique. A pixel-wise approach is well-suited to estimate NCPA on large pupils and subsequent projection on the deformable mirror with Cartesian geometry. However it calls for a careful regularization for optimal results. The weight of the regularization is written in close-form for un-supervised tuning. The accuracy of NCPA pre-compensation is below 8 nm for a wide range of conditions. Point-by-point phase estimation improves the accuracy of the Phase Diversity method. The algorithm is validated in simulation and experimentally. It will be implemented in SAXO, the XAO system of the second generation VLT instrument: SPHERE.
Optimization of transport protocols with path-length constraints in complex networks.
Ramasco, José J; de La Lama, Marta S; López, Eduardo; Boettcher, Stefan
2010-09-01
We propose a protocol optimization technique that is applicable to both weighted and unweighted graphs. Our aim is to explore by how much a small variation around the shortest-path or optimal-path protocols can enhance protocol performance. Such an optimization strategy can be necessary because even though some protocols can achieve very high traffic tolerance levels, this is commonly done by enlarging the path lengths, which may jeopardize scalability. We use ideas borrowed from extremal optimization to guide our algorithm, which proves to be an effective technique. Our method exploits the degeneracy of the paths or their close-weight alternatives, which significantly improves the scalability of the protocols in comparison to shortest-path or optimal-path protocols, keeping at the same time almost intact the length or weight of the paths. This characteristic ensures that the optimized routing protocols are composed of paths that are quick to traverse, avoiding negative effects in data communication due to path-length increases that can become specially relevant when information losses are present. PMID:21230151
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.
A Linear Algorithm for the Pos\\/Neg-Weighted 1Median Problem on a Cactus
Rainer E. Burkard; Jakob Krarup
1998-01-01
The 1-median problem on a network asks for a vertex minimizing the sum of the weighted shortest path distances from itself\\u000a to all other vertices, each associated with a certain positive weight. We allow fornegative weights as well and devise an exact algorithm for the resulting ‘pos\\/neg-weighted’ problem defined on a cactus. The algorithm\\u000a visits every vertex just once and
NASA Astrophysics Data System (ADS)
Chen, Jun; Luo, Chaomin; Krishnan, Mohan; Paulik, Mark; Tang, Yipeng
2010-01-01
An enhanced dynamic Delaunay Triangulation-based (DT) path planning approach is proposed for mobile robots to plan and navigate a path successfully in the context of the Autonomous Challenge of the Intelligent Ground Vehicle Competition (www.igvc.org). The Autonomous Challenge course requires the application of vision techniques since it involves path-based navigation in the presence of a tightly clustered obstacle field. Course artifacts such as switchbacks, ramps, dashed lane lines, trap etc. are present which could turn the robot around or cause it to exit the lane. The main contribution of this work is a navigation scheme based on dynamic Delaunay Triangulation (DDT) that is heuristically enhanced on the basis of a sense of general lane direction. The latter is computed through a "GPS (Global Positioning System) tail" vector obtained from the immediate path history of the robot. Using processed data from a LADAR, camera, compass and GPS unit, a composite local map containing both obstacles and lane line segments is built up and Delaunay Triangulation is continuously run to plan a path. This path is heuristically corrected, when necessary, by taking into account the "GPS tail" . With the enhancement of the Delaunay Triangulation by using the "GPS tail", goal selection is successfully achieved in a majority of situations. The robot appears to follow a very stable path while navigating through switchbacks and dashed lane line situations. The proposed enhanced path planning and GPS tail technique has been successfully demonstrated in a Player/Stage simulation environment. In addition, tests on an actual course are very promising and reveal the potential for stable forward navigation.
Venkatesan Guruswami; Sanjeev Khanna; Rajmohan Rajaraman; Bruce Shepherd; Mihalis Yannakakis
1999-01-01
We study the approximability of edge-disjoint paths and related problems. In theedge-disjoint paths problem (EDP), we are given a network G with source-sink pairs(s i ; t i ), 1 i k, and the goal is to nd a largest subset of source-sink pairs thatcan be simultaneously connected in an edge-disjoint manner. We show that in directednetworks, for any >
A dynamic programming algorithm applied to track initiation
Coleman, D.E.
1989-09-01
An approach for initiating tracks for multiple target tracking is presented. A means of using a graph to represent objects moving in a sequence of images is given. The approach for initiating tracks is based on a dynamic programming algorithm for finding the shortest path in the graph. For comparison purposes an extensive optimal solution and other practical track initiation approaches from the open literature are discussed. 7 refs., 7 figs.
Hammock-on-Ears Decomposition: A Technique for the E cient Parallel Solution of Shortest
Hammock-on-Ears Decomposition: A Technique for the E cient Parallel Solution of Shortest Paths, ~, of outerplanar subgraphs (called hammocks) satisfying certain separator properties. Our work combines and extends the sequential hammock decomposition technique intro- duced by G. Frederickson and the parallel ear decomposition
Hammock-on-Ears Decomposition: A Technique for the Efficient Parallel Solution of Shortest
Zaroliagis, Christos D.
Hammock-on-Ears Decomposition: A Technique for the Efficient Parallel Solution of Shortest Paths (called hammocks) satis- fying certain separator properties. We achieve this decomposition in O(log n log algo- rithm for decomposing any (di)graph into a set of outerplanar subgraphs (called hammocks
Shortest-Cycle Photonic Network Restoration K J Warbrick, X Lu, R Friskney and K Durrani
Haddadi, Hamed
Shortest-Cycle Photonic Network Restoration K J Warbrick, X Lu, R Friskney and K Durrani Nortel is currently based upon point-to-point optical connections organised into physical rings. This architecture has and protection paths and nodes configured in the ring. This is the basis of protection in SONET/SDH ring networks
Sun, Quanping; Chen, Xiaogang; Chen, Qianliang; Dai, Ning; Liao, Wenhe; He, Ning
2009-10-01
Molar crown is very small and has not only thin-wall, but also complex profile, especially, the occlusal surface of each molar crown has many cusps, ridges and fossae being differently distributed. When conventional processing method is used, it is impossible to machine molar prosthesis rapidly and exactly. To enhance machining velocity and improve the surface precision of molar crown, an algorithm of entity rapid offset-based STL format is put forward. By the application of Zigzag toolpath planning and micro-machining cutter, the finishing toolpaths for high speed milling molar prosthesis are generated. In terms of Mikron UCP800 high-speed machine center, the molar all-crown made of alloy aluminum material is successfully machined. The test results show that the algorithm of tool-path generation works fast, the number of toolpaths is small, and the cutter feeds smoothly. PMID:19947500
Information Spread of Emergency Events: Path Searching on Social Networks
Hu, Hongzhi; Wu, Tunan
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
The value of information in shortest path optimization/
Rinehart, Michael David
2010-01-01
Information about a random event (termed the source) is typically treated as a (possibly noisy) function of that event. Information has a destination, an agent, that uses the information to make a decision. In traditional ...
Carpooling : the 2 Synchronization Points Shortest Paths Problem
Paris-Sud XI, UniversitÃ© de
Carpooling is an appropriate solution to address traffic congestion and to reduce the ecological footprint encouraged to park private cars near multimodal hubs (i.e. park and ride stations) and to use the public to the public transport system. An appropriate solution, requiring little investment and reducing the ecological
Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality
M. E. J. Newman
2001-01-01
Using computer databases of scientific papers in physics, biomedical research, and computer science, we have constructed networks of collaboration between scientists in each of these disciplines. In these networks two scientists are considered connected if they have coauthored one or more papers together. Here we study a variety of nonlocal statistics for these networks, such as typical distances between scientists
Scaling inequalities for shortest paths in regular and invasion percolation.
not hold in d = 2, [Kesten, 1987].) Using a partly di#erent approach we prove a similar theorem in two systems, [Kesten & Zhang, 1993] and [Aizenman & Burchard, 1999]. In the second part of the paper we
Shortest Path Computation with No Information Leakage Kyriakos Mouratidis
Yiu, Man Lung
reveal personal information, such as social habits, health condition, shop- ping preferences, lifestyle systems and the diffusion of smart-phones has led to an expanding market of location-based services (LBSs, lifestyle choices, etc) which may be tracked and misused by the LBS. Pos- sible forms of misuse include
Methodology for Augmenting Existing Paths with Additional Parallel Transects
Wilson, John E.
2013-09-30
Visual Sample Plan (VSP) is sample planning software that is used, among other purposes, to plan transect sampling paths to detect areas that were potentially used for munition training. This module was developed for application on a large site where existing roads and trails were to be used as primary sampling paths. Gap areas between these primary paths needed to found and covered with parallel transect paths. These gap areas represent areas on the site that are more than a specified distance from a primary path. These added parallel paths needed to optionally be connected together into a single path—the shortest path possible. The paths also needed to optionally be attached to existing primary paths, again with the shortest possible path. Finally, the process must be repeatable and predictable so that the same inputs (primary paths, specified distance, and path options) will result in the same set of new paths every time. This methodology was developed to meet those specifications.
A robust point set registration algorithm based on information geometry
NASA Astrophysics Data System (ADS)
Hua, Xiaoqiang; Wang, Ping; Ji, Kefeng; Gao, Yinghui; Fu, Ruigang
2014-11-01
Point set registration is a key component in many computer vision tasks. This paper proposes a point set registration algorithm based on information geometry. Point sets to be registration are converting to the statistical manifolds by Gaussian mixture model. The component of mixture model represents the dimension of statistical manifold and point set is a point on manifold. Through conversion, point set registration is reformulated as searching the shortest path between two manifold and we can use the em algorithm which defined by information geometry to get the optimization solution. Experimental results show that the proposed algorithm is robust to noise and outliers, and achieved very good accuracy.
Approximation Algorithms and Heuristics for a 2-depot, Heterogeneous Hamiltonian Path Problem
Doshi, Riddhi Rajeev
2011-10-21
heterogeneous vehicles. As the addressed routing problem is NP-Hard, we develop an approximation algorithm and heuristics to solve the problem. Our approach involves dividing the routing problem into two sub-problems: Partitioning and Sequencing. Partitioning...
Zhao, Gongyun
Abstract. Most existing interior-point methods for a linear complementarit* *y problem (LCP) require when the problem is a P* LCP and ha* *s a solution. Moreover, when the problem is a monotone LCP classifications. 90C05 Abbreviated Title: An Infeasible Interior-Point Algorithm for LCP 1
Zhao, Gongyun
complementarity problem (LCP) require the existence of a strictly feasible point to guarantee that the iterates when the problem is a P # LCP and has a solution. Moreover, when the problem is a monotone LCP and hasÂPoint Algorithm for LCP 1 Introduction The linear complementarity problem (LCP) is the problem of finding a vector
An Implementation of Mobile Robots' Path Planning and Tracing Based on Fuzzy PID Algorithms
Wu Zhou; Yanjun Fang
2008-01-01
To participate in the Asia Broadcast Union Robocon Contest 2008, some intelligent mobile robots are designed in Wuhan University of China. The two-wheel robot is navigated by two separated photoelectric encoders fixed beside the wheels symmetrically. The encoders can give the feedback of the practical robot's displacement and speed. The advanced fuzzy PID algorithm is proposed to improve the conventional
Ivan Stojmenovic; Xu Lin
2001-01-01
In a localized routing algorithm, each node makes forwarding decisions solely based on the position of itself, its neighbors, and its destination. In distance, progress, and direction-based approaches (reported in the literature), when node A wants to send or forward message m to destination node D, it forwards m to its neighbor C which is closest to D (has best
Heikalabad, Saeed Rasouli; Nematy, Farhad; Rahmani, Naeim
2011-01-01
Enabling real time applications in wireless sensor networks requires certain delay and bandwidth which pose more challenges in the design of routing protocols. The algorithm that is used for packet routing in such applications should be able to establish a tradeoff between end to end delay parameter and energy consumption. In this paper, we propose a new multi path routing algorithm for real time applications in wireless sensor networks namely QEMPAR which is QoS aware and can increase the network lifetime. Simulation results show that the proposed algorithm is more efficient than previous algorithms in providing quality of service requirements of real-time applications.
Parallel message-passing architecture for path planning
NASA Astrophysics Data System (ADS)
Tavora, Jose; Lourtie, Pedro M. G.
1991-03-01
A prototype solving the Shortest Path Problem (SPP) by a parallel message-passing algorithm is presented. The system, an OCCAM program running on a transputer board hosted by a PC, implements a known distributed algorithm for the SPP, based on the 'diffused computation' paradigm. A new parallel message-passing architecture is proposed, built upon a static packet-switching network with a fractal topology. The recursive, unlimited network, features an interesting property when applied to four-link processors (like transputers): it's decomposable, at any hierarchical level, in four-link modules or supernodes. Labelling and routing algorithms for the network, exploiting self-similarity, are described. Experimental results, obtained with a single transputer solving irregular random graphs (up to 256 nodes) are presented, showing a time complexity function growing linearly with the total number of arcs.
Dijkstra's Algorithm On-Line: An Empirical Case Study from Public Railroad Transport
Frank Schulz; Dorothea Wagner; Karsten Weihe
1999-01-01
Traffic information systems are among the most prominent real-world applications of Dijkstra’s algorithm for shortest paths.\\u000a We consider the scenario of a central information server in the realm of public railroad transport on wide-area networks.\\u000a Such a system has to process a large number of on-line queries in real time. In practice, this problem is usually solved by\\u000a heuristical variations
Dijkstra's Algorithm On-Line: An Empirical Case Study from Public Railroad Transport
Frank Schulz; Dorothea Wagner; Karsten Weihe
2000-01-01
Traffic information systems are among the most prominent real-world applications of Dijkstra's algorithm for shortest paths. We consider the scenario of a central information server in the realm of public railroad transport on wide-area networks. Such a system has to process a large number of on-line queries for optimal travel connections in real time. In practice, this problem is usually
Shortest Expected Delay Routing for Erlang Servers
Ivo J. B. F. Adan; Jaap Wessels
1996-01-01
The queueing problem with Poisson arrivals and two identical parallel Erlang servers is analyzed for the case of shortest expected delay routing. This problem may be represented as a random walk on the integer grid in the first quadrant of the plane. An important aspect of the random walk is that it is possible to make large jumps in the
Designing a dynamic path guidance system based on electronic maps by using Q-learning
NASA Astrophysics Data System (ADS)
Zou, Liang; Xu, Jianmin; Zhu, Lingxiang
2005-11-01
Shortest path problem from one origin node to one destination node in non-FIFO (First In First Out) dynamic networks is an unsolved hard problem in dynamic path guidance system. A new approach based on Q-learning is adopted to solve the problem based on electronic maps in this paper. The approach uses geographical information on electronic maps to define Q-learning's value function. Q-learning algorithm's strategy train learning method and training process on path searching are presented. Finally based on Guangzhou City's electronic map, we randomly generate a dynamic network containing 20000 nodes, 40000 links and 144 time intervals, which do not satisfy FIFO to test the approach proposed in this paper. The approach is implemented with this dynamic network and its computational performance is analyzed experimentally. The experimental results prove the effectiveness of the approach.
Alur, Rajeev
for weighted timed automata to a parametric shortestÂpath problem in directed graphs. We give a fixÂpoinOptimal Paths in Weighted Timed Automata ? Rajeev Alur 1;2 , Salvatore La Torre 1;3 , and George J to this optimization problem consists of reducing it to a (parametric) shortestÂpath problem in a finite directed graph
The Trade-offs of Multicast Trees and Algorithms
Liming Wei; Deborah Estrin
1995-01-01
Multicast trees can be shared across sources (shared trees) or may be source-specific (shortest pathtrees). Inspired by recent interests in using shared trees for interdomain multicasting, we investigate thetrade-offs among shared tree types and source specific shortest path trees, by comparing performanceover both individual multicast group and the whole network. The performance is evaluated in termsof path length, link cost,
Efficient Algorithms for Shortest Partial Seeds in Words
Lonardi, Stefano
: occurrences are aligned a a a a a a a a a a a ab b b b T. Kociumaka, S. Pissis, J. Radoszewski, W. Rytter, T Periodicity: occurrences are aligned a a a a a a a a a a a ab b b ba a a b T. Kociumaka, S. Pissis, J: occurrences may overlap a a a a a a a a a a a a ab b b b T. Kociumaka, S. Pissis, J. Radoszewski, W. Rytter, T
Moore, John Barratt
dimensional Hilbert space, interior point algorithms for solving LQ control problems with finitely many linear methods are an efficient tool for solving many classes of constrained optimization problems. One of 1PM's which has resulted in new algorithms for solving constrained optimal control problems
Straub, John E.
for a diffusive dynamics assuming isotropic friction. The resulting reaction path is temperature dependent-9606 97 01437-2 I. INTRODUCTION In estimating the reaction rate for a chemical reaction the careful on this choice. For activated processes, the absolute reaction rate constant is very sensitive to the choice
Primal-dual approximation algorithms for the survivable network design problem
Goemans, M.; Williamson, D.
1994-12-31
We consider the survivable network design problem (SNDP), the problem of designing a minimum cost network satisfying connectivity requirements between pairs of vertices. We describe a heuristic algorithm with a provable worst-case performance guarantee for this problem, as well as for a host of related problems. The algorithm is primal-dual and generalizes exact algorithms for the shortest path and minimum spanning tree problems. The most recent version of the algorithm, due to M. Goemans, A. Goldberg, S. Plotkin, D. Shmoys, {acute E}. Tardos and D. Williamson, has the best known performance guarantee both in general and for most special cases. The talk will be a survey of a stream of results of the authors and a number of colleagues, including the above-mentioned researchers and H. Gabow, M. Mihail and V. Vazirani. The emphasis of the talk will be on the methodology behind this approximation algorithm.
Optimal paths for a car that goes both forwards and backwards
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?
?minimax: An Optimally Randomized MINIMAX Algorithm.
García Díez, Silvia; Laforge, Jérôme; Saerens, Marco
2012-08-01
This paper proposes a simple extension of the celebrated MINIMAX algorithm used in zero-sum two-player games, called ?minimax. The ?minimax algorithm allows controlling the strength of an artificial rival by randomizing its strategy in an optimal way. In particular, the randomized shortest-path framework is applied for biasing the artificial intelligence (AI) adversary toward worse or better solutions, therefore controlling its strength. In other words, our model aims at introducing/implementing bounded rationality to the MINIMAX algorithm. This framework takes into account all possible strategies by computing an optimal tradeoff between exploration (quantified by the entropy spread in the tree) and exploitation (quantified by the expected cost to an end game) of the game tree. As opposed to other tree-exploration techniques, this new algorithm considers complete paths of a tree (strategies) where a given entropy is spread. The optimal randomized strategy is efficiently computed by means of a simple recurrence relation while keeping the same complexity as the original MINIMAX. As a result, the ?minimax implements a nondeterministic strength-adapted AI opponent for board games in a principled way, thus avoiding the assumption of complete rationality. Simulations on two common games show that ?minimax behaves as expected. PMID:22893439
The Dwarf Novae of Shortest Period
J. R. Thorstensen; J. O. Patterson; J. Kemp; S. Vennes
2002-06-25
We present observations of the dwarf novae GW Lib, V844 Her, and DI UMa. Radial velocities of H-alph yield orbital periods of 0.05332 +- 0.00002 d (= 76.78 m) for GW Lib and and 0.054643 +- 0.000007 d (= 78.69 m) for V844 Her. Recently, the orbital period of DI UMa was found to be only 0.054564 +- 0.000002 d (= 78.57 m) by Fried et al. (1999), so these are the three shortest orbital periods among dwarf novae with normal-abundance secondaries. GW Lib has attracted attention as a cataclysmic binary showing apparent ZZ Ceti-type pulsations of the white dwarf primary. Its spectrum shows sharp Balmer emission flanked by strong, broad Balmer absorption, indicating a dominant contribution by white-dwarf light. Analysis of the Balmer absorption profiles is complicated by the unknown residual accretion luminosity and lack of coverage of the high Balmer lines. Our best-fit model atmospheres are marginally hotter than the ZZ Ceti instability strip, in rough agreement with recent ultraviolet results from HST. The spectrum and outburst behavior of GW Lib make it a near twin of WZ Sge, and we estimate it to have a quiescent V absolute magnitude 12. Comparison with archival data reveals proper motion of 65 +- 12 mas/yr. The mean spectrum of V844 Her is typical of SU UMa dwarf novae. We detected superhumps in the 1997 May superoutburst with superhump period = 0.05597 +- 0.00005 d. The spectrum of DI UMa appears normal for a dwarf nova near minimum light. These three dwarf novae have nearly identical short periods but completely dissimilar outburst characteristics. We discuss possible implications.
Detection of deregulated modules using deregulatory linked path.
Hu, Yuxuan; Gao, Lin; Shi, Kai; Chiu, David K Y
2013-01-01
The identification of deregulated modules (such as induced by oncogenes) is a crucial step for exploring the pathogenic process of complex diseases. Most of the existing methods focus on deregulation of genes rather than the links of the path among them. In this study, we emphasize on the detection of deregulated links, and develop a novel and effective regulatory path-based approach in finding deregulated modules. Observing that a regulatory pathway between two genes might involve in multiple rather than a single path, we identify condition-specific core regulatory path (CCRP) to detect the significant deregulation of regulatory links. Using time-series gene expression, we define the regulatory strength within each gene pair based on statistical dependence analysis. The CCRPs in regulatory networks can then be identified using the shortest path algorithm. Finally, we derive the deregulated modules by integrating the differential edges (as deregulated links) of the CCRPs between the case and the control group. To demonstrate the effectiveness of our approach, we apply the method to expression data associated with different states of Human Epidermal Growth Factor Receptor 2 (HER2). The experimental results show that the genes as well as the links in the deregulated modules are significantly enriched in multiple KEGG pathways and GO biological processes, most of which can be validated to suffer from impact of this oncogene based on previous studies. Additionally, we find the regulatory mechanism associated with the crucial gene SNAI1 significantly deregulated resulting from the activation of HER2. Hence, our method provides not only a strategy for detecting the deregulated links in regulatory networks, but also a way to identify concerning deregulated modules, thus contributing to the target selection of edgetic drugs. PMID:23894653
Mobile transporter path planning
NASA Technical Reports Server (NTRS)
Baffes, Paul; Wang, Lui
1990-01-01
The use of a genetic algorithm (GA) for solving the mobile transporter path planning problem is investigated. The mobile transporter is a traveling robotic vehicle proposed for the space station which must be able to reach any point of the structure autonomously. Elements of the genetic algorithm are explored in both a theoretical and experimental sense. Specifically, double crossover, greedy crossover, and tournament selection techniques are examined. Additionally, the use of local optimization techniques working in concert with the GA are also explored. Recent developments in genetic algorithm theory are shown to be particularly effective in a path planning problem domain, though problem areas can be cited which require more research.
Integrated flight path planning system and flight control system for unmanned helicopters.
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
Integrated Flight Path Planning System and Flight Control System for Unmanned Helicopters
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
A Flexible Reservation Algorithm for Advance Network Provisioning
Balman, Mehmet; Chaniotakis, Evangelos; Shoshani, Arie; Sim, Alex
2010-04-12
Many scientific applications need support from a communication infrastructure that provides predictable performance, which requires effective algorithms for bandwidth reservations. Network reservation systems such as ESnet's OSCARS, establish guaranteed bandwidth of secure virtual circuits for a certain bandwidth and length of time. However, users currently cannot inquire about bandwidth availability, nor have alternative suggestions when reservation requests fail. In general, the number of reservation options is exponential with the number of nodes n, and current reservation commitments. We present a novel approach for path finding in time-dependent networks taking advantage of user-provided parameters of total volume and time constraints, which produces options for earliest completion and shortest duration. The theoretical complexity is only O(n2r2) in the worst-case, where r is the number of reservations in the desired time interval. We have implemented our algorithm and developed efficient methodologies for incorporation into network reservation frameworks. Performance measurements confirm the theoretical predictions.
Sampling diffusive transition paths
F. Miller III, Thomas; Predescu, Cristian
2006-10-12
We address the problem of sampling double-ended diffusive paths. The ensemble of paths is expressed using a symmetric version of the Onsager-Machlup formula, which only requires evaluation of the force field and which, upon direct time discretization, gives rise to a symmetric integrator that is accurate to second order. Efficiently sampling this ensemble requires avoiding the well-known stiffness problem associated with sampling infinitesimal Brownian increments of the path, as well as a different type of stiffness associated with sampling the coarse features of long paths. The fine-features sampling stiffness is eliminated with the use of the fast sampling algorithm (FSA), and the coarse-feature sampling stiffness is avoided by introducing the sliding and sampling (S&S) algorithm. A key feature of the S&S algorithm is that it enables massively parallel computers to sample diffusive trajectories that are long in time. We use the algorithm to sample the transition path ensemble for the structural interconversion of the 38-atom Lennard-Jones cluster at low temperature.
Computing the Length of the Shortest Telomere in the Nucleus
NASA Astrophysics Data System (ADS)
Dao Duc, K.; Holcman, D.
2013-11-01
The telomere length can either be shortened or elongated by an enzyme called telomerase after each cell division. Interestingly, the shortest telomere is involved in controlling the ability of a cell to divide. Yet, its dynamics remains elusive. We present here a stochastic approach where we model this dynamics using a Markov jump process. We solve the forward Fokker-Planck equation to obtain the steady state distribution and the statistical moments of telomere lengths. We focus specifically on the shortest one and we estimate its length difference with the second shortest telomere. After extracting key parameters such as elongation and shortening dynamics from experimental data, we compute the length of telomeres in yeast and obtain as a possible prediction the minimum concentration of telomerase required to ensure a proper cell division.
The Trade-offs of Multicast Trees and Algorithms
Deborah Estrin; Liming Wei
1994-01-01
Multicast trees can be shared across sources (shared trees)or may be source-specific (shortest path trees). Inspired byrecent interests in using shared trees for interdomain multicasting,we investigate the trade-offs among shared treetypes and source specific shortest path trees, by comparingperformance over both individual multicast group and thewhole network. The performance is evaluated in terms ofpath length, link cost, and traffic concentration.We
An efficient QoS-aware routing algorithm for LEO polar constellations
NASA Astrophysics Data System (ADS)
Tian, Xin; Pham, Khanh; Blasch, Erik; Tian, Zhi; Shen, Dan; Chen, Genshe
2013-05-01
In this work, a Quality of Service (QoS)-aware routing (QAR) algorithm is developed for Low-Earth Orbit (LEO) polar constellations. LEO polar orbits are the only type of satellite constellations where inter-plane inter-satellite links (ISLs) are implemented in real world. The QAR algorithm exploits features of the topology of the LEO satellite constellation, which makes it more efficient than general shortest path routing algorithms such as Dijkstra's or extended Bellman-Ford algorithms. Traffic density, priority, and error QoS requirements on communication delays can be easily incorporated into the QAR algorithm through satellite distances. The QAR algorithm also supports efficient load balancing in the satellite network by utilizing the multiple paths from the source satellite to the destination satellite, and effectively lowers the rate of network congestion. The QAR algorithm supports a novel robust routing scheme in LEO polar constellation, which is able to significantly reduce the impact of inter-satellite link (ISL) congestions on QoS in terms of communication delay and jitter.
Advisory Algorithm for Scheduling Open Sectors, Operating Positions, and Workstations
NASA Technical Reports Server (NTRS)
Bloem, Michael; Drew, Michael; Lai, Chok Fung; Bilimoria, Karl D.
2012-01-01
Air traffic controller supervisors configure available sector, operating position, and work-station resources to safely and efficiently control air traffic in a region of airspace. In this paper, an algorithm for assisting supervisors with this task is described and demonstrated on two sample problem instances. The algorithm produces configuration schedule advisories that minimize a cost. The cost is a weighted sum of two competing costs: one penalizing mismatches between configurations and predicted air traffic demand and another penalizing the effort associated with changing configurations. The problem considered by the algorithm is a shortest path problem that is solved with a dynamic programming value iteration algorithm. The cost function contains numerous parameters. Default values for most of these are suggested based on descriptions of air traffic control procedures and subject-matter expert feedback. The parameter determining the relative importance of the two competing costs is tuned by comparing historical configurations with corresponding algorithm advisories. Two sample problem instances for which appropriate configuration advisories are obvious were designed to illustrate characteristics of the algorithm. Results demonstrate how the algorithm suggests advisories that appropriately utilize changes in airspace configurations and changes in the number of operating positions allocated to each open sector. The results also demonstrate how the advisories suggest appropriate times for configuration changes.
NASA Astrophysics Data System (ADS)
Luangpaiboon, P.
2009-10-01
Many entrepreneurs face to extreme conditions for instances; costs, quality, sales and services. Moreover, technology has always been intertwined with our demands. Then almost manufacturers or assembling lines adopt it and come out with more complicated process inevitably. At this stage, products and service improvement need to be shifted from competitors with sustainability. So, a simulated process optimisation is an alternative way for solving huge and complex problems. Metaheuristics are sequential processes that perform exploration and exploitation in the solution space aiming to efficiently find near optimal solutions with natural intelligence as a source of inspiration. One of the most well-known metaheuristics is called Ant Colony Optimisation, ACO. This paper is conducted to give an aid in complicatedness of using ACO in terms of its parameters: number of iterations, ants and moves. Proper levels of these parameters are analysed on eight noisy continuous non-linear continuous response surfaces. Considering the solution space in a specified region, some surfaces contain global optimum and multiple local optimums and some are with a curved ridge. ACO parameters are determined through hybridisations of Modified Simplex and Simulated Annealing methods on the path of Steepest Ascent, SAM. SAM was introduced to recommend preferable levels of ACO parameters via statistically significant regression analysis and Taguchi's signal to noise ratio. Other performance achievements include minimax and mean squared error measures. A series of computational experiments using each algorithm were conducted. Experimental results were analysed in terms of mean, design points and best so far solutions. It was found that results obtained from a hybridisation with stochastic procedures of Simulated Annealing method were better than that using Modified Simplex algorithm. However, the average execution time of experimental runs and number of design points using hybridisations were longer than those using a single method when compared. Finally they stated a recommendation of proper level settings of ACO parameters for all eight functions that can be used as a guideline for future applications of ACO. This is to promote ease of use of ACO in real life problems.
Parsimonious path openings and closings.
Morard, Vincent; Dokladal, Petr; Decenciere, Etienne
2014-04-01
Path openings and closings are morphological tools used to preserve long, thin, and tortuous structures in gray level images. They explore all paths from a defined class, and filter them with a length criterion. However, most paths are redundant, making the process generally slow. Parsimonious path openings and closings are introduced in this paper to solve this problem. These operators only consider a subset of the paths considered by classical path openings, thus achieving a substantial speed-up, while obtaining similar results. In addition, a recently introduced 1D opening algorithm is applied along each selected path. Its complexity is linear with respect to the number of pixels, independent of the size of the opening. Furthermore, it is fast for any input data accuracy (integer or floating point) and works in stream. Parsimonious path openings are also extended to incomplete paths, i.e., paths containing gaps. Noise-corrupted paths can thus be processed with the same approach and complexity. These parsimonious operators achieve a several orders of magnitude speed-up. Examples are shown for incomplete path openings, where computing times are brought from minutes to tens of milliseconds, while obtaining similar results. PMID:24569442
NASA Technical Reports Server (NTRS)
Ng, Hok K.; Grabbe, Shon; Mukherjee, Avijit
2010-01-01
The optimization of traffic flows in congested airspace with varying convective weather is a challenging problem. One approach is to generate shortest routes between origins and destinations while meeting airspace capacity constraint in the presence of uncertainties, such as weather and airspace demand. This study focuses on development of an optimal flight path search algorithm that optimizes national airspace system throughput and efficiency in the presence of uncertainties. The algorithm is based on dynamic programming and utilizes the predicted probability that an aircraft will deviate around convective weather. It is shown that the running time of the algorithm increases linearly with the total number of links between all stages. The optimal routes minimize a combination of fuel cost and expected cost of route deviation due to convective weather. They are considered as alternatives to the set of coded departure routes which are predefined by FAA to reroute pre-departure flights around weather or air traffic constraints. A formula, which calculates predicted probability of deviation from a given flight path, is also derived. The predicted probability of deviation is calculated for all path candidates. Routes with the best probability are selected as optimal. The predicted probability of deviation serves as a computable measure of reliability in pre-departure rerouting. The algorithm can also be extended to automatically adjust its design parameters to satisfy the desired level of reliability.
Scaling up multiphoton neural scanning: the SSA algorithm.
Schuck, Renaud; Annecchino, Luca A; Schultz, Simon R
2014-01-01
In order to reverse-engineer the information processing capabilities of the cortical circuit, we need to densely sample neural circuit; it may be necessary to sample the activity of thousands of neurons simultaneously. Frame scanning techniques do not scale well in this regard, due to the time "wasted" scanning extracellular space. For scanners in which inertia can be neglected, path length minimization strategies enable large populations to be imaged at relatively high sampling rates. However, in a standard multiphoton microscope, the scanners responsible for beam deflection are inertial, indicating that an optimal solution should take rotor and mirror momentum into account. We therefore characterized the galvanometric scanners of a commercial multiphoton microscope, in order to develop and validate a MATLAB model of microscope scanning dynamics. We tested the model by simulating scan paths across pseudo-randomly positioned neuronal populations of differing neuronal density and field of view. This model motivated the development of a novel scanning algorithm, Adaptive Spiral Scanning (SSA), in which the radius of a circular trajectory is constantly updated such that it follows a spiral trajectory scanning all the cells. Due to the kinematic efficiency of near-circular trajectories, this algorithm achieves higher sampling rates than shortest path approaches, while retaining a relatively efficient coverage fraction in comparison to raster or resonance based frame-scanning approaches. PMID:25570582
A Dynamic Programming Approach to Identifying the Shortest Path in Virtual Learning Environments
ERIC Educational Resources Information Center
Fazlollahtabar, Hamed
2008-01-01
E-learning has been widely adopted as a promising solution by many organizations to offer learning-on-demand opportunities to individual employees (learners) in order to reduce training time and cost. While successful information systems models have received much attention among researchers, little research has been conducted to assess the success…
Solving Stochastic Shortest-Path Problems with RTDP Cognitive Systems Laboratory
Bonet, Blai
Departamento de ComputaciÂ´on Universidad SimÂ´on BolÂ´ivar Aptdo. 89000, Caracas 1080-A Venezuela Abstract We Decision Processes (mdps) that is of central importance to AI: they are the natural gen- eralization
Relative Improvement by Alternative Solutions for Classes of Simple Shortest Path Problems
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
Relative Improvement by Alternative Solutions for Classes of Simple Shortest Path Problems
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
Transitive functional annotation by shortest-path analysis of gene expression data
Zhou, Xianghong Jasmine
be used as an important attribute to link genes of the same biological pathway. Based on large-scale yeast to completely capture the relationship between two expression profiles for such reasons as time-shift (5
Monotonicity Testing and Shortest-Path Routing on the Jop Briet1
Ben-Sasson, Eli
],[Bha08],[HK08] is one of the oldest and most studied problems in Property Testing. The problem], [GGL+ 00], [Fis04], [Ras99], [Bha08], [BGJ+ 09]. Here the order relation x y is defined to hold for x
NASA Technical Reports Server (NTRS)
Janich, Karl W.
2005-01-01
The At-Least version of the Generalized Minimum Spanning Tree Problem (L-GMST) is a problem in which the optimal solution connects all defined clusters of nodes in a given network at a minimum cost. The L-GMST is NPHard; therefore, metaheuristic algorithms have been used to find reasonable solutions to the problem as opposed to computationally feasible exact algorithms, which many believe do not exist for such a problem. One such metaheuristic uses a swarm-intelligent Ant Colony System (ACS) algorithm, in which agents converge on a solution through the weighing of local heuristics, such as the shortest available path and the number of agents that recently used a given path. However, in a network using a solution derived from the ACS algorithm, some nodes may move around to different clusters and cause small changes in the network makeup. Rerunning the algorithm from the start would be somewhat inefficient due to the significance of the changes, so a genetic algorithm based on the top few solutions found in the ACS algorithm is proposed to quickly and efficiently adapt the network to these small changes.
Watanabe, Shin; Tero, Atsushi; Takamatsu, Atsuko; Nakagaki, Toshiyuki
2011-09-01
Traffic optimization of railroad networks was considered using an algorithm that was biologically inspired by an amoeba-like organism, plasmodium of the true slime mold, Physarum polycephalum. The organism developed a transportation network consisting of a tubular structure to transport protoplasm. It was reported that plasmodium can find the shortest path interconnecting multiple food sites during an adaptation process (Nakagaki et al., 2001. Biophys. Chem. 92, 47-52). By mimicking the adaptation process a path finding algorithm was developed by Tero et al. (2007). In this paper, the algorithm is newly modified for applications of traffic distribution optimization in transportation networks of infrastructure such as railroads under the constraint that the network topology is given. Application of the algorithm to a railroad in metropolitan Tokyo, Japan is demonstrated. The results are evaluated using three performance functions related to cost, traveling efficiency, and network weakness. The traffic distribution suggests that the modified Physarum algorithm balances the performances under a certain parameter range, indicating a biological process. PMID:21620930
Efficient Transitive Closure Algorithms
Yannis E. Ioannidis; Raghu Ramakrishnan
1988-01-01
We have developed some efficient algorithms for computing the transitive closure of a directed graph. This paper presents the algorithms for the problem of reachability. The algorithms, however, can be adapted to deal with path computations and a signitkantJy broader class of queries based on onesided recursions. We analyze these algorithms and compare them to algorithms in the literature. The
Disk scheduling algorithms based on rotational position
D. Jacobsen; J. Wilkes
1991-01-01
When sufficient processor power is available, disk scheduling based on rotational position as well as disk arm position is shown to provide improved performance. A taxonomy of algorithms based on Shortest Access Time First (SATF) have been developed, and several of them have been explored through simulations. The access-time based algorithms match or outperform all the seek-time ones we studied.
Robot path planning with distance-safety criterion
NASA Technical Reports Server (NTRS)
Suh, Suk-Hwan; Shin, Kang G.
1987-01-01
A method for determining an optimal path with a weighted distance-safety criterion is developed. The goal is to strike a compromise between the shortest path and the centerline path, which is safer. The method is composed of three parts: (i) construction of a region map by dividing the workspace, (ii) interregion optimization to determine the entry and departure points of the path in each region, and (iii) intraregion optimization for determining the (optimal) path segment within each region. The region map is generated by using an approximate Voronoi diagram, and region optimization is achieved using variational dynamic programming. Although developed for 2-D problems, the method can be easily extended to a class of 3-D problems. Numerical examples are presented to demonstrate the method.
An Optimal Level of Adding Edges for a Simple Path to a Complete K-ary Tree
NASA Astrophysics Data System (ADS)
Sawada, Kiyoshi
2010-10-01
This study proposes a model of adding edges of forming a simple path to a level of depth N in a complete K-ary (K?3) tree of height H under giving priority to edges between two nodes of which the deepest common ancestor is deeper. An optimal depth N* is obtained by maximizing the total shortening path length which is the sum of shortening lengths of shortest paths between every pair of all nodes in the complete K-ary tree.
The shortest period detached binary white dwarf system
NASA Astrophysics Data System (ADS)
Kilic, Mukremin; Brown, Warren R.; Kenyon, S. J.; Allende Prieto, Carlos; Andrews, J.; Kleinman, S. J.; Winget, K. I.; Winget, D. E.; Hermes, J. J.
2011-05-01
We identify SDSS J010657.39-100003.3 (hereafter J0106-1000) as the shortest period detached binary white dwarf (WD) system currently known. We targeted J0106-1000 as part of our radial velocity programme to search for companions around known extremely low-mass (ELM; ˜0.2 M?) WDs using the 6.5-m Multiple Mirror Telescope. We detect peak-to-peak radial velocity variations of 740 km s-1 with an orbital period of 39.1 min. The mass function and optical photometry rule out a main-sequence star companion. Follow-up high-speed photometric observations obtained at the McDonald 2.1-m telescope reveal ellipsoidal variations from the distorted primary but no eclipses. This is the first example of a tidally distorted WD. Modelling the light curve, we constrain the inclination angle of the system to be 67°± 13°. J0106-1000 contains a pair of WDs (0.17 M? primary + 0.43 M? invisible secondary) at a separation of 0.32 R?. The two WDs will merge in 37 Myr and most likely form a core He-burning single subdwarf star. J0106-1000 is the shortest time-scale merger system currently known. The gravitational wave strain from J0106-1000 is at the detection limit of the Laser Interferometer Space Antenna (LISA). However, accurate ephemeris and orbital period measurements may enable LISA to detect J0106-1000 above the Galactic background noise. Based on observations obtained at the Multiple Mirror Telescope (MMT) Observatory, a joint facility of the Smithsonian Institution and the University of Arizona.
Cox, R.G.
1984-01-01
Much controversy surrounds government regulation of routing and scheduling of Hazardous Materials Transportation (HMT). Increases in operating costs must be balanced against expected benefits from local HMT bans and curfews when promulgating or preempting HMT regulations. Algorithmic approaches for evaluating HMT routing and scheduling regulatory policy are described. A review of current US HMT regulatory policy is presented to provide a context for the analysis. Next, a multiobjective shortest path algorithm to find the set of efficient routes under conflicting objectives is presented. This algorithm generates all efficient routes under any partial ordering in a single pass through the network. Also, scheduling algorithms are presented to estimate the travel time delay due to HMT curfews along a route. Algorithms are presented assuming either deterministic or stochastic travel times between curfew cities and also possible rerouting to avoid such cities. These algorithms are applied to the case study of US highway transport of spent nuclear fuel from reactors to permanent repositories. Two data sets were used. One data set included the US Interstate Highway System (IHS) network with reactor locations, possible repository sites, and 150 heavily populated areas (HPAs). The other data set contained estimates of the population residing with 0.5 miles of the IHS and the Eastern US. Curfew delay is dramatically reduced by optimally scheduling departure times unless inter-HPA travel times are highly uncertain. Rerouting shipments to avoid HPAs is a less efficient approach to reducing delay.
TIME-OPTIMAL PATHS FOR LATERAL NAVIGATION OF AN AUTONOMOUS UNDERACTUATED AIRSHIP
Salim Hima; Yasmina Bestaoui
This paper deals with a characterization of the shortest paths for lateral navigation of an autonomous underactuated airship taking into account its dynamics and actuator limitations. The initial and terminal positions are given. We would like to specify the control forces that steer the unmanned aerial vehicle to the given terminal position requiring the minimal time for lateral navigation. The
UAV Intelligent Path Planning for Wilderness Search and Rescue Computer Science Department
Goodrich, Michael A.
has a 100% target detection rate. This means that as the UAV camera footprint moves alongUAV 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
ORIGINAL ARTICLE Multi-objective optimal path selection in electric vehicles
Sait, Sadiq M.
include recharging time in their cri- teria for shortest paths in addition to traveling time and distance. The two main obstacles that hamper the popularity of EVs are their traveling limits and recharging time. The traveling limit of an EV is the maximum time that it can travel without recharging. Rechargeable batteries
Vanquishing the XCB Question: The Methodological Discovery of the Last Shortest Single Axiom for the
Fitelson, Branden
Vanquishing the XCB Question: The Methodological Discovery of the Last Shortest Single Axiom(z y)) z)) a single axiom for the classical equivalential calculus when the rules of inference consist on the other two axioms.) Heretofore, thirteen shortest single axioms for classical equivalence of length
Pokemon Cards and the Shortest Common Superstring Mark Stamp Austin E Stamp
Stamp, Mark
PokÂ´emon Cards and the Shortest Common Superstring Mark Stamp Austin E Stamp June 12, 2003 Abstract Evidence is presented that certain sequences of PokÂ´emon cards are determined by selecting consecutive (SCS), i.e., the shortest string that contains each of the PokÂ´emon card sequences as a consecutive
Hardness of Approximating the Shortest Vector Problem in High L p Norms
Khot, Subhash
Hardness of Approximating the Shortest Vector Problem in High L p Norms Subhash Khot email : khot integers p #21; p(#15;), it is NPÂhard to approximate the Shortest Vector Problem in L p norm within factor hardness shown by Micciancio [27]. 1 #12; 1 Introduction An nÂdimensional lattice L is a set of vectors f P
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.
Minimum-Risk Path Finding by an Adaptive Amoebal Network
NASA Astrophysics Data System (ADS)
Nakagaki, Toshiyuki; Iima, Makoto; Ueda, Tetsuo; Nishiura, Yasumasa; Saigusa, Tetsu; Tero, Atsushi; Kobayashi, Ryo; Showalter, Kenneth
2007-08-01
When two food sources are presented to the slime mold Physarum in the dark, a thick tube for absorbing nutrients is formed that connects the food sources through the shortest route. When the light-avoiding organism is partially illuminated, however, the tube connecting the food sources follows a different route. Defining risk as the experimentally measurable rate of light-avoiding movement, the minimum-risk path is exhibited by the organism, determined by integrating along the path. A model for an adaptive-tube network is presented that is in good agreement with the experimental observations.
Tsiotras, Panagiotis
Multi-resolution Path Planning: Theoretical Analysis, Efficient Implementation, and Extensions iterations more efficiently. Finally, we extend this path planning algorithm to dynamic environments planning algorithm based on the wavelet transform of the environment has been reported previously
Gamma-Normal Probability Distribution Arc Length
Hesam
2014-11-04
used to attack randomness, and many researchers have done lots of work on stochastic ..... showed the performance of the proposed methodology for the shortest path. ... Dreyfus, S. (1969) An appraisal of some shortest path algorithms.
NASA Technical Reports Server (NTRS)
Mcroberts, Malcolm
1990-01-01
Viewgraphs on path planning control are presented. Topics covered include: model based path planning; sensor based path planning; hybrid path planning; proximity sensor array; and applications for fuzzy logic.
The shortest modulation period Blazhko RR Lyrae star: SS Cnc
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.
Identification of biochemical network modules based on shortest retroactive distances.
Sridharan, Gautham Vivek; Hassoun, Soha; Lee, Kyongbum
2011-11-01
Modularity analysis offers a route to better understand the organization of cellular biochemical networks as well as to derive practically useful, simplified models of these complex systems. While there is general agreement regarding the qualitative properties of a biochemical module, there is no clear consensus on the quantitative criteria that may be used to systematically derive these modules. In this work, we investigate cyclical interactions as the defining characteristic of a biochemical module. We utilize a round trip distance metric, termed Shortest Retroactive Distance (ShReD), to characterize the retroactive connectivity between any two reactions in a biochemical network and to group together network components that mutually influence each other. We evaluate the metric on two types of networks that feature feedback interactions: (i) epidermal growth factor receptor (EGFR) signaling and (ii) liver metabolism supporting drug transformation. For both networks, the ShReD partitions found hierarchically arranged modules that confirm biological intuition. In addition, the partitions also revealed modules that are less intuitive. In particular, ShReD-based partition of the metabolic network identified a 'redox' module that couples reactions of glucose, pyruvate, lipid and drug metabolism through shared production and consumption of NADPH. Our results suggest that retroactive interactions arising from feedback loops and metabolic cycles significantly contribute to the modularity of biochemical networks. For metabolic networks, cofactors play an important role as allosteric effectors that mediate the retroactive interactions. PMID:22102800
A hybrid genetic algorithm for the weight setting problem in OSPF\\/ISIS routing
Luciana S. Buriol; Mauricio G. C. Resende; Celso C. Ribeiro; Mikkel Thorup
2005-01-01
Intradomain traffic engineering aims to make more effi- cient use of network resources within an autonomous system. Interior Gateway Protocols such as OSPF (Open Shortest Path First) and IS-IS (Intermediate System- Intermediate System) are commonly used to select the paths along which traffic is routed within an autonomous system. These routing protocols direct traffic based on link weights assigned by
Direct transitive closure algorithms: design and performance evaluation
Rakesh Agrawal; Shaul Dar; H. V. Jagadish
1990-01-01
We present new algorithms for computing transitive closure of large database relations. Unlike iterative algorithms, such as the seminaive and logarithmic algorithms, the termination of our algorithms does not depend on the length of paths in the underlying graph (hence the name direct algorithms). Besides reachability computations, the proposed algorithms can also be used for solving path problems. We discuss
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
Performance Evaluation of Two New Disk Scheduling algorithms for Real-Time Systems
Shenze Chen; John A. Stankovic; James F. Kurose; Donald F. Towsley
1991-01-01
In this paper, we present two new disk scheduling algorithms for real-time systems. The twoalgorithms, called SSEDO(for Shortest Seek and Earliest Deadline by Ordering) and SSEDV(forShortest Seek and Earliest Deadline by Value), combine deadline information and disk servicetime information in different ways. The basic idea behind these new algorithms is to give thedisk I\\/O request with the earliest deadline a
Passivity-Based Designs for Synchronized Path Following
I.-A. F. Ihle; Murat Arcak; Thor I. Fossen
2006-01-01
We consider a formation control system where individual systems are controlled by a path-following design and the path variables are to be synchronized. We first show a passivity property for the path following system and, next, combine this with a passivity-based synchronization algorithm developed in Arcak, M. (2006), The passivity approach expands the classes of synchronization schemes available to the
Efficient Path Delay Test Generation with Boolean Satisfiability
Bian, Kun
2013-12-10
delay test generator CodGen. A mixed structural-functional approach was implemented in CodGen where longest paths were detected using the K Longest Path Per Gate (KLPG) algorithm and path justification and dynamic compaction were handled with the SAT...
Planning Flight Paths of Autonomous Aerobots
NASA Technical Reports Server (NTRS)
Kulczycki, Eric; Elfes, Alberto; Sharma, Shivanjli
2009-01-01
Algorithms for planning flight paths of autonomous aerobots (robotic blimps) to be deployed in scientific exploration of remote planets are undergoing development. These algorithms are also adaptable to terrestrial applications involving robotic submarines as well as aerobots and other autonomous aircraft used to acquire scientific data or to perform surveying or monitoring functions.
Fast, precise flattening of cubic Bezier path and offset curves
Thomas F. Hain; Athar L. Ahmad; David D. Langan
We present two related algorithms for flattening (generating polyline approximations for) curves associated with planar cubic Bezier segments. One flattens the path curve, and the other flattens the left and right offset curves. The algorithm for flattening path curves yields an average of 67% of the vertices generated by recursive subdivision, while maintaining flatness to within 4% of the specified
NASA Astrophysics Data System (ADS)
Ma, Yong; Wang, Hongwei; Zamirian, M.
2012-01-01
We present a new approach containing two steps to determine conflict-free paths for mobile objects in two and three dimensions with moving obstacles. Firstly, the shortest path of each object is set as goal function which is subject to collision-avoidance criterion, path smoothness, and velocity and acceleration constraints. This problem is formulated as calculus of variation problem (CVP). Using parametrization method, CVP is converted to time-varying nonlinear programming problems (TNLPP) and then resolved. Secondly, move sequence of object is assigned by priority scheme; conflicts are resolved by multilevel conflict resolution strategy. Approach efficiency is confirmed by numerical examples.
Richard C. Brewster; Pavol Hell; Sarah H. Pantel; Romeo Rizzi; Anders Yeo
f ~P1g, or f ~P1; ~P2g, the G-packing problem is NP-complete. When G = f ~P1g, the G-packing problem is simply the matching problem. We treat in detail the one remaining case, G = f ~P1; ~P2g. We give in this case a polynomial algorithm for the packing problem. We also give the following positive results: a Berge type augmenting configuration theorem, a min-max characterization, and a reduction to bipartite matching. These results apply also to packings by the family G consisting of all directed paths and cycles. We also explore weighted variants of the problem and include a polyhedral analysis.
NASA Technical Reports Server (NTRS)
Prabhakaran, Nagarajan; Rishe, Naphtali; Athauda, Rukshan
1997-01-01
The South East coastal region experiences hurricane threat for almost six months in every year. To improve the accuracy of hurricane forecasts, meteorologists would need the storm paths of both the present and the past. A hurricane path can be established if we could identify the correct position of the storm at different times right from its birth to the end. We propose a method based on both spatial and temporal image correlations to locate the position of a storm from satellite images. During the hurricane season, the satellite images of the Atlantic ocean near the equator are examined for the hurricane presence. This is accomplished in two steps. In the first step, only segments with more than a particular value of cloud cover are selected for analysis. Next, we apply image processing algorithms to test the presence of a hurricane eye in the segment. If the eye is found, the coordinate of the eye is recorded along with the time stamp of the segment. If the eye is not found, we examine adjacent segments for the existence of hurricane eye. It is probable that more than one hurricane eye could be found from different segments of the same period. Hence, the above process is repeated till the entire potential area for hurricane birth is exhausted. The subsequent/previous position of each hurricane eye will be searched in the appropriate adjacent segments of the next/previous period to mark the hurricane path. The temporal coherence and spatial coherence of the images are taken into account by our scheme in determining the segments and the associated periods required for analysis.
Parallel Shortest Lattice Vector Enumeration on Graphics Cards
of parallel computing systems. To illustrate the algorithm, it was implemented on graphics cards using CUDA, exhaustive search 1 Introduction Lattice-based cryptosystems are assumed to be secure against quantum com, especially to implementation aspects. In this paper we consider parallelization and special hardware
Adaptable Path Planning in Regionalized Environments
NASA Astrophysics Data System (ADS)
Richter, Kai-Florian
Human path planning relies on several more aspects than only geometric distance between two locations. These additional aspects mostly relate to the complexity of the traveled path. Accordingly, in recent years several cognitively motivated path search algorithms have been developed that try to minimize wayfinding complexity. However, the calculated paths may result in large detours as geometric properties of the network wayfinding occurs in are ignored. Simply adding distance as an additional factor to the cost function is a possible, but insufficient way of dealing with this problem. Instead, taking a global view on an environment by accounting for the heterogeneity of its structure allows for adapting the path search strategy. This heterogeneity can be used to regionalize the environment; each emerging region may require a different strategy for path planning. This paper presents such an approach to regionalized path planning. It argues for the advantages of the chosen approach, develops a measure for calculating wayfinding complexity that accounts for structural and functional aspects of wayfinding, and states a generic algorithm for regionalization. Finally, regionalized path planning is demonstrated in a sample scenario.
NASA Astrophysics Data System (ADS)
Todo, Synge
The loop algorithm for the world-line quantum Monte Carlo method on quantum lattice models is presented. After introducing the path integral representation that maps a quantum model to a classical one, we describe the continuous imaginary time limit, cluster algorithm, and the rejection free scheme, which are the major improvements on the quantum Monte Carlo technique during the last decades. By means of the loop algorithm, one can simulate various unfrustrated quantum lattice models of millions of sites at extremely low temperatures with absolute accuracy, being free from the critical and fine-mesh slowing down and the Suzuki-Trotter discretization error. We also discuss some technical aspects of the algorithm such as effective implementation and parallelization.
Route choices of transport bicyclists: a comparison of actually used and shortest routes
2014-01-01
Background Despite evidence that environmental features are related to physical activity, the association between the built environment and bicycling for transportation remains a poorly investigated subject. The aim of the study was to improve our understanding of the environmental determinants of bicycling as a means of transportation in urban European settings by comparing the spatial differences between the routes actually used by bicyclists and the shortest possible routes. Methods In the present study we examined differences in the currently used and the shortest possible bicycling routes, with respect to distance, type of street, and environmental characteristics, in the city of Graz, Austria. The objective measurement methods of a Global Positioning System (GPS) and a Geographic Information System (GIS) were used. Results Bicycling routes actually used were significantly longer than the shortest possible routes. Furthermore, the following attributes were also significantly different between the used route compared to the shortest possible route: Bicyclists often used bicycle lanes and pathways, flat and green areas, and they rarely used main roads and crossings. Conclusion The results of the study support our hypothesis that bicyclists prefer bicycle pathways and lanes instead of the shortest possible routes. This underlines the importance of a well-developed bicycling infrastructure in urban communities. PMID:24597725
Efficient Path Planning for Highly Articulated Robots using Adaptive Forward Dynamics
North Carolina at Chapel Hill, University of
Efficient Path Planning for Highly Articulated Robots using Adaptive Forward Dynamics Russell Gayle Carolina at Chapel Hill, U.S.A. 2 INRIA Rhone-Alpes, France We present an efficient path planning algorithm- tection and response computation algorithms for articulated models. Our plan- ner computes an initial path
Learning to improve path planning performance
Chen, Pang C.
1995-04-01
In robotics, path planning refers to finding a short. collision-free path from an initial robot configuration to a desired configuratioin. It has to be fast to support real-time task-level robot programming. Unfortunately, current planning techniques are still too slow to be effective, as they often require several minutes, if not hours of computation. To remedy this situation, we present and analyze a learning algorithm that uses past experience to increase future performance. The algorithm relies on an existing path planner to provide solutions to difficult tasks. From these solutions, an evolving sparse network of useful robot configurations is learned to support faster planning. More generally, the algorithm provides a speedup-learning framework in which a slow but capable planner may be improved both cost-wise and capability-wise by a faster but less capable planner coupled with experience. The basic algorithm is suitable for stationary environments, and can be extended to accommodate changing environments with on-demand experience repair and object-attached experience abstraction. To analyze the algorithm, we characterize the situations in which the adaptive planner is useful, provide quantitative bounds to predict its behavior, and confirm our theoretical results with experiments in path planning of manipulators. Our algorithm and analysis are sufficiently, general that they may also be applied to other planning domains in which experience is useful.
The prediction of radio-path characteristics
NASA Astrophysics Data System (ADS)
Gitina, G. M.; Kalinin, Iu. K.
The paper examines algorithms for the long-term prediction of radio-path characteristics in the ionosphere, the main characteristic being the MUF at a given distance. The proposed approach is based on long-term memories called DATA BANKS. Attention is given to the characteritics of the various banks, including the BANK OF CITIES, the BANK OF RADIO PATHS, the REFERENCE DATA BANK, and the OUTPUT DATA BANK.
Path planning on satellite images for unmanned surface vehicles
NASA Astrophysics Data System (ADS)
Yang, Joe-Ming; Tseng, Chien-Ming; Tseng, P. S.
2015-03-01
In recent years, the development of autonomous surface vehicles has been a field of increasing research interest. There are two major areas in this field: control theory and path planning. This study focuses on path planning, and two objectives are discussed: path planning for Unmanned Surface Vehicles (USVs) and implementation of path planning in a real map. In this paper, satellite thermal images are converted into binary images which are used as the maps for the Finite Angle A* algorithm (FAA*), an advanced A* algorithm that is used to determine safer and suboptimal paths for USVs. To plan a collision-free path, the algorithm proposed in this article considers the dimensions of surface vehicles. Furthermore, the turning ability of a surface vehicle is also considered, and a constraint condition is introduced to improve the quality of the path planning algorithm, which makes the traveled path smoother. This study also shows a path planning experiment performed on a real satellite thermal image, and the path planning results can be used by an USV.
Dimitris J. Kavvadias; Grammati E. Pantziou; Paul G. Spirakis; Christos D. Zaroliagis
1996-01-01
We show how to decompose efficiently in parallel any graph into a number, ~ fl, ofouterplanar subgraphs (called hammocks) satisfying certain separator properties. Ourwork combines and extends the sequential hammock decomposition technique introducedby Frederickson and the parallel ear decomposition technique, thus we call itthe hammock-on-ears decomposition. We mention that hammock-on-ears decompositionalso draws from techniques in computational geometry and that an
Kuperstein, Inna; Grieco, Luca; Cohen, David P A; Thieffry, Denis; Zinovyev, Andrei; Barillot, Emmanuel
2015-03-01
Several decades of molecular biology research have delivered a wealth of detailed descriptions of molecular interactions in normal and tumour cells. This knowledge has been functionally organised and assembled into dedicated biological pathway resources that serve as an invaluable tool, not only for structuring the information about molecular interactions but also for making it available for biological, clinical and computational studies. With the advent of high-throughput molecular profiling of tumours, close to complete molecular catalogues of mutations, gene expression and epigenetic modifications are available and require adequate interpretation. Taking into account the information about biological signalling machinery in cells may help to better interpret molecular profiles of tumours. Making sense out of these descriptions requires biological pathway resources for functional interpretation of the data. In this review, we describe the available biological pathway resources, their characteristics in terms of construction mode, focus, aims and paradigms of biological knowledge representation. We present a new resource that is focused on cancer-related signalling, the Atlas of Cancer Signalling Networks. We briefly discuss current approaches for data integration, visualisation and analysis, using biological networks, such as pathway scoring, guilt-by-association and network propagation. Finally, we illustrate with several examples the added value of data interpretation in the context of biological networks and demonstrate that it may help in analysis of high-throughput data like mutation, gene expression or small interfering RNA screening and can guide in patients stratification. Finally, we discuss perspectives for improving precision medicine using biological network resources and tools. Taking into account the information about biological signalling machinery in cells may help to better interpret molecular patterns of tumours and enable to put precision oncology into general clinical practice. PMID:25688112
Definition of average path and relativity parameter computation in CASA
NASA Astrophysics Data System (ADS)
Wu, Dawei; Huang, Yan; Chen, Xiaohua; Yu, Chang
2001-09-01
System CASA (computer-assisted semen analysis) is a medical applicable system which gets the sperm motility and its parameters using image processing method. But there is no any authoritative administration or academic organization gives a set of criterion for CASA now result in lowering the effective compare of work between the labs or researchers. The average path and parameters relative to it as average path velocity, amplitude of lateral head displacement and beat cross frequency are often unable to compare between systems because of different algorithm. The paper presents a new algorithm that could define the average path uniquely and compute those 3 parameters above quickly and handy from any real path.
An Energy Efficient Stable Election-Based Routing Algorithm for Wireless Sensor Networks
Wang, Jin; Zhang, Zhongqi; Xia, Feng; Yuan, Weiwei; Lee, Sungyoung
2013-01-01
Sensor nodes usually have limited energy supply and they are impractical to recharge. How to balance traffic load in sensors in order to increase network lifetime is a very challenging research issue. Many clustering algorithms have been proposed recently for wireless sensor networks (WSNs). However, sensor networks with one fixed sink node often suffer from a hot spots problem since nodes near sinks have more traffic burden to forward during a multi-hop transmission process. The use of mobile sinks has been shown to be an effective technique to enhance network performance features such as latency, energy efficiency, network lifetime, etc. In this paper, a modified Stable Election Protocol (SEP), which employs a mobile sink, has been proposed for WSNs with non-uniform node distribution. The decision of selecting cluster heads by the sink is based on the minimization of the associated additional energy and residual energy at each node. Besides, the cluster head selects the shortest path to reach the sink between the direct approach and the indirect approach with the use of the nearest cluster head. Simulation results demonstrate that our algorithm has better performance than traditional routing algorithms, such as LEACH and SEP. PMID:24284767
Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms
Rao, N.S.V. [Oak Ridge National Lab., TN (US); Kareti, S.; Shi, Weimin [Old Dominion Univ., Norfolk, VA (US). Dept. of Computer Science; Iyengar, S.S. [Louisiana State Univ., Baton Rouge, LA (US). Dept. of Computer Science
1993-07-01
A formal framework for navigating a robot in a geometric terrain by an unknown set of obstacles is considered. Here the terrain model is not a priori known, but the robot is equipped with a sensor system (vision or touch) employed for the purpose of navigation. The focus is restricted to the non-heuristic algorithms which can be theoretically shown to be correct within a given framework of models for the robot, terrain and sensor system. These formulations, although abstract and simplified compared to real-life scenarios, provide foundations for practical systems by highlighting the underlying critical issues. First, the authors consider the algorithms that are shown to navigate correctly without much consideration given to the performance parameters such as distance traversed, etc. Second, they consider non-heuristic algorithms that guarantee bounds on the distance traversed or the ratio of the distance traversed to the shortest path length (computed if the terrain model is known). Then they consider the navigation of robots with very limited computational capabilities such as finite automata, etc.
Characterization of spatial channel model based on ray path analysis in high-rise urban environment
Do-Young Kwak; Nogyoung Kang; Jaewon Lee; Seong-Cheol Kim; Joonsoo Choi
2003-01-01
The strongest ray analysis based on the computer simulation of wave propagation between a base station(BS) and mobile stations(MSs) is carried out to obtain the spatial-time wideband channel characteristics. The strongest rays are responsible for about 70% of the total received power for BS-MS pairs on the average and their arrival angles rarely deviate from the shortest path lines between
Path optimization for oil probe
NASA Astrophysics Data System (ADS)
Smith, O'Neil; Rahmes, Mark; Blue, Mark; Peter, Adrian
2014-05-01
We discuss a robust method for optimal oil probe path planning inspired by medical imaging. Horizontal wells require three-dimensional steering made possible by the rotary steerable capabilities of the system, which allows the hole to intersect multiple target shale gas zones. Horizontal "legs" can be over a mile long; the longer the exposure length, the more oil and natural gas is drained and the faster it can flow. More oil and natural gas can be produced with fewer wells and less surface disturbance. Horizontal drilling can help producers tap oil and natural gas deposits under surface areas where a vertical well cannot be drilled, such as under developed or environmentally sensitive areas. Drilling creates well paths which have multiple twists and turns to try to hit multiple accumulations from a single well location. Our algorithm can be used to augment current state of the art methods. Our goal is to obtain a 3D path with nodes describing the optimal route to the destination. This algorithm works with BIG data and saves cost in planning for probe insertion. Our solution may be able to help increase the energy extracted vs. input energy.
Jacob Benesty; Steven L. Gay
2002-01-01
Recently, the proportionate normalized least mean square (PNLMS) algorithm was developed for use in network echo cancelers. In comparison to the normalized least mean square (NLMS) algorithm, PNLMS has very fast initial convergence and tracking when the echo path is sparse. Unfortunately, when the impulse response is dispersive, the PNLMS converges much slower than NLMS. This implies that the rule
Path Planning Algorithms for Multiple Heterogeneous Vehicles
Oberlin, Paul V.
2010-01-16
as the \\Precedence Constrained Asymmetric Travelling Salesman Problem" (PCATSP). v ACKNOWLEDGMENTS Special thanks to the Air Force Research Laboratory (AFRL) Air Vehicles Direc- torate for providing funding and motivation for portions of this thesis, Waqar Malik...
Raghvendra V. Cowlagi; Panagiotis Tsiotras
2010-01-01
A multi-resolution path planning algorithm based on the wavelet transform of the environment has been reported previously in the literature. In this paper, we provide a proof of completeness of this algorithm. In addition, we present an implementation of this algorithm that reuses information obtained in previous iterations to perform subsequent iterations more efficiently. Finally, we extend this path planning
Adaptive path planning for flexible manufacturing
Chen, Pang C.
1994-08-01
Path planning needs to be fast to facilitate real-time robot programming. Unfortunately, current planning techniques are still too slow to be effective, as they often require several minutes, if not hours of computation. To overcome this difficulty, we present an adaptive algorithm that uses past experience to speed up future performance. It is a learning algorithm suitable for automating flexible manufacturing in incrementally-changing environments. The algorithm allows the robot to adapt to its environment by having two experience manipulation schemes: For minor environmental change, we use an object-attached experience abstraction scheme to increase the flexibility of the learned experience; for major environmental change, we use an on-demand experience repair scheme to retain those experiences that remain valid and useful. Using this algorithm, we can effectively reduce the overall robot planning time by re-using the computation result for one task to plan a path for another.
Show me the (shortest) way to go home Foams, soap films and minimization
Cox, Simon
Simon Cox Show me the (shortest) way to go home Foams, soap films and minimization #12;The force two possible (non-trivial) soap film combinations that touch all edges: Wire Frames foams not be straight. Wire Frames foams@aber.ac.uk #12;Soap films solve the Steiner problem: Given n cities on a plain
DISCUSS: Critical Path Analysis
NSDL National Science Digital Library
Baker, Barrie
This module, by Barrie Baker and Neville Hunt of Coventry University, introduces critical path analysis and addresses the following topics: Networks, Critical paths, Floats, Activity-on-node (AON) networks. Excel spreadsheets are used to provide examples and exercises.
Traveling salesman path problems
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 ...
Multiobjective Evolutionary Path Planning via Sugeno-Based Tournament Selection
NASA Technical Reports Server (NTRS)
Dozier, Gerry; McCullough, Shaun; Homaifar, Abdollah; Esterline, Albert
1998-01-01
This paper introduces a new tournament selection algorithm that can be used for evolutionary path planning systems. The fuzzy (Sugeno) tournament selection algorithm (STSA) described in this paper selects candidate paths (CPs) to be parents and undergo reproduction based on: (1) path feasibility, (2) the euclidean distance of a path from the origin to its destination, and (3) the average change in the slope of a path. In this paper, we provide a detailed description of the fuzzy inference system used in the STSA as well as some examples of its usefulness. We then use 12 instances of our STSA to rank a population of CPs based on the above criteria. We also show how the STSA can obviate the need for the development of an explicit (lexicographic multiobjective) evaluation function and use it to develop multiobjective motion paths.
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.
Staff detection with stable paths.
Dos Santos Cardoso, Jaime; Capela, Artur; Rebelo, Ana; Guedes, Carlos; Pinto da Costa, Joaquim
2009-06-01
The preservation of musical works produced in the past requires their digitalization and transformation into a machine-readable format. The processing of handwritten musical scores by computers remains far from ideal. One of the fundamental stages to carry out this task is the staff line detection. We investigate a general-purpose, knowledge-free method for the automatic detection of music staff lines based on a stable path approach. Lines affected by curvature, discontinuities, and inclination are robustly detected. Experimental results show that the proposed technique consistently outperforms well-established algorithms. PMID:19372615
Efficient Data Mining for Path Traversal Patterns
Ming-syan Chen; Jong Soo Park; Philip S. Yu
1998-01-01
In this paper, we explore a new data mining capability that involves mining path traversal patterns in a distributed information-providing environment where documents or objects are linked together to facilitate interactive access. Our solution procedure consists of two steps. First, we derive an algorithm to convert the original sequence of log data into a set of maximal forward references. By
Particle RRT for Path Planning with Uncertainty
Nik A. Melchior; Reid G. Simmons
2007-01-01
This paper describes a new extension to the Rapidly-exploring Random Tree (RRT) path planning algo- rithm. The Particle RRT algorithm explicitly considers uncer- tainty in its domain, similar to the operation of a particle filter. Each extension to the search tree is treated as a stochastic process and is simulated multiple times. The behavior of the robot can be characterized
Asymptotically optimal path planning and surface reconstruction for inspection
Papadopoulos, Georgios
2014-01-01
Motivated by inspection applications for marine structures, this thesis develops algorithms to enable their autonomous inspection. Two essential parts of the inspection problem are (1) path planning and (2) surface ...
Path dependent receding horizon control policies for hybrid electric vehicles
Kolmanovsky, Ilya V.
Future hybrid electric vehicles (HEVs) may use path-dependent operating policies to improve fuel economy. In our previous work, we developed a dynamic programming (DP) algorithm for prescribing the battery state of charge ...
Passivity-based designs for synchronized path-following
Ivar-andré F. Ihle; Murat Arcak; Thor I. Fossen
2007-01-01
We consider a formation control system where individual systems are controlled by a path-following design and the path variables are to be synchronized. We first show a passivity property for the path-following system, and next, combine this with a passivity-based synchronization algorithm developed in Arcak [2007. Passivity as a design tool for group coordination. IEEE Transactions on Automatic Control, in
Walden's Paths - Ensemble Edition
NSDL National Science Digital Library
2011-01-04
Walden?s Paths enables users of digital document collections (e.g. the Web) to exploit these documents by reusing them for previously unintended audiences in an academic setting. Authors of paths (usually educators) overlay a linear, directed meta-structure over the Web documents and recontextualize these by adding explanatory text to achieve their curricular goals. Paths do not modifythe structure or content of the Web resources that they include. The creation of a path over pre-organized content (e.g. books, Web pages) to reorganize and associate related information serves to facilitate easy retrieval and communication. Walden?s Paths displays the information that the path points to in conjunction with the textual annotations added by the author of the path.
Path Covering Problems and Testing of Printed Circuits
Giovanni Andreatta; Francesco Mason
1995-01-01
This work deals with a problem, arising in the context of printed circuit testing, that will be formulated as a path covering problem on trees. For this problem, which consists in minimizing the number of continuity testing, an exact algorithm of linear complexity is here proposed for the first time. A general classification of path covering problems is also presented
Car-like robot path following in large unstructured environments
Shahram Rezaei; Jose Guivant; Eduardo M. Nebot
2003-01-01
This paper addresses the problem of on-line path following for a car working in unstructured outdoor environments. The partially known map of the environment is updated and expanded in real time by a Simultaneous Localization and Mapping (SLAM) algorithm. This information is used to implement global path planning. A cost graph is initially constructed followed by a search to find
The Loss Path Multiplicity Problem in Multicast Congestion Control
Supratik Bhattacharyya; Donald F. Towsley; James F. Kurose
1999-01-01
An important concern for source-based multicast congestion control algorithms is the loss path multiplicity (LPM) problem that arises because a transmitted packet can be lost on one or more of the many end-to- end paths in a multicast tree. Consequently, if a multicast source's trans- mission rate is regulated according to loss indications from receivers, the rate may be completely
REGULAR ARTICLE Coordinate reduction for exploring chemical reaction paths
Schlegel, H. Bernhard
improve the efficiency of reaction path optimization algorithms. Keywords Reaction path Ã PCA Ã Potential- ecule as a function of its geometrical parameters [1]. The potential energy surface representing The potential energy surface for the reaction of a typical molecular system composed of N atoms is defined
Real time path planning for UAV based on Focused D
Yingchun Chen; Ye Zhao; Huakui Wang
2011-01-01
With its long endurance, high safety and low signature, an Unmanned Aerial Vehicle (UAV) plays a great part in intelligence collection, surveillance, reconnaissance, patrol, and target acquisition. Path planning is of significant interest for the autonomous navigation of UAV. A three-dimensional path-planning algorithm based on Focused Dynamic A? algorithm is presented for UAV under three-dimensional dynamic environments. The problem is
Fast, precise flattening of cubic Bézier path and offset curves
Thomas F. Hain; Athar L. Ahmad; Sri Venkat R. Racherla; David D. Langan
2005-01-01
Abstract We present two,related algorithms,for flattening (generating polyline approximations,for) curves associated with planar cubic Be´ zier segments. One flattens the path curve, and the other flattens the left and right offset curves. The algorithm for flattening path curves yields an average of 67% of the vertices generated by recursive subdivision, while maintaining flatness to within 4% of the specified value,
Path-consistency: When space misses time
Chmeiss, A.; Jegou, P. [Universite de Provence, Marseille (France)
1996-12-31
Within the framework of constraint programming, particulary concerning the Constraint Satisfaction Problems (CSPs), the techniques of preprocessing based on filtering algorithms were shown to be very important for the search phase. In particular, two filtering methods have been studied, these methods exploit two properties of local consistency: arc- and path-consistency. Concerning the arc-consistency methods, there is a linear time algorithm (in the size of the problem) which is efficient in practice. But the limitations of the arc-consistency algorithms requires often filtering methods with higher order like path-consistency filterings. The best path-consistency algorithm proposed is PC-6, a natural generalization of AC-6 to path-consistency. Its time complexity is O(n{sup 3}d{sup 4}) and its space complexity is O(n{sup 3}d{sup 4}), where n is the number of variables and d is the size of domains. We have remarked that PC-6, though it is widely better than PC-4, was not very efficient in practice, specially for those classes of problems that require an important space to be run. Therefore, we propose here a new path-consistency algorithm called PC-7, its space complexity is O(n{sup 3}d{sup 4}) but its time complexity is O(n{sup 3}d{sup 4}) i.e. worse than that of PC-6. However, the simplicity of PC-7 as well as the data structures used for its implementation offer really a higher performance than PC-6. Furthermore, it turns out that when the size of domains is a constant of the problems, the time complexity of PC-7 becomes. like PC-6, optimal i.e. O(n{sup 3}).
Vulnerability of complex networks under path-based attacks
NASA Astrophysics Data System (ADS)
Pu, Cun-Lai; Cui, Wei
2015-02-01
We investigate vulnerability of complex networks including model networks and real-world networks subject to path-based attacks. Specifically, we remove approximately the longest simple path from a network iteratively until there are no paths left in the network. We propose two algorithms, the random augmenting approach (RPA) and the Hamilton-path based approach (HPA), for finding the approximately longest simple path in a network. Results demonstrate that steps of longest-path attacks increase with network density linearly for random networks, while exponentially increasing for scale-free networks. The more homogeneous the degree distribution is, the more fragile the network, which is different from the previous results of node or edge attacks. HPA is generally more efficient than RPA in the longest-path attacks of complex networks. These findings further help us understand the vulnerability of complex systems, better protect complex systems, and design more tolerant complex systems.
A weighted coding in a genetic algorithm for the degree-constrained minimum spanning tree problem
Günther R. Raidl; Bryant A. Julstrom
2000-01-01
The coding by which chromosomes represent candidate solu- tions is a fundamental design choice in a genetic algorithm. This paper describes a novel coding of spanning trees in a genetic algorithm for the degree-constrained minimum span- ning tree problem. For a connected, weighted graph, this problem seeks to identify the shortest spanning tree whose degree does not exceed an upper
Yi-Ju Ho; Jing-Sin Liu
2009-01-01
In this paper, we present an obstacle avoiding smooth path planning method based on Voronoi diagram and composite Bezier curve algorithm which obtains the curvature bounded path with small length. In our algorithm, a Voronoi diagram is constructed according to the global environment. The piecewise linear rough path in the Voronoi diagram which keeps away from the obstacles is obtained
A new MLC segmentation algorithm/software for step-and-shoot IMRT delivery.
Luan, Shuang; Wang, Chao; Chen, Danny Z; Hu, Xiaobo S; Naqvi, Shahid A; Yu, Cedric X; Lee, Chad L
2004-04-01
We present a new MLC segmentation algorithm/software for step-and-shoot IMRT delivery. Our aim in this work is to shorten the treatment time by minimizing the number of segments. Our new segmentation algorithm, called SLS (an abbreviation for static leaf sequencing), is based on graph algorithmic techniques in computer science. It takes advantage of the geometry of intensity maps. In our SLS approach, intensity maps are viewed as three-dimensional (3-D) "mountains" made of unit-sized "cubes." Such a 3-D "mountain" is first partitioned into special-structured submountains using a new mixed partitioning scheme. Then the optimal leaf sequences for each submountain are computed by either a shortest-path algorithm or a maximum-flow algorithm based on graph models. The computations of SLS take only a few minutes. Our comparison studies of SLS with CORVUS (both the 4.0 and 5.0 versions) and with the Xia and Verhey segmentation methods on Elekta Linac systems showed substantial improvements. For instance, for a pancreatic case, SLS used only one-fifth of the number of segments required by CORVUS 4.0 to create the same intensity maps, and the SLS sequences took only 25 min to deliver on an Elekta SL 20 Linac system in contrast to the 72 min for the CORVUS 4.0 sequences (a three-fold improvement). To verify the accuracy of our new leaf sequences, we conducted film and ion-chamber measurements on phantom. The results showed that both the intensity distributions as well as dose distributions of the SLS delivery match well with those of CORVUS delivery. SLS can also be extended to other types of Linac systems. PMID:15124986
A new infeasible interior-point algorithm for linear programming
Miguel Argáez; Leticia Velázquez
2003-01-01
In this paper we present an infeasible path-following interior-point algorithm for solving linear programs using a relaxed notion of the central path, called quasicentral path, as a central region. The algorithm starts from an infeasible point which satisfies that the norm of the dual condition is less than the norm of the primal condition. We use weighted sets as proximity
Time-optimal path generation for continuous and quasi-continuous path control of industrial robots
I. Troch
1989-01-01
For a given continuous path, the problem of designing a time-optimal time-parametrization is considered. First, algorithms are presented which, under rather mild assumptions, yield the exact solution within two computational steps consisting of a forward and a backward computation. Then, the problem of quasi-continuous robot motion is investigated in detail. An algorithm of the same type results, but the computational
Variational nature, integration, and properties of Newton reaction path.
Bofill, Josep Maria; Quapp, Wolfgang
2011-02-21
The distinguished coordinate path and the reduced gradient following path or its equivalent formulation, the Newton trajectory, are analyzed and unified using the theory of calculus of variations. It is shown that their minimum character is related to the fact that the curve is located in a valley region. In this case, we say that the Newton trajectory is a reaction path with the category of minimum energy path. In addition to these findings a Runge-Kutta-Fehlberg algorithm to integrate these curves is also proposed. PMID:21341822
Path Factorization Approach to Stochastic Simulations
NASA Astrophysics Data System (ADS)
Athènes, Manuel; Bulatov, Vasily V.
2014-12-01
The computational efficiency of stochastic simulation algorithms is notoriously limited by the kinetic trapping of the simulated trajectories within low energy basins. Here we present a new method that overcomes kinetic trapping while still preserving exact statistics of escape paths from the trapping basins. The method is based on path factorization of the evolution operator and requires no prior knowledge of the underlying energy landscape. The efficiency of the new method is demonstrated in simulations of anomalous diffusion and phase separation in a binary alloy, two stochastic models presenting severe kinetic trapping.
Algorithms and Algorithmic Languages.
ERIC Educational Resources Information Center
Veselov, V. M.; Koprov, V. M.
This paper is intended as an introduction to a number of problems connected with the description of algorithms and algorithmic languages, particularly the syntaxes and semantics of algorithmic languages. The terms "letter, word, alphabet" are defined and described. The concept of the algorithm is defined and the relation between the algorithm and…
PathFinder: a negotiation-based performance-driven router for FPGAs
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
New potential functions for multi robot path planning : SWARM or SPREAD
Sung-hwan Kim; Gyungtae Lee; Inpyo Hong; Young-Joo Kim; Daeyoung Kim
2010-01-01
Artificial Potential Field (APF) is widely used for an autonomous robot path planning and navigation because of light complexity and elegance of results. Although it is useful in single robot path planning, appropriate algorithm for multi-robot path planning has not been proposed. Existing APFs which can apply to multi-robot only regard robots as obstacles even if these robots are not
Advanced Physics: Path Integral
NSDL National Science Digital Library
Wolfgang Christian
A cursor is shown in an x-y graph. The cursor can be dragged around the graph and its path is marked as it is moved. The data are sent to a DataTable which shows x, y, and the value of the path integral, F.dl.
NSDL National Science Digital Library
Australian National University
This site features an interactive applet that models the Sun's path from a geocentric view. It calculates and visualizes the position of the Sun based on latitude and time, and allows students to simulate the Sun's position and path for an hour, a day, a month or a year.
Path Planning for UAV in Radar Network Area
Fu Xiao-wei; Liu Zhong; Gao Xiao-guang
2010-01-01
This paper mainly introduces a path planning algorithm for the unmanned aerial vehicles (UAVs) to avoid radar network. The radar network contains several radars which have different detection ranges. In this algorithm, firstly, according to the theory of the Delaunay triangulations, a directed graph is constructed based on the locations and the detection ranges of the radars. Secondly, the Dijkstra
Dynamic path planning in sensor-based terrain acquisition
V. J. Lumelsky; S. Mukhopadhyay; K. Sun
1990-01-01
The terrain acquisition problem is formulated as that of continuous motion planning, and no constraints are imposed on obstacle geometry. Two algorithms are described for acquiring planar terrains with obstacles of arbitrary shape. Estimates of the algorithm performance are derived as upper bounds on the lengths of generated paths
Path-Independent Load Balancing With Unreliable Machines James Aspnes
Aspnes, James
Path-Independent Load Balancing With Unreliable Machines James Aspnes Yang Richard Yang Yitong YinÂ§ Abstract We consider algorithms for load balancing on unreliable ma- chines. The objective is to optimize-independent load-balancing algorithms, giving the measure of makespan and the normalized measure of reassignments
Enzymatic reaction paths as determined by transition path sampling
NASA Astrophysics Data System (ADS)
Masterson, Jean Emily
Enzymes are biological catalysts capable of enhancing the rates of chemical reactions by many orders of magnitude as compared to solution chemistry. Since the catalytic power of enzymes routinely exceeds that of the best artificial catalysts available, there is much interest in understanding the complete nature of chemical barrier crossing in enzymatic reactions. Two specific questions pertaining to the source of enzymatic rate enhancements are investigated in this work. The first is the issue of how fast protein motions of an enzyme contribute to chemical barrier crossing. Our group has previously identified sub-picosecond protein motions, termed promoting vibrations (PVs), that dynamically modulate chemical transformation in several enzymes. In the case of human heart lactate dehydrogenase (hhLDH), prior studies have shown that a specific axis of residues undergoes a compressional fluctuation towards the active site, decreasing a hydride and a proton donor--acceptor distance on a sub-picosecond timescale to promote particle transfer. To more thoroughly understand the contribution of this dynamic motion to the enzymatic reaction coordinate of hhLDH, we conducted transition path sampling (TPS) using four versions of the enzymatic system: a wild type enzyme with natural isotopic abundance; a heavy enzyme where all the carbons, nitrogens, and non-exchangeable hydrogens were replaced with heavy isotopes; and two versions of the enzyme with mutations in the axis of PV residues. We generated four separate ensembles of reaction paths and analyzed each in terms of the reaction mechanism, time of barrier crossing, dynamics of the PV, and residues involved in the enzymatic reaction coordinate. We found that heavy isotopic substitution of hhLDH altered the sub-picosecond dynamics of the PV, changed the favored reaction mechanism, dramatically increased the time of barrier crossing, but did not have an effect on the specific residues involved in the PV. In the mutant systems, we observed changes in the reaction mechanism and altered contributions of the mutated residues to the enzymatic reaction coordinate, but we did not detect a substantial change in the time of barrier crossing. These results confirm the importance of maintaining the dynamics and structural scaffolding of the hhLDH PV in order to facilitate facile barrier passage. We also utilized TPS to investigate the possible role of fast protein dynamics in the enzymatic reaction coordinate of human dihydrofolate reductase (hsDHFR). We found that sub-picosecond dynamics of hsDHFR do contribute to the reaction coordinate, whereas this is not the case in the E. coli version of the enzyme. This result indicates a shift in the DHFR family to a more dynamic version of catalysis. The second inquiry we addressed in this thesis regarding enzymatic barrier passage concerns the variability of paths through reactive phase space for a given enzymatic reaction. We further investigated the hhLDH-catalyzed reaction using a high-perturbation TPS algorithm. Though we saw that alternate reaction paths were possible, the dominant reaction path we observed corresponded to that previously elucidated in prior hhLDH TPS studies. Since the additional reaction paths we observed were likely high-energy, these results indicate that only the dominant reaction path contributes significantly to the overall reaction rate. In conclusion, we show that the enzymes hhLDH and hsDHFR exhibit paths through reactive phase space where fast protein motions are involved in the enzymatic reaction coordinate and exhibit a non-negligible contribution to chemical barrier crossing.
Multigrid solution of a path integral formulation for the hydrogen atom
Dov Bai
2004-05-18
An efficient multigrid Monte-Carlo algorithm for calculating the ground state of the hydrogen atom using path integral is presented. The algorithm uses a unigrid approach. The action integral near r=0 is modified so that the correct values of observables are obtained. It is demonstrated that the critical slow down (CSD) is eliminated. Finally, the algorithm is compared to the staging algorithm.
Michael Grunwald Transition path sampling
Gruenwald, Michael
Michael Gr¨unwald Transition path sampling simulations of structural phase transformations compromises the comparability of simulation and experiment considerably. Here, we use transition path sam of parallel crystal planes. We subject the pathways obtained with transition path sam- pling
Real-time generation and control of cutter path for 5-axis CNC machining
Chih-Ching Lo
1999-01-01
This paper presents a new approach to real-time generation and control of the cutter path for 5-axis machining applications. The cutter path generation method comprises real-time algorithms for cutter-contact path interpolation, cutter offsetting, and coordinate conversion. In addition, a global feedback loop is closed by the CNC interpolator so as to augment the controlled accuracy in practical cutter path generation.
Longest jobs first algorithm in solving job shop scheduling using adaptive genetic algorithm (GA)
NASA Astrophysics Data System (ADS)
Alizadeh Sahzabi, Vahid; Karimi, Iman; Alizadeh Sahzabi, Navid; Mamaani Barnaghi, Peiman
2012-01-01
In this paper, genetic algorithm was used to solve job shop scheduling problems. One example discussed in JSSP (Job Shop Scheduling Problem) and I described how we can solve such these problems by genetic algorithm. The goal in JSSP is to gain the shortest process time. Furthermore I proposed a method to obtain best performance on performing all jobs in shortest time. The method mainly, is according to Genetic algorithm (GA) and crossing over between parents always follows the rule which the longest process is at the first in the job queue. In the other word chromosomes is suggested to sorts based on the longest processes to shortest i.e. "longest job first" says firstly look which machine contains most processing time during its performing all its jobs and that is the bottleneck. Secondly, start sort those jobs which are belonging to that specific machine descending. Based on the achieved results," longest jobs first" is the optimized status in job shop scheduling problems. In our results the accuracy would grow up to 94.7% for total processing time and the method improved 4% the accuracy of performing all jobs in the presented example.
Longest jobs first algorithm in solving job shop scheduling using adaptive genetic algorithm (GA)
NASA Astrophysics Data System (ADS)
Alizadeh Sahzabi, Vahid; Karimi, Iman; Alizadeh Sahzabi, Navid; Mamaani Barnaghi, Peiman
2011-12-01
In this paper, genetic algorithm was used to solve job shop scheduling problems. One example discussed in JSSP (Job Shop Scheduling Problem) and I described how we can solve such these problems by genetic algorithm. The goal in JSSP is to gain the shortest process time. Furthermore I proposed a method to obtain best performance on performing all jobs in shortest time. The method mainly, is according to Genetic algorithm (GA) and crossing over between parents always follows the rule which the longest process is at the first in the job queue. In the other word chromosomes is suggested to sorts based on the longest processes to shortest i.e. "longest job first" says firstly look which machine contains most processing time during its performing all its jobs and that is the bottleneck. Secondly, start sort those jobs which are belonging to that specific machine descending. Based on the achieved results," longest jobs first" is the optimized status in job shop scheduling problems. In our results the accuracy would grow up to 94.7% for total processing time and the method improved 4% the accuracy of performing all jobs in the presented example.
Tortuous path chemical preconcentrator
Manginell, Ronald P. (Albuquerque, NM); Lewis, Patrick R. (Albuquerque, NM); Adkins, Douglas R. (Albuquerque, NM); Wheeler, David R. (Albuquerque, NM); Simonson, Robert J. (Cedar Crest, NM)
2010-09-21
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.
ERIC Educational Resources Information Center
Stegemoller, William; Stegemoller, Rebecca
2004-01-01
The path taken and the turns made as a turtle traces a polygon are examined to discover an important theorem in geometry. A unique tool, the Angle Adder, is implemented in the investigation. (Contains 9 figures.)
NSDL National Science Digital Library
PathFinder Science contains research projects about water conservation, tardigrades, a winter bird survey, ozone, ultraviolet light and DNA, global warming, spot removal, lichens, stream monitoring, amphibian biomonitoring, and particulate monitoring. Free registration to the PathFinder Science Network offers the opportunity to be a part of the listserv, upload collaborative project data or publish research work. There are tools and tips to help students publish their research on the web.
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.
The lawnmower problem and other geometric path covering problems
Fekete, S.; Arkin, E.; Mitchell, J.
1994-12-31
We discuss the Lawnmower Problem: Given a polygonal region, find the shortest closed path along which we have to move a given object (typically a square or a circle), such that any point of the region will be covered by the object for some position of it movement. In another version of the problem, known as the Milling Problem, the object has to stay within the region at all times. Practical motivations for considering the Lawnmower Problem come from manufacturing (spray painting, quality control), geography (aerial surveys), optimization (tour planning for a large number of clients with limited mobility), and gardening. The Milling Problem has gained attention by its importance for NC pocket machining. We show that both problems are NP-hard and discuss approximation methods for various versions of the problem.
NASA Astrophysics Data System (ADS)
Li, Qingquan; Zeng, Zhe; Zhang, Tong; Li, Jonathan; Wu, Zhongheng
2011-02-01
Optimal paths computed by conventional path-planning algorithms are usually not "optimal" since realistic traffic information and local road network characteristics are not considered. We present a new experiential approach that computes optimal paths based on the experience of taxi drivers by mining a huge number of floating car trajectories. The approach consists of three steps. First, routes are recovered from original taxi trajectories. Second, an experiential road hierarchy is constructed using travel frequency and speed information for road segments. Third, experiential optimal paths are planned based on the experiential road hierarchy. Compared with conventional path-planning methods, the proposed method provides better experiential optimal path identification. Experiments demonstrate that the travel time is less for these experiential paths than for paths planned by conventional methods. Results obtained for a case study in the city of Wuhan, China, demonstrate that experiential optimal paths can be flexibly obtained in different time intervals, particularly during peak hours.
NASA Astrophysics Data System (ADS)
Matvienko, G. G.; Oshlakov, V. K.; Stepanov, A. N.; Sukhanov, A. Ya
2015-02-01
We consider the algorithms that implement a broadband ('multiwave') radiative transfer with allowance for multiple (aerosol) scattering and absorption by main atmospheric gases. In the spectral range of 0.6 – 1 ?m, a closed numerical simulation of modifications of the supercontinuum component of a probing femtosecond pulse is performed. In the framework of the algorithms for solving the inverse atmospheric-optics problems with the help of a genetic algorithm, we give an interpretation of the experimental backscattered spectrum of the supercontinuum. An adequate reconstruction of the distribution mode for the particles of artificial aerosol with the narrow-modal distributions in a size range of 0.5 – 2 mm and a step of 0.5 mm is obtained.
Some Materials for Discrete Mathematics
NSDL National Science Digital Library
Lady, E. Lee
Files in PDF, DVI, and Postscript format. Contents include: an algorithm for solving linear Diophantine equations, the Chinese remainder theorem, mathematical induction and recursive algorithms, Change of base to Cantor representation, Dijkstra's algorithm for shortest path, and amortization.
Adaptive robot path planning in changing environments
Chen, P.C.
1994-08-01
Path planning needs to be fast to facilitate real-time robot programming. Unfortunately, current planning techniques are still too slow to be effective, as they often require several minutes, if not hours of computation. To overcome this difficulty, we present an adaptive algorithm that uses past experience to speed up future performance. It is a learning algorithm suitable for incrementally-changing environments such as those encountered in manufacturing of evolving products and waste-site remediation. The algorithm allows the robot to adapt to its environment by having two experience manipulation schemes: For minor environmental change, we use an object-attached experience abstraction scheme to increase the flexibility of the learned experience; for major environmental change, we use an on-demand experience repair scheme to retain those experiences that remain valid and useful. Using this algorithm, we can effectively reduce the overall robot planning time by re-using the computation result for one task to plan a path for another.
Algorithms for effective querying of compound graph-based pathway databases
2009-01-01
Background Graph-based pathway ontologies and databases are widely used to represent data about cellular processes. This representation makes it possible to programmatically integrate cellular networks and to investigate them using the well-understood concepts of graph theory in order to predict their structural and dynamic properties. An extension of this graph representation, namely hierarchically structured or compound graphs, in which a member of a biological network may recursively contain a sub-network of a somehow logically similar group of biological objects, provides many additional benefits for analysis of biological pathways, including reduction of complexity by decomposition into distinct components or modules. In this regard, it is essential to effectively query such integrated large compound networks to extract the sub-networks of interest with the help of efficient algorithms and software tools. Results Towards this goal, we developed a querying framework, along with a number of graph-theoretic algorithms from simple neighborhood queries to shortest paths to feedback loops, that is applicable to all sorts of graph-based pathway databases, from PPIs (protein-protein interactions) to metabolic and signaling pathways. The framework is unique in that it can account for compound or nested structures and ubiquitous entities present in the pathway data. In addition, the queries may be related to each other through "AND" and "OR" operators, and can be recursively organized into a tree, in which the result of one query might be a source and/or target for another, to form more complex queries. The algorithms were implemented within the querying component of a new version of the software tool PATIKAweb (Pathway Analysis Tool for Integration and Knowledge Acquisition) and have proven useful for answering a number of biologically significant questions for large graph-based pathway databases. Conclusion The PATIKA Project Web site is http://www.patika.org. PATIKAweb version 2.1 is available at http://web.patika.org. PMID:19917102
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.
Scalable network distance browsing in spatial databases
Hanan Samet; Jagan Sankaranarayanan; Houman Alborzi
2008-01-01
An algorithm is presented for nding the k nearest neighbors in a spatial network in a best-rst manner using network distance. The algorithm is based on precomputing the shortest paths between all possible vertices in the network and then making use of an encod- ing that takes advantage of the fact that the shortest paths from vertex u to all
Automatic tool path generation for finish machining
Kwok, Kwan S.; Loucks, C.S.; Driessen, B.J.
1997-03-01
A system for automatic tool path generation was developed at Sandia National Laboratories for finish machining operations. The system consists of a commercially available 5-axis milling machine controlled by Sandia developed software. This system was used to remove overspray on cast turbine blades. A laser-based, structured-light sensor, mounted on a tool holder, is used to collect 3D data points around the surface of the turbine blade. Using the digitized model of the blade, a tool path is generated which will drive a 0.375 inch diameter CBN grinding pin around the tip of the blade. A fuzzified digital filter was developed to properly eliminate false sensor readings caused by burrs, holes and overspray. The digital filter was found to successfully generate the correct tool path for a blade with intentionally scanned holes and defects. The fuzzified filter improved the computation efficiency by a factor of 25. For application to general parts, an adaptive scanning algorithm was developed and presented with simulation results. A right pyramid and an ellipsoid were scanned successfully with the adaptive algorithm.
An efficient evolutionary algorithm for the degree-constrained minimum spanning tree problem
G. R. Raidl
2000-01-01
The representation of candidate solutions and the variation operators are fundamental design choices in an evolutionary algorithm (EA). This paper proposes a novel representation technique and suitable variation operators for the degree-constrained minimum spanning tree problem. For a weighted, undirected graph G(V, E), this problem seeks to identify the shortest spanning tree whose node degrees do not exceed an upper
NASA Technical Reports Server (NTRS)
Bill, R. C.; Johnson, R. D. (inventors)
1979-01-01
A gas path seal suitable for use with a turbine engine or compressor is described. A shroud wearable or abradable by the abrasion of the rotor blades of the turbine or compressor shrouds the rotor bades. A compliant backing surrounds the shroud. The backing is a yieldingly deformable porous material covered with a thin ductile layer. A mounting fixture surrounds the backing.
DNA Computing Hamiltonian path
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
ERIC Educational Resources Information Center
Grimm, Karen
1999-01-01
Describes "Off the Beaten Path", a program that takes at-risk students out of the traditional classroom and puts them into a camping atmosphere in order to increase academic achievement, improve self-esteem, and promote better social skills. (WRM)
Edith Elkind; Amit Sahai; Kenneth Steiglitz
2004-01-01
We consider the problem of picking (buying) an inexpensive s -- t path in a graph where edges are owned by independent (selfish) agents, and the cost of an edge is known to its owner only. We study the problem of finding frugal mechanisms for this task, i.e. we investigate the payments the buyer must make in order to buy
ERIC Educational Resources Information Center
Lee, John B.; Clery, Suzanne B.; Presley, Jennifer B.
This report uses the national Baccalaureate and Beyond longitudinal database to look at the early career paths of 1993 college graduates. The results provide information on which college graduates became teachers, where they taught, and whether they left teaching within 3 years. Overall, it is not easy to predict who may be potential teachers when…
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…
Graham B. Spanier; Paul C. Glick
1980-01-01
High divorce rates and the traditionally discrepant ages at death for husbands and wives indicate a need for a more complete understanding of the paths to remarriage in contemporary America. This study uses data from the U.S. Bureau of the Census' Current Population Survey to examine the extent and timing of remarriage, social factors associated with remarriage, and the impact
H. S. Behera; Simpi Patel; Bijayalakshmi Panda
2011-01-01
The main objective of the paper is to improve the Round Robin (RR) algorithm using dynamic ITS by coalescing it with Shortest Remaining Time Next (SRTN) algorithm thus reducing the average waiting time, average turnaround time and the number of context switches. The original time slice has been calculated for each process based on its burst time.This is mostly suited
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.
Efficiently finding the minimum free energy path from steepest descent path
NASA Astrophysics Data System (ADS)
Chen, Changjun; Huang, Yanzhao; Ji, Xiaofeng; Xiao, Yi
2013-04-01
Minimum Free Energy Path (MFEP) is very important in computational biology and chemistry. The barrier in the path is related to the reaction rate, and the start-to-end difference gives the relative stability between reactant and product. All these information is significant to experiment and practical application. But finding MFEP is not an easy job. Lots of degrees of freedom make the computation very complicated and time consuming. In this paper, we use the Steepest Descent Path (SDP) to accelerate the sampling of MFEP. The SHAKE algorithm and the Lagrangian multipliers are used to control the optimization of both SDP and MFEP. These strategies are simple and effective. For the former, it is more interesting. Because as we known, SHAKE algorithm was designed to handle the constraints in molecular dynamics in the past, has never been used in geometry optimization. Final applications on ALA dipeptide and 10-ALA peptide show that this combined optimization method works well. Use the information in SDP, the initial path could reach the more optimal MFEP. So more accurate free energies could be obtained and the amount of computation time could be saved.
Purino, Martín A; Ramírez, Miguel A; Daranas, Antonio H; Martín, Víctor S; Padrón, Juan I
2012-12-01
Prins cyclization of bis-homoallylic alcohols with aldehydes catalyzed by iron(III) salts shows excellent cis selectivity and yields to form 2,7-disubstituted oxepanes. The iron(III) is able to catalyze this process with unactivated olefins. This cyclization was used as the key step in the shortest total synthesis of (+)-isolaurepan. PMID:23167915
Filtered backprojection proton CT reconstruction along most likely paths
Rit, Simon; Dedes, George; Freud, Nicolas; Sarrut, David; Letang, Jean Michel [Universite de Lyon, CREATIS, CNRS UMR5220, Inserm U1044, INSA-Lyon, Universite Lyon 1, Centre Leon Berard, 69008 Lyon (France)
2013-03-15
Purpose: Proton CT (pCT) has the potential to accurately measure the electron density map of tissues at low doses but the spatial resolution is prohibitive if the curved paths of protons in matter is not accounted for. The authors propose to account for an estimate of the most likely path of protons in a filtered backprojection (FBP) reconstruction algorithm. Methods: The energy loss of protons is first binned in several proton radiographs at different distances to the proton source to exploit the depth-dependency of the estimate of the most likely path. This process is named the distance-driven binning. A voxel-specific backprojection is then used to select the adequate radiograph in the distance-driven binning in order to propagate in the pCT image the best achievable spatial resolution in proton radiographs. The improvement in spatial resolution is demonstrated using Monte Carlo simulations of resolution phantoms. Results: The spatial resolution in the distance-driven binning depended on the distance of the objects from the source and was optimal in the binned radiograph corresponding to that distance. The spatial resolution in the reconstructed pCT images decreased with the depth in the scanned object but it was always better than previous FBP algorithms assuming straight line paths. In a water cylinder with 20 cm diameter, the observed range of spatial resolutions was 0.7 - 1.6 mm compared to 1.0 - 2.4 mm at best with a straight line path assumption. The improvement was strongly enhanced in shorter 200 Degree-Sign scans. Conclusions: Improved spatial resolution was obtained in pCT images with filtered backprojection reconstruction using most likely path estimates of protons. The improvement in spatial resolution combined with the practicality of FBP algorithms compared to iterative reconstruction algorithms makes this new algorithm a candidate of choice for clinical pCT.
Path allocation for wavelength path sharing University College London
Haddadi, Hamed
: Wavelength path sharing (WPS) was introduced previously as a means of bridging the gap between the bit answers can be found depending upon the method used for the comparison. 2. Wavelength path sharing (WPS A logical path segment between WPS nodes S & T being transparently routed through X. Key #12;2 shows
Superlinearly Convergent Infeasible-Interior-Point Algorithm for Degenerate LCP
F. A. Potra; R. Sheng
1998-01-01
A large-step infeasible path-following method is proposed for solving general linear complementarity problems with sufficient matrices. If the problem has a solution, the algorithm is superlinearly convergent from any positive starting points, even for degenerate problems. The algorithm generates points in a large neighborhood of the central path. Each iteration requires only one matrix factorization and at most three (asymptotically
PATHS groundwater hydrologic model
Nelson, R.W.; Schur, J.A.
1980-04-01
A preliminary evaluation capability for two-dimensional groundwater pollution problems was developed as part of the Transport Modeling Task for the Waste Isolation Safety Assessment Program (WISAP). Our approach was to use the data limitations as a guide in setting the level of modeling detail. PATHS Groundwater Hydrologic Model is the first level (simplest) idealized hybrid analytical/numerical model for two-dimensional, saturated groundwater flow and single component transport; homogeneous geology. This document consists of the description of the PATHS groundwater hydrologic model. The preliminary evaluation capability prepared for WISAP, including the enhancements that were made because of the authors' experience using the earlier capability is described. Appendixes A through D supplement the report as follows: complete derivations of the background equations are provided in Appendix A. Appendix B is a comprehensive set of instructions for users of PATHS. It is written for users who have little or no experience with computers. Appendix C is for the programmer. It contains information on how input parameters are passed between programs in the system. It also contains program listings and test case listing. Appendix D is a definition of terms.
Kinematic path planning for space-based robotics
NASA Astrophysics Data System (ADS)
Seereeram, Sanjeev; Wen, John T.
1998-01-01
Future space robotics tasks require manipulators of significant dexterity, achievable through kinematic redundancy and modular reconfigurability, but with a corresponding complexity of motion planning. Existing research aims for full autonomy and completeness, at the expense of efficiency, generality or even user friendliness. Commercial simulators require user-taught joint paths-a significant burden for assembly tasks subject to collision avoidance, kinematic and dynamic constraints. Our research has developed a Kinematic Path Planning (KPP) algorithm which bridges the gap between research and industry to produce a powerful and useful product. KPP consists of three key components: path-space iterative search, probabilistic refinement, and an operator guidance interface. The KPP algorithm has been successfully applied to the SSRMS for PMA relocation and dual-arm truss assembly tasks. Other KPP capabilities include Cartesian path following, hybrid Cartesian endpoint/intermediate via-point planning, redundancy resolution and path optimization. KPP incorporates supervisory (operator) input at any detail to influence the solution, yielding desirable/predictable paths for multi-jointed arms, avoiding obstacles and obeying manipulator limits. This software will eventually form a marketable robotic planner suitable for commercialization in conjunction with existing robotic CAD/CAM packages.
Demonstration of scan path optimization in proton therapy
Kang, Joanne H.; Wilkens, Jan J.; Oelfke, Uwe [Department of Medical Physics in Radiation Oncology, German Cancer Research Center (DKFZ), Im Neuenheimer Feld 280, 69120 Heidelberg (Germany)
2007-09-15
A three-dimensional (3D) intensity modulated proton therapy treatment plan to be delivered by magnetic scanning may comprise thousands of discrete beam positions. This research presents the minimization of the total scan path length by application of a fast simulated annealing (FSA) optimization algorithm. Treatment plans for clinical prostate and head and neck cases were sequenced for continuous raster scanning in two ways, and the resulting scan path lengths were compared: (1) A simple back-and-forth, top-to-bottom (zigzag) succession, and (2) an optimized path produced as a solution of the FSA algorithm. Using a first approximation of the scanning dynamics, the delivery times for the scan sequences before and after path optimization were calculated for comparison. In these clinical examples, the FSA optimization shortened the total scan path length for the 3D target volumes by approximately 13%-56%. The number of extraneous spilled particles was correspondingly reduced by about 13%-54% due to the more efficient scanning maps that eliminated multiple crossings through regions of zero fluence. The relative decrease in delivery time due to path length minimization was estimated to be less than 1%, due to both a high scanning speed and time requirements that could not be altered by optimization (e.g., time required to change the beam energy). In a preliminary consideration of application to rescanning techniques, the decrease in delivery time was estimated to be 4%-20%.
Energy aware path planning in complex four dimensional environments
NASA Astrophysics Data System (ADS)
Chakrabarty, Anjan
This dissertation addresses the problem of energy-aware path planning for small autonomous vehicles. While small autonomous vehicles can perform missions that are too risky (or infeasible) for larger vehicles, the missions are limited by the amount of energy that can be carried on board the vehicle. Path planning techniques that either minimize energy consumption or exploit energy available in the environment can thus increase range and endurance. Path planning is complicated by significant spatial (and potentially temporal) variations in the environment. While the main focus is on autonomous aircraft, this research also addresses autonomous ground vehicles. Range and endurance of small unmanned aerial vehicles (UAVs) can be greatly improved by utilizing energy from the atmosphere. Wind can be exploited to minimize energy consumption of a small UAV. But wind, like any other atmospheric component , is a space and time varying phenomenon. To effectively use wind for long range missions, both exploration and exploitation of wind is critical. This research presents a kinematics based tree algorithm which efficiently handles the four dimensional (three spatial and time) path planning problem. The Kinematic Tree algorithm provides a sequence of waypoints, airspeeds, heading and bank angle commands for each segment of the path. The planner is shown to be resolution complete and computationally efficient. Global optimality of the cost function cannot be claimed, as energy is gained from the atmosphere, making the cost function inadmissible. However the Kinematic Tree is shown to be optimal up to resolution if the cost function is admissible. Simulation results show the efficacy of this planning method for a glider in complex real wind data. Simulation results verify that the planner is able to extract energy from the atmosphere enabling long range missions. The Kinematic Tree planning framework, developed to minimize energy consumption of UAVs, is applied for path planning in ground robots. In traditional path planning problem the focus is on obstacle avoidance and navigation. The optimal Kinematic Tree algorithm named Kinematic Tree* is shown to find optimal paths to reach the destination while avoiding obstacles. A more challenging path planning scenario arises for planning in complex terrain. This research shows how the Kinematic Tree* algorithm can be extended to find minimum energy paths for a ground vehicle in difficult mountainous terrain.
Economic Path Scheduling for Mobile Agent System on Computer Network
NASA Astrophysics Data System (ADS)
Olajubu, E. A.
Mobile agent technology has a lot of gains to offer network-centric applications. The technology promises to be very suitable for narrow-bandwidth networks by reducing network latency and allowing transparent per-to-per computing. Multi-agent technology had been proposed for many network-centric applications with little or no path scheduling algorithms. This paper describes the need for path scheduling algorithms for agents in multi-agent systems. Traveling salesman problem (TSP) scheme is used to model ordered agents and the unordered agents schedule their path based on random distribution. The two types of agents were modeled and simulated based on bandwidth usage and response time as performance metrics. Our simulation results shows that ordered agents have superior performance against unordered agents. The ordered agents exhibit lower bandwidth usage and higher response time.
Parallel dynamic programming for on-line flight path optimization
NASA Technical Reports Server (NTRS)
Slater, G. L.; Hu, K.
1989-01-01
Parallel systolic algorithms for dynamic programming(DP) and their respective hardware implementations are presented for a problem in on-line trajectory optimization. The method is applied to a model for helicopter flight path optimization through a complex constraint region. This problem has application to an air traffic control problem and also to a terrain following/threat avoidance problem.
Fractal raster tool paths for layered manufacturing of porous objects
Gurunathan Saravana Kumar; Ponnusamy Pandithevan; Appa Rao Ambatti
2009-01-01
The present work describes an approach for layered manufacturing (LM) of porous objects using an appropriate modelling scheme, a pre-processing algorithm for slicing and a raster tool path generation based on the porosity information. Initially an overall framework of modelling and data transfer that includes controlled porosity information apart from the external geometry of porous objects and its transfer for
Finding a longest path in a complete multipartite digraph
G. Gutin
1993-01-01
A digraph obtained by replacing each edge of a complete mpartite graph with an arc or a pair of mutually opposite arcs with the same end vertices is called a complete m-partite digraph. We describe an O(n 3) algorithm for finding a longest path in a complete m-partite (m ? 2) digraph with n
Time-Optimal Control of Robotic Manipulators Along Specified Paths
J. E. Bobrow; S. Dubowsky; J. S. Gibson
1985-01-01
The minimum-time manipulator control problem is solved for the case when the path is specified and the actuator torque limitations are known. The optimal open-loop torques are found, and a method is given for implementing these torques with a conventional linear feedback control system. The algorithm allows bounds on the torques that may be arbitrary functions of the joint angles
Denoising jet engine gas path measurements using nonlinear filters
Rajeev Verma; Ranjan Ganguli
2005-01-01
Traditionally, linear filters have been used to smooth time series of gas path measurements before performing fault detection and isolation. However, linear filters can smooth out sharp trend shifts in the signal and are also not good at removing outliers. Since most fault detection and isolation algorithms are optimized for Gaussian noise, they can show performance degradation when outliers are
On the Minimization of Average Path Lengths for Heterogeneous MDDs
Shinobu Nagayama; Tsutomu Sasao
2004-01-01
In this paper, we propose an exact and a heuristic min- imization algorithms for the average path length (APL) of heterogeneous multi-valued decision diagrams (MDDs). In a heterogeneous MDD, each variable can take on the dif- ferent number of values. To represent a binary logic func- tion using a heterogeneous MDD, we partition the binary variables into groups, and treat
Visibility in Discrete Geometry: an application to discrete geodesic paths
Paris-Sud XI, UniversitÃ© de
in computational geometry. We present algorithms to compute the set of pixels in a non-convex domain. Introduction In discrete geometry, many Euclidean geometric tools are redefined to take into accountVisibility in Discrete Geometry: an application to discrete geodesic paths David Coeurjolly
ECS 122A: Algorithm Design and Analysis Handout 4 UC Davis --Charles Martel May. 9, 2012
California at Davis, University of
of vertices i, j (we return either the sequence of vertices to visit, or we return NONE to construct an n Ã? n table P where each entry P[i, j] is a pointer to a linked list of the vertices on the shortest path. Note that once the table is built, it take to (k) time to answer a query for a given i, j
NASA Astrophysics Data System (ADS)
Zheng, Feifei; Simpson, Angus R.; Zecchin, Aaron C.
2011-08-01
This paper proposes a novel optimization approach for the least cost design of looped water distribution systems (WDSs). Three distinct steps are involved in the proposed optimization approach. In the first step, the shortest-distance tree within the looped network is identified using the Dijkstra graph theory algorithm, for which an extension is proposed to find the shortest-distance tree for multisource WDSs. In the second step, a nonlinear programming (NLP) solver is employed to optimize the pipe diameters for the shortest-distance tree (chords of the shortest-distance tree are allocated the minimum allowable pipe sizes). Finally, in the third step, the original looped water network is optimized using a differential evolution (DE) algorithm seeded with diameters in the proximity of the continuous pipe sizes obtained in step two. As such, the proposed optimization approach combines the traditional deterministic optimization technique of NLP with the emerging evolutionary algorithm DE via the proposed network decomposition. The proposed methodology has been tested on four looped WDSs with the number of decision variables ranging from 21 to 454. Results obtained show the proposed approach is able to find optimal solutions with significantly less computational effort than other optimization techniques.
Spiral tool-path generation with constant scallop height for sheet metal CNC incremental forming
Hu Zhu; Zhijun Liu; Jianhui Fu
2011-01-01
A spiral tool-path generation method with constant scallop height for the sheet metal CNC incremental forming was proposed\\u000a based on triangular mesh model. On the basis of the curvatures estimation of triangular mesh model, the calculation method\\u000a of spiral tool-path interval with constant scallop height was discussed. Moreover, the algorithms for generation of spiral\\u000a drive path using the polygon boundary
Multi-UAV path planning in obstacle rich environments using Rapidly-exploring Random Trees
Mangal Kothari; Ian Postlethwaite; Da-Wei Gu
2009-01-01
This paper presents path planning algorithms using Rapidly-exploring Random Trees (RRTs) to generate paths for multiple unmanned air vehicles (UAVs) in real time, from given starting locations to goal locations in the presence of static, pop-up and dynamic obstacles. Generating non-conflicting paths in obstacle rich environments for a group of UAVs within a given short time window is a challenging
Estimation of channel temporal auto-correlation and coherence time based on propagation paths
Xuefeng Yin; Junhe Zhou; Byung-Jae Kwak; Hyun Kyu Chung
2010-01-01
In this contribution, we investigate the applicability of using multiple propagation paths to estimate the temporal auto-correlation function and the coherence time of wireless propagation channels. The Space-Alternating Generalized Expectation-maximization (SAGE) algorithm is applied for extracting the paths from measurement data. It is found that the channel auto-correlation function and coherence time computed based on the path parameters are biased.
Efficiently Discovering Hammock Paths from Induced Similarity Networks
Hossain, M Shahriar; Ramakrishnan, Naren
2010-01-01
Similarity networks are important abstractions in many information management applications such as recommender systems, corpora analysis, and medical informatics. For instance, by inducing similarity networks between movies rated similarly by users, or between documents containing common terms, and or between clinical trials involving the same themes, we can aim to find the global structure of connectivities underlying the data, and use the network as a basis to make connections between seemingly disparate entities. In the above applications, composing similarities between objects of interest finds uses in serendipitous recommendation, in storytelling, and in clinical diagnosis, respectively. We present an algorithmic framework for traversing similarity paths using the notion of `hammock' paths which are generalization of traditional paths. Our framework is exploratory in nature so that, given starting and ending objects of interest, it explores candidate objects for path following, and heuristics to admissib...
FPGA-based tool path computation: An application for shoe last machining on CNC lathes
Antonio Jimeno; José Luis Sánchez; Higinio Mora Mora; Jerónimo Mora Pascual; Juan Manuel García Chamizo
2006-01-01
Tool path generation is one of the most complex problems in computer aided manufacturing. Although some efficient strategies have been developed, most of them are only useful for standard machining. The algorithm called Virtual Digitizing computes the tool path by means of a virtually digitized model of the surface and a geometry specification of the tool and its motion, so
Identification of limit cycles in multi-nonlinearity, multiple path systems
NASA Technical Reports Server (NTRS)
Mitchell, J. R.; Barron, O. L.
1979-01-01
A method of analysis which identifies limit cycles in autonomous systems with multiple nonlinearities and multiple forward paths is presented. The FORTRAN code for implementing the Harmonic Balance Algorithm is reported. The FORTRAN code is used to identify limit cycles in multiple path and nonlinearity systems while retaining the effects of several harmonic components.
Tool path generation and 3D tolerance analysis for free-form surfaces
Choi, Young Keun
2005-08-29
in the tool paths. Several parts, for which the CC points are generated using the proposed algorithm, are machined using a three axes milling machine. As part of the validation process, the tool paths generated during machining are analyzed to compare...
Search properties of some sequential decoding algorithms.
NASA Technical Reports Server (NTRS)
Geist, J. M.
1973-01-01
Sequential decoding procedures are studied in the context of selecting a path through a tree. Several algorithms are considered, and their properties are compared. It is shown that the stack algorithm introduced by Zigangirov (1966) and by Jelinek (1969) is essentially equivalent to the Fano algorithm with regard to the set of nodes examined and the path selected, although the description, implementation, and action of the two algorithms are quite different. A modified Fano algorithm is introduced, in which the quantizing parameter is eliminated. It can be inferred from limited simulation results that, at least in some applications, the new algorithm is computationally inferior to the old. However, it is of some theoretical interest since the conventional Fano algorithm may be considered to be a quantized version of it.
Molecular definition of the shortest region of deletion overlap in the Langer-Giedion syndrome
Lüdecke, Hermann-Josef; Johnson, Carey; Wagner, Michael J.; Wells, Dan E.; Turleau, Catherine; Tommerup, Niels; Latos-Bielenska, Anna; Sandig, Klaus-Rainer; Meinecke, Peter; Zabel, Bernhard; Horsthemke, Bernhard
1991-01-01
The Langer-Giedion syndrome (LGS), which is characterized by craniofacial dysmorphism and skeletal abnormalities, is caused by a genetic defect in 8q24.1. We have used 13 anonymous DNA markers from an 8q24.1-specific microdissection library, as well as c-myc and thyroglobulin gene probes, to map the deletion breakpoints in 16 patients with LGS. Twelve patients had a cytogenetically visible deletion, two patients had an apparently balanced translocation, and two patients had an apparently normal karyotype. In all cases except one translocation patient, loss of genetic material was detected. The DNA markers fall into 10 deletion intervals. Clone L48 (D8S51) defines the shortest region of deletion overlap (SRO), which is estimated to be less than 2 Mbp. Three clones–pl7-2.3EE (D8S43), L24 (D8S45), and L40 (D8S49)–which flank the SRO recognize evolutionarily conserved sequences. ImagesFigure 1Figure 3Figure 4 PMID:1836105
NSDL National Science Digital Library
The well known Berkeley Digital Library SunSite, discussed in the February 9, 1996 Scout Report, has recently added a new resource to its collection. The PATH database, maintained by the Harmer E. Davis Transportation Library at the University of California, is "the world's largest bibliographical database pertaining to Intelligent Transportation Systems (ITS)." It is searchable and browsable (Browse by ITS Thesaurus Term), and contains over 9,000 records and abstracts "including monographs, journal articles, conference papers, technical reports, theses and selected media coverage," dating back to the 1940s.
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.
NSDL National Science Digital Library
2012-01-01
This mobile app (available for both iOS and Android devices) was developed by the National Council of Teachers of Mathematics with funding from Verizon Foundation. The app is based on the Decimal Maze from the popular lesson "Too Big or Too Small". The goal is to help Okta reach the target (maximum, minimum, or a specific value) by choosing a path from the top of the maze to the bottom — adding, subtracting, multiplying and dividing as the player goes. Seven levels with seven puzzles in each level test the player's skills with operation with powers of ten, negative numbers, fractions, decimals, and exponents.
Bleakley, Hoyt; Lin, Jeffrey
2012-01-01
We examine portage sites in the U.S. South, Mid-Atlantic, and Midwest, including those on the fall line, a geomorphological feature in the southeastern U.S. marking the final rapids on rivers before the ocean. Historically, waterborne transport of goods required portage around the falls at these points, while some falls provided water power during early industrialization. These factors attracted commerce and manufacturing. Although these original advantages have long since been made obsolete, we document the continuing importance of these portage sites over time. We interpret these results as path dependence and contrast explanations based on sunk costs interacting with decreasing versus increasing returns to scale. PMID:23935217
NSDL National Science Digital Library
Tom Biddlecome
1999-11-08
The Ohio State Universitys Library web site notes As a navigational aviator, Byrd pioneered in the technology that would be the foundation for modern polar exploration and investigation. As a decorated and much celebrated hero, Byrd drew popular attention to areas of the world that became focal points of scientific investigation in numerous disciplines. More information about Admiral Richard E. Byrd can be found at (http:--www.lib.ohio-state.edu-arvweb-polar-byrd-byrd.htm). The next animation, #1001, shows Byrds plane as it follows the flight path presented in this animation.
Regularization Paths for Generalized Linear Models via Coordinate Descent
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
Wilfred Goldmann; Angela Chong; James Foster; James Hope; Nora Hunter
1998-01-01
The prion protein (PrP) gene modulates the in- cidence and incubation periods of transmissible spongiform encephalopathies of sheep, goats, mice and man. Here, a new caprine PrP allele encoding the shortest naturally occurring PrP protein so far described is reported. This variant contains only three instead of the usual five copies of a short peptide repeat (Pro-Gln\\/His-Gly-Gly-Gly-(Gly)-Trp- Gly-Gln) characteristic of
Fujikawa, Kazuo
2015-01-01
We establish the direct $d=2$ on-shell bosonization $\\psi_{L}(x_{+}) = e^{i\\xi(x_{+})}$ and~$\\psi_{R}^{\\dagger}(x_{-}) = e^{i\\xi(x_{-})}$ in path integral formulation by deriving the off-shell relations $\\psi_{L}(x)\\psi_{R}^{\\dagger}(x) = \\exp[i\\xi(x)]$ and $\\psi_{R}(x)\\psi_{L}^{\\dagger}(x) = \\exp[-i\\xi(x)]$. Similarly, the on-shell bosonization of the bosonic commuting spinor, $\\phi_{L}(x_{+}) = ie^{-i\\xi(x_{+})}\\partial^{+}e^{-i\\chi(x_{+})}$, $\\phi^{\\dagger}_{R}(x_{-}) = e^{-i\\xi(x_{-})-i\\chi(x_{-})}$ and $\\phi_{R}(x_{-}) = ie^{i\\xi(x_{-})}\\partial^{-}e^{+i\\chi(x_{-})}$, $\\phi^{\\dagger}_{L}(x_{+}) = e^{i\\xi(x_{+})+i\\chi(x_{+})}$, is established in path integral formulation by deriving the off-shell relations $\\phi_{L}(x)\\phi^{\\dagger}_{R}(x) = ie^{-i\\xi(x)}\\partial^{+}e^{-i\\chi(x)}$ and $\\phi_{R}(x)\\phi^{\\dagger}_{L}(x) = ie^{i\\xi(x)}\\partial^{-}e^{i\\chi(x)}$.
Bidirectional A Search on Time-Dependent Road Networks
2010-04-02
modifications that improve the performance of our algorithm, and prove their correctness. ...... portation Research Records, 1645:170–175, 1998. [6] I. Chabini and S. Lan. ... An appraisal of some shortest-path algorithms. Operations. Research ...
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.
Flight Paths of Orbiting Satellites
NSDL National Science Digital Library
This is an activity to help students visualize the relationship of motion, time and space as it relates to objects orbiting the earth. They will be able to track the path of an orbiting object on a globe, plot the path of an orbiting object on a flat world map, and explain that an object orbiting earth on a plane will produce a flight path which appears as wavy lines on the earths surface.
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.
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
SDSS J0926+3624: the shortest period eclipsing binary star
NASA Astrophysics Data System (ADS)
Copperwheat, C. M.; Marsh, T. R.; Littlefair, S. P.; Dhillon, V. S.; Ramsay, G.; Drake, A. J.; Gänsicke, B. T.; Groot, P. J.; Hakala, P.; Koester, D.; Nelemans, G.; Roelofs, G.; Southworth, J.; Steeghs, D.; Tulloch, S.
2011-01-01
With orbital periods of the order of tens of minutes or less, the AM Canum Venaticorum stars are ultracompact, hydrogen-deficient binaries with the shortest periods of any binary subclass, and are expected to be among the strongest gravitational wave sources in the sky. To date, the only known eclipsing source of this type is the P= 28 min binary SDSS J0926+3624. We present multiband, high time resolution light curves of this system, collected with William Herschel Telescope (WHT)/ULTRACAM in 2006 and 2009. We supplement these data with additional observations made with Liverpool Telescope/Rapid Imager to Search for Exoplanets (LT/RISE), XMM-Newton and the Catalina Real-Time Transient Survey. From light curve models we determine the mass ratio to be q=M2/M1= 0.041 ± 0.002 and the inclination to be ?. We calculate the mass of the primary white dwarf to be 0.85 ± 0.04 M? and the donor to be 0.035 ± 0.003 M?, implying a partially degenerate state for this component. We observe superhump variations that are characteristic of an elliptical, precessing accretion disc. Our determination of the superhump period excess is in agreement with the established relationship between this parameter and the mass ratio, and is the most precise calibration of this relationship at low q. We also observe a quasi-periodic oscillation in the 2006 data, and we examine the outbursting behaviour of the system over a 4.5 year period.
AH Cam: A metal-rich RR Lyrae star with the shortest known Blazhko period
NASA Technical Reports Server (NTRS)
Smith, Horace A.; Matthews, Jaymie M.; Lee, Kevin M.; Williams, Jeffrey; Silbermann, N. A.; Bolte, Michael
1994-01-01
Analysis of 746 new V-band observations of the RR Lyrae star AH Cam obtained during 1989 - 1992 clearly show that its light curve cannot be described by a single period. In fact, at first glance, the Fourier spectrum of the photometry resembles that of a double-mode pulsator, with peaks at a fundamental period of 0.3686 d and an apparent secondary period of 0.2628 d. Nevertheless, the dual-mode solution is a poor fit to the data. Rather, we believe that AH Cam is a single-mode RR Lyrae star undergoing the Blazhko effect: periodic modulation of the amplitude and shape of its light curve. What was originally taken to be the period of the second mode is instead the 1-cycle/d alias of a modulation sidelobe in the Fourier spectrum. The data are well described by a modulation period of just under 11 d, which is the shortest Blazhko period reported to date in the literature and confirms the earlier suggestion by Goranskii. A low-resolution spectrum of AH Cam indicates that it is relatively metal rich, with delta-S less than or = 2. Its high metallicity and short modulation period may provide a critical test of at least one theory for the Blazhko effect. Moskalik's internal resonance model makes specific predictions of the growth rate of the fundamental model vs fundamental period. AH Cam falls outside the regime of other known Blazhko variables and resonance model predictions, but these are appropriate for metal-poor RR Lyrae stars. If the theory matches the behavior of AH Cam for a metal-rich stellar model, this would bolster the resonance hypothesis.
An Interior Random Vector Algorithm for MultiStage Stochastic Linear Programs
Eithan Schweitzer
1998-01-01
In this paper, an interior point algorithm for linear programs is adapted for solving multistage stochastic linear programs. The algorithm is based on Monteiro and Adler's path-following algorithm for deterministic linear programs. In practice, the complexity of the algorithm is linear with respect to the size of the sample space. The algorithm starts from a feasible solution of the problem
Critical Path-Based Thread Placement for NUMA Systems
Su, C Y; Li, D; Nikolopoulos, D S; Grove, M; Cameron, K; de Supinski, B R
2011-11-01
Multicore multiprocessors use a Non Uniform Memory Architecture (NUMA) to improve their scalability. However, NUMA introduces performance penalties due to remote memory accesses. Without efficiently managing data layout and thread mapping to cores, scientific applications, even if they are optimized for NUMA, may suffer performance loss. In this paper, we present algorithms and a runtime system that optimize the execution of OpenMP applications on NUMA architectures. By collecting information from hardware counters, the runtime system directs thread placement and reduces performance penalties by minimizing the critical path of OpenMP parallel regions. The runtime system uses a scalable algorithm that derives placement decisions with negligible overhead. We evaluate our algorithms and runtime system with four NPB applications implemented in OpenMP. On average the algorithms achieve between 8.13% and 25.68% performance improvement compared to the default Linux thread placement scheme. The algorithms miss the optimal thread placement in only 8.9% of the cases.
Computing Path Tables for Quickest Multipaths In Computer Networks
Grimmell, W.C.
2004-12-21
We consider the transmission of a message from a source node to a terminal node in a network with n nodes and m links where the message is divided into parts and each part is transmitted over a different path in a set of paths from the source node to the terminal node. Here each link is characterized by a bandwidth and delay. The set of paths together with their transmission rates used for the message is referred to as a multipath. We present two algorithms that produce a minimum-end-to-end message delay multipath path table that, for every message length, specifies a multipath that will achieve the minimum end-to-end delay. The algorithms also generate a function that maps the minimum end-to-end message delay to the message length. The time complexities of the algorithms are O(n{sup 2}((n{sup 2}/logn) + m)min(D{sub max}, C{sub max})) and O(nm(C{sub max} + nmin(D{sub max}, C{sub max}))) when the link delays and bandwidths are non-negative integers. Here D{sub max} and C{sub max} are respectively the maximum link delay and maximum link bandwidth and C{sub max} and D{sub max} are greater than zero.
Thermoalgebras and path integral
Khanna, F.C. [Theoretical Physics Institute, University of Alberta, Edmonton, AB T6G 2J1 (Canada); TRIUMF, Vancouver, BC, V6T 2A3 (Canada)], E-mail: khanna@phys.ualberta.ca; Malbouisson, A.P.C. [Centro Brasileiro de Pesquisas Fisicas/MCT, 22290-180 Rio de Janeiro, RJ (Brazil)], E-mail: adolfo@cbpf.br; Malbouisson, J.M.C. [Instituto de Fisicas, Universidade Federal da Bahia, 40210-340 Salvador, BA (Brazil)], E-mail: jmalboui@ufba.br; Santana, A.E. [Instituto de Fisicas, Universidade de Brasilia, 70910-900 Brasilia, DF (Brazil)], E-mail: asantana@fis.unb.br
2009-09-15
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 (S{sup 1}){sup d}xR{sup D-d} topology is addressed.
Path integral simulation of polarized solitons in optical fibers
NASA Astrophysics Data System (ADS)
Hayata, K.; Saka, K.; Koshiba, M.
1990-11-01
An efficient computational approach based on the path integral concept is described to solve nonlinear pulse propagation dynamics in realistic optical fibers. As model equations which can predict the propagation, we consider the perturbed (scalar) and the coupled (vectorial) nonlinear Schrödinger equations for monomode and birefringent fibers, respectively. With the equivalence between path integration and Fresnel transform, an efficient algorithm can be employed which has been developed for use in the field of wave signal processing of holographic data. After ensuring the validity of the method through the application to canonical soliton problems, results are shown for nonlinear pulse propagation under realistic conditions.
On load paths and load bearing topology from finite element analysis
NASA Astrophysics Data System (ADS)
Kelly, D.; Reidsema, C.; Lee, M.
2010-06-01
Load paths can be mapped from vector plots of 'pointing stress vectors'. They define a path along which a component of load remains constant as it traverses the solution domain. In this paper the theory for the paths is first defined. Properties of the plots that enable a designer to interpret the structural behavior from the contours are then identified. Because stress is a second order tensor defined on an orthogonal set of axes, the vector plots define separate paths for load transfer in each direction of the set of axes. An algorithm is therefore presented that combines the vectors to define a topology to carry the loads. The algorithm is shown to straighten the paths reducing bending moments and removing stress concentration. Application to a bolted joint, a racing car body and a yacht hull demonstrate the usefulness of the plots.
NASA Astrophysics Data System (ADS)
Zhu, Detong
2001-11-01
This paper presents a family of improved secant algorithms via two preconditional curvilinear paths, the preconditional modified gradient path and preconditional optimal path, for solving general nonlinear optimization problems with nonlinear equality constraints. We employ the stable Bunch-Parlett factorization method of symmetric matrices so that two preconditional curvilinear paths are very easily formed. The nonmonotone curvilinear search technique, by introducing a nonsmooth merit function and adopting a dogleg-typed movement, is used to speed up the convergence progress in the contours of objective function with large curvature. Global convergence of the proposed algorithms is obtained under some reasonable conditions. Furthermore, the dogleg-typed step overcomes the Maratos effect to bring the local superlinear convergence rate. The results of numerical experiments are reported to show the effectiveness of the proposed algorithms.
Algorithms and architectures for high performance analysis of semantic graphs.
Hendrickson, Bruce Alan
2005-09-01
Semantic graphs offer one promising avenue for intelligence analysis in homeland security. They provide a mechanism for describing a wide variety of relationships between entities of potential interest. The vertices are nouns of various types, e.g. people, organizations, events, etc. Edges in the graph represent different types of relationships between entities, e.g. 'is friends with', 'belongs-to', etc. Semantic graphs offer a number of potential advantages as a knowledge representation system. They allow information of different kinds, and collected in differing ways, to be combined in a seamless manner. A semantic graph is a very compressed representation of some of relationship information. It has been reported that the semantic graph can be two orders of magnitude smaller than the processed intelligence data. This allows for much larger portions of the data universe to be resident in computer memory. Many intelligence queries that are relevant to the terrorist threat are naturally expressed in the language of semantic graphs. One example is the search for 'interesting' relationships between two individuals or between an individual and an event, which can be phrased as a search for short paths in the graph. Another example is the search for an analyst-specified threat pattern, which can be cast as an instance of subgraph isomorphism. It is important to note than many kinds of analysis are not relationship based, so these are not good candidates for semantic graphs. Thus, a semantic graph should always be used in conjunction with traditional knowledge representation and interface methods. Operations that involve looking for chains of relationships (e.g. friend of a friend) are not efficiently executable in a traditional relational database. However, the semantic graph can be thought of as a pre-join of the database, and it is ideally suited for these kinds of operations. Researchers at Sandia National Laboratories are working to facilitate semantic graph analysis. Since intelligence datasets can be extremely large, the focus of this work is on the use of parallel computers. We have been working to develop scalable parallel algorithms that will be at the core of a semantic graph analysis infrastructure. Our work has involved two different thrusts, corresponding to two different computer architectures. The first architecture of interest is distributed memory, message passing computers. These machines are ubiquitous and affordable, but they are challenging targets for graph algorithms. Much of our distributed-memory work to date has been collaborative with researchers at Lawrence Livermore National Laboratory and has focused on finding short paths on distributed memory parallel machines. Our implementation on 32K processors of BlueGene/Light finds shortest paths between two specified vertices in just over a second for random graphs with 4 billion vertices.
Dutta, Rudra
in Path, Star, and Tree Networks: Complexity, Bounds, and Algorithms Shu Huang, Rudra Dutta, and George N. Rouskas Abstract-- We consider the problem of traffic grooming in WDM path, star, and tree networks of results which settle the complexity of traffic grooming in path and star networks, by proving
Obstacle avoidance and path planning
Stephen Cameron
1994-01-01
Outlines the state-of-the-art in obstacle avoidance and path planning for industrial robots that is practical on the current generation of computer hardware. Describes practical vehicle planners and planning for manipulators. Summarizes that obstacle avoidance and path planning are techniques with differing goals. Sonar is the standard method of obstacle avoidance systems which is largely limited by the reliability of the
Wall-climbing Robot Path Planning for Testing Cylindrical Oilcan Weld Based on Voronoi Diagram
Zhuang Fu; Yan-zheng Zhao; Zhi-yuan Qian; Qi-xin Cao
2006-01-01
To improve the efficiency of the weld testing for a cylindrical oilcan performed by the wall-climbing robot, this paper gives an algorithm for generating the Voronoi diagram from the points set on a cylinder by modification process. Based on this algorithm the paper also provides a method about the design of cylindrical tank wallboards and the weld testing path planning
Multiple-Event Location with Station-Correlated Path Corrections
NASA Astrophysics Data System (ADS)
Rodi, W.; Myers, S. C.
2003-12-01
Multiple-event location methods solve jointly for the locations of a set of seismic events and travel-time corrections associated with the paths from the events to the observing stations. Many of these methods assume the path corrections for a given station are the same for all events, which effects an important constraint on the event locations but which restricts the method to event clusters of small aperture. A notable exception is the double-differencing method, which allows for de-correlation of path corrections for well separated pairs of events. However, these methods do not typically incorporate a model of complete or partial correlation of path corrections between seismic stations, and thus omit potentially valuable information for many common network geometries. This paper investigates a new approach to multiple-event location that models the correlation of travel-time corrections for each pair of paths as a function of both event and station separation. The approach generates path corrections from a ``universal correction function'', which is sampled at the event location and station location to produce the correction for a given path. The universal correction function is estimated from observed travel-time residuals using a geo-statistical interpolation technique (kriging), making use of prior covariance information to impose correlations between paths. We have tested this approach on a data set from the Nevada Test Site (NTS) comprising Pn and Pg arrival times from 64 stations and 74 explosions for which precise location parameters are available. In this data set some stations are separated by less than 10 km while the median nearest-neighbor distance is only 70 km. Our tests compare event locations obtained using station-uncorrelated and station-correlated path corrections, each estimated from the observed travel-time residuals relative to the IASP91 earth model. In our initial tests, the path corrections are derived using the known locations of the events and then used in a single-event location algorithm applied to each event. The resulting event mislocations are consistently smaller when station-correlated corrections are used. More realistic tests entail estimating the path corrections jointly with the event locations in a multiple-event location process. Preliminary tests of this type on the NTS data indicate that multiple-event location methods incorporating station-correlated path corrections yield modestly smaller mislocations than the traditional methods.
A Fast Taboo Search Algorithm for the Job Shop Problem
Eugeniusz Nowicki; Czeslaw Smutnicki
1996-01-01
A fast and easily implementable approximation algorithm for the problem of finding a minimum makespan in a job shop is presented. The algorithm is based on a taboo search technique with a specific neighborhood definition which employs a critical path and blocks of operations notions. Computational experiments (up to 2,000 operations) show that the algorithm not only finds shorter makespans
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.
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.
MAXI J1659-152: the shortest orbital period black-hole transient in outburst
NASA Astrophysics Data System (ADS)
Kuulkers, E.; Kouveliotou, C.; Belloni, T.; Cadolle Bel, M.; Chenevez, J.; Díaz Trigo, M.; Homan, J.; Ibarra, A.; Kennea, J. A.; Muñoz-Darias, T.; Ness, J.-U.; Parmar, A. N.; Pollock, A. M. T.; van den Heuvel, E. P. J.; van der Horst, A. J.
2013-04-01
MAXI J1659-152 is a bright X-ray transient black-hole candidate binary system discovered in September 2010. We report here on MAXI, RXTE, Swift, and XMM-Newton observations during its 2010/2011 outburst. We find that during the first one and a half week of the outburst the X-ray light curves display drops in intensity at regular intervals, which we interpret as absorption dips. About three weeks into the outbursts, again drops in intensity are seen. These dips have, however, a spectral behaviour opposite to that of the absorption dips, and are related to fast spectral state changes (hence referred to as transition dips). The absorption dips recur with a period of 2.414 ± 0.005 h, which we interpret as the orbital period of the system. This implies that MAXI J1659-152 is the shortest period black-hole candidate binary known to date. The inclination of the accretion disk with respect to the line of sight is estimated to be 65-80°. We propose the companion to the black-hole candidate to be close to an M5 dwarf star, with a mass and radius of about 0.15-0.25 M? and 0.2-0.25 R?, respectively. We derive that the companion had an initial mass of about 1.5 M?, which evolved to its current mass in about 5-6 billion years. The system is rather compact (orbital separation of ?1.33 R?), and is located at a distance of 8.6 ± 3.7 kpc, with a height above the Galactic plane of 2.4 ± 1.0 kpc. The characteristics of short orbital period and high Galactic scale height are shared with two other transient black-hole candidate X-ray binaries, i.e., XTE J1118+480 and Swift J1735.5-0127. We suggest that all three are kicked out of the Galactic plane into the halo, rather than being formed in a globular cluster. Table 1 is available in electronic form at http://www.aanda.org
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.
NASA Astrophysics Data System (ADS)
Shakeri, Nadim; Jalili, Saeed; Ahmadi, Vahid; Rasoulzadeh Zali, Aref; Goliaei, Sama
2015-01-01
The problem of finding the Hamiltonian path in a graph, or deciding whether a graph has a Hamiltonian path or not, is an NP-complete problem. No exact solution has been found yet, to solve this problem using polynomial amount of time and space. In this paper, we propose a two dimensional (2-D) optical architecture based on optical electronic devices such as micro ring resonators, optical circulators and MEMS based mirror (MEMS-M) to solve the Hamiltonian Path Problem, for undirected graphs in linear time. It uses a heuristic algorithm and employs n+1 different wavelengths of a light ray, to check whether a Hamiltonian path exists or not on a graph with n vertices. Then if a Hamiltonian path exists, it reports the path. The device complexity of the proposed architecture is O(n2).
Algorithmic design of self-folding polyhedra
Pandey, Shivendra; Ewing, Margaret; Kunas, Andrew; Nguyen, Nghi; Gracias, David H.; Menon, Govind
2011-01-01
Self-assembly has emerged as a paradigm for highly parallel fabrication of complex three-dimensional structures. However, there are few principles that guide a priori design, yield, and defect tolerance of self-assembling structures. We examine with experiment and theory the geometric principles that underlie self-folding of submillimeter-scale higher polyhedra from two-dimensional nets. In particular, we computationally search for nets within a large set of possibilities and then test these nets experimentally. Our main findings are that (i) compactness is a simple and effective design principle for maximizing the yield of self-folding polyhedra; and (ii) shortest paths from 2D nets to 3D polyhedra in the configuration space are important for rationalizing experimentally observed folding pathways. Our work provides a model problem amenable to experimental and theoretical analysis of design principles and pathways in self-assembly. PMID:22139373
Heuristically optimal path scanning for high-speed multiphoton circuit imaging
Sadovsky, Alexander J.; Kruskal, Peter B.; Kimmel, Joseph M.; Ostmeyer, Jared; Neubauer, Florian B.
2011-01-01
Population dynamics of patterned neuronal firing are fundamental to information processing in the brain. Multiphoton microscopy in combination with calcium indicator dyes allows circuit dynamics to be imaged with single-neuron resolution. However, the temporal resolution of fluorescent measures is constrained by the imaging frequency imposed by standard raster scanning techniques. As a result, traditional raster scans limit the ability to detect the relative timing of action potentials in the imaged neuronal population. To maximize the speed of fluorescence measures from large populations of neurons using a standard multiphoton laser scanning microscope (MPLSM) setup, we have developed heuristically optimal path scanning (HOPS). HOPS optimizes the laser travel path length, and thus the temporal resolution of neuronal fluorescent measures, using standard galvanometer scan mirrors. Minimizing the scan path alone is insufficient for prolonged high-speed imaging of neuronal populations. Path stability and the signal-to-noise ratio become increasingly important factors as scan rates increase. HOPS addresses this by characterizing the scan mirror galvanometers to achieve prolonged path stability. In addition, the neuronal dwell time is optimized to sharpen the detection of action potentials while maximizing scan rate. The combination of shortest path calculation and minimization of mirror positioning time allows us to optically monitor a population of neurons in a field of view at high rates with single-spike resolution, ?125 Hz for 50 neurons and ?8.5 Hz for 1,000 neurons. Our approach introduces an accessible method for rapid imaging of large neuronal populations using traditional MPLSMs, facilitating new insights into neuronal circuit dynamics. PMID:21715667
Khan, Wajahat Faheem
2008-01-01
We study the performance of a differential backlog routing algorithm in a network with random failures. Differential Backlog routing is a novel routing algorithm where packets are routed through multiple paths to their ...
Michele Mosca
2008-08-04
This article surveys the state of the art in quantum computer algorithms, including both black-box and non-black-box results. It is infeasible to detail all the known quantum algorithms, so a representative sample is given. This includes a summary of the early quantum algorithms, a description of the Abelian Hidden Subgroup algorithms (including Shor's factoring and discrete logarithm algorithms), quantum searching and amplitude amplification, quantum algorithms for simulating quantum mechanical systems, several non-trivial generalizations of the Abelian Hidden Subgroup Problem (and related techniques), the quantum walk paradigm for quantum algorithms, the paradigm of adiabatic algorithms, a family of ``topological'' algorithms, and algorithms for quantum tasks which cannot be done by a classical computer, followed by a discussion.
Variable path cryogenic acoustic interferometer
NASA Astrophysics Data System (ADS)
Kucera, D. M.; Ketterson, J. B.
1998-12-01
We describe a variable path acoustic interferometer for use at cryogenic temperatures. Movement is enabled without mechanical coupling via two piezoelectric bimorphs wired and mounted in a manner that preserves the parallelism of two ultrasonic transducers that define the acoustic path. A certain degree of in situ alignment can also be accomplished. Path length sweeps from 0 to 180 ?m have been made at cryogenic temperatures and preliminary sound velocity measurements in liquid 4He and gaseous 3He near 4 K are presented which agree well with past measurements.
Counting Paths in VPA Is Complete for #NC1
Andreas Krebs; Nutan Limaye; Meena Mahajan
2010-01-01
\\u000a We give a #NC\\u000a 1 upper bound for the problem of counting accepting paths in any fixed visibly pushdown automaton. Our algorithm involves a\\u000a non-trivial adaptation of the arithmetic formula evaluation algorithm of Buss, Cook, Gupta, Ramachandran ([9]). We also show\\u000a that the problem is #NC\\u000a 1 hard. Our results show that the difference between #BWBP and #NC\\u000a 1 is
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.
On effectiveness of routing algorithms for satellite communication networks
NASA Astrophysics Data System (ADS)
Yu, Wei; Wei, Sixiao; Xu, Guobin; Chen, Genshe; Pham, Khanh; Blasch, Erik P.; Lu, Chao
2013-05-01
For worldwide, a satellite communication network is an integral component of the global networking infrastructure. In this paper, we focus on developing effective routing techniques that consider both user preferences and network dynamic conditions. In particular, we develop a weighted-based route selection scheme for the core satellite communication network. Unlike the shortest path routing scheme, our scheme chooses the route from multiple matched entries based on the assigned weights that reflect the dynamic condition of networks. We also discuss how to derive the optimal weights for route assignment. To further meet user's preference, we implement the multiple path routing scheme to achieve the high rate of data transmission and the preemption based routing scheme to guarantee the data transmission for high priority users. Through extensive simulation studies, our data validates the effectiveness of our proposed routing schemes.
Quantum Adiabatic Algorithms and Large Spin Tunnelling
NASA Technical Reports Server (NTRS)
Boulatov, A.; Smelyanskiy, V. N.
2003-01-01
We provide a theoretical study of the quantum adiabatic evolution algorithm with different evolution paths proposed in this paper. The algorithm is applied to a random binary optimization problem (a version of the 3-Satisfiability problem) where the n-bit cost function is symmetric with respect to the permutation of individual bits. The evolution paths are produced, using the generic control Hamiltonians H (r) that preserve the bit symmetry of the underlying optimization problem. In the case where the ground state of H(0) coincides with the totally-symmetric state of an n-qubit system the algorithm dynamics is completely described in terms of the motion of a spin-n/2. We show that different control Hamiltonians can be parameterized by a set of independent parameters that are expansion coefficients of H (r) in a certain universal set of operators. Only one of these operators can be responsible for avoiding the tunnelling in the spin-n/2 system during the quantum adiabatic algorithm. We show that it is possible to select a coefficient for this operator that guarantees a polynomial complexity of the algorithm for all problem instances. We show that a successful evolution path of the algorithm always corresponds to the trajectory of a classical spin-n/2 and provide a complete characterization of such paths.
Algorithms for an Unmanned Vehicle Path Planning Problem
Qin, Jianglei
2013-06-25
deployed in military operations in Afghanistan in 2002. These robots have been used to detect and disarm explosive devices. It has also been used to collect air samples to detect chemical and radiological agents[10]. Like Packbots, many other UVs...
PAL: A Path Selection Algorithm for Life Critical Data
Sadik Armagan; Enda Fallon; Yuansong Qiao
2010-01-01
The real time data transmission facilities provided by Personal Area Networks (PAN) can improve both the life expectancy and living conditions of patients following cardiac surgery. The limited signal range of such devices however, coupled with the life critical nature of the data transferred places strict performance limits on the mobility protocol. The Stream Control Transmission Protocol (SCTP) can support
A Path Following Algorithm for the Graph Matching Problem
Bach, Francis
, gradient methods, machine learning, classification, image processing. Ã? 1 INTRODUCTION THE graph matching problem is among the most important challenges of graph processing and plays a central role in various as well. A nonexhaus- tive list of graph matching applications includes document processing tasks like
A Path Following Algorithm for the Graph Matching Problem
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.
Path following algorithm for the graph matching problem
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
Algorithms and Sensors for Small Robot Path Following
Roumeliotis, Stergios I.
with GPS dropouts in urban ar- eas and under tree canopies, coping with obstacles that fall within-- Tracked mobile robots in the 20 kg size class are un- der development for applications in urban the safety and ef- fectiveness of urban reconnaissance and rescue operations. The size and weight of a recent
Guidewire path simulation using equilibrium of forces
NASA Astrophysics Data System (ADS)
Cardoso, Fernando M.; Furuie, Sergio S.
2014-03-01
Vascular diseases are among the major causes of death in developed countries and the treatment of those pathologies may require endovascular interventions, in which the physician utilizes guidewires and catheters through the vascular system to reach the injured vessel region. Several computational studies related to endovascular procedures are in constant development. So, predicting the guidewire path may be of great value for both physicians and researchers. We propose a method to simulate and predict the guidewire and catheter path inside a blood vessel based on equilibrium of forces, which leads, iteratively, to the minimum energy configuration. This technique was validated with physical models using a Ø0.33mm stainless steel guidewire. This method presented RMS error, in average, less than 1 mm. Moreover, the algorithm presented low variation (in average, ?=0.03mm) due to the variation of the input parameters. Therefore, even for a wide range of different parameters configuration, similar results are presented, which makes this technique easier to work with. Since this method is based on basic physics, it is simple, intuitive, easy to learn and easy to adapt.
Scattering theory with path integrals
NASA Astrophysics Data System (ADS)
Rosenfelder, R.
2014-03-01
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.
An introduction to critical paths.
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
COMPUTER SCIENCE: MISCONCEPTIONS, CAREER PATHS
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
Atmospheric Science Data Center
2014-12-08
... orbits that observe the same areas under the same nominal angular conditions. Areas that are close to each other in longitude will be ... 1 crosses the equator at 64.60° west longitude. Orbital Paths/Blocks ...
Collaborative Authoring of Walden's Paths
Li, Yuanling
2012-10-19
The World Wide Web contains rich collections of digital materials that can be used in education and learning settings. The collaborative authoring prototype of Walden's Paths targets two groups of users: educators and learners. From the perspective...
Yong Seung Cho; Soon-Tae Hong
2007-06-01
We consider the path space of a curved manifold on which a point particle is introduced in a conservative physical system with constant total energy to formulate its action functional and geodesic equation together with breaks on the path. The second variation of the action functional is exploited to yield the geodesic deviation equation and to discuss the Jacobi fields on the curved manifold. We investigate the topology of the path space using the action functional on it and its physical meaning by defining the gradient of the action functional, the space of bounded flow energy solutions and the moduli space associated with the critical points of the action functional. We also consider the particle motion on the $n$-sphere $S^{n}$ in the conservative physical system to discuss explicitly the moduli space of the path space and the corresponding homology groups.
Scattering theory with path integrals
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.
Survivable paths in multilayer networks
Parandehgheibi, Marzieh
2012-01-01
We consider the problem of protection in multilayer networks. In single-layer net- works, a pair of disjoint paths can be used to provide protection for a source-destination pair. However, this approach cannot be directly ...
NASA Astrophysics Data System (ADS)
Romanovkii, O. A.; Kharchenko, O. V.; Yakovlev, S. V.
2015-02-01
Algorithm for planning and performing lidar and path measurements of the meteorological parameters of the atmosphere is presented. Wavelengths promising for measuring the humidity and temperature of the atmosphere on tropospheric paths are determined. Lidar signals are calculated to determine humidity profiles and random errors in reconstruction of humidity and temperature profiles at these wavelengths using an overtone CO laser as a radiation source. The feasibility of determining the background water vapor concentrations on short paths using a Sr laser is demonstrated.
Lung fissure detection in CT images using global minimal paths
NASA Astrophysics Data System (ADS)
Appia, Vikram; Patil, Uday; Das, Bipul
2010-03-01
Pulmonary fissures separate human lungs into five distinct regions called lobes. Detection of fissure is essential for localization of the lobar distribution of lung diseases, surgical planning and follow-up. Treatment planning also requires calculation of the lobe volume. This volume estimation mandates accurate segmentation of the fissures. Presence of other structures (like vessels) near the fissure, along with its high variational probability in terms of position, shape etc. makes the lobe segmentation a challenging task. Also, false incomplete fissures and occurrence of diseases add to the complications of fissure detection. In this paper, we propose a semi-automated fissure segmentation algorithm using a minimal path approach on CT images. An energy function is defined such that the path integral over the fissure is the global minimum. Based on a few user defined points on a single slice of the CT image, the proposed algorithm minimizes a 2D energy function on the sagital slice computed using (a) intensity (b) distance of the vasculature, (c) curvature in 2D, (d) continuity in 3D. The fissure is the infimum energy path between a representative point on the fissure and nearest lung boundary point in this energy domain. The algorithm has been tested on 10 CT volume datasets acquired from GE scanners at multiple clinical sites. The datasets span through different pathological conditions and varying imaging artifacts.
Proc. IWPEC-04, Vol. 3162 in LNCS, pp. 174-186, Springer, 2004 Perfect Path Phylogeny Haplotyping
Niedermeier, Rolf
algorithms are known for computing perfect phylo- genies from complete and error-free input instances for the case of complete and error-free input data [1, 2]. In the special case where perfect path phylogenies perfect phylogeny is NP-hard [8]. This is even true for the restricted case of path phylogenies [5
Quantifying the reliability of dispersal paths in connectivity networks.
Hock, Karlo; Mumby, Peter J
2015-04-01
Many biological systems, from fragmented landscapes to host populations, can be represented as networks of connected habitat patches. Links between patches in these connectivity networks can represent equally diverse processes, from individuals moving through the landscape to pathogen transmissions or successive colonization events in metapopulations. Any of these processes can be characterized as stochastic, with functional links among patches that exist with various levels of certainty. This stochasticity then needs to be reflected in the algorithms that aim to predict the dispersal routes in these networks. Here we adapt the concept of reliability to characterize the likelihood that a specific path will be used for dispersal in a probabilistic connectivity network. The most reliable of the paths that connect two patches will then identify the most likely sequence of intermediate steps between these patches. Path reliability will be sensitive to targeted disruptions of individual links that form the path, and this can then be used to plan the interventions aimed at either preserving or disrupting the dispersal along that path. The proposed approach is general, and can be used to identify the most likely dispersal routes in various contexts, such as predicting patterns of migrations, colonizations, invasions and epidemics. PMID:25716187
An Efficient Evolutionary Algorithm for the Degree-Constrained Minimum Spanning Tree Problem
R. Raidl
2000-01-01
The representation of candidate solutions and the variation operators are fundamental design choices in an evolutionary algorithm (EA). This paper proposes a novel representation technique and suitable variation operators for the degree-constrained minimum spanning tree problem. For a weighted, undirected graph G(V;E), this problem seeks to identify the shortest spanning tree whose node degrees do not exceed an upper bound
Primal-Dual Target-Following Algorithms for Linear Programming
B. Jansen; C. Roos; T. Terlaky; J. ph. Vial
1993-01-01
In this paper we propose a method for linear programming with the propertythat, starting from an initial non--central point, it generates iterates that simultaneouslyget closer to optimality and closer to centrality. The iteratesfollow paths that in the limit are tangential to the central path. Along withthe convergence analysis we provide a general framework which enables us toanalyze various primal--dual algorithms
ERIC Educational Resources Information Center
Suydam, Marilyn N., Ed.; Osborne, Alan R., Ed.
This volume contains a series of papers on algorithmic learning. Included are six reviews of research pertaining to various aspects of algorithmic learning, six reports of pilot experiments in this area, a theoretical discussion of "The Conditions for Algorithmic Imagination," and an annotated bibliography. All the papers assume a common…
NSDL National Science Digital Library
Dr Gene Tagliarini
CSC 325. (MAT 325) Numerical Algorithms (3) Prerequisite: CSC 112 or 121, MAT 162. An introduction to the numerical algorithms fundamental to scientific computer work. Includes elementary discussion of error, polynomial interpolation, quadrature, linear systems of equations, solution of nonlinear equations and numerical solution of ordinary differential equations. The algorithmic approach and the efficient use of the computer are emphasized.
Autonomous Path-Following by Approximate Inverse Dynamics and Vector Field Prediction
NASA Astrophysics Data System (ADS)
Gerlach, Adam R.
In this dissertation, we develop two general frameworks for the navigation and control of autonomous vehicles that must follow predefined paths. These frameworks are designed such that they inherently provide accurate navigation and control of a wide class of systems directly from a model of the vehicle's dynamics. The first framework introduced is the inverse dynamics by radial basis function (IDRBF) algorithm, which exploits the best approximation property of radial basis functions to accurately approximate the inverse dynamics of non-linear systems. This approximation is then used with the known, desired state of the system at a future time point to generate the system input that must be applied to reach the desired state in the specified time interval. The IDRBF algorithm is then tested on two non-linear dynamic systems, and accurate path-following is demonstrated. The second framework introduced is the predictive vector field (PVF) algorithm. The PVF algorithm uses the equations of motion and constraints of the system to predict a set of reachable states by sampling the system's configuration space. By finding and minimizing a continuous mapping between the system's configuration space and a cost space relating the reachable states of the system with a vector field (VF), one can determine the system inputs required to follow the VF. The PVF algorithm is then tested on the Dubin's vehicle and aircraft models, and accurate path-following is demonstrated. As the PVF algorithm's performance is dependent on the quality of the underlying system model and VF, algorithms are introduced for automatically generating VFs for constant altitude paths defined by a series of waypoints and for handling modeling uncertainties. Additionally, we provide a mathematical proof showing that this method can automatically produce VFs of the desired form. To handle modeling uncertainties, we enhance the PVF algorithm with the Gaussian process machine learning framework, enabling the algorithm to learn the true system model, online, in the presence of measurement noise. We call this algorithm the PVF-GP algorithm. To demonstrate the PVF-GP algorithm, we compare its performance to the PVF algorithm after introducing modeling uncertainties to the underlying system model and introducing an external wind disturbance. Test results show the PVF-GP algorithm offers dramatically improved path-following performance over the non-learning PVF algorithm.
Path planning for robotic truss assembly
NASA Technical Reports Server (NTRS)
Sanderson, Arthur C.
1993-01-01
A new Potential Fields approach to the robotic path planning problem is proposed and implemented. Our approach, which is based on one originally proposed by Munger, computes an incremental joint vector based upon attraction to a goal and repulsion from obstacles. By repetitively adding and computing these 'steps', it is hoped (but not guaranteed) that the robot will reach its goal. An attractive force exerted by the goal is found by solving for the the minimum norm solution to the linear Jacobian equation. A repulsive force between obstacles and the robot's links is used to avoid collisions. Its magnitude is inversely proportional to the distance. Together, these forces make the goal the global minimum potential point, but local minima can stop the robot from ever reaching that point. Our approach improves on a basic, potential field paradigm developed by Munger by using an active, adaptive field - what we will call a 'flexible' potential field. Active fields are stronger when objects move towards one another and weaker when they move apart. An adaptive field's strength is individually tailored to be just strong enough to avoid any collision. In addition to the local planner, a global planning algorithm helps the planner to avoid local field minima by providing subgoals. These subgoals are based on the obstacles which caused the local planner to fail. A best-first search algorithm A* is used for graph search.
Mixed time slicing in path integral simulations
Steele, Ryan P.; Zwickl, Jill; Shushkov, Philip; Tully, John C. [Department of Chemistry, Yale University, New Haven, Connecticut 06405 (United States)
2011-02-21
A simple and efficient scheme is presented for using different time slices for different degrees of freedom in path integral calculations. This method bridges the gap between full quantization and the standard mixed quantum-classical (MQC) scheme and, therefore, still provides quantum mechanical effects in the less-quantized variables. Underlying the algorithm is the notion that time slices (beads) may be 'collapsed' in a manner that preserves quantization in the less quantum mechanical degrees of freedom. The method is shown to be analogous to multiple-time step integration techniques in classical molecular dynamics. The algorithm and its associated error are demonstrated on model systems containing coupled high- and low-frequency modes; results indicate that convergence of quantum mechanical observables can be achieved with disparate bead numbers in the different modes. Cost estimates indicate that this procedure, much like the MQC method, is most efficient for only a relatively few quantum mechanical degrees of freedom, such as proton transfer. In this regime, however, the cost of a fully quantum mechanical simulation is determined by the quantization of the least quantum mechanical degrees of freedom.
On hallucinated garden paths UC San Diego
On hallucinated garden paths Roger Levy UC San Diego Department of Linguistics 2010 LSA Annual., 1995) #12;Garden-pathing in incremental parsing Â· Garden-path sentence a consequence of incrementality recent examples don't match this definition Â· Tabor et al. (2004): garden-paths on continuous substrings
A new approach to the maximum flow problem
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
A Synthesized Heuristic Task Scheduling Algorithm
Dai, Yanyan; Zhang, Xiangli
2014-01-01
Aiming at the static task scheduling problems in heterogeneous environment, a heuristic task scheduling algorithm named HCPPEFT is proposed. In task prioritizing phase, there are three levels of priority in the algorithm to choose task. First, the critical tasks have the highest priority, secondly the tasks with longer path to exit task will be selected, and then algorithm will choose tasks with less predecessors to schedule. In resource selection phase, the algorithm is selected task duplication to reduce the interresource communication cost, besides forecasting the impact of an assignment for all children of the current task permits better decisions to be made in selecting resources. The algorithm proposed is compared with STDH, PEFT, and HEFT algorithms through randomly generated graphs and sets of task graphs. The experimental results show that the new algorithm can achieve better scheduling performance. PMID:25254244
Essential paths space on ADE SU(3) graphs: A geometric approach
Jesus A. Pineda; E. Isasi; M. I. Caicedo
2014-07-10
Using triangular sequences of vertices as an analogue for a backtracking step on a path in SU(3), we offer a geometric understanding of the path creation and annihilation operators in terms of creation and annihilation of triangular sequences of vertices. We find that our implementation of these operators yields the expected mathematical properties as applied to essential and non essential paths. We prove that the space of paths of a given length can be decomposed in a way similar to that shown previously for SU(2), which is to say that one can write a path of a given length as a direct sum of sub-spaces which are ortogonal subspaces constructed by recurrent applications of the path creation operator on subspaces of essential paths of shorter length. We propose an algorithm that shows explicitly how a given path can be obtained as an interated and ordered application of the creation operator on a path belonging to the kernel of the annihilation operator.
Multi-horizon reactive and deliberative path planning for autonomous cross-country navigation
NASA Astrophysics Data System (ADS)
Kluge, Karl C.; Morgenthaler, Matt K.
2004-09-01
As part of the Raptor system developed for DARPA's PerceptOR program, three path planning methods have been integrated together in the framework of a command-arbitration based architecture. These methods combine reactive and deliberative elements, performing path planning within different planning horizons. Short range path planning (< 10 m) is done by a module called OAradials. OAradials is purely reactive, evaluating arcs corresponding to possible steering commands for the proximity of discrete obstacles, abrupt elevation changes, and unsafe slope conditions. Medium range path planning (<30 m) is performed by a module called Biased Random Trees - Follow Path (BRT-FP). Based on LaValle and Kuffner's rapidly exploring random trees planning algorithm, BRT-FP continuously evaluates the local terrain map in order to generate a good path that advances the robot towards the next intermediate waypoint in a user-specified plan. A pure-pursuit control algorithm generates candidate steering commands intended to keep the robot on the generated path. Long range path planning is done by the Dynamic Planner (DPlanner) using Stentz' D* algorithm. Use of D* allows efficient exploitation of prior terrain data and dynamic replanning as terrain is explored. Outputs from DPlanner generate intermediate goal points that are fed to the BRT-FP planner. A command-level arbitration scheme selects steering commands based on the weighted sum of the steering preferences generated by the OAradials and BRT-FP path planning behaviors. This system has been implemented on an ATV platform that has been actuated for autonomous operation, and tested on realistic cross-country terrain in the context of the PerceptOR program.
NASA Technical Reports Server (NTRS)
Zuk, J.
1976-01-01
Improved gas-path seals are needed for better fuel economy, longer performance retention, and lower maintenance, particularly in advanced, high-performance gas turbine engines. Problems encountered in gas-path sealing are described, as well as new blade-tip sealing approaches for high-pressure compressors and turbines. These include a lubricant coating for conventional, porous-metal, rub-strip materials used in compressors. An improved hot-press metal alloy shows promise to increase the operating surface temperatures of high-pressure-turbine, blade-tip seals to 1450 K (2150 F). Three ceramic seal materials are also described that have the potential to allow much higher gas-path surface operating temperatures than are possible with metal systems.
Research on global path planning based on ant colony optimization for AUV
NASA Astrophysics Data System (ADS)
Wang, Hong-Jian; Xiong, Wei
2009-03-01
Path planning is an important issue for autonomous underwater vehicles (AUVs) traversing an unknown environment such as a sea floor, a jungle, or the outer celestial planets. For this paper, global path planning using large-scale chart data was studied, and the principles of ant colony optimization (ACO) were applied. This paper introduced the idea of a visibility graph based on the grid workspace model. It also brought a series of pheromone updating rules for the ACO planning algorithm. The operational steps of the ACO algorithm are proposed as a model for a global path planning method for AUV. To mimic the process of smoothing a planned path, a cutting operator and an insertion-point operator were designed. Simulation results demonstrated that the ACO algorithm is suitable for global path planning. The system has many advantages, including that the operating path of the AUV can be quickly optimized, and it is shorter, safer, and smoother. The prototype system successfully demonstrated the feasibility of the concept, proving it can be applied to surveys of unstructured unmanned environments.
A Dynamic Navigation Algorithm Considering Network Disruptions
NASA Astrophysics Data System (ADS)
Jiang, J.; Wu, L.
2014-04-01
In traffic network, link disruptions or recoveries caused by sudden accidents, bad weather and traffic congestion, lead to significant increase or decrease in travel times on some network links. Similar situation also occurs in real-time emergency evacuation plan in indoor areas. As the dynamic nature of real-time network information generates better navigation solutions than the static one, a real-time dynamic navigation algorithm for emergency evacuation with stochastic disruptions or recoveries in the network is presented in this paper. Compared with traditional existing algorithms, this new algorithm adjusts pre-existing path to a new optimal one according to the changing link travel time. With real-time network information, it can provide the optional path quickly to adapt to the rapid changing network properties. Theoretical analysis and experimental results demonstrate that this proposed algorithm performs a high time efficiency to get exact solution and indirect information can be calculated in spare time.
Finding Out Critical Points For Real-Time Path Planning
NASA Astrophysics Data System (ADS)
Chen, Wei
1989-03-01
Path planning for a mobile robot is a classic topic, but the path planning under real-time environment is a different issue. The system sources including sampling time, processing time, processes communicating time, and memory space are very limited for this type of application. This paper presents a method which abstracts the world representation from the sensory data and makes the decision as to which point will be a potentially critical point to span the world map by using incomplete knowledge about physical world and heuristic rule. Without any previous knowledge or map of the workspace, the robot will determine the world map by roving through the workspace. The computational complexity for building and searching such a map is not more than O( n2 ) The find-path problem is well-known in robotics. Given an object with an initial location and orientation, a goal location and orientation, and a set of obstacles located in space, the problem is to find a continuous path for the object from the initial position to the goal position which avoids collisions with obstacles along the way. There are a lot of methods to find a collision-free path in given environment. Techniques for solving this problem can be classified into three approaches: 1) the configuration space approach [1],[2],[3] which represents the polygonal obstacles by vertices in a graph. The idea is to determine those parts of the free space which a reference point of the moving object can occupy without colliding with any obstacles. A path is then found for the reference point through this truly free space. Dealing with rotations turns out to be a major difficulty with the approach, requiring complex geometric algorithms which are computationally expensive. 2) the direct representation of the free space using basic shape primitives such as convex polygons [4] and overlapping generalized cones [5]. 3) the combination of technique 1 and 2 [6] by which the space is divided into the primary convex region, overlap region and obstacle region, then obstacle boundaries with attribute values are represented by the vertices of the hypergraph. The primary convex region and overlap region are represented by hyperedges, the centroids of overlap form the critical points. The difficulty is generating segment graph and estimating of minimum path width. The all techniques mentioned above need previous knowledge about the world to make path planning and the computational cost is not low. They are not available in an unknow and uncertain environment. Due to limited system resources such as CPU time, memory size and knowledge about the special application in an intelligent system (such as mobile robot), it is necessary to use algorithms that provide the good decision which is feasible with the available resources in real time rather than the best answer that could be achieved in unlimited time with unlimited resources. A real-time path planner should meet following requirements: - Quickly abstract the representation of the world from the sensory data without any previous knowledge about the robot environment. - Easily update the world model to spell out the global-path map and to reflect changes in the robot environment. - Must make a decision of where the robot must go and which direction the range sensor should point to in real time with limited resources. The method presented here assumes that the data from range sensors has been processed by signal process unite. The path planner will guide the scan of range sensor, find critical points, make decision where the robot should go and which point is poten- tial critical point, generate the path map and monitor the robot moves to the given point. The program runs recursively until the goal is reached or the whole workspace is roved through.
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.
A transitive closure algorithm for test generation
Srimat T. Chakradhar; Vishwani D. Agrawal; Steven G. Rothweiler
1993-01-01
A transitive-closure-based test generation algorithm is presented. A test is obtained by determining signal values that satisfy a Boolean equation derived from the neural network model of the circuit incorporating necessary conditions for fault activation and path sensitization. The algorithm is a sequence of two main steps that are repeatedly executed: transitive closure computation and decision-making. A key feature of
Kinetic Constrained Optimization of the Golf Swing Hub Path
Nesbit, Steven M.; McGinnis, Ryan S.
2014-01-01
This study details an optimization of the golf swing, where the hand path and club angular trajectories are manipulated. The optimization goal was to maximize club head velocity at impact within the interaction kinetic limitations (force, torque, work, and power) of the golfer as determined through the analysis of a typical swing using a two-dimensional dynamic model. The study was applied to four subjects with diverse swing capabilities and styles. It was determined that it is possible for all subjects to increase their club head velocity at impact within their respective kinetic limitations through combined modifications to their respective hand path and club angular trajectories. The manner of the modifications, the degree of velocity improvement, the amount of kinetic reduction, and the associated kinetic limitation quantities were subject dependent. By artificially minimizing selected kinetic inputs within the optimization algorithm, it was possible to identify swing trajectory characteristics that indicated relative kinetic weaknesses of a subject. Practical implications are offered based upon the findings of the study. Key Points The hand path trajectory is an important characteristic of the golf swing and greatly affects club head velocity and golfer/club energy transfer. It is possible to increase the energy transfer from the golfer to the club by modifying the hand path and swing trajectories without increasing the kinetic output demands on the golfer. It is possible to identify relative kinetic output strengths and weakness of a golfer through assessment of the hand path and swing trajectories. Increasing any one of the kinetic outputs of the golfer can potentially increase the club head velocity at impact. The hand path trajectory has important influences over the club swing trajectory. PMID:25435779
Kinetic constrained optimization of the golf swing hub path.
Nesbit, Steven M; McGinnis, Ryan S
2014-12-01
This study details an optimization of the golf swing, where the hand path and club angular trajectories are manipulated. The optimization goal was to maximize club head velocity at impact within the interaction kinetic limitations (force, torque, work, and power) of the golfer as determined through the analysis of a typical swing using a two-dimensional dynamic model. The study was applied to four subjects with diverse swing capabilities and styles. It was determined that it is possible for all subjects to increase their club head velocity at impact within their respective kinetic limitations through combined modifications to their respective hand path and club angular trajectories. The manner of the modifications, the degree of velocity improvement, the amount of kinetic reduction, and the associated kinetic limitation quantities were subject dependent. By artificially minimizing selected kinetic inputs within the optimization algorithm, it was possible to identify swing trajectory characteristics that indicated relative kinetic weaknesses of a subject. Practical implications are offered based upon the findings of the study. Key PointsThe hand path trajectory is an important characteristic of the golf swing and greatly affects club head velocity and golfer/club energy transfer.It is possible to increase the energy transfer from the golfer to the club by modifying the hand path and swing trajectories without increasing the kinetic output demands on the golfer.It is possible to identify relative kinetic output strengths and weakness of a golfer through assessment of the hand path and swing trajectories.Increasing any one of the kinetic outputs of the golfer can potentially increase the club head velocity at impact.The hand path trajectory has important influences over the club swing trajectory. PMID:25435779
Identifying a Criminal's Network of Trust
Magalingam, Pritheega; Davis, Stephen
2015-01-01
Tracing criminal ties and mining evidence from a large network to begin a crime case analysis has been difficult for criminal investigators due to large numbers of nodes and their complex relationships. In this paper, trust networks using blind carbon copy (BCC) emails were formed. We show that our new shortest paths network search algorithm combining shortest paths and network centrality measures can isolate and identify criminals' connections within a trust network. A group of BCC emails out of 1,887,305 Enron email transactions were isolated for this purpose. The algorithm uses two central nodes, most influential and middle man, to extract a shortest paths trust network.
Benchmarking Gas Path Diagnostic Methods: A Public Approach
NASA Technical Reports Server (NTRS)
Simon, Donald L.; Bird, Jeff; Davison, Craig; Volponi, Al; Iverson, R. Eugene
2008-01-01
Recent technology reviews have identified the need for objective assessments of engine health management (EHM) technology. The need is two-fold: technology developers require relevant data and problems to design and validate new algorithms and techniques while engine system integrators and operators need practical tools to direct development and then evaluate the effectiveness of proposed solutions. This paper presents a publicly available gas path diagnostic benchmark problem that has been developed by the Propulsion and Power Systems Panel of The Technical Cooperation Program (TTCP) to help address these needs. The problem is coded in MATLAB (The MathWorks, Inc.) and coupled with a non-linear turbofan engine simulation to produce "snap-shot" measurements, with relevant noise levels, as if collected from a fleet of engines over their lifetime of use. Each engine within the fleet will experience unique operating and deterioration profiles, and may encounter randomly occurring relevant gas path faults including sensor, actuator and component faults. The challenge to the EHM community is to develop gas path diagnostic algorithms to reliably perform fault detection and isolation. An example solution to the benchmark problem is provided along with associated evaluation metrics. A plan is presented to disseminate this benchmark problem to the engine health management technical community and invite technology solutions.
PATH DECOMPOSITION METHOD FOR POTENTIALS
A. Laissaoui; L. Chetouani
We know all that thanks the development of the various formulations, moreover all equiva- lent, the physical phenomena explained by quantum mechanics are understood better. Among these formulations, we can quote most known because of its success: the formulation of Feyn- man (1) which uses the tool of the path integral. Not a long time ago, obtaining solutions for certain
C. S. Feibel
2004-01-01
A complex series of evolutionary steps, contingent upon a dynamic environmental context and a long biological heritage, have led to the ascent of Homo sapiens as a dominant component of the modern biosphere. In a field where missing links still abound and new discoveries regularly overturn theoretical paradigms, our understanding of the path of human evolution has made tremendous advances
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.
Career Paths in Environmental Sciences
Career paths, current and future, in the environmental sciences will be discussed, based on experiences and observations during the author's 40 + years in the field. An emphasis will be placed on the need for integrated, transdisciplinary systems thinking approaches toward achie...
Equivariant Localization of Path Integrals
Richard J. Szabo
1996-08-12
We review equivariant localization techniques for the evaluation of Feynman path integrals. We develop systematic geometric methods for studying the semi-classical properties of phase space path integrals for dynamical systems, emphasizing the relations with integrable and topological quantum field theories. Beginning with a detailed review of the relevant mathematical background -- equivariant cohomology and the Duistermaat-Heckman theorem, we demonstrate how the localization ideas are related to classical integrability and how they can be formally extended to derive explicit localization formulas for path integrals in special instances using BRST quantization techniques. Various loop space localizations are presented and related to notions in quantum integrability and topological field theory. We emphasize the common symmetries that such localizable models always possess and use these symmetries to discuss the range of applicability of the localization formulas. A number of physical and mathematical applications are presented in connection with elementary quantum mechanics, Morse theory, index theorems, character formulas for semi-simple Lie groups, quantization of spin systems, unitary integrations in matrix models, modular invariants of Riemann surfaces, supersymmetric quantum field theories, two-dimensional Yang-Mills theory, conformal field theory, cohomological field theories and the loop expansion in quantum field theory. Some modern techniques of path integral quantization, such as coherent state methods, are also discussed. The relations between equivariant localization and other ideas in topological field theory, such as the Batalin-Fradkin-Vilkovisky and Mathai-Quillen formalisms, are presented.
Employer Resource Manual. Project Path.
ERIC Educational Resources Information Center
Kane, Karen R.; Del George, Eve
Project Path at Illinois' College of DuPage was established to provide pre-employment training and career counseling for disabled students. To encourage the integration of qualified individuals with disabilities into the workplace, the project compiled this resource manual for area businesses, providing tips for interacting with disabled people…
Perceived Shrinkage of Motion Paths
ERIC Educational Resources Information Center
Sinico, Michele; Parovel, Giulia; Casco, Clara; Anstis, Stuart
2009-01-01
We show that human observers strongly underestimate a linear or circular trajectory that a luminous spot follows in the dark. At slow speeds, observers are relatively accurate, but, as the speed increases, the size of the path is progressively underestimated, by up to 35%. The underestimation imposes little memory load and does not require…
Low bias integrated path estimators
James M. Calvin
2007-01-01
We consider the problem of estimating the time-average variance constant for a stationary process. A previous paper described an approach based on multiple integrations of the simulation output path, and described the efficiency improvement that can result compared with the method of batch means (which is a special case of the method). In this paper we describe versions of the
Kinsey, Stephen
was monitored during recovery from anaerobic, burst exercise in white and dark muscle, and in hemolymph4045 Muscle fibers typically fall within a size range of 10100·µm along the shortest axis (e from mitochondria to sites of ATP demand (Mainwood and Rakusan, 1982). However, some muscle fibers from
Obstacle Bypassing in Optimal Ship Routing Using Simulated Annealing
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.
QoS based Distributed Multipath Routing Algorithm for IPv6
Muhammad Orner Farooq; Sadia Aziz
2008-01-01
In this paper we propose QoS based distributed multipath routing algorithm for IPv6 (QoS-MPR). The algorithm is able to work alongside traditional routing algorithms and it can construct label switched paths in order to provide rigorous QoS guarantees. QoS-MPR is developed to work with differentiated services architecture and its capability to establish label switched paths allows us to inject more
Assessing perceptions about hazardous substances (PATHS): the PATHS questionnaire.
Rubin, G James; Amlôt, Richard; Page, Lisa; Pearce, Julia; Wessely, Simon
2013-08-01
How people perceive the nature of a hazardous substance may determine how they respond when potentially exposed to it. We tested a new Perceptions AbouT Hazardous Substances (PATHS) questionnaire. In Study 1 (N = 21), we assessed the face validity of items concerning perceptions about eight properties of a hazardous substance. In Study 2 (N = 2030), we tested the factor structure, reliability and validity of the PATHS questionnaire across four qualitatively different substances. In Study 3 (N = 760), we tested the impact of information provision on Perceptions AbouT Hazardous Substances scores. Our results showed that our eight measures demonstrated good reliability and validity when used for non-contagious hazards. PMID:23104995
A Reliable Multicast Algorithm for Mobile Ad Hoc Networks
Thiagaraja Gopalsamy; Mukesh Singhal; Dhabaleswar K. Panda; P. Sadayappan
2002-01-01
A reliable multicast algorithm, called RMA, for mobile ad hoc networks is presented that is based on a new cost criterion, called link lifetime, for determining the optimal path between a pair of nodes. The algorithm has the characteristics of using an undirected graph for its routing operations rather than a fixed structure like a tree or a mesh. Previously
Hard paths, soft paths or no paths? Cross-cultural perceptions of water solutions
Hall, Sharon J.
status play in shaping how people conceptualize water solutions? 3) What role does water scarcity play selected based on their diversity in development status and water scarcity (Figure 1) Â· Participants no path (2 = 5.19, p = 0.02, = 0.22). Water Scarcity Â· Respondents from water-scarce sites were found
Vision-based path-planning in unstructured environments
Britta Hummel; Sören Kammel; Thao Dang; Christian Duchow; Christoph Stiller
Abstract — Autonomous driving in unstructed environments has attracted an unprecedented level of attention when the DARPA announced the Grand Challenge Competitions in 2004 and 2005. Autonomous driving involves (at least) three major subtasks: perception of the environment, path planning and subsequent vehicle control. Whereas the latter has proven a solved problem, the first two constituted, apart from hardware failures, the most prominent source of errors in both Grand Challenges. This paper presents a system for real-time feature detection and subsequent path planning based on multiple stereoscopic and monoscopic vision cues. The algorithm is, in principle, suitable for arbitrary environments as the features are not tailored to a particular application. A slightly modified version of the system described here has been succesfully used in the Qualifications and the Final Race of the Grand Challenge 2005 within the Desert Buckeyes’ autonomous vehicle. I.
NASA Astrophysics Data System (ADS)
Pérez, Alejandro; Tuckerman, Mark E.
2011-08-01
Higher order factorization schemes are developed for path integral molecular dynamics in order to improve the convergence of estimators for physical observables as a function of the Trotter number. The methods are based on the Takahashi-Imada and Susuki decompositions of the Boltzmann operator. The methods introduced improve the averages of the estimators by using the classical forces needed to carry out the dynamics to construct a posteriori weighting factors for standard path integral molecular dynamics. The new approaches are straightforward to implement in existing path integral codes and carry no significant overhead. The Suzuki higher order factorization was also used to improve the end-to-end distance estimator in open path integral molecular dynamics. The new schemes are tested in various model systems, including an ab initio path integral molecular dynamics calculation on the hydrogen molecule and a quantum water model. The proposed algorithms have potential utility for reducing the cost of path integral molecular dynamics calculations of bulk systems.