Search

This research designs an intelligent parking system including service application layer, perception layer, data analysis layer, and management layer. The network system adopts opm15 system, and the parking space recognition adopts improved convolution neural networks (CNNs) algorithm and image recognition technology. Firstly, the parking space is occupied and located, and the shortest path (Dynamic Programming, DP) is selected. In order to describe the path algorithm, the parking system model is established. Aiming at the problems of DP low power and adjacent path interference in the path detection system, a method of combining interference elimination technology with enhanced detector technology is proposed to effectively eliminate the interference path signal and improve the performance of the intelligent parking system. In order to verify whether the CNNs system designed in this study has advantages, the simulation experiments of CNNs, ZigBee, and manual parking are carried out. The results show that the parking system designed in this study can control the parking error, has smaller parking error than ZigBee, and has more than 25.64% less parking time than ZigBee, and more than 34.83% less time than manual parking. In terms of parking energy consumption, when there are less free parking spaces, CNNs have lower energy consumption.

An original graph-based model and algorithm for optimal industrial task scheduling are proposed in this article. The innovative algorithm designed, dubbed “Dijkstra optimal tasking” (DOT), is suitable for fully distributed task scheduling of autonomous industrial agents for optimal resource allocation, including energy use. The algorithm was designed starting from graph theory fundamentals, from the ground up, to guarantee a generic nature, making it applicable on a plethora of tasking problems and not case-specific. For any industrial setting in which mobile agents are responsible for accomplishing tasks across a site, the objective is to determine the optimal task schedule for each agent, which maximizes the speed of task achievement while minimizing the movement, thereby minimizing energy consumption cost. The DOT algorithm is presented in detail in this manuscript, starting from the conceptualization to the mathematical formulation based on graph theory, having a thorough computational implementation and a detailed algorithm benchmarking analysis. The choice of Dijkstra, as opposed to other shortest path methods (namely, A * Search and Bellman-Ford) in the proposed graph-based model and algorithm, was investigated and justified. An example of a real-world application based on a refinery site is modeled and simulated and the proposed algorithm's effectiveness and computational efficiency are duly evaluated. A dynamic obstacle course was incorporated to effectively demonstrate the proposed algorithm's applicability to real-world applications.

Dynamic shortest path algorithms are the ones which are used to accommodate the online sequence of update operations to the underlying graph topology and also facilitate the subsequent query operations. Many solutions exist for the different versions of the problem, all of which identify the set of vertices whose shortest paths may be affected by the changes and then update their shortest paths according to the update sequence. In this paper, we are dynamizing the Dijkstra algorithm which helps to efficiently solve the dynamic single source shortest path problem. Dynamization is achieved by using the retroactive priority queue data structure. Retroactive data structure identify the set of affected vertices step by step and thus help to accommodate the changes in least number of computations. So, with a suitable dynamic graph representation and the use of retroactive priority queue, we have proposed algorithm to dynamize Dijkstra algorithm giving solution of dynamic single source shortest path problem with complexity O(nlg m) for the update time. We have performed experimental analysis by comparing the performance of the proposed algorithm with other algorithms. Our experimental results indicate that the proposed algorithm has better performance in terms of time and memory usage.

Shortest path length methods are routinely used to validate whether genes of interest are functionally related to each other based on biological network information. However, the methods are computationally intensive, impeding extensive utilization of network information. In addition, non-weighted shortest path length approach, which is more frequently used, often treat all network connections equally without taking into account of confidence levels of the associations. On the other hand, graph-based information diffusion method, which employs both the presence and confidence weights of network edges, can efficiently explore large networks and has previously detected meaningful biological patterns. Therefore, in this study, we hypothesized that the graph-based information diffusion method could prioritize genes with relevant functions more efficiently and accurately than the shortest path length approaches. We demonstrated that the graph-based information diffusion method substantially differentiated not only genes participating in same biological pathways (p << 0.0001) but also genes associated with specific human drug-induced clinical symptoms (p << 0.0001) from random. Furthermore, the diffusion method prioritized these functionally related genes faster and more accurately than the shortest path length approaches (pathways: p = 2.7e-28, clinical symptoms: p = 0.032). These data show the graph-based information diffusion method can be routinely used for robust prioritization of functionally related genes, facilitating efficient network validation and hypothesis generation, especially for human phenotype-specific genes.

Creating a routing backbone is a fundamental problem in both biology and engineering. The routing backbone of the trail networks of arboreal turtle ants (Cephalotes goniodontus) connects many nests and food sources using trail pheromone deposited by ants as they walk. Unlike species that forage on the ground, the trail networks of arboreal ants are constrained by the vegetation. We examined what objectives the trail networks meet by comparing the observed ant trail networks with networks of random, hypothetical trail networks in the same surrounding vegetation and with trails optimized for four objectives: minimizing path length, minimizing average edge length, minimizing number of nodes, and minimizing opportunities to get lost. The ants’ trails minimized path length by minimizing the number of nodes traversed rather than choosing short edges. In addition, the ants’ trails reduced the opportunity for ants to get lost at each node, favoring nodes with 3D configurations most likely to be reinforced by pheromone. Thus, rather than finding the shortest edges, turtle ant trail networks take advantage of natural variation in the environment to favor coherence, keeping the ants together on the trails., Author summary We investigated the trail networks of arboreal turtle ants in the canopy of the tropical forest, to ask what characterizes the colony’s choice of foraging paths within the vegetation. We monitored day to day changes in the junctions and edges of trail networks of colonies in the dry forest of western Mexico. We compared the paths used by the ants to simulated random paths in the surrounding vegetation. We found that the paths of turtle ants prioritize coherence, keeping ants together on the trail, over minimizing the average edge length. The choice of paths reduces the number of junctions in the trail where ants could get lost, and favors junctions with a physical configuration that makes it likely that successive ants will reinforce the same path. Our work suggests that design principles that emphasize keeping information flow constrained to streamlined, coherent trails may be useful in human-designed distributed routing and transport networks or robot swarms.

Algorithms for finding the shortest path between two nodes in a graph have been heavily studied for decades. Half a century ago solutions were found for the specific class of problems that involves finding the path of least length, when edges are weighted with a single metric. For example, although the Bellman-Ford and Dijkstra algorithms use different methodologies, both techniques depend on a single metric where the lengths of paths are found by adding path weights in the conventional way. The situation becomes more complicated when multiple metrics or single metrics other than simple Euclidean distance are involved. In these cases, the definition of ``shortest,'' or ``best'' is not straightforward. In addition, it is not always a simple matter to verify that packets in a distributed network are forwarded on best paths that are guaranteed loop-free. We call the set of edge weights, plus the rules that determine how paths are concatenated and compared, the path algebra. We find that the structure of a path algebra is the key to understanding how packets will be forwarded in a distributed network; specifically whether they will be forwarded on best, loop-free paths. This is independent of any path-finding algorithm. We show that ``best'' paths and loop-free paths are separate (albeit subtly related) properties, that are dependent on whether or not a path algebra is monotonic and strictly bounded. We examine examples of path algebras that possess various combinations of those two properties in order to illustrate how they affect the construction of forwarding paths. Finally, we prove that if a path algebra is monotonic and strictly bounded, it is guaranteed to produce forwarding paths that are best and loop-free. Previous works have introduced these ideas in separate contexts. We provide a consistent framework and prove general concepts that have only been introduced or discussed in special cases.

Nearest neighbor (NN) and range (RN) queries are basic query types in spatial databases. In this study, we refer to collections of NN and RN queries as spatial proximity (SP) queries. At peak times, location-based services (LBS) need to quickly process SP queries that arrive simultaneously. Timely processing can be achieved by increasing the number of LBS servers, however, this also increases service costs. Existing solutions evaluate SP queries sequentially, thus, such solutions involve unnecessary distance calculations. This study proposes a unified batch algorithm (UBA) that can effectively process SP queries in dynamic spatial networks. With the proposed UBA, the distance between two points is indicated by the travel time on the shortest path connecting them. The shortest travel time changes frequently depending on traffic conditions. The goal of the proposed UBA is to avoid unnecessary distance calculations for nearby SP queries. Thus, the UBA clusters nearby SP queries and exploits shared distance calculations for query clusters. Extensive evaluations using real-world roadmaps demonstrated the superiority and scalability of UBA compared with state-of-the-art sequential solutions.

The five Platonic solids—tetrahedron, cube, octahedron, dodecahedron, and icosahedron—have found many applications in mathematics, science, and art. Path planning for the Platonic solids had been suggested, but not validated, except for solving the rolling-cube puzzles for a cubic dice. We developed a path-planning algorithm based on the breadth-first-search algorithm that generates a shortest path for each Platonic solid to reach a desired pose, including position and orientation, from an initial one on prescribed grids by edge-rolling. While it is straightforward to generate triangular and square grids, various methods exist for regular-pentagon tiling. We chose the Penrose tiling because it has five-fold symmetry. We discovered that a tetrahedron could achieve only one orientation for a particular position.

Recent epigenetics research has demonstrated that chromatin conformation plays an important role in various aspects of gene regulation. Chromosome Conformation Capture (3C) technology makes it possible to analyze the spatial organization of chromatin in a cell. Several algorithms for three-dimensional reconstruction of chromatin structure from 3C experimental data have been proposed. Compared to other algorithms, ShRec3D, one of the most advanced algorithms, can reconstruct a chromatin model in the shortest time for high-resolution whole-genome experimental data. However, ShRec3D employs a graph shortest path algorithm, which introduces errors in the resulting model. We propose an improved algorithm that optimizes shortest path distances using a genetic algorithm approach. The proposed algorithm and ShRec3D were compared using in silico 3C experimental data. Compared to ShRec3D, the proposed algorithm demonstrated significant improvement relative to the similarity between the algorithm's output and the original model with a reasonable increase to calculation time.

Graph-based groupwise image registration (G-GIR) aims to register a group of input images accurately without any bias. In G-GIR, an image similarity metric (ISM) is used to construct a graph that links similar images with graph edges. From the graph, a group center image and the shortest paths linking it to all other images can be determined. The deformation field aligning each image to the group center image can be obtained by composing sub-deformation fields that come from registration of adjacent images along the corresponding shortest path. The majority of ISMs used in G-GIR are based on image intensity. Since image intensity can be ambiguous and is not directly related to deformation directions, inconsistency problem in the sub-deformation fields along the shortest paths can occur. The word ``inconsistency'' mentioned here refers to the directions of deformation vectors in the sub-deformation fields along each shortest path are significantly different or even opposite at corresponding locations. Such problem can make G-GIR inefficient and easily to be trapped in local minimum. In this paper, we propose a new ISM for G-GIR, by which the consistency in the sub-deformation fields along the shortest paths can be significantly improved. We evaluate our method in comparison with three state-of-the-art ISMs using a common G-GIR framework. The experimental results with both toy and real images show that our method significantly improves registration accuracy.

A novel image feature set named histogram of triangular paths in graph (HoTPiG) is presented. The purpose of this study is to evaluate the feasibility of the proposed HoTPiG feature set through two clinical computer-aided detection tasks: nodule detection in lung CT images and aneurysm detection in head MR angiography images. The HoTPiG feature set is calculated from an undirected graph structure derived from a binarized volume. The features are derived from a 3-D histogram in which each bin represents a triplet of shortest path distances between the target node and all possible node pairs near the target node. First, the vessel structure is extracted from CT/MR volumes. Then, a graph structure is extracted using an 18-neighbor rule. Using this graph, a HoTPiG feature vector is calculated at every foreground voxel. After explicit feature mapping with an exponential-χ2 kernel, each voxel is judged by a linear support vector machine classifier. The proposed method was evaluated using 300 CT and 300 MR datasets. The proposed method successfully detected lung nodules and cerebral aneurysms. The sensitivity was about 80% when the number of false positives was three per case for both applications. The HoTPiG image feature set was presented, and its high general versatility was shown through two medical lesion detection applications.

Temporal behavior is an essential aspect of all biological systems. Time series have been previously represented as networks. Such representations must address two fundamental problems on how to: (1) Create appropriate networks to reflect the characteristics of biological time series. (2) Detect characteristic dynamic patterns or events as network temporal communities. General community detection methods use metrics comparing the connectivity within a community to random models, or are based on the betweenness centrality of edges or nodes. However, such methods were not designed for network representations of time series. We introduce a visibility-graph-based method to build networks from time series and detect temporal communities within these networks. To characterize unevenly sampled time series (typical of biological experiments), and simultaneously capture events associated to peaks and troughs, we introduce the Weighted Dual-Perspective Visibility Graph (WDPVG). To detect temporal communities in individual signals, we first find the shortest path of the network between start and end nodes, identifying high intensity nodes as the main stem of our community detection algorithm that act as hubs for each community. Then, we aggregate nodes outside the shortest path to the closest nodes found on the main stem based on the closest path length, thereby assigning every node to a temporal community based on proximity to the stem nodes/hubs. We demonstrate the validity and effectiveness of our method through simulation and biological applications.

International audience; We addressed comprehensively the performance of Shortest-Path HARP Refinement (SP-HR), SinMod, and DENSEanalysis using 2D slices of synthetic CSPAMM and DENSE images with realistic contrasts obtained from 3D phantoms. The three motion estimation techniques were interrogated under ideal and no-ideal conditions (with MR induced artifacts, noise, and throughplane motion), considering several resolutions and noise levels. Under noisy conditions, and for isotropic pixel sizes of 1.5 mm and 3.0 mm in CSPAMM and DENSE images respectively, the nRMSE obtained for the circumferential and radial strain components were 10. 7 ± 10.8% and 25.5 ± 14.8% using SP-HR, 11. 9 ± 2.5% and 29.3 ± 6.5% using SinMod, and 6.4 ± 2.0% and 2 18.2 ± 4.6% using DENSEanalysis. Overall, the results showed that SP-HR tends to fail for large tissue motions, whereas SinMod and DENSEanalysis gave accurate displacement and strain field estimations, being the last which performed the best.

We propose a method for calculating standard spatiotemporal gait parameters from individual human joints with a side-view depth sensor. Clinical walking trials were measured concurrently by a side-view Kinect and a pressure-sensitive walkway, the Zeno Walkway. Multiple joint proposals were generated from depth images by a stochastic predictor based on the Kinect algorithm. The proposals are represented as vertices in a weighted graph, where the weights depend on the expected and measured lengths between body parts. A shortest path through the graph is a set of joints from head to foot. Accurate foot positions are selected by comparing pairs of shortest paths. Stance phases of the feet are detected by examining the motion of the feet over time. The stance phases are used to calculate four gait parameters: stride length, step length, stride width, and stance percentage. A constant frame rate was assumed for the calculation of stance percentage because time stamps were not captured during the experiment. Gait parameters from 52 trials were compared to the ground truth walkway using Bland-Altman analysis and intraclass correlation coefficients. The large spatial parameters had the strongest agreements with the walkway (ICC(2, 1) = 1.00 and 0.98 for stride and step length with normal pace, respectively). The presented system directly calculates gait parameters from individual foot positions while previous side-view systems relied on indirect measures. Using a side-view system allows for tracking walking in both directions with one camera, extending the range in which the subject is in the field of view.

Many popular algorithms for searching the space of leaf-labelled (phylogenetic) trees are based on tree rearrangement operations. Under any such operation, the problem is reduced to searching a graph where vertices are trees and (undirected) edges are given by pairs of trees connected by one rearrangement operation (sometimes called a move). Most popular are the classical nearest neighbour interchange, subtree prune and regraft, and tree bisection and reconnection moves. The problem of computing distances, however, is $${\mathbf {N}}{\mathbf {P}}$$ N P -hard in each of these graphs, making tree inference and comparison algorithms challenging to design in practice. Although ranked phylogenetic trees are one of the central objects of interest in applications such as cancer research, immunology, and epidemiology, the computational complexity of the shortest path problem for these trees remained unsolved for decades. In this paper, we settle this problem for the ranked nearest neighbour interchange operation by establishing that the complexity depends on the weight difference between the two types of tree rearrangements (rank moves and edge moves), and varies from quadratic, which is the lowest possible complexity for this problem, to $${\mathbf {N}}{\mathbf {P}}$$ N P -hard, which is the highest. In particular, our result provides the first example of a phylogenetic tree rearrangement operation for which shortest paths, and hence the distance, can be computed efficiently. Specifically, our algorithm scales to trees with tens of thousands of leaves (and likely hundreds of thousands if implemented efficiently).

This paper presents an integrated model for energy consumption and range estimation, capable of energy-efficient routing. This integrated model predicts the energy consumption on all road segments in the road network and applies shortest path algorithms to calculate energy-efficient routes. A temperature-dependent model of the battery internal resistance based on real-world data translates the energy consumption prediction into driving range. The graph representation of the road network is transformed from a node-based graph to an edge-based graph to allow cost allocation of one edge based on the characteristics of the preceding edge. The integrated model is used to perform an analysis of energy-efficient routes for a real-life scenario. The analysis showed that the energy-optimal route is different from the time- and distance-optimal route with energy-efficiency gains up to 37% for the chosen scenario. The energy-efficient route tends to lean toward a distance-optimal route in the case of low auxiliary consumption and to lean toward a time-optimal route in the case of high auxiliary consumption. The energy-efficient route generation is tested in real life for one case of the chosen scenario. The measured results showed a good match with the predicted values for the energy consumption with a 9% mean relative error and preserved the ranking of all routes in terms of the travel distance, travel time, and energy consumption. The proposed integrated model is a functional model for energy consumption in real-life that differentiates many energy consumption influencing factors and produces energy-efficient routes with good accuracy.

Dubins tours represent a solution of the Dubins Traveling Salesman Problem (DTSP) that is a variant of the optimization routing problem to determine a curvature-constrained shortest path to visit a set of locations such that the path is feasible for Dubins vehicle, which moves only forward and has a limited turning radius. The DTSP combines the NP-hard combinatorial optimization to determine the optimal sequence of visits to the locations, as in the regular TSP, with the continuous optimization of the heading angles at the locations, where the optimal heading values depend on the sequence of visits and vice versa. We address the computationally challenging DTSP by fast evaluation of the sequence of visits by the proposed Windowing Surrogate Model (WiSM) which estimates the length of the optimal Dubins path connecting a sequence of locations in a Dubins tour. The estimation is sped up by a regression model trained using close to optimum solutions of small Dubins tours that are generalized for large-scale instances of the addressed DTSP utilizing the sliding window technique and a cache for already computed results. The reported results support that the proposed WiSM enables a fast convergence of a relatively simple evolutionary algorithm to high-quality solutions of the DTSP. We show that with an increasing number of locations, our algorithm scales significantly better than other state-of-the-art DTSP solvers.

The One-to-one Pickup and Delivery Problem with Shortest-path Transport along Real-life Paths (OPDPSTRP) is presented in this paper. It is a variation of the One-to-one Pickup and Delivery Problem (OPDP), which is common in daily life, such as the Passenger Train Operation Plans (PTOP) and partial Taxi-sharing Problem. Unlike the classical OPDP, in the OPDPSTRP, (1) each demand must be transported along the shortest path according to passengers/shippers requirements, and (2) each vehicle should travel along a real-life path. First, six route structure rules are proposed for the OPDPSTRP, and a kind of Mixed-Integer Programming (MIP) models is formulated for it. Second, A Variable Neighborhood Descent (VND), a Variable Neighborhood Research (VNS), a Multi-Start VND (MS_VND) and a Multi-Start VNS (MS_VNS) with five neighborhood operators has been developed to solve the problem. Finally, The Gurobi solver, the VND, the VNS, the MS_VND and the MS_VNS have been compared with each other by 84 random instances partitioned in small size connected graphs, medium size connected graphs and large size connected graphs. From the test results we found that solutions generated by these approaches are often comparable with those found by the Gurobi solver, and the solutions found by these approaches are better than the solutions found by the Gurobi solver when solving instances with larger numbers of demands. In almost all instances, the MS_VND significantly outperforms the VND and the VNS in terms of solution quality, and outperforms the MS_VNS both in terms of solution quality and CPU time. In the instances with large numbers of demands, the MS_VND is still able to generate good feasible solutions in a reasonable CPU time, which is of vital practical significance for real-life instances.

Node-link diagrams are widely used to visualise networks. However, even the best network layout algorithms ultimately result in 'hairball' visualisations when the graph reaches a certain degree of complexity, requiring simplification through aggregation or interaction (such as filtering) to remain usable. Until now, there has been little data to indicate at what level of complexity node-link diagrams become ineffective or how visual complexity affects cognitive load. To this end, we conducted a controlled study to understand workload limits for a task that requires a detailed understanding of the network topology---finding the shortest path between two nodes. We tested performance on graphs with 25 to 175 nodes with varying density. We collected performance measures (accuracy and response time), subjective feedback, and physiological measures (EEG, pupil dilation, and heart rate variability). To the best of our knowledge, this is the first network visualisation study to include physiological measures. Our results show that people have significant difficulty finding the shortest path in high-density node-link diagrams with more than 50 nodes and even low-density graphs with more than 100 nodes. From our collected EEG data we observe functional differences in brain activity between hard and easy tasks. We found that cognitive load increased up to a certain level of difficulty after which it decreased, likely because participants had given up. We also explored the effects of global network layout features such as size or number of crossings, and features of the shortest path such as length or straightness on task difficulty. We found that global features generally had a greater impact than those of the shortest path., Comment: To be presented at IEEE Conference on Information Visualization (InfoVis 2020)

The anatomical therapeutic chemical (ATC) classification system is a widely accepted drug classification scheme. This system comprises five levels and includes several classes in each level. Drugs are classified into classes according to their therapeutic effects and characteristics. The first level includes 14 main classes. In this study, we proposed two network-based models to infer novel potential chemicals deemed to belong in the first level of ATC classification. To build these models, two large chemical networks were constructed using the chemical-chemical interaction information retrieved from the Search Tool for Interactions of Chemicals (STITCH). Two classic network algorithms, shortest path (SP) and random walk with restart (RWR) algorithms, were executed on the corresponding network to mine novel chemicals for each ATC class using the validated drugs in a class as seed nodes. Then, the obtained chemicals yielded by these two algorithms were further evaluated by a permutation test and an association test. The former can exclude chemicals produced by the structure of the network, i.e., false positive discoveries. By contrast, the latter identifies the most important chemicals that have strong associations with the ATC class. Comparisons indicated that the two models can provide quite dissimilar results, suggesting that the results yielded by one model can be essential supplements for those obtained by the other model. In addition, several representative inferred chemicals were analyzed to confirm the reliability of the results generated by the two models. This article is part of a Special Issue entitled: Accelerating Precision Medicine through Genetic and Genomic Big Data Analysis edited by Yudong Cai & Tao Huang.