Página 1 dos resultados de 2519 itens digitais encontrados em 0.016 segundos

Computational experiments with a lazy version of a  K  quickest simple path ranking algorithm

Pascoal, M.; Captivo, M.; Clímaco, J.
Fonte: Universidade de Coimbra Publicador: Universidade de Coimbra
Tipo: Artigo de Revista Científica
ENG
Relevância na Pesquisa
46.25%
Abstract The quickest path problem is related to the classical shortest path problem, but its objective function concerns the transmission time of a given amount of data throughout a path, which involves both cost and capacity. The K-quickest simple paths problem generalises the latter, by looking for a given number K of simple paths in non-decreasing order of transmission time. Two categories of algorithms are known for ranking simple paths according to the transmission time. One is the adaptation of deviation algorithms for ranking shortest simple paths (Pascoal et al. in Comput. Oper. Res. 32(3):509–520, 2005; Rosen et al. in Comput. Oper. Res. 18(6):571–584, 1991), and another is based on ranking shortest simple paths in a sequence of networks with fixed capacity lower bounds (Chen in Inf. Process. Lett. 50:89–92, 1994), and afterwards selecting the K quickest ones. After reviewing the quickest path and the K-quickest simple paths problems we describe a recent algorithm for ranking quickest simple paths (Pascoal et al. in Ann. Oper. Res. 147(1):5–21, 2006). This is a lazy version of Chen’s algorithm, able to interchange the calculation of new simple paths and the output of each k-quickest simple path. Finally...

Evolutionary multi-move path-relinking for transmission network expansion planning

Rahmani, M.; Rashidinejad, M.; Carreno, E. M.; Romero, R. A.
Fonte: Universidade Estadual Paulista Publicador: Universidade Estadual Paulista
Tipo: Conferência ou Objeto de Conferência
ENG
Relevância na Pesquisa
35.93%
This paper presents the application of a new metaheuristic algorithm to solve the transmission expansion planning problem. A simple heuristic, using a relaxed network model associated with cost perturbation, is applied to generate a set of high quality initial solutions with different topologies. The population is evolved using a multi-move path-relinking with the objective of finding minimum investment cost for the transmission expansion planning problem employing the DC representation. The algorithm is tested on the southern Brazilian system, obtaining the optimal solution for the system with better performance than similar metaheuristics algorithms applied to the same problem. ©2010 IEEE.

Open-set optimum-path forest classifier= : Classificador optimum-path forest para cenário aberto; Classificador optimum-path forest para cenário aberto

Pedro Ribeiro Mendes Júnior
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 22/08/2014 PT
Relevância na Pesquisa
35.98%
Em reconhecimento de padrões, um cenário aberto é aquele em que não há amostras de treinamento para algumas classes que podem aparecer durante o teste. Normalmente, muitas aplicações são inerentemente de cenário aberto. Consequentemente, as soluções bem sucedidas da literatura para cenário fechado nem sempre são adequadas para problemas de reconhecimento na prática. Nesse trabalho, propomos um novo classificador multiclasse para cenário aberto, que estende o classificador Optimum-Path Forest (OPF). O OPF é um classificador de padrões baseado em grafos, simples, independente de parâmetros, multiclasse e desenvolvido para para problemas de cenário fechado. O método que propomos, o Open-Set OPF (OSOPF), incorpora a capacidade de reconhecer as amostras pertencentes às classes que são desconhecidas no tempo de treinamento, sendo adequado para reconhecimento em cenário aberto. Além disso, propomos novas medidas para avaliação de classificadores propostos para problemas em cenário aberto. Nos experimentos, consideramos seis grandes bases de dados com diferentes cenários de reconhecimento e demonstramos que o OSOPF proposto supera significativamente as abordagens existentes na literatura.; An open-set recognition scenario is the one in which there are no a priori training samples for some classes that might appear during testing. Usually...

P-T Path of a Variscan Shear Zone recorded on Quartz-Aluminous Shearband Boudins

Rodrigues, Benedito C.; Pamplona, J.; Peternell, Mark; Moura, António; Schwindinger, Martin
Fonte: Universidade do Minho Publicador: Universidade do Minho
Tipo: Conferência ou Objeto de Conferência
Publicado em /09/2013 ENG
Relevância na Pesquisa
35.99%
The work is focused on the P-T path recorded on internal shearband boudin microstructures, developed during simple shear progressive deformation (Malpica-Lamego Ductile Shear Zone – MLDSZ, NW Portugal). In the studied area, MLDSZ is a NW-SE striking Variscan crustal shear zone with a subvertical and west-dipping foliation and a sub-horizontal stretching lineation; it is recorded as a heterogeneous simple shear zone with bulk left-lateral kinematics (Pamplona and Rodrigues, 2011). The deformation zone is marked by a generalized foliation (Sn) defined by Bt+Ms±Sil and a stretching mineral lineation marked by sillimanite fibres. Microstructural analysis, fluid inclusions studies, Raman spectroscopy, crystallographic preferred orientation on quartz grains and fractal geometry based analysis were applied to the boudins.; Fundação para a Ciência e a Tecnologia (FCT)

Coordinated Path Following Control and Formation Control of Mobile Robots; Koordinierte Pfadverfolgungsregelung und Formationskontrolle mobiler Roboter

Kanjanawanishkul, Kiattisin
Fonte: Universidade de Tubinga Publicador: Universidade de Tubinga
Tipo: Dissertação
EN
Relevância na Pesquisa
36.05%
Rapid advances in sensing, computing and communication technologies have led to considerably increased research activities in multi-robot systems over the last decade. Topics include multi-robot motion planning, cooperative manipulation, aerial applications involving cooperative exploration of the unknown environment, automated highway systems, software architectures for multi-robot systems, and formation control. Multi-robot systems have been proven to offer additional advantages in terms of flexibility in operating a group of robots and failure tolerance due to redundancy in available mobile robots. However, the benefits of using multi-robot teams do not come without cost. Coordinating teams of autonomous robots is much more challenging than maneuvering a single robot. This dissertation addresses formation control problems, which are among the most active research topics in multi-robot systems. Over the last two decades, there have been a large number of publications on this field, and it is still growing. Recently, this research has been extended to some related research areas, e.g., consensus problems and distributed control systems, imposing new challenges on formation control problems. In general, formation control subproblems addressed in the literature can be classified as formation shape generation...

Empirical Simultaneous Confidence Regions for Path-Forecasts

JORDÀ, Òscar; KNÜPPEL, Malte; MARCELLINO, Massimiliano
Fonte: Instituto Universitário Europeu Publicador: Instituto Universitário Europeu
Tipo: Trabalho em Andamento Formato: application/pdf; digital
EN
Relevância na Pesquisa
35.96%
Measuring and displaying uncertainty around path-forecasts, i.e. forecasts made in period T about the expected trajectory of a random variable in periods T+1 to T+H is a key ingredient for decision making under uncertainty. The probabilistic assessment about the set of possible trajectories that the variable may follow over time is summarized by the simultaneous confidence region generated from its forecast generating distribution. However, if the null model is only approximative or altogether unavailable, one cannot derive analytic expressions for this confidence region, and its non-parametric estimation is impractical given commonly available predictive sample sizes. Instead, this paper derives the approximate rectangular confidence regions that control false discovery rate error, which are a function of the predictive sample covariance matrix and the empirical distribution of the Mahalanobis distance of the path-forecast errors. These rectangular regions are simple to construct and appear to work well in a variety of cases explored empirically and by simulation. The proposed techniques are applied to provide con.dence bands around the Fed and Bank of England real-time path-forecasts of growth and inflation.

All-Path Bridging: Path Exploration Protocols for Data Center and Campus Networks

Rojas, Elisa; Ibañez, Guillermo; Giménez-Guzmán, Jose Manuel; Carral, Juan A.; García-Martínez, Alberto; Martínez-Yelmo, Isaías; Arco, Jose Manuel
Fonte: Universidade de Alcalá Publicador: Universidade de Alcalá
Tipo: info:eu-repo/semantics/article; info:eu-repo/semantics/acceptedVersion Formato: application/pdf
ENG
Relevância na Pesquisa
36.08%
Today, link-state routing protocols that compute multiple shortest paths predominate in data center and campus networks, where routing is performed either in layer three or in layer two using link-state routing protocols. But current proposals based on link-state routing do not adapt well to real time traffic variations and become very complex when attempting to balance the traffic load. We propose All-Path bridging, an evolution of the classical transparent bridging that forwards frames over shortest paths using the complete network topology, which overcomes the limitations of the spanning tree protocol. All-Path is a new frame routing paradigm based on the simultaneous exploration of all paths of the real network by a broadcast probe frame, instead of computing routes on the network graph. This paper presents All- Path switches and their differences with standard switches and describes ARP-Path protocol in detail, its path recovery mechanisms and compatibility with IEEE 802.1 standard bridges. ARP-Path is the first protocol variant of the All-Path protocol family. ARP-Path reuses the standard ARP Request and Reply packets to explore reactively the network and find the fastest path between two hosts. We compare its performance in terms of latency and load distribution with link-state shortest-path routing bridges...

All-path bridging: Path exploration as an efficient alternative to path computation in bridging standards

Ibáñez, Guillermo; Rojas, Elisa
Fonte: IEEE Publicador: IEEE
Tipo: info:eu-repo/semantics/acceptedVersion; info:eu-repo/semantics/conferenceObject
Publicado em /06/2013 ENG
Relevância na Pesquisa
36.05%
Link-state based routing protocols are dominant in Shortest Path Bridges (IEEE 802.1aq) and also at TRILL (IETF) Rbridges. Both standards propose a hybrid of switch and router adding a link state routing protocol in layer two that computes shortest paths between bridges. Surprisingly, path exploration mechanisms have not yet been considered at standardization bodies, in spite of some outstanding advantages: simplicity,instantaneous path adaptation to traffic load with load adaptive routing and low latency. We have developed All-path, a family of protocols based on simple path exploration mechanisms based on full flooding of a single frame, as an alternative to the "beatentrail" of path computation. Path exploration (either instantaneous or periodical, proactive or reactive) is an efficient alternative to path computation for bridged networks because the processing cost of address learning at bridges from broad cast frames is very low and Ethernet links provide very high link capacity so that the extra packet broad casts do not impact load significantly. Standardization groups should consider the application of path exploration (instantaneous or periodical, proactive or reactive) mechanisms in Audio Video Bridges and ingeneric bridging networks like campus and data centers to find redundant paths...

Layered path planning for an autonomous mobile robot

Haight, Timothy A.
Fonte: Monterey, California. Naval Postgraduate School Publicador: Monterey, California. Naval Postgraduate School
Tipo: Tese de Doutorado Formato: 111 p.;28 cm.
EN_US
Relevância na Pesquisa
36.09%
In order to continue to improve the usefulness of robots, it is becoming increasingly important to have them act as autonomous agents. A significant step toward this object is autonomous motion planning. This research was conducted as part of a broader effort to empower Yambico-11, a mobile robot under development at the Naval Postgraduate School, with ability to move autonomously. We believe that this problem is best attacked in layers. This thesis is our proposal for the initial layer. Given a robot's current location and its goal location, we use the homotopy relation to reduce the infinite set of path choices into a more manageable and smaller set of path classes. Specifically, we solve the problem of how to enable a robot to autonomously identify and label these classes of paths. We begin by decomposing the robot's operating environment into a collection of convex pieces called cells. The cells are transformed into a graph by adjacency. We show that every simple path on the graph corresponds to a unique simple homotopy class in the robot's world. We then search the graph to give each class a symbolic representation which also provides intermediate path planning clues. Subsequent layers can use these clues to form a more detailed plan. We implement the cell decomposition...

Path tracking using simple planar curves

Abresch, Richard James
Fonte: Monterey, California. Naval Postgraduate School Publicador: Monterey, California. Naval Postgraduate School
Tipo: Tese de Doutorado Formato: vi, 96 p.: ill.;28 cm.
EN_US
Relevância na Pesquisa
36.13%
Approved for public release, distribution unlimited; This thesis presents a method of controlling an autonomous vehicle's motion in a two dimensional environment. Its' purpose is to expand the functionality of a vehicle's motion by complementing a point to point path planning scheme with a path to path scheme. The method introduced in this paper will use the vehicle's position and the desired path to calculate the necessary curvature to effect movement onto the desired reference path. The reference path will be a simple planar curve, such as, a circle or line. After successful testing of an operating algorithm, the method shall be incorporated into a robot's software system. This path tracking method will lay the groundwork for a dynamic obstacle avoidance system for a mobile robot.; US Navy (USN) author

On Brownian motion, simple paths, and loops

Sapozhnikov, Artem; Shiraishi, Daisuke
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 15/12/2015
Relevância na Pesquisa
36.19%
We provide a decomposition of the trace of the Brownian motion into a simple path and an independent Brownian soup of loops that intersect the simple path. More precisely, we prove that any subsequential scaling limit of the loop erased random walk is a simple path (a new result in three dimensions), which can be taken as the simple path of the decomposition. In three dimensions, we also prove that the Hausdorff dimension of any such subsequential scaling limit lies in $(1,\frac53]$. We conjecture that our decomposition characterizes uniquely the law of the simple path. If so, our results would give a new strategy to the existence of the scaling limit of the loop erased random walk and its rotational invariance.; Comment: 38 pages

All Colors Shortest Path Problem

Bilge, Yunus Can; Çağatay, Doğukan; Genç, Begüm; Sarı, Mecit; Akcan, Hüseyin; Evrendilek, Cem
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 24/07/2015
Relevância na Pesquisa
36.07%
All Colors Shortest Path problem defined on an undirected graph aims at finding a shortest, possibly non-simple, path where every color occurs at least once, assuming that each vertex in the graph is associated with a color known in advance. To the best of our knowledge, this paper is the first to define and investigate this problem. Even though the problem is computationally similar to generalized minimum spanning tree, and the generalized traveling salesman problems, allowing for non-simple paths where a node may be visited multiple times makes All Colors Shortest Path problem novel and computationally unique. In this paper we prove that All Colors Shortest Path problem is NP-hard, and does not lend itself to a constant factor approximation. We also propose several heuristic solutions for this problem based on LP-relaxation, simulated annealing, ant colony optimization, and genetic algorithm, and provide extensive simulations for a comparative analysis of them. The heuristics presented are not the standard implementations of the well known heuristic algorithms, but rather sophisticated models tailored for the problem in hand. This fact is acknowledged by the very promising results reported.

A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs

Mertzios, George B.; Corneil, Derek G.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 26/04/2010
Relevância na Pesquisa
36.13%
Given a graph $G$, the longest path problem asks to compute a simple path of $G$ with the largest number of vertices. This problem is the most natural optimization version of the well known and well studied Hamiltonian path problem, and thus it is NP-hard on general graphs. However, in contrast to the Hamiltonian path problem, there are only few restricted graph families such as trees and some small graph classes where polynomial algorithms for the longest path problem have been found. Recently it has been shown that this problem can be solved in polynomial time on interval graphs by applying dynamic programming to a characterizing ordering of the vertices of the given graph \cite{longest-int-algo}, thus answering an open question. In the present paper, we provide the first polynomial algorithm for the longest path problem on a much greater class, namely on cocomparability graphs. Our algorithm uses a similar - but essentially simpler - dynamic programming approach, which is applied to a Lexicographic Depth First Search (LDFS) characterizing ordering of the vertices of a cocomparability graph. Therefore, our results provide evidence that this general dynamic programming approach can be used in a more general setting, leading to efficient algorithms for the longest path problem on greater classes of graphs. LDFS has recently been introduced in \cite{Corneil-LDFS08}. Since then...

A Morphological Adaptation Approach to Path Planning Inspired by Slime Mould

Jones, Jeff
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 11/03/2015
Relevância na Pesquisa
35.98%
Using a particle model of slime mould we demonstrate scoping experiments which explore how path planning may be performed by morphological adaptation. We initially demonstrate simple path planning by a shrinking blob of virtual plasmodium between two attractant sources within a polygonal arena. We examine the case where multiple paths are required and the subsequent selection of a single path from multiple options. Collision-free paths are implemented via repulsion from the borders of the arena. Finally, obstacle avoidance is implemented by repulsion from obstacles as they are uncovered by the shrinking blob. These examples show proof-of-concept results of path planning by morphological adaptation which complement existing research on path planning in novel computing substrates.

Longest-path attacks on complex networks

Pu, Cunlai; Cui, Wei
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 28/05/2014
Relevância na Pesquisa
36.11%
We investigate the longest-path attacks on complex networks. 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 totally 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.; Comment: 5 figures, 6pages

On the weights of simple paths in weighted complete graphs

Rubei, Elena
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 02/10/2012
Relevância na Pesquisa
35.99%
Consider a weighted graph G with n vertices, numbered by the set {1,...,n}. For any path p in G, we call w_G(p) the sum of the weights of the edges of the path and we define the multiset {\cal D}_{i,j} (G) = {w_G(p) | p simple path between i and j} We establish a criterion to say when, given a multisubset of the set of the real numbers there exists a weighted complete graph G such that the multisubset is equal to {\cal D}_{i,j} (G) for some i,j vertices of G. Besides we establish a criterion to say when, given for any i, j in {1,...,n} a multisubset of the set of the real numbers,{\cal D}_{i,j}, there exists a weighted complete graph G with vertices {1,...,n} such that {\cal D}_{i,j} (G)= {\cal D}_{i,j} for any i,j.

A Trichotomy for Regular Simple Path Queries on Graphs

Bagan, Guillaume; Bonifati, Angela; Groz, Benoit
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 31/12/2012
Relevância na Pesquisa
46.25%
Regular path queries (RPQs) select nodes connected by some path in a graph. The edge labels of such a path have to form a word that matches a given regular expression. We investigate the evaluation of RPQs with an additional constraint that prevents multiple traversals of the same nodes. Those regular simple path queries (RSPQs) find several applications in practice, yet they quickly become intractable, even for basic languages such as (aa)* or a*ba*. In this paper, we establish a comprehensive classification of regular languages with respect to the complexity of the corresponding regular simple path query problem. More precisely, we identify the fragment that is maximal in the following sense: regular simple path queries can be evaluated in polynomial time for every regular language L that belongs to this fragment and evaluation is NP-complete for languages outside this fragment. We thus fully characterize the frontier between tractability and intractability for RSPQs, and we refine our results to show the following trichotomy: Evaluations of RSPQs is either AC0, NL-complete or NP-complete in data complexity, depending on the regular language L. The fragment identified also admits a simple characterization in terms of regular expressions. Finally...

A Little More, a Lot Better: Improving Path Quality by a Simple Path Merging Algorithm

Raveh, Barak; Enosh, Angela; Halperin, Dan
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.09%
Sampling-based motion planners are an effective means for generating collision-free motion paths. However, the quality of these motion paths (with respect to quality measures such as path length, clearance, smoothness or energy) is often notoriously low, especially in high-dimensional configuration spaces. We introduce a simple algorithm for merging an arbitrary number of input motion paths into a hybrid output path of superior quality, for a broad and general formulation of path quality. Our approach is based on the observation that the quality of certain sub-paths within each solution may be higher than the quality of the entire path. A dynamic-programming algorithm, which we recently developed for comparing and clustering multiple motion paths, reduces the running time of the merging algorithm significantly. We tested our algorithm in motion-planning problems with up to 12 degrees of freedom. We show that our algorithm is able to merge a handful of input paths produced by several different motion planners to produce output paths of much higher quality.; Comment: 8 pages, 5 figures

On $r$-Simple $k$-Path

Abasi, Hasan; Bshouty, Nader H.; Gabizon, Ariel; Haramaty, Elad
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.28%
An $r$-simple $k$-path is a {path} in the graph of length $k$ that passes through each vertex at most $r$ times. The $r$-SIMPLE $k$-PATH problem, given a graph $G$ as input, asks whether there exists an $r$-simple $k$-path in $G$. We first show that this problem is NP-Complete. We then show that there is a graph $G$ that contains an $r$-simple $k$-path and no simple path of length greater than $4\log k/\log r$. So this, in a sense, motivates this problem especially when one's goal is to find a short path that visits many vertices in the graph while bounding the number of visits at each vertex. We then give a randomized algorithm that runs in time $$\mathrm{poly}(n)\cdot 2^{O( k\cdot \log r/r)}$$ that solves the $r$-SIMPLE $k$-PATH on a graph with $n$ vertices with one-sided error. We also show that a randomized algorithm with running time $\mathrm{poly}(n)\cdot 2^{(c/2)k/ r}$ with $c<1$ gives a randomized algorithm with running time $\poly(n)\cdot 2^{cn}$ for the Hamiltonian path problem in a directed graph - an outstanding open problem. So in a sense our algorithm is optimal up to an $O(\log r)$ factor.

A greedy approximation algorithm for the longest path problem in undirected graphs

Pongrácz, Lajos L.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.03%
In graph theory, the longest path problem is the problem of finding a simple path of maximum length in a given graph. For some small classes of graphs, the problem can be solved in polynomial time [2, 4], but it remains NP-hard on general graphs, since it includes the Hamiltonian path problem as a special case [3]. Motivated by finding a simple, quick algorithm for finding long paths in large graphs, in this paper we show a greedy algorithm with a time complexity of O(n^2 (n+m)), where n is the number of the vertices and m is the number of edges.; Comment: 6 pages, 3 figures Withdrawn due to an error in search subroutine, 2nd figure and time complexity