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

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

Link permanente para citações:

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

Fonte: Universidade Estadual Paulista
Publicador: Universidade Estadual Paulista

Tipo: Conferência ou Objeto de Conferência

ENG

Relevância na Pesquisa

35.93%

#Construction phase#GRASP#Multi-move path-relinking#Transmission expansion planning#Brazilian system#High quality#Initial solution#Investment costs#Meta heuristic algorithm#Meta-heuristics algorithms#Network models

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.

Link permanente para citações:

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

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%

#Reconhecimento de padrões#Reconhecimento em cenário aberto#Floresta de caminhos ótimos#Pattern recognition#Open set recognition#Optimum-path forest

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

Link permanente para citações:

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

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)

Link permanente para citações:

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

Fonte: Universidade de Tubinga
Publicador: Universidade de Tubinga

Tipo: Dissertação

EN

Relevância na Pesquisa

36.05%

#Robotik#600#Mobile Roboter , Multi-Roboter-Systeme , Koordinerte Pfadverfolgungsregelung , Formationskontrolle#Mobile Robots , Multi-Robot Systems , Coordinated Path Following Control , Formation Control

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

Link permanente para citações:

## Empirical Simultaneous Confidence Regions for Path-Forecasts

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%

#path forecast#forecast uncertainty#simultaneous confidence region#Scheffé’s S-method#Mahalanobis distance#false discovery rate#C32#C52#C53

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.

Link permanente para citações:

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

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%

#Path exploration#Path computation#Routing switches#Shortest path bridges#All-Path#Automatización#Automation#CIENCIAS TECNOLÓGICAS#TECHNOLOGY

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

Link permanente para citações:

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

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

Link permanente para citações:

## Layered path planning for an autonomous mobile robot

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

Link permanente para citações:

## Path tracking using simple planar curves

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%

#Operations research#Robots#Control systems#Mathematical models#Robots Software#Path planning#Obstacle Avoidance#Autonomous Vehicle Motion

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

Link permanente para citações:

## On Brownian motion, simple paths, and loops

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

Link permanente para citações:

## All Colors Shortest Path Problem

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.

Link permanente para citações:

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

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

Link permanente para citações:

## A Morphological Adaptation Approach to Path Planning Inspired by Slime Mould

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.

Link permanente para citações:

## Longest-path attacks on complex networks

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

Link permanente para citações:

## On the weights of simple paths in weighted complete graphs

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.

Link permanente para citações:

## A Trichotomy for Regular Simple Path Queries on Graphs

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

Link permanente para citações:

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

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

Link permanente para citações:

## On $r$-Simple $k$-Path

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.

Link permanente para citações:

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

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

Link permanente para citações: