Search

This work proposes a hybrid path-planning algorithm, the HE* algorithm, which combines the discrete grid-based E* search and continuous Bernstein-Bézier (BB) motion primitives. Several researchers have addressed the smooth path planning problem and the sample-based integrated path planning techniques. We believe that the main benefits of the proposed approach are: directly drivable path, no additional post- optimization tasks, reduced search branching, low computational complexity, and completeness guarantee. Several examples and comparisons with the state of the art planners are provided to illustrate and evaluate the main advantages of the HE* algorithm. HE* yields a collision-safe and smooth path that is close to spatially optimal (the Euclidean shortest path) with a guaranteed continuity of curvature. Therefore, the path is easily drivable for a wheeled robot without any additional post- optimization and smoothing required. HE* is a two- stage algorithm which uses a direction-guiding heuristics computed by the E* search in the first stage, which improves the quality and reduces the complexity of the hybrid search in the second stage. In each iteration, the search is expanded by a set of BBs, the parameters of which adapt continuously according to the guiding heuristics. Completeness is guaranteed by relying on a complete node mechanism, which also provides an upper bound for the calculated path cost. A remarkable feature of HE* is that it produces good results even at coarse resolutions.

Due to the time-varying characteristics of energy harvesting sources, it is a challenge for energy harvesting to provide stable energy output. In this article, the time fair energy allocation (TFEA) problem is investigated, and an utility maximization framework is proposed to guarantee both time fairness and energy efficiency of energy allocation. Then we propose a prediction based energy allocation scheme. First, a deep learning predictor is used to predict the harvested energy. Second, we transform the TFEA problem into an Euclidean shortest path problem and propose a fast time fair energy allocation algorithm (FTF) based on inflection points search. Our algorithm can significantly decrease the iteration number of the shortest path search and reduce the computation time. In addition, we propose an edge computing assisted energy allocation framework, in which the computing tasks are offloaded to edge gateways. The proposed scheme is evaluated in the scenario of metro vehicles health monitoring. Experiment results show that the time consumption of FTF is at least 92.2% lower than traditional algorithms, while the time fairness of FTF is the best. The total time cost and energy cost of our edge computing scheme is also competitive compared with traditional local computing schemes.

We present an optimal algorithm for determining a time-minimal rectilinear path among transient rectilinear obstacles. An obstacle is transient if it exists only for a specific time interval, i.e., it appears and then disappears at specific times. Given a point robot moving with bounded speed among non-intersecting transient rectilinear obstacles and a pair of points (s, d), we determine a time-minimal, obstacle-avoiding path from s to d. Our algorithm runs in $$\varTheta (n \log n)$$ time, where n is the total number of vertices in the obstacle polygons. The main challenge in solving this problem arises when the robot may be required to wait for an obstacle to disappear, before it can continue moving towards its destination. Our algorithm builds on the continuous Dijkstra paradigm, which simulates propagating a wavefront from the source point. We also present an $$O(n^2 \log n)$$ time algorithm for computing the Euclidean shortest path map among transient polygonal obstacles in the plane. This decreases the time complexity of the existing algorithm (Fujimura, in: Proceedings 1992 IEEE international conference on robotics and automation, vol 2, pp 1488–1493, 1992. https://doi.org/10.1109/ROBOT.1992.220041 ) by a factor of n. The shortest path map can be preprocessed for point location, after which a shortest path query from s to any point d can be answered in time $$O(\log n + k)$$ where, k is the number of edges in the path.

Path planning relies on free-space expansions. The Ray Path Finder (RPF) and RayScan algorithms solve the Euclidean shortest path problem. Both rely on free-space expansions by basing on the bug concept, which is to cast rays to a desired target and trace any obstructing contours. By combining heuristic costs, an optimal path can be found. In this work, a new and insightful analysis aiding future designs of this class of heuristic bug-based planners is provided. A rigorous proof for a modified Pledge in RPF is included. A corrected RPF prototype is designed to compare with Anya, a state-of-the-art free-space planner. The computational advantages of the heuristic bug-baed planners can offer are provided.

Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. Previously, Hershberger and Suri [SIAM J. Comput. 1999] gave an algorithm of $O(n\log n)$ time and $O(n\log n)$ space, where $n$ is the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suri's algorithm, Wang [SODA 2021] reduced the space to $O(n)$ while the runtime of the algorithm is still $O(n\log n)$. In this paper, we present a new algorithm of $O(n+h\log h)$ time and $O(n)$ space, provided that a triangulation of the free space is given, where $h$ is the number of obstacles. The algorithm, which improves the previous work when $h=o(n)$, is optimal in both time and space as $\Omega(n+h\log h)$ is a lower bound on the runtime. Our algorithm builds a shortest path map for a source point $s$, so that given any query point $t$, the shortest path length from $s$ to $t$ can be computed in $O(\log n)$ time and a shortest $s$-$t$ path can be produced in additional time linear in the number of edges of the path., Comment: To appear in STOC 2021

Routing service considering uncertainty is at the core of intelligent transportation systems and has attracted increasing attention. Existing stochastic shortest path models require the exact probability distributions of travel times and usually assume that they are independent. However, the distributions are often unavailable or inaccurate due to insufficient data, and correlation of travel times over different links has been observed. This paper presents a robust shortest path (RSP) model that only requires partial distribution information of travel times, including the support set, mean, variance, and correlation matrix. We introduce a concept of robust mean-excess travel time to hedge against the risk from both the uncertainty of the random travel times and the uncertainty in their distributions. To solve the RSP problem, an equivalent dual formulation is derived and used to design tight lower and upper bound approximation methods, which adopt the scenario approach and semi-definite programming approach, respectively. To solve large problems, we further propose an efficient primal approximation method, which only needs to solve two deterministic shortest path problems and a mean-standard deviation shortest path problem, and analyze its approximation performance. Experiments validate the tightness of the proposed bounds and demonstrate the impact of uncertainty on the relative benefit and cost of robust paths.

We consider optimal and suboptimal algorithms for the Euclidean Shortest Path Problem (ESPP) in two dimensions. For optimal path planning, Our approach leverages ideas from two recent works: Polyanya, a mesh-based ESPP planner which we use to represent and reason about the environment, and Compressed Path Databases (CPD), a speedup technique for pathfinding on grids and spatial networks, which we exploit to efficiently compute candidate paths, in order to construct a completely novel ESPP algorithm, End Point Search (EPS). In a range of experiments and empirical comparisons we show that: (i) the auxiliary data structures required by EPS are cheap to build and store; (ii) for optimal search, the new algorithm is faster than a range of recent ESPP planners, with speedups ranging from several factors to over one order of magnitude; (iii) for anytime search, where feasible solutions are needed fast, we report even better performance. For suboptimal path planning, we extend the CPD such that it computes and compresses first move data of a larger number of selected candidate nodes covering every point in the Euclidean space. Our approach is search-free, simultaneously fast, and returns a path within a fixed bound of the optimal solution. In a range of empirical results, we show that: (i) our approach outperforms both offline/online optimal and suboptimal ESPP algorithms proposed in the literature; (ii) our approach demonstrates excellent path quality, better than all existing suboptimal ESPP algorithms; and (iii) the approach offers flexibility by allowing a trade-off between the CPD construction cost (space and time) and the suboptimality bound.

A multi-pass sequential localized search technique to solve the problem of path planning of hyper-redundant manipulators for the shortest path in real-time in the presence of obstacles is proposed. The problem is approached from a control perspective as a shortest path optimal control problem, where the configuration space is searched for path points that optimize a cost function. This method addresses the “curse of dimensionality” of exhaustive search techniques via a multi-pass sequential localized search, and sensitivity to local minima of greedy approaches via a backtracking technique. Further, theoretical proof shows that the proposed technique converges to a global optimal (if only one exists) or a suboptimal (if many exist) solution. The algorithm is implemented on a 6-DOF PUMA 560 and a 9-DOF hyper-redundant manipulator arm and simulation results are analyzed for cost and time of execution.

Shortest path problem in real life applications has to deal with multiple criteria. This article intends to solve a proposed multi-criteria shortest path problem of a weighted connected directed network whose associated edge weights are represented as rough variables in order to tackle the imprecision. We have exhibited two different approaches to determine the optimum path(s) of the proposed problem. The first approach is the proposed modified rough Dijkstra’s labelling algorithm. The second approach considers the rough chance constrained programming technique to formulate the proposed multi-criteria shortest path problem which is eventually solved by two different methods: the goal attainment method and the nondominated sorting genetic algorithm II. These methodologies are numerically illustrated for a multi-criteria weighted connected directed network. Moreover, the simulated results on similar networks of large order and size are analyzed to show the efficiency of the algorithms.

In the resource constrained shortest path problem we are given a directed graph along with a source node and a destination node, and each arc has a cost and a vector of weights specifying its requirements from a set of resources with finite budget limits. A minimum cost source-destination path is sought such that the total consumption of the arcs from each resource does not exceed its budget limit. In the case of constant number of weight functions we give a fully polynomial time multi-criteria approximation scheme for the problem which returns a source-destination path of cost at most the optimum, however, the path may slightly violate the budget limits. On the negative side, we show that there does not exist a polynomial time multi-criteria approximation scheme for the problem if the number of weight functions is not a constant. The latter result applies to a broad class of problems as well, including the multi-dimensional knapsack, the multi-budgeted spanning tree, the multi-budgeted matroid basis and the multi-budgeted bipartite perfect matching problems.

Given an arbitrary directed graph G = ( V , E ) with non-negative edge lengths, we present an algorithm that computes all pairs shortest paths in time O ( m ∗ n + m lg n + n T ψ ( m ∗ , n ) ) , where m ∗ is the number of different edges contained in shortest paths and T ψ ( m ∗ , n ) is the running time of an algorithm ψ solving the single-source shortest path problem (SSSP). This is a substantial improvement over a trivial n times application of ψ that runs in O ( n T ψ ( m , n ) ) . In our algorithm we use ψ as a black box and hence any improvement on ψ results also in improvement of our algorithm. A combination of our method, Johnson’s reweighting technique and topological sorting results in an O ( m ∗ n + m lg n ) all-pairs shortest path algorithm for directed acyclic graphs with arbitrary edge lengths. We also point out a connection between the complexity of a certain sorting problem defined on shortest paths and SSSP. Finally, we show how to improve the performance of the proposed algorithm in practice. We then empirically measure the running times of various all-pairs shortest path algorithms on randomly generated graph instances and obtain very promising results.

In this paper, we introduce and investigate the Minimum Eccentricity Shortest Path (MESP) problem in unweighted graphs. It asks for a given graph to find a shortest path with minimum eccentricity. Let n and m denote the number of vertices and the number of edges of a given graph. We demonstrate that: • a minimum eccentricity shortest path plays a crucial role in obtaining the best to date approximation algorithm for a minimum distortion embedding of a graph into the line; • the MESP problem is NP-hard for planar bipartite graphs with maximum degree 3 and W[2]-hard for general graphs; • a shortest path of minimum eccentricity k can be computed in O ( n 2 k + 2 m ) time; • a 2-approximation, a 3-approximation, and an 8-approximation for the MESP problem can be computed in O ( n 3 ) time, in O ( n m ) time, and in O ( m ) time, respectively; • in a graph with a shortest path of eccentricity k, a k-dominating set can be found in n O ( k ) time.

In todays Internet, the shortest path tree (SPT) construction is an important issue in data exchange. To forward a data packet, each router uses routing protocols and link state information to identify the shortest paths from itself to other routers, which yields the shortest path tree. In reality, the network topology often varies over time. In existing studies, the locally affected nodes are identified and the shortest paths are recomputed so as to update the SPT. However, when the network size becomes large, the process of reconstructing the shortest paths for the affected nodes is very time consuming. Herein, we propose an adaptive amoeba method to build SPT in dynamic graphs. The proposed method is illustrated using a three-step procedure. First, we generalize the original Physarum model to enable it to have the ability to find the shortest paths in directed graphs. Secondly, the Physarum model is further extended to construct the shortest path tree when there are multiple sink nodes. Finally, we demonstrate that the developed method is capable of reconstructing the SPT by adapting the tube flow when link weight changes occur. Different from previous methods, the proposed algorithm is capable of identifying and recomputing the shortest paths for the affected nodes as well as maintaining the original paths for the unaffected vertices spontaneously. We demonstrate the performance of the proposed algorithm by comparing it with the Label Setting algorithm and Dijkstra algorithm in four randomly generated graphs. The computational results suggest the most appropriate algorithms to be used in different scenarios.

We study the problem of finding a short path from a start to a goal within a two-dimensional continuous and isotropic terrain that has been discretized into an array of accessible and blocked cells. A classic approach obtains a grid path where each step is along the edge of an accessible cell or diagonally across one. Grid paths suffer from `digitization bias' -- even if two locations have line-of-sight, the minimum travelling cost between them can be greater than the distance along the line-of-sight. In a vertex path, steps are allowed from a cell corner to any other cell corner if they have line-of-sight. While the `digitization bias' is smaller, shortest vertex paths are impractical to find by brute force. Recent research has thus turned to methods for finding short (but not necessarily shortest) vertex paths. To establish the methods' potential utility, we calculate upper bounds on the difference in length between the shortest vertex paths versus the shortest r-constrained ones where an r-constrained path consists of line segments that each traverse at most r rows and at most r columns of cells. The difference in length reduces as r increases -- indeed the shortest vertex paths are at most 1 percent shorter than the shortest 4-constrained ones. This article will be useful to developers and users of short(est) vertex paths algorithms who want to trade path length for improved runtimes in a predictable manner.

This paper is concerned with a biobjective routing problem, called the shortest path with shortest detour problem, in which the length of a route is minimized as one criterion and, as second, the maximal length of a detour route if the chosen route is blocked is minimized. Furthermore, the relation to robust optimization is pointed out, and we present a new polynomial time algorithm, which computes a minimal complete set of efficient paths for the shortest path with shortest detour problem. Moreover, we show that the number of nondominated points is bounded by the number of arcs in the graph.

Path planning has become a central problem in motion planning. The classic version of the problem aims to find an obstacle-free path with the minimum length for a given workspace containing a set of obstacles and two sources and destination points. However, some real world applications consider maximizing the path clearance (i.e.,the distance between the robot and obstacles) as the secondary objective. This bi-objective path planning problem has been studied using evolutionary and other heuristic algorithms which do not guarantee achieving Pareto optimal paths. In this paper, we first study this problem using deterministic algorithms. Next, we propose an efficient algorithm for the problem in the grid workspace. We then propose an O(n3) time algorithm for the problem under the Manhattan distance in a continuous workspace containing n vertical segments as obstacles. Finally, we show the obtained solutions are proper approximation for the problem under the Euclidean distance. Introducing a bi-objective length and clearance path planning (bi-PP) model.Proposing an algorithm for solving the bi-PP in grid and finding Pareto fronts.Proposing an algorithm for solving the bi-PP in continuous Manhattan space.Approximating Pareto solutions of the bi-PP under the Euclidean distance.

Shortest path problem in stochastic graphs has been recently studied in the literature and a number of algorithms has been provided to find it using varieties of learning automata models. However, all these algorithms suffer from two common drawbacks: low speed and lack of a clear termination condition. In this paper, we propose a novel learning automata-based algorithm for this problem which can speed up the process of finding the shortest path using parallelism. For this parallelism, several traverses are initiated, in parallel, from the source node towards the destination node in the graph. During each traverse, required times for traversing from the source node up to any visited node are estimated. The time estimation at each visited node is then given to the learning automaton residing in that node. Using different time estimations provided by different traverses, this learning automaton gradually learns which neighbor of the node is on the shortest path. To set a condition for the termination of the proposed algorithm, we analyze the algorithm using a recently introduced model, Adaptive Stochastic Petri Net (ASPN-LA). The results of this analysis enable us to establish a necessary condition for the termination of the algorithm. To evaluate the performance of the proposed algorithm in comparison to the existing algorithms, we apply it to find the shortest path in six different stochastic graphs. The results of this evaluation indicate that the time required for the proposed algorithm to find the shortest path in all graphs is substantially shorter than that required by similar existing algorithms.

In this paper, a unified scheme is proposed for solving the classical shortest path problem and the generalized shortest path problem, which are highly nonlinear. Particularly, the generalized shortest path problem is more complex than the classical shortest path problem since it requires finding a shortest path among the paths from a vertex to all the feasible destination vertices. Different from existing results, inspired by the optimality principle of Bellman’s dynamic programming, we formulate the two types of shortest path problems as linear programs with the decision variables denoting the lengths of possible paths. Then, biased consensus neural networks are adopted to solve the corresponding linear programs in an efficient and distributed manner. Theoretical analysis guarantees the performance of the proposed scheme. In addition, two illustrative examples are presented to validate the efficacy of the proposed scheme and the theoretical results. Moreover, an application to mobile robot navigation in a maze further substantiates the efficacy of the proposed scheme.

In this study, we propose an exact method for finding all the Pareto-optimal paths for a multi-criteria constrained shortest path problem. We show that solving the special bi-criteria problem is equivalent to generating at most | P | constrained shortest paths with successive tightened constraints, where | P | is the total number of all Pareto-optimal paths. For the general multi-criteria case, we propose a decomposition procedure and theoretically prove that this method can identify all the Pareto-optimal paths from at most ( u - 1 ) ! | P | candidate paths, where u is the number of criteria. Numerical studies demonstrate that our algorithm is highly efficient and robust.

In this research paper the author introduces the notion of i-v fuzzy multigraph. The classical Dijkstra’s algorithmic rule to search out the shortest path in graphs isn't applicable to fuzzy graph theory. Consequently the author proposes a brand new algorithmic rule referred to as by IVF-Dijkstra's algorithmic rule with the philosophy of the classical Dijkstra's formula to unravel the SPP in an i-v fuzzy multigraph

In this paper the author introduces the notion of Z-weighted graph or Z-graph in Graph Theory, considers the Shortest Path Problem (SPP) in a Z-graph. The classical Dijkstra’s algorithm to find the shortest path in graphs is not applicable to Z-graphs. Consequently the author proposes a new algorithm called by Z-Dijkstra's Algorithm with the philosophy of the classical Dijkstra's Algorithm to solve the SPP in a Z-graph.

The persistent alternation of the internet world is changing networks rapidly. Shortest path discovery, especially over dynamic networks such as web page links, telephone or route networks, and ontologies, has received intense attention because of its importance for services in IoT. For example, when a new road is newly opened or becomes unavailable for any unexpected reason, the shortest paths must be recomputed. The system should respond promptly to its users with the updated recommended paths. In this paper, we propose a disk-based shortest path method that updates the shortest paths in a very large dynamic graph efficiently. The proposed method uses partial shortest paths as indices for efficient shortest path discovery. We classify the changes in the graph into four cases, such as the insertion or deletion of edges and the increase or decrease of edge weights. Our proposed strategy considers updating only the corresponding parts of the indices for each case. Our experiments on real-world dynamic datasets verify that the proposed framework updates the shortest paths 4 to 50 times faster than the existing type of framework.

We consider the single-source shortest paths problem in a digraph with negative edge costs allowed. A hybrid of the BellmanFord and Dijkstra algorithms is suggested, improving the running time bound of BellmanFord for graphs with a sparse distribution of negative cost edges. The algorithm iterates Dijkstra several times without re-initializing the tentative value d(v) at vertices. At most k+2 iterations solve the problem, if for any vertex reachable from the source, there exists a shortest path to it with at most k negative cost edges.In addition, a new, straightforward proof is suggested that the BellmanFord algorithm produces a shortest paths tree.

The shortest path problem is a classical combinatorial optimization problem with countless real-life applications. Numerous algorithms have been proposed to solve the SPP since the classical Dijkstra algorithm, as well as new approaches to improve the algorithms’ optimality. But according to the real-world transport conditions, researchers began to study variants of this problem which include the time-dependent SPP and the multimodal networks. In this paper, we introduce our new time-dependent shortest path algorithm for multimodal transportation network. The proposed algorithm is a goal-oriented single-source single-destination algorithm. It takes into account the concept of “closeness” to the target node as heuristic to drive the search towards its destination. The optimality of the algorithm is principally based on computing a virtual path which is basically an Euclidean distance from the source to the target aiming at a restriction of the search space.

Pseudo-random sequence generators are widely used in many areas, such as stream ciphers, radar systems, Monte-Carlo simulations and multiple access systems. Generalization of linear feedback shift registers (LFSRs) and feedback with carry shift registers (FCSRs), algebraic feedback shift registers (AFSRs) [ 7 ] can generate pseudo-random sequences over an arbitrary finite field. In this paper, we present an algorithm derived from the Extended Euclidean Algorithm that can efficiently find a smallest AFSR over a quadratic field for a given sequence. It is an analog of the Extended Euclidean Rational Approximation Algorithm [ 1 ] used in solving the FCSR synthesis problem. For a given sequence $\mathbf{a}$, $2\Lambda(\alpha)+1$ terms of sequence $\mathbf{a}$ are needed to find the smallest AFSR, where $\Lambda(\alpha)$ is a complexity measure that reflects the size of the smallest AFSR that outputs $\mathbf{a}$.

An improved method of approaching the calculation of maximum flow is developed, which implies applying the method of trees and capacities of tabular processors. The solution can be extended for a problem with several sources and runoffs. This will solve the problem on the optimization of transportation networks with and without limitations in throughput capacity. We designed an improved method for calculating the shortest path, which is resolved by using the Minty Dijkstra's algorithm. By solving the shortest path problem, we receive the shortest route and a list of vertices that it passes. By having indicators of freight traffic from each vertex to all others, we build a tree of the shortest paths. Going from one vertex to another vertex, we obtain density of traffic in the network without limitation in the throughput capacity. When the network has a throughput capacity limitation, imposing flows on the network is a bit complicated. In this case, it is necessary to subtract each elementary flow from the existing throughput capacity of the arc, on which it is imposed. For finding the shortest path, it is possible to correct the flows manually. The process of transforming network models for the process of cargo transportation to the matrix models is presented, through the use of the modified Dijkstra's algorithm. Elements of transportation networks in this case are set in the form of directed graphs. Graphic representation of the results of solving a network traffic problem is given.

This main purpose of this paper is to develop an algorithm to find the shortest path on a network in which the weights of the edges are represented by bipolar neutrosophic numbers. Finally, a numerical example has been provided for illustrating the proposed approach.

When shortest path algorithm be used in real time road network monitoring system, the time complexity of the algorithm is becoming the bottleneck of the system. the paper proposes a solution to improve the shortest path algorithm. By making use of the k-ary-reverse tree and locality principle, this improved algorithm keeps the data operation, in priority queue, be localized in a small range. So the time complexity of this improved shortest path algorithm is optimized from O(nlog2n) to $$O(k\times n)$$O(k×n); the parameter k denotes the average count of adjacency edges to each vertex, and n denotes the total count of vertexes in the network. Note that, the parameter k mainly depends on the edges density in the network. Generally speaking, the mean value of parameter k is not more than 4 in the road network, i.e. the time complexity of the improved algorithm is optimized from O(nlog2n) to O(n) in the road network. So the paper makes a conclusion that there is a linear correlation between the time complexity and the vertexes count n in the improved algorithm.

Shortest path is a fundamental graph problem with numerous applications. However, the concept of classic shortest path is insufficient. In this paper, we study various concepts of “shortest” path in temporal graphs, called minimum temporal paths. Computing these minimum temporal paths is challenging as subpaths of a “shortest” path may not be “shortest” in a temporal graph. We propose efficient algorithms to compute minimum temporal paths and verified their efficiency using large real-world temporal graphs.

We establish a powerful construction of D-optimal Euclidean designs, or D-optimal rotatable designs, on the unit hyperball by using the corner vectors associated with the symmetry groups of (semi-)regular polytopes. This is a full generalization of the classical construction choosing points in the form (a,…,a,0,…,0) or in their orbits under the symmetry group of a regular hyperoctahedron (Gaffke and Heiligers 1995b), (Hirao et al. 2014), as well as Scheffe’s {n, 2}-lattice design on the simplex. We prove a Gaffke-Heiligers type theorem for D n - and A n -invariant D-optimal Euclidean designs which is a “reduction theorem” on the computational cost of searching observation points, and thereby construct many families of D-optimal Euclidean designs. For each group A n , D n , B n , H 3, H 4, F 4, E 6, E 7, E 8, we determine the maximum degree of a D-optimal Euclidean design constructed by our method and in particular discover examples of degrees 5 and 6 for E 8 and H 4, respectively. We also classify such maximum-degree designs for the groups H 3, H 4 and F 4 acting on the 3- and 4-dimensional Euclidean spaces.